技术进展 | SDFUZZ:目标状态驱动的定向模糊测试

基本信息

**原文名称：**SDFUZZ:Target States Driven 

Directed Fuzzing

**原文作者：**PenghuiLi，WeiMeng，ChaoZhang

**原文链接：**https://www.usenix.org/conference/

usenixsecurity24/presentation/li-penghui

**发表期刊：**USENIX，2024

一、引言

定向灰盒模糊（DGF）通常将测试引向高价值的目标站点位置，其被广泛应用于崩溃重现和漏洞验证，但之前的经常不必要地探索不能触发目标漏洞的程序代码和路径。缓解上述问题的一种解决方案是首先确定触发崩溃所需的程序代码/路径，然后仅对所需的代码/路径进行模糊测试。SieveFuzz分析过程间控制流图(ICFG)以识别到达目标站点所需的函数，并在到达不需要的函数时终止执行。Beacon通过向后间隔分析计算到达目标站点的先决条件，并提前终止不满足先决条件的执行。SelectFuzz静态地将控制和数据相关代码识别到目标站点。但是，它们高估了与执行相关的程序代码和路径集，从而严重限制了它们的性能。

此外，本文观察到定向模糊的主要应用场景都提供了详细的漏洞描述，从中可以推导出高价值的程序状态(即目标状态)，例如漏洞被触发时的调用轨迹。通过揭示这些目标状态，定向模糊器可以排除大量不必要的探索。受观察结果的启发，本文提出了SDFUZZ，一种由目标状态驱动的有效定向模糊工具。SDFUZZ首先自动提取漏洞报告和静态分析结果中的目标状态。SDFUZZ采用选择性插桩技术，将模糊范围缩小到达到目标状态所需的代码。一旦SDFUZZ探测到剩余的执行无法达到目标状态，那么SDFUZZ就会提前终止测试用例的执行。进一步利用新的目标状态反馈，将先前不精确的距离度量细化为二维反馈机制，主动推动对目标状态的探索。

二、概述

本文利用目标状态驱动DGF。在程序的巨大探索空间中，有很大一部分代码或路径无法触发目标漏洞。对程序的所有部分进行测试会造成不必要的资源消耗。如图1中，在L20处有一个断言失败，在DGF中，这个位置通常被设置为目标站点。在函数main()中通过L4的执行（即执行1）可以到达目标站点，并可能触发断言失败。通过L6的执行（即执行2）只能到达目标站点。幸运的是，目标状态描述了（可能）出现漏洞的有趣程序状态。在本文中，将预期的调用轨迹和目标站点的到达顺序定义为目标状态，认为模糊测试应该探索这些有趣的目标状态，而不仅仅是达到目标站点的位置。

图1 代码示例

本文开发了一种基于目标状态的定向模糊测试工具SDFUZZ。SDFUZZ的工作流程如图2所示。SDFUZZ首先自动提取目标状态并将其解析为指定格式。然后，SDFUZZ识别达到目标状态所需的代码，并从模糊测试中去除其他不需要的代码。它在使用目标状态而不是目标站点，这优于先前的解决方案。一旦SDFUZZ探测到测试用例的剩余执行无法到达目标状态，就会提前终止执行，从而增加模糊测试吞吐量（即每单位时间的执行次数）。SDFUZZ使用二维反馈机制主动引导测试朝向目标状态。在第一个维度中，SDFUZZ测量测试用例的最佳运行时状态与目标状态之间的相似性，并偏向相似性较高的状态。在第二个维度中，SDFUZZ采用一种新的精确加权的程序间距离度量。

 图2 SDFUZZ工作流程图

三、提取目标状态

为了提取目标状态，SDFUZZ需要漏洞报告或静态分析结果。对于后者，SDFUZZ使用现有的静态分析工具来分析程序的源代码。

