前言

对于防御者来说，现有的内存损坏和控制流劫持保护措施提供的保护并不
完整。对于软件开发人员来说，手动代码分析无法扩展到大型程序。这些漏洞
可能被恶意攻击者利用，导致数据泄露、系统崩溃，甚至是更严重的安全事
件。
fuzzing 技术，作为一种无需静态分析、动态调试等手段，却能有效识别和
暴露软件程序中的潜在漏洞和安全问题的技术，正广泛应用于安全实践之中。
Fuzzing 技术本身也正在快速迭代，但论真正划时代意义的工具，非 AFL 莫
属。作者虽然没有以论文形式发表该成果，但是通过该项目的技术细节文档，
可以轻松看懂每部分的逻辑。并且，AFL++整合了 AFL 的各类插件，实现兼容
性、性能和变异能力的提升，并改进了遗传算法中变异的自定义方案，方便研
究人员进行二次开发

1 Fuzzing 的历史和发展

为了更好地理解fuzzing技术，首先从最原始的fuzzing流程开始：

简单来说就是，使用某种规则来生成测试用例，然后提供给程序进行执行，观察程序是否
崩溃，如果发生了崩溃，就报告 bugs，否则直接进入下一轮的循环。流程确实是非常简单，但最难的是，怎么去生成能触发漏洞的测试用例呢？这就是形成fuzzing算法之间效果差异的地方，这最核心的部分算法的目的是不断地往触发崩溃的方向去制作出新的测试样例。该部分主要有两种派别，分别采用了变异(代表如afl、afl++)/生成（代表如boofuzz）算法。
Fuzzing 技术的发展可以分为以下几个阶段

1.1 早期（1980s）

1989 年，Barton Miller 等人在《An Empirical Study of the Reliability of UNIX
Utilities》一文中首次提出 Fuzzing 概念，并通过随机输入发现了多个 UNIX
工具的崩溃问题。这一研究揭示了 Fuzzing 作为漏洞检测工具的潜力。

1.2 理论深化与工具开发（1990s）

随着 Fuzzing 概念的传播，研究者们开始深入探讨其理论基础，开发了许多
早期 Fuzzing 工具，如 SPIKE 和 Peach。1998 年，Michael Sutton 等人在
《Fuzzing: Brute Force Vulnerability Discovery》一书中详细探讨了 Fuzzing 的应
用和改进方法。
然而，早期型fuzzing技术采用的盲目随机突变，不太可能达到测试代码中的某些代码路径，从而使一些漏洞完全超出了该技术的范围。

1.3 灰盒 Fuzzing 的兴起（2000s）

后来，人们渐渐发现覆盖率引导模糊测试（Coverage-Guided Fuzzing）为最有效
的软件漏洞发现方法之一，因为它能够系统地探索未测试的代码路径和边界条
件，从而显著提高漏洞发现的效率和成功率。
为了提高 Fuzzing 的效率和有效性，研究者引入了灰盒 Fuzzing 技术，通过
插桩和反馈机制来优化输入生成策略。2007 年，Zalewski 发布了 AFL
（American Fuzzy Lop），这是一种采用灰盒 Fuzzing 技术的工具，大大提高了
Fuzzing 的覆盖率（Coverage）和漏洞发现率。

1.4 现代 Fuzzing（2010s 至今）

现代 Fuzzing 工具结合了先进的变异算法、分布式计算和云服务等，实现了高
效的大规模漏洞检测。工具如 libFuzzer和 Honggfuzz在 Google 和其他大型
科技公司中广泛应用，为软件安全性提供了强有力的保障。

AFL、AFL++主要是采用变异策略来生成测试样例，它们效果为什么这么好？AFL++为什么相较于AFL改进如此巨大？接下来的部分将试图弄清其中的来龙去脉。

2 AFL：遗传算法与确定性变异策略

2.1 AFL-Fuzz简介

American fuzzy lop (AFL) 是一个开源的模糊测试工具，采用遗传算法以有效地提高测试用例的代码覆盖率。目前为止，它帮助检测了数十个主要软件项目中的重大程序错误，包括X.Org Server、PHP、OpenSSL、pngcrush、bash、Firefox、BIND、Qt和SQLite等。
其执行流程大致如下：

