原文名称    SLIME: Program-Sensitive Energy Allocation for Fuzzing

原文链接   https://www.bbge.org/publication/

lv-2022-issta/Lv-2022-issta.pdf

发表期刊   Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis

一、 引言

在模糊测试中，能量分配环节负责将更多的计算能量分配给具有高效率的种子文件，从而更快地触发新的路径和崩溃。现有的能量分配算法通常将预定的属性（如种子执行速度、种子大小、种子覆盖率等）作为其分配逻辑中的关键度量来估计种子的潜力。这一算法基于一个假设：某个属性在不同的PUT（待测程序，Program Under Test）中具有相同的效率。然而，本篇论文的作者通过一组实验发现这一假设并不成立，即现有的静态能量分配机制很难在不同PUT上达到理想的效果。

为了解决上述问题，本文作者提出了一种名为SLIME的新型程序敏感（Program Sensitive）能量调度机制，实现了对具有不同属性的种子进行自适应能量分配的技术。本文后续部分将讨论SLIME的实现思路。

二、 Motivation

作者发现了具有相同属性的种子的效率在不同PUT中并不总是一致这一现象，并通过一系列实验证明了该现象是客观存在的。

作者使用MOPT对gdk、objdump和pdfimages这三个在模糊测试中广泛使用的目标程序进行48小时的模糊测试，每个程序重复4次。然后，作者通过搜集大量资料，总结了9种常见的种子有效性度量标准，包括种子执行速度、种子尺寸、种子产生深度、比较语句数量、循环数量等等。根据这9种属性的定义，对种子进行排序，将前40%的种子标记为拥有该属性，然后统计所选种子经过变异后触发的唯一路径和崩溃的总数，并统计这些选中种子的总执行次数。最后，根据上述统计值计算属性的模糊测试效率，即唯一路径和崩溃的总数除以总执行时间。结果如下图所示：

三、解决方案

为了解决现有能量分配策略中存在的问题，SLIME被设计为针对给定目标程序，根据每个属性的效率自适应地将变异能量分配给具有高效属性的种子。SLIME首先对队列中的每个种子进行变异，记录其在不同属性上的表现。然后，SLIME将具有相同属性的种子聚类，根据属性的模糊效率为这些种子分配适当的能量。

为了在测试目标程序的同时记录新发现的interesting种子在不同属性上的性能，SLIME对种子进行变异然后检测种子是否触发了新的执行路径和崩溃。如果发现了一个新的interesting种子触发了新的执行路径，SLIME会将该种子加入到原始队列中，并记录种子在每个预定义的属性上的性能。

此外，还需要定期更新种子的属性并重新进行聚类，因为种子的属性有可能在模糊测试中进行变化。

为了完成上述工作，作者设计了如Figure 2所示的框架。该框架主要包含三个阶段：Exploration Stage、Update Stage和Exploitation Stage。

SLIME在模糊测试开始时进入Exploration Stage，对原始队列中的所有种子进行变异。对于触发新的独特路径和崩溃的interesting种子，SLIME将其加入原始队列，计算并记录其属性值。为了最大化SLIME的模糊测试效率，Exploration Stage拥有两个结束条件：1）第一次进入该阶段，如果SLIME对于独特路径和崩溃的发现效率下降到了一定阈值，则进入Update Stage；2）非第一次进入该阶段，对原始队列中所有种子进行固定次数的变异循环后进入Update Stage。

在Update Stage种，SLIME根据Exploration Stage得到的种子属性记录更新种子的属性值，然后遍历原始队列中的所有种子，重构所有属性队列。每个属性队列根据种子在该属性上的表现从高到低排序，如果对应的属性队列没有达到最大长度，并且当前种子在该属性上的性能优于该属性队列中的最后一个种子，则将该种子加入队列。这样，在遍历原始队列中的种子后，SLIME就得到了分别满足各自定义的属性队列。

SLIME重构所有属性队列后，进入Exploitation Stage进行能量分配。SLIME利用属性自适应能量分配算法来估计每个属性队列发现interesting用例的潜力，并根据估计的潜力统计选择一个属性队列并对属性队列中的种子进行变异。具体地说，SLIME的属性队列选择可以看作一个多臂老虎机问题，属性自适应能量分配算法的目标是估计每个属性队列发现interesting种子的潜力，并根据潜力选择属性队列。

为了使得能量算法具有较低的开销从而避免降低模糊测试的效率，作者设计了基于上置信界方差感知（Upper Confidence Bound Variance-aware）的算法。在Exploitation Stage，SLIME使用该算法估计估计新发现interesting种子数量的置信区间，然后将估计区间的置信上界当作奖励，作为选择属性队列的依据。具体的算法如下，其中  表示Exploitation stage选择第  个属性队列并变异其中的种子时，触发新的独特路径或崩溃的interesting的输入数量；  表示第  个属性队列的  值的和；  表示第  个属性队列  的平方和；  表示选取第  个属性队列的次数，  表示选择所有队列的总数；  表示第  个属性队列的估计方差估值，这提高了算法的收敛速度并有助于更快地找到有效的属性队列；  表示第  个属性队列的上确界估值。可以看到，如果一个队列触发独特路径和崩溃的数量越多、历史中被选中的次数越少，则该队列被选中的可能性越高。

四、实现与局限

RQ1：SLIME的模糊测试效果如何？

RQ2：SLIME各主要部分对模糊测试性能的贡献是什么？

作者同样进行了消融实验以验证SLIME主要组成部分的有效性。

为了验证属性自适应能量分配算法的贡献，作者使用不同的队列选择算法构建了另一个版本的SLIME，即SLIME_rand，它在Exploitation Stage中以相同的概率随机选择每个属性队列。作者评估了SLIME_rand在gdk、objdump和tiffsplit上的漏洞发现性能，结果如表8所示。结果表明，如果没有属性自适应能量分配算法，属性队列结构不能显著提高漏洞发现性能。

五、结论