目录

• source code fuzzing的基本流程
• Instrument
  • afl-gcc插桩分析
• Fuzz target
  • 初始化
  • setup_shm()
  • Fork Server
    • 关键执行函数fuzz_one()
    • fuzz_one CALIBRATION
    • fuzz_one TRIMMING
    • fuzz_one PERFORMANCE SCORE
  • fuzz_one变异
    • SIMPLE BITFLIP (+dictionary construction)阶段
      • bitflip 1/1
      • arith 16/8
      • arith 32/8
    • INTERESTING VALUES阶段
      • interest 8/8
      • user extras (insert)
      • auto extras (over)
    • RANDOM HAVOC阶段
    • SPLICING阶段

前言
这是我读了部分AFL源码的产物，有些地方很可能表述或理解地并不准确，欢迎交流和指教。

source code fuzzing的基本流程

（图片引用自AFL++文档）
主要内容是Instrument target和Fuzz本体

Instrument

根据compiler的选择不同会影响后续fuzzing效率

• LTO mode (afl-clang-lto/afl-clang-lto++)

  LTO（Link Time Optimization）链接时优化是链接期间的程序优化，多个中间文件通过链接器合并在一起，并将它们组合为一个程序，缩减代码体积，因此链接时优化是对整个程序的分析和跨模块的优化。

  需要llvm 11+，这是当前afl支持的效率最高的选择（理论上，实际情况会受未知因素影响，比如fuzzing libxml2的时候），也意味着编译要花更长时间

• LLVM mode (afl-clang-fast/afl-clang-fast++)

  依赖LLVM的optimizer，稳定性较高的编译器，用的比较多，可以跨平台（non-x86）编译

  实现了编译级插桩，效果比汇编级插桩更好

• GCC_PLUGIN mode (afl-gcc-fast/afl-g++-fast)

  效果和LLVM mode差不多，不过依赖的是GCC_plugin，也比较推荐

• GCC mode (afl-gcc/afl-g++) (or afl-clang/afl-clang++ for clang)

  相较其他编译器，没别的特色，基本用不到

从编译的实现流程上理解插桩模式差异

afl-gcc插桩分析

考虑到afl的插桩方式随编译器的选择而变化，从最简单的afl-gcc开始入手。

先把一个简单程序用afl-gcc编译，代码来源

很显然，只要输出指定字符串，程序就会访问到非法内存，同时程序根据输入头部的不同产生多个分支，从而测试AFL输入样本的变异过程
编译中程序显示对52处位置进行了插桩

把编译得到的文件丢进IDA，可以发现编译生成的函数中有多个__afl_maybe_log，显然他们由afl-gcc的插桩产生。

当执行到这段代码，fuzzer知道这段代码被触发，从而统计每次输入样本的边缘覆盖率。

正常生成可执行文件过程为

• 预处理：.c生成.i
• 编译：.i生成.s，到汇编语言
• 汇编：.s生成.o，汇编语言到机器语言
• 链接：由.o生成可执行文件

IR：高级语言到汇编的中间语言，可以解决平台间的差异

llvm负责IR到汇编语言的转化，并在此过程中进行插桩

插桩的代码执行时与更新共享内存中的执行信息，从而对代码覆盖率进行统计

使用afl-clang-fast编译，产生的函数__sanitizer_cov_trace_pc_guard，就是llvm插桩的经典例子

ASAN(Address Sanitizer)：在数据前后添加禁止访问区域，访问到后报错

• 存在一个判断标准，判断合法地址和非法地址
• 每个数据只能写在给他分配的位置上
• 会把原本相邻的变量隔离
• 需要更长的编译时间

Fuzz target

源代码比较长，我就挑了几个重要函数的源码进行分析

初始化

进入main函数，首先获取时间，循环读取参数

下面接了一大堆目录处理和前期检查的函数

setup_shm()

forkserver、主进程、fork出的子进程间存在共享内存，这段共享内存由内核管理，其中存储数组，记录每次样本执行访问到的代码路径

• 如果是forkserver，通过管道通信
• fork出的子进程通过共享内存传输结果