①在从源码编译程序时进行插桩，以记录代码覆盖率（Code Coverage）。
②选择一些输入文件作为初始测试集，加入输入队列（queue）。
③对队列中的文件按一定策略进行“突变”。
④如果变异文件扩展了覆盖范围，则将其保留并添加到队列中。
⑤上述过程循环进行，期间触发 crash 的文件会被记录下来。
其核心主函数为fuzz_one()，示例图如下：

fuzz_one(queue_entry *q):获取测试用例并喂给目标程序，根据优胜者机制按概率跳过。调用trim_case剪枝，calculate_score打分，然后进行变异（如bitflip、arithmetic inc/dec等），变异后调用common_fuzz_stuff处理结果。这是主要函数。
以下是值得关注的函数，如何对数据进行剪枝，如何评估测试用例并优选种子，等等
trim_case():对当前测试用例进行剪枝，以减少无效数据。
calculate_score():计算测试用例得分。根据执行时间、覆盖率、新路径和深度对测试用例评分，确保高潜力的测试用例在变异过程中获得更多机会。
save_if_interesting():保存有趣的测试用例。检查执行结果是否有趣，即，调用has_new_bits(virgin_bits)来判断是否产生了新的路径元组，若是则保存或加入队列。trace_bits指向由全体进程共享的内存区域，其中包含每次样本执行的覆盖率，其实是之后提到的覆盖次数桶的压缩存储。

2.2 插桩技术

既然要进行覆盖率的引导来辅助遗传算法的进化过程，就必须统计覆盖率，而如果想要记录这一数值，就需要用到插桩技术，插桩一共有三种模式：llvm mode，汇编层面插桩，qemu-mode动态插桩。

2.2.1静态插桩

有两种静态插桩方式：llvm mode，汇编层面插桩。
如果拥有受测试程序的源代码，可以使用静态插桩技术来实现覆盖率的记录和增强，这一功能被AFL项目命名为llvm mode，具体实现方式是借助LLVM的Pass来更改中间代码表示IR(Intermediate Representation)，从而在编译过程中实现插桩。

在有源代码的情况下，可以使用 AFL 自带的 afl-gcc 或 afl-clang 插桩方式，这些工具通过修改 GCC 或 Clang 编译器，在编译过程中插入覆盖率收集代码，性能介于 QEMU 动态插桩和 LLVM 静态插桩之间。

接下来详细叙述怎么进行汇编层面插桩。实际的插桩工作发生在汇编为机器语言的环节。查看该项目的afl-as.h头文件，可以看到，以下这段内容是AFL插入到每个代码块结束处的汇编代码，其调用(call指令)__afl_maybe_log，这个正是探测点（Probe Points）相关汇编代码。

从控制流的角度来看，代码块（code block）是一个或多个语句的集合，这些语句按照程序的逻辑顺序一起执行。代码块的基本功能是将一系列操作组织在一起，以实现特定的功能或操作。代码块的控制流主要涉及语句的顺序执行、条件分支和循环。

该源代码插桩方式正是将所有代码块的开始部分进行插入，因为插入点位于基本块的开始处，可以准确记录程序执行到这个代码块的次数和路径。
而对于分支(如)和函数调用的插桩，AFL会把所有函数调用都进行插桩，但分支的数量往往比较巨大，为了让用户能够按需进行性能和插桩完整程度的权衡，AFL提供了一个值inst_ratio_str ,这个值用于控制对分支的插桩比例，R(100)是0-100随机值，如果>inst_ratio_str则不进行插桩，这就完成了按概率来进行对分支的插桩。其代码逻辑如下

此外，对于LLVM插桩，跟随afl-llvm-rt.o.c查看LLVM Pass层次的实现代码，实际上可以发现，很多内容都是用c来表示的，但功能和先前的汇编差不多，比如插桩比例的控制：

又比如forkserver与父进程的等待和通信，这些内容将会在接下来进行详细叙述。

2.2.2动态插桩

在没有源代码的情况下进行插桩，被称为唯二进制插桩 (Binary-only instrumentation)。AFL 的作者对 QEMU（一种跨架构软件执行环境工具，也可称为”跨架构二进制翻译器”）进行了二次开发，使其具备二进制插桩的能力。具体而言，是对QEMU 使用基础块（basic blocks）作为翻译单元。直接查看其二开的QEMU不太方便，查看technical_details.txt说的概念：