**漏洞报告。**崩溃转储由触发漏洞时的活动函数调用记录组成，如图3所示。每条记录包含：1）函数名称（例如option1）和2）调用位置（例如file.c:15）。因此，首先使用正则表达式在漏洞报告中搜索包含此类信息的描述。提取后，进一步解析它们以确定它们是否与所需的格式匹配。还根据漏洞类型和描述自动对目标状态进行排序。例如，use-after-free漏洞通常包含多个目标状态，则会按释放和使用位置对目标状态进行排序。

图3 崩溃转储

**静态分析结果。**SDFUZZ会自动从静态分析结果中提取目标状态。由于不同的静态分析工具采用不同的方式来表示其结果，因此自然而然地，自动提取必须针对每个静态分析工具进行专门设计。本文目前开发SDFUZZ与一种流行的静态分析工具SVF一起使用。

四**、所需代码选择性插桩**

SDFUZZ通过在DGF的探索阶段选择性插桩与目标状态相关的覆盖率反馈所需代码来缩小模糊测试范围。首先，SDFUZZ确定代码的哪一部分是必需的，然后在模糊测试过程中忽视那些不需要的代码，即仅保留了达到目标状态所需的代码。这些代码是SieveFuzz和Beacon中保留的达到目标站点的代码的子集，这是因为目标状态进一步限制了到达目标站点的路径。因此，它可以帮助过滤掉更多代码并提高模糊测试吞吐量。本文解决方案选择性插桩代码覆盖率反馈所需的代码，而不是直接从源代码或可执行文件中将其删除。

图4 所需代码识别算法

本文提出了一个函数级算法用于识别所需代码，如图4算法1所示。该算法以一组目标状态(TS)和目标程序的ICFG(ICFG)作为输入。目标状态中出现的函数（即目标状态函数）与漏洞相关，并直接作为所需函数包含在内（第5行）。此外，这些目标状态函数可能依赖于其他函数。算法首先执行向后的过程内分析，以识别目标状态函数所依赖的函数（第6行）。如果在具有函数调用站点的基本块和目标状态函数的基本块之间存在过程内路径，则包含该函数。例如，包含函数check()是因为L15处的函数target()依赖于它。此外，这些新包含的函数可能会调用其他函数来实现其功能。因此，本文算法分析CG，并将这些函数包含在最初包含的函数之外的CG路径上（第14-15行）。通过这种方式，SDFUZZ扩展了实现目标状态所需的函数集。所以check()的调用函数被添加到所需代码中。

SDFUZZ不会直接从目标可执行文件中移除代码，而是采用基于插桩的方法来排除不需要的代码。SDFUZZ有选择地只插桩已识别的所需代码以进行代码覆盖率反馈，从而向模糊测试器隐藏其他不需要的函数并缩小模糊范围。这种设计具有容错能力。即使某些代码区域被错误地识别为不需要，执行仍可以通过这些代码区域进一步接近目标位置和状态。SDFUZZ不会分配测试精力来探索未插桩的路径。因此，它摆脱了先前解决方案中错误代码消除造成的严重缺陷，还减少了插桩覆盖率跟踪代码造成的开销。

五、提前终止执行

本文开发了一种新的模糊测试技术，可以提前中止无法达到目标状态的执行。如果已知某些执行无法达到目标状态，则会提前终止它们以节省探索资源。通过提前终止不必要的执行，这可以显著提高模糊测试的吞吐量。与之前基于可达性的执行终止方法不同，SDFUZZ还会终止无法达到目标状态的可达执行。要提前终止执行，必须预测执行最终是否能够达到目标状态。这很困难，因为程序状态会随着程序执行而动态更新，例如通过函数调用和返回。鉴于现代程序的高度复杂性，可以展示的程序状态空间可能非常大。

**运行时程序状态监控。**SDFUZZ监控运行时函数调用并记录函数调用堆栈。这些函数通过函数调用或返回从堆栈中推送或弹出。函数调用位置使SDFUZZ能够区分在不同位置调用的同一函数。程序状态跟踪可能会导致状态爆炸并造成沉重的开销。本文通过仅跟踪与目标状态相关的函数的状态来缓解此问题。具体而言，SDFUZZ仅在程序调用或从目标状态中的函数返回时更新并检查程序状态以进行提前终止。

