【译】AFL白皮书

[toc]

AFL 翻译

afl-fuzz 技术 白皮书

本文档快速概述了American Fuzzy Lop的核心内容。

请参阅README获取一般指导手册；有关AFL背后动机和设计目标的讨论，请参阅historical_notes.txt。

historical_notes: 这篇文档主要谈论了AFL（American Fuzzy Lop）的设计理念和灵感来源，以及与其他fuzzing工具的比较。作者认为，AFL的设计目标是解决其他工具无法解决的问题，包括速度、可靠性、简单性和可链接性。他们采用了一些小而相互补充的方法来实现这些目标，其中包括使用gcov块覆盖率选择最佳测试用例，使用进化算法进行fuzz，通过精心修剪语料库或跳过不可修剪但非功能性的输入文件区域等。此外，AFL还可以处理资源密集型或交互式工具，使用户能够使用更轻量级的目标创建有趣的测试用例。总之，AFL旨在发现有趣的漏洞，并且在这方面表现出色。

0. 设计说明(Design statement)

American Fuzzy Lop（AFL）致力于不局限于任何单一的操作原则(singular principle of operation)，也不仅仅是为了证明某个特定理论。这款工具更像是一套在实际操作中经过测试、效果出乎意料的优秀技巧的组合，而且这些技巧是我当时能想到的最简单、最可靠的实现方式。

这些特性的诞生很大程度上得益于轻量级的插桩技术instrumentation 支持，这为AFL的发展提供了坚实的基础。但我们应该把这些技术看作是达到目的的手段，而非终极目标。AFL真正遵循的核心原则是速度、可靠性和易用性(ease(缓解) of use)。

1. 覆盖率检测(Coverage measurements)

注入到编译后程序中的插桩技术可以捕捉分支（即代码执行的不同路径）的覆盖情况，并粗略统计每个分支的执行次数。这种技术在分支点注入的代码本质上相当于以下内容：

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

这里的 cur_location 值是在编译时随机生成的，目的是简化复杂项目链接过程，并确保 XOR（异或）操作的输出能均匀分布。

shared_mem[] 数组是一个 64 KB 的共享内存（SHM）区域，由调用程序传递给被插桩的二进制文件。输出映射中的每一个字节都可以被看作是被插桩代码中特定的[branch_src, branch_dst]元组的一个命中(hit)。

通过选择映射(map)的大小，使得它在几乎所有预定目标中的碰撞都相对较少，这些目标代码的分支数大多在2k到10k之间

同时，它的大小足够小，可以在几微秒内分析映射，并毫不费力地放入二级缓存L2中。

与简单的块覆盖相比，这种形式的覆盖提供了更多程序执行路径的信息(insight)。并且，它可以简单地区分以下执行路径(trace)：

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

What is the difference between block coverage and branch coverage?

大写字母代表程序基本块之间的边，每一条边都有一个随机化的ID（即cur_location），值分别为A-E，所以

B->C->D 路径表现为 shared_mem[(B >> 1) ^ C]++ shared_mem[(C >> 1) ^ D]++

B->D->C 路径表现为 shared_mem[(B >> 1) ^ D]++ shared_mem[(D >> 1) ^ C]++

显然是可以区分的。但是块覆盖只会记录 B,C,D 块均命中，却无法区分。

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

前面所示的伪代码的最后一行中进行移位操作是为了保持元组的方向性（如果没有这个，A ^ B 将与 B ^ A 无法区分）并且可以区分不同的紧密循环(tight loops)（否则 , A ^ A 显然等于 B ^ B)。

如果不移位: 对于路径 A->B 与 B->A 表现均为 shared_mem[A ^ B]++ ，无法区分 对于环形路径 A->A 与 B->B 表现均为 shared_mem[0]++，无法区分

由于 Intel CPU 上缺乏简单的饱和运算指令(saturating arithmetic opcodes)，意味着命中计数器有时可能会回绕至零。尽管这种情况相对罕见且局限性较强，但它被视为一个可以接受的性能折中方案(trade-off)。

通俗来讲，饱和运算就是具有上下界的算数指令，比如一个规定算数范围为-100~100的饱和算数指令中，(40+80)-(50+60)=100-100=0（而不是10）

Intel 没有使用饱和算数指令，而使用modular arithmetic. 导致最大值的溢出会向最小值保留，比如最常见的正溢出与负溢出

2. 新路径检测(Detecting new behaviors)

Fuzzer 全程维护这个全局的元组map shared_mem[]；这些数据能在各自的路径中被快速对比，并仅需几个dword或qword宽度的指令和一个简单的循环即可更新。

当变异(mutated)的输入产生包含新元组的执行路径时，相应的输入文件将被保留并路由以供稍后进行额外处理（第三部分介绍）。 在执行路径中不触发新的局部状态转换的输入（即不产生新的元组）将被丢弃，即使它们产生了新的全局控制流。

