Legion: Best-First Concolic Execution

Legion: Best-First Concolic Execution

Cybersecurity Seminars Online seminar
Tuesday, 17 November 2020
2 pm - 3 pm (AEDT)

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.

About the speaker

Dongge Liu
PhD Student, The University of Melbourne

Dongge Liu is a third-year PhD student interested in applying machine learning algorithms to assist software vulnerability detection. His current research focuses on developing a principled way to balance the complementary nature of fuzzing and concolic execution with a novel variation of the Monte Carlo tree search algorithm. A paper of this project has recently been published in ASE20, a core rank A conference. His passion for general machine learning applications and open-source software development has brought him to many practical projects, such as Google Summer of Code.


Event contact

Share this event