if (block_address > elf_text_start && block_address < elf_text_end) 这一判断是为了确保当前基础块的地址在可执行代码段（.text 段）内，以过滤掉不相关的地址。
紧接着，cur_location = (block_address >> 4) ^ (block_address << 8); 通过移位和异或运算计算当前基础块的位置。这种计算方式生成一个相对唯一的标识符，用于标识当前基础块。
shared_mem[cur_location ^ prev_location]++;使用当前块的位置与前一个块的位置进行异或运算，更新共享内存中的覆盖率信息。shared_mem 是一个共享内存区域，用于记录不同路径的执行次数。
prev_location = cur_location >> 1;更新前一个块的位置，以便在下一个基础块执行时进行正确的覆盖率计算。其实现的正是QEMU下的覆盖率引导计算，相关内容在后面还会详细说明。
本身的二进制翻译器如 QEMU、DynamoRIO 和 PIN 启动较慢，为了弥补这一点，AFL 在 QEMU 模式下使用了 fork server和管道机制，前面已作详细说明。经过这些优化，QEMU 模式下的 AFL 开销是白盒模式(有源代码插桩fuzzing)的 2-5 倍，而使用 PIN 的开销则高达 100 倍以上。

2.3 eff_map对变异的影响

这里还要引入一个eff_map的概念，此项记录了每个字节是否引起了新路径元组的出现，用以评估其对整个执行路径元组的影响。如果 byte 尝试所有改变都没有出现新路径，AFL开发者认为这种字节很有可能只是单纯的非元数据，AFL后续会参考eff_map 进行选择性的跳过。接下来每次变异都会检查eff_map中的对应项 ，如果当前字节对应的项为 0 ，则检查变异以后路径是否有新元组产生，如果是则置为 1。

而且，eff_map会将输入测试用例文件小于128字节的情况，认为每个字节都是有效的，而如果一个测试用例，90%的字节都能触发新路径元组，那么AFL会直接把剩余的10%也认为是有效的。
这种做法改善了变异的方向性，使其能够避免过多的无效变异，从而更加专注于有效的变异。

2.4 输入队列变异

在完成上述步骤以后，AFL会对测试样例进行变异操作。
这部分的内容更像是经验主义的产物，没有什么比较有意思的细节，但被实践证明是高效率的，因而被采纳。主要的代码逻辑仍位于afl-fuzz.c。

2.4.1 简单位翻转(simple bitflip)变异

首先是简单的位翻转(Simple Bitflip)，该操作是之后一系列变异方式的基础

该定义宏实现了指定位翻转的功能，_ar传入需要进行位翻转操作的字节数组指针，_b则是要翻转的位置。实际上该定义宏常见于各项目，不再赘述。
由简单翻转衍生出的变异模式有：
bitflip 1/1：步长为 1 bit，每次翻转 1 bit。
bitflip 2/1：步长为 1 bit，每次翻转相邻的 2 bit。
bitflip 4/1：步长为 1 bit，每次翻转相邻的 4 bit。
bitflip 8/8：步长为 1 byte，每次翻转 1 byte，并检查效应图（eff_map）。
bitflip 16/8：步长为 1 byte，每次翻转相邻的 2 byte。
bitflip 32/8：步长为 1 byte，每次翻转相邻的 4 byte。
此处以bitflip 4/1为例：

实现的就是步长总长度1byte，每次翻转这1byte里面连续的4bits。实际上其它的位翻转变异实现功能上是大同小异的，细节可能稍微有点不一样。common_fuzz_stuff实际上正如其名，是在检测fuzz是否成功触发新路径，如果是，那么就记录该路径并放弃继续变异，这次变异的结果也会被保存。
该操作的剩余部分的作用将在字典变异里提及，此处按下不表。

2.4.2 加减法变异

加减法变异，就是对测试用例做加减法方面的变异；为了避免无意义的重复变异，使用could_be_bitflip来检查变异结果与位翻转重合的部分（比如+4就等于在低第3位把0变为1，这样就重合了）；而且会限定大致的加减法变异范围，默认是从-35尝试到+35。该变异分为arith 8/8、arith 16/8、arith 32/8，步长都是1 byte，而范围分别对应byte、word、double word的现实情况，比如短、中等、长整形值的变化，字母abcd的横向变动，等等。以arith 8/8为例，观察其实现：