这种方法允许对程序状态进行非常细粒度(fine-grained)和长期的探索，同时不必对复杂的执行路径执行任何复杂计算和不可靠的的全局比较，同时也能防止搜寻过程中的路径爆炸(path explosion)。

为了展示这种算法的特点，我们可以考虑以下情况：第二个执行轨迹因为包含了新的元组（CA, AE）而被认为是一个显著的新路径：

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

同时 #2 产生后，#3 就不再认为是有意义的了，尽管以下模式的全局路径截然不同，它还是不会被视为独特的：

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

除了检测新元组外，Fuzzer 还粗略考虑元组命中数。 被分为以下几个桶(buckets)：

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

在某种程度上，桶 buckets 的数量是是实现过程中的一个特点，它允许把插桩技术生成的 8-bit计数器直接映射到模糊测试器执行文件所依赖的一个8-position位置的位图上。这个位图用于跟踪每个元组已经出现的执行次数。前者由插桩产生，后者由 AFL 运行时路径已出现的元组数来计数。

在如果变化仅发生在单个桶的范围内，则会被忽略；但如果从一个桶到另一个桶，则这种转变会被标记为程序控制流中的一个有趣的变化。也会指导下一阶段的进化过程 evolutionary process .(见下一章)

命中计数行为提供了一种区分潜在有趣的控制流变化的方法，比如一个通常只执行一次的代码块突然执行了两次。同时，它对经验上不太显著的变化（例如循环从47个周期变成48个周期）相当不敏感。计数器还在某种程度上“意外地”防止了在密集的执行路径中元组碰撞的发生。

执行过程受到内存和执行时间限制的限制；默认情况下，超时时间设置为初始化标准执行速度对应时间的5倍，大概 20 ms。这些激进的超时时间旨在防止模糊测试器陷入陷阱中而导致性能严重下降，例如，为了提高 1% 的覆盖率却导致速度慢了 100 倍；我们从实用角度出发，拒绝这种情况，并希望 fuzzer 可以找到一个更轻松的方式来遍历相同数量的代码。经验测试，更宽松的时间限制不值得。

3. 输入队列变异(Evolving the input queue)

产生了新的程序状态转换的变异测试用例会被添加到输入队列中，并用作新一轮次 fuzzing 的起点。这些用例是已有测试用例的补充，但并不替换掉已有测试用例。

与更贪心的遗传算法相比，这种方法允许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

pulling-jpegs-out-of-thin-air: 本文介绍了afl-fuzz工具的一个有趣的应用场景。作者创建了一个只包含"hello"字符串的文本文件，并将其作为输入交给了一个期望接收JPEG图像的程序。由于该输入文件与有效的图片格式不符，因此该程序会立即拒绝该输入。然而，afl-fuzz可以利用轻量级汇编级别的插装技术，发现将第一个字节设置为0xff触发了被测试应用程序中略微不同的内部代码路径。afl-fuzz将这个测试用例作为下一轮fuzzing的种子。在几百个代和数亿次execve()调用后，afl-fuzz逐渐发现了构成有效JPEG文件的基本控制结构。最终，它成功地合成了一个有效的JPEG图像。作者指出，这种方法不仅可以用于合成JPEG图像，还可以用于压力测试其他类型的解析器。本文还讨论了afl-fuzz工具的局限性，即当目标二进制文件中存在具有大搜索空间的原子执行检查时，可能会对fuzzer造成难以克服的障碍。

afl-fuzz-nobody-expects-cdata-sections: 本文主要介绍了AFL-fuzz的一个实验结果，即通过随机变异输入文件和轻微调整进程状态来发现程序中的新状态转换。作者最初认为这种方法只能使fuzzer比土豆更聪明一些，但后来发现它可以成功地合成JPEG文件。文章还讨论了AFL-fuzz在探索人类可读格式（如HTML或JavaScript）时的局限性，并介绍了一些解决方案。最后，作者提到了AFL-fuzz在测试libxml2时的惊人表现，尽管这与其设计意图有所违背。

本文介绍了AFL-fuzz在测试XML解析器libxml2时的一个惊人发现。作者最初只是想测试该解析器的基本功能，但在两天内，AFL-fuzz生成了一个包含特殊CDATA部分的XML文件，这个部分很难通过随机变异来发现。作者认为这可能是因为AFL-fuzz在编译插桩二进制文件时使用了-O3 -funroll-loops参数，或者是因为libxml2中的一些字符串比较操作使用了类似的代码结构。作者表示，这个结果让他感到有点神秘，因为它违反了AFL-fuzz的设计限制之一。作者还提到，尽管AFL-fuzz能够发现某些高度冗长的文本语法，但在其他情况下，使用简单的语法感知、基于模板的工具可能更加有效。

这个过程产生的合成语料库本质上是一个“嗯，有新东西！”的输入集合，可以作为后续任何其他测试流程的种子（例如，手动对资源密集型桌面应用程序进行压力测试）。

