AFL技术 白皮书

GPT翻译AFL whitepaper，建议对照原文阅读，或者直接阅读原文。

附原文链接：https://lcamtuf.coredump.cx/afl/technical_details.txt

本文档提供了对American Fuzzy Lop（AFL）内部工作原理的简要概述。有关通用指南，请参阅README；关于AFL背后的动机和设计目标的讨论，请参阅historical_notes.txt。

0）设计说明

American Fuzzy Lop 尽力避免专注于任何单一操作原则，也不是针对特定理论的概念验证。这个工具可以被视为一系列经过实践测试、被证实具有惊人有效性，并且在当时我能想到的最简单、最健壮的方式下实施的一些技巧的集合。

其中许多特性的实现得益于轻量级插装技术的可用性，这为该工具提供了基础，但这个机制仅仅应被视为达到目的的手段。唯一真正的主导原则是速度、可靠性和易用性。

1）覆盖率测量

在编译程序中注入的插装代码会捕获分支（边缘）覆盖率，以及粗略的分支执行次数。在分支点注入的代码本质上等同于：

cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++; 
prev_location = cur_location >> 1;

cur_location的值是随机生成的，以简化复杂项目的链接过程，并保持XOR输出均匀分布。

shared_mem[]数组是一个64KB的共享内存区域，由调用方传递给插桩二进制文件。在输出映射中设置的每个字节可以看作是插装代码中特定的（branch_src，branch_dst）元组的执行次数。

映射（map）的大小被选择为几乎所有预期目标的碰撞都是零散的，这些目标通常具有2k到10k个可发现的分支点：

Branch cnt	Colliding tuples	Example targets
1,000	0.75%	giflib, lzo
2,000	1.5%	zlib, tar, xz
5,000	3.5%	libpng, libwebp
10,000	7%	libxml
50,000	30%	-

同时，映射的大小足够小，以便在接收端可以在微秒级别内进行分析，并且轻松适应L2缓存中。

这种形式的覆盖率比简单的块覆盖率提供了更多关于程序执行路径的信息。特别地，它可以轻松区分以下执行跟踪：

A -> B -> C -> D -> E (tuples: AB, BC, CD, DE)
A -> B -> D -> C -> E (tuples: AB, BD, DC, CE)

这有助于发现底层代码中的微妙错误条件，因为安全漏洞通常与意外或错误的状态转换相关，而不仅仅是到达一个新的基本块。

在之前展示的伪代码中，最后一行进行的位移操作是为了保留元组的方向性（否则，A ^ B 将无法区分于 B ^ A），并保持紧密循环的身份（否则，A ^ A 显然等于 B ^ B）。

在 Intel CPU 上缺乏简单的饱和算术操作码意味着命中计数器有时可能会归零。由于这是一个相当不太可能和局部化的事件，因此被视为可接受的性能权衡。

2）检测新的行为

模糊测试器维护着一个全局元组映射表，其中记录了先前执行中出现的元组。这些数据可以与单个执行跟踪快速比较，并通过几个双字或四字宽的指令和简单的循环进行更新。

当经过变异的输入产生了包含新元组的执行跟踪时，相应的输入文件将被保留并路由到后续的额外处理中（参见第3节）。那些在执行跟踪中没有触发新的局部状态转换（即没有产生新元组）的输入将被丢弃，即使它们的整体控制流序列是唯一的。

这种方法可以在程序状态上进行非常精细和长期的探索，而无需执行计算密集型且易于出错的复杂执行跟踪的全局比较，并避免了路径爆炸的问题。

为了说明该算法的特性，考虑下面所示的第二个执行跟踪，由于存在新的元组（CA、AE），它将被认为是显著新的：

#1: A -> B -> C -> D -> E
#2: A -> B -> C -> A -> E

同时，经过#2的处理后，尽管具有明显不同的整体执行路径，以下模式将不被视为唯一：

#3: A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E

除了检测新的元组之外，模糊测试工具还考虑了粗粒度元组的命中计数。这些计数被分为几个桶：

1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+

在某种程度上，桶的数量是一种实现的产物：它允许将插装生成的8位计数器就地映射到模糊测试工具可执行文件所依赖的8位位图中，以跟踪每个元组的已见执行计数。