这里最关键的实现是，ARITH_MAX 控制了变异的范围和次数，j 的值每次递增 1，步长为 1 字节。通过 r = orig ^ (orig + j) 进行异或运算，将原始值和加法变异后的值进行异或，从而得到它们之间所有不同的位。然后使用 could_be_bitflip(r) 判断这些不同的位是否可以通过位翻转实现同样的加法变异，从而实现变异上的去重。
最后，真正记录变异的是步骤 out_buf[i] = orig + j 和 out_buf[i] = orig - j。这种方法确保了每次变异操作的唯一性和有效性，通过排除可以通过简单位翻转实现的变异，优化了变异过程。

2.4.3 特殊值(interesting values)变异

这部分就是将数值替换为预先定义好的“有趣的”值，这些特殊值比较容易引起软件的崩溃，非常值得测试。同时，这一部分会使用could_be_bitflip、could_be_arith与之前的阶段进行去重。特殊值如下，可以看出来这些变异对控制长度的字段将会十分有针对性，能测试出比如常见的输入边界没有控制好的问题，导致最后一个字节可以写入到超出预期的内存空间，那么就导致了内存破坏漏洞的产生，在特定的情况，这种漏洞会成为漏洞利用链的一环。

主要有三种，interest 8/8，interest 16/8、interest 32/8，范围分别对应短、中、长整形。以interest 8/8（范围和步长均为8 bits）为例，这部分的代码逻辑主要如下:

其实这种变异就是直接赋值为预先定义好的interesting值。可以看到是与之前各种变异大同小异的，主要区别是使用了if (could_be_bitflip(orig ^ (u8)interesting_8[j]) ||could_be_arith(orig, (u8)interesting_8[j], 1)) 这个判断来与先前的位翻转变异、加减法变异进行去重。

2.4.4 字典(dictionary stuff)变异

使用字典内容来进行变异，与上一部分针对特殊整型值的变异不太一样的是，这一部分主要是针对一些特殊的、有实际意义的字符串内容来进行变异。
该字典被命名为extras，里面的内容被称作tokens其首先会被按字符串长度从小到大排列，以实现更快速的判断出已经无法放入更长字符串的事实并打断循环。
然后，逐一从该字典中取出字符串，并且采用覆盖 (over)、中间插入(insert，比over显然时间复杂度更高，因为需要移动字符串尾部)的方式来进行测试样例的变异。此处以覆盖型的字典变异的代码实现为例。

可以看出来 memcpy(out_buf + i, extras[j].data, last_len);就是在测试样例的尾部追加字典内的字符串。而这一部分有一个条件很长的if判断，一个一个来看
条件1：extras_cnt > MAX_DET_EXTRAS && UR(extras_cnt) >= MAX_DET_EXTRAS 这里有一个特性，AFL 会检查 tokens 的数量。如果 tokens 的数量超过预设的 MAX_DET_EXTRAS（默认为200），则针对每个 token，会根据概率决定是否进行替换。UR(extras_cnt) 是一个在运行时生成的随机数，范围在0到extras_cnt之间。根据 MAX_DET_EXTRAS 的设置和UR(extras_cnt)的结果大小进行比对，决定是否跳过对当前 extras[j] 元素的处理。
条件2：extras[j].len > len - i 表示当前位置没有足够的空间来插入 extras[j] 的数据。
条件3：!memcmp(extras[j].data, out_buf + i, extras[j].len)表示要插入的数据已经存在于当前位置，因此不需要重复插入，这样就实现了去重
条件4：!memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, extras[j].len))则是查看eff_map有没有认为该处的数据并不重要
而这里还有一个非常有效的方式，用户没有提供字典的时候，会依靠最先前的bitfilp去选择出有效的字符串组成一个字符串的集合(token)。作者在代码注释中进行了解释。

