AFL分享

AFL

1.介绍afl大致流程

①从源码编译程序时进行插桩，以记录代码覆盖率（Code Coverage）；

②选择一些输入文件，作为初始测试集加入输入队列（queue）；

③将队列中的文件按一定的策略进行“突变”；

④如果经过变异文件更新了覆盖范围，则将其保留添加到队列中;

⑤上述过程会一直循环进行，期间触发了crash的文件会被记录下来。

二、插桩：

为什么要插桩？：

1.代码覆盖率
代码覆盖率是一种度量代码的覆盖程度的方式，也就是指源代码中的某行代码是否已执行。这里涉及到三个概念，基本块（basic-block）、边界（edge）、元组（tuple）。

2.基本块（Basic Block）
将程序的代码划分为一个个基本块，在这个基本块中第一条指令被执行后，后续的指令也会被全部执行，每个基本块中所有指令的执行次数是相同的，下图就是对分块的一个简单示例。

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

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

怎么插桩？：

插什么？：

插桩代码的伪代码如下：

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

cur_location的值是随机产生的，为的是简化连接复杂对象的过程和保持XOR输出分布是均匀的，后者可用减少tuple映射到shared_mem[] 时发生冲突的概率。

shared_mem[] 数组是一个64kb的共享空间。其中的每一字节里面存储着对于特定的Edge也就是tuple的命中次数，所以最多可用处理64k个Edge。

prev_location = cur_location >> 1; 如果不右移，A->B与B->A这两个不一样的执行路径生成的异或值是一样的，会导致无法区分。

三、准备测试用例:

在read_testcases函数中，会对用户给出的测试用例做筛选，比如判断是否是常规文件，而不是目录文件，设备文件等，判断测试用例是否为空文件等。因此部分无效的初始测试用例会被抛弃。

四、变异-确定性变异：

4.1确定性变异：（如果当前测试用例做过确定性变异，就会直接做非确定性变异，也就是每个测试用例只做依次确定性变异）

1.bitflip，位反转

基本原理：bitflip，按位翻转，1变为0，0变为1。

拿到一个原始文件，打头阵的就是bitflip，而且还会根据翻转量/步长进行多种不同的翻转，按照顺序依次为：

• bitflip 1/1，每次翻转1个bit，按照每1个bit的步长从头开始

//stage_max是当前测试用例的bit数 for (stage_cur = 0; stage_cur < stage_max; stage_cur++) { 
    //翻转第stage_cur 位bit FLIP_BIT(out_buf, stage_cur); //将修改后的测试用例拿去测一下目标二进制，如果有触发新的tuple或者使某个tuple的命中数增加了合理值，就把翻转后的内容作为新的测试用例加入到queue种， //如果用户主动结束测试，或者用户主动请求放弃当前测试用例等，common_fuzz_stuff就返回1，执行abandon_entry if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry; //没出错就把修改的那一位改回来 FLIP_BIT(out_buf, stage_cur); ..... } 

• bitflip 2/1，每次翻转相邻的2个bit，按照每1个bit的步长从头开始
• bitflip 4/1，每次翻转相邻的4个bit，按照每1个bit的步长从头开始
• bitflip 8/8，每次翻转相邻的8个bit，按照每8个bit的步长从头开始，即依次对每个byte做翻转
• bitflip 16/8，每次翻转相邻的16个bit，按照每8个bit的步长从头开始，即依次对每个word做翻转
• bitflip 32/8，每次翻转相邻的32个bit，按照每8个bit的步长从头开始，即依次对每个dword做翻转

每次翻转后会将翻转后测试用例作为输入检测一次程序，如果导致崩溃就放弃对这个测试用例的继续变异，直接对下一个测试用例进行如上操作

自动检测token

生成effector map

在进行bitflip 8/8变异时，AFL还生成了一个非常重要的信息：effector map。这个effector map几乎贯穿了整个deterministic fuzzing的始终。

具体地，在对每个byte进行翻转时，如果其造成执行路径与原始路径不一致，就将该byte在effector map中标记为1，即“有效”的，否则标记为0，即“无效”的。

