翻译 afl白皮书

白皮书地址http://lcamtuf.coredump.cx/afl/technical_details.txt

afl设计目标和动机的讨论地址http://lcamtuf.coredump.cx/afl/historical_notes.txt

0.设计说明

AFL没有专注于奇特的操作原理和特定理论的POC，而是做到最好。AFL可以被认为是一些Hacks技巧的集合，这些技巧在实际应用中被测试，发现非常有效，同时这些技巧以我当时想到的最简单、强健的方式实现。

得益于轻量级指令的使用，使得许多由此产生的功能成为可能，但是这种机制仅被认为一种手段。唯一真正的控制原则是速度、可靠性、易用性。

1.覆盖率测量

指令被注入已经编译好的程序来捕获分支覆盖率，用于粗略统计分支命中次数。被注入分支处的代码本质上等于：

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

为了简化链接复杂项目，cur_location的值被随机生成，并且使用XOR来保持输出均匀分布。

shared_mem[]数组是一个64KB大小共享内存区域，由调用者传递到测试程序中。在输出映射(map)的每个字节集合可以认为命中了被检测代码的一个特殊元组(branch_src, branch_dst)。

通过选择映射内存(map)的大小，使大多数目标的分支冲突是零散的，这些目标代码的分支数大多在2000到10000之间。

 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
     20,000 | 14%              | sqlite
     50,000 | 30%              | -

同时，shared_mem[]数组的大小足够小，使接收段程序在毫秒内分析，同时毫不费力的适应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上确实简单的饱和（saturating）运算符，因此命中计数会出现累计后回到0的情况。这中情况不大会出现在局部事件，因此视为可以为了性能的权衡。

2.检测新行为

模糊器(fuzzer)维持一个之前执行中的全局分支元组映射;这个数据可以快速的与独立的跟踪（traces)进行比较，然后用仅仅几个dword或qword宽执行和一个简单的循环来更新。

当一个突变的输入产生一个包含新元组的执行跟踪时，相应的输入文件将被保留并被路由，以便以后进行额外的处理(参见第3节)。不会在执行跟踪中触发新本地级状态转换的输入（不产生新的分支元组）即使它们的整个控制流序列是惟一的，也会被丢弃。

这种方法允许对程序状态进行非常细粒度和长期的研究，而不必对复杂的执行跟踪执行任何计算密集型和脆弱的全局比较，同时避免了路径爆炸的灾难。

为了展示算法的特性，思考下面两个路径追踪，因为存在新的元组(CA, AE)，所以是新的路径。

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

同时，第二条路径继续，后面的模式将不会被认为是唯一的，尽管有一个明显不同的整体执行路径。

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

除了检测新的元组外，模糊器同时考虑粗粒度元组命中数。这些被分割成几个桶：

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

在某种程度上，桶（bucket）数量是一个人工实现。它允许由指令生成8位计数器的原位映射，用于模糊器可执行程序对所依赖的8个位置位图来保持对已见的分支元组计数进行追踪。

在单个桶范围内的变化会被忽略，而从一个桶到另一个桶的转移，会被认为是程序控制流的一个有趣转变，在下面部分中概述演化过程。

命中统计的行为提供了一种区别潜在有趣的控制流变化的方式，比如一个代码块被执行了两次而通常命中了一次。同时，它对经验上不太明显的变化是很不敏感的，比如一个循环从第47次到第48次。对于密集追踪映射（dense trace maps)的元组冲突，计数器同样提供了一定程度“偶然”免疫力。

通过内存和执行时间来严格控制执行。默认情况，超时时间被设置为初始校准时间的5倍，最大舍入为20ms。主动超时用于减低tarpit，提高1%覆盖率同时降低100倍速度，来防止模糊器性能急速下降。我们务实地拒绝这种情况，希望模糊器能够找到一种更便宜的方法来到达相同的代码。实际测试强烈表明，更充足的时间限制是不值得的。

3.输入队列的演变

在程序中产生新状态变化的变异测试用例将被添加到输入队列中，并用作以后几轮模糊测试的起点。它们作为补充，不会自动替换现有的发现。

相对于更贪婪的遗传，此方法允许AFL逐步探索底层文件格式的各种不相交和可能互不兼容的特征，如下图展示的图片：

下面网址讨论了该算法的许多实际用例：

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

