AFL++ 源码分析——覆盖率

前文 AFL++ 同步机制 提到，执行同步函数 sync_fuzzers 会调用函数 save_if_interesting。顾名思义，这个save_if_interesting 函数是用来保存 interesting 的 corpus。

AFL++ 认为 corpus 是否 interesting，是基于 corpus 对 binary 的代码覆盖率来判断。在分析 save_if_interesting 的源码之前，有必要了解一下 AFL++ 的覆盖率统计机制。

一、原理简介

在AFL++ 白皮书 中，对覆盖率的计算有简要说明。

首先，通过插桩，来跟踪 corpus 在 binary 中走过的路径，并将路径转换为一系列 (branch_src, branch_dst) 元组的集合。例如：

1
2

corpus 1: A -> B -> C -> D -> E  =>  (AB, BC, CD, DE)
corpus 2: A -> B -> D -> C -> E  =>  (AB, BD, DC, CE)

其次，通过一个共享数组 shared_mem 来记录 (branch_src, branch_dst) 元组（可以看作是 CFG 中的 edge 的表示）被命中的次数，伪代码为：

1
2
3

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

当 corpus 从 branch_src 走到 branch_dst 时，将 branch_dst 与branch_src进行异或运算的结果作为 shared_mem 的索引，并给索引指向的元素进行加一操作，表示多命中一次(branch_src, branch_dst)。

值得注意的是最后一行的右移操作。当从 branch_dst 开始找下一个 edge 时，并没有直接把 cur_location 赋值给 pre_location，而是先对cur_location 进行了一次右移操作，再赋值给pre_location。这样处理的好处有两个：

1. 区分 AB 和 BA。如果没有进行右移，那么 A^B 算出的索引，和 B^A 算出的索引，二者是相等的，也就是把 AB 和 BA 看做是同一个 edge。实际上 CFG 中 edge 都是有向边，方向性是一个很重要的信息。
2. 区分 AA 和 BB。在循环体中，如果 prev_location 与cur_location相等，那么 cur_location^prev_location 的结果将恒等于 0。导致循环体执行不同的 basic block 时，在 shared_mem 中无法得到有效区分。

这种统计方式也是有一定局限性的，例如：

1
2
3

corpus 1: A -> B -> C -> D -> E  =>  (AB, BC, CD, DE)
corpus 2: A -> B -> C -> A -> E  =>  (AB, BC, CA, AE)
corpus 3: A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E  =>  (AB, BC, CD, DE)

corpus 2 与 corpus 1 相比，增加了新的 edge 元组 CA 和 AE。因此 AFL++ 认为 corpus 2 找到一条新的路径。
corpus 3 与 corpus 1 相比，没有增加新的 edge 元组。即使 corpus 3 的真实路径与 corpus 1 的真实路径有明显区别，但在 AFL++ 看来，corpus 3 并没有找到一条新路径。

AFL++ 在判断一个 corpus 是否 interesting 时，除了考虑 corpus 有没有找到新路径（命中新 edge），也会考虑 edge 的命中次数。为了简化命中次数的比较，AFL++ 对次数进行分桶处理，将命中次数分为如下 8 个桶（以 2 的幂次来分割）。当 corpus 使得 edge 的命中次数从一个桶变到另一个桶时，它也会被认为是 interesting。

1

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

此处有个疑问：3 作为单独一个桶有点乱入的感觉，为什么不是 2-3 作为一个桶，且为什么没有 0 这个桶呢？

总结一下，AFL++ 认为一个 corpus 是 interesting，当且仅当 corpus 至少满足以下条件之一：

1. corpus 找到了一个新的 edge。
2. corpus 使某个 edge 的命中次数从一个 bucket 转移到另一个 bucket。

二、源码分析

1. save_if_interesting

save_if_interesting 函数位于afl-fuzz-bitmap.c，其签名为：

1

u8 save_if_interesting(afl_state_t *afl, void *mem, u32 len, u8 fault);

