Fuzzing a survey 译文

本文翻译自 《Fuzzing: a survey》

https://link.springer.com/article/10.1186/s42400-018-0002-y

Copyright information

© The Author(s) 2018

Open Access

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Update: 2020-11-03

概述

漏洞是威胁互联网安全的根源之一。为了提前发现、修复漏洞，研究者已经开发出几种不同的测试手段，其中模糊测试是应用最为广泛的技术之一。近年来，模糊测试解决方案例如 AFL，已经在漏洞挖掘领域取得了不小的成果。这篇文章主要总结近年来出现的 fuzz 技术，并且比较它们孰优孰劣。

首先我们讨论一个问题：为什么 fuzz 技术如此流行？通过比较不同的漏洞挖掘方案总结一个答案。
接着我们回顾 fuzz 技术，并且详细讨论其中最为流行的技术：基于覆盖率的模糊测试。然后我们提出一种可以使 fuzz 更加聪明、效率更高的技术。
最后我们展示一些 fuzz 实例，讨论 fuzz 未来的发展方向。

简介

安全漏洞已经成为互联网的主要威胁之一，在 RFC 2828 给出漏洞的定义：漏洞是一个系统在设计、实现、操作、管理上的瑕疵或弱点，攻击者可以利用这些弱点绕过系统的安全策略。
通过利用漏洞(特别是 0day 漏洞)，攻击者可对系统造成严重的威胁。
2017 年的 WannaCry 勒索者病毒所利用的就是微软 SMB 协议漏洞。根据报告，WannaCry 在一天内感染了分布在 150 个国家或地区近 230000 台计算机设备。它对金融、能源、医疗等产业造成了不可估量的损失。
考虑到漏洞对系统造成的严重危害，研究者们在漏洞挖掘技术上投入了很多努力。
目前提出的漏洞挖掘方法有：静态分析、动态分析、符号执行、模糊测试
其中 fuzz 技术允许在对测试目标知之甚少的情况下展开测试，正处于热门阶段，在工业控制领域尤为如此。
fuzz 的概念于 1990 年代首次提出。通过数年的研究，fuzz 技术得到了一定的发展。然而在实际测试中，fuzz 只能找到有限的内存破坏漏洞，并且对代码的覆盖率很低。此外，随机的测试流程对于漏洞挖掘来说效率极低，所以很多提升 fuzz 效率的方式逐渐被提出。
结合了反馈导向-遗传算法的 fuzz 技术较之前更加灵活高效。其中的佼佼者就是 AFL fuzzer。受到 AFL 的启发，很多高效的解决方案和改进策略被提出，fuzz 技术和十几年前大有不同。因此，我们有必要总结一下研究者们杰出的工作，并且展望 fuzz 技术的未来。

这篇文章组织结构如下：“背景知识”小节介绍了漏洞挖掘的基础知识和技术，”模糊测试“小节针对 fuzz 技术给出详细的原理描述，包括基础概念和 fuzz 面临的关键问题。在“基于覆盖率的模糊测试”小节中，我们将介绍一种 coverage-based fuzzer 以及研究者们围绕它所做的一些工作。在“技术融合”小节中我们总结一下能够提升 fuzz 效率的几种技术，以及原理。“对不同应用进行模糊测试”小节针对几种不同的应用进行模糊测试。“fuzz 技术的新趋势”小节我们讨论和总结 fuzz 技术的发展趋势。最后在“结论”小节中总结这篇文章。

背景知识(Background)

在本节中，我们对于传统漏洞挖掘技术给出一个简短的介绍，包括静态分析、动态分析、污点追踪、符号执行和模糊测试。接着我们分别总结这些方案的优缺点。

静态分析
静态分析指的是在不运行程序的情况下进行某些分析操作。实际上静态分析手段经常被用在具有源代码或者抽象代码的情况。通过分析词法、语法、语义、数据流、模型，可以找到隐藏在内部的 BUG。
静态分析的优点是检测速度快。分析人员可使用静态分析工具快速检查源代码，并且在短时间内定位 BUG。然而在实际应用中，静态分析的错误率很高。由于缺少简单易用的威胁检测模型，静态分析工具总是存在大量的误报结果，因此通过工具的结果再去判断是否真的存在漏洞是一项艰苦的工作。

动态分析
和静态分析不同，动态分析需要一个真实的或是模拟的运行环境。通过监控和分析程序运行状态，分析工具可以清晰地检测到程序的异常。动态分析其优点是结果高度精确，但是也存在很多缺陷。
首先，动态调试分析程序需要大量的人工交互操作，导致分析效率低下。另外，分析程序的研究人员需要具有较强的专业知识和技能。简而言之，动态分析只适合小范围的分析，并且对人员有较高要求。

符号执行
符号执行是一种被认为是非常有前途的漏洞挖掘技术。通过符号化程序输入，符号执行为每个执行路径维护一组约束条件。执行之后，将使用约束求解器来求解约束，并确定由哪些输入导致这条路径被执行。从理论上讲，符号执行可以覆盖程序中的任何执行路径，在小程序测试中表现出良好的效果，但也存在许多局限性。首先，路径爆炸问题。随着程序规模的扩大，执行状态也随之爆炸，超出了约束求解器的求解能力。第二，环境相互作用。在符号执行中，当目标程序与符号执行环境之外的组件（如系统调用、处理信号等）交互时，可能会出现问题。前人的工作已经证明，符号执行目前仍然很难应用到大型应用程序上。