通过此过程生成的合成预料库实质上是“嗯，这做了些新事情”的紧凑文件集合，可以为其他测试过程提供种子（比如，手动对资源密集型桌面程序进行压力测试）。

通过这种方法，大多数目标队列会增加1000到10000个条目；大约10-30%归因于新元组的发现，剩下的是命中次数相关。

下表比较了使用几种不同的引导模糊测试方法时发现文件语法和浏览程序状态的相对能力。 检测到的目标是使用-O3编译并带有虚拟文本文件的GNU补丁2.7.3。 该会话由带有afl-fuzz的输入队列中的一次传递组成：

  Fuzzer guidance | Blocks  | Edges   | Edge hit | Highest-coverage
    strategy used | reached | reached | cnt var  | 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

第一个条目blind fuzzing（“S”)表示测试执行一轮。第二组L表示模糊器使用循环方式运行多个执行周期，与指令执行周期相关，这需要更多的时间才能完全处理增长的队列。

在一个单独的实验中获得了大致相似的结果，在该实验中，对模糊器进行了修改，以编译出所有随机的模糊阶段，只剩下一系列基本的顺序操作，例如步行翻转。 由于此模式无法更改输入文件的大小，因此为会话填充了有效的统一差异：

  Queue extension | Blocks  | Edges   | Edge hit | Number of unique
    strategy used | reached | reached | cnt var  | 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.语料剔除

上述渐进的状态探索方法意味着程序中稍后合成的一些测试用例可能具有边缘覆盖（edge coverage）范围，这是其祖先提供的覆盖范围的严格超集。

为了优化模糊测试的工作量，AFL使用快速算法定期重新评估队列，该算法选择较小的测试用例子集，该用例仍然覆盖到目前为止所看到的每个元组，并且其特性特别适合该工具。

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

然后使用简单的工作流依次处理元组：

1）在临时工作集中找到下一个元组，

2）找到该元组的获胜队列条目（winning queue entry），

3）在工作集中注册该条目的跟踪中存在的所有元组，

4）如果集合中缺少任何元组，请转到1)。

生成的”优先”（favored）条目预料数量比起始数据集小5-10倍。非优先项不会被丢弃，但是在队列中遇到时，它们会被以不同的概率跳过：

• 如果队列存在新的、还未模糊的优先（favored）测试用例，那么跳过99%的未优先的测试用例。
• 如果没有新的优先测试用例
  • 如果已经对当前非优先测试用例进行了模糊测试，那么95%的时间将会跳过它。
  • 如果还未进行模糊测试，那么75%的几率跳过它。

基于经验测试，这在队列循环速度和测试用例多样性之间提供一个合理的平衡。

使用afl-min工具在输入或输出预料库上执行稍微复杂且更慢的语料剔除。

5.整理输入文件

文件大小对模糊测试性能有着巨大的影响，因为大文件会导致目标二进制文件变慢，并且降低测试用例变异（mutated）接触文件结构中控制格式而不是冗余数据块的可能性。在perf_tips.txt对此进行更详细的讨论。

除了用户可能会提供低质量的初始预料库外，某些类型的变异（mutated）也可能具有也可能逐步增加生成文件大小的作用，因此如何应对这种趋势很重要。

幸运的是，检测反馈机制提供了一种自动缩小输入文件的简单方法，同时确保对文件的更改不会影响执行路径。

afl-fuzz内置的整理器（trimmer）尝试按顺序删除具有可变长度和步进的数据块。任何不影响追踪映射图（trace map）校验和的删除都被提交到磁盘。整理器（trimmer）的设计不是特别彻底（not designed to be particularly），相反，它尝试在精度和execve()调用次数之间取得平衡，选择块大小和步长。平均每个文件收益为5-20%

afl-tmin工具使用更详尽，迭代的算法，并且还尝试对修剪后的文件执行字母标准化。 afl-tmin的操作如下：

首先，afl-tmin会自动选择操作模式。如果初始输入导致目标二进制崩溃，afl-tmin会运行在无命令模式（non-instrumented mode），仅保留产生简单测试用例文件的调整。如果目标二进制不会崩溃，afl-tmin使用命令模式（instrumented mode），只保留产生完全相同执行路径的调整。

实际的最小化算法为：

