Fuzzing 是什么

在当今众多的软件测试技术中，Fuzzing 由于其概念上的简单性、部署的低门槛，以及在发现软件漏洞中的实际效果而一直备受青睐。从直观上说，Fuzzing 就是使用“fuzz 输入”来运行待测试程序（Program Under Test, PUT）的过程。Fuzz 输入是指 PUT 可能没预期到的输入，换句话说，是 PUT 可能处理不当并触发开发者未意图的行为的输入。

定义 1 (Fuzzing). Fuzzing 是使用从输入空间（“fuzz 输入空间”）中采样的输入来执行 PUT 的过程，该输入空间超出了 PUT 的预期输入范围。

定义 2 (Fuzz Testing). Fuzz 测试是使用 fuzzing 来检查 PUT 是否违反了某一正确性策略。

定义 3 (Fuzzer). Fuzzer 是对 PUT 进行 fuzz 测试的程序。

定义 4 (Fuzz Campaign). Fuzz campaign 是在特定正确性策略的 PUT 上执行 fuzzer 的特定过程。

定义 5 (Bug Oracle). Bug oracle 是一个程序，也许作为 fuzzer 的一部分，用于确定 PUT 的特定执行是否违反了某个特定的正确性策略。

通用 Fuzz 测试算法

需要注意的是，fuzz 配置中的值类型取决于 fuzz 算法的类型。例如，向 PUT 发送随机字节流的 fuzz 算法的配置空间相对简单。而另一方面，复杂的 fuzzers 包含接受一组配置并随时间演进的算法，这包括添加和删除配置。

种子是传递给 PUT 的一个（通常结构良好的）输入，用于通过修改它来生成测试用例。Fuzzers 通常维护一个称为种子池的种子集合，并且某些 fuzzers 会随着 fuzz campaign 的进行而演进这个池。

算法 1 接受一组 fuzz 配置�和一个超时������作为输入，并输出一组发现的 bug �。第一部分是PREPROCESS函数，该函数在 fuzz campaign 开始时执行。第二部分是循环中的五个函数系列：SCHEDULE、INPUTGEN、INPUTEVAL、CONFUPDATE和CONTINUE。

循环的每次执行都被称为 fuzz iteration，每次 INPUTEVAL 在一个测试用例上执行 PUT 被称为 fuzz run。

• PREPROCESS(�)→�

  用户为 PREPROCESS 提供一组 fuzz 配置作为输入，它返回可能修改的 fuzz 配置集合。根据 fuzz 算法，PREPROCESS 可能执行各种操作，如向 PUT 插入检测代码或测量种子文件的执行速度。

• SCHEDULE�,��������,������→conf

  SCHEDULE 接受当前的 fuzz 配置集、当前时间 �������� 和一个超时 ������ 作为输入，并选择一个 fuzz 配置用于当前的 fuzz iteration。

•  INPUTGEN (conf)→ tcs

  INPUTGEN接收一个 fuzz 配置作为输入，并返回一组具体的测试用例���作为输出。在生成测试用例时，INPUTGEN使用����中的特定参数。某些模糊测试器使用����中的种子生成测试用例，而其他模糊测试器使用模型或语法作为参数。

•  INPUTEVAL ( conf, tcs, �bug )→�′, execinfos

  INPUTEVAL接收一个 fuzz conf、一组测试用例���和一个 bug oracle ���� 作为输入。它在 ��� 上执行 PUT，并使用 ����检查执行是否违反了正确性策略。

Fuzzers 的分类

我们可以基于每次 fuzz 运行中语义的粒度将 fuzzers 分为三类：黑盒、灰盒和白盒 fuzzers。

黑盒 fuzzer指的是不查看 PUT 内部逻辑的技术。它只观察 PUT 的输入和输出。黑盒测试在软件测试中也被称为 IO 驱动或数据驱动测试。但一些工作也使用适应性策略为黑盒生成更有意义的测试用例。

