LEGION: Best-First Concolic Testing
Dongge Liu, Gidon Ernst, Toby Murray, Benjamin IP Rubinstein
2020 35TH IEEE/ACM INTERNATIONAL CONFERENCE ON AUTOMATED SOFTWARE ENGINEERING (ASE 2020) | IEEE COMPUTER SOC | Published : 2020
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) ..View full abstract
This research was supported by Data61 under the Defence Science and Technology Group's Next Generation Technologies Program.