【NDSS 2022 论文分享】多目标协同引导的灰盒模糊测试

覆盖率引导的灰盒模糊测试技术（Coverage-guided grey-box fuzzing，简称CGF）作为模糊测试技术的一种重要分支，最近受到了研究人员广泛的关注。相比最简单的黑盒模糊测试以及复杂的白盒模糊测试技术，覆盖率引导的灰盒模糊测试技术的关键在于通过简易的插桩使代码覆盖率最大化。从本质上讲，灰盒模糊测试技术是一个优化问题，优化问题的关键是在输入空间中搜索最优解并对目标进行优化，对目标进行优化意味着搜索能使目标数值达到最大或者最小值的输入。在覆盖率引导的灰盒模糊测试中，首要的目标是代码覆盖率，因此它的目标是将覆盖率最大化。

单目标引导是搜索能使某个单一目标达到最优解的方法，例如覆盖率最大，然而在真实的应用场景中，通常需要对多个目标进行优化来解决复杂的问题，例如探测不同种类的漏洞提高模糊测试效率。此外，在模糊测试的不同阶段，需要根据当时的测试情况来自适应地选择不同的目标进行优化，例如，当我们测试内存分配的代码时，与内存消耗相关的目标应该被侧重；在求解条件约束的时候，输入字节满足分支条件的能力则应该是要侧重的目标，因此提出了多目标优化（multi-objective optimization，简称MOO）的概念来研究多个目标之间的协同、权衡和折中。

1.灰盒模糊测试过程介绍

灰盒模糊测试首先根据相应的目标从种子队列中选择种子，根据分配的能量大小决定对这个种子的变异和执行次数。之后变异这个种子产生测试用例，在执行测试用例时监视是否覆盖新的路径，如果输入覆盖了新路径就将它保存进种子队列中。然后模糊测试会继续选择新的种子，进入下一个循环。除了代码覆盖率，灰盒模糊测试在选择种子的时候还会考虑其他的目标。例如，AFL （American Fuzzy Lop）会将那些执行速度更快、文件大小更小的种子标记为“favored”，作为高质量种子，这些被标记的种子会以更大的概率被选中，从而提升效率。通过计算执行速度以及文件大小的乘积，AFL可以搜索最优输入来进行目标优化。

虽然基于覆盖率的灰盒模糊测试技术在测试中也考虑了覆盖率以外的目标，但是现有的模糊测试工具不能真正地支持多目标协同优化。例如，AFL在模糊测试过程当中也考虑输入的执行时间和文件大小，那些执行时间乘以文件大小结果较小的输入会被优先选择。理论上讲，在搜索过程中，某次选择时只考虑一个结果（例如选择一个执行时间乘以文件大小结果较小的输入），会导致搜索算法陷入局部最优解，从而不能求解出全局最优解。此外，其他的工具在处理多目标优化的问题时也存在局限性，它们在加入新目标时，往往会舍弃旧目标。例如，MemLock在选择种子时优先选择消耗内存更多的输入来触发内存消耗漏洞，因此，它除了有覆盖率这个基本的目标，还有内存消耗量这个目标，但是在添加内存消耗这个目标时，MemLock 移除了AFL中执行时间和文件大小的原有目标，这种做法会严重影响模糊测试的执行速度。其他的工具使用了十分简单的方法来解决多目标优化，要么会陷入局部最优解，要么会引入较大的性能开销，因此我们需要提出一种能在灰盒模糊测试中同时优化多个目标的高效方法。

2.多目标协同引导的难点和挑战

基于以上背景分析，为了能在模糊测试中同时优化多个目标实现协同引导，我们总结了如下三个需要解决的关键问题：

（1）协调多个目标之间的冲突关系。在模糊测试的过程中，我们发现优化某个目标会对另一个目标产生负面影响，例如，为了求解分支条件约束而优化的目标会使模糊测试的执行速度变慢。这种多个目标之间的内在联系要求我们在搜索全局最优解的时候，需要在不同的测试阶段合适地选择不同的目标。因此，需要在模糊测试多目标优化中自适应地选择目标组合。