根据这种方法，对于大多数目标程序，队列的大小通常会增长到1k到10k条记录之间。其中约有10-30%的增长是由于发现新元组，其余的增长则与命中计数的变化有关。这意味着，通过使用元组策略，AFL能够更加高效地生成测试用例，并且能够更快地探索目标程序的不同执行路径。

以下表格比较了在使用几种指导 fuzzing 的方法时，发现文件语义（file syntax）和探索程序状态的相对能力。每种策略下的测试结果都包括块（Blocks）覆盖率、边（Edges）覆盖率、命中最多的边计数变量（Edge hit cnt var）以及在达到最高覆盖率时生成的测试用例。测试使用的目标是GNU patch 2.7.3，编译选项为-O3，并使用一个虚拟文本文件作为种子进行测试。测试过程中使用了afl-fuzz进行单次输入队列遍历。

在这个测试中，使用了以下几种引导策略：

• 初始文件（Initial file）：使用虚拟文本文件作为种子，随机生成测试用例。
• 盲目fuzzing S（Blind fuzzing S）：随机生成测试用例，并在测试用例中添加一些特定的字节序列，以探索程序的不同执行路径。
• 盲目fuzzing L（Blind fuzzing L）：与盲目fuzzing S类似，但添加的字节序列更长。
• 块覆盖率（Block coverage）：使用AFL的块覆盖率引导策略，生成测试用例以尽可能覆盖目标程序的基本块。
• 边覆盖率（Edge coverage）：使用AFL的边覆盖率引导策略，生成测试用例以尽可能覆盖目标程序的基本边。
• AFL模型（AFL model）：使用AFL的深度学习模型进行引导，生成测试用例以尽可能覆盖目标程序的执行路径。

块覆盖率，边覆盖率，边命中率，最高覆盖率下生成的测试用例

盲fuzzing的第一个条目（“S”）代表仅执行了一轮测试；第二组条目（“L”）展示了fuzzer在循环中运行了与插桩测试相当的执行周期数，这需要更多的时间来完全处理不断增长的队列。

Blind fuzzing 为盲变异，有 S 与 L 两种方式，均相当于对照组 execution cycles 就是字面意思，即计算机体系结构中取指、译码、执行中的执行周期。 instrumented runs 可以翻译成插桩运行，也可以认为是有指导、有反馈地运行，指代的就是后续 Block, Edge coverage, AFL model 这些有指导的、不盲的 fuzzing. 保持 Blind fuzzing 与后续 instrumented runs 的循环执行周期数大致相近，才有比较的意义。 插桩运行时队列生长的速度慢，因为需要反复分析；盲 fuzzing 弄出一个测试用例队列是最快的，但能不能有效就不一定了。

在另一个单独的实验中，获得了大致相似的结果。该测试中，研究人员对fuzzer进行了修改，在这里让 fuzzer 在编译时去掉所有的随机 fuzzing 阶段，仅保留一系列基本的、顺序的操作，如遍历位翻转。由于这种模式不能改变输入文件的大小，因此实验使用了一个有效的、统一的 diff 输出作为种子：

正如之前提到的，一些关于遗传算法fuzzing的早期工作依赖于维护单一测试用例并不断变异它以最大化覆盖率。至少在上述测试中，这种“贪婪”的方法似乎并没有比盲fuzzing策略带来供显著的优势。换句话说，这段文字表明在进行fuzzing测试时，使用单个测试用例并不一定比使用其他策略更有效。

4. 精简语料库(Culling the corpus)

上述列出的渐进式状态探索方法意味着，在进行fuzzing测试时，后期生成的一些测试用例的边覆盖可能会比它们的“祖先”用例提供的覆盖更加全面。

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

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

“算法性能优化”（algorithmic performance tuning）策略。这个策略是AFL用来探索程序状态和语法的一种方式。在这个策略中，AFL会先把所有的输入文件进行元组化操作，将它们转换成一个个元组，然后按照一定的顺序逐个进行处理。处理的过程包括以下几个步骤：

接下来，这些元组会按照以下简单的工作流程依次处理：

1. 找到下一个还没有在临时工作集中出现的元组；
2. 定位到这个元组对应的最佳队列条目（winning queue entry）；
3. 将此元素产生的路径上出现的所有元组加入当前工作集
4. 如果工作集中还有缺失的元组，则回到第1步继续查找。

这个过程会不断循环，直到所有的元组都被处理完毕。

在这个过程中，AFL会生成一个“受青睐”的输入文件集合，这些文件集合通常比起始数据集小5-10倍。非“受青睐”的输入文件不会被丢弃，但当它们在队列中遇到时，会以不同的概率被跳过：

• 如果队列中有新的、尚未进行fuzzing的“受青睐”文件，则99%的非“受青睐”文件将被跳过，以便处理“受青睐”文件。