该函数用于配置共享内存和virgin_bits

将三个状态数组全部初始化为255（0~65535）

• virgin_bits记录尚未覆盖的区域
• virgin_tmout记录timeout时的tuple信息
• virgin_crash记录crash时的tuple信息

int shmget(key_t key, size_t size, int shmflg)申请共享大小为65536的共享内存

• 第一参数为 IPC_PRIVATE，使用IPC_PRIVATE创建的IPC对象, key值属性为0，和IPC对象的编号就没有了对应关系。这样毫无关系的进程，就不能通过key值来得到IPC对象的编号（因为这种方式创建的IPC对象的key值都是0）。因此，这种方式产生的IPC对象，和无名管道类似，不能用于毫无关系的进程间通信。但也不是一点用处都没有，仍然可以用于有亲缘关系的进程间通信。
• 第二参数 MAP_SIZE 为65536，是这一段内存的大小。
• 第三参数 IPC_CREAT | IPC_EXCL | 0600，代表这段内存的权限
  • 0600权限代表，只有创建者可以进行读写
  • IPC_CREAT 如果共享内存不存在，则创建一个共享内存，否则打开操作。
  • IPC_EXCL 只有在共享内存不存在的时候，新的共享内存才建立，否则就产生错误。

void shmat(int shm_id, const void shm_addr, int shmflg) 访问共享内存

• 第一参数指定这一段共享内存的id

• 第二参数为NULL一般，shm_addr指定共享内存连接到当前进程中的地址位置，通常为空，表示让系统来选择共享内存的地址。

• 第三参数shm_flg是一组标志位，通常为0。

• 返回一个指向共享内存起始位置的指针，存入trace_bits

Fork Server

forkserver功能

• 由主进程创建的子进程，负责fork出fuzz对象，使用pipe和主进程通信
• 管道只能在父子进程间通信，如果要实现祖孙进程通信，需要设置环境变量，孙进程通过环境变量获取文件描述符

调用链perform_dry_run(use_argv) -> calibrate_case(argv, q, use_mem, 0, 1) -> init_forkserver(argv)

perform_dry_run()：每个测试用例都执行一次，仅对初始输入执行一次测试，以确保程序按预期运行

calibrate_case()：校准一个新的测试用例，只在处理输入目录和发现新路径是执行

init_forkserver()：用于初始化forkserver

1. 初始参数中st_pipe[2], ctl_pipe[2]分别为状态管道和控制管道

   1 2 3 4 5 6

   EXP_ST void init_forkserver(char** argv) {    static struct itimerval it;  int st_pipe[2], ctl_pipe[2];  int status;  s32 rlen;

2. 接着fork出子进程forkserver并使其脱离主进程

   1 2 3 4 5 6 7

   forksrv_pid = fork();//子进程为forkserver   if (forksrv_pid < 0) PFATAL("fork() failed");  //fork失败   if (!forksrv_pid) {   //forkserver执行  …………   setsid();  //让子进程完全独立运行

3. 重定向forkserver的stdout、stderr到dev_null_fd

   视情况重定向stdin

   • 若定义了out_file，则把stdin重定向到dev_null_fd
   • 否则关闭out_fd（间接关闭了stdin）

   完成后对FORKSRV_FD和FORKSRV_FD + 1进行重定向

   linux之dup和dup2函数解析

   1 2 3 4 5 6 7 8 9 10

   dup2(dev_null_fd, 1); dup2(dev_null_fd, 2); if (out_file) {   dup2(dev_null_fd, 0); } else {   dup2(out_fd, 0);   close(out_fd); } if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed"); if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed");

4. 执行execv之前还有一系列参数设置，这里先略过，如果execv执行失败，那么主进程将通过trace_bits = EXEC_FAIL_SIG（位于bitmap）获得信息。

   1 2 3 4 5 6 7

   execv(target_path, argv);   /* Use a distinctive bitmap signature to tell the parent about execv()    falling through. */   *(u32*)trace_bits = EXEC_FAIL_SIG; exit(0);

