-- SoK: The Progress, Challenges, and Perspectives ofDirected Greybox Fuzzing


Introduction

灰盒模糊测试技术现在已经成为了软件测试中最具可扩展性和实用性的方法。与黑盒模糊测试和白箱模糊相比,灰箱模糊具有较高的效率和有效性。灰盒模糊测试广泛用于测试应用软件、库[5]以及内核代码,并在实践中应用于各种目标,包括协议、智能协议和多线程程序。并且大多数的灰盒模糊测试都是基于覆盖指导的,目的是在有限的时间预算内覆盖尽可能多的程序路径。这是因为代码覆盖率与bug覆盖率是紧密相关的,并且具有更高代码覆盖率的模糊器可以发现更多的bug。但是将不同的代码视为相同的是不合适的,有些代码的bug可能性会更大,通过盲目地扩展代码覆盖范围来测试软件效率较低,特别是在极端情况下。因此研究人员提出了导向型模糊测试。

与基于覆盖的模糊测试的全局范围覆盖不同,导向型模糊测试会将大部分时间花在特定目标位置(容易出bug的地方)。传统的导向模糊测试是基于符号执行,但是这种方法会受到符号执行一些问题而限制(复杂的约束求解和路径爆炸等问题)。后来提出了手动标记目标和基于距离(种子与目标)的导向型灰盒模糊测试(AFLGo)。现代的DGF已经超越了依赖人工标记的目标站点和基于距离的度量来确定种子优先级的主要模式。在不同的场景下,会使用不同形式的目标(如目标序列)来使用不同的方式(如序列覆盖率)引导Fuzzing。


Background

1. Coverage-guide Greybox Fuzzing(AFL)

基于覆盖引导的灰盒模糊测试技术是目前流行的模糊测试方案。AFL又是其代表。接下来用AFL的原理说明一下CGF的原理。AFL使用在程序中插桩,从而可以在运行时获得边覆盖率。然后他会从种子队列中选择一个种子对其赋予能量并进行突变,如果突变的种子触发了新的路径或者是触发bug都会将其作为一个新的种子添加到中子队列中。CGF核心技术可以大致分为覆盖粒度,突变策略,种子优先级,能量调度。

2. Directed Greybox Fuzzing

   image.png

DGF与CGF不同,DGF会将更关注于目标点的覆盖,而不是全代码的覆盖。AFLGo是第一个导向型的灰盒模糊测试技术,接下来以AFLGo来说明DGF的原理。首先AFLGo会手动的设置目标点和计算目标基本块到其他基本块的距离。然后在模糊测试中,会更具覆盖率和距离来判断该输入是否添加到种子队列。并且会根据模拟退火策略基于种子不同的能量。(与AFL的核心区别,就是AFLGo会利用距离特性逐渐让种子执行路径靠近目标点)

3. Difference between CGF and DGF


4. Application of DGF



The state of the art works

本文调查了过去三年里的28个DGF,并根据相应的指标对这些工作使用核心技术的进行分析。

1. Directed Type

Directed type 是DGF中一个重要的指标。起初Directed type是手动标记的目标点(例如AFLGo 和Hawkeye)。但是后来的研究发现目标之间的关系也是有作用的(例如UAFuzz和UAFl)。Lolly和Berry使用目标序列来引导Fuzzing(其中Berry结合了符号执行来增强Lolly)。Memlock是通过内存使用来发现未控制的内存消耗bug的。vfuzz是基于脆弱概率,通过深度学习模型预测脆弱概率来引导模糊过程到潜在的脆弱代码区域。SemFuzz和DrillerGo利用从CVE描述和git日志中检索到的语义信息来指导fuzzing和生成PoC利用。SAVIOR和parmeSan通过sanitizers的信息​来引导Fuzzing。IJON利用人工分析的注释来指导fuzzer克服重大障碍。 PFUZZER被显式地定向于输入解析器,以很好地覆盖可能的输入空间。

2. Input Optimization

标记目标之后,DGF需要生成种子输入来调用模糊过程。良好的种子输入可以使模糊过程更接近目标位置,提高后期突变过程的性能。SeededFuzz侧重于改善初始种子的产生和选择,以达到定向Fuzzing的目的。它利用动态污染分析来识别种子中能够影响程序目标点值的字节,并通过改变相对字节生成新的输入,并将它们提供给目标程序以触发错误。FuzzGuard使用一种基于深度学习的方法,在执行之前过滤掉无法到达的输入。它将程序输入视为一种模式,并使用大量标有可达性的输入来训练一个模型。然后,FuzzGuard利用该模型在不运行输入的情况下预测新生成输入的可达性,从而节省了实际执行的时间。TOFU利用以protobuf规范形式存在的程序输入的已知结构来生成有效的输入。SemFuzz利用从CVE描述和git日志中检索到的信息(系统调用和参数)构建设计的种子输入,以增加命中脆弱功能的概率。TIFF和ProFuzzer识别输入类型,以协助突变,以最大限度地触发内存损坏bug的可能性。PFUZZER[27]是一种语法驱动的方法,它专门针对输入解析器,在不生成合理输入的情况下最大化输入空间覆盖率。

