afl-fuzz技术白皮书

0. afl-fuzz的设计宗旨
   ================
   速度、可靠、易用

1. 覆盖率计算
   ========
   通过在编译期间instrument一些指令来捕获branch (edge) coverage和运行时分支执行计数
   在分支点插入的指令大概如下：

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

1. 为了简化连接复杂对象的过程和保持XOR输出平均分布，当前位置是随机产生的。

2. share_mem[]数组是一个调用者传给被instrument程序的64KB的共享内存区域，数组的元素是Byte。数组中的每个元素，都被编码成一个(branch_src, branch_dst)，相当于存储路径的bitmap。这个数组的大小要应该能存2K到10K个分支节点，这样即可以减少冲突，也可以实现毫秒级别的分析。
   这种形式的覆盖率，相对于简单的基本块覆盖率来说，对程序运行路径提供了一个更好的描述。以下面两个路径产生的tupes为例：
   A -> B -> C -> D -> E (tuples: AB, BC, CD, DE)
   A -> B -> D -> C -> E (tuples: AB, BD, DC, CE)
   这更有助于发现代码的漏洞，因为大多数安全漏洞经常是一些没有预料到的状态转移，而不是因为没有覆盖那一块代码。

3. 最后一行右移操作是用来保持tuples的定向性。如果没有右移操作，A ^ B和B ^ A就没办法区别了，同样A ^ A和B ^ B也是一样的。Intel CPU缺少算数指令，左移可能会会导致级数重置为0，但是这种可能性很小，用左移纯粹是为了效率。

4. 发现新的执行路径
   =========

AFL-fuzzer用一个全局的map用来存储之前执行时看到的tupes。这些数据可以被用来对不同的trace进行快速对比，从而可以计算出是否新执行了一个dword指令/一个qword-wide指令/一个简单的循环。
当一个变异的输入产生了一个包含新路径（tuple）的执行trace时，对应的输入文件就被保存，然后被用在新的fuzzing过程中。对于那些没有产生新路径的输入，就算他们的instrumentation输出模式是不同的，也会被抛弃掉。
这种算法考虑了一个非常细粒度的、长期的对程序状态的探索，同时它还不必执行复杂的计算，不必对整个复杂的执行流进行对比，也避免了路径爆炸的影响。为了说明这个算法是怎么工作的，考虑下面的两个trace，第二个trace出现了新的tuples(CA, AE)

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

同时，由于执行了第2个trace,下面的pattern就不被认为是不同的了，尽管它看起来是一个不同的执行路径。

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

为了发现新的tuples，AFL-fuzzer也会粗糙地计算已经有的tuple的数目。它们被分成几个bucket：

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

从某种程度上讲，这些数字有一些fuzzer架构的意义：
它是一个8-bit counter和一个8-position bitmap的映射。其中8-bit counter是通过instrument产生的；而8-bit position bitmap则依赖于fuzzer跟踪的，已经执行的tuple数目。
只更改了单个bucket的改变会被忽略掉。在程序控制流中，从一个bucket到另一个bucket的转变，会被标记为感兴趣的改变，接下来会被使用。
hit count算法可以分辨出控制流是否发生改变，比如说一个基本块被执行了两次，但其实它只被hit了一次。hit count算法对循环了多少次是不敏感的。
另外，算法通过设置执行超时，来避免效率过低的fuzz。从而进一步发现效率比较高的fuzz方式。

3. 输入队列的进化
   ==========

经变异的测试用例，会使程序产生新的状态转移。这些测试用例稍后被添加到input队列中，用作下一个fuzz循环。它们补充但不替换现有的发现。
这种算法允许工具可以持续探索不同的代码路径，其实底层的数据格式可能是完全不同的。如下图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xYrgiiBY-1586859319387)(http://lcamtuf.coredump.cx/afl/afl_gzip.png)]

下面的链接是对这个算法的一些实际应用，可以参考下：
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

这种过程下产生的语料库基本上是这些输入文件的集合：它们都能触发一些新的执行路径。产生的语料库，可以被用来作为其他测试的种子。
使用这种方法，大多数目标程序的队列会增加到大概1k到10k个entry。大约有10-30%归功于对新tupe的发现，剩下的和hit counts改变有关。

下面这这表比较了几个不同的guided fuzzing方法，发现文件语法和探索程序执行路径的能力：

    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”)代表仅仅执行了一个回合的测试。
