AFL解析篇0x01 AFL技术手册（翻译）

前言

本文翻译自AFL的技术白皮书，如果英文水平足够还是建议去看原文
https://lcamtuf.coredump.cx/afl/technical_details.txt
在对AFL进行源码剖析之前，先看一下里边包含了哪些技术点，使得在后续阅读源码的时候能做到有的放矢。

0.设计说明

AFL尽量不去关注任何单一的操作原则，也不去证明任何特定的理论。这个工具可以被看作是经过时间测试的一组技巧，它们被发现非常有效，并且以最简单、最见状的方式实现。

许多由此产生的特性之所以成为可能，都要归功于作为该工具基础的轻量级工具的可用性，但这种机制应该仅仅被视为达到目的的一种手段。唯一真正的控制原则是速度、可靠性和易用性。

1.覆盖率度量

通过插桩收集编译后程序的分支（边）覆盖率，以及粗糙的分支命中计数，在分支点注入的代码本质上等同于

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

cur_location的值是随机生成的，以简化连接复杂项目的过程，并保持异或操作之后的分布均匀。

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

同时，它的大小足够小，可以让map在接收端在几微妙内被分析，并且可以轻松地装入L2缓存。

这种形式地覆盖比简单的块覆盖更能深入了解程序的执行路径。特别是，它简单地区分了以下执行跟踪：

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

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

移位操作的原因在伪代码的最后一句显示，通过这个可以区分出来（B^A,AB）.

intel cpu上没有简单的饱和算术操作码，这意味着命中计数器有时会绕到零。由于这是一个不大可能发生的本地化事件，因此它被视为可接受的性能权衡。

2.检测新的行为

fuzzer维持一个之间执行中的全局元组的map；这些数据可以与单独的跟踪进行快速编辑哦，并且在两个dword或qword范围的指令和一个简单的循环中进行更新

当一个变异后的输入产生了一个包含新元组的执行轨迹，相应的输入文件将被保留并且添加后续的路由。对于在执行轨迹中不能触发新的区域的转换被抛弃，即使即使它们的整体控制流序列是唯一的。

这种方法允许对程序状态进行非常细粒度和长期的探索，同时不需要对复杂的执行轨迹执行任何计算密集型和脆弱的全局比较，同时避免路径爆炸的问题。