模糊测试
Fuzz 是目前最流行的漏洞发现技术。模糊测试是20世纪90年代由美国威斯康星州大学的Barton Miller首次提出的，模糊测试产生大量的正常和异常输入，通过将生成的内容反馈给目标应用程序并监控执行状态来检测是否触发异常。与其他技术相比，fuzz 技术易于部署，具有良好的可扩展性和适用性，可以在有源代码或无源代码的情况下执行。此外，由于模糊测试基于程序的正常运行过程，因此具有较高的精度。fuzz 可以很容易地应用到大规模应用程序上。尽管模糊测试技术面临着效率低、代码覆盖率低等诸多缺点，但模糊技术已经成为目前最有效、最先进的漏洞发现技术之一。

表1显示了不同技术的优缺点。

模糊测试(Fuzzing)

模糊测试的执行过程
图 1 描述了传统模糊测试的主要过程。工作过程主要由四个阶段组成：测试用例生成阶段、测试用例运行阶段、程序执行状态监控和异常分析。

模糊测试从一堆程序输入的生成开始。生成测试用例的质量直接影响测试效果。输入应尽可能满足测试程序对输入格式的要求。另一方面，输入也不能过于遵守输入格式的要求，这些经过特殊处理的输入很可能会导致程序崩溃。根据目标程序的不同，输入可以是不同格式的文件、网络通信数据、具有指定特性的可执行二进制文件等。如何生成足够好的测试用例是模糊测试面临的主要挑战。一般来说，有两种常用的生成器：基于生成的生成器和基于变异的生成器。
测试用例在生成后被送到目标程序。fuzzers 自动启动和终止目标程序，并驱动目标程序的测试用例处理过程。在执行之前，分析人员可以配置目标程序的启动和终止方式，并预定义参数和环境变量。通常，模糊测试过程在超时、程序挂起或崩溃的时候停止。

Fuzzer 在目标程序执行期间监视执行状态，期望出现异常和崩溃。常用的异常监视方法包括监视特定的系统信号、崩溃和其他行为。对于没有直观表现的异常，可以使用第三方工具，包括 AddressSanitizer，DataflowSanitizer，ThreadSanitizer，LeakSanitizer 等。当异常被捕获时，fuzzer 会存储相应的测试用例以供回放和分析。

在分析阶段，分析人员试图确定捕获的异常的位置和原因。分析通常在调试程序的帮助下进行，如gdb、windbg或其他二进制分析工具，如ida pro、ollydbg等。二进制检测工具，如 Pin。自动崩溃分析是另一个重要的研究领域。

Fuzzer 的类型
Fuzzer 可以分为基于生成和基于突变两种。对于基于生成的 fuzzer，需要了解程序的构成(知识)。例如对于文件格式 fuzz，通常提供预先定义文件格式的配置文件。根据配置文件生成测试用例。这些测试用例由于有配置文件的约束，能够更容易地通过程序验证，更有可能测试目标程序的深层代码。然而，在没有可用的配置文件、说明文档情况下，分析待测程序的测试用例格式是一项艰巨的工作。因此，基于突变的 fuzzer 被更为广泛的采用。

对于基于突变的 fuzzer 来说，初始条件下需要一组有效的输入。测试用例是通过初始输入和 fuzz 过程中生成的测试用例的变异而生成的。我们在表2中比较了基于生成的 fuzzer 和基于变异的 fuzzer 。

根据对程序源代码的依赖性和程序分析的程度，fuzzer 可以分为白盒、灰盒和黑盒。基于白盒的 fuzzer 可以访问程序的源代码，因此可通过分析源代码以及测试用例如何影响程序的运行状态来收集更多的信息。黑盒 fuzzer 在不了解目标程序内部结构的情况下进行模糊测试。灰盒 fuzzer 也不需要源代码，通过程序分析获得目标程序的内部信息。我们在表3中列出了一些常见的白盒、灰盒和黑盒 fuzzer。

根据开发的策略，还可以将 fuzzer 分为定向 fuzzer 和基于覆盖的 fuzzer。定向 fuzzer 的目标是生成覆盖程序目标代码和目标路径的测试用例，而基于覆盖的 fuzzer 的目标是生成覆盖尽可能多的程序代码的测试用例。定向 fuzzer 目的是对程序进行更快的测试，而基于覆盖的 fuzzer 目的是进行更彻底的测试，并尽可能地检测出更多的错误。无论是定向 fuzzer 还是基于覆盖的fuzzer，如何提取执行路径信息是关键问题。

根据对程序执行状态的监控与测试用例生成之间是否存在反馈，fuzzer 可以分为硬核 fuzzer 和智能 fuzzer。智能 fuzzer 根据收集到的测试用例如何影响程序行为的信息来调整测试用例的生成。对于基于变异的 fuzzer，反馈信息可以用来确定测试用例的哪一部分应该被变异以及变异它们的方式。硬核 fuzzer 具有更好的测试速度，而智能 fuzzer 可以生成更好的测试用例并获得更好的效率。

Fuzz 中的关键问题
传统的 fuzz 算法在实际应用中通常采用基于随机的 fuzz 策略。由于程序分析技术的局限，导致 fuzzer 不够智能。因此模糊测试仍然面临许多挑战。我们列出一些关键问题如下。

如何变异种子输入？基于变异的生成策略以其方便、易设置等优点被现代 fuzzer 广泛应用。然而，如何变异和生成能够覆盖更多程序路径和更容易触发错误的测试用例是一个关键问题。具体来说，基于变异的 fuzzer 在进行变异时需要回答两个问题：
（1）在哪里变异？
（2）如何变异？
只有几个关键位置上的变化才会影响程序的控制流。因此，如何在测试用例中定位这些关键位置是非常重要的。此外，fuzzer 在关键位置上如何变异是另一个关键问题，即如何确定可以引导程序到达脆弱路径的值。总之，测试用例的盲目变异导致测试资源的严重浪费，更好的变异策略可以显著提高 fuzz 的效率。