**基于不可恢复偏差的解决方案。**多目标漏洞的目标状态是函数调用的有序列表数组，每个列表对应一个目标站点。因此，图5算法2将某个时间点的当前程序状态(PS)、之前达到的目标状态(reachedTSs)、有序目标状态(TSs)和ICFG作为输入。它迭代目标状态以找到在测试用例的模糊测试试验期间未达到的第一个目标状态（第3-6行）。如果已达到所有目标状态，算法将直接返回（第7-8行）。否则，它会检查偏差函数调用，尤其是第一个偏差，即通过rootDeviation函数寻找根偏差（第10行）。根偏差表示程序状态开始偏离目标状态的执行位置，可以通过迭代比较调用站点（第20-26行）来找到第一个偏差函数调用。如果存在任何偏差（第11行），算法会进一步分析剩余的执行是否可以根据ICFG恢复偏差以达到目标状态（第12行）。如果执行的程序状态存在不可恢复的偏差，则可以立即终止。算法检查程序的ICFG，并探测是否存在从根偏差代码位置到目标状态中的预期函数调用的程序路径。这样的路径意味着偏差可能会在未来的执行中恢复，因为执行可以从根偏差函数调用返回并运行到预期的函数调用。因此，可能恢复偏差的执行不会被终止。

图5 执行终止与目标状态相似性算法

使用图6中列出的执行的三个程序状态（即PS1-PS3）来说明算法的工作流程。当执行到达第2行之后时，可以观察到PS1。程序状态在第二项中偏离目标状态，即（input，L2）vs.（option1，L4）。偏差可能是可以恢复的，因为后续执行可能会从函数input()返回并在L4处的预期函数option1()旁边运行。从ICFG的角度来看，这可以反映为从偏差位置（例如L2）到预期位置（例如L4）存在程序路径。因此，执行不会在PS1处终止。在PS2处，程序状态恰好是TS1的前缀，没有其他偏差，并且不会偏离TS1。执行不会终止。然而，在PS3的情况下，它在(clean,L7)处偏离了TS1中的(option1,L4)，并且没有从L7到L4的路径。执行将终止。

图6 目标状态与程序执行状态

六、二维反馈

（1）目标状态反馈

SDFUZZ将运行时程序状态与目标状态进行比较，并计算相似度得分以主动指导探索。反馈有利于程序状态与目标状态更相似的测试用例。

算法2中还显示了状态相似度计算的工作流程。在第3-6行找到第一个未达到的目标状态(nextTS)后，SDFUZZ使用根偏差的索引来计算相似度得分。如果当前程序状态与第一个未达到的目标状态(nextTS)不完全匹配，SDFUZZ首先通过计算匹配的偏差Idx与其大小的比率来衡量当前程序状态与它的匹配程度（第13行）。算法还考虑了之前达到的目标状态，并将比率的得分与达到的TS的大小相加。使用目标状态的数量进一步对得分进行归一化并返回。如果当前程序状态与nextTS匹配，算法将直接返回达到的目标状态的比例（第16行）。由于算法可能会被多次调用以执行测试用例，因此将最佳分数分配为测试用例的结果。

（2）距离反馈

SDFUZZ还使用距离度量来指导模糊测试过程。先前的距离度量并不精确，因为其平等地考虑了CG中的每个边。根据经验配置一个恒定权重（例如，在基于AFLGo的定向模糊测试器中为10）来近似到达目标函数的机会。因此，即使有很高的机会到达目标函数，长调用链的执行也可能被分配较大的距离值并被降低优先级。

SDFUZZ在计算过程间距离时使用精确的边权重来减轻不精确性，边权重有望反映调用者函数调用被调用者函数的机会。SDFUZZ根据调用点权重计算边权重。将调用者函数调用被调用者函数的调用点权重定义为从调用者函数的开头到被调用者调用点的过程内距离（即，如AFLGo中所示的最短路径上的基本块距离）。由于同一个被调用者函数可能有多个调用点，因此过程间边权重是调用者函数fi()和被调用者函数fj()之间的最短调用点权重(weight(fi,fj))。这也在公式2中显示，其中dfi()计算函数fi中的过程内距离。对于图1中的函数option1()，由于函数start和函数check()的调用点位于同一个基本块中，因此它们的边权重为0，而不是像AFLGo中那样为10。

