一种基于汤普森采样的新型种子调度方案，用于覆盖引导的灰盒模糊测试

《Journal of Systems and Software》：A novel seed scheduling scheme using Thompson sampling for coverage-guided greybox fuzzing

基于路径相似性的动态种子聚类与定制化Thompson抽样算法协同提升代码覆盖均衡与崩溃检测效率。

　　

张文|陈金福|蔡赛华|王坤|刘一松|丁浩通

江苏大学计算机科学与通信工程学院，中国江苏省镇江市学府路301号，212013

摘要

覆盖引导的灰盒模糊测试（CGF）旨在在有限的时间内最大化代码区域的探索范围，从而提高代码覆盖率。现有方法通常通过执行速度和大小等属性来估计种子潜力，但往往忽略了被探索程序空间的分布以及种子类别在检测新覆盖范围方面的潜力，导致代码区域探索不平衡，对复杂代码的检测能力有限。本文提出了一种新的模糊测试种子调度方法TMS-Fuzz，该方法通过区分种子输入的执行覆盖特征来平衡代码区域的探索。通过计算不同种子输入的执行覆盖路径的相似性，TMS-Fuzz能够动态且自适应地对它们进行分组。此外，为了提高模糊测试的投资回报率（ROI），TMS-Fuzz使用定制的汤普森采样算法来统计选择ROI最高的种子组，这意味着该组中的种子变异最有可能发现新的独特路径和程序崩溃。最后，TMS-Fuzz通过对选定的种子组中的种子文件进行变异来对目标程序进行模糊测试。在八个真实世界程序上的评估表明，与最先进的开源模糊测试工具相比，TMS-Fuzz在提高边缘覆盖率和程序崩溃检测能力方面表现更好。

引言

作为一种广泛使用的自动化软件测试技术，模糊测试通过自动化过程随机变异现有输入来生成新的测试输入，旨在生成能够覆盖程序中潜在错误和异常情况的输入。通过监控被测试程序的运行状态，它可以检测是否存在漏洞、错误、异常行为或程序崩溃，从而揭示软件中的安全问题（Aschermann等人，2019年；Zheng等人，2019年；Huang等人，2024年；Fioraldi等人，2020b年）。在这些模糊测试方法中，覆盖引导的灰盒模糊测试（CGF）是最受欢迎的方法之一（Li等人，2018年；B?hme等人，2019年；Chen等人，2023年）。它利用代码覆盖率作为反馈来指导输入生成过程，保留通过变异产生的有趣的新输入（即触发新程序状态的输入）。这确保了新输入能够探索目标程序的不同控制流边缘，从而最大化程序输入空间的探索范围（Liang等人，2022年）。

此外，在模糊测试过程中优化种子调度和变异策略是CGF的两个关键研究挑战。适当的变异策略可以显著提高模糊测试发现新边缘覆盖率和暴露程序崩溃的能力。例如，现有的变异调度方法主要基于历史变异数据来优化变异操作符的概率分布（Lyu等人，2019年；Jauernig等人，2023年），使得模糊测试工具在变异过程中更有可能选择更有效的变异操作符。对于种子调度，主要挑战是确定种子库中哪些种子最有可能生成能够在被测试程序中探索尽可能多新边缘的新输入。这些有潜力的种子会被赋予更高的执行优先级和更多的变异机会，以实现更高的代码覆盖率。一个简单而理想的策略是根据种子在程序的控制流图（CFG）中能够覆盖的可达边缘数量来调度种子。然而，这种理想化的方法假设CFG中的所有边缘都可以通过变异到达。但在实际程序中，往往存在难以通过随机变异绕过的复杂约束，这使得这种理想化的策略效果较差。先前的研究还表明，通过随机输入变异到达子节点通常比到达父节点更困难（Peng等人，2018年）。换句话说，通过随机变异突破约束以到达新的控制流边缘颇具挑战性。对于嵌入在较简单约束中的浅层边缘，大量变异输入可能能够到达它们。但对于嵌入在更复杂约束中的深层边缘，通过变异生成的新输入可能很少（如果有的话），因为许多分支难以通过随机变异访问。

目前，在现有的CGF种子调度方法中，EcoFuzz（Yue等人，2020年）根据种子变异历史生成的新路径覆盖数量来计算奖励概率，从而指导模糊测试工具优先选择奖励概率较高的种子，因为这些种子在变异过程中产生新路径覆盖的潜力更大。AFLFAST（B?hme等人，2019年）通过使用马尔可夫链优先选择低频路径的种子输入，引导模糊测试工具探索输入执行较少覆盖的路径。K-Scheduler（She等人，2022年）根据程序执行时的控制流图构建一个边缘地平图，并计算种子节点的Katz中心性来估计到达未访问边缘的可能性，从而实现种子的优先调度。然而，随着模糊测试过程的进行，种子数量呈爆炸性增长，导致巨大的计算负担，时间成本变得不可预测。此外，SLIME（Lyu等人，2022年）定义了详细的种子属性，并根据种子在特定属性上的表现对其进行从高到低的排序。它使用自定义的上置信界方差感知（UCB-V）算法来估计每个属性队列发现未知路径的潜力，并根据这种潜力选择属性队列并对该队列中的种子进行变异，从而实现种子调度。