• 如果队列中没有新的“受青睐”文件：

  • 如果当前的非“受青睐”文件已经进行过fuzzing，它将有 95% 的概率被跳过。

  • 如果该文件还没有进行任何fuzzing，则跳过的概率下降到75%。

通过这种方式，会更频繁地处理“受青睐”的文件，而不是浪费时间处理那些已经被处理过的或者不太可能产生漏洞的文件。

根据实证测试结果，这种方法在队列循环速度(queue cycling speed)和测试用例多样性(test case diversity)之间实现了合理的平衡。

可以使用 afl-cmin 对输入或输出的测试集进行更精细但速度较慢的筛选。这个工具会永久性地去除多余的条目，并生成一个更小的语料库，适用于 afl-fuzz 或其他外部工具。

5. 修剪输入文件(Trimming input files)

文件大小对fuzzing的性能有重大影响，原因有两个，一是大文件使目标二进制文件运行变慢，二是它们降低了变异触及关键的格式控制结构而非冗余数据块的概率，从而降低测试的效率。这在perf_tips.txt中有更详细的讨论。

抛开用户可能提供低质量起始语料库的可能性不谈，某些类型的变异可能逐渐增加生成文件的大小，因此阻止这种趋势很重要。

幸运的是，插桩技术提供了一种简单的方法，可以自动裁剪输入文件，同时确保这些更改不会影响执行路径。

“instrumentation feedback”技术可以帮助AFL自动修剪输入文件，以提高fuzzing测试的效率和质量。AFL在执行fuzzing测试时，通过对程序进行插桩（instrumentation）来获取有关程序执行路径的反馈信息。利用这些反馈信息，AFL可以自动识别输入文件中不必要的部分，并将其删除，从而减小文件大小。同时，由于这些更改不会影响程序的执行路径，因此可以确保测试用例的质量不会受到影响。

AFL中内置的修剪器(trimmer)会尝试按顺序删除具有可变长度和步长的数据块；任何不影响路径图校验和的删除操作都将被提交到磁盘。这个减枝器并没有设计地非常准确详尽；相反，它试图在精度和执行 execve() 调用次数之间寻求平衡。平均每个文件的优化效果大约在 5-20% 左右。

与内置的修剪器不同，afl-tmin使用更为彻底、迭代的算法，并尝试对修剪后的文件进行字符标准化(alphabet normalization)。afl-tmin的操作如下所述：

首先，AFL会自动选择操作模式。如果初始输入会导致目标二进制文件崩溃，afl-tmin 将以非插桩模式运行，不断尝试去调整输入让它变得更简单的同时仍然可以导致目标程序崩溃；如果目标没有崩溃，该工具使用插桩模式，只保留那些能产生完全相同执行路径的调整。

最小化的算法包括以下步骤：

1. 尝试用大步长将大块数据置零。经验证，这将会为后续更细粒度的工作铺路从而降低 execve 调用。

2. 以二分搜索的方式进行块删除，逐渐减小块的大小和步长。

3. 通过计算字符数量并尝试批量将每个字符替换为零值来进行字母表规范化。

4. 最后，在非零字节上执行逐字节标准化。

afl-tmin 使用 ASCII 数字 ‘0’ 替换零值，而不是使用 0x00 字节。这么做的原因是这种修改对文本解析的干扰较小，因此更有可能成功地最小化文本文件。

这里使用的算法虽然不如学术研究中提出的一些其他测试用例最小化方法那样复杂，但它需要的执行次数更少，在大多数实际应用中能产生与其相媲美的结果。

6. 模糊测试策略(Fuzzing strategies)

插桩技术提供的反馈让我们能更容易理解各种fuzzing策略的价值，并优化它们的参数，以确保这些策略在各种不同的文件类型上都能同样有效。afl-fuzz 使用的策略通常是格式无关的(format-agnostic)，在以下链接中有更详细的讨论：

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

这篇文章讨论了二进制fuzzing的策略，以及它们的有效性和限制。文章提到，成功的fuzzer取决于它们的fuzzing策略。如果对输入文件做出的更改过于保守，fuzzer将实现非常有限的覆盖率。如果调整过于激进，则会导致大多数输入在非常早期的阶段失败解析，浪费CPU周期并产生难以调查和排除故障的混乱测试用例。

文章介绍了AFL（American Fuzzy Lop）的设计，该设计提供了一种罕见的反馈循环：您可以仔细测量哪些类型的更改实际上导致代码中新分支的发现。AFL通过一系列逐渐复杂但详尽和确定性的fuzzing策略（例如顺序位翻转和简单算术）来接近每个新输入文件，然后再进入纯随机行为。这样做的原因是先生成最简单和最优雅的测试用例；但是，该设计还提供了一种非常好的方法来量化每种新策略带来的价值 - 以及我们是否需要它。