低代码覆盖率的问题？代码覆盖率越高表示程序执行状态的覆盖率越高，测试也越彻底。以前的工作已经证明，更高的覆盖率会得到更高的找到错误的概率。然而，大多数测试用例只覆盖少数路径，而多数代码无法访问。因此，仅仅通过大量的测试用例生成和投入测试资源来实现高覆盖率并不是一个明智的选择。基于覆盖的 fuzzer 试图借助程序分析技术（如程序插装）来解决这个问题。我们将在下一节介绍细节。

通过验证的问题？程序通常在解析和处理数据之前验证。验证起到保护程序的作用，节省了计算资源，保护程序免受无效输入和恶意构造的输入造成损坏。无效的测试用例总是被忽略或丢弃。
幻数、特定的字符串、版本号检查和校验和是程序中常用的验证方法。由黑盒和灰盒 fuzzer 生成的测试用例很难通过这些验证，导致 fuzz 效率很低。因此，如何通过验证是另一个关键挑战。

为了应对这些问题，人们提出了各种方法，既有传统的技术，如程序检测和污染分析，也有新的技术，如 RNN 和LSTM。这些技术的原理将在“技术融合”一节中讨论。

基于覆盖率的模糊测试

基于覆盖的 fuzz 策略被现代 fuzzer 广泛应用，并被证明是非常有效的。为了实现一个深入而彻底的 fuzz 过程，fuzzer 应该尝试遍历尽可能多的程序运行状态。然而，由于程序行为的不确定性，程序状态不存在简单的度量标准。此外，一个好的度量标准应该在进程运行期间容易被确定。因此，代码覆盖率成为近似的度量方案。使用这种方案，代码覆盖率的增加表示程序进入新的状态。此外，通过编译内部和外部工具，代码覆盖率可以很容易地测量。我们认为代码覆盖是一种近似的度量标准，因为在实践中，一个固定的代码覆盖率并不表示一个连续的程序状态。使用此度量标准可能会导致某些信息丢失。在这一部分中，我们以 afl 为例说明。

代码覆盖率测量
在程序分析中，程序由基本块组成。基本块是具有单个入口和出口点的代码段，基本块中的指令将被顺序执行，并且只执行一次。在代码覆盖率测量中，最新的方法是以基本块作为最佳粒度。其原因包括：
（1）基本块是程序执行的最小相干单元；
（2）测量函数或指令会导致信息丢失或冗余；
（3）基本块可以通过第一条指令的地址来识别，并且基本块信息可以通过代码检测来轻松提取。
目前，有两种基于基本块的测量方法，统计被执行的基本块数量、统计基本块之间转换的次数。在后一种方法中，程序被解释为一个图，节点被用来表示基本块，边被用来表示基本块之间的转换。实验表明，简单地计算已执行的基本块将导致严重的信息丢失。如图2所示，如果首先执行程序路径（bb1、bb2、bb3、bb4），然后执行路径（bb1、bb2、bb4），则丢失新边（bb2、bb4）信息。

AFL 第一次将边(edge)测量方法引入到基于覆盖的 fuzz 中。以 afl 为例说明基于覆盖的 fuzzer 在模糊测试过程中如何获取代码覆盖率信息。
afl通过轻量级程序插桩获得代码覆盖率信息。根据是否提供源代码，afl提供了两种插装模式：编译插装和外部插装。根据我们使用的编译器，在编译插桩模式下编译时，afl同时提供gcc和llvm支持，这将在生成二进制文件时插入检测代码片段。
在外部模式下，afl提供qemu模式，当基本块转换为tcg块时将检测代码片段。

片段 1 显示了插入指令的代码片段的伪代码。在指令插入技术中，一个随机 ID，即变量 cur_location 被插入到基本块中。变量 shared_mem 数组是一个64 KB的共享内存区域，其中每个字节都映射到一个特定边的命中（bb_src，bb_dst）例如(BB2, BB4)。当基本块转换发生时，将计算哈希值，并更新数组中相应的字节值。图3描述了散列和位图的映射。


基于覆盖率的 fuzz 流程

算法1给出了基于覆盖的 fuzzer 的一般工作过程。测试从初始给定的种子输入开始。如果种子输入集没有给定，那么fuzzer自己构造一个。在主循环中，fuzzer 反复选择一个种子用于后续的变异和测试用例生成。然后驱动目标程序在fuzzer的监控下执行生成的测试用例。收集触发崩溃的测试用例，并将其他有趣的用例添加到种子池中。对于基于覆盖的 fuzzer，能够触发新控制流的测试用例被认为是有趣的。主循环在预先配置的超时或中止信号时停止。

在 fuzz 过程中，fuzzer 通过各种方法跟踪执行。基本上，fuzzer 跟踪执行有两个目的，代码覆盖率和异常捕获。代码覆盖率信息用于进行彻底的程序状态探索，而异常跟踪是为了更好地发现错误。如前一小节所述，afl通过代码插桩和afl位图跟踪代码覆盖率。
图4显示了AFL的工作过程，AFL是一种非常有代表性的基于覆盖率的 fuzzer 。目标应用程序执行前被插桩。如前所述，afl支持编译时插桩和外部插桩，使用gcc/llvm模式和qemu模式。还应提供初始种子输入。在主循环中，
（1）fuzzer 根据种子选择策略从种子池中选择最合适的种子，afl选择最快和最小的种子。
（2）根据变异策略对种子文件进行变异，生成一批测试用例。AFL目前采用了一些随机修改和测试用例拼接的方法，包括可变长度和步长的顺序位翻转、小整数的顺序加减和已知有趣整数的顺序插入，如0，1，int_max，etc.
（3）测试用例放入程序，fuzzer 跟踪执行过程。收集覆盖率信息以确定有趣的测试用例，即到达新控制流的测试用例。有趣的测试用例被添加到种子池中，以供下一轮运行。

