今天我们主要介绍一篇来自ICSE 2022的文章《One Fuzzing Strategy to Rule Them All》。这篇文章主要做了两个工作：一是针对AFL系模糊器中变异策略Havoc对模糊测试性能的影响进行了深度的研究，二是基于前述研究结果提出了一个轻量级的改进策略。本文将在后面篇幅中详细介绍这两个部分的内容。

首先，我们回忆一下AFL系模糊器中Havoc变异策略的实现机制。Havoc是AFL系模糊器的精髓，其整体框架如图1所示。

如图1所示，Havoc变异策略主要由变异次数和变异器叠加（mutator stacking）次数决定。Havoc变异策略首先会基于实时种子信息（如种子执行时间、种子覆盖到的比特位图大小等）确定种子的变异次数（对应于图2中的stage_max变量值），即模糊器需要执行多少次的Havoc操作（一次Havoc操作是指从一个特定的种子，经过一系列变异后得到一个测试用例的过程）；在确定了变异次数之后，Havoc在每次Havoc操作之前确定一个变异器叠加次数（对应于图2中的use_stacking变量值），并根据该次数按序随机应用多种变异方法。图2为AFL中Havoc框架源代码。

在变异器叠加阶段，Havoc首先根据变异器叠加次数对一个种子应用多种变异操作。具体来说，Havoc首先确定应用的变异器叠加大小，其值为2到128之间任一2的幂值；然后Havoc为每个叠加随机选择变异器并进行变异操作。最后，将所有堆叠的变异操作应用于种子以生成一个新的测试用例。

此外，论文将Havoc分为两类，如表1所示。其中红色为单元变异器，蓝色为块变异器。其中，单元变异器对程序中的数据存储单元（如比特、字节、字、双字等）进行变异，不会改变输入的长度，而块变异器倾向于对模糊器随机选择的块（大小不定）进行变异，由于包含插入或删除操作，因此很大概率会改变输入的长度。

Havoc可以通过两种方法与其他模糊器进行集成：

在主模糊测试策略变异阶段的后期进行Havoc，原生AFL/AFL++便采取这种方式进行集成；

Havoc和主模糊测试策略并行执行，如QSYM支持的三个线程，这三个线程分别执行Havoc、AFL确定性变异策略和符号执行。

表2揭示了所研究的模糊器及其是否包含Havoc策略的信息，其中Pure Hovoc是空白对照组。

表3展示了实验的基准程序，选择下列程序的原因主要有三个：一是这12个基准程序囊括了7个不同的种子输入文件格式；二是这些程序规模从1885行到120K行，能够代表实际中大多数的程序；三是它们能够涵盖各种功能，包括开发工具（如readelf、objdump）、代码处理工具（如tiff2bw）、图形处理工具（如djpeg）、网络分析工具（如tcpdump）等。

RQ1：在不同模糊器中，Havoc的性能表现如何？

该问题尝试调查在所研究的模糊器中使用默认Havoc策略对于模糊测试性能的影响，主要从Havoc占用的时间、Havoc对于覆盖率提升的影响、在无Havoc模糊器中集成Havoc后对于模糊测试的影响这三个角度阐述。

RQ2：在不同的Havoc时间设置下，Havoc在不同模糊器中的表现如何？

该问题主要探讨在不同执行时间设置下启用Havoc后对于所研究模糊器性能的影响。

（1）针对RQ1，论文作者设计了2个实验，并对相应的结果进行论述。

在进行实验之前，论文作者对不同模糊器中Havoc执行时间进行统计，如图3所示。需要注意的是，如前所述，Neuzz和MTFuzz中并没有Havoc变异策略，而这里的运行时间是通过将顺序方式将Havoc集成到对应模糊器后得到的统计数据，我们将在实验2中详细说明。

从图3的Havoc执行时间，我们可以看到AFL、AFL++和FairFuzz默认允许的Havoc总执行时间相当有限，而在MOPT和QSYM中允许Havoc执行的时间要长的多，主要原因是这两个模糊器中引入特定的机制以改善模糊测试性能：MOPT使用粒子群优化算法使Havoc执行时间变长，而QSYM默认使用了一个额外的线程单独执行Havoc操作。

论文作者将模糊器中原本包含的Havoc模块剔除，并与原模糊器的性能进行比较。表4比较了原模糊器和剔除Havoc之后模糊器在边覆盖方面的表现。其中Major列展示了剔除Havoc后的边覆盖数。

由表4结果可以看出，Havoc能够显著提高目标程序的边覆盖率，特别是MOPT和QSYM。同时我们也能看出，模糊器边覆盖性能与Havoc执行时间也有一定的相关性，即对于大多数模糊器来说，执行更长时间的Havoc可能会导致更高的边覆盖率。

为了探究Havoc机制在那些本身无Havoc机制模糊器中的影响，论文作者使用顺序Havoc集成方式，将默认的Havoc添加到本身无Havoc机制的模糊器中，集成后Havoc执行时间如图3（红色标记的模糊器）所示。表5展示了集成后模糊器边覆盖的表现。