文章提到了几种具体的fuzzing策略，包括Walking bit flips、Walking byte flips、Simple arithmetics、Known integers、Stacked tweaks和Test case splicing。每种策略都有其独特的优点和缺点，并且效果因格式而异。例如，Walking bit flips是最基本的策略之一，可以发现大约70个新路径，但成本相对较高，每个输入文件的每个字节需要八个execve()调用。另一方面，Simple arithmetics可以以相对较低的成本发现更复杂的条件，但成本仍然相对较高，每个输入文件的每个字节需要约20个execve()调用。

总之，文章提供了有关二进制fuzzing策略的详细信息，以及这些策略的有效性和限制。这对于正在开发自己的fuzzer的人们来说可能会很有用。

特别是在早期阶段，afl-fuzz大部分工作都是高度确定性的，随机堆叠（stacked tweaks）的修改和测试用例的拼接（test case splicing）只在后期才会进行。这些确定性策略包括：

• 顺序位翻转，有不同的长度和步长
• 顺序小整数加减
• 顺序插入特殊整数（0、1、INT_MAX等）

采用确定性步骤的初衷与它们产生紧凑的测试用例和在非崩溃输入与崩溃输入之间保持小差异的倾向相关。

在确定性fuzzing完成后，AFL会使用非确定性策略，包括堆叠位翻转、插入、删除、算术运算和不同测试用例的拼接。这些策略的相对收益和execve()成本在上述博客文章中进行了讨论。

由于 historical_notes.txt 文档中讨论的原因（主要包括性能、简单性和可靠性），AFL 通常不尝试推断特定变异与程序状态之间的关系；这些 fuzzing 步骤只是名义上的盲（随机），它们会也只会受输入队列指导。

即便如此，这套规则也有一个（不太重要的）例外：当一个新的队列条目经过初始的确定性fuzzing步骤时，如果观察到对文件中某些区域的调整对执行路径的校验和没有影响，那么它们可以被排除在确定性fuzzing的其余阶段之外，fuzzer可以直接进行随机调整。特别是对于冗长的、可读性高的数据格式，这可以将执行次数降低10-40%，而覆盖率几乎没有下降。在极端情况下，例如通常块对齐的tar档案，收益可能高达90%。

AFL中的一种优化技巧，即"修剪输入文件和控制文件大小"。 具体来说，AFL使用一种称为"effector maps"的机制来记录测试过程中每个输入文件的状态和效果，并根据这些信息来决定下一步的操作。这些"effector maps"是本地的，即每个队列条目都有自己的"effector maps"，并且只在不改变底层文件大小或布局的确定性阶段保持有效。通过这种机制，AFL能够高效、可靠地进行fuzzing测试，并且这种机制的实现也相对简单。

7. 字典构建(Dictionaries)

AFL使用插桩技术来获取程序执行时的反馈信息，并根据这些信息自动识别输入文件中的语法token。这使得AFL能够检测到预定义或自动检测到的字典的某些组合是否构成了被测试解析器的有效语法。通过这种方式，AFL能够更加智能地生成测试用例，并且能够更好地探索程序状态空间。

这里讨论了 afl-fuzz 是如何实现语法检测的:

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

这段内容主要讲述了AFL-fuzz在处理语法复杂的数据格式时存在的局限性，以及一种通过构建基本语法单元列表来改善AFL-fuzz对这些格式的测试能力的方法。作者提出了一个简单的算法，该算法可以通过检测连续的比特翻转触发与邻近区域不同但整个字节序列中一致的执行路径来识别语法单元，并将其添加到字典中以供后续随机组合。这种方法虽然不能替代手工构建的关键字列表，但可以帮助那些没有时间或倾向于构建完整字典的人们。

AFL通过将基本的、容易获取的语法token以纯随机方式组合在一起，利用插桩技术和进化设计队列提供反馈机制，以区分无意义的变异和触发仪器代码中新行为的变异，并逐步在这个发现的基础上构建更复杂的语法。

换句话说，AFL使用随机测试数据来探索程序状态，从而找到新的测试路径和漏洞。同时，AFL还利用进化算法对测试数据进行优化，以获得更好的测试效果。

字典可以帮助fuzzer快速重构高度冗长和复杂的语言的语法，例如JavaScript、SQL或XML。上面提到的博客文章中给出了生成的几个SQL语句的示例。字典是一种用于指导fuzzer生成有效测试数据的技术，它可以包含一些预定义的语法标记或关键词，以帮助fuzzer更好地理解程序语法结构，并生成更有意义的测试数据。在AFL中，字典被用于扩展随机测试数据的范围，以便发现更多的测试路径和漏洞。

有趣的是，AFL的插桩技术还允许fuzzer自动隔离已经存在于输入文件中的语法token。它在通过在翻转比特时定位对程序执行路径产生一致性改变的位置来实现；这表明代码中内置了与预定义值的原子比较。fuzzer依赖于这个信号来构建紧凑的"自动字典"，然后与其他fuzzing策略一起使用。