关键问题
前面的介绍表明，要运行一个高效的基于覆盖率的 fuzzer 需要解决很多问题。围绕这些问题进行了许多探索。我们在本小节中总结并列举一些最新的工作成果，如表4所示。

问题A：如何获得初始输入？
大多数最先进的基于覆盖率的 fuzzer 采用基于变异的测试用例生成策略，这在很大程度上取决于初始种子输入的质量。良好的初始种子输入可以显著提高 fuzz 的效率和有效性。具体来说，
（1）提供格式良好的种子输入可以节省构建一个种子所需的大量CPU时间
（2）良好的初始输入可以满足复杂文件格式的要求
（3）基于格式良好的种子输入的变异更有可能生成更深入的测试用例。从而到达难以到达的路径
（4）良好的种子输入可以在多次测试中重复使用

收集种子输入的常用方法包括使用标准数据、从因特网上抓取、使用现有的POC样本。开放源代码的应用程序在发布同时会附带一个用于测试程序功能的基准数据。这些数据是根据应用程序的特性和功能构建的，这些特性和功能自然地构建了一组良好的种子输入。考虑到目标应用输入的多样性，从网络抓取是最直观的方法。我们可以轻松下载具有特定格式的文件。此外，对于一些常用的文件格式，网络上有许多开放的测试项目提供免费的测试数据集。使用现有的POC样本也是一个好主意。然而，种子输入量过大会造成第一次运行的时间浪费，由此带来另一个问题，即如何提取原始语料。afl提供了一个工具，它用于提取实现相同代码覆盖率的最小输入集。

问题B：如何生成测试用例？
测试用例的质量是影响 fuzz 效率和有效性的重要因素。首先，好的测试用例可以探索到更多的程序执行状态，并在更短的时间内覆盖更多的代码。此外，好的测试用例可以瞄准潜在的易受攻击的位置，从而更快地发现程序错误。因此，如何基于种子输入生成良好的测试用例是一个重要的问题。

Rawat 等人（2017）提出了 Vuzzer，一种结合静态和动态分析的应用感知灰盒 fuzzer。种子输入的变异涉及到两个关键问题：在哪里变异以及变异成什么。具体来说，Vuzzer 在进入主循环之前通过静态分析提取即时值、幻数值和其他影响控制流的特征字符串。在程序执行过程中，Vuzzer 使用动态污点分析技术来收集影响控制流分支的信息，包括特定值和相应的偏移量。Vuzzer 通过对收集到的值进行变异，并在识别的位置进行变异，可以生成更符合分支判断条件的测试用例，并通过程序验证。但是，Vuzzer 仍然无法在程序中通过其他类型的验证，例如基于哈希的校验和。Vuzzer 的插桩模块、主循环等模块是基于 Pin 实现的，与AFL相比速度更慢。

Wang等人（2017）提出的 Skyfire 是一种数据驱动的种子生成解决方案。Skyfire从爬取的输入中学习概率上下文敏感语法（PCSG），并在生成输入时利用所学知识。实验表明，Skyfire生成的测试用例覆盖的代码比AFL多，发现的错误也多。同时也证明了测试用例的质量是影响 fuzz 效率和有效性的重要因素。

随着机器学习技术的发展和广泛应用，一些研究者试图利用机器学习技术来辅助测试用例的生成。Godefraoid 等人使用基于神经网络的统计机器学习技术-NIQUES自动生成测试用例。具体来说，他们首先通过机器学习技术从一堆有效的输入中学习输入格式，然后将学习到的知识杠杆化(?)，指导测试用例的生成。它们在微软 edge 浏览器中的 pdf 解析器上进行了 fuzz。尽管实验没有取得令人鼓舞的结果，但仍然是一个良好的思路。Rajpal 等人（2017）使用神经网络从过去的 fuzz 用例中学习，并预测输入文件中要变异的字节。Nichols 等人（2017）使用生成对抗性网络（gan）模型帮助使用新种子文件重新初始化系统。实验表明，gan比 lstm 更快、更有效，有助于发现更多的代码路径。

问题C：如何从种子池(seed pool)中选择种子？
在主循环中，新一轮测试开始时，fuzzer 从种子池中重复选择种子进行变异。如何从池中选择种子是 fuzz 中另一个重要的开放性问题。前人的工作已经证明，良好的种子选择策略可以显著提高 fuzz 效率，并有助于更快地发现更多的错误。有了良好的种子选择策略，fuzzer可以
（1）优先处理那些更有帮助的种子，包括覆盖更多的代码，更容易触发漏洞
（2）减少重复执行路径，节省计算资源
（3）优化选择种子，覆盖更深更易受攻击的代码，帮助更快地识别隐藏的漏洞。

Böhme 等人（2017）提出了基于覆盖率的灰盒 fuzzer AFLFAST。他们发现大多数测试用例都集中在相同的几个路径上。例如，在 PNG 处理程序中，通过随机变异生成的大多数测试用例都是无效的，并触发错误处理路径。aflfast 将路径分为高频率路径和低频率路径。在 fuzz 中，aflfast测量可执行路径的频率，对种子进行优先级排序，并将更多的计算资源分配给运行低频率路径的种子。

Rawat 等人（2017）整合静态和动态分析，以确定难以深入的路径，并优先考虑深入路径的种子。Vuzzer 的种子选择策略可以帮助找到隐藏在深层路径中的漏洞。

Aflgo 采用定向选择策略。它将一些易受攻击的代码定义为目标位置，并选择更接近目标位置的测试用例。aflgo文件中提到了四类易受攻击的代码，包括补丁、程序崩溃缺少足够的跟踪信息、静态分析工具验证的结果以及与敏感信息相关的代码片段。通过适当的定向算法，aflgo可以在感兴趣的代码上分配更多的测试资源。QTEP 利用静态代码分析来检测容易出错的源代码，并优先处理能够覆盖更多错误代码的种子。aflgo和qtep在很大程度上依赖于静态分析工具的有效性。然而，目前的静态分析工具的误报率仍然很高，无法给出准确的验证。