调用者和被调用者之间的边权重形成加权CG。这允许SDFUZZ计算两个任意函数之间的精确CG距离。在公式3中形式化了计算过程间距离的方法。如果CG中至少有一条从函数fs到函数fe的路径，则它们的距离计算为最短路径中边权重的总和。否则，如果没有从函数fs到函数fe的路径，则距离被视为不可用或无限。

（3）种子选择和功率调度

SDFUZZ结合两个维度的反馈来指导种子的选择和功率调度。为了使模糊测试快速接近目标状态，SDFUZZ根据目标状态反馈和种子距离两个属性对语料库中的种子进行顺序排序。通常，SDFUZZ偏好目标状态反馈更好、距离更短的种子。它以目标状态反馈作为主要排序属性，距离作为次要排序属性。原因是捕捉运行时上下文的目标状态反馈更精确，可以更好地帮助接近目标状态。SDFUZZ还改进了AFLGo的功率调度算法，根据二维反馈为种子分配能量。

七、实验设计及结果

1. 实验一：目标状态生成能力

首先评估SDFUZZ是否可以自动提取真实漏洞的目标状态。选择Magma，这是一个广泛使用的模糊测试基准，包含138个错误及其相应的报告。检查所包含错误的崩溃转储，然后应用SDFUZZ提取目标状态。之后，手动验证提取的目标状态的正确性。结果表明，在138个案例中，SDFUZZ可以成功提取127个案例中的正确目标状态，其中崩溃转储包含在错误报告中。这表明SDFUZZ对真实漏洞具有很高的适用性。SDFUZZ无法为没有可用崩溃转储的案例生成目标状态。漏洞具有多种目标状态，例如，目标数量从一到三个不等，函数调用次数从二到六不等。根据经验，没有观察到目标状态对SDFUZZ性能的影响。

2. 实验二：SDFUZZ的性能

在一组已知漏洞上评估SDFUZZ的性能。

实验设置。构建了一个综合数据集。包括其他最近的DGF评估的程序和漏洞、Google Fuzzer测试套件和AFLGo的测试套件。总的来说，数据集中包含了45个独特的漏洞，并在表1中列出它们。所包含的漏洞涵盖了缓冲区溢出、堆溢出等一系列全面的漏洞类型，可以很好地评估SDFUZZ的能力。所有实验均在运行Ubuntu18.04的服务器上进行，该服务器配备两个18核IntelXeonGold6140CPU和256GBRAM。

为实验准备目标状态和种子输入。首先找到漏洞报告的来源并提取目标状态。SDFUZZ成功提取了所有案例的目标状态。然后，使用SDFUZZ对漏洞进行五次测试，每次测试都有24小时的时间限制。对于Google的Fuzzer测试套件中的漏洞，使用存储库中提供的种子输入（如果可用）；对于其他案例，使用空种子输入。

必需代码识别。选择性检测技术可以显著缩小模糊测试范围到所需代码。首先分析SDFUZZ为45个评估漏洞识别的所需代码的比例。SDFUZZ平均消除了48.18%的不需要的函数，并将模糊测试范围缩小到其他51.82%的需要的函数。对于几个案例（例如re2中的#24），SDFUZZ甚至可以消除超过80%的不需要的函数并触发漏洞。

漏洞暴露。测量了暴露已知漏洞所用的时间，并将评估结果列于表1。SDFUZZ在24小时（1,440分钟）的时间限制内可以复现45个漏洞中的44个。这证明了SDFUZZ在暴露已知漏洞方面的高效性。

3. 实验三：与现有方法比较

将最先进的开源定向模糊器作为比较目标：AFLGo、WindRanger和SieveFuzz。Beacon以二进制文件的形式公开提供。