8. 崩溃去重(De-duping crashes)

崩溃去重是一个合格的fuzzing工具中更为重要的问题之一。许多朴素的方法都会遇到问题；特别是，仅查看故障地址可能会导致完全不相关的问题被聚集在一起，如果故障发生在常见的库函数（例如strcmp、strcpy）中，则会出现这种情况；而对调用栈回溯进行校验和可能会导致崩溃计数极度膨胀，如果故障可以通过许多不同的、可能是递归的代码路径到达。

afl-fuzz实现的解决方案认为，如果满足以下两个条件之一，崩溃就是唯一的：

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

这种方法在早期可能会存在一些路径数量膨胀的问题，但它展示了非常强的自我限制(self-limiting)效果，类似于afl-这种去重方式与执行路径分析的逻辑一起构成了 afl-fuzz 的基石。

9. 崩溃调查(Investigating crashes)

许多类型的崩溃漏洞的可利用性是模糊不清的；afl-fuzz 试图通过提供一个崩溃探索模式(crash exploration mode)来解决这个问题，在这种模式下，一个已知存在漏洞的测试用例会被以与fuzzer正常操作非常相似的方式进行fuzzing，但有一个约束条件，即任何非崩溃的变异都将被丢弃。

很多类型的崩溃的可利用性 exploitability 是难以界定的；afl-fuzz 会尝试使用崩溃调查模式 crash exploration mode 来解决这一问题：规则与正常操作模式类似，但变异过后不崩溃的测试用例会被直接丢弃。

这种解决方法的价值在这篇文章中详细探讨:

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

该文介绍了AFL-fuzz的新功能——崩溃探索模式。在进行fuzzing测试时，发现崩溃问题后需要花费大量时间来确定是否存在安全风险。而使用崩溃探索模式可以很快地生成一组相关但略有不同的崩溃，以便更准确地估计您对故障地址的控制程度，或者找出是否可以通过适当的方式解决越界读取等问题。这项新功能可以使您更加精准地判断崩溃问题是否具有安全风险，而无需花费大量时间进行手动调试。

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

对于崩溃来说，与通常的队列元素相反，将崩溃的输入进行减枝是毫无意义的。它们被发现之后就会原封不动的保存，以便将它们与父（未崩溃）元素进行对比分析。也就是说，是否用 afl-tmin 去剪枝都行

10. fork服务器(The fork server)

为了提高性能，afl-fuzz使用了一个"fork server"，其中fuzzing过程中只需经过一次execve()、链接和libc初始化，然后通过利用写时复制(copy-on-write)从停止的进程映像中复制、clone。该实现在这里有更详细的描述：

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

该篇文章介绍了在没有execve()的情况下对随机程序进行fuzzing的方法。该方法主要是通过找到一个简单的二进制文件来测试数据解析库的有趣功能，并使用稍微不同的、随机变异的输入在每次运行中执行它。这种方法的优点是可以消除深入文档、理解底层库提供的API并编写自定义代码来测试解析器的需要，同时使模糊测试过程重复和强大。然而，由于特别是对于简单的库，你可能会花费大部分时间等待execve()、链接器和所有库初始化例程完成它们的工作。为了解决这个问题，作者想出了一些方法，例如编写自定义ELF加载器并在使用mprotect()暂时锁定fuzzer本身使用的内存的同时在进程中执行程序，但是这些方法都比较复杂。最终，作者采用了Jann Horn提出的方法，将小型代码注入到被测二进制文件中，以便让execve()发生并在实际程序中提前停止，然后在子进程中使用copy-on-write创建与已加载程序相同的克隆，从而实现了快速、可靠的模糊测试。该方法可以加快许多常见图像库的模糊测试速度。

fork server是插桩的一个重要组成部分，它只是在第一个被插桩的函数处停止，等待来自afl-fuzz的命令。

在处理快速目标时，使用fork server可以提供相当大的性能提升，通常在1.5倍到2倍之间。除此之外，还有两种模式可以使用：

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

• 启用“持久化”(persistent mode)模式，其中一个进程用于尝试多个输入，大大减少了重复fork()调用的开销。这通常需要对目标程序进行一些代码更改，但可以将快速目标的性能提高5倍或更多，

  • 近似于进程内fuzzing作业的好处，同时仍然保持非常强大的隔离性，使得fuzzer进程和目标二进制文件之间的隔离非常可靠。

11. 并行处理(Parallelization)

并行机制依赖于定期检查由独立运行的其他CPU核心或远程机器产生的队列，并有选择地拉取在本地尝试时产生尚未被该fuzzer看到的行为的测试用例。

这种方法极大地提高了fuzzer设置的灵活性，包括对共同数据格式的不同解析器运行同步实例。此外，如果想了解更多关于这种设计的信息，请参阅parallel_fuzzing.txt。