5. 主进程的pipe为fsrv_ctl_fd = ctl_pipe[1]用于写;fsrv_st_fd = st_pipe[0]用于读; 设置完成后等待forkserver的返回状态信号

   • 如果长度正好为4（exit），一切正常，直接返回
   • 否则分类处理异常信号，打印消息并退出
     • crash
     • timeout

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

   /* Close the unneeded endpoints. */ close(ctl_pipe[0]); close(st_pipe[1]);   fsrv_ctl_fd = ctl_pipe[1]; fsrv_st_fd  = st_pipe[0]; //等待返回消息 it.it_value.tv_sec = ((exec_tmout * FORK_WAIT_MULT) / 1000); it.it_value.tv_usec = ((exec_tmout * FORK_WAIT_MULT) % 1000) * 1000;   setitimer(ITIMER_REAL, &it, NULL); rlen = read(fsrv_st_fd, &status, 4);   it.it_value.tv_sec = 0; it.it_value.tv_usec = 0; setitimer(ITIMER_REAL, &it, NULL); if (rlen == 4) {   OKF("All right - fork server is up.");   return; }

fuzzing策略

各种初始设置完成后进入while循环，执行fuzzing主程序

先来看一个比较重要的数据结构queue_entry的特点

• 存储输入样本
• 存储每次执行样本后的基本信息
• 链表连接

其中top_rated里面存放的是bitmap中每个位置当前最短路径

cull_queue()

功能：每次执行fuzz_one之前，简化队列

1. 如果是dumb_mode或者score_changed为0（即上一次fuzz没有产生更好的路径），直接返回

   1	if (dumb_mode || !score_changed) return;

2. 遍历队列，还原favored设置

   1 2 3 4 5

   q = queue; while (q) {   q->favored = 0;   q = q->next; }

