  Concolic execution and fuzzing are two complementary coverage-based testing
techniques. How to achieve the best of both remains an open challenge. To
address this research problem, we propose and evaluate Legion. Legion
re-engineers the Monte Carlo tree search (MCTS) framework from the AI
literature to treat automated test generation as a problem of sequential
decision-making under uncertainty. Its best-first search strategy provides a
principled way to learn the most promising program states to investigate at
each search iteration, based on observed rewards from previous iterations.
Legion incorporates a form of directed fuzzing that we call approximate
path-preserving fuzzing (APPFuzzing) to investigate program states selected by
MCTS. APPFuzzing serves as the Monte Carlo simulation technique and is
implemented by extending prior work on constrained sampling. We evaluate Legion
against competitors on 2531 benchmarks from the coverage category of Test-Comp
2020, as well as measuring its sensitivity to hyperparameters, demonstrating
its effectiveness on a wide variety of input programs.
