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 | corpus 1: A -> B -> C -> D -> E => (AB, BC, CD, DE) |
其次,通过一个共享数组 shared_mem
来记录 (branch_src, branch_dst)
元组(可以看作是 CFG 中的 edge 的表示)被命中的次数,伪代码为:
1 | cur_location = <COMPILE_TIME_RANDOM>; |
当 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
。这样处理的好处有两个:
- 区分 AB 和 BA。如果没有进行右移,那么
A^B
算出的索引,和B^A
算出的索引,二者是相等的,也就是把 AB 和 BA 看做是同一个 edge。实际上 CFG 中 edge 都是有向边,方向性是一个很重要的信息。 - 区分 AA 和 BB。在循环体中,如果
prev_location
与cur_location
相等,那么cur_location^prev_location
的结果将恒等于 0。导致循环体执行不同的 basic block 时,在shared_mem
中无法得到有效区分。
这种统计方式也是有一定局限性的,例如:
1 | corpus 1: 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+ |
总结一下,AFL++ 认为一个 corpus 是 interesting,当且仅当 corpus 至少满足以下条件之一:
- corpus 找到了一个新的 edge。
- 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 | if (st.st_size && st.st_size <= MAX_FILE) { |
可以看到 save_if_interesting
函数的入参分别为:
1 | afl: AFL++ 的全局状态 |
在 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 | /* Check if the current execution path brings anything new to the table. |
在第一部分介绍 AFL++ 统计覆盖率的原理时有讲,AFL++ 将每个 edge 的命中频次进行分桶处理,分成了 8 个桶,每个桶实际上是以一个 bit 位来表示。在 AFL++ 源码中用 afl->virgin_bits
来记录,对应函数中的形参virgin_map
。
在 virgin_map
中,若virgin_map[12345]=0b10110110
,表示 AFL++ 产生的所有 corpus 在 12345 这个 edge 上,有命中 2 次、8-15 次、128+ 次三种情况。
而 afl->fsrv.trace_bits
则记录了当前 corpus 走过 edge 的命中频次(分桶后的结果),那么通过位运算即可判断当前 corpus 走过的 edge 是否有变换。
值得注意的是:在 AFL++ 初始化 afl->virgin_bits
时,将所有的 bit 位都设为 1,因此 1 表示没有落在这个桶,0 表示落在这个桶。但在 afl->fsrv.trace_bits
中,bit 为 1 表示落在这个桶,0 表示没有落在这个桶。两者 bit 为 1 的含义刚好相反!
1 | memset(afl->virgin_bits, 255, map_size); // afl-fuzz.c 设置 virgin_bits 初始值 |
函数中为了加速运算(减少循环次数),在 32 位系统和 64 位系统中,分别将 afl->virgin_bits
和afl->fsrv.trace_bits
转换为对应类型的 virgin
和current
。
在 while
循环中,调用 discover_word
函数来完成 current
和virgin
的实际比对操作。
3. discover_word
具体完成某个 edge 的 bitmap 对比的是 discover_word
函数,其代码为:
1 | /* Updates the virgin bits, then reflects whether a new count or a new tuple is |
首先,计算 *current & *virgin
,即将current
的首元素与 virgin
的首元素进行按位与运算。由于 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
是由于将 u64 转为 u8,即 virgin
和current
的每个元素实际上对应了 8 个 edge。
4. describe_op
在 AFL++ 获得一个 interesting 的 corpus 之后,会将其保存为文件。在保存之前,通过 describe_op
函数来生成文件名,在文件名中记录一些关键信息:
1 | id: 记录 corpus 的 id 编号 |