已知漏洞的特征也可用于种子选择策略。Slowfuzz（Petsios等人2017）的主要 fuzz 目标是复杂算法的漏洞，这些算法往往会消耗大量计算资源。因此，slowfuzz 更偏向于选择消耗更多资源（如cpu时间和内存）的种子。然而，收集消耗资源的信息会带来很大的开销，降低 fuzz 的效率。例如，为了收集cpu时间，slowfuzz 统计执行的指令数。此外，slowfuzz 对资源消耗信息的准确性要求很高。

问题D：如何有效地测试应用程序？
在主循环中，目标应用由 fuzzer 反复启动和终止。众所周知，对于用户端应用程序的 fuzz，进程的创建和终止将消耗大量的CPU时间。频繁的创建和终止进程会严重降低 fuzz 的效率。因此，人们提出了很多优化措施。afl 使用一个 forkserver 方法，该方法为已加载的程序创建一个相同的克隆体，并在每次运行时重用该克隆体。此外，afl 还提供了持久模式（persistent mode）和并行模式（parallel mode），前者有助于避免缓慢的 execve() 等系统调用和链接过程的开销，后者有助于在多核系统上并行测试。英特尔处理器跟踪（PT）（james 2013）技术用于内核 fuzz，以节省覆盖率跟踪带来的开销。Xu等人（2017）旨在解决多核机上并行 fuzz 的性能瓶颈。通过设计和实现三个新的操作原语，他们表示自己的工作可以显著加快现代 fuzzer 的速度，如 afl 和 libfuzzer。

技术融合

现代应用程序通常使用非常复杂的数据结构，对复杂数据结构的解析更容易带来漏洞。采用随机变异方法的 fuzz 策略将生成大量无效的测试用例，fuzz 效率低。目前最先进的 fuzzer 通常采用智能 fuzz 策略。智能 fuzzer 通过程序分析技术收集程序控制流和数据流信息，从而利用收集到的信息改进测试用例的生成。由智能 fuzzer 生成的测试用例更有针对性，更有可能满足程序对数据结构和逻辑判断的要求。图5描绘了智能 fuzzer 的草图。为了构建一个智能 fuzzer ，集成了多种技术。如前几节所述，fuzz 在实践中面临许多挑战。在这一部分中，我们试图总结以前的工作所使用的技术，以及这些技术如何在 fuzz 过程中应对挑战。

生成测试用例
如前所述，fuzzing 中的测试用例是用基于生成的方法或基于变异的方法生成的。如何生成满足复杂数据结构要求且更容易触发难以到达路径的测试用例是一个关键的挑战。研究者们提出了很多解决方案。
在基于生成的 fuzz 中，生成器根据输入数据格式和配置文件生成测试用例。例如文件处理程序，文档中仅仅提到了常用的文件格式，但是没有提到一些小众文件格式。如何获取输入的格式信息是一个很难解决的问题。一般采用机器学习技术和格式化方法来解决问题。Godefroid 等人使用机器学习技术，特别是递归神经网络，学习输入文件的语法，从而使用学习的语法生成格式合适的测试用例。Wang 等人使用格式方法，具体来说，它定义了一个概率上下文敏感语法，并提取格式知识来生成格式良好的种子输入。

更多最先进的 fuzzer 采用基于变异的 fuzz 策略。在变异过程中，通过修改部分种子输入来生成测试用例。在变异 fuzz 过程中，变异模块随机地将种子的字节数修改为随机值或多个特殊值，这实际上是非常低效的。因此，如何确定要修改的位置和修改时使用的值是另一个关键问题。
在基于覆盖的 fuzz 中，应该首先修改可能影响控制流传输的字节。污点分析技术用于跟踪字节对控制流的影响，以定位变异种子的关键字节（Rawat等2017年）。知道变异的关键位置只是开始。fuzz 过程通常在一些分支中被阻塞。例如，条件判断中的特定字节和其他值进行比较。采用逆向工程和污点分析等技术。通过扫描二进制代码，从条件判断语句中收集即时值，并在变异过程中利用选择的值作为候选值，fuzzer 可以绕过一些关键的验证和检查，如版本检查。
Rawat 等人（2017）尝试利用机器学习等技术解决挑战。微软的研究人员利用机器学习技术，比如深度神经网络（dnn），通过lstm，基于先前的 fuzz 经验，预测哪些字节会发生变异，在变异中使用什么值。

程序执行
在主循环中，目标程序被重复执行。提取程序执行状态信息，用于提高程序执行效率。在执行阶段涉及到的两个关键问题是如何指导 fuzz 过程以及如何探索新的路径。
我们希望 Fuzz 能够覆盖更多的代码并更快地发现错误，因此需要路径执行信息。在基于覆盖率的 fuzz 中，可以使用多种检测技术记录被执行的路径并计算覆盖率信息。根据是否提供源代码（如果提供），可使用符合要求的编译插桩和外部插桩。对于定向 fuzz，使用模式识别等静态分析技术来识别和指定目标代码，这样更容易发现脆弱点。
静态分析技术也可用于收集控制流信息，例如路径深度，这可作为指导测试用例生成的另一个参考。通过检测收集的路径执行信息可以帮助指导 fuzz 过程。一些新的系统特性和硬件特性也被用于执行信息的收集。英特尔处理器跟踪（Intel PT）是英特尔处理器提供的一项新功能，它具有执行速度快、不依赖源代码等优点，可以准确高效地跟踪执行过程。在 kafl 中，这一特性被用于os内核的 fuzz，并被证明是相当有效的。