漏洞检测。比较结果如表1所示。SDFUZZ的表现通常优于其他定向模糊器，暴露的漏洞更多。具体来说，AFLGo、WindRanger、Beacon和SieveFuzz分别暴露了36、37、34和40个漏洞。暴露的漏洞数量少于SDFUZZ。在大多数暴露的案例中，SDFUZZ所用的时间比比较的定向模糊器要短。速度分别比AFLGo、WindRanger、Beacon和SieveFuzz高出2.83倍、2.65倍、1.29倍和1.81倍。SDFUZZ的表现也分别比AFLGo、WindRanger、Beacon和SieveFuzz高出18.60倍、12.55倍、4.25倍和8.80倍。表1中划出了每个漏洞的最佳结果。我们观察到SDFUZZ在45个案例中的35个案例（77.8%）中表现最佳，证明了技术的有效性。

代码消除。SieveFuzz使用基于目标站点位置的代码消除技术并开源。SieveFuzz平均删除了约31.53%的不需要的代码，比SDFUZZ消除的少43.29%。这证明了目标状态信息对于代码消除的好处。

路径修剪和模糊测试吞吐量。路径修剪的有效性可以反映在模糊测试吞吐量中，即每单位时间的执行次数。发现SDFUZZ实现了更高的模糊测试吞吐量。由于不同的程序通常具有不同的处理时间，因此计算吞吐量因子值作为每种情况下工具的吞吐量与AFLGo的吞吐量之比。然后，计算所有情况下的几何平均值作为平均吞吐量。SDFUZZ、WindRanger、Beacon和SieveFuzz的吞吐量因子值分别为9.32、0.93、1.43和8.09。这表明，与仅使用距离度量的模糊器相比，采用执行终止技术的模糊器具有更高的吞吐量。

漏洞触发路径。本文发现其他模糊器大多通过与SDFUZZ从目标状态派生的路径相同的路径触发漏洞。具体来说，重放模糊器生成的暴露漏洞的崩溃输入，并分析触发的程序路径。然后，将这些路径与目标状态中的路径相关联。SDFUZZ通过这些路径触发漏洞。另一方面，AFLGo、WindRanger、Beacon和SieveFuzz最终分别在28、20、25和30个案例中采用了目标状态中的路径。这样的观察有两个含义。首先，SDFUZZ可以直接将探索引向此类路径，而无需在其他路径上花费太多精力。这是SDFUZZ与其他定向模糊器相比具有卓越性能的根本原因。其次，通过朝着目标状态前进，虽然SDFUZZ可能会忽略一些其他路径，但这不会严重损害SDFUZZ的性能。

4. 实验四：消融实验

在同一数据集上进行了消融研究，以了解SDFUZZ中的每种技术如何影响性能。首先，为了评估目标状态的影响，设计了SDFUZZ的一个变体，即SDFUZZbl，它仅利用漏洞位置（目标站点）——简化的目标状态。通过禁用其选择性检测添加了SDFUZZ的变体——SDFUZZ-si。此外，我们设计了四个变体用于逐个组件的评估。由于SDFUZZ建立在AFLGo之上，因此每个变体都启用了AFLGo上的一项关键技术。特别是，AFLGO+si、AFLGO+et、AFLGO+sf和AFLGO+df分别在AFLGo上进一步启用了选择性检测、执行终止、目标状态反馈和距离反馈。

八、总结

定向灰盒模糊测试通常会不必要地探索无法触发漏洞的代码和路径。在本文中，提出了SDFUZZ，这是一种由目标状态驱动的高效定向模糊测试器，可缓解此问题。SDFUZZ通过消除不必要的代码和提前终止无法达到目标状态的执行来排除不必要的探索。SDFUZZ还采用二维反馈机制来主动引导测试方向。评估结果表明，SDFUZZ可以更快地触发漏洞，并且优于先前的工作。SDFUZZ还发现了四个以前未知的漏洞，证明了其在自动化漏洞验证中的实用价值。

—END—