Evaluating Search Strategies in Dynamic Symbolic Execution for Java Test Generation

Abstract

Dynamic symbolic execution (DSE) is a powerful technique for automated test generation, but its effectiveness largely depends on the search strategy used to explore program paths. This thesis introduces MAZE, a modular DSE engine for Java bytecode grounded in a formal operational semantics. MAZE distinguishes itself from existing Java-based DSE tools through its modular architecture supporting diverse search strategies and their arbitrary combinations, enabling the systematic comparison of strategies.

We evaluate six distinct search strategies, including coverage-guided, constraint complexityguided, and hybrid approaches that combine complementary techniques. These are applied to 10 Java classes chosen for their diverse control flow, floating-point operations, and objectoriented features, with effectiveness measured by line and branch coverage and mutant kill ratio. Informed, state-aware strategies consistently outperform default approaches such as depth-first (DFS) and breadth-first search (BFS). Notably, BFS consistently outperforms DFS across most benchmarks, suggesting it may serve as a more suitable default. However, strategy effectiveness is still context-sensitive, with certain strategies excelling in floating-point-heavy or recursive code. Consequently, interleaved strategies tend to perform best by combining the strengths of multiple techniques.

While MAZE outperforms non-DSE tools such as EvoSuite and Randoop on our benchmark set, its current support for only a subset of Java limits evaluation on large-scale open-source projects. Nevertheless, the controlled environment allows for isolating the impact of different search strategies. Our findings highlight that search strategy design plays a central role in improving DSE-based test generation.