测试执行中的另一个关注点是探索新的路径。在程序的控制流中，fuzzer 需要通过复杂的条件判断。程序分析技术包括静态分析、污点分析等，可以用来识别执行过程中的阻塞点，从而解决问题。符号执行技术在路径探索中具有天然的优势。通过求解约束集，符号执行技术可以得到满足特定条件要求的值。Taintscope（Wang等人2010）使用符号执行技术来获取程序中验证逻辑的结果。Driller（Stephens等人2016）利用混合执行绕过传统判断并发现更深层次的漏洞。
经过多年的发展，fuzz 技术的粒度更细、更加灵活和智能。反馈驱动的 fuzz 技术为指导测试用例生成提供了一种有效的方法。

对不同应用进行模糊测试

自出现以来，fuzz 技术就被用来检测大量应用程序的漏洞。根据不同应用的特点，在实际应用中采用不同的 fuzzer 和策略。

文件格式 fuzz
大多数应用程序都涉及文件处理，fuzz 技术在查找这些应用程序的错误时被广泛使用。模糊测试可以用标准格式或不标准格式的文件来操作。最常用的文档文件、图像和媒体文件是标准格式的文件。目前对 fuzz 的研究主要集中在文件格式的模糊化上，研究者们提出了很多 fuzz 工具，如 Peach（peachtech 2017）、最新的 afl 及其扩展（rawat等）。前面的介绍涉及到各种文件格式的fuzzer ，这里我们不再强调其他工具。

文件格式 fuzz 的一个重要分支是web浏览器上的 fuzz。随着 web 浏览器的发展，其功能得到了前所未有的扩展。浏览器处理的文件类型已经从传统的HTML、CSS、JS 扩展到其他类型的文件，如 PDF、SVG 等。具体来说，浏览器将 web 页面解析为dom树，dom 树将 web 页面解析为与事件和响应相关的文档对象树。浏览器的 dom 解析和页面呈现是当前比较热门的 fuzz 目标。针对 web 浏览器比较出名的 fuzz 工具包括 grinder 框架（stephenless 2016）、comraider（zimmer 2013）、bf3（aldeid 2013）等等。

内核 fuzz
操作系统内核的 fuzz 一直是一个难题，涉及到许多挑战。首先，与用户态 fuzzing 不同，内核中的崩溃和挂起会导致整个系统崩溃，如何捕获崩溃是一个问题。其次，系统权限机制导致了一个相对封闭的执行环境，考虑到 fuzzer 通常在 ring 3 级别中运行，如何与内核交互是另一个问题。目前与内核通信的最佳提议是调用内核API函数。此外，广泛使用的内核如 Windows 和 MacOS 都是闭源的，并且 fuzz 效率很低。但是随着智能 fuzz 技术的发展，内核 fuzz 技术也取得了一些新的进展。

通常， fuzz 内核的方法是随机调用具有随机生成的参数值的内核 API 函数。根据 fuzzer 的关注点，内核 fuzzer 可以分为两类：基于已知的 fuzzer 和基于覆盖率的 fuzzer 。

对于基于已知的 fuzzer ，使用内核 api 函数调用进行 fuzz 面临两个主要挑战：
（1）api调用的参数应具有遵循api规范的随机且格式良好的值
（2）内核api调用的顺序应看起来有效（han和cha 2017）
代表性工作包括Trinity（Jones 2010）和IMF（Han和Cha 2017）。trinity是一个类型感知的内核 fuzzer。在 trinity 中，根据参数类型生成测试用例。系统调用的参数根据数据类型进行修改。此外，还提供了某些枚举值和值的范围，以帮助生成格式良好的测试用例。imf 试图学习 api 执行的正确顺序和 api 调用之间的值依赖性，并将学习到的知识用于生成测试用例。

基于覆盖率的 fuzz 技术在发现用户应用程序漏洞方面取得了巨大的成功。人们开始将基于覆盖率的 fuzz 方法应用于内核漏洞的发现。代表性工作包括 Syzkaller（Vyukov 2015）、Triforceafl（Hertz 2015）和 Kafl（Schumilo等人2017年）。Syzkaller 通过编译为内核安装工具，并在一组 QEMU 虚拟机上运行内核。在 fuzz 过程中，覆盖范围和异常都会被跟踪。
Triforceafl 是 afl 的一个改进版本，它支持 qemu 全系统仿真的内核 fuzz。
kafl 利用新的硬件特性 intel pt 来跟踪覆盖范围，只跟踪内核代码。实验表明，kafl 的速度是 triforce 的 40 倍左右，大大提高了效率。

协议 Fuzz
目前，很多本地应用都是以 b/s 模式向网络服务转化的。服务部署在网络上，客户端应用程序通过网络协议与服务器通信。
网络协议的安全测试成为另一个重要的关注点。如果协议中的安全问题，可能导致比本地应用程序更严重的后果，如拒绝服务、信息泄漏等。与文件格式 fuzz 相比，协议 fuzz 涉及不同的问题。首先，服务可以定义自己的通信协议，很难确定协议的标准。此外，即使是标准定义的文档化协议，在开发过程中仍然很难遵循 RFC 等规范。

典型的协议 fuzzer 包括 Spike，它提供了一套工具，允许用户快速创建网络协议压力测试器。serge gorbunov 和 arnold rosenbloom 提出了autofuzz（gorbunov和rosenbloom，2010），它通过构造一个有限状态自动机来学习协议实现，并利用所学知识生成测试用例。Greg Banks 等人提出 SNOOZE（Banks等人2006），它用有状态 fuzz 方法来识别协议缺陷。joeri de ruiter（de ruiter and poll 2015）提出了一种协议状态 fuzz 方法，该方法描述了状态机中 TLS 的工作状态，并根据逻辑流对其进行 fuzz 处理。之前的工作一般采用有状态的方法对协议工作过程进行建模，并根据协议规范生成测试用例。