单个桶范围内的更改将被忽略；从一个桶到另一个桶的转换被标记为程序控制流的有趣变化，并被路由到下面一节中概述的进化过程中。

命中计数的行为提供了一种区分潜在有趣的控制流变化的方式，例如某段代码在通常只执行一次的情况下执行两次。同时，它对经验上不太显著的变化（例如循环从47个周期变为48个周期）相对不敏感。计数器还在稠密的跟踪图中提供了一定程度的“偶然”抵抗元组碰撞的能力。

执行受到内存和执行时间限制的严格监控；默认情况下，超时时间设置为初始校准执行速度的5倍，向上取整为20毫秒。这种激进的超时设置旨在防止模糊测试器性能因陷入”粘着陷阱”而严重下降，即在性能提升1%的同时变慢100倍；我们实用主义地拒绝它们，并希望模糊测试器能找到更廉价的方式达到相同的代码。经验测试强烈表明，更宽松的时间限制不值得代价。

3）演化输入队列

将产生了程序内新状态转换的突变测试用例添加到输入队列中，并作为未来一轮模糊测试的起点。它们是对现有发现的补充，而不是自动替换。

与更贪婪的遗传算法相比，这种方法允许工具逐步探索底层数据格式的各种不相交且可能相互不兼容的特征，如下图所示：

这个算法的几个实际例子在这里进行了讨论：

http://lcamtuf.blogspot.com/2014/11/pulling-jpegs-out-of-thin-air.html
http://lcamtuf.blogspot.com/2014/11/afl-fuzz-nobody-expects-cdata-sections.html

通过这个过程产生的合成语料库实质上是一组紧凑的“嗯，这个做了一些新的事情！”输入文件的集合，并可用于后续的任何其他测试过程中（例如，手动对资源密集型桌面应用程序进行压力测试）。

采用这种方法，大多数目标的队列增长到大约1,000到10,000个条目之间；其中大约10-30％归因于新元组的发现，其余则与命中计数的变化有关。

下表比较了在使用几种不同的引导模糊测试方法时，发现文件语法和探索程序状态的相对能力。被插装的目标是使用-O3编译的GNU patch 2.7.3，并使用虚拟文本文件进行种子；会话包括对输入队列的单次遍历，使用afl-fuzz进行模糊测试：

Fuzzer guidance strategy used	Blocks reached	Edges reached	Edge hit cnt var	Highest-coverage test case generated
(Initial file)	156	163	1.00	(none)
Blind fuzzing S	182	205	2.23	First 2 B of RCS diff
Blind fuzzing L	228	265	2.23	First 4 B of -c mode diff
Block coverage	855	1,130	1.57	Almost-valid RCS diff
Edge coverage	1,452	2,070	2.18	One-chunk -c mode diff
AFL model	1,765	2,597	4.99	Four-chunk -c mode diff

盲目模糊测试的第一个条目（“S”）表示只执行了一轮测试；第二组数据（“L”）显示模糊器循环运行的次数与插装运行的次数相当，但需要更多时间来完全处理不断增长的队列。

在另一个单独的实验中，将模糊器修改为编译掉所有随机模糊阶段，只保留一系列基本的顺序操作，例如逐位翻转。由于这种模式无法改变输入文件的大小，因此会话使用有效的统一差异进行种子操作，大致获得了类似的结果：

Queue extension strategy used	Blocks reached	Edges reached	Edge hit cnt var	Number of unique crashes found
(Initial file)	624	717	1.00	-
Blind fuzzing	1,101	1,409	1.60	0
Block coverage	1,255	1,649	1.48	0
Edge coverage	1,259	1,734	1.72	0
AFL model	1,452	2,040	3.16	1

正如前面所提到的，一些关于遗传模糊测试的先前工作依赖于维护单个测试用例并通过演化来最大化覆盖率。至少在上述描述的测试中，这种“贪婪”的方法似乎并没有比盲目模糊测试策略带来实质性的好处。

4）精简语料库

上述的渐进状态探索方法意味着在游戏的后期合成的一些测试用例的边缘覆盖范围可能是其祖先所提供的覆盖范围的严格超集。

为了优化模糊测试的效果，AFL定期使用一种快速算法重新评估队列，选择一个更小的子集，仍然覆盖到目前为止见到的每个元组，并具有使它们对该工具特别有利的特征。