与此相反，白盒 fuzzer通过分析 PUT 的内部以及执行 PUT 时收集的信息来生成测试用例。动态符号执行（DSE）可以被视为白盒 fuzzer，因为它用具体的运行时状态替换部分符号值。

灰盒 Fuzzer采取了一种中间态度，获取了 PUT 和/或其执行中的部分内部信息。与白盒 fuzzers 不同，灰盒 fuzzers 不会推理 PUT 的全部语义；相反，它们可能会对 PUT 执行轻量级的静态分析，和/或收集关于其执行的动态信息，如代码覆盖率。这种方法通常依赖于近似的、不完美的信息，从而获得速度，并能够测试更多的输入。

从 X 到 Y 的实线箭头表示 Y 引用、参考或以其他方式使用来自 X 的技术。

• 第 1 列指示 fuzzer 是黑盒（⬤）、白盒（◑）还是灰盒（○）。当 fuzzer 在两个阶段使用不同类型的反馈收集时，会显示两个圆圈。
• 第 2 列显示 fuzzer 的源代码是否公开可用。
• 第 3 列表示 fuzzer 是否需要 PUT 的源代码来操作。
• 第 4 列指示 fuzzer 是否支持内存中的 fuzzing。
• 第 5 列关于 fuzzer 是否可以推断模型。
• 第 6 列显示 fuzzer 在PREPROCESS中执行静态或动态分析。
• 第 7 列表示 fuzzer 是否支持处理多个种子，并进行调度。
• 第 8 列指定 fuzzer 是否执行输入变异来生成测试用例。◑ 表示 fuzzer 根据执行反馈指导输入变异。
• 第 9 列关于 fuzzer 是否基于模型生成测试用例。
• 第 10 列显示 fuzzer 是否执行符号分析来生成测试用例。
• 第 11 列标识了那些利用污点分析来指导其测试用例生成的 fuzzer。
• 第 12 和 13 列显示 fuzzer 是否使用堆栈哈希或代码覆盖率执行崩溃分类。
• 第 14 列表示 fuzzer 在CONFUPDATE期间是否进化种子池，如向池中添加新种子。
• 第 15 列关于 fuzzer 是否在线学习输入模型。
• 第 16 列显示哪些 fuzzer 从种子池中移除种子。

另外，您可以在 fuzzing-survey 上找到知识图谱。

PREPROCESS

某些 fuzzers 在第一次 fuzz 迭代之前，通过修改初始的 fuzz 配置集来准备主循环作为第一步。这样的预处理通常用于对 PUT 进行插桩、去除可能冗余的配置、修剪种子，以及生成驱动应用程序。

插桩

与黑盒 fuzzers 不同，灰盒和白盒 fuzzers 都可以对 PUT 进行插桩，以便在 INPUTEVAL 执行 fuzz 运行时收集执行反馈，或者在运行时模糊内存内容。

程序插桩可以是静态的或动态的——前者在 PUT 运行之前发生（PREPROCESS），而后者在 PUT 运行时发生（INPUTEVAL）。

静态插桩通常在编译时对源代码或中间代码进行。由于它在运行时之前发生，所以通常比动态插桩带来的运行时开销要小。除了基于源的插桩外，研究人员还开发了基于二进制的静态插桩。

尽管动态插桩的开销比静态插桩大，但它的优势在于可以轻松地对动态链接的库进行插桩，因为它是在运行时执行的。

具体而言，插桩可能会设置：

• 执行反馈。LibFuzzer、AFL 及其后续版本通过在 PUT 中对每个分支指令进行插桩来计算分支覆盖率；
• 线程调度。插桩还可以通过明确控制线程的调度来触发不同的非确定性程序行为，例如竞态条件错误。
• 内存中的模糊。在繁琐的初始化之后对 PUT 进行快照可以避免为每次迭代重新生成一个进程。要模糊一个新的测试用例，可以在将新的测试用例直接写入内存之前恢复内存快照。

种子选择与种子修剪