然而，这些现有方法没有考虑测试过程中不同种子执行路径的覆盖模式在整个程序空间中的整体分布。由于种子输入之间的差异，不同种子探索的程序空间也有所不同。相似的种子具有相似的输入模式和执行行为，种子之间的差异越大，它们探索的程序空间就越多样化。忽视关于不同类型种子探索的区域及其检测新代码覆盖潜力信息，测试往往只停留在探索程序空间的特定区域。这导致目标程序中不同代码区域的探索不平衡，限制了全面探索整个程序空间的能力。

为了解决现有方法的问题，本文提出了一种基于汤普森采样的种子调度策略，称为TMS-Fuzz。TMS-Fuzz旨在通过根据种子的输入覆盖模式对种子进行分组，并考虑种子组的覆盖分布和潜在变异值来平衡不同代码区域的探索。首先，TMS-Fuzz根据种子路径覆盖之间的路径相似性动态且自适应地对种子进行分组。同一组内的种子具有相似的覆盖模式和执行行为，形成在特征空间中彼此接近的种子集合，代表程序空间的特定区域和行为模式。对于种子较少的组，这表明相应的代码区域被探索得较少，该区域的边缘和分支覆盖较少。其次，TMS-Fuzz使用定制的汤普森采样算法根据种子在发现独特路径和程序崩溃方面的表现来估计每个种子组的潜在测试奖励。最后，在估计奖励的指导下，TMS-Fuzz统计选择种子组并对组内的种子进行变异。通过实时动态更新每个种子组的潜在投资回报率，TMS-Fuzz确保执行时优先考虑潜在价值较高的种子，同时避免模糊测试工具对那些执行边缘已被其他种子过度覆盖的种子的偏好。这有助于平衡不同代码区域的探索。本文的主要贡献如下：

•

设计了一种动态、自适应的种子聚类方法，以捕捉不同种子执行覆盖之间的路径相似性，实现种子的聚类。

•

基于种子聚类结果，种子组的评估自然地被构建为一个多臂老虎机（MAB）问题。使用定制的汤普森采样算法，根据不同种子组在生成独特路径和程序崩溃方面的表现来估计每个种子组的潜在测试奖励。在估计奖励的指导下，从选定的种子组中统计选择种子进行模糊测试。这种定制使得动态臂管理能够适应模糊测试过程中种子组数量的变化。

•

在对八个广泛使用的真实世界程序进行的初步实验研究中，TMS-Fuzz在检测独特程序崩溃和代码覆盖率方面表现更好。

本文的其余部分组织如下。第2节介绍背景。第3节介绍了所提出的基于汤普森采样的种子调度策略的动机和实现。第4节总结了实验结果，并通过分析不同模糊测试方法的性能来讨论我们的发现。第5节总结了相关工作。第6节总结了本文并展望了未来的工作。

章节片段

覆盖引导的灰盒模糊测试

覆盖引导的灰盒模糊测试（CGF）使用轻量级仪器技术来捕获程序的控制流信息。通过收集种子输入在执行过程中的测试覆盖数据，它指导测试用例的生成，以发现目标程序中的更多路径。通常，CGF的主要工作流程如图1所示，包括三个部分：种子调度、能量分配和变异执行。在模糊测试工具将初始测试用例集加载到种子后

动机

在覆盖引导的灰盒模糊测试（CGF）中，模糊测试工具仅在变异过程中保留有趣的新输入（即触发新程序状态的输入），并对这些有趣输入进行进一步变异。通过不断变异这些有趣的测试输入，模糊测试工具在程序的输入空间中搜索可能可利用的错误行为。在这个具有父子关系的变异过程中，通过变异生成的子输入具有

评估

根据第3章的描述，我们在AFL（Zalewski，2014）的2.57b版本上实现了我们的方法TMS-Fuzz。（请注意，在本章的所有实验中，我们采用的AFL版本是2.57b。）此外，在本章中，我们设计了实验来验证TMS-Fuzz的性能，并使用实验结果来回答以下研究问题：

1)

RQ1：与其他优化种子调度策略的模糊测试方法相比，

覆盖引导的灰盒模糊测试

自从AFL（American Fuzzy Lop）（Zalewski，2014）发布以来，覆盖引导的灰盒模糊测试（CGF）开始快速发展。针对CGF基本工作流程中的各个问题，研究人员也进行了大量的探索和改进工作，主要可以从两个方面来阐述：种子调度和种子变异策略。因此，如第1章所述，一些研究专注于如何选择更有潜力的种子输入

结论和未来工作

在本文中，我们提出了一种新的覆盖引导的灰盒模糊测试种子调度方法，称为TMS-Fuzz。该方法分析了种子执行路径特征的差异，并根据种子在程序空间内的执行覆盖分布对种子进行分组。我们进一步应用定制的汤普森采样算法来估计每个种子组的潜在测试奖励，基于它们在发现独特路径和程序崩溃方面的表现。这种方法显著提高了

CRediT作者贡献声明

张文：撰写——原始草案、方法论、调查。陈金福：撰写——审阅与编辑、监督。蔡赛华：撰写——审阅与编辑、监督。王坤：可视化、数据整理。刘一松：监督。丁浩通：调查。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。