3. Seed Prioritization

DGF的关键是选择并优先选择在某些指标下表现更好的种子。目前使用的指标可以分为三个:距离,相似度,概率。

4. Power Assignment

目前大多数的DGF工具能量分配阶段都使用了模拟退火的算法。AFLGo使用模拟退火为基础的能量调度逐步分配更多的能量给更接近目标位置的种子,同时减少能量给更远的种子。与传统的随机漫步调度不同,总是接受更好的解决方案,可能会陷入局部最优,模拟退火接受不如当前的解决方案有一定的概率,所以可以跳出局部最优,达到全局最优解决方案。Hawkeye也采用了模拟退火,但增加了优先级。因此,靠近靶点的种子先突变,进一步提高了方向性。LOLLY采用优化的基于模拟退火的功率调度来实现最大的序列覆盖。

5. Mutator Scheduling

一些模糊器优化突变策略以辅助定向模糊,这主要是通过将突变体分类到不同粒度来实现的。Hawkeye利用了一种自适应突变策略,它将突变器分为粗粒度和细粒度。粗粒度的mutators用于在突变期间更改大量字节,而细粒度的mutators只涉及几个字节级的修改、插入或删除。当种子能够达到目标函数时,它提供了较少的发生粗粒度突变的机会。一旦种子到达目标,进行细粒度突变的时间就会增加,而粗粒度突变则会减少。在实践中,mutators的调度是由经验值控制的。V-Fuzz将突变策略分为轻微突变和严重突变,并根据实际的模糊状态通过阈值动态调整突变策略。SemFuzz执行类似的分类,只是它关注系统调用。SemFuzz利用对输入的粗突变来找到一个系统调用序列,以便将执行移动到“易受攻击的函数”。之后,它切换到syscall序列上的细粒度突变,以监视“关键变量”。TAFL也采用了感知粒度的mutators调度,基于经验观察:(1)粗粒度mutators在路径增长上优于细粒度mutators;(2)组合多个变异体比使用单一变异体性能更好。根据输入类型探测所识别的输入字段类型,ProFuzzer需要不同的突变策略。

6. Data-flow Analysis

数据流分析,如污染分析,可以反映突变对生成的输入的影响,有助于优化突变策略和输入生成。RDFuzz利用一种disturb-and-check的方法来识别和保护距离敏感内容的输入,这对于保持距离是至关重要的。在变异期间防止这些内容突变可以帮助更有效地接近目标代码位置。UAFL采用信息流分析来识别条件语句中的输入与程序变量之间的关系,并对这些信息流强度高的输入字节赋予更高的突变可能性,因为它们更有可能改变目标语句的值。SemFuzz通过反向数据流分析跟踪关键变量所依赖的内核函数参数。SeededFuzz利用动态污染分析来识别在安全敏感的程序站点上影响值的种子字节。PFUZZER使用输入的动态污染来将处理过的每个值与它所派生的输入字符关联起来。TIFF通过内存数据结构识别和动态污染分析来推断输入类型,增加了基于类型突变触发内存损坏漏洞的概率。然而,数据流分析通常会增加运行时开销。

image.png

Challenges and Solution

1. Binary Code Support

目前很多的DGF对源代码依赖性比较强,如果针对于二进制程序,很多的DGF都不可用。二进制fuzzing有三个问题。

(1)繁重的运行时开销。因为简单的二进制代码模糊测试通常需要利用一个全系统仿真器,而目前的全系统仿真器通常效率比较低,开销比较大。

(2)目标信息收集困难。对于开源的PUT,我们可以从各种渠道获得目标信息,比如CVE漏洞描述、git提交日志中的更改,以及源代码中关键位置的人工体验。但是,对于一个放入二进制代码,我们只能从bug跟踪中提取目标信息。

(3)难以确定目标。源码可以很好的确定目标,但是对于二进制而言,确定目标就很困难,可能需要利用IDA pro对其进行反汇编。

解决方案

缓解性能限制的可行解决方案是硬件辅助。Intel PT是最近Intel处理器中一个轻量级的硬件特性。它捕获关于程序执行的跟踪数据,从而取代动态检测的需要。使用Intel PT捕获的包跟踪以及相应的PUT二进制文件,安全分析人员可以完全重建PUT的执行路径。平均而言,基于Intel pt的方法比QEMU-AFL快4.3倍。目前这种方法还没有应用到DGF。

针对二进制码级目标识别标注问题,可以利用基于机器学习的方法或启发式二进制扩散方法自动识别脆弱码。

2. Automatic target identification

大多数已知的导向模糊测试工具需要人工手动的标记目标。这些标记需要一定的先验知识,然而获取这些先验知识是一个挑战。为了实现目标的自动识别,(1)我们可以使用静态分析工具找到PUT中潜在的危险区域(这些工具通常是特定于所使用的bug类型和编程语言的)(2)或者可以利用compiler sanitizer passes (例如UBSan)注释PUT中的潜在bug。(3)基于深度学习的方法对脆弱性进行预测 (4)可以通过基于Bindiff的二值级比较,提取不同的函数及其不同的基本块,从而识别目标的补丁分支。