由表5的结果可以看出，Integration列的Havoc和Major子列边覆盖数之和大于原始模糊器的覆盖数，因此采用默认设置的Havoc可以提高所研究的模糊器的边覆盖性能；此外，纯Havoc列的结果也说明Havoc本质上也是一个很强大的模糊器，对一个种子执行足够时间的Havoc，可以实现比许多现有模糊器更高的边缘覆盖率。

首先在迭代持续时间t设置为一个小时的条件下进行评估，在24小时的时间预算下，修改后的Havoc将执行12小时。实验结果如表6所示，其中Orig列表示原始模糊器（未修改），New列表示与修改后的Havoc集成的模糊器。注：该机制不适合纯Havoc和QSYM，因为它们在整个模糊测试过程中都会启用Havoc。

从上述结果可知，对于大多数模糊器来说，执行更长时间的Havoc的模糊器会得到更好的边覆盖结果。

此外，作者计算了平均边覆盖的标准差STD，采用新策略集成Havoc的模糊器STD（819）明显小于默认策略Havoc集成的模糊器STD值（8879）。因此，通过运行足够时间的Havoc，可以显著减少不同模糊器边覆盖性能的差距（由不同模糊器设计不同而带来的性能差距）。

图5展示了与修改后的Havoc集成的模糊器的基本块覆盖结果。

为了进一步研究Havoc与模糊器的集成模式下改变迭代持续时间对其边覆盖性能的影响，作者启用不同的设置（Havoc迭代持续时间分别为1/2/4/12小时）进行实验，实验结果如表7所示。从下述结果可以看出，在Havoc的总执行时间不变的情况下，调整其迭代执行时间对相关模糊器的边覆盖性能影响有限。

作者观察到启用多线程的QSYM具有更好的表现，因此提出一种假设：并行执行多种模糊测试策略可能会提高边探索的能力。为了验证这个假设，作者在所研究的模糊器中添加额外的线程用于执行Havoc策略，分别使用一个和两个额外的线程来执行Havoc策略。实验结果如图6所示，由该结果可以看出，在执行Havoc上投入更多的计算资源可能会减少执行时间，使模糊测试达到性能的瓶颈，因此很不划算。

之前的结果表明，在足够充分的Havoc执行时间下，多个模糊器具有相当接近的边覆盖性能，作者通过引入Jaccard Distance指标来研究边之间的差异性。不同模糊器与纯Havoc之间Jaccard Distance值如图7所示。对于边覆盖来说，Jaccard Distance值越大，表明能够发现更多的新边。从图7结果可以看出，QSYM、MTFuzz和Neuzz具有较大的Jaccard Distance值，其原因在于QSYM使用符号执行策略来探索难以到达的边，而MTFuzz和Neuzz使用神经网络进一步指导模糊测试过程。总的来说，将Havoc应用于不同的模糊器很可能会探索一些较为常见的边，而基于符号执行或神经网络指导的模糊器可以更好的补充Havoc的结果，即发现一些新的边。

最后，作者研究了Havoc策略对于程序漏洞暴露方面的影响，其结果如表8所示。由结果可以看出，Havoc在暴露潜在的程序漏洞方面也发挥着至关重要的作用。

前述的一系列实验表明了Havoc策略在模糊测试过程中具有很强的性能表现，为了进一步压榨Havoc的性能，作者研究了Havoc所采用的变异器叠加机制对于性能的影响。如前所述，变异叠加机制包括两个步骤：确定叠加大小和选择随机变异器，而这两个步骤是影响Havoc性能的关键。其中叠加大小对于性能的影响如图8所示，变异器类型对性能的影响如图9所示。

综合上述实验结果，变异器堆叠大小和变异类型（块/单元变异）的最佳实践（产生最佳性能）取决于具体的目标程序，因此可以根据目标程序来决定最佳实践。作者提出了轻量级单线程技术，具体来说，该技术将整个模糊测试变异任务建模为一个多臂老虎机问题：将有限的资源分配给可选操作（堆叠大小和变异类型选择）以最大化期望收益（即边覆盖率），同时设计了两层多臂老虎机，即堆叠大小级老虎机和变异类型级老虎机。图10展示了的整体框架。

作者采用广泛使用的UCB1-Tuned算法来解决所提出的多臂老虎机问题：

将t时刻的奖励定义为对于8个老虎机能否探索到新边：如果一个选择的堆叠大小和它所选择的变异器所产生的种子能够探索到新的边，那么堆叠大小级的老虎机及其相应的变异器叠加级老虎机得到的奖励都是1；否则，它们都为0，具体算法如图11所示。

实验评估结果如图12和图13所示。

总的来说，本文是第一篇系统性研究Havoc变异策略对模糊测试的影响的文章。从Havoc执行时间、集成了Havoc的模糊器和未集成Havoc的模糊器上性能的比较这两个维度揭示：Havoc执行时间越长，其边覆盖性能越好；从迭代持续时间、平均边覆盖标准方差、块覆盖率、并行、边差异性、唯一崩溃这六个维度揭示了Havoc策略在模糊测试中潜在的性能。

同时作者从变异器类型和变异器叠加大小这两个角度出发，提出了一种轻量级方法，该方法通过将Havoc策略建模为多臂老虎机问题，通过动态优化Havoc叠加大小和变异类型来提高模糊测试的性能。