该算法通过为每个队列条目分配与其执行延迟和文件大小成比例的分数来工作，然后选择每个元组的得分最低的候选项。

然后，这些元组按顺序使用简单的工作流程进行处理：

1. 找到尚未在临时工作集中的下一个元组，
2. 定位该元组的获胜队列条目，
3. 在工作集中注册该条目的跟踪中存在的所有元组，
4. 如果集合中存在任何缺失的元组，则返回到步骤#1。

生成的“favored”条目语料库通常比起始数据集小5-10倍。Non-favored 条目不会被丢弃，但在队列中遇到时，它们以不同的概率被跳过。

• 如果队列中存在尚未进行模糊测试的新的优选条目，将跳过99%的非优选条目以便处理这些优选条目。
• 如果没有新的优选条目：
  • 如果当前的非优选条目之前已经进行过模糊测试，则有95%的概率跳过它。
  • 如果它尚未进行过任何模糊测试轮次，则跳过的概率降低到75%。

根据实证测试，这提供了队列循环速度和测试用例多样性之间的合理平衡。

稍微更复杂但速度较慢的剪枝可以使用afl-cmin在输入或输出语料库上进行。该工具永久丢弃冗余条目并生成适用于afl-fuzz或外部工具的较小语料库。

5）裁剪输入文件

文件大小对模糊测试性能有着显著影响，原因在于大文件使目标二进制文件变得更慢，并且它们减少了变异会触及重要格式控制结构而不是冗余数据块的可能性。这一点在《perf_tips.txt》中有更详细的讨论。

除了用户提供低质量的起始语料库之外，某些类型的变异可能会导致生成的文件大小逐步增加，因此重要的是要抵消这种趋势。

幸运的是，插桩反馈提供了一种自动修剪输入文件的简单方法，同时确保对文件所做的更改不会影响执行路径。

afl-fuzz 中内置的修剪器尝试顺序地移除具有可变长度和跳过步骤的数据块；对于不会影响跟踪映射校验和的删除操作，将其保存到磁盘上。修剪器并不设计得非常彻底；相反，它试图在精度和进程上的 execve() 调用次数之间取得平衡，选择与块大小和跳过步骤匹配的设置。平均每个文件的收益约为 5-20%。

独立的 afl-tmin 工具使用一种更详尽、迭代的算法，还尝试对修剪后的文件进行字母归一化。afl-tmin 的操作如下。

首先，该工具会自动选择操作模式。如果初始输入导致目标二进制文件崩溃，afl-tmin 将以非插桩模式运行，只保留那些生成了更简单的文件但仍导致目标崩溃的调整。如果目标不会崩溃，该工具将使用插桩模式，并仅保留产生完全相同执行路径的调整。

实际的最小化算法如下：

1. 尝试用大的步长将大块数据置零。经验证明，这可以在后续更细粒度的尝试之前减少执行次数。
2. 以二分搜索的方式，使用逐渐减小的块大小和步长进行块删除。
3. 通过计算唯一字符的数量，尝试用零值进行批量替换，进行字母归一化。
4. 作为最后的结果，在非零字节上进行逐字节的归一化处理。

相比使用0x00字节将数据置零，afl-tmin使用ASCII数字’0’进行替换。这样做的原因是这种修改更不容易干扰文本解析，因此更有可能成功地对文本文件进行最小化处理。

这里使用的算法比一些学术工作中提出的其他测试用例最小化方法要简单，但需要更少的执行次数，并且在大多数实际应用中产生相当的结果。

6）Fuzzing策略

插桩提供的反馈信息使得理解各种模糊测试策略的价值并优化其参数，以便在广泛的文件类型上同样发挥作用变得容易。afl-fuzz使用的策略通常不依赖于特定文件格式，并在此处进行了更详细的讨论：

http://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html

值得注意的是，特别是在早期阶段，afl-fuzz的大部分工作实际上是高度确定性的，并且仅在后期才逐渐转向随机的叠加修改和测试用例拼接。确定性策略包括：

• 以不同的长度和步进进行顺序位翻转，
• 逐个添加和减去小整数，
• 逐个插入已知的有趣整数（0、1、INT_MAX等），

以确定性步骤开头的目的与它们倾向于产生紧凑的测试案例和非崩溃输入与崩溃输入之间的小差异有关。