（2）适合多目标协同引导的能量调度。灰盒模糊测试的能量调度是用来控制变异和执行次数（能量）的，它能够引导模糊测试朝着特定的方向进行搜索。之前针对灰盒模糊测试能量调度的工作，例如AFLFast和EcoFuzz，基于种子的路径发现能力来分配合适的能量，目的是节约能量或者说节约模糊测试的执行次数。然而在多目标优化的场景下，能量调度就需要考虑实际的目标组合选择。因此，需要一种和目标组合选择相匹配的能量调度策略。

（3）减少多目标优化带来的性能开销。执行速度在模糊测试中是一个很关键的指标。当我们考虑多目标优化时，目标组合选择、能量调度或者其他部分都会带来性能开销。例如，Cerebro使用了帕累托前沿（Pareto frontier，包含最优解的结果集合）的思想以及非支配排序，在迭代算法中搜索最优解，但是它在求解最优解的时候，算法在一次模糊测试循环中只执行了一次，而模糊测试的进程则是处于等待结果的待机状态，浪费了宝贵的执行时间。在搜索最优解时，像Cerebro 这种单次的执行很难找到全局最优解，因为求解帕累托前沿并达到拟合通常需要迭代超过一百次。如果直接将这个迭代求解的过程放入模糊测试进程，会造成巨大的性能开销，因此需要设计相应的方法以较小的性能开销搜索多目标优化的最优解。

为了能解决上述模糊测试多目标优化的三个问题，我们设计并实现了MobFuzz。首先为了解决自适应地选择目标组合问题，我们将模糊测试中的多目标优化建模为一个多玩家多臂老虎机（Multi-Player Multi-Armed Bandit，简称MPMAB）模型。经典多臂老虎机模型的目的是通过选择合适的游戏臂将全局收益最大化。我们将目标组合选择视作有各自目的的不同玩家，来解决自适应地选择目标组合这个问题。这个算法的作用是能选择在当前模糊测试状态下收益最大的目标组合。

为了解决适合目标组合选择的能量调度问题，我们将模糊测试的种子视作老虎机的游戏臂，并将模糊测试过程分为探索（exploration）和利用（exploitation）两个阶段，分别分配不同的能量。通过这种自适应的能量调度，MobFuzz 能够控制种子的变异和执行次数，从而针对不同的目标组合分配合适的能量，在搜索最优解的时候还可以节约能量。为了解决性能开销问题，我们提出了针对灰盒模糊测试的非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm in CGF，简称NIC），它是基于非支配排序和帕累托前沿的一种迭代算法。我们还提出了新的变异策略，将不同的目标组合与变异策略建立起联系，使某些目标数值优化的变异策略会被优先选择。此外，还通过其他新的技术来减小性能开销，例如共享种子队列。

图1 MobFuzz主要流程

如图1所示，我们在传统灰盒模糊测试的基础上增加了两个关键部分：多玩家多臂老虎机模型以及针对模糊测试的非支配排序遗传算法。多玩家多臂老虎机模型能自适应地选择目标组合并分配能量，非支配排序遗传算法则是通过迭代的过程输出目标的最优解且尽可能降低性能开销。

MobFuzz 的主要流程如下：首先从种子队列中选取一个种子，由多玩家多臂老虎机模型决定在当前模糊测试状态下最合适的目标组合；然后基于选择的目标组合，该模型根据探索和利用的不同阶段分配不同的能量；紧接着MobFuzz 根据能量对种子进行变异并执行；与此同时，它监视着被选目标组合中目标的数值。如果目标数值达到了特定的开始条件，就打开非支配排序遗传算法，通过迭代的过程来逐步更新并输出目标的最优解；最后，非支配排序遗传算法求解得到的帕累托种子被保存进入种子队列，并继续下一个模糊测试循环。

 （本文只选取原文中部分章节，更多精彩内容敬请期待后续出版的《网络安全研究进展》）

【NDSS 2022 论文分享】LOGICMEM：一种基于逻辑推理的自动化内核配置文件生成方法

【Usenix Security 2022论文分享】双星攻击：对于自动系统中深度估计避障算法的远程攻击

【S&P 2022 论文分享】稻草攻击：压死安卓系统的最后一根稻草

【NDSS 2022 论文分享】危险的集成：团队协作平台第三方小程序安全风险分析