在 sync_fuzzers 中调用 save_if_interesting 的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

if (st.st_size && st.st_size <= MAX_FILE) {

    u8  fault;
    u8 *mem = mmap(0, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    
    if (mem == MAP_FAILED) { PFATAL("Unable to mmap '%s'", path); }
    
    /* See what happens. We rely on save_if_interesting() to catch major
       errors and save the test case. */
    
    u32 new_len = write_to_testcase(afl, (void **)&mem, st.st_size, 1);
    
    fault = fuzz_run_target(afl, &afl->fsrv, afl->fsrv.exec_tmout);
    
    if (afl->stop_soon) { goto close_sync; }
    
    afl->syncing_party = sd_ent->d_name;
    afl->queued_imported += save_if_interesting(afl, mem, new_len, fault);
    show_stats(afl);
    afl->syncing_party = 0;
    
    munmap(mem, st.st_size);

}

可以看到 save_if_interesting 函数的入参分别为：

1
2
3
4

afl: AFL++ 的全局状态
mem: corpus 的内容
len: corpus 的长度
fault: fuzz_run_target 的执行结果，0 表示正常结束，1 表示运行超时，2 表示出现 crash

在 save_if_interesting 函数体内，主要执行了如下流程：

sequenceDiagram
    save_if_interesting ->> has_new_bits: 检查 corpus 是否能更新 bitmap
    has_new_bits ->> discover_word: 检查 bitmap 是否有变化
    discover_word -->> has_new_bits: 返回检查结果
    has_new_bits -->> save_if_interesting: 返回 0 表示无变化，返回 1 表示命中次数的 bucket 有变化，返回 2 表示找到了一个新 edge
    save_if_interesting ->> describe_op: 创建 corpus 文件名
    describe_op -->> save_if_interesting: 返回 corpus 文件名
    save_if_interesting ->> ck_write: 将 corpus 保存为文件
    save_if_interesting ->> add_to_queue: 将 corpus 添加到 AFL++ 的队列中

2. has_new_bits

负责检查整个 bitmap 是否有变化的是 has_new_bits 函数，其代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/* Check if the current execution path brings anything new to the table.
   Update virgin bits to reflect the finds. Returns 1 if the only change is
   the hit-count for a particular tuple; 2 if there are new tuples seen.
   Updates the map, so subsequent calls will always return 0.

   This function is called after every exec() on a fairly large buffer, so
   it needs to be fast. We do this in 32-bit and 64-bit flavors. */

inline u8 has_new_bits(afl_state_t *afl, u8 *virgin_map) {

#ifdef WORD_SIZE_64

  u64 *current = (u64 *)afl->fsrv.trace_bits;
  u64 *virgin = (u64 *)virgin_map;

  u32 i = ((afl->fsrv.real_map_size + 7) >> 3);

#else

  u32 *current = (u32 *)afl->fsrv.trace_bits;
  u32 *virgin = (u32 *)virgin_map;

  u32 i = ((afl->fsrv.real_map_size + 3) >> 2);

#endif                                                     /* ^WORD_SIZE_64 */

  u8 ret = 0;
  while (i--) {

    if (unlikely(*current)) discover_word(&ret, current, virgin);

    current++;
    virgin++;

  }

  if (unlikely(ret) && likely(virgin_map == afl->virgin_bits))
    afl->bitmap_changed = 1;

  return ret;

}

首先在宏定义中，计算整个 binary 的 bitmap 的长度i（可以理解为 edge 的个数）。

然后在 while 循环中，依次循环每个 edge，调用 discover_word 函数来完成实际比对操作。

current和 virgin 分别表示当前 corpus 覆盖路径对应的 bitmap，以及整个 AFL++ 已走过的路径所对应的 bitmap。

需要理解它们的数据结构，current和 virgin 是长度相等的一维数组，每个元素的有效数据是一个字节，即 8 个 bits 构成的 bit 数组，在 64 位和 32 位系统中，分别用 u64 指针和 u32 指针来指示。

在第一部分介绍 AFL++ 统计覆盖率的原理时有讲，AFL++ 讲每个 edge 的命中频次进行分桶处理，分成了 8 个桶，每个桶实际上是以一个 bit 位来表示。

在 AFL++ 初始化 virgin 时，将所有的 bit 位都设为 1，因此 1 表示没有落在这个桶，0 表示落在这个桶。但在 current 中，bit 为 1 表示落在这个桶，0 表示没有落在这个桶。需要注意 bit 为 1 的含义相反！

以 virgin 为例，若virgin[12345]=0b10110110，表示 AFL++ 产生的所有 corpus 在 12345 这个 edge 上，有命中 2 次、8-15 次、128+ 次三种情况。

3. discover_word

具体完成某个 edge 的 bitmap 对比的是 discover_word 函数，其代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/* Updates the virgin bits, then reflects whether a new count or a new tuple is
 * seen in ret. */
inline void discover_word(u8 *ret, u64 *current, u64 *virgin) {

  /* Optimize for (*current & *virgin) == 0 - i.e., no bits in current bitmap
     that have not been already cleared from the virgin map - since this will
     almost always be the case. */

  if (*current & *virgin) {

    if (likely(*ret < 2)) {

      u8 *cur = (u8 *)current;
      u8 *vir = (u8 *)virgin;

      /* Looks like we have not found any new bytes yet; see if any non-zero
         bytes in current[] are pristine in virgin[]. */

      if ((cur[0] && vir[0] == 0xff) || (cur[1] && vir[1] == 0xff) ||
          (cur[2] && vir[2] == 0xff) || (cur[3] && vir[3] == 0xff) ||
          (cur[4] && vir[4] == 0xff) || (cur[5] && vir[5] == 0xff) ||
          (cur[6] && vir[6] == 0xff) || (cur[7] && vir[7] == 0xff))
        *ret = 2;
      else
        *ret = 1;

    }

    *virgin &= ~*current;

  }

}

首先，计算 *current & *virgin，即将current 指向的 8 个 bits 与 virgin 指向的 8 个 bits 进行按位与运算。

前面说到 bit=1 在current与 virgin 中的含义是相反的，那么 current 与virgin按位与的结果为 1，说明至少有一个桶，virgin是没到过的，而 current 到了。

接着，判断 likely(*ret < 2)，在 AFL++ 看来*ret < 2 是一个很可能出现的情况，current找到一个新的 edge，才会将设置*ret=2。

判断 current 是否找到一个新的 edge，是通过依次比较 (cur[k] && vir[k] == 0xff), k=0...7 来实现的。vir[k]==0xff表示所有桶的 bit 位为 1，即这个 edge 从来没到过。而 cur[k]==1 表示当前 corpus 到了这个 edge，从而认为 corpus 找到了新 edge。

此处有个疑问：k 从 0 到 7 要怎么理解？从代码来看，current 和 virgin 的每个元素用 64 个 bit 来存储，分 8 次读取，某一次读取的 8 个 bit 是全为 1 就可以。那为什么不直接用 8 个 bit 来存储？

4. describe_op

在 AFL++ 获得一个 interesting 的 corpus 之后，会将其保存为文件。在保存之前，通过 describe_op 函数来生成文件名，在文件名中记录一些关键信息：

1
2
3
4
5
6
7

id: 记录 corpus 的 id 编号
sync: 从哪个目录同步过来
src: 从哪个 corpus 演化而来，记录来源 corpus 的 id
time: AFL++ 的运行时间
execs: AFL++ 的运行次数
+cov: 当前 corpus 找到了新 edge，即 has_new_bits 返回 2
+tout: 当前 corpus 运行超时

三、参考资料

1. AFL 源码阅读（六）：队列、变异、同步
2. AFL++ 白皮书和源码阅读