0x00 前言
这篇文章主要从源码角度剖析AFL的编译时插桩（compile-time instrumentation）。AFL超级棒的一点在于其“灰盒”的特性：通过编译时插桩获动态获取目标程序的边覆盖信息。此外，AFL的forkserver机制使得AFL在运行过程中只需调用一次execv()函数，避免了多次调用execv()引起的开销（注：每执行一次execv()，都需要将目标程序加载到内存，进行链接等操作）。
注意：本文只分析能获得目标程序源码、开启forkserver下的AFL的一些内部实现，主要以afl-gcc为例对插桩代码进行解读，涉及到的源文件主要有afl-fuzz.c，afl-as.c，afl-as.h 和 afl-gcc.c。
0x01 插桩
AFL的插桩在汇编阶段实现。在获取目标程序源码后，首先需要通过afl-gcc/alf-g++编译目标程序，对目标程序进行插桩，得到插桩后的二进制文件。而从源文件到可执行文件，需要依次经过：预处理、编译、汇编、链接。其中，编译器将预处理后源文件编译成汇编语言，汇编器将汇编语言翻译成机器语言，而AFL的插桩就是在汇编阶段实现。
afl-gcc本质上是一个gcc的wrapper，afl-gcc通过设置gcc的-B选项设置编译器的搜索路径为 “afl_path/as”。我们编译好AFL后，会在afl的根目录下生成afl-gcc、as 和 afl-as等文件，其中，as作为符号链接指向afl-as。接下来，本文将着重分析 afl-as.h 和 afl-as.c文件。
/* afl-gcc.c */
u8 *afl_path = getenv("AFL_PATH");
if (afl_path) {
tmp = alloc_printf("%s/as", afl_path); //tmp = afl_path/as
if (!access(tmp, X_OK)) { //判断对tmp是否有执行权限
as_path = afl_path;
ck_free(tmp);
return;
}
ck_free(tmp);
}
cc_params[cc_par_cnt++] = "-B";
cc_params[cc_par_cnt++] = as_path;
...
afl-as.c首先通过函数add_instrumentation()在汇编层面对目标程序进行插桩，然后再调用gcc默认的汇编器as或者用户设置的汇编器执行真正的汇编过程（注：用户可以通过设置环境变量AFL_AS自定义要使用的汇编器 ）。
/* afl-as.c */
int main(int argc, char** argv) {
...
if (!just_version) add_instrumentation();
if (!(pid = fork())) {
execvp(as_params[0], (char**)as_params); //真正的汇编过程，as_params[0] = afl_as ? afl_as : (u8*)"as";
FATAL("Oops, failed to execute '%s' - check your PATH", as_params[0]);
}
...
}
add_instrumentation()插桩的大致思路：首先，只对.text段进行插桩，afl-as通过字符串匹配判断是不是.text段；其次，遍历目标程序对应的汇编文件的每一行代码，然后判断其是不是一个基本块的开始，如果是的话，就在这行代码之前进行插桩。
/* afl-as.c */
while (fgets(line, MAX_LINE, inf)) {
....
if (!strncmp(line + 2, "text\n", 5) ||
!strncmp(line + 2, "section\t.text", 13) ||
!strncmp(line + 2, "section\t__TEXT,__text", 21) ||
!strncmp(line + 2, "section __TEXT,__text", 21)) {
instr_ok = 1;
continue;
}
....
if (line[0] == '\t') {
if (line[1] == 'j' && line[2] != 'm' && R(100) < inst_ratio) {
fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32,
R(MAP_SIZE)); //插桩
ins_lines++;
}
continue;
}
...
}
先看一下fprintf函数的原型，其中第二个参数是格式化字符串，从第三个参数开始都将作为格式化字符串的参数，fprintf会将格式化字符串的最终输出打印到stream所指向的流中。
int fprintf(FILE *stream, const char *format, ...);
现在来分析插桩的语句，afl-as调用fprintf() 函数将桩代码插入目标程序的汇编文件：outf是一个指针，指向被插桩的汇编文件；trampoline_fmt_*是要插入的桩代码；R(MAP_SIZE)是0~MAP_SIZE之间的一个随机数，作为trampoline_fmt_*的参数，其实质是为当前基本块分配的ID。
fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32, R(MAP_SIZE))
接下来，以32位为例，分析插入的桩代码（从这里开始，本文的代码分析基本都是按照afl-as.h中桩代码的顺序分析的）：
/* afl-as.h */
static const u8* trampoline_fmt_32 =
"\n"
"/* --- AFL TRAMPOLINE (32-BIT) --- */\n"
"\n"
".align 4\n"
"\n"
"leal -16(%%esp), %%esp\n"
"movl %%edi, 0(%%esp)\n"
"movl %%edx, 4(%%esp)\n"
"movl %%ecx, 8(%%esp)\n"
"movl %%eax, 12(%%esp)\n"
"movl $0x%08x, %%ecx\n"
"call __afl_maybe_log\n"
"movl 12(%%esp), %%eax\n"
"movl 8(%%esp), %%ecx\n"
"movl 4(%%esp), %%edx\n"
"movl 0(%%esp), %%edi\n"
"leal 16(%%esp), %%esp\n"
"\n"
"/* --- END --- */\n"
"\n";
这段的代码的主要作用是调用__afl_maybe_log：
（1）第8-12行代码将寄存器edi、edx、ecx、eax保存到栈上。在后续的桩代码中会使用这几个寄存器，因此需要先保存这些寄存器的值到栈上，以便后续恢复寄存器的值。
（2）将寄存器ecx的值设置为fprintf()中传入的R(MAP_SIZE)，第13行中%08x对应的值是R(MAP_SIZE)，R(MAP_SIZE)的作用是生成一个0～MAP_SIZE间的随机数，作为当前基本块的ID。
（3）调用__afl_maybe_log。
（4）恢复edi等寄存器，对应于15行到第19行代码。
接下来看`__alf_maybe_log的实现：
"__afl_maybe_log:\n"
"\n"
" lahf\n"
" seto %al\n"
"\n"
" /* Check if SHM region is already mapped. */\n"
"\n"
" movl __afl_area_ptr, %edx\n" ;__afl_area_ptr指向共享内存
" testl %edx, %edx\n"
" je __afl_setup\n"
"\n"
在__afl_maybe_log里面，会首先判断共享内存是否映射完成（__afl_area_ptr指向共享内存，在后面会解释），如果未完成映射，会执行__afl_setup；如果映射完成，那么会执行 __afl_store。
0x02 共享内存
在AFL中，共享内存主要用于AFL进程和target进程通信。target进程可以通过写入共享内存更新一个测试用例对target的边覆盖信息；而AFL进程可以在target执行完毕后，通过访问共享内存获取target的边覆盖信息。具体地，在一个测试用例被执行前，共享内存会被重置；在执行该测试用例的过程中会被更新；当该测试用例执行完毕后，就会得到这个测试用例对应的共享内存。因此，共享内存能够表示目标程序执行某个测试用例后的边覆盖情况。
那，什么是共享内存呢？
共享内存是Linux下进程间的一种通信方式，两个进程将各自的一段虚拟地址空间映射到同一块物理地址上，然后这两个进程就可以通过操作这块物理地址进行通信。Linux下共享内存的具体实现方式：
（1）使用shmget()函数创建共享内存，并返回一个共享内存标识符shm_id 。shmget()原型为int shmget(key_t key, size_t size, int shmflg);。但是此时共享内存还不能被任何进程访问。
（2）shmat()函数的作用就是根据shm_id，将进程attach到共享内存上，即将进程虚拟地址空间中的一段内存映射到共享内存。shmat()的函数原型为void *shmat(int shmid, const void *shmaddr, int shmflg);。
AFL进程中共享内存设置
AFL通过共享内存获取一个测试用例对target的边覆盖信息。AFL开启后，会通过setup_shm()设置共享内存。
（1）首先通过shmget()创建大小为MAP_SIZE的共享内存：
shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);
（2）将共享内存标识符存储到环境变量，forkserver进程和target进程就可以通过环境变量访问共享内存标识符：
shm_str = alloc_printf("%d", shm_id); setenv(SHM_ENV_VAR, shm_str, 1);
（3）AFL使用变量 trace_bits attach到共享内存，然后AFL就可以通过trace_bits访问共享内存。在每次执行target之前，AFL会将trace_bits清零。
trace_bits = shmat(shm_id, NULL, 0);
target进程共享内存设置
在 __alf_maybe_log中，如果共享内存未完成映射，就会执行je __afl_setup设置共享内存。__afl_setup的作用是获取AFL进程设置的共享内存标识符，并在target进程内attach到共享内存。
"__afl_setup:\n"
"\n"
" /* Do not retry setup if we had previous failures. */\n"
"\n"
" cmpb $0, __afl_setup_failure\n"
" jne __afl_return\n"
"\n"
" /* Map SHM, jumping to __afl_setup_abort if something goes wrong.\n"
" We do not save FPU/MMX/SSE registers here, but hopefully, nobody\n"
" will notice this early in the game. */\n"
"\n"
" pushl %eax\n" ;将eax寄存器压栈
" pushl %ecx\n" ;将ecx寄存器压栈
"\n"
" pushl $.AFL_SHM_ENV\n" ;压入getenv的参数
" call getenv\n" ;getenv(AFL_SHM_ENV)，返回值存储在eax寄存器
" addl $4, %esp\n"
"\n"
" testl %eax, %eax\n" ;判断环境变量AFL_SHM_ENV是否存在
" je __afl_setup_abort\n" ;环境变量AFL_SHM_ENV不存在，共享内存映射失败
"\n"
" pushl %eax\n" ; eax = getenv(AFL_SHM_ENV)
" call atoi\n" ; eax = atoi(getenv(AFL_SHM_ENV))
" addl $4, %esp\n"
"\n"
" pushl $0 /* shmat flags */\n"
" pushl $0 /* requested addr */\n"
" pushl %eax /* SHM ID */\n"
" call shmat\n" ; eax = shmat(shm_id, 0, 0)
" addl $12, %esp\n"
"\n"
" cmpl $-1, %eax\n"
" je __afl_setup_abort\n"
"\n"
" /* Store the address of the SHM region. */\n"
"\n"
" movl %eax, __afl_area_ptr\n"
" movl %eax, %edx\n"
"\n"
" popl %ecx\n"
" popl %eax\n"
"\n"
分析上述桩代码，其实主要作了以下几件事：
（1）通过环境变量获取共享内存标识符shm_id：getenv(AFL_SHM_ENV)
（2）通过shmat()函数，将共享内存地址存储到__afl_area_ptr：___afl_area_ptr = shmat(shm_id, 0, 0)
0x03 forkserver
forkserver主要是为了避免频繁调用execve()引起的开销。在完成了共享内存映射后，就会进入forkserver核心部分，执行__afl_forkserver。
首先，看一下forkserver进程是如何创建的。AFL通过init_forkserver()进行forkserver相关的初始化工作：
（1）创建状态管道和命令管道，用于AFL和forkserver进程之间的通信。AFL通过写命令管道向forkserver发送命令，forkserver通过读命令管道接收AFL的发送的命令；forkserver通过写状态管道向AFL发送信息，AFL通过读状态管道接收forkserver发送的信息。
int st_pipe[2], ctl_pipe[2]；
（2）创建forkserver进程。 在forkserver进程中，首先对状态管道和命令管道进行重定位；之后，forkserver进程调用execv()，会在target第一个基本块处执行插入的桩代码，调用__afl_maybe_log，然后跳到__afl_setup设置共享内存。共享内存设置完毕后，就进入了__afl_forkserver。
dup2(ctl_pipe[0], FORKSRV_FD) 和 dup2(st_pipe[1], FORKSRV_FD +1）
execv(target_path, argv);
接下来看一下__afl_forkserver：
"__afl_forkserver:\n"
"\n"
" /* Enter the fork server mode to avoid the overhead of execve() calls. */\n"
"\n"
" pushl %eax\n"
" pushl %ecx\n"
" pushl %edx\n"
"\n"
" /* Phone home and tell the parent that we're OK. (Note that signals with\n"
" no SA_RESTART will mess it up). If this fails, assume that the fd is\n"
" closed because we were execve()d from an instrumented binary, or because\n"
" the parent doesn't want to use the fork server. */\n"
"\n"
" pushl $4 /* length */\n"
" pushl $__afl_temp /* data */\n"
" pushl $" STRINGIFY((FORKSRV_FD + 1)) " /* file desc */\n"
" call write\n" ; write(STRINGIFY((FORKSRV_FD + 1)), __afl_temp, 4)
" addl $12, %esp\n"
"\n"
" cmpl $4, %eax\n"
" jne __afl_fork_resume\n"
"\n"
forkserver首先会向状态管道写端（即 FORKSRV_FD + 1）写入4字节的内容，告诉AFL“我准备好fork了”，而AFL进程也会通过读状态管道，判断forkserver进程是否创建成功：
rlen = read(fsrv_st_fd, &status, 4);
forkserver创建成功后，就会进入__afl_fork_wait_loop ，forkserver会阻塞，直到读取命令管道成功：read(STRINGIFY(FORKSRV_FD), __afl_tmp, 4)，然后forkserver判断AFL是否发送了“fork一个子进程”的命令：
"__afl_fork_wait_loop:\n"
"\n"
" /* Wait for parent by reading from the pipe. Abort if read fails. */\n"
"\n"
" pushl $4 /* length */\n"
" pushl $__afl_temp /* data */\n"
" pushl $" STRINGIFY(FORKSRV_FD) " /* file desc */\n"
" call read\n" ; read(STRINGIFY(FORKSRV_FD), __afl_tmp, 4)
" addl $12, %esp\n"
"\n"
" cmpl $4, %eax\n"
" jne __afl_die\n"
"\n"
" /* Once woken up, create a clone of our process. This is an excellent use\n"
" case for syscall(__NR_clone, 0, CLONE_PARENT), but glibc boneheadedly\n"
" caches getpid() results and offers no way to update the value, breaking\n"
" abort(), raise(), and a bunch of other things :-( */\n"
"\n"
AFL在run_target()中通过命令管道向forkserver发送消息：
res = write(fsrv_ctl_fd, &prev_timed_out, 4)
当forkserver收到AFL创建一个子进程的命令后，就会调用fork()创建target进程（Linux下的fork()提供了copy-on-write机制，fork()开销很低）：
" call fork\n"
"\n"
" cmpl $0, %eax\n"
" jl __afl_die\n"
" je __afl_fork_resume\n"
在target进程里面，会跳到__afl_fork_resume执行，关闭文件描述符，恢复target的正常执行：
"__afl_fork_resume:\n"
"\n"
" /* In child process: close fds, resume execution. */\n"
"\n"
" pushl $" STRINGIFY(FORKSRV_FD) "\n"
" call close\n"
"\n"
" pushl $" STRINGIFY((FORKSRV_FD + 1)) "\n"
" call close\n"
"\n"
" addl $8, %esp\n"
"\n"
" popl %edx\n"
" popl %ecx\n"
" popl %eax\n"
" jmp __afl_store\n"
"\n"
在forkserver进程里面，也就是在父进程里面，会将target进程的PID写入状态管道，然后等待target进程结束。target进程结束后，forkserver会再次向AFL说“我准备好fork了”，并继续执行__afl_fork_wait_loop，等待AFL发送“fork一个子进程”的命令。
" /* In parent process: write PID to pipe, then wait for child. */\n"
"\n"
" movl %eax, __afl_fork_pid\n"
"\n"
" pushl $4 /* length */\n"
" pushl $__afl_fork_pid /* data */\n"
" pushl $" STRINGIFY((FORKSRV_FD + 1)) " /* file desc */\n"
" call write\n"
" addl $12, %esp\n"
"\n"
" pushl $0 /* no flags */\n"
" pushl $__afl_temp /* status */\n"
" pushl __afl_fork_pid /* PID */\n"
" call waitpid\n"
" addl $12, %esp\n"
"\n"
" cmpl $0, %eax\n"
" jle __afl_die\n"
"\n"
" /* Relay wait status to pipe, then loop back. */\n"
"\n"
" pushl $4 /* length */\n"
" pushl $__afl_temp /* data */\n"
" pushl $" STRINGIFY((FORKSRV_FD + 1)) " /* file desc */\n"
" call write\n"
" addl $12, %esp\n"
"\n"
" jmp __afl_fork_wait_loop\n"
forkserver创建完target进程后，需要将target进程的PID写道状态管道；而AFL进程则需要从状态管道中读出target进程的PID。
res = read(fsrv_st_fd, &child_pid, 4)
0x04 边覆盖记录
在__alf_maybe_log中，如果共享内存完成了映射，就会执行__afl_store，在共享内存中更新边覆盖情况。
"__afl_store:\n"
"\n"
" /* Calculate and store hit for the code location specified in ecx. There\n"
" is a double-XOR way of doing this without tainting another register,\n"
" and we use it on 64-bit systems; but it's slower for 32-bit ones. */\n"
"\n"
#ifndef COVERAGE_ONLY
" movl __afl_prev_loc, %edi\n" ;将__alf_prev_loc的值存储到寄存器edi
" xorl %ecx, %edi\n" ;将“__alf_prev_loc 异或 ecx”的值存储到edi寄存器中，相当于将边ID存储到了寄存器edi中
" shrl $1, %ecx\n" ;将ecx的值右移1位，然后存储至ecx寄存器中
" movl %ecx, __afl_prev_loc\n" ;将ecx寄存器的值存储到__afl_prev_loc中
#else
" movl %ecx, %edi\n"
#endif /* ^!COVERAGE_ONLY */
"\n"
#ifdef SKIP_COUNTS
" orb $1, (%edx, %edi, 1)\n"
#else
" incb (%edx, %edi, 1)\n"
#endif /* ^SKIP_COUNTS */
"\n"
__afl_store的作用是计算前一个基本块（pre_location）到当前基本块（cur_location）这条边的ID，然后统计其出现次数。具体地，AFL使用（pre_location >> 1) xor (cur_locatino) 的方式记录一条边；使用共享内存（存储在寄存器edx中）统计边的出现次数。在上述汇编代码中：
（1）ecx存储的是R(MAP_SIZE)得到的值，也就是存储着为当前这个基本块分配的ID，即伪代码中的cur_location；
（2）__afl_prev_loc表示上一个基本块的ID>>1；
（3）edx存储的是共享内存的地址。
（4）incb (%edx, %edi, 1)这条指令就在共享内存（edx）中，将这条边（edi）的出现次数+1。
__afl_store之后是__afl_return:\n。
"__afl_return:\n"
"\n"
" addb $127, %al\n"
" sahf\n"
" ret\n"
"\n"
关于插桩，可能会存在两个疑问：
（1）边覆盖不够精确，是否能够实现路径覆盖？边覆盖确实不够精确，但是目前来看，它还是简单实用的。论文Be Sensitive and Collaborative: Analyzing Impact of Coverage Metrics in Greybox Fuzzing对不同代码覆盖率统计方式对于fuzzing的影响进行了研究。
（2）trace_bits使用边ID作为索引，是否存在hash碰撞？答案是存在的，hash碰撞由两部分引起。首先，trace_bits的大小为64KB，每个索引对应的数据大小为1 byte，也就是说，最多能存放2^16条边，遇到边数大于2^16的目标程序，理论上会有概率存在碰撞；其次，边ID的计算方式没有过滤碰撞，因此这里也可能存在碰撞。为了解决hash碰撞，CollAFL提出了新的边ID计算方式，CSI-Fuzz也设计了新的插桩方式。
0x05 总结
AFL一共涉及三个进程，AFL进程，forkserver进程，以及targetg进程。AFL进程创建了forkserver进程，forkserver进程根据AFL的指令创建target进程。
AFL和forkserver通过管道进行通信。
AFL和target通过共享内存通信，获取目标程序代码覆盖信息。AFL通过trace_bits访问共享内存，target通过__afl_area_ptr访问共享内存。