完成确定性模糊测试后，非确定性步骤包括堆叠的位翻转、插入、删除、算术运算和不同测试案例的拼接。

所有这些策略的相对收益和execve()成本已经进行了调查，并在上述博客文章中进行了讨论。

由于性能、简单性和可靠性等原因，AFL通常不尝试推理特定变异和程序状态之间的关系；模糊测试步骤在名义上是盲目的，仅由输入队列的演化设计指导。

尽管如此，这个规则有一个（微不足道的）例外：当一个新的队列条目经过初始的确定性模糊测试步骤，并且观察到对文件中某些区域的调整对执行路径的校验和没有影响时，它们可以被排除在剩余的确定性模糊测试阶段之外，模糊测试器可以直接进行随机调整。对于冗长、可读性强的数据格式，这可以减少大约10-40%的执行次数，而覆盖率几乎没有明显下降。在极端情况下，比如通常以块对齐的tar档案，收益可以高达90%。

由于底层的”效应器映射”是每个队列条目局部的，并且仅在不改变底层文件的大小或一般布局的确定性阶段有效，这个机制似乎非常可靠，并且证明了实现起来很简单。

7）字典

插桩提供的反馈信息使得在某些类型的输入文件中自动识别语法标记变得容易，并且可以检测到预定义或自动检测的字典术语的某些组合构成了被测试解析器的有效语法。

可以在这里找到有关在afl-fuzz中实现这些特性的讨论：

http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html

基本上，当基本的、通常容易获取的语法标记以纯随机的方式组合在一起时，插桩和队列的进化设计共同提供了一种反馈机制，用于区分无意义的突变和触发插桩代码中新行为的突变，并逐步构建更复杂的语法。

使用词典已被证明能够使模糊测试工具快速重构高度冗长和复杂的语言的语法，例如JavaScript、SQL或XML。在上述提到的博客文章中，给出了几个生成的SQL语句的示例。

有趣的是，AFL的插桩机制还使得模糊测试工具能够自动分离已存在于输入文件中的语法标记。它可以通过查找连续的字节序列，当进行位翻转时，会对程序的执行路径产生一致的变化；这暗示了代码中固定值的原子比较。模糊测试工具依靠这个信号来构建紧凑的”自动词典”，然后与其他模糊测试策略结合使用。

8）De-duping crashes去除复制的崩溃

在任何高效的模糊测试工具中，崩溃去重是一个非常重要的问题。许多朴素的方法都会遇到问题。特别是，仅仅关注错误地址可能会导致完全不相关的问题被聚集在一起，如果错误发生在一个常见的库函数（比如strcmp、strcpy）中；而对调用堆栈回溯进行校验和计算可能会导致崩溃次数极度膨胀，如果故障可以通过多个不同的、可能是递归的代码路径到达。

afl-fuzz实现的解决方案在以下两种情况下将考虑崩溃为唯一：

• 崩溃跟踪包含了之前崩溃中未见过的元组，
• 崩溃跟踪缺少之前所有故障中始终存在的元组。

这种方法在早期可能会导致一些路径计数的膨胀，但它表现出非常强的自限制效应，类似于afl-fuzz的执行路径分析逻辑，这也是afl-fuzz的基石。

9）调查崩溃

许多类型的崩溃漏洞的可利用性是模棱两可的。afl-fuzz尝试通过提供崩溃探索模式来解决这个问题。在这种模式下，一个已知会导致故障的测试样本被以与模糊测试器正常操作非常相似的方式进行模糊测试，但有一个限制条件，即任何非崩溃的变异都会被丢弃。

关于这种方法的价值的详细讨论可以在这里找到：

http://lcamtuf.blogspot.com/2014/11/afl-fuzz-crash-exploration-mode.html

该方法利用插桩反馈来探索崩溃程序的状态，以克服模糊的故障条件，并将新发现的输入进行隔离，供人工审查。

关于崩溃问题，值得注意的是，与普通队列条目不同，崩溃输入不会被修剪；它们会被保留原样，以便更容易将它们与队列中的父级非崩溃条目进行比较。不过，可以使用afl-tmin来根据需要缩小它们的大小。

10）The fork server

为了提高性能，afl-fuzz使用了一个”fork server”（分叉服务器），其中模糊的进程只需要通过一次execve()、链接和libc初始化，并且通过利用写时复制（copy-on-write）从一个停止的进程镜像进行克隆。具体的实现细节可以在这里找到：