1. 尝试使用较大步进将大数据块归零。经验上，这可以通过减少细粒度工作来减少执行人员数量。
2. 通过减少块长度、步进、二进制搜索样式（binary-search-style）来执行块删除操作。
3. 通过计算唯一字符并尝试用零值来批量替换每个字符来执行字母归一化。
4. 最后，对非0字节执行逐字节标准化。

afl-tmin使用ASCII数字’0’代替使用数字0x00清零。这样的修改不太可能干扰文本解析，所以更有可能成功最小化文本文件。

与其他学术论文中提出的测试用例最小化方法相比，afl-tmin更加简单（less involved)，需要的执行量少得多，并且在大多数实际应用中往往产出更多可比的结果。

6.模糊测试策略

指令（instrumentation）提供的反馈使其轻松了解各种模糊策略的价值，并且优化策略参数，从而使它们能够在各种文件类型中均能很好地工作。afl-fuzz所使用的策略与文件格式无关，更多细节在：http://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html

值得注意的是在早期，afl-fuzz所做大部分工作实际上都是确定性的，在后期才逐渐增加随机栈修改和测试用例拼接。确定性策略包括：

• 使用不同长度、步进来顺序位翻转（bit flips）。
• 对小整数进行顺序加法。
• 顺序插入已知的有趣数字（比如0、1、INT_MAX等）。

以确定性步骤执行的目的在于非崩溃输入与崩溃输入之间产生较小差异。

非确定性步骤包括堆叠位（stacked bit）翻转、插入、删除、算术操作、不同测试用例拼接。

所有策略的相对收益和execve()成本已经在上面提及的博客文章中进行了讨论。

出于historical_notes.txt中讨论的原因（主要是性能、简单性、可靠性），AFL通常不会尝试推断特殊变异与程序状态之间的关系。模糊化步骤名义上是盲目的，仅由输入队列的演化设计来指导。

也就是说，此规则有一个（不重要的）例外：当队列中条目经历了确定性步骤的初始集合时，观察到文件中某些区域的调整对执行路径的校验和无影响，它们可能会被排除在确定性模糊测试之外，模糊测试可能会直接进行随机调整。特别是对于冗长的、人类可读的数据格式，这可以将程序的执行次数减少10-40%，而覆盖率却没有明显下降。在极端情况下，例如常见的块对齐tar归档，收益可能高达90%

因为底层的“effector maps”在每个队列条目中都是本地的，并且仅在确定阶段有效，同时不会改变文件大小和总体布局，因此这个机制看起来非常可靠，且易于实现。

7.字典

工具（instrumentation）提供的反馈使自动识别某些类型输入文件中语法标记、检测预定义、或自动检测词典术语的某些组合构成的有效语法变得容易。

关于afl-fuzz中这些功能如何实现的讨论可以在下面的链接中查看：http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html

本质上，将容易获得的基础语法符号（token）以纯随机的方式组合一起，队列的发展和工具（instrumentation）一起提供了一种反馈机制，以区分无意义的变异和触发检测代码新行为的变异，并在此发现之上逐步构建更复杂的语法。

词典已显示能够让模糊器快速的重建高度冗长和复杂的语言，比如javascript、sql、xml；上面提到的博客文章给出了几个生成SQL语句的示例。

有趣的是afl工具还运行模糊器自动隔离输入文件中已经存在的语法标记。它通过查找字节的运行来实现，这些字节的运行在翻转时会对程序的执行路径产生持久的影响。这表示与代码中预定义值之间的原子比较。模糊器依靠这个信号来构建紧凑的”自动化词典“（auto dictionaties），然后与其他模糊策略结合使用。

8.反重复崩溃（De-duping crashes）

对于任何称职的模糊测试工具来说，防止重复引起崩溃是更重要的问题之一。许多简单的方法都会出现这种问题。特别地，如果问题出现在常用的库函数（say、strcmp、strcpy）中，仅仅查看错误发生地址会导致不相关的问题聚集在一起。如果通过许多不同、可能递归的代码路径到达错误发生处，那么校验和调用栈可能导致极端的崩溃统计膨胀。

如果满足下面两个条件之一，则afl实施方案认为崩溃是唯一的：

• 崩溃追踪包含以前任何崩溃中都没有发现的分支路径元组。
• 崩溃追踪丢失了之前崩溃一直存在的元组。