这样做的逻辑是：如果一个byte完全翻转，都无法带来执行路径的变化，那么这个byte很有可能是属于”data”，而非”metadata”（例如size, flag等），对整个fuzzing的意义不大。所以，在随后的一些变异中，会参考effector map，跳过那些“无效”的byte，从而节省了执行资源。

2.arithmetic，进行加减操作

在bitflip变异全部进行完成后，便进入下一个阶段：arithmetic。与bitflip类似的是，arithmetic根据目标大小的不同，也分为了多个子阶段：

• arith 8/8，每次对8个bit进行加减运算，按照每8个bit的步长从头开始，即对文件的每个byte进行整数加减变异

 for (i = 0; i < len; i++) { 
    u8 orig = out_buf[i];//指向当前操作的字节 /* Let's consult the effector map... */ if (!eff_map[EFF_APOS(i)]) { 
   //查看当前字节是否是有效字节，如果不是就跳过当前字节 stage_max -= 2 * ARITH_MAX; continue; } for (j = 1; j <= ARITH_MAX; j++) { 
    u8 r = orig ^ (orig + j);//用于判断这次计算是否只是一个简单的位翻转 /* Do arithmetic operations only if the result couldn't be a product of a bitflip. */ //用于比较arithmetic是否只是对目标字节进行了bitflip里的那几种位翻转，如果是，就没必要继续了，因为前面做过了 if (!could_be_bitflip(r)) { 
    out_buf[i] = orig + j; if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry; stage_cur++; } else stage_max--; r = orig ^ (orig - j); if (!could_be_bitflip(r)) { 
    out_buf[i] = orig - j; if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry; stage_cur++; } else stage_max--; out_buf[i] = orig;//恢复当前字节，单一变量 } } 

• arith 16/8，每次对16个bit进行加减运算，按照每8个bit的步长从头开始，即对文件的每个word进行整数加减变异
• arith 32/8，每次对32个bit进行加减运算，按照每8个bit的步长从头开始，即对文件的每个dword进行整数加减变异

加减变异的上限，在config.h中的宏ARITH_MAX定义，默认为35。所以，对目标整数会进行+1, +2, …, +35, -1, -2, …, -35的变异。特别地，由于整数存在大端序和小端序两种表示方式，AFL会贴心地对这两种整数表示方式都进行变异。

此外，AFL还会智能地跳过某些arithmetic变异。第一种情况就是前面提到的effector map：如果一个整数的所有bytes都被判断为“无效”，那么就跳过对整数的变异。第二种情况是之前bitflip已经生成过的变异：如果加/减某个数后，其效果与之前的某种bitflip相同，那么这次变异肯定在上一个阶段已经执行过了，此次便不会再执行。

3.interest

下一个阶段是interest，具体可分为：

• interest 8/8，每次对8个bit进替换，按照每8个bit的步长从头开始，即对文件的每个byte进行替换

for (i = 0; i < len; i++) { 
    u8 orig = out_buf[i];//指向当前字节 /* Let's consult the effector map... */ if (!eff_map[EFF_APOS(i)]) { 
   //检测当前字节是不是有效位 stage_max -= sizeof(interesting_8); continue; } //对每个字节，用所有的interesting依次替换一次 for (j = 0; j < sizeof(interesting_8); j++) { 
    /* Skip if the value could be a product of bitflips or arithmetics. */ //检查这次替换是不是和之前的位翻转或者算术部分是一样的结果 if (could_be_bitflip(orig ^ (u8)interesting_8[j]) || could_be_arith(orig, (u8)interesting_8[j], 1)) { 
    stage_max--; continue; } out_buf[i] = interesting_8[j];//替换 if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry; out_buf[i] = orig;//复原 stage_cur++; } } 

• interest 16/8，每次对16个bit进替换，按照每8个bit的步长从头开始，即对文件的每个word进行替换
• interest 32/8，每次对32个bit进替换，按照每8个bit的步长从头开始，即对文件的每个dword进行替换

而用于替换的”interesting values”，是AFL预设的一些比较特殊的数：

static s8 interesting_8[] = { 
    INTERESTING_8 };//9 static s16 interesting_16[] = { 
    INTERESTING_8, INTERESTING_16 };//9+10=19 static s32 interesting_32[] = { 
    INTERESTING_8, INTERESTING_16, INTERESTING_32 };//9+10+8=27 