http://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html

fork server 是注入的插装功能的重要组成部分，它会在第一个插装函数处停止，并等待来自afl-fuzz的命令。

使用快速目标时，fork server可以带来相当大的性能提升，通常在1.5倍到2倍之间。还有其他可能的优化方式，包括：

• 在手动（”延迟”）模式下使用分叉服务器，跳过较大的、用户选择的初始化代码块。这只需要对目标程序进行很小的代码修改，并且对于某些目标，可以实现10倍以上的性能提升。
• 启用”持久”模式，在单个进程中尝试多个输入，大大减少了重复fork()调用的开销。这通常需要对目标程序进行一些代码修改，但可以将快速目标的性能提升5倍以上，接近在进程内进行模糊测试作业的好处，同时仍保持非常强大的分离性，将模糊器进程和目标二进制之间进行隔离。

11）并行化

并行化机制依赖于定期检查在其他CPU核心或远程机器上独立运行的实例产生的队列，然后有选择性地引入在本地尝试时产生的尚未被当前fuzzer看到的行为的测试用例。

这种设计允许在fuzzer设置中具有极大的灵活性，包括针对共同数据格式的不同解析器运行同步实例，通常会产生协同效应。

有关这一设计的更多信息，请参阅parallel_fuzzing.txt。

12）二进制插桩

对于黑盒的二进制目标，使用单独构建的 QEMU 版本在“用户仿真”模式下完成插桩。这也允许在不同架构之间执行代码，例如在 x86 上执行 ARM 二进制代码。

QEMU 将基本块作为翻译单元；插桩是在此基础上实现的，并使用类似于编译时钩子的模型：

if (block_address > elf_text_start && block_address < elf_text_end) {

    cur_location = (block_address >> 4) ^ (block_address << 8);
    shared_mem[cur_location ^ prev_location]++; 
    prev_location = cur_location >> 1;

  }

第二行中基于移位和异或的混淆用于遮蔽指令对齐的影响。

QEMU、DynamoRIO 和 PIN 等二进制翻译器的启动速度相对较慢；为了解决这个问题，QEMU 模式利用了类似于编译器插桩代码中使用的 fork 服务器，有效地生成已在 _start 处暂停的已初始化进程的副本。

首次翻译新的基本块也会产生相当大的延迟。为了消除这个问题，AFL fork 服务器通过在运行的模拟器和父进程之间提供通道进行扩展。该通道用于通知父进程有关任何新遇到的块的地址，并将它们添加到将来的子进程中将被复制的翻译缓存中。

由于这两个优化，QEMU 模式的开销约为 2-5 倍，而 PIN 则为 100 倍以上。

13）afl-analyze工具

文件格式分析器是先前讨论的最小化算法的简单扩展；该工具不是试图删除无操作块，而是执行一系列字节翻转，然后对输入文件中的字节序列进行注释标记。

它使用以下分类方案：

• “无操作块”（No-op blocks） - 在这些段中，位翻转对控制流没有明显的变化。常见的例子可能是注释部分、位图文件中的像素数据等。
• “表面内容”（Superficial content） - 在这些段中，一些位翻转会引起一些控制流的变化，但并非所有的位翻转都会产生变化。例如，富文档（如XML、RTF）中的字符串。
• “关键流”（Critical stream） - 一系列字节，其中所有的位翻转以不同但相关的方式改变控制流。这可能是压缩数据、非原子比较的关键字或魔术值等。
• “疑似长度字段”（Suspected length field） - 一个小的原子整数，在任何方式下触摸时都会引起一致的控制流变化，暗示长度检查失败。
• “疑似校验和或魔术整数”（Suspected cksum or magic int） - 一个整数，行为类似于长度字段，但其数值使得长度解释不太可能。这暗示着校验和或其他”魔术”整数。
• “疑似校验和块”（Suspected checksummed block） - 一个较长的数据块，任何变化总是触发相同的新执行路径。很可能是在后续解析之前，未通过校验和或类似完整性检查。
• “魔法值段”（Magic value section） - 一种通用的令牌，其中的变化会导致前面概述的二进制行为类型，但不符合其他任何标准。可能是原子比较的关键字或其他内容。