最近刚刚接触AFL(american fuzzy lop)，打算先通过阅读AFL源码来进行学习，在读源码之前我看了看AFL技术白皮书（Technical “whitepaper” for afl-fuzz），本文主要写一下我目前对于AFL插桩的粗浅理解，如有错误，恳请指正。

参考资料： 白皮书原文

在介绍AFL插桩之前，先简单介绍一下相关的基本概念

1.代码覆盖率 代码覆盖率是一种度量代码的覆盖程度的方式，也就是指源代码中的某行代码是否已执行。其计量方式很多，但无论是GCC的GCOV还是LLVM的SanitizerCoverage，都提供函数（function）、基本块（basic-block）、边界（edge）三种级别的覆盖率检测，更具体的细节可以参考LLVM的官方文档。

2.基本块（Basic Block） 缩写为BB，指一组顺序执行的指令，BB中第一条指令被执行后，后续的指令也会被全部执行，每个BB中所有指令的执行次数是相同的，也就是说一个BB必须满足以下特征：

3.边（edge） AFL的技术白皮书中提到fuzzer通过插桩代码捕获边（edge）覆盖率。那么什么是edge呢？我们可以将程序看成一个控制流图（CFG），图的每个节点表示一个基本块，而edge就被用来表示在基本块之间的跳转。知道了每个基本块和跳转的执行次数，就可以知道程序中的每个语句和分支的执行次数，从而获得比记录BB更细粒度的覆盖率信息。

4.元组（tuple） 具体到AFL的实现中，使用二元组(branch_src, branch_dst)来记录当前基本块 + 前一基本块 的信息，从而获取目标的执行流程和代码覆盖情况。

什么是插桩？ 在AFL编译文件时候afl-gcc会在规定位置插入桩代码，可以理解为一个个的探针(但是没有暂停功能)，在后续fuzz的过程中会根据这些桩代码进行路径探索，测试等。

AFL通过插桩的形式注入到被编译的程序中，实现对分支（branch、edge）覆盖率的捕获，以及分支节点计数。代码大致如下:

代码十分简单，我们来分析一下

第一行就是用一个随机数cur_location 标记当前的块。 之后将当前块和前一块异或保存到shared_mem[]，其中shared_mem[]数组是一个被调用者传入插桩二进制的64Kb SHM大小的区域。 最后一行将cur_location右移一位作为prev_location，这样就完成了对两个块的路径的标记。

这里就会有几个问题

1.为什么要将cur_location 和 prev_location进行异或处理，如果进行其他处理效果会怎样? 得到的答案是可能作者觉得这样处理得到的结果还不错，这里暂时还没想明白。

2.为什么要将cur_location进行除以二之后再赋给prev_location? 这里是为了区分两个块之间不同方向的路径，设想直接将cur_location作为下一个块的pre_location，那么这将很难鉴别A ^ B和B ^ A，这样显然不是我们想要的结果。

此外，在分支较多的情况下，产生的数据会发生冲突，下图就是白皮书中贴出的数据。