这些数的定义：

#define INTERESTING_8 \ -128, /* Overflow signed 8-bit when decremented */ \ -1, /* */ \ 0, /* */ \ 1, /* */ \ 16, /* One-off with common buffer size */ \ 32, /* One-off with common buffer size */ \ 64, /* One-off with common buffer size */ \ 100, /* One-off with common buffer size */ \ 127 /* Overflow signed 8-bit when incremented */ #define INTERESTING_16 \ -32768, /* Overflow signed 16-bit when decremented */ \ -129, /* Overflow signed 8-bit */ \ 128, /* Overflow signed 8-bit */ \ 255, /* Overflow unsig 8-bit when incremented */ \ 256, /* Overflow unsig 8-bit */ \ 512, /* One-off with common buffer size */ \ 1000, /* One-off with common buffer size */ \ 1024, /* One-off with common buffer size */ \ 4096, /* One-off with common buffer size */ \ 32767 /* Overflow signed 16-bit when incremented */ #define INTERESTING_32 \ -LL, /* Overflow signed 32-bit when decremented */ \ -, /* Large negative number (endian-agnostic) */ \ -32769, /* Overflow signed 16-bit */ \ 32768, /* Overflow signed 16-bit */ \ 65535, /* Overflow unsig 16-bit when incremented */ \ 65536, /* Overflow unsig 16 bit */ \ , /* Large positive number (endian-agnostic) */ \  /* Overflow signed 32-bit when incremented */ 

与之前类似，effector map仍然会用于判断是否需要变异；此外，如果某个interesting value，是可以通过bitflip或者arithmetic变异达到，那么这样的重复性变异也是会跳过的。

4.dictionary

进入到这个阶段，就接近deterministic fuzzing的尾声了。具体有以下子阶段：

• user extras (over)，从头开始，将用户提供的tokens依次替换到原文件中
• user extras (insert)，从头开始，将用户提供的tokens依次插入到原文件中
• auto extras (over)，从头开始，将自动检测的tokens依次替换到原文件中

对于用户提供的tokens，AFL先按照长度从小到大进行排序。这样做的好处是，只要按照顺序使用排序后的tokens，那么后面的token不会比之前的短，从而每次覆盖替换后不需要再恢复到原状。

随后，AFL会检查tokens的数量，如果数量大于预设的MAX_DET_EXTRAS（默认值为200），那么对每个token会根据概率来决定是否进行替换：

 for (j = 0; j < extras_cnt; j++) { 
    /* Skip extras probabilistically if extras_cnt > MAX_DET_EXTRAS. Also skip them if there's no room to insert the payload, if the token is redundant, or if its entire span has no bytes set in the effector map. */ //UR(extras_cnt) >= MAX_DET_EXTRAS)用于概率跳过 if ((extras_cnt > MAX_DET_EXTRAS && UR(extras_cnt) >= MAX_DET_EXTRAS) || extras[j].len > len - i || !memcmp(extras[j].data, out_buf + i, extras[j].len) || !memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, extras[j].len))) { 
    stage_max--; continue; } 

user extras (insert)

这一子阶段是对用户提供的tokens执行插入变异。不过与上一个子阶段不同的是，此时并没有对tokens数量的限制，所以全部tokens都会从原文件的第1个byte开始，依次插入第1个byte的前面，由于token之前已经按小到大排序了，所以后面的token可以直接覆盖前面的，对第1个byte执行完所有token之后，会先将第1个byte复原，然后对第2个byte开始一样的操作；此外，由于原文件并未发生替换，所以effector map不会被使用。

 for (i = 0; i <= len; i++) { 
   //依次对当前测试用例的所有字节操作 stage_cur_byte = i; for (j = 0; j < extras_cnt; j++) { 
   //依次对tokens操作 if (len + extras[j].len > MAX_FILE) { 
   //token插入后不能超过file极限，否则跳过当前token stage_max--; continue; } /* Insert token */ memcpy(ex_tmp + i, extras[j].data, extras[j].len);//先把token插到对应位置 /* Copy tail */ memcpy(ex_tmp + i + extras[j].len, out_buf + i, len - i);//再把后面的原文件剩余字节插入 if (common_fuzz_stuff(argv, ex_tmp, len + extras[j].len)) { 
    ck_free(ex_tmp); goto abandon_entry; } stage_cur++; } /* Copy head */ ex_tmp[i] = out_buf[i];//接下来要测试第i+1个字节了，把前面的字节内容恢复 } 