第二行的Blind fuzzing 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. 语料的选择
   ========

上述探索程序路径的方法意味着：一些后来出现的test cases产生的edge coverage，可能会是之前的test cases产生的edge coverage的超集。
为了优化fuzzing的结果，AFL会用一个快速算法周期性的重新计算队列，这个算法选择一个小的能够覆盖目前所有tuple的test cases子集。
算法是这么工作的：给队列的每一个entry赋一个值（这个值是它的执行时延和文件大小的比例），然后为每个tuple选择值最小的一个。
这些tuples之后会按照下述流程进行处理：

  1) Find next tuple not yet in the temporary working set,

  2) Locate the winning queue entry for this tuple,

  3) Register *all* tuples present in that entry's trace in the working set,

  4) Go to #1 if there are any missing tuples in the set.

这样产生的语料，会比初始的数据集小5到10倍。没有被选择的也没有被扔掉，而是在遇到下列对队列时，以一定概率略过：

  - If there are new, yet-to-be-fuzzed favorites present in the queue, 
    99% of non-favored entries will be skipped to get to the favored ones.

  - If there are no new favorites:

  - If the current non-favored entry was fuzzed before, it will be skipped 95% of the time.

  - If it hasn't gone through any fuzzing rounds yet, the odds of skipping drop down to 75%.

基于以往的测试经验，这提供了一个队列循环速度和test case多样性的平衡。
我们也可以用afl-cmin去专门处理数据，这个工具会永久丢弃冗余的entries，然后产生一个供afl-fuzz或其他工具使用的语料。

5. 整理输入文件
   =========

文件大小对fuzzing的性能有很大的影响，一是因为大文件会让目标程序变慢，二是因为大文件减少了一个mutation触发重要格式控制结构的，而不是总在触发冗余的数据块。因为一些mutations可以使得产生文件的大小迭代性增加，所以也要考虑（一个不好的起始语料）这个因素。
幸运的是，instrumentation的反馈提供了一个用来自动精简（trim down）输入文件的简单的方法，这种方法同时还保证了对文件的改变不会对执行路径产生影响。afl-fuzz内置的trimmer试图用计算变量长度和step over的方法，循序地减少数据块。
这个trimmer试图在精确和产生的进程数之间做一个平衡。而afl-min这个工具则是用了一个更详尽的迭代算法去精简文件，当然耗时更多。

6. Fuzzing策略
   ============

instrumentation产生的反馈，让我们更容易去理解不同fuzzing策略的价值，进而去优化它们的参数使得它们更有效。
afl-fuzz所使用的策略是一种与格式无关的策略，详见：http://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html
afl-fuzz一开始所做的工作都是确定性的，之后才会有一些随机性的更改和test case的拼接，这些确定性策略包括：

  - Sequential bit flips with varying lengths and stepovers,

  - Sequential addition and subtraction of small integers,

  - Sequential insertion of known interesting integers (0, 1, INT_MAX, etc),

非确定性步骤包括：stacked bit flips, insertions, deletions, arithmetics, and splicing of different test cases.

为了性能、简洁性、可靠性，AFL不试图去推断某个mutation和program state的关系。
这意味着，这条规则有一个例外：
当一个新的队列条目，经过初始的确定性fuzzing步骤集合时，并且文件的部分区域被观测到对执行路径的校验和没有影响，这些队列条目在接下来的确定性fuzzing阶段可能会被排除。
尤其是对那些冗长的数据格式，这可以在保持覆盖率不变的情况下，减少10-40%的执行次数。在一些极端情况下，比如一些block-aligned的tar文件，这个数字可以达到90%。