Fuzzers 接收一组控制 fuzzing 算法行为的 fuzz 配置。但 fuzz 配置的某些参数可以有大的甚至无限的域。种子选择问题是关于如何减少初始种子池的大小。

一个常见的方法，称为minset，找到一个最小的种子集，该种子集最大化了覆盖度指标，如节点覆盖度。例如，假设当前的配置集�由两个种子�1和�2组成，它们覆盖 PUT 的以下地址：�1→10,20,�2→20,30。如果我们有第三个种子�3→10,20,30，执行速度大致与�1和�2相同，那么可以认为使用�3进行模糊测试比使用�1和�2更有意义，因为�3在执行时间成本的一半内测试了相同的代码集。

Fuzzers 在实践中使用了各种不同的覆盖度指标。例如，AFL 的 minset 是基于分支覆盖度的，每个分支上有一个对数计数器。这背后的理念是只有当它们的数量级不同时，才认为分支计数是不同的。Honggfuzz基于执行的指令数、执行的分支数和唯一的基本块来计算覆盖度。这个指标允许 fuzzer 将执行时间较长的内容添加到 minset 中，这有助于发现拒绝服务漏洞或性能问题。

此外，种子修剪是另一方面，用于减少种子池的大小。一个使用种子修剪的著名 fuzzer 是 AFL，它使用其代码覆盖度插桩来迭代地移除种子的一部分，只要修改后的种子达到相同的覆盖度即可。

SCHEDULING

回顾之前的通用算法。调度意味着为下一个 fuzz 迭代选择一个 fuzz configuration，通过分析当前的可用信息来得到最有利的结果（例如，最大化覆盖率）。

对于更先进的 fuzzer，如 BFF 和 AFLFast，它们的成功很大程度上归功于它们创新的调度算法。

在黑盒子设置中，**FCS（Fuzz Configuration Scheduling）**算法能使用的唯一信息是一个配置的 fuzz 结果 — 目前使用它发现的崩溃和漏洞的数量以及到目前为止花费在它上的时间。

在灰盒设置中，FCS 算法可以选择使用关于每个 fuzz configuration 的更丰富的信息集，例如，当进行 fuzz 一个配置时所达到的覆盖率。AFL 是这一类别的先驱，它是基于进化算法（EA）的。直观地说，EA 维护一个 fuzz configuration 的种群，每个配置都有一些”适应度”的值。EA 选择适合的配置并应用它们到基因转换如突变和重组，以产生后代，这些后代可能在以后成为新的 fuzz configuration。这种假设是，这些产生的配置更有可能是适合的。

如果你对灰盒调度算法的细节感兴趣，AFL–>AFLFast–>AFLGo 的发展展示了它的进步，同时还有一些后续的 fuzzer 利用静态分析。

INPUT GENERATION

在 fuzzer 的设计中，用于input generation的技术是最关键的部分。传统上，fuzzer 被分为生成型或变异型。

• 生成型 fuzzer 根据描述 PUT 期望的输入的模型来生成测试用例。
• 变异型 fuzzer 通常被视为没有明确模型，因为种子只是示例输入，它们并没有完全描述 PUT 的预期输入范围。

Generation-Based Fuzzers

可以由用户配置预定义模型。这类 fuzzer 提供 API 供用户创建自己的输入模型，或接收用户提供的协议规范、基于语法的输入。

不依赖于预定义或用户提供的模型，而是推导出模型，被称为推导模型。推导可能在PREPROCESS阶段，包括通过数据驱动方法推导控制流图，或通过分析 API 记录来推导输入。PULSAR[2] 根据一套捕获的网络数据包自动推导出网络协议模型。然后使用学到的网络协议对程序进行 fuzz。

Mutation-Based Fuzzers

经典的随机测试在满足特定路径条件的测试用例生成方面效率不高。考虑一个简单的 C 语句：if (input == 42)。如果输入是 32 位整数，随机猜测正确的输入值的概率是1/232。