3. Differentiated weight metric

目前很多的优先级的指标考虑存在问题,例如基于距离的种子优先级,只考虑分支的长度,没有考虑支跳转之间的概率,所以这种不精确性会限制DGF的性能。

解决方法:

    一个可能的解决方案是考虑分支跳转概率。当基于概率评估目标的可达性时,每个种子都是根据种子生成一个输入到达目标的可能性来排序的,也就是将该种子的当前执行路径转换为经过目标的目标路径的概率。由于执行路径可以看作是连续分支的马尔可夫链,因此路径的概率可以通过收集路径内所有分支的概率来计算。利用蒙特卡罗方法统计计算出分支概率的比值,从而估计出分支概率。 这种基于概率的方法一个可能的缺点是潜在的运行时开销。统计跳跃计数和概率计算都引入了额外的计算。缓解性能下降的一个简单方法是区间采样。另一种可能的解决方案是加速计算,这涉及到如何存储和访问元数据(其实就是设计一种新型的数据结构)。

4. Global Optimum Deviation

当DGF测试中存在多个目标时,如何协调这些目标是另一个挑战。一种策略是基于Dijkstras算法寻找全局最短距离,就像AFLGo一样。但是,这种全局最优可能会错过最接近某个目标的局部最优种子,从而导致偏差。另一种协调多目标的策略是目标分离。对于每个种子,只选择所有目标之间的最小距离作为种子的距离,并根据最小距离对种子进行优先排序。这样,我们可以避免局部最优偏差,但这可能会减慢达到特定目标的速度。

5. Missing Indirect Calls

DGF在确定种子优先级,无论使用哪种指标,都需要基于控制流图或者是调用图。但是大多数研究者通过LLVM的内置api静态构造控制流图和调用图都会缺少间接调用儿时的图的不完整。如果没有间接调用,基于调用图和控制流图的距离测量是不准确的,影响DGF到达目标的能力。

可能的解决方法

(1)对函数指针执行Andersen的points-to分析。然而,这种基于包含的上下文不敏感指针分析会导致间接调用有许多传出边,可能会产生对给定输入不可能产生的执行路径。

(2)TOFU使用函数类型签名来近似每个间接调用站点的可调用集。但是,它没有考虑强制类型转换,强制类型转换可能允许调用不同类型的函数,从而导致不精确性。

(3)对于动态情况,ParmeSan识别了实际执行过程中间接调用缺失的边,并逐步对调用图进行补偿。最后,在执行了足够多的模糊处理之后,图往往是完整的。然而,这样的解决方案不可避免地增加了运行时开销,并且不能保证完整性。

6. Exploration-exploitation coordination

DGF面临的最后一个挑战是如何协调exploration阶段和exploitation阶段一方面,更多的exploration阶段可以为开发提供充分的信息;另一方面,过度exploration阶段会占用大量资源,延缓开发。exploration阶段和exploitation阶段如何界线是一个挑战。AFLGo是以利用运行时间来进行界定(exploration阶段(20小时)和exploitation阶段(4小时)),但是这种方式非常不灵活。

解决办法:

(1)RDFuzz使用一个交织的时间表,交替进行exploration阶段和exploitation阶段

(2)另一种可能的解决方案是利用动态策略来协调exploration阶段和exploitation阶段的分离,这样可以在exploration阶段和exploitation阶段之间进行适应性转换。具体策略如下图。

   image.png

Discussion

1. Multi-targets Relationship Exploitation

目前很多的DGF很多都没有关注目标之间的关系当有多个目标时,可以使用多个目标之间的关系来优化DGF。如果它们不相关,我们可以给它们分配权重来区分重要性或概率。否则,隐藏的关系可以被提取和开发,以提高方向性。作者提出了一些常见的关系。(1)空间关系。目标在执行树上的相对位置。(2)​有状态的关系。​对于涉及程序状态的目标,我们可以考虑它们在状态空间中的位置。(3)交叉关系。对于多线程程序,线程调度影响不同线程中事件的执行顺序。建议:DGF应该多注意目标之间的关系。

2. Technology Integration

DGF技术可以多与其他技术结合从而提高fuzzing的效率和有效性。常见的技术有:静态分析、控制流分析、数据流分析、机器学习、语义分析、和符号执行。

3. Implementation Limitation

很多的工具都是基于AFL实现的,但是AFL本身就有自己的缺陷,所以会导致这些工具产生相似的缺陷。AFL的缺陷有(1)由于AFL的边缘覆盖是基于基本块转换的,因此只能在基本块级敏感,不能区分指令级的路径差。(2)另一问题就是路径碰撞,因为AFL编译时会对每个分支跳转插入随机数,由于这些随机数会重复,从而导致路径碰撞。这个问题可以使用哈希方案来解决。

4. Efficiency Improvement

由于很多工具会使用数据分析或者其他的技术,从而会使得性能下降。所以应该将与执行无关的计算从运行时转移到编译时。或者在运行时用一些适合的数据结构来提高性能。

5. Future research suggestions