👍
在本论文中,我们介绍了AFL++,这是一个由社区驱动的开源工具,集成了最先进的模糊测试研究,旨在使研究具有可比性、可重现性、可组合性和最重要的是可用性。它提供了多种新颖的特性,例如其自定义变异器API,能够在许多阶段扩展模糊测试过程。借助它,有经验的安全测试人员还可以编写特定目标的变异器。我们希望AFL++不仅成为当前研究的新基准工具,也能成为未来研究的基准工具,因为它可以快速测试新技术,并评估单一技术与最先进技术的效果,以及与其他技术的组合效果。本论文对精选的模糊测试技术进行了评估,揭示了一个事实,即虽然每种新颖的模糊测试方法可以提高某些目标的性能,但会降低其他目标的性能。这是未来模糊测试研究在评估中应该考虑的一个观点。
模糊测试(Fuzzing)的研究是一个蓬勃发展的领域。模糊测试以完全自动化的方式揭示了各种各样的漏洞。近年来,信息安全社区对模糊测试产生了浓厚的兴趣,并在不同领域引发了进步。在Shoshitaishvili等人进行的测试中,符号辅助的模糊测试识别的漏洞数量几乎是符号执行的三倍[39]。旨在改进模糊测试的技术数量不断增加[28],有时甚至不需要完全功能的代码。此外,模糊测试技术通常是正交和独立开发的,因此将它们组合起来可能是一个漫长的过程。对于工业界和开源社区来说,决定哪些研究值得关注可能是困难的。他们可能会坚持使用基本设置,尽管现代研究可能会更快地找到目标的更多漏洞。另一方面,研究人员本身可能很难评估他们的新工具,并且可能会发现自己无法将功能与解决模糊测试中不同但相关问题的兼容技术相结合,例如为其变异器选择最近的种子调度。如果新的反馈概念无法与解决其他问题的现有技术相结合,比如克服难以比较的指令,那么它可能无法充分发挥其潜力,从而降低了研究在论文上的影响力
在本论文中,我们试图通过提高广泛可用的、以研究为基础的模糊测试水平,以及为研究人员提供一个可扩展的API来解决这些问题。我们提出了一个新颖的模糊测试框架,AFL++。未来的研究可以将AFL++作为一个新的基准。它使研究人员有可能评估他们的提案与AFL++中已实现的最先进的正交特性的组合,同时大大降低了实施的难度。同时,它为业界专业人士提供了一系列易于使用的功能,这些功能来自于前沿的研究,可以极大地改善模糊测试活动的结果。AFL++是AFL模糊测试工具的重新设计分支,由Zalewski开发[47],在学术界和工业界都已经证明是一个坚实的基础。
选择AFL作为基础是因为在项目开始时,AFL已经停止维护了18个月,同时有很多社区补丁和学术分支可用。因此,这为项目提供了一个完美的起点。与之相比,LIBFUZZER和HONGGFUZZ在项目开始时仍在积极维护,目前仍未有较大的分支和增强(虽然ENTROPIC [9]和Vranken的增强 [41]等是值得注意的例外情况)。
虽然AFL++最初是基于AFL的一组补丁和分支,但随着时间的推移,我们重新实现了非基于AFL的研究,如REDQUEEN [5],以及将AFL的研究级扩展重新设计为适用于生产环境的版本。我们在这个最先进的基础上添加了新颖的特性,这些特性也将在本论文中讨论。
总之,本论文将深入探讨一年来积极的开源模糊测试研究的见解,讨论所学到的教训,并探讨新颖的自定义变异器API,这是实施新型模糊测试研究的一种方式。
American Fuzzy Lop,简称AFL [47] 是有史以来最广泛使用和最成功的覆盖率导向模糊测试工具之一。它是许多与模糊测试相关的出版物的当前基准。在本节中,我们深入讨论了 American Fuzzy Lop 以及在过去几年中针对改进该模糊测试工具特定方面所进行的研究,但尽可能简洁明了。本节中解释的概念与将在第3节中介绍的AFL++直接相关。
AFL是一种变异的、覆盖率导向的模糊测试工具。它通过变异一组测试用例来达到程序中以前未被探索过的点。当这种情况发生时,触发新覆盖的测试用例会被保存在测试用例队列中。
AFL的覆盖率反馈是一种混合指标,将边缘覆盖率与在一次运行中执行各个边缘的次数进行组合。这个计数被分桶到2的幂次方,以避免路径爆炸。如果某个输入探索了至少一个边缘的新桶,那么它被认为是有趣的(即保存到队列中)。这些桶,或者称为命中计数,会在执行过程中记录到一个共享的位图中,其中每个字节表示一个边缘。这个位图的大小是有限的,因此可能会发生碰撞。AFL使用了加权最小集覆盖的近似方法来维护一组在覆盖范围方面被偏好的测试用例,以速度和大小作为权重。
利用覆盖率反馈,AFL还尝试在队列中的每个测试用例上,通过一个称为修剪的阶段,来减小测试用例的大小,提高目标的速度,并同时保持覆盖率不变。
AFL的变异分为两类:确定性变异和随机(havoc)变异。确定性阶段包括对测试用例内容进行单一确定性变异,例如位翻转、添加、替换为一组常见有趣值(如-1、INT_MAX等)。在随机阶段,变异是随机堆叠的,还包括对测试用例大小的更改(例如添加或删除输入的部分)。此外,在稍后的阶段,AFL可能会将两个测试用例合并为一个,并应用随机变异,这被称为拼接(splicing)阶段。
为了避免execve()
的开销,AFL采用了所谓的forkserver。模糊测试器将一个通过IPC机制控制的forkserver注入到目标程序中。每当AFL需要执行一个测试用例时,它会先写入输入,然后告诉目标程序自己进行fork操作。子进程将执行测试用例,而父进程则等待。forkserver也可以在目标程序中稍后fork。在这种情况下,模糊测试器不需要每次运行昂贵的初始化和启动过程的开销。
Persistent mode是为了显著提高性能而设计的。众所周知fork()
是一个性能瓶颈,Persistent Mode不会为每个测试用例进行fork操作。相反,可以向目标程序中插入一个循环,在每次迭代中执行一个测试用例。为了使其正常工作,每次迭代需要尽量减少状态变化。这意味着在每个迭代中,目标程序应该保持和上一次迭代相同的状态,不引入额外的状态变化。这样可以避免重复执行初始化和启动过程的开销,从而提高性能。
现代的覆盖率导向模糊测试工具可能会实现不同的优先级算法,以安排模糊测试流水线中的各个元素。调度器的目标通常是通过智能测试用例选择来提高总体覆盖率和漏洞检测能力。
由Böhme等人开发的AFLFAST [11]表明有必要加重对低频路径的重视程度,以探索更多分支并发现更多漏洞。他们对AFL进行了几项改进,不仅着重于测试常见路径,还旨在暴露出额外的程序行为。他们强调了两个问题:
作者通过一组新颖的搜索策略来解决第一个问题,通过引入六种功率调度来计算在模糊测试过程中收集到的参数所产生的能量来解决第二个问题。
作为种子调度的一个横向问题,MOPT(Mutation-Oriented Programming Technique)引入了变异调度。在这项工作中,Lyu等人探索了使用自定义粒子群优化算法给予不同的变异操作符不同的概率的可能性。这种优化提高了模糊测试器快速发现覆盖范围的能力。在他们对AFL的修补程序中,作者将模糊测试阶段划分为以下两个模块。Pilot模块用于评估操作符,并根据效果分配概率。Code模块生成变异,并考虑到Pilot阶段中找到的概率。
传统上,覆盖率导向的模糊测试器在探索其背后的代码时常常遇到障碍。典型的障碍包括较大的比较操作,例如字符串比较和校验和检查。为了解决这个问题,进行了一系列的研究。
LAF-INTEL [2] 是一个旨在绕过复杂的多字节比较的工作,它将这些比较划分为多个单字节比较。通过这种方式,可以逐字节地进行这些比较,并且覆盖率导向的模糊测试器可以在每个部分中获得反馈。原始的实现是一组LLVM插件,用于拆分整数比较,还包括对字符串比较函数(如strcmp)的调用,当其中一个参数在编译时已知时。具体而言,LAF-INTEL 实现了以下细节:
最近,基于KAFL [36],REDQUEEN [5]在不使用造成巨大开销技术如污点追踪 [46] 或符号执行 [6, 37] 的情况下,探索了绕过硬比较和校验和检查的可能性,这与文献中其他的一些先前工作 [35] [12] [33] [44] 类似。该模糊测试器专注于被定义为输入状态(I2S)的比较,这是一种在其操作数中至少有一个直接依赖于输入的比较类型。作者表明许多会造成阻碍的比较属于这种类型,并开发了一种定位和绕过它们的技术。REDQUEEN首先在着色(colorization)
阶段增加输入的熵,通过用随机数据替换字节来保持测试案例的覆盖率。通过观察I2S比较的操作数,模糊测试器可以减少定位其在输入中位置的猜测次数。然后,REDQUEEN突变输入,替换从比较中提取的I2S标记,并再次使用这些信息来定位校验和检查并将其修补。在每个模糊测试阶段结束时,REDQUEEN再次使用I2S替换来修复新生成的有趣输入的校验和。如果失败,则修补过的校验和被检测为误报,将其移除。
模糊测试工具常见的问题是它们可能会生成大部分无效的输入,使得解析阶段后程序的状态变得无法访问。解决这个问题的方法是使用输入模型,有效地减少生成的输入空间。这使得基于反馈的模糊测试工具可以探索程序中的深层路径。
Pham等人引入了AFL的结构化模糊测试方法:AFLSMART [34]。AFLSMART使用PEACH [14] pits作为输入模型格式,PEACH是一种广泛用于结构化黑盒模糊测试的规范。这种选择使得可以重用为PEACH编写的协议规范。AFLSMART在第一次从队列中提取测试用例时进行解析。它以一种惰性方式进行解析,即延迟破解,这允许AFLSMART在探索覆盖率时如果足够好,可以避免浪费时间进行解析。解析步骤的结果是表示AST(抽象语法树)的虚拟结构。AFLSMART引入了高阶结构性变异,即对虚拟结构进行变异,而不是对原始字节进行变异。它可以配置为仅使用这些结构性变异,或者与Havoc中的其他变异方式一起使用。
在本节中,我们将解释AFL++的工程背景。AFL++的核心是AFL的一个分支版本,AFL是一种模糊测试工具,一部分学术模糊测试研究基于它,并且在工业中也得到了广泛使用。本节将介绍AFL++在原有基础上增加的功能,包括第2节中讨论的许多特性。AFL++的功能不仅限于本节讨论的内容。在可用性和工程方面的许多小的改进超出了本文的范围。有关这些小而有效的改进的深入介绍,请参阅AFL++的文档[18]。
AFL++整合了AFLFAST,并在其基础上添加了额外的能量调度。其中包括了AFLFAST的所有调度:fast、coe、explore、quad、lin、exploit。AFL++可以通过以下方法来控制这些调度:
默认调度是"explore"。除此之外,AFL++ 还添加了 "mmopt" 和 "rare" 调度。 "mmopt" 调度增加了最新种子的分数,以帮助更深入地探索新发现的路径。 "rare" 调度忽略了种子的运行时间,与所有其他调度不同,并且额外关注很少被其他种子覆盖的边缘,这是一个有效的度量,正如在[24] [10]中所展示的。
AFL++整合了比传统的AFL的确定性和Havoc管道更多的变异器。这些变异器可以与其他变异器组合使用。
AFL++可以轻松地为学术界的新研究进行扩展,并可根据漏洞发现的具体目标进行适应。为此,它提供了一个不断增长的API。目前的状态如下。
自定义变异器允许模糊测试研究在AFL++的基础上构建新的调度、变异和最小化方法,而无需像目前许多工具那样分叉和修补AFL。最初的支持最早在Holler的AFL分支[19]中独立开发,但随后得到了许多新功能的扩展。插件可以用C ABI兼容的语言编写,甚至可以用Python进行原型开发。借助当前的API,例如,AFLSMART可以完全重写为AFL++插件。以下功能目前可以实现:
afl_custom_(de)init 每个自定义变异器都可以使用这些易于理解的函数来初始化或反初始化模块,即afl_custom_init和afl_custom_deinit。AFL++的伪随机生成器种子会传递给init。然后,自定义变异器应确保在给定相同种子的情况下,模糊测试的结果是可重现的。
afl_custom_queue_get 这是一个回调函数,用于确定自定义模糊器是否应该对当前队列条目进行模糊。在这个例程中,用户还可以执行与输入相关的元数据初始化,例如用于结构化模糊的虚拟结构。
afl_custom_fuzz 在给定的输入上执行自定义变异。它接受一个额外的测试用例作为参数。
afl_custom_havoc_mutation 在给定的输入上执行单个自定义变异。这个变异会与混沌阶段中的其他变异叠加在一起。afl_custom_havoc_mutation_probability函数返回自定义变异在混沌阶段中被调用的概率,以进行调优(默认为6%,受到AFLSMART的启发)。
**afl_custom_post_process ** 在某些情况下,从自定义变异器返回的变异数据的格式不适合直接用这个输入来执行目标。例如,使用libprotobuf-mutator时,返回的数据是protobuf格式,对应于给定的语法,首先需要将其转换为目标的纯文本格式。在这种情况下,或者用于修复校验和和大小时,用户可以定义afl_custom_post_process函数。
afl_custom_queue_new_entry 在将新的测试用例添加到队列后调用此函数,这是一个有用的hook,可用于将元数据存储到磁盘上。
Trimming Support 在AFL++中实现的通用修剪例程(见第2.1.1节)可能会破坏复杂格式的结构。特别是当目标能够处理输入的一部分(例如覆盖率),然后在剩余的输入上出现错误时。在这种情况下,实现一个自定义的修剪例程是有意义的。该API由多个方法组成,因为在每个修剪步骤之后,必须根据地图对覆盖率位图进行修剪。
afl_custom_init_trim 在每次修剪操作开始时会调用此函数,并接收初始缓冲区。它应该返回在此输入上可能的迭代步数(例如,如果输入具有n个元素,其中一个应该被删除,则返回n-1)。如果实现的修剪算法不允许确定(剩余)步数的数量,那么它可以返回1,表示可以进一步进行修剪,而这将在afl_custom_post_trim返回0时进行。
afl_custom_trim 在每次修剪操作中都会调用此函数。它会记住当前状态,因此可以为每次迭代保存重新解析的步骤。它应该返回修剪后的输入缓冲区,其中返回的数据长度不能超过初始输入数据的长度。
afl_custom_post_trim 在每次修剪操作之后都会调用此函数,以通知修剪步骤是否成功(在相同的覆盖范围内)。此方法必须返回下一个修剪迭代索引(从0到在afl_custom_init_trim中返回的最大步数)。
AFL++实现了基于REDQUEEN的 Input-To-State(I2S)替换的变异器。除了上面描述的内容外,我们还进行了一些优化,以改进原始实现。
首先,着色化似乎在增加输入字节的熵方面非常有效,但如果例如关键字段(如大小字段)被随机变异,它可能会大大减慢模糊器的速度。所以我们扩展了着色化,不仅在覆盖位图的哈希保持不变时保留变异区域,还在执行速度保持在原始速度的2倍减慢范围内时保留。这一改进似乎在REDQUEEN的异常目标中发挥了作用。
另一个扩展是对每个比较进行概率模糊。如果模糊器在尝试绕过比较时未能生成有趣的输入,下一次将以较低的概率模糊此比较。这避免了在无法解决的比较上花费太多时间,这些比较似乎是I2S但实际上不是。
CmpLog Instrumentation 这个变异器不像原始的REDQUEEN实现那样使用断点来记录比较操作数,而是使用了与Fioraldi等人在WEIZZ中使用的类似的共享表。每个比较记录其最近256次执行的操作数,存储在一个256MB的表中,该表在模糊器和目标之间共享。
表的第一部分维护每个比较的元数据,如大小、ID和实际执行次数。512KB的总大小可以以高效的方式在缓存局部性方面进行遍历。元数据足以注册一个未使用的比较,并且永远不会访问与操作数相对应的内存。这种插装在LLVM和QEMU插装中都可用。
AFL++实现了MOPT的Core和Pilot模式。此外,AFL++还对MOPT进行了补丁,使其能够与Input-To-State变异器结合使用。另外,AFL++还支持将MOPT与标准的变异模式进行交替。
AFL++支持多种工具链进行插桩:LLVM、GCC、QEMU、Unicorn和QBDI。此外,它还提供了一个代理模块,可以将测试用例转发给目标,并为afl-fuzz提供任何类型的覆盖率,甚至包括远程和非覆盖率,比如电流消耗或JTAG分支地址等。
表1总结了在每个插桩后端中实现的最重要特性,这些特性在第3节中进行了讨论。
NeverZero 在插桩后端的选择之外,我们还针对AFL的hitcount机制进行了优化。使用一个字节作为位图条目的一个问题是,边缘执行的计数可能会溢出。当发生这种情况时,我们观察到如果一个边缘以256的倍数被触发,导致相应的位图条目溢出为0,模糊器处于不一致状态。我们尝试通过两种解决方案来解决这个问题,即NeverZero和Saturated Counters。前者通过始终将进位标志添加到位图条目来避免溢出为0,因此,如果一个边缘被执行至少一次,条目永远不会为0。后者在计数器达到255时将其冻结。在一系列的实验中,我们观察到NeverZero非常有效,可以提高AFL在覆盖率和速度方面的性能(种子选择现在考虑了以前隐藏的边缘)。然而,饱和计数器会降低AFL的整体性能。我们选择在大多数可用的插桩中将NeverZero作为AFL++的默认设置。饱和计数器仍然在AFL++存储库的一个分支中可用,以进行进一步的研究或复现。
我们从LLVM 3.4开始支持,一直到撰写时为止的LLVM 11版本,该版本当时处于测试阶段。在LLVM模式下,AFL++除了支持边缘覆盖率[43]之外,还支持一系列覆盖度指标:
Context-sensitive Edge Coverage 这种指标是通过将每个块的分配ID与被调用者的唯一ID进行XOR运算来计算的。这个解决方案首次在[12]中探讨过,在代码覆盖率方面似乎是有效的,但会带来更多的碰撞和较慢的速度。
Ngram 这种指标是指在记录边缘时,模糊器不仅考虑前一个块和目标块,还考虑了目标块和前N-1个块,其中N是一个介于2和16之间的数字。这种方法可以提供更多的上下文信息,可能会带来更好的代码覆盖率。
在LLVM模式下,AFL++除了用于覆盖率反馈的LLVM pass外,还附带了几个额外的pass。所有的LAFINTEL pass都包含在内,并带有一个实验性模式,可以拆分浮点比较,这在诸如视频解码器或JavaScript解释器等软件中非常常见。此外,字符串比较函数分析也得到了改进,以便能够在分配固定字符串时处理全局和局部变量。还有CmpLog pass,正如前面所讨论的。一个广泛使用的特性,例如Fratrik [29]使用的,是可以指定要进行插桩的特定源模块。这在处理许多输入格式的目标中非常有用,用户只想专注于其中之一。在持久模式中,除了AFL中传递输入到目标的标准方式(stdin或文件),AFL++还可以通过共享内存传递新的测试用例。这种配置在持久模式下带来了额外的2倍速度提升,从而在初始测试中总体上加速了10-20倍,相对于fork模式。
AFL++的LLVM模式还实现了INSTRIM [20]补丁,结合了之前提到的所有功能。INSTRIM是一种在LLVM中进行插桩时选择基本块的有效方法。它通过基于支配树的分析,避免了在不必要的位置放置插桩。在大多数目标上,它将所需的插桩位置数量减少到标准插桩的至少一半,从而在性能和速度方面提高了模糊测试的效果。
除了旧的afl-gcc编译器,AFL++还提供了一个GCC插件。该插件包括延迟初始化和持续模式的支持,类似于AFL LLVM模式。支持的功能与LLVM不完全相同,但在AFL++中计划添加更多功能,以最终达到功能平衡的目标。
在AFL++中,针对二进制文件的模糊测试,版本2.1的AFL QEMU补丁几乎完全被基于QEMU 3.1.1的一套更好的补丁所替代。与其他基于二进制修补的二进制文件模糊测试(如基于二进制修补的retrowrite [13])相比,QEMU模式在仿真时添加了插桩。基本块的转换不再在QEMU中的上下文中记录,而是使用助手进行内联的日志记录例程的调用。通过这种方式,我们可以重新启用AFL禁用的块链接(首次以线程不安全的方式在[8]中展示),平均加速2-3倍。使用助手还可以使用线程局部存储,这是TCG[3]不支持的概念。最近,我们的QEMU模式还由Fioraldi扩展,加入了QAsan [16],以支持对堆违规进行污染检查,包括AddressSanitizer的基于动态二进制翻译的实现 [38]。
CompareCoverage 为了缩小源码级和二进制级模糊测试之间的功能差距,AFL++ QEMU模式可以使用CompareCoverage [31]类似于LAFINTEL的方式来分割比较操作。与LLVM pass不同,代码不会被修改,而是hook所有的比较操作,然后比较每个操作数的每个字节,如果相等则增加一个不同的位图条目。这种插桩类似于LIBFUZZER的基于popcnt的插桩,但在字节级别上操作,因此生成的输入较少,避免了路径扩展问题。这个问题使得LIBFUZZER的value-profile模式在某些目标上比正常模式效率稍低。它可以配置为仅分割具有立即操作数的整数比较、所有整数比较,或所有整数和浮点数比较。
Persistent Mode 与以前的QEMU模式相比,AFL++的QEMU模式支持持久模式。实现持久模式有两种主要的方法:
这种模式甚至可以达到10倍的加速效果,建议尽可能使用。
对于对固件等二进制文件进行模糊测试,AFL++集成了afl-unicorn的分支,由Voss[40]开发,将AFL支持添加到了Unicorn Engine[30]中,称为unicornafl。虽然Voss的原始版本在初始基本块上启动了fork服务器,并且只能通过Python进行垃圾回收的方式使用,但AFL++的unicornafl添加了一个低级C API,以及与Rust和Python绑定,直接与AFL++交互。Unicorn已经包含了设置页面映射、读写内存和寄存器、添加钩子、以及根据不同条件启动和停止执行的API。AFL++特定的API允许在任何时候启动快速的持续模式,并设置多个退出和后处理程序以检测崩溃。
该API提供了uc_afl_forkserver_start,这是一个特定的调用,可以在某个特定的时间点启动fork服务器,实际上是在模糊测试运行之前冻结当前状态,并告诉AFL++开始生成输入。
一个特殊的uc_afl_fuzz函数作为一个一站式解决方案,直接为每个测试用例读取输入 - 支持持久模式。目标固件在父进程中保持相同的状态,每个模糊测试用例都针对一个分叉的模拟器副本执行。此外,forkserver还包含了一个Unicorn的JIT缓存机制,受到AFL QEMU模式的启发。Unicornafl将插桩直接添加到翻译的块中,减少了对间接跳转的需求,重新启用了类似QEMU模式中讨论过的优化的块连接。uc_afl_fuzz函数如下:
fuzz函数还接受一个退出点列表,指示在哪些点上模拟将停止,一个标志,指示是否应该在没有Unicorn错误条件的情况下也调用验证回调函数,以及一个额外的整数计数器,指示是否以及多少次在再次分叉之前持续模式循环。Maier等人在AFL++的基础上使用了它来对内核进行模糊测试[26],甚至对RTOS进行了模糊测试[27]。
本文作者:Du4t
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!