论文标题
军团：最佳首先的一致性测试
Legion: Best-First Concolic Testing
论文作者
论文摘要
一致的执行和模糊是两种基于互补的测试技术。如何实现两者的最佳状态仍然是一个悬而未决的挑战。为了解决这个研究问题，我们提出和评估军团。 Legion重新设计了AI文献的Monte Carlo Tree Search（MCT）框架，以将自动化测试生成视为不确定性下的顺序决策问题。它的最佳搜索策略提供了一种原则性的方法，可以根据以前的迭代中观察到的奖励来学习在每个搜索迭代中进行调查的最有前途的计划状态。 Legion结合了一种定向模糊的形式，我们称之为近似路径保护模糊（AppFuzzing）来调查MCT选择的程序状态。 AppFuzzing用作Monte Carlo模拟技术，可以通过扩展在受约束采样上的先前工作来实现。我们评估了2020年覆盖范围类别的2531个基准的竞争对手对竞争对手的评估，并衡量了其对超参数的敏感性，证明了其对各种输入程序的有效性。
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.