该方法很容易在早期受到某些路径计数膨胀的影响，但具有非常强的自我限制，类似afl-fuzz的执行路径分析逻辑。

9.崩溃调查

许多类型的崩溃的可利用性可能是模棱两可的。 afl-fuzz尝试通过提供一种崩溃探索模式来解决此问题，在该模式下，以一种与模糊测试器的正常操作非常相似的方式对已知故障的测试用例进行模糊测试，但是存在一个约束条件，该约束条件会导致丢弃任何非崩溃的突变 。

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

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

该方法使用工具的反馈来探索崩溃程序的状态，以克服模棱两可的故障条件，然后隔离新发现的输入以供人工检查。

关于崩溃，值得注意的是，与普通队列条目相比，崩溃输入不修剪； 它们将完全按照发现的方式保存，以便更轻松地将它们与队列中的父级非崩溃条目进行比较。 也就是说，可以使用afl-tmin随意收缩它们。

10.Fork server

为了提高性能，afl-fuzz使用了一个“ fork server”，其中经过模糊处理的进程仅通过execve()、链接和libc初始化进行一次，然后通过利用写时复制从停止的进程映像中进行克隆。此处更详细地描述了实现：

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

fork server是注入的指令的一部分，并且仅在第一个指令工具处停止以等待来自afl-fuzz的命令。

使用快速目标，fork server可以提供可观的性能提升，通常在1.5倍至2倍之间。也可以：

• 在手动（“延迟deferred”）模式下使用fork server，跳过较大的，用户选择的初始化代码块。它要求对目标程序进行非常少量的代码更改，并且对于某些目标，可以产生10倍以上的性能提升。

• 启用“持久persistent”模式，该模式使用单个进程来尝试多个输入，从而极大地限制了重复fork（）调用的开销。通常，这需要对目标程序进行一些代码更改，但可以将快速目标的性能提高5倍或更多。在保持模糊测试过程与目标二进制文件之间非常稳健的隔离的同时，类似进程内模糊测试工作的好处。

11.并行化

并行化机制依赖于定期检查由其他CPU内核或远程计算机上独立运行的实例所产生的队列，然后选择性地引入测试用例，这些测试用例在本地尝试时会产生手头模糊器尚未看到的行为。

这在模糊器设置中提供了极大的灵活性，包括在具有共同效果的情况下针对通用数据格式的不同解析器运行同步实例。

有关此设计的更多信息，请参见parallel_fuzzing.txt。

12. 二进制目标

在“用户态模拟”模式下，借助单独构建的QEMU版本，可以完成对黑箱，仅二进制目标的检测。这也允许执行跨体系结构的代码-例如x86上的ARM二进制文件。

QEMU使用基本块作为翻译单位；该工具是在此基础上实现的，并使用与编译时钩子（compile-time hooks）大致类似的模型：

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 server。该通道用于通知父对象任何新遇到的块的地址，并将其添加到将为将来的子进程复制的转换缓存中。

这两项优化的结果是，与PIN的100x +相比，QEMU模式的开销约为2-5倍。

13.afl-analyze工具

文件格式分析器是前面讨论的最小化算法的简单扩展；该工具执行一系列连续的字节翻转，然后注解输入文件中的字节运行，而不是尝试删除无操作块。

它使用以下分类方案：

• “无操作块”：位翻转不会明显改变控制流的段。常见示例可能是注释部分，位图文件中的像素数据等。

• “表面内容”：部分（但不是全部）bitflips的片段

  产生一些控制流变化。示例可以包括丰富文档（例如XML，RTF）中的字符串。
  

• “关键流”：字节序列，所有位翻转均以不同但相关的方式改变控制流。这可能是压缩数据，非原子比较关键字或魔术值等。

• “可疑长度字段”：小的原子整数，以任何方式接触时，都会导致程序控制流发生一致的变化，提示长度检查失败。

• “可疑的校验和cksum或魔数magic int”：一个与长度字段类似的整数，但是其数值使长度解释不太可能。这表明校验和或其他“魔术”整数。

• “疑似校验和块”：一长串数据，其中任何更改总是触发相同的新执行路径。可能是由于在进行任何后续解析之前，校验和失败或类似的完整性检查失败引起的。

• “魔数部分（magic value section）”：一种通用标记，其中的更改会导致前面概述的二进制行为类型，但不满足其他任何条件。可能是原子比较关键字。