AFL编译时插桩-安全客 - 安全资讯平台

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也设计了新的插桩方式。