12. 二进制插桩(Binary-only instrumentation)

AFL使用一个在“用户”模式下单独构建的QEMU版本来完成。这也允许执行跨架构代码，例如在x86上运行ARM二进制文件。

QEMU将基本块作为翻译单元，插桩是在此之上实现的，并使用大致类似于编译时Hook的模型。

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;
}

这段代码检查基本块地址是否在ELF文件的文本段（.text）中，如果是，则将当前位置和前一个位置异或后存储在共享内存中，并将当前位置右移一位作为前一个位置。这样可以记录程序执行路径并用于AFL的fuzzing测试。

第二行中的移位异或混淆（shift-and-XOR-based scrambling）。这种混淆是为了掩盖指令对齐的影响，因为指令对齐可能会导致基本块地址的低位不同。

此外，由于像QEMU、DynamoRIO和PIN等二进制翻译器的启动速度比较慢，为了解决这个问题，QEMU模式利用了类似于编译器插桩代码使用的fork server。它会在一个已经初始化并暂停在 _start 处的进程中生成多个副本，从而加快启动速度。

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

由于这两个优化，QEMU模式的开销大约是白盒的2-5倍，而PIN的开销超过100倍。

13. AFL分析工具(The afl-analyze tool)

文件格式分析器 file format analyzer 是前面讨论的最小化算法的简单扩展；该工具不是试图删除无操作块，而是对输入文件执行一系列的字节翻转，后给输入文件执行的各个字节做注解与分类。

它的分类策略如下：

它使用以下分类方案：

• 无操作块(No-op blocks):

  • 位翻转不会对控制流产生明显变化的段。
  • 常见的例子可能是注释部分、位图文件中的像素数据等。

• 表面内容(Superficial content)

  • 段落中有些但不是全部位翻转会导致一些控制流的变化。
  • 例如，富文本文档中的字符串（如XML、RTF）。

• 关键流(Critical stream)

  • 一系列字节，其中所有位翻转以不同但相关的方式改变控制流。
  • 这可能是压缩数据、非原子比较的关键字或魔数等。

• 疑似长度字段(Suspected length field)

  • 小的、原子整数，在任何情况下都会引起一致的程序控制流变化
  • 这往往预示着长度检测的错误。

• 疑似校验和或魔法整数(Suspected cksum or magic int)

  • 一个整数，行为类似于长度字段，但其数值使得长度解释不太可能。
  • 预示这是一个校验和或其他魔数。

• 疑似校验和块(Suspected checksummed block)

  • 一个长的数据块，任何更改总是触发相同的新执行路径。
  • 可能是在任何后续解析之前未通过校验和或类似完整性检查而导致的。

• 魔数字段(Magic value section)

  • 一种通用的标记，更改会导致前面概述的二进制行为类型，但不符合其他任何条件。
  • 可能是一个原子比较的关键字或其他东西。

TODO

• link
• https://blog.csdn.net/weixin_42110652/article/details/122093156

ref:

https://lcamtuf.coredump.cx/afl/technical_details.txt

afl设计目标和动机的讨论地址: http://lcamtuf.coredump.cx/afl/historical_notes.txt https://xidoo.top/2022/01/afl-white-book/ https://www.jianshu.com/p/cc7a486e5adb https://dowob.cn/2020/02/13/afl%E7%99%BD%E7%9A%AE%E4%B9%A6/ https://www.cnblogs.com/0xHack/p/9407640.html https://zhuanlan.zhihu.com/p/529960677 https://blog.csdn.net/weixin_42110652/article/details/122093156

附: AFL设计目标和动机的讨论(historical notes)

1. 影响

简而言之，afl-fuzz的灵感主要来自于Tavis Ormandy在2007年所做的工作。Tavis使用gcov块覆盖率从大量数据中选择最佳的测试用例，并将它们作为传统模糊测试工作流的起点，做了一些非常有说服力的实验。

（所谓“有说服力”，是指：获得了大量有趣的漏洞。）

与此同时，Tavis和我都对进化模糊测试很感兴趣。Tavis有他的实验，我则在2007年左右编写了一个名为bunny-the-fuzzer的工具。

Bunny使用了一种与afl-fuzz并没有太大区别的生成算法，但还试图推理各种输入位与程序内部状态之间的关系，希望从中得到一些额外的价值。这种推理/相关性部分可能在某种程度上受到了Will Drewry和Chris Evans等人在同一时间完成的其他项目的启发。

状态相关方法(state correlation approach)在论文中听起来非常诱人，但最终使模糊器变得复杂、脆弱且难以使用；每个目标程序都需要进行一两次调整。因为Bunny的表现并不比不那么复杂的暴力工具好多少，我最终决定放弃它。你仍然可以在以下网址找到它的原始文档：

https://code.google.com/p/bunny-the-fuzzer/wiki/BunnyDoc

