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+ |
此处有个疑问:3 作为单独一个桶有点乱入的感觉,为什么不是 2-3 作为一个桶,且为什么没有 0 这个桶呢?
总结一下,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. |
首先在宏定义中,计算整个 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 | /* Updates the virgin bits, then reflects whether a new count or a new tuple is |
首先,计算 *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 | id: 记录 corpus 的 id 编号 |