为了解释该算法，考虑以下两种路径，第二条路径较之第一条会被认为是全新的，因为有新的元组(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

除了检测新的元组外，fuzzer还考虑粗糙的元组命中计数，这些被分为几个部分：

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

在某种程度上，命中的数量是一个实现工件：它允许由检测生成的8位计数器到fuzzer可执行文件所依赖的8位位图的原位映射，以跟踪每个元组已经看到的执行次数。

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

命中计数行为提供了一种方法来区分可能感兴趣的控制流更改，例如执行两次的代码块，而该代码块通常只命中一次。与此同时，它对经验上不太显著的变化相当不敏感，比如从47循环到48循环的循环。计数器还提供了某种程度的对密集跟踪映射中元组冲突的”意外“免疫。

执行受到内存和执行时间的限制；默认情况下，超时设置为初始校准执行速度的5倍，四舍五入到20毫秒。激进的超时是为了防止模糊器的性能急剧下降，比如，提高1%的覆盖率，同时速度慢100倍；我们务实地拒绝它们，并希望fuzzer将找到一个更便宜地方式来达到相同的代码。经验检验强烈表明，更慷慨的时间限制并不值得付出代价。

3.演化输入队列

在程序中产生新状态转换的突变测试用例将被添加到输入队列中，并用作未来几轮模糊操作的起点。它们补充，但不会自动取代现有的发现。

与更贪婪的遗传算法相比，这种方法允许工具逐步探索底层数据格式的各种不关联和可能相互不兼容的特性。

这个过程生成的合成语料库本质上是”嗯，这做了一些新事情！“。输入文件的紧凑集合，可以用来为任何其他测试过程提供种子（例如，手动对资源密集型桌面应用程序进行压力测试）

使用这种方法，大多数目标的队列会增长1k到10k条目之间；其中大约10%-30%归因于新元组的发现，其余部分与命中数的变化有关。

在前面提到的时候，遗传模糊的一些早期工作依赖于维护单个测试用例，并将其演化以最大化覆盖范围。至少在上面描述的测试中，这种”贪婪“的方法似乎并没有比盲目模糊策略带来实质性的好处。

4.精简语料库

上面概述的渐进状态探索方法意位着，在测试中稍后合成的一些测试用例可能具有新的边缘覆盖，是它们的祖先提供的覆盖的严格超集。

为了优化模糊工作，AFL使用一种快速算法周期性地重新评估队列，该算法选择一个更小的测试用例子集，这些测试用例仍然覆盖到目前为止看到的每个元组，并且它们的特征使它们特别适合该工具。

该算法的工作原理是根据每个队列条目的执行延迟和文件大小为其分配一个分数；然后为每个元组选择得分最低的候选人。

使用一个简单的工作流元组顺序处理：

1）查找下一个元组中是否有临时工作集

2）定位赢得队列输入的元组

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

4）如果集合中有任何遗漏的元组，回到1）

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

-如果触发了新的行为，没有被fuzz过的favorites在队列中，99%的不感兴趣的输入将跳过 从而得到favored ones。

-如果没有行为：

-如果当前不敢兴趣的输入之前被fuzz过了，其被跳过的概率是95%

-如果它还没有被fuzz，跳过的概率下降到75%

通过实证测试，在队列循环速度和测试用例多样性之间实现了合理的平衡。

使用afl-cmin，可以对输入或输出语料库进行稍微复杂但速度慢得多的精简。该工具永久地丢弃冗余条目，并生成一个适合与afl-fuzz或外部工具一起使用地较小的语料库。

5.修剪输入文件

文件大小对模糊性能有显著的影响，这是因为大文件会使目标二进制文件变慢，而且它们降低了突变接触重要格式控制结构的可能性。

除了用户可能会提供低质量的起始语料库外，某些类型的编译可能会产生迭代式地增加生成文件大小的影响，因此扭转这种趋势很重要。

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

afl-fuzz的内置修剪器试图顺序地删除具有可变长度和跨越的数据块；任何不影响跟踪映射的校验和的删除都被提交到磁盘。修剪器的设计不是特别彻底；相反，它试图在精度和花费在进程上的execve()调用数之间取得平衡，选择匹配的块大小和跨越。每个文件的平均增益约为5-20%。

独立的afl-tmin工具使用了更详尽的迭代算法，并尝试对裁剪后的文件执行字母规范化。afl-tmin的操作如下。

首先，工具自动选择操作模式。如果初始输入使目标二进制程序崩溃，afl-tmin将在非插桩模式下运行，只需保持任何产生更简单文件的调整，但仍然使目标程序崩溃。如果目标是非崩溃的，工具使用插桩模式，只保留产生完全相同的执行路径的调整。

实际的最小化算法为：

1） 尝试对大的数据块进行零转换。从经验上看，这可以通过在以后抢占更细粒度的工作来减少执行人员的数量。

2）以二进制搜索的方式，通过减少块大小和步进来执行块删除过程。

3）通过计数唯一的字符并尝试用零值批量替换每个字符来执行字母规范化。

4）最后，在非零字节上执行逐字节规格化。

afl-tmin不适用0x00字节进行归零，而是使用ASCII数字‘0’.这样做是因为这样的修改不太可能干扰文本解析，所以更有可能成功地最小化文本文件。

这里使用的算法比学术工作中提出的其他一些测试用例最小化方法涉及的少，但需要执行的次数少得多，并且往往在大多数真实应用程序中产生可比较的结果。

6.fuzzing策略

该工具提供的反馈使人们更容易理解各种模糊策略的价值，并优化它们的参数，以便它们在广泛的文件类型中同样良好地工作。afl-fuzz使用地策略通常使与格式无关的，这里将进行更详细的讨论。

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

-具有不同长度和跨越的顺序位翻转

-小整数的序列加减

-顺序插入已知的感兴趣的整数(0,1,INT_MAX,etc)

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

随着确定性模糊的消失，非确定性步骤包括堆叠位翻转、插入、删除、算术和不同测试用例的拼接。

所有这些策略的相对收益和执行成本已经在前面提到的博客文章中进行了调查和讨论。

由于historical_notes.txt中谈论的原因（主要是性能、简单性和可靠性），AFL通常不会试图推理特定突变和程序状态之间的关系；模糊步骤在名义上是盲目的，并且仅由输入队列的进化设计来引导。

也就是说，这条规则有一个（微不足道的）例外：当一个新的队列条目经过确定性fuzz的初始步骤，并调整一些地区在文件的校验和观察到没有影响执行路径，他们可能被排除在确定性的剩余阶段，fuzzer可能直奔随机调整。特别是对于冗长的、人类可读的数据格式，这可以减少10%-40%左右的执行次数，而不会显著降低覆盖率。在极端情况下，例如生成的块对其tar压缩文件，增益可以高达90%。

因为底层的”效应器映射“对每个队列条目都是本地的，并且只在不改变底层文件的大小或总体布局的确定性阶段有效，所以这种机制看起来工作得非常可靠，而且被证明是很容易实现的。

7.字典

该工具提供的反馈使自动识别某些类型的输入文件中的语法标记变得很容易，并且可以检测预定义的或自动检测字典术语的某些组合是否构成测试解析器的有效语法。

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

词典使fuzzer能够快速重建高度冗长和复杂的语言（如JavaScript、SQL或XML）的语法。

有趣的是，AFL检测还允许fuzzer自动隔离输入文件中已经存在的语法标记。它可以通过查找字节的运行，当翻转时，对程序的执行路径产生一致的变化；这暗示了与代码中预定义值的底层原子比较。fuzzer依靠这个信号来构建紧凑的”汽车词典“，然后与其他模糊策略一起使用。

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

对任何有能力的模糊工具来说，消除崩溃的重复是一个更重要的问题。许多幼稚的方法会遇到问题；特别是，如果故障发生在公共库函数（例如，strcmp,strcpy）中，只查看故障地址可能会导致完全不相关的问题聚集在一起；如果可以通过许多不同的、可能是递归的代码路径到达错误，则校验和调用堆栈回溯可能会导致极端的崩溃计数膨胀。

在afl-fuzz中实现的解决方案认为，如果满足两个条件中的任何一个，则崩溃是唯一的。

-奔溃跟踪包括一个在以前的任何崩溃中都没有看到的元组

-崩溃跟踪缺少在之前的崩溃中始终存在的元组

这种方法在早期很容易受到路径计数膨胀的影响，但表现出很强的自我限制效应，类似于afl-fuzz基本的执行路径分析逻辑。

9.调查崩溃

许多类型崩溃的可利用性可能是模棱两可的，afl-fuzz试图通过提供一个崩溃探索模式来解决这个问题，在这个模式中，已知的故障测试用例以一种非常类似于fuzzer的正常的操作的方式被模糊，但是有一个约束会导致任何非崩溃突变被丢弃。

该方法使用插桩返回来探索崩溃程序的状态，以克服模糊的故障条件，然后将新发现的输入分离出来供人审查。

关于崩溃的主体，值得注意的是，与正常的队列条目相比，崩溃的输入是”没有“修剪的；他们被完全保留在发现的位置，以便更容易将他们与父队列中的非崩溃入口及逆行比较。也就是说，afl-tmin可以用来随意缩小它们。

10. The fork server

为了提高性能，afl-fuzz使用了一个"fork服务器"，其中模糊进程只经过execve()、链接和libc初始化一次，然后利用写时复制从停止的进程映像中克隆。这里更详细地描述了实现。

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

fork服务器是注入的检测的一个重要方面，它知识在第一个检测函数处停止，等待afl-fuzz的命令。

对于快速目标，分叉服务器可以提供相当大的性能提升，通常在1.5倍到2倍之间，这也是可能的。

-在手动（”延迟“）模式下使用fork服务器，跳过较大的、用户选择的初始化代码块。它需要对目标程序进行非常温和的代码更改，有些目标可以产生10倍以上的性能增益。

-启用”持久“模式，其中单个进程用于尝试多个输入，极大地限制了重复fork()调用的开销。这通常需要对目标程序进行一些代码更改，但可以将快速目标的性能提高5倍或更多——近似于进程内模糊的好处，同时仍然保持fuzzer进程和目标二进制之间非常健壮的隔离。

11.平行化

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

这为fuzzer设置了极大的灵活性，包括针对同一种通用数据格式的不同解析器运行同步实例，通常具有协同效果。

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;

  }

第二行中基于移位和xor的置乱用于掩盖指令对齐的效果。

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

第一次翻译一个新的基本块也会引起大量的延迟。为了消除这个问题，AFL fork server通过在正在运行的模拟器和父进程之间提供一个通道进行了扩展。该通道用于将新遇到的块的地址通知父进程，并将它们添加到将为将来的子进程复制的转换缓存中。

这两个优化的结果是，QEMU模式的开销大约是2-5倍，而PIN模式的开销是100倍以上。