fuzz 技术的新趋势

Fuzz 技术作为一种自动检测漏洞的方法，显示了其高效性和有效性。然而，正如前面提到的，仍然有许多挑战需要解决。在这一部分中，我们简要介绍了自己的理解，以供参考。

首先，智能 fuzzer 为改进模糊测试技术提供了更多的可能性。在以前的工作中，传统的静态分析和动态分析技术被集成到 fuzz 中。虽然取得了一定的进步，但还是有限。智能 fuzzer 通过多种方式收集目标程序的执行信息，对 fuzz 过程进行更精细的调整。随着对不同类型漏洞的深入理解，以及对 fuzz 中漏洞特征的利用，智能 fuzzer 有助于发现更复杂的漏洞。

第二，新技术可在许多方面帮助 fuzzer 更好的检测漏洞。如机器学习和相关的技术已经被用来改进 fuzz 中的测试用例的生成。如何将新技术的优势和特点与 fuzz 结合起来，是另一个值得思考的问题。

第三，不应忽视新的系统特性和硬件特性。Vyukov 和 Schumilo 的工作表明，新的硬件特性大大提高了 fuzz 的效率，给了我们很好的启发。

结论

模糊测试技术是目前最有效的漏洞发现方法之一。本文对 fuzz 及其最新进展进行了全面的回顾和总结。首先，我们将模糊测试技术与其他漏洞发现方法进行了比较，然后介绍了模糊测试技术的概念和关键挑战。本文着重介绍了近年来发展迅速的基于覆盖率的 fuzz 技术。最后，总结了 fuzz 技术融合、fuzz 技术的应用及可能出现的新趋势。