简单举例来说，如果在位翻转变异过程中存在一个字符串：前导字节[IHDR]尾随字节，改变前导和尾随字节导致程序流的变化不大或没有变化，但触及"IHDR"字符串中的任何字符总是产生相同且独特的路径，那么AFL就会把IHDR列入字典变异的考量之中。
接下来，MAX_AUTO_EXTRA限定extras最高的存储容量。这段代码是模糊测试算法的一部分，通过检测校验和变化来收集和处理有意义的自动令牌。它在位翻转影响到执行结果时，收集字节到令牌数组 a_collect，并在令牌长度符合预设范围时调用 maybe_add_auto 函数进行处理。如果校验和发生变化，令牌会被处理并重置收集过程，从而确保只处理有影响的令牌。

其变异的具体实现与覆盖型字典变异类似，此处不再赘述。

2.4.5 随机毁坏(random havoc)变异

该变异方法只会在启用” dumb mode”时进行,实际上，这个方法与本文重点探讨的遗传算法不一样，这种变异与AFL之前出现的fuzz工具类似，进行随机性非常高的盲目变异而不进行任何筛选。此处不进行详细探讨。

2.4.6 (随机的)拼接(splicing)变异

该变异方法只会在启用” dumb mode”时进行，使用该类变异，把值得尝试拼接的测试用例拼接起来，有时候会有意想不到的效果，并且，在该变异后，紧接着会进行随机毁坏变异。由于该变异方式使用率和fuzzing成功率都较低，此处也不进行详细探讨。

2.5 fork server多进程执行测试样例

插桩完成后，可以通过 afl-fuzz 开始模糊测试。
execve的执行需要系统中断，系统调用，还需要载入目标文件和库、解析符号地址等操作，如果大量的fuzzing测试当中每次都要使用execve，将非常消耗性能。
所以，AFL 实现了一套 fork 服务器机制来减少系统调用的次数，并集中调配资源。其基本思路是启动目标进程后，由目标进程运行一个 fork 服务器，fuzzer 与这个 fork 服务器通信，由 fork 服务器完成 fork 和执行目标程序的操作。父进程 (fuzzer) 和子进程 (目标进程) 通过管道通信，目标进程在准备好后通知 fuzzer 可以开始 fork。
首先，在开始模糊测试时，AFL 使用 execve 启动目标程序，这步操作只执行一次。之后的子进程通过 fork 从已初始化的进程中创建，继承了相同的内存和资源，不需要重新加载目标程序和相关库。

Shared Memory：这是每个子进程之间的共享内存区域，用于子进程之间快速的信息沟通，子进程会通过 shmat() 将共享内存映射到自身地址空间中，便于记录执行路径信息。在子进程中，__afl_area_ptr 用于存储共享内存的地址，该地址指向 trace_bits。共享内存用于存储 trace_bits，这是一个记录每次执行路径的哈希表。
init_forkserver() 函数用于初始化每个独立的 fork 子进程服务器。该函数首先会创建两个管道 st_pipe 和 ctl_pipe，AFL 使用两个管道 st_pipe 和 ctl_pipe 实现父进程与子进程之间的通信。ctl_pipe 用于传递控制命令，而 st_pipe 则用于传递状态信息。通过这些管道，父进程（fuzzer）可以与子进程（目标程序）高效地交换信息。
然后调用 fork() 创建子进程。子进程会执行目标程序，并将管道描述符映射到预定义的文件描述符 FORKSRV_FD 和 FORKSRV_FD + 1。代码实现如下：

在目标程序启动后，fork 服务器进入等待状态，通过读取 ctl_pipe 等待 fuzzer 的控制命令。一旦接收到开始执行的命令，fork 服务器会调用 fork() 创建一个新的子进程，该子进程负责执行变异后的输入数据。这一等待逻辑是位于插桩位置的。查看汇编代码，这里有一个 __afl_fork_wait_loop 标签，外部通过 jmp 进入该标签。标签的主要功能是调用 read 函数对 FORKSRV_FD 指向的通信管道进行读取，如果读取到来自fuzzer 主进程的指令，则调用 fork 函数。

从这里也可以看出，AFL 的 fork 服务器确实是由最初由父进程(fuzzer进程)创建的首个子进程(后称为forkserver)创建更多的子进程来执行测试用例。


以上代码主要是为 fork 服务器设置控制和状态管道，并执行目标程序。在子进程中，将管道文件描述符重定向到预定义的文件描述符，并关闭不再需要的文件描述符，设置环境变量以优化性能，最终调用 execv 启动目标程序。

2.6 元组命中次数桶

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课