这种情况激励了基于种子的输入生成以及白盒输入生成。如果你熟悉模拟退火或遗传算法用于优化的原理，你会很容易理解变异型 fuzzer 的理念。它们的目标是筛选出最适合的种子。

Bit-flipping是许多 fuzzer 常用的一种技巧。为了随机地变异种子，一些 fuzzer 采用一个称为 mutation ratio 的用户参数，这决定了在INPUTGEN的单次执行中要翻转的位的数量。

arithmetic mutation将选定的一段视为整数并对其执行简单的算术操作。例如，AFL 可能选择种子中的一个 4 字节值，然后用随机生成的小整数�替换种子中的值，其中�是随机生成的。

还有几种block-based mutation策略，其中 block 是种子的连续字节：

• 在种子的随机位置插入随机生成的块；
• 从种子中删除随机选择的块；
• 用随机值替换随机选择的块；
• 通过添加随机块来调整种子的大小；
• 从一个种子中取一个随机块插入到另一个种子的随机块中；

或者，你可以用预定义的值，如%s和%x这样的格式字符，替换输入中的某些部分。

White-box Fuzzer 的程序分析

对于白盒 fuzzer，它们允许执行复杂的静态或动态分析以进行深入的变异。例如，Dowser[3] 在编译期间进行静态分析，基于启发式方法找出可能包含错误的循环。

Dynamic Symbolic Execution

在高层次上看，经典的符号执行使用符号值作为输入来运行程序。当执行 PUT 时，它构建符号表达式，而不是求值为具体的值。每次达到条件分支指令时，它都会分叉两个符号执行环境，一个为真分支，另一个为假分支。对于每个路径，符号执行为其遇到的每个分支指令构建一个路径公式。如果存在使得路径满足的具体输入，那么路径公式就是可满足的。人们可以通过查询 SMT 求解器获得路径公式的解来生成具体的输入。

但与灰盒或黑盒方法相比，动态符号执行相对较慢。为了解决高成本问题，常见的策略是通过灰盒 fuzzing 估计执行每个路径的概率，或者由用户指定 PUT 的部分来使用动态符号执行。

Guided Fuzzing

Guided fuzzing 主要包括两个阶段：

1. 对 PUT 进行深入的程序分析以获得有用信息，和
2. 根据前面的分析来生成测试用例。

例如，TaintScope[4] 使用精细的污点分析来查找“热点字节”，这些输入字节流入关键的系统或 API 调用。Angora[5] 改进了这种“热点字节”的方法，使用污点分析将每个路径约束与相应的字节相关联。然后，它执行一个受梯度下降算法启发的搜索，以指导其变异以解决这些约束。

INPUT EVALUATION

在生成输入之后，fuzzer 会在此输入上执行 PUT 并决定如何处理执行结果。此过程称为input evaluation。

关键目的是使用 bug oracle 检测 bug，它是一种安全策略。例如，由于指针覆盖导致的内存漏洞在被解引用时可能会抛出段错误。此外，研究者提出了多种方法来高效地检测不安全或不期望的程序行为。

• Memory and Type Safety：追踪有效内存地址和不兼容的类型转换；检测非法的控制流修改。
• Input Validation：例如 XSS 和 SQL 注入漏洞。
• Semantic Difference：语义错误通常通过differential testing方法发现，该方法比较相似（但不完全相同）的程序的行为。

然后，fuzzer 应该对程序 bug 的结果进行分类和分析。分析和报告导致策略违规的测试用例的过程称为triage。

首先，deduplication是从输出集中修剪触发与另一个测试用例相同错误的任何测试用例的过程。由于实际的实现考虑，它避免了在硬盘上存储重复的结果，从而浪费磁盘空间和其他资源。

目前在实践中使用的三种主要去重方法是：stack backtrace hashing、coverage-based deduplication 和Semantics-aware Deduplication。