Abbreviations
AFL: American Fuzzy Lop; BB: Basic Block; DNN: Deep Neural Networks; LSTM: Long Short-Term Memory; POC: Proof of Concept
Acknowledgements
This research was supported in part by the National Natural Science Foundation of China (Grant No. 61772308 61472209, and U1736209), and Young Elite Scientists Spon- sorship Program by CAST (Grant No. 2016QNRC001), and award from Tsinghua Information Science And Technology National Laboratory.
Authors’ contributions
JL drafted most of the manuscripts, BZ helped proofreading and summarized parts of the literature, and Prof. CZ abstracted the classifier for existing solutions and designed the overall structure of the paper. All authors read and approved the final manuscript.
Competing interests
CZ is currently serving on the editorial board for Journal of Cybersecurity.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References
Aldeid (2013) Browser fuzzer 3. https://www.aldeid.com/wiki/Bf3. Accessed 25 Dec 2017
Amini P (2017) Sulley fuzzing framework. https://github.com/OpenRCE/sulley. Accessed 25 Dec 2017
Banks G, Cova M, Felmetsger V, Almeroth K, Kemmerer R, Vigna G (2006) Snooze: toward a stateful network protocol fuzzer. In: International Conference on Information Security. Springer, Berlin. pp 343–358
Böhme M, Pham V-T, Nguyen M-D, Roychoudhury A (2017) Directed greybox fuzzing. In: Proceeding CCS ’17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, New York. pp 2329–2344. https://doi.org/10.1145/3133956.3134020
Böhme M, Pham VT, Roychoudhury A (2017) Coverage-based greybox fuzzing as markov chain. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM. pp 1032–1043
Bowne S (2015) Fuzzing with spike. https://samsclass.info/127/proj/p18-spike. htm. Accessed 25 Dec 2017
Cha SK, Avgerinos T, Rebert A, Brumley D (2012) Unleashing mayhem on binary code. In: Security and Privacy (SP) 2012 IEEE Symposium on. IEEE, San Francisco. pp 380–394. https://doi.org/10.1109/SP.2012.31
De Ruiter J, Poll E (2015) Protocol state fuzzing of tls implementations. In: Proceeding SEC’15 Proceedings of the 24th USENIX Conference on Security Symposium. USENIX Association, Berkeley. pp 193–206
Godefroid P, Levin MY, Molnar D (2012) Sage: whitebox fuzzing for security testing. Queue 10(1):20
Godefroid P, Peleg H, Singh R (2017) Learn & fuzz: Machine learning for input fuzzing. In: Proceeding ASE 2017 Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. IEEE Press, Piscataway. pp 50–59
Gorbunov S, Rosenbloom A (2010) Autofuzz: Automated network protocol fuzzing framework. IJCSNS 10(8):239
Han H, Cha SK (2017) Imf: Inferred model-based fuzzer. In: Proceeding CCS ’17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, New York. pp 2345–2358. https://doi.org/10.1145/3133956.3134103
Hertz J (2015) Triforceafl . https://github.com/nccgroup/TriforceAFL. Accessed 25 Dec 2017
James R (2013) Processor tracing. https://software.intel.com/en-us/blogs/2013/09/18/processor-tracing. Accessed 25 Dec 2017
Jones D (2010) trinity. https://github.com/kernelslacker/trinity. Accessed 25 Dec 2017
King JC (1976) Symbolic execution and program testing. Commun ACM 19(7):385–394
lcamtuf (2014) Fuzzing random programs without execve(). https://lcamtuf. blogspot.jp/2014/10/fuzzing-binaries-without-execve.html. Accessed 25 Dec 2017
libfuzzer (2017) A library for coverage-guided fuzz testing. https://llvm.org/docs/LibFuzzer.html. Accessed 25 Dec 2017
Liu B, Shi L, Cai Z, Li M (2012) Software vulnerability discovery techniques: A survey. In: Multimedia Information Networking and Security (MINES), 2012 Fourth International Conference on. IEEE, Nanjing. pp 152–156. https://doi. org/10.1109/MINES.2012.202
Luk C-K, Cohn R, Muth R, Patil H, Klauser A, Lowney G, Wallace S, Reddi VJ, Hazelwood K (2005) Pin: building customized program analysis tools with dynamic instrumentation. In: Acm sigplan notices, volume 40. ACM, Chicago. pp 190–200
Nichols N, Raugas M, Jasper R, Hilliard N (2017) Faster fuzzing: Reinitialization with deep neural models. arXiv preprint arXiv:1711.02807
PeachTech (2017) Peach. https://www.peach.tech/. Accessed 25 Dec 2017 Petsios T, Zhao J, Keromytis AD, Jana S (2017) Slowfuzz: Automated
domain-independent detection of algorithmic complexity vulnerabilities. In: Proceeding CCS ’17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, New York.
pp 2155–2168. https://doi.org/10.1145/3133956.3134073
Rajpal M, Blum W, Singh R (2017) Not all bytes are equal: Neural byte sieve for fuzzing. arXiv preprint arXiv:1711.04596
Rawat S, Jain V, Kumar A, Cojocar L, Giuffrida C, Bos H (2017) Vuzzer: Application-aware evolutionary fuzzing. In: Proceedings of the Network and Distributed System Security Symposium (NDSS). https://www.vusec. net/download/?t=papers/vuzzer_ndss17.pdf Schumilo S, Aschermann C, Gawlik R, Schinzel S, Holz T (2017) kAFL: Hardware-assisted feedback fuzzing for OS kernels. In: Kirda E, Ristenpart T (eds). 26th USENIX Security Symposium, USENIX Security 2017. USENIX Association, Vancouver. pp 167–182
Serebryany K, Bruening D, Potapenko A, Vyukov D (2012) Addresssanitizer: A fast address sanity checker. In: Proceeding USENIX ATC’12 Proceedings of the 2012 USENIX conference on Annual Technical Conference. USENIX Association, Berkeley. pp 309–318
Serebryany K, Iskhodzhanov T (2009) Threadsanitizer: data race detection in practice. In: Proceedings of the Workshop on Binary Instrumentation and Applications. pp 62–71
Shirey RW (2000) Internet security glossary. https://tools.ietf.org/html/rfc2828. Accessed 25 Dec 2017
Stephenfewer (2016) Grinder. https://github.com/stephenfewer/grinder. Accessed 25 Dec 2017
Stephens N, Grosen J, Salls C, Dutcher A, Wang R, Corbetta J, Shoshitaishvili Y, Kruegel C, Vigna G (2016) Driller: Augmenting fuzzing through selective symbolic execution. In: NDSS, volume 16, San Diego. pp 1–16
Sutton M, Greene A, Amini P (2007) Fuzzing: brute force vulnerability discovery. Pearson Education, Upper Saddle River
Takanen A, Demott JD, Miller C (2008) Fuzzing for software security testing and quality assurance. Artech House
The Clang Team (2017) Dataflowsanitizer. https://clang.llvm.org/docs/DataFlowSanitizerDesign.html. Accessed 25 Dec 2017
The Clang Team (2017) Leaksanitizer. https://clang.llvm.org/docs/LeakSanitizer.html. Accessed 25 Dec 2017
Van Sprundel I (2005) Fuzzing: Breaking software in an automated fashion. Decmember 8th
Vyukov D (2015) Syzkaller. https://github.com/google/syzkaller. Accessed 25 Dec 2017
Wang J, Chen B, Wei L, Liu Y (2017) Skyfire: Data-driven seed generation for fuzzing. In: Security and Privacy (SP), 2017 IEEE Symposium on. IEEE, San Jose. https://doi.org/10.1109/SP.2017.23
Wang S, Nam J, Tan L (2017) Qtep: quality-aware test case prioritization. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering. ACM, New York. pp 523–534. https://doi.org/10.1145/3106237.3106258
Wang T, Wei T, Gu G, Zou W (2010) Taintscope: A checksum-aware directed fuzzing tool for automatic software vulnerability detection. In: Security and privacy (SP) 2010 IEEE symposium on. IEEE, Berkeley. pp 497–512. https:// doi.org/10.1109/SP.2010.37
Wichmann BA, Canning AA, Clutterbuck DL, Winsborrow LA, Ward NJ, Marsh DWR (1995) Industrial perspective on static analysis. Softw Eng J 10(2):69–75
Wikipedia, Wannacry ransomware attack (2017). https://en.wikipedia.org/wiki/WannaCry_ransomware_attack. Accessed 25 Dec 2017
Wikipedia (2017) Dynamic program analysis. https://en.wikipedia.org/wiki/Dynamic_program_analysis. Accessed 25 Dec 2017
Wu Z-Y, Wang H-C, Sun L-C, Pan Z-L, Liu J-J (2010) Survey of fuzzing. Appl Res Comput 27(3):829–832
Xu W, Kashyap S, Min C, Kim T (2017) Designing new operating primitives to improve fuzzing performance. In: Proceeding CCS ’17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, New York. pp 2313–2328. https://doi.org/10.1145/3133956. 3134046
Yang Q, Li JJ, Weiss DM (2007) A survey of coverage-based testing tools. The Computer Journal 52(5):589–597
Zalewski, M (2017) American fuzzy lop. http://lcamtuf.coredump.cx/afl/. Accessed 25 Dec 2017
Zalewski M (2017) Afl technical details. http://lcamtuf.coredump.cx/afl/technical_details.txt. Accessed 25 Dec 2017
Zimmer D (2013) Comraider. http://sandsprite.com/tools.php?id=16. Accessed 25 Dec 2017
translate：CataLpa