Abstract
Legion is a grey-box coverage-based concolic testing tool designed to balance the complementary strengths of fuzzing and symbolic execution. By formulating program exploration as a sequential decision-making problem under uncertainty, Legion utilizes a variation of Monte Carlo Tree Search (MCTS) to guide its search strategy. Central to its approach is Approximate Path-Preserving Fuzzing (APPF), a novel constrained random testing technique that generates diverse inputs targeting specific program regions. In the Test-Comp 2020 competition, Legion demonstrated high efficacy, performing within 90% of the best-in-class scores in 9 out of 22 categories and excelling in benchmarks involving deep loops.
Introduction
Automated software testing typically relies on two primary paradigms: fuzzing and symbolic execution. Fuzzing is highly efficient at exploring shallow code but often fails at "choke points"—specific conditional statements (e.g., if (x == 123456)) that are statistically improbable to satisfy through random mutation. Symbolic execution offers the precision to solve these constraints but is frequently crippled by "path explosion," where the number of possible execution paths grows exponentially with program complexity.
Legion seeks the "Goldilocks zone" by combining these techniques. It treats the challenge of when to solve a constraint versus when to use random exploration as a strategic decision-making problem, aiming to achieve high code coverage and identify elusive bugs without succumbing to the limitations of either individual method.
Methodology
Legion introduces a "best-first" concolic (Concrete + Symbolic) testing framework built upon two core innovations:
MCTS-Guided Exploration
Legion models the program's execution tree as a game board, employing Monte Carlo Tree Search (MCTS) to determine which paths to prioritize. By using the Upper Confidence Bound for Trees (UCT) score, the tool balances exploration (investigating uncertain or new paths) and exploitation (deepening the search in paths that have already yielded high coverage or interesting behavior).
Approximate Path-Preserving Fuzzing (APPF)
When MCTS identifies a target path, Legion employs APPF rather than standard fuzzing. APPF is a mutation-based algorithm that generates a high volume of diverse inputs while attempting to maintain the constraints of the selected path. This keeps the fuzzer focused on specific, interesting code regions that symbolic execution has identified as reachable. The prototype is implemented in Python 3, utilizing the angr symbolic execution engine and the Z3 constraint solver.
Experimental Evaluation
The tool was evaluated using the Test-Comp 2020 benchmarks, which include diverse C programs designed to test recursion, deep loops, and complex equality constraints.
Key Results
- Competitive Performance: Legion achieved scores within 90% of the top-performing tools in 9 of 22 categories. In the
cover-branchescategory, it reached this threshold in 7 out of 13 sub-categories. - Deep Loop Proficiency: Legion demonstrated a unique ability to handle deep loops and corner cases. In the
standard_copy*benchmarks, Legion succeeded in 9 out of 18 cases, whereas all other competing tools failed to achieve full marks. - Strategic Instrumentation: By identifying and omitting loop guards that only evaluate one way, Legion focuses its computational resources on "interesting" decisions, such as assertions within loops that are likely to contain bugs.
Limitations and Future Work
While successful, the authors noted several areas for refinement. The current instrumentation introduces significant performance overhead, which the team intends to mitigate by using Intel PIN for binary tracing. Additionally, Legion currently struggles with long chains of equality constraints (e.g., in bitvector sets) where fuzzing provides little reward. Future iterations will focus on fine-tuning the MCTS exploration ratio and implementing periodic memory pruning to prevent exhaustion during long execution traces.
Summary updated