• Stack backtrace hashing：在此方法中，一个自动化工具会在崩溃时记录 stack backtrace，并基于该 backtrace 的内容分配一个 stack hash。例如，如果程序在执行 function foo 的某行代码时崩溃，并且调用堆栈为main→d→c→b→a→foo，那么一个采用�=5的 stack backtrace hashing 实现会将该测试用例与其他调用堆栈以main→d→c→b→a→foo结束的崩溃执行组合在一起。

  

• Coverage-based Deduplication：根据其文档描述，AFL 认为崩溃是独特的，如果（i）崩溃覆盖了以前未见过的边，或者（ii）崩溃没有覆盖在所有之前的崩溃中出现的边。
• Semantics-aware Deduplication：RETracer [6] 基于每次崩溃的逆向数据流分析来执行崩溃分类。具体而言，RETracer 通过分析崩溃转储（core dump）来检查哪个指针导致了崩溃，并递归地确定哪个指令为其分配了错误的值。它最终找到一个具有最大帧级别的函数并“指责”该函数。然后使用被指责的函数对崩溃进行分类。

其次，Prioritization，也称为 fuzzer 中的taming problem，指的是根据测试用例触发的漏洞的严重性和独特性来对其进行排序或分类。而exploitability则用于非正式地评估，基于某个测试用例所揭示的安全漏洞，开发出实际攻击工具的可能性有多大。

triage的另一个重要部分是test case minimization。测试用例最小化是识别违反策略的测试用例中必要部分的过程，并可选择地产生一个比原来更小、更简单但仍然导致违规的测试用例。

triage 的另一个关键环节是test case minimization。这是一个过程，旨在确定使程序行为异常的测试用例中的关键部分，并可以进一步简化这些用例，生成比原始用例更简短、更简洁的版本，但仍能触发相同的异常行为。

CONFIGURATION UPDATING

CONFUPDATE函数在区分黑盒 fuzzer 与灰盒或白盒 fuzzer 的行为上起到关键作用。CONFUPDATE函数可以基于当前 fuzzing 运行中收集到的配置和执行信息来修改配置集合。例如，进化算法（Evolutionary Algorithm, EA）在新个体被发现的过程中维护了一个承诺的种子池，使该种子池随着 fuzz 活动的进行而进化。大多数基于 EA 的 fuzzer 使用节点或分支覆盖作为适应性函数。

因此，一个常见的研究点是精化适应性函数，使其能够检测到更微妙和更细粒度的改进指标。例如，AFL 通过记录一个分支被执行的次数来优化其适应性函数定义。

Reference

1. Manès, V. J., Han, H., Han, C., Cha, S. K., Egele, M., Schwartz, E. J., & Woo, M. (2019). The art, science, and engineering of fuzzing: A survey. IEEE Transactions on Software Engineering, 47(11), 2312-2331.
2. H. Gascon, C. Wressnegger, F. Yamaguchi, D. Arp, and K. Rieck, “PULSAR: Stateful black-box fuzzing of proprietary network protocols,” in Proc. Int. Conf. Security Privacy Commun. Syst.,2015, pp. 330–347.
3. I. Haller, A. Slowinska, M. Neugschwandtner, and H. Bos, “Dowsing for overflows: A guided fuzzer to find buffer boundary violations,” in Proc. USENIX Security Symp.,2013, pp. 49–64
4. T. Wang, T. Wei, G. Gu, and W. Zou, “TaintScope: A checksumaware directed fuzzing tool for automatic software vulnerability detection,” in Proc. IEEE Symp. Security Privacy, 2010, pp. 497–512.
5. P. Chen and H. Chen, “Angora: Efficient fuzzing by principled search,” in Proc. IEEE Symp. Security Privacy, 2018, pp. 855–869.
6. W. Cui, M. Peinado, S. K. Cha, Y. Fratantonio, and V. P. Kemerlis, “RETracer: Triaging crashes by reverse execution from partial memory dumps,” in Proc. Int. Conf. Softw. Eng., 2016, pp. 820–831.

原文始发于learner L：（十）Fuzzing 基础