3. 循环取出处于top_rate中并且被temp_v标记的用例，每取出一个，清除temp_v中所有属于这个entry的bit，并设置它的favored位，令queued_favored，如果这个用例还没被fuzz过，令pending_favored++，标记优先执行

   1 2 3 4 5 6 7 8 9 10 11

   for (i = 0; i < MAP_SIZE; i++)   if (top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {     u32 j = MAP_SIZE >> 3;     while (j--)       if (top_rated[i]->trace_mini[j])         temp_v[j] &= ~top_rated[i]->trace_mini[j];       top_rated[i]->favored = 1;     queued_favored++;     if (!top_rated[i]->was_fuzzed) pending_favored++;   }

4. 简化队列,标记冗余项

   1 2 3 4 5

   q = queue;   while (q) {     mark_as_redundant(q, !q->favored);     q = q->next;   }

if (!queue_cur)

功能：判断一次循环是否结束，是则初始化队列

queue_cur指向当前队列中元素，为空说明遍历到结尾

不为空则直接下一步

1. 记录轮数、重置状态

   1 2 3 4

   queue_cycle++;    current_entry     = 0;   cur_skipped_paths = 0;    queue_cur         = queue;

2. seek_to的值来源于find_start_position()，找到fuzzer重启后的开始位置

   （只在fuzzer重启的第一个循环里用到）这里把queue_cur抬高到seek_to位置，恢复重启前的状态

   1 2 3 4 5

   while (seek_to) {   current_entry++;   seek_to--;   queue_cur = queue_cur->next; }

3. 展示状态，就是命令行面板，每次状态更新或在其他状况下就会调用一次

   1	show_stats();

4. 非终端模式下输出循环数

   1 2 3 4

   if (not_on_tty) {         ACTF("Entering queue cycle %llu.", queue_cycle);         fflush(stdout);       }

5. queue_path不变，说明一整个循环未发现新路径，设置cycles_wo_finds+1或者use_splicing=1，他注释说会更换策略，但如果设置了-d参数，其实本来用的就是splicing，直接计数就行，cycles_wo_finds只是根据它的数量判断现在是否可以结束fuzzing，没别的影响

   1 2 3 4 5 6

   if (queued_paths == prev_queued) {           if (use_splicing) cycles_wo_finds++; else use_splicing = 1;         } else cycles_wo_finds = 0;       prev_queued = queued_paths;

6. 设置prev_queued为上一次的结果

   1	prev_queued = queued_paths;

7. 如果设置了相关参数，sync_fuzzers()可以从其他fuzzer获取测试用例

   1 2	if (sync_id && queue_cycle == 1 && getenv("AFL_IMPORT_FIRST"))         sync_fuzzers(use_argv);

关键执行函数fuzz_one()

终于到了最关键的地方

fuzz_one从当前队列中取一个用例执行

fuzz成功返回0，跳过或bailed out返回1

1. 进来先判断是否有favored, non-fuzzed用例需要执行

   如果有，则有99%的概率跳过在它之前的用例

   1 2 3 4

   if (pending_favored){    if ((queue_cur->was_fuzzed || !queue_cur->favored) &&         UR(100) < SKIP_TO_NEW_PROB) return 1; }

2. 即使没有需要优先fuzz的用例，非dumb_mode下，当前用例不是favored，队列中超过10个元素的情况下

   • 当前已运行超过2轮，未被fuzz过的，跳过概率75%（就是说第一二次循环就会跳过很大一部分，这是由于perform_dry_run里已经跑过一轮测试了）
   • 否则，跳过概率95%

   1 2 3 4 5 6 7

   else if (!dumb_mode && !queue_cur->favored && queued_paths > 10) {     if (queue_cycle > 1 && !queue_cur->was_fuzzed) {       if (UR(100) < SKIP_NFAV_NEW_PROB) return 1;     } else {       if (UR(100) < SKIP_NFAV_OLD_PROB) return 1;     }   }

3. 直接把当前测试用例映射到内存，提高效率

   1	orig_in = in_buf = mmap(0, len, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);

4. out_buf不是从文件读，这里相当于直接用了malloc(len+1)，即使mmap也不能提高效率

   1	out_buf = ck_alloc_nozero(len);

fuzz_one CALIBRATION

只有存在cal_failed被标记才会执行

cal_failed在calibrate_case()中，发生以下情况会+1

• 若测试时发生crash_mode(-C设置crash_mode为2，否则为0？)以外的fault
• 非dumb_mode，且第一次测试运行后trace_bits为空

同时afl允许我们通过设置，即使发生上述情况，也不在此阶段执行CALIBRATION（通过令cal_failed=3）

该判定位于perform_dry_run()

• 设置timeout_given =2，则忽略FAULT_TMOUT
• 未设置crash_mode时，设置环境变量AFL_SKIP_CRASHES为1，忽略FAULT_CRASH

然而，出现上述问题会使cal_failures++，若报错比例过高，就会要求你检查设置

回到fuzz_one，若校准错误小于3

让存在校准问题的用例再次校准

• 出现FAULT_ERROR，说明无法运行，直接放弃抢救，报错
• 出现crash_mode，接着往下运行
• 其他任何情况都跳过，cur_skipped_paths++

fuzz_one TRIMMING

非dumb_mode且该case尚未trim时执行

最后结果存储在out_buf

trim_case(char** argv, struct queue_entry* q, u8* in_buf)

1. 长度小于5直接返回

2. len_p2=2^x > q->len

   remove_len取len_p2/16与4的最大值

   1 2	len_p2 = next_p2(q->len); remove_len = MAX(len_p2 / TRIM_START_STEPS, TRIM_MIN_BYTES);

3. 循环判断remove_len是否大于最小步长max(len_p2 /1024，4），满足则继续

   否则跳转到7

   1	while (remove_len >= MAX(len_p2 / TRIM_END_STEPS, TRIM_MIN_BYTES))

4. 格式化remove_len到tmp

   1	sprintf(tmp, "trim %s/%s", DI(remove_len), DI(remove_len));

5. 内部循环，根据 remove_pos, trim_avail生成新case

   1 2 3 4 5 6 7

   while (remove_pos < q->len){ write_with_gap(in_buf, q->len, remove_pos, trim_avail); fault = run_target(argv, exec_tmout); cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST); if (cksum == q->exec_cksum){……} else remove_pos += remove_len }

   static void write_with_gap(void* mem, u32 len, u32 skip_at, u32 skip_len)

   功能：删除skip_at开始skip_len长度的内容，新内容存储于mem（此处为in_buf）

   运行一次新case，确认当前删除是否影响bitmap

   • 如果不影响，保存这次缩减
   • 否则remove_pos后移步长remove_len

6. remove_len/2，回到3进行判断

   1	remove_len >>= 1;

7. needs_write为1（在5的if中设置）说明case需要更新,把in_buf内容写入文件，并更新bitmap信息

   1 2 3 4 5

   if (needs_write){ ck_write(fd, in_buf, q->len, q->fname); memcpy(trace_bits, clean_trace, MAP_SIZE); update_bitmap_score(q); }

fuzz_one PERFORMANCE SCORE

1. 调用calculate_score(queue_cur)计算当前queue_cur的score

2. 如果设置了skip_deterministic或者queue_cur->was_fuzzed或者queue_cur->passed_det=1

   如果当前的queue_cur->exec_cksum % master_max不等于master_id - 1

   跳转havoc_stage

fuzz_one变异

考虑到这部分代码比较长，我主要从功能上入手，结合部分代码分析

变异分为6个阶段

• SIMPLE BITFLIP (+dictionary construction)阶段
• ARITHMETIC INC/DEC 阶段
• INTERESTING VALUES阶段
• DICTIONARY STUFF阶段
• RANDOM HAVOC阶段
• SPLICING阶段

SIMPLE BITFLIP (+dictionary construction)阶段

按位翻转，每次都是比特位级别的操作，从 1bit 到 32bit

_ar是操作对象，_br指明操作第几个字节(_bf) >> 3中的第几个bit(128 >> ((_bf) & 7))（从高位到低位）

一个异或相当于实现了对一个指定bit位的翻转

bitflip 1/1

1. 第一个翻转会遍历case中的每一位，每次翻转1个bit
2. 如果翻转后，common_fuzz_stuff()返回1，就直接跳过整个case，否则把这个bit再翻转回来

3. 检测token并添加

   1	maybe_add_auto(a_collect, a_len);

   从注释上理解token得概念：如果在某一段连续bit上进行连续翻转后，都能让程序产生新的路径，就称连续翻转的这些bit为一个token

common_fuzz_stuff(char** argv, u8* out_buf, u32 len)

1. 用新的case运行程序，获取fault

   1 2	write_to_testcase(out_buf, len); fault = run_target(argv, exec_tmout);

2. 检测fault值

   1 2 3 4 5 6

   if (fault == FAULT_TMOUT) {     if (subseq_tmouts++ > TMOUT_LIMIT) {       cur_skipped_paths++;       return 1;     }   } else subseq_tmouts = 0;

   • 如果FAULT_TMOUT并且subseq_tmouts（fuzz每个case时置零）未超出限制，返回1

   • 若不是FAULT_TMOUT，subseq_tmouts=0

3. 用户要求进程终止，返回1
4. save_if_interesting()
5. 返回0

bitflip 2/1

每次连续反转2个bit，步长为1bit

bitflip 4/1

每次连续反转2个bit，步长为1bit

bitflip 8/8

增加了effector map，每次连续反转8个bit，步长为8bit

与之前找token的方式相似，如果byte翻转生成了新路径，就让这个byte在effector map中位置为1，否则为0。目的也是让后续变异参考，确认哪些位置是关键的参数，绕过无用的数据。

初始只有第一个、最后一个位置为1

每次发现新路径设置1

发现有效位超过90%直接全为1

注意，如果采用dumb mode或从fuzzer后续不会用到effector map的结果

bitflip 16/8

每次连续反转16个bit，步长为8bit

bitflip 32/8

每次连续反转32个bit，步长为8bit

ARITHMETIC INC/DEC 阶段

目的是测试易于整数溢出的数据

与位翻转不同，从 8bit 级别开始，而且每次进行的是加减运算操作

arith 8/8

每次对8bit进行加减运算，步长8bit

1. case遍历

   1 2 3

   for (i = 0; i < len; i++){ u8 orig = out_buf[i]; }

   orig为每次操作的位置

2. effector map为0直接跳过

   1	if (!eff_map[EFF_APOS(i)])

3. 循环进行前后异或，一共ARITH_MAX=35轮

   1	for (j = 1; j <= ARITH_MAX; j++)

4. org与orig+j进行异或

   1	u8 r = orig ^ (orig + j);

5. 要求每次产生的case不能与bitflip产生的相同，否则直接跳过

   通过orig+j的方式生成新的case进行测试

   1 2 3 4 5 6 7 8 9

   if (!could_be_bitflip(r)) {     stage_cur_val = j;   out_buf[i] = orig + j;     if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;   stage_cur++;   } else stage_max--;

6. 与上一步相似，使用org-j生成新的case进行测试

   1 2 3 4 5 6

   r =  orig ^ (orig - j); if (!could_be_bitflip(r)) {   stage_cur_val = -j;   out_buf[i] = orig - j;   …… } else stage_max--;

7. 恢复原case

   1	out_buf[i] = orig;

arith 16/8

每次对16bit进行加减运算，步长8bit，对小端、大端加减法都进行测试

arith 32/8

每次对32bit进行加减运算，步长8bit，对小端、大端加减法都进行测试

INTERESTING VALUES阶段

使用“interesting values”对文件内容进行替换，替换内容为一系列确定的值

interest 8/8

每次对8bit进行替换变异，步长8bit

1. case遍历

   1	for (i = 0; i < len; i++)

2. eff_map检验不为0

   1	if (!eff_map[EFF_APOS(i)])

3. 替换内容遍历

   1	for (j = 0; j < sizeof(interesting_8); j++)

4. 要求新case不能被bitfilp和arith生成过

   1 2	if (could_be_bitflip(orig ^ (u8)interesting_8[j]) ||           could_be_arith(orig, (u8)interesting_8[j], 1))

5. 朴实无华的执行并恢复原case

   1 2 3 4

   stage_cur_val = interesting_8[j]; out_buf[i] = interesting_8[j]; if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry; out_buf[i] = orig;

interest 16/8

每次对16bit进行替换变异，步长8bit

interest 32/8

每次对32bit进行替换变异，步长8bit

DICTIONARY STUFF阶段

用户提供的字典里有token，用来替换要进行变异的文件内容，如果用户没提供就使用 bitflip 自动生成的 token

user extras (over)

以8bit为步长，标记起始位置开始，替换为token

1. 每个字节都替换一遍

   1	for (i = 0; i < len; i++)

2. 遍历用户字典

   1	for (j = 0; j < extras_cnt; j++)

3. 出现以下情况，直接下一条token

   1 2 3 4

   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)))

   • 字典token数>200，随机生成一个小于字典token数，仍>=200
   • 替换token后长度超过case原大小
   • case中数据与token一致
   • eff_map为0

4. 替换，执行

   1 2 3

   last_len = extras[j].len; memcpy(out_buf + i, extras[j].data, last_len);  if (common_fuzz_stuff(argv, out_buf, len))

5. 所有token结束后恢复，跳回步骤1

   1	memcpy(out_buf + i, in_buf + i, last_len);

user extras (insert)

以8bit为步长，标记起始位置插入token

auto extras (over)

以8bit为步长，标记起始位置开始，替换为在bitflip阶段生成的token

这是deterministic steps的最后一步

我们可以在这里设置完成状态

RANDOM HAVOC阶段

进行很大程度的杂乱破坏，随机组合，规则比较杂，但目的一致

SPLICING阶段

通过将两个case按一定规则进行拼接，得到一个新case

HAVOC和SPLICING是相结合的，拼接case后会回到havoc进行随机变异

参考文章：

1. AFL源码阅读笔记之gcc与fuzz部分https://bbs.pediy.com/thread-265936.htm
2. AFL 源码分析https://blog.csdn.net/song_lee/article/details/108244627
3. 漏洞挖掘技术之 AFL 项目分析https://bbs.pediy.com/thread-249912.htm

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课