也有一些独立的工作。最值得注意的是，那一年早些时候，Jared DeMott在Defcon上做了一个关于基于覆盖率的模糊测试的演讲，该模糊测试依赖于覆盖率作为适应度函数(fitness function)。

Jared的方法与afl-fuzz所做的并不完全相同，但大致相似。他的模糊器试图显式地(explicitly )解决单个输入文件的最大覆盖问题；相比之下，afl仅选择能够做出新事物的情况（这会产生更好的结果-请参见technical_details.txt）。

几年后，Gabriel Campana发布了fuzzgrind，这是一个完全依赖于Valgrind和约束求解器来最大化覆盖率而没有任何暴力位的工具；微软研究人员则广泛讨论了他们仍未公开的基于求解器的SAGE框架。

在过去的六年左右，我还看到了很多学术论文，涉及智能模糊测试（主要关注符号执行）和一些讨论使用遗传算法实现相同目标的概念验证应用程序的论文。我不太相信这些实验的实用性；我怀疑其中许多都遭受了bunny-the-fuzzer的诅咒，在论文和精心设计的实验中很酷，但在其他情况下却无法找到新的、有价值的安全漏洞。

在某些方面，“酷”的解决方案所要竞争的基线比看起来更令人印象深刻，这使得竞争者难以脱颖而出。举个例子，看看Gynvael和Mateusz Jurczyk的工作，将“愚蠢”的模糊测试应用于ffmpeg，现代浏览器和媒体播放器的重要且关键的组件：

http://googleonlinesecurity.blogspot.com/2014/01/ffmpeg-and-thousand-fixes.html

轻松地获得与同样复杂软件中最先进的符号执行相当的结果似乎仍然相当不可能，并且迄今为止还没有在实践中证明过。

但是我偏离了主题；最终，归因很难，赞美AFL背后的基本概念可能是一种浪费时间。魔鬼往往隐藏在常常被忽视的细节中，这就带我们来到了…

2. afl-fuzz的设计目标 简而言之，我认为afl-fuzz的当前实现解决了其他工具似乎无法解决的一些问题：

1）速度。当你的“智能”方法需要大量资源时，很难与暴力破解竞争。如果你的仪器使找到一个漏洞的可能性增加了10倍，但运行速度减慢了100倍，那么你的用户就会受到损失。

为避免从一开始就处于劣势，afl-fuzz旨在让你以大致原生速度模糊测试大多数目标-即使它没有添加价值，你也不会损失太多。

此外，该工具利用仪器在几个方面实际上减少了工作量：例如，通过精心修剪语料库或跳过输入文件中不可修剪但非功能性的部分。

2）坚如磐石的可靠性。如果你的方法脆弱且意外失败，很难与暴力破解竞争。自动化测试很有吸引力，因为它简单易用且可扩展；任何违反这些原则的东西都是一种不受欢迎的权衡，意味着你的工具将被使用得更少，并且结果不太一致。

大多数基于符号执行、污点跟踪或复杂语法感知仪器的方法目前在实际目标中相当不可靠。更重要的是，它们的失败模式可能使它们比“愚蠢”的工具更糟糕，这种退化对于经验不足的用户来说可能很难察觉和纠正。

相比之下，afl-fuzz的设计是坚如磐石的，主要是通过保持简单来实现的。实际上，在其核心，它被设计成一个非常好的传统模糊器，拥有各种有趣的、经过深入研究的策略。花哨的部分只是帮助它将工作集中在最重要的地方。

3）简洁性。测试框架的作者可能是唯一真正了解工具提供的所有设置的人，也是唯一可以精确调整它们的人。然而，即使是最基本的模糊测试框架通常也带有无数个旋钮和模糊比率，需要操作者提前猜测。这可能会造成更多的伤害而不是好处。

AFL旨在尽可能避免这种情况。你可以玩的三个旋钮是输出文件、内存限制和覆盖默认自动校准超时的能力。其余部分只是应该正常工作。当它不起作用时，用户友好的错误消息会概述可能的原因和解决方法，并让你立即回到正轨。

4）可链接性。大多数通用模糊器不能轻松地针对资源占用量大或交互重的工具进行测试，这需要创建定制的进程内模糊器或投入大量CPU功率（其中大部分浪费在与我们实际想要测试的代码无直接关系的任务上）。

AFL试图通过允许用户使用更轻量级的目标（例如，独立的图像解析库）创建一小组有趣的测试用例，这些测试用例可以稍后被馈送到手动测试过程或UI测试中来解决这个问题。

如technical_details.txt所述，AFL并不是通过系统地应用单一的总体CS概念来做到这一点的，而是通过尝试各种小型、互补的方法来实现的，这些方法已经被证明比机会更可靠地产生结果。仪器的使用是这个工具箱的一部分，但远非最重要的部分。

最终，重要的是 afl-fuzz 被设计用来发现酷炫的漏洞 - 并且在这方面具有相当强大的记录。