7. 字典
   =====

instrumentation产生的反馈让我们可以自动的辨认出一些输入文件的语法符号，从而可以进一步发现，某些预定义的或者自动检测的字典条目可以组成一个正确的被测程序语法。
详见：http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html

大体上，一开始一些基本的语法token被随机组合在一块时。instrumentation和队列进化设计一起提供了一个反馈机制，可以用来区分哪些可以触发新行为和那些无意义的语法。进一步可以基于这种反馈机制，构建更复杂的语法。
这种词典已经被证明可以让fuzzer快速地构建一些很复杂的语法，比如JavaScript, SQL, XML。

8. crashes的重复
   =============
   crashes的重复数据删除，对于每一个完整的fuzzing工具来说是一个必不可少的问题，然而很多工具都用了错误的解决方案.
   比如，只看出错的内存地址，如果错误发生在一个库函数中，就会导致一些完全无关的问题被聚合在一块。
   同一个错误，有可能是通过不同的路径触发的，所以call stack校验和这种方案也不可靠。
   afl-fuzz采用的方案是：如果下列条件之一符合，就认为crash是唯一的：

  - The crash trace includes a tuple not seen in any of the previous crashes,
  - The crash trace is missing a tuple that was always present in earlier faults.

9. 调查crashes
   ============

对不同类型的crash进行探索是有歧义的，afl-fuzz提供了一个crash探索模式。
在这种模式下，导致crash的test case以一种和普通fuzz类似的方式去测试，但是抛弃了所有没有导致crash的mutations，详见：http://lcamtuf.blogspot.com/2014/11/afl-fuzz-crash-exploration-mode.html。
这种方法利用instrumentation的反馈，探索crash程序的状态，从而进一步通过歧义性的失败条件，找到了最新发现的input。
对于crashes来说，值得注意的是和正常的队列条目对比，导致crash的input没有被去掉，为了和它们的父条目（队列中没有导致crash的条目）对比，它们被保存下来，
这就是说afl-tmin可以被用来随意缩减它们。

10. The fork server
    ===================

为了提升性能，afl-fuzz使用了一个“fork server”，fuzz进程只进行一次execve(),linking和libc initialization，之后的fuzz进程通过写时拷贝技术从已经停止的fuzz进程镜像直接拷贝。详见：http://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html
fork server被集成在了instrumentation的程序下，在第一个instrument函数执行时，fork server就停止并等待afl-fuzz的命令。
对于需要快速发包的测试，fork server可以提升1.5到2倍的性能。

11. 并行机制
    ========

实现并行的机制是，定期检查不同cpu core或不同机器产生的队列，然后有选择性的把队列中的条目放到test cases中。
详见： parallel_fuzzing.txt.

12. 二进制instrumentation
    ======================
    AFL-Fuzz对二进制黑盒目标程序的instrumentation是通过QEMU的“user emulation”模式实现的。
    这样我们就可以允许跨架构的运行，比如ARM binaries运行在X86的架构上。QEMU使用basic blocks作为翻译单元，利用QEMU做instrumentation，再使用一个和编译期instrumentation类似的guided fuzz的模型。
    像QEMU, DynamoRIO, and PIN这样的二进制翻译器，启动是很慢的QEMU mode同样使用了一个fork server，和编译期一样，通过把一个已经初始化好的进程镜像，直接拷贝到新的进程中。
    当然第一次翻译一个新的basic block还是有必要的延迟，为了解决这个问题AFL fork server在emulator和父进程之间提供了一个频道。这个频道用来通知父进程新添加的blocks的地址，之后吧这些blocks放到一个缓存中，以便直接复制到将来的子进程中。这样优化之后，QEMU模式对目标程序造成2-5倍的减速，相比之下，PIN造成100倍以上的减速。