auto extras (over)

这一项与”user extras (over)”很类似，区别在于，这里的tokens是最开始bitflip阶段自动生成的。另外，自动生成的tokens总量会由USE_AUTO_EXTRAS限制（默认为10）。

五、变异-非确定性变异：

1.havoc

对于非dumb mode的主fuzzer来说，完成了上述deterministic fuzzing后，便进入了充满随机性的这一阶段；对于dumb mode或者从fuzzer来说，则是直接从这一阶段开始。

havoc，顾名思义，是充满了各种随机生成的变异，是对原文件的“大破坏”。具体来说，havoc包含了对原文件的多轮变异，每一轮都是将多种方式组合（stacked）而成：

• 随机选取某个bit进行翻转

 FLIP_BIT(out_buf, UR(temp_len << 3));//随机选取一位翻转 

• 随机选取某个byte，将其设置为随机的interesting value

out_buf[UR(temp_len)] = interesting_8[UR(sizeof(interesting_8))];//随机选取一个字节，用interesting的随机字段替换 

• 随机选取某个word，并随机选取大、小端序，将其设置为随机的interesting value

if (temp_len < 2) break; //随机选取两个字节，替换位interesting_16，并且还会随机大小端的方式替换 if (UR(2)) { 
    *(u16*)(out_buf + UR(temp_len - 1)) = interesting_16[UR(sizeof(interesting_16) >> 1)]; } else { 
    *(u16*)(out_buf + UR(temp_len - 1)) = SWAP16( interesting_16[UR(sizeof(interesting_16) >> 1)]); } 

• 随机选取某个dword，并随机选取大、小端序，将其设置为随机的interesting value
• 随机选取某个byte，对其减去一个随机数
• 随机选取某个byte，对其加上一个随机数
• 随机选取某个word，并随机选取大、小端序，对其减去一个随机数
• 随机选取某个word，并随机选取大、小端序，对其加上一个随机数
• 随机选取某个dword，并随机选取大、小端序，对其减去一个随机数
• 随机选取某个dword，并随机选取大、小端序，对其加上一个随机数
• 随机选取某个byte，将其设置为随机数
• 随机删除一段bytes
• 随机选取一个位置，插入一段随机长度的内容，其中75%的概率是插入原文中随机位置的内容，25%的概率是插入一段随机选取的数
• 随机选取一个位置，替换为一段随机长度的内容，其中75%的概率是替换成原文中随机位置的内容，25%的概率是替换成一段随机选取的数
• 随机选取一个位置，用随机选取的token（用户提供的或自动生成的）替换
• 随机选取一个位置，用随机选取的token（用户提供的或自动生成的）插入

不仅如此，AFL还会设置一个随机值use_stacking ，对当前测试用例做use_stacking 次上述的随机变异

u32 use_stacking = 1 << (1 + UR(HAVOC_STACK_POW2));//1随机左移1-7位，也是2，4，8，16，32，64，128， for (i = 0; i < use_stacking; i++) { 
    ...... havoc代码； ...... } 

2.splice

历经了如此多的考验，文件的变异也进入到了最后的阶段：splice。如其意思所说，splice是将两个seed文件拼接得到新的文件，并对这个新文件继续执行havoc变异。

locate_diffs(in_buf, new_buf, MIN(len, target->len), &f_diff, &l_diff); /* f_diff指向两个测试用例第一个不同的字节，如果<0，就说明两个测试用例一样 l_diff指向两个测试用例最后一个不同的字节，如果<2，说明从第3个字节开始的内容都一样 f_diff == l_diff说明就一个字节不同 以上三种情况就不需要拼接了 */ if (f_diff < 0 || l_diff < 2 || f_diff == l_diff) { 
    ck_free(new_buf); goto retry_splicing; } 

寻找插入位置：

//在第一个不同和最后一个不同的字节间随机找一个拼接位置 split_at = f_diff + UR(l_diff - f_diff);