作者：rk700

Part 1：AFL內部實現細節小記

AFL(American Fuzzy Lop)是一款開源的fuzzing工具。最近我對其代碼進行了簡要的閱讀，大致總結了一些AFL的實現細節，在此記錄整理。

代碼插樁

使用AFL，首先需要通過afl-gcc/afl-clang等工具來編譯目標，在這個過程中會對其進行插樁。

我們以afl-gcc為例。如果閱讀文件afl-gcc.c便可以發現，其本質上只是一個gcc的wrapper。我們不妨添加一些輸出，從而在調用execvp()之前打印全部命令行參數，看看afl-gcc所執行的究竟是什么：

gcc /tmp/hello.c -B /root/src/afl-2.52b -g -O3 -funroll-loops -D__AFL_COMPILER=1 -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1

可以看到，afl-gcc最終調用gcc，并定義了一些宏，設置了一些參數。其中最關鍵的就是-B /root/src/afl-2.52b這條。根據gcc --help可知，-B選項用于設置編譯器的搜索路徑，這里便是設置成/root/src/afl-2.52b(是我設置的環境變量AFL_PATH的值，即AFL目錄，因為我沒有make install)。

如果了解編譯過程，那么就知道把源代碼編譯成二進制，主要是經過”源代碼”->”匯編代碼”->”二進制”這樣的過程。而將匯編代碼編譯成為二進制的工具，即為匯編器assembler。Linux系統下的常用匯編器是as。不過，編譯完成AFL后，在其目錄下也會存在一個as文件，并作為符號鏈接指向afl-as。所以，如果通過-B選項為gcc設置了搜索路徑，那么afl-as便會作為匯編器，執行實際的匯編操作。

所以，AFL的代碼插樁，就是在將源文件編譯為匯編代碼后，通過afl-as完成。

接下來，我們繼續閱讀文件afl-as.c。其大致邏輯是處理匯編代碼，在分支處插入樁代碼，并最終再調用as進行真正的匯編。具體插入代碼的部分如下：

fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32, R(MAP_SIZE));

這里通過fprintf()將格式化字符串添加到匯編文件的相應位置。篇幅所限，我們只分析32位的情況，trampoline_fmt_32的具體內容如下：

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";

這一段匯編代碼，主要的操作是：

  • 保存edi等寄存器
  • 將ecx的值設置為fprintf()所要打印的變量內容
  • 調用方法__afl_maybe_log()
  • 恢復寄存器

__afl_maybe_log作為插樁代碼所執行的實際內容，會在接下來詳細展開，這里我們只分析"movl $0x%08x, %%ecx\n"這條指令。

回到fprintf()命令：

fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32, R(MAP_SIZE));

可知R(MAP_SIZE)即為上述指令將ecx設置的值，即為。根據定義，宏MAP_SIZE為64K，我們在下文中還會看到他；R(x)的定義是(random() % (x))，所以R(MAP_SIZE)即為0到MAP_SIZE之間的一個隨機數。

因此，在處理到某個分支，需要插入樁代碼時，afl-as會生成一個隨機數，作為運行時保存在ecx中的值。而這個隨機數，便是用于標識這個代碼塊的key。在后面我們會詳細介紹這個key是如何被使用的。

fork server

編譯target完成后，就可以通過afl-fuzz開始fuzzing了。其大致思路是，對輸入的seed文件不斷地變化，并將這些mutated input喂給target執行，檢查是否會造成崩潰。因此，fuzzing涉及到大量的fork和執行target的過程。

為了更高效地進行上述過程，AFL實現了一套fork server機制。其基本思路是：啟動target進程后，target會運行一個fork server；fuzzer并不負責fork子進程，而是與這個fork server通信，并由fork server來完成fork及繼續執行目標的操作。這樣設計的最大好處，就是不需要調用execve()，從而節省了載入目標文件和庫、解析符號地址等重復性工作。如果熟悉Android的話，可以將fork server類比為zygote。

接下來，我們來看看fork server的具體運行原理。首先，fuzzer執行fork()得到父進程和子進程，這里的父進程仍然為fuzzer，子進程則為target進程，即將來的fork server。

forksrv_pid = fork();

而父子進程之間，是通過管道進行通信。具體使用了2個管道，一個用于傳遞狀態，另一個用于傳遞命令：

int st_pipe[2], ctl_pipe[2];

對于子進程（fork server），會進行一系列設置，其中包括將上述兩個管道分配到預先指定的fd，并最終執行target：

  if (!forksrv_pid) {
...
    if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed");
    if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed");
...
    execv(target_path, argv);

對于父進程（fuzzer），則會讀取狀態管道的信息，如果一切正常，則說明fork server創建完成。

  fsrv_st_fd  = st_pipe[0];
...
  rlen = read(fsrv_st_fd, &status, 4);
...
  /* If we have a four-byte "hello" message from the server, we're all set.
Otherwise, try to figure out what went wrong. */

  if (rlen == 4) {
    OKF("All right - fork server is up.");
    return;
  }

接下來，我們來分析fork server是如何與fuzzer通信的。

fork server側的具體操作，也是在之前提到的方法__afl_maybe_log()中。首先，通過寫入狀態管道，fork server會通知fuzzer，其已經準備完畢，可以開始fork了，而這正是上面提到的父進程等待的信息：

  "__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"
  " addl $12, %esp\n"
  "\n"
  " cmpl $4, %eax\n"
  " jne __afl_fork_resume\n"

接下來，fork server進入等待狀態__afl_fork_wait_loop，讀取命令管道，直到fuzzer通知其開始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"

一旦fork server接收到fuzzer的信息，便調用fork()，得到父進程和子進程：

  " call fork\n"
  "\n"
  " cmpl $0, %eax\n"
  " jl __afl_die\n"
  " je __afl_fork_resume\n"

子進程是實際執行target的進程，其跳轉到__afl_fork_resume。在這里會關閉不再需要的管道，并繼續執行：

  "__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"

父進程則仍然作為fork server運行，其會將子進程的pid通過狀態管道發送給fuzzer，并等待子進程執行完畢；一旦子進程執行完畢，則再通過狀態管道，將其結束狀態發送給fuzzer；之后再次進入等待狀態__afl_fork_wait_loop：

  " /* 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"

以上就是fork server的主要邏輯，現在我們再回到fuzzer側。在fork server啟動完成后，一旦需要執行某個測試用例，則fuzzer會調用run_target()方法。在此方法中，便是通過命令管道，通知fork server準備fork；并通過狀態管道，獲取子進程pid：

    s32 res;

    /* In non-dumb mode, we have the fork server up and running, so simply
tell it to have at it, and then read back PID. */

    if ((res = write(fsrv_ctl_fd, &prev_timed_out, 4)) != 4) {
...
    if ((res = read(fsrv_st_fd, &child_pid, 4)) != 4) {
...

隨后，fuzzer再次讀取狀態管道，獲取子進程退出狀態，并由此來判斷子進程結束的原因，例如正常退出、超時、崩潰等，并進行相應的記錄。

    if ((res = read(fsrv_st_fd, &status, 4)) != 4) {
...
  /* Report outcome to caller. */

  if (WIFSIGNALED(status) && !stop_soon) {

    kill_signal = WTERMSIG(status);

    if (child_timed_out && kill_signal == SIGKILL) return FAULT_TMOUT;

    return FAULT_CRASH;

  }

共享內存

作為fuzzer，AFL并不是像無頭蒼蠅那樣對輸入文件無腦地隨機變化（其實也支持這種方式，即dumb模式），其最大特點就是會對target進行插樁，以輔助mutated input的生成。具體地，插樁后的target，會記錄執行過程中的分支信息；隨后，fuzzer便可以根據這些信息，判斷這次執行的整體流程和代碼覆蓋情況。

AFL使用共享內存，來完成以上信息在fuzzer和target之間的傳遞。具體地，fuzzer在啟動時，會執行setup_shm()方法進行配置。其首先調用shemget()分配一塊共享內存，大小MAP_SIZE為64K:

shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);

分配成功后，該共享內存的標志符會被設置到環境變量中，從而之后fork()得到的子進程可以通過該環境變量，得到這塊共享內存的標志符：

shm_str = alloc_printf("%d", shm_id);
if (!dumb_mode) setenv(SHM_ENV_VAR, shm_str, 1);

并且，fuzzer本身，會使用變量trace_bits來保存共享內存的地址：

trace_bits = shmat(shm_id, NULL, 0);

在每次target執行之前，fuzzer首先將該共享內容清零：

memset(trace_bits, 0, MAP_SIZE);

接下來，我們再來看看target是如何獲取并使用這塊共享內存的。相關代碼同樣也在上面提到的方法__afl_maybe_log()中。首先，會檢查是否已經將共享內存映射完成：

  " /* Check if SHM region is already mapped. */\n"
  "\n"
  " movl __afl_area_ptr, %edx\n"
  " testl %edx, %edx\n"
  " je __afl_setup\n"

__afl_area_ptr中保存的就是共享內存映射到target的內存空間中的地址，如果其不是NULL，便保存在ebx中繼續執行；否則進一步跳轉到__afl_setup。

__afl_setup處會做一些錯誤檢查，然后獲取環境變量AFL_SHM_ENV的內容并將其轉為整型。查看其定義便可知，這里獲取到的，便是之前fuzzer保存的共享內存的標志符。

  "__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"
  " pushl %ecx\n"
  "\n"
  " pushl $.AFL_SHM_ENV\n"
  " call getenv\n"
  " addl $4, %esp\n"
  "\n"
  " testl %eax, %eax\n"
  " je __afl_setup_abort\n"
  "\n"
  " pushl %eax\n"
  " call atoi\n"
  " addl $4, %esp\n"

最后，通過調用shmat()，target將這塊共享內存也映射到了自己的內存空間中，并將其地址保存在__afl_area_ptr及edx中。由此，便完成了fuzzer與target之間共享內存的設置。

  " pushl $0 /* shmat flags */\n"
  " pushl $0 /* requested addr */\n"
  " pushl %eax /* SHM ID */\n"
  " call shmat\n"
  " 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"

注記：如果使用了fork server模式，那么上述獲取共享內存的操作，是在fork server中進行；隨后fork出來的子進程，只需直接使用這個共享內存即可。

分支信息的記錄

現在，用于通信的共享內存已準備完畢，接下來我們看看具體通信的是什么。

由官網文檔可知，AFL是根據二元tuple(跳轉的源地址和目標地址)來記錄分支信息，從而獲取target的執行流程和代碼覆蓋情況，其偽代碼如下：

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

我們再回到方法__afl_maybe_log()中。上面提到，在target完成準備工作后，共享內存的地址被保存在寄存器edx中。隨后執行以下代碼：

  "__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"
  " xorl %ecx, %edi\n"
  " shrl $1, %ecx\n"
  " movl %ecx, __afl_prev_loc\n"
#else

  " movl %ecx, %edi\n"
#endif /* ^!COVERAGE_ONLY */

  "\n"
#ifdef SKIP_COUNTS

  " orb $1, (%edx, %edi, 1)\n"
#else

  " incb (%edx, %edi, 1)\n"

這里對應的便正是文檔中的偽代碼。具體地，變量__afl_prev_loc保存的是前一次跳轉的”位置”，其值與ecx做異或后，保存在edi中，并以edx（共享內存）為基址，對edi下標處進行加一操作。而ecx的值右移1位后，保存在了變量__afl_prev_loc中。

那么，這里的ecx，保存的應該就是偽代碼中的cur_location了。回憶之前介紹代碼插樁的部分：

static const u8* trampoline_fmt_32 = 
...
  "movl $0x%08x, %%ecx\n"
  "call __afl_maybe_log\n"

在每個插樁處，afl-as會添加相應指令，將ecx的值設為0到MAP_SIZE之間的某個隨機數，從而實現了偽代碼中的cur_location = <COMPILE_TIME_RANDOM>;。

因此，AFL為每個代碼塊生成一個隨機數，作為其“位置”的記錄；隨后，對分支處的”源位置“和”目標位置“進行異或，并將異或的結果作為該分支的key，保存每個分支的執行次數。用于保存執行次數的實際上是一個哈希表，大小為MAP_SIZE=64K，當然會存在碰撞的問題；但根據AFL文檔中的介紹，對于不是很復雜的目標，碰撞概率還是可以接受的：

   Branch cnt | Colliding tuples | Example targets
  ------------+------------------+-----------------
        1,000 | 0.75%            | giflib, lzo
        2,000 | 1.5%             | zlib, tar, xz
        5,000 | 3.5%             | libpng, libwebp
       10,000 | 7%               | libxml
       20,000 | 14%              | sqlite
       50,000 | 30%              | -

如果一個目標過于復雜，那么AFL狀態面板中的map_density信息就會有相應的提示：

┬─ map coverage ─┴───────────────────────┤
│    map density : 3.61% / 14.13%        │
│ count coverage : 6.35 bits/tuple       │
┼─ findings in depth ────────────────────┤

這里的map density，就是這張哈希表的密度。可以看到，上面示例中，該次執行的哈希表密度僅為3.61%，即整個哈希表差不多有95%的地方還是空的，所以碰撞的概率很小。不過，如果目標很復雜，map density很大，那么就需要考慮到碰撞的影響了。此種情況下的具體處理方式可見官方文檔。

另外，比較有意思的是，AFL需要將cur_location右移1位后，再保存到prev_location中。官方文檔中解釋了這樣做的原因。假設target中存在A->A和B->B這樣兩個跳轉，如果不右移，那么這兩個分支對應的異或后的key都是0，從而無法區分；另一個例子是A->B和B->A，如果不右移，這兩個分支對應的異或后的key也是相同的。

由上述分析可知，之前提到的共享內存，被用于保存一張哈希表，target在這張表中記錄每個分支的執行數量。隨后，當target執行結束后，fuzzer便開始對這張表進行分析，從而判斷代碼的執行情況。

分支信息的分析

首先，fuzzer對trace_bits（共享內存）進行預處理：

classify_counts((u32*)trace_bits);

具體地，target是將每個分支的執行次數用1個byte來儲存，而fuzzer則進一步把這個執行次數歸入以下的buckets中：

static const u8 count_class_lookup8[256] = {

  [0]           = 0, 
  [1]           = 1, 
  [2]           = 2, 
  [3]           = 4, 
  [4 ... 7]     = 8, 
  [8 ... 15]    = 16,
  [16 ... 31]   = 32,
  [32 ... 127]  = 64,
  [128 ... 255] = 128

};

舉個例子，如果某分支執行了1次，那么落入第2個bucket，其計數byte仍為1；如果某分支執行了4次，那么落入第5個bucket，其計數byte將變為8，等等。

這樣處理之后，對分支執行次數就會有一個簡單的歸類。例如，如果對某個測試用例處理時，分支A執行了32次；對另外一個測試用例，分支A執行了33次，那么AFL就會認為這兩次的代碼覆蓋是相同的。當然，這樣的簡單分類肯定不能區分所有的情況，不過在某種程度上，處理了一些因為循環次數的微小區別，而誤判為不同執行結果的情況。

隨后，對于某些mutated input來說，如果這次執行沒有出現崩潰等異常輸出，fuzzer還會檢查其是否新增了執行路徑。具體來說，是對trace_bits計算hash并來實現：

u32 cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

通過比較hash值，就可以判斷trace_bits是否發生了變化，從而判斷此次mutated input是否帶來了新路徑，為之后的fuzzing提供參考信息。

總結

以上便是對AFL內部細節的一些分析整理，其實還有很多地方值得進一步深入去研究，例如AFL是如何判斷一條路徑是否是favorite的、如何對seed文件進行變化，等等。如果只是使用AFL進行簡單的fuzzing，那么這些細節其實不需要掌握太多；但是如果需要在AFL的基礎上進一步針對特定目標進行優化，那么了解AFL的內部工作原理就是必須的了。

Part 2：AFL文件變異一覽

上一部分主要對AFL的一些實現細節進行了分析，但正如最后所說，還有很多細節講到。所以我又另外寫了這篇，專門介紹AFL是如何對輸入文件進行變異的。

總的來講，AFL維護了一個隊列(queue)，每次從這個隊列中取出一個文件，對其進行大量變異，并檢查運行后是否會引起目標崩潰、發現新路徑等結果。變異的主要類型如下：

  • bitflip，按位翻轉，1變為0，0變為1
  • arithmetic，整數加/減算術運算
  • interest，把一些特殊內容替換到原文件中
  • dictionary，把自動生成或用戶提供的token替換/插入到原文件中
  • havoc，中文意思是“大破壞”，此階段會對原文件進行大量變異，具體見下文
  • splice，中文意思是“絞接”，此階段會將兩個文件拼接起來得到一個新的文件

其中，前四項bitflip, arithmetic, interest, dictionary是非dumb mode（-d）和主fuzzer（-M）會進行的操作，由于其變異方式沒有隨機性，所以也稱為deterministic fuzzing；havoc和splice則存在隨機性，是所有狀況的fuzzer（是否dumb mode、主從fuzzer）都會執行的變異。

以下將對這些變異類型進行具體介紹。

bitflip

拿到一個原始文件，打頭陣的就是bitflip，而且還會根據翻轉量/步長進行多種不同的翻轉，按照順序依次為：

  • bitflip 1/1，每次翻轉1個bit，按照每1個bit的步長從頭開始
  • 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做翻轉

作為精妙構思的fuzzer，AFL不會放過每一個獲取文件信息的機會。這一點在bitflip過程中就體現的淋漓盡致。具體地，在上述過程中，AFL巧妙地嵌入了一些對文件格式的啟發式判斷。

自動檢測token

在進行bitflip 1/1變異時，對于每個byte的最低位(least significant bit)翻轉還進行了額外的處理：如果連續多個bytes的最低位被翻轉后，程序的執行路徑都未變化，而且與原始執行路徑不一致(檢測程序執行路徑的方式可見上篇文章中“分支信息的分析”一節)，那么就把這一段連續的bytes判斷是一條token。

例如，PNG文件中用IHDR作為起始塊的標識，那么就會存在類似于以下的內容：

........IHDR........

當翻轉到字符I的最高位時，因為IHDR被破壞，此時程序的執行路徑肯定與處理正常文件的路徑是不同的；隨后，在翻轉接下來3個字符的最高位時，IHDR標識同樣被破壞，程序應該會采取同樣的執行路徑。由此，AFL就判斷得到一個可能的token：IHDR，并將其記錄下來為后面的變異提供備選。

AFL采取的這種方式是非常巧妙的：就本質而言，這實際上是對每個byte進行修改并檢查執行路徑；但集成到bitflip后，就不需要再浪費額外的執行資源了。此外，為了控制這樣自動生成的token的大小和數量，AFL還在config.h中通過宏定義了限制：

/* Length limits for auto-detected dictionary tokens: */

#define MIN_AUTO_EXTRA      3
#define MAX_AUTO_EXTRA      32

/* Maximum number of auto-extracted dictionary tokens to actually use in fuzzing
   (first value), and to keep in memory as candidates. The latter should be much
   higher than the former. */

#define USE_AUTO_EXTRAS     10

#define MAX_AUTO_EXTRAS     (USE_AUTO_EXTRAS * 10)

對于一些文件來說，我們已知其格式中出現的token長度不會超過4，那么我們就可以修改MAX_AUTO_EXTRA為4并重新編譯AFL，以排除一些明顯不會是token的情況。遺憾的是，這些設置是通過宏定義來實現，所以不能做到運行時指定，每次修改后必須重新編譯AFL。

生成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，從而節省了執行資源。

由此，通過極小的開銷（沒有增加額外的執行次數），AFL又一次對文件格式進行了啟發式的判斷。看到這里，不得不嘆服于AFL實現上的精妙。

不過，在某些情況下并不會檢測有效字符。第一種情況就是dumb mode或者從fuzzer，此時文件所有的字符都有可能被變異。第二、第三種情況與文件本身有關：

/* Minimum input file length at which the effector logic kicks in: */

#define EFF_MIN_LEN         128

/* Maximum effector density past which everything is just fuzzed
   unconditionally (%): */

#define EFF_MAX_PERC        90

即默認情況下，如果文件小于128 bytes，那么所有字符都是“有效”的；同樣地，如果AFL發現一個文件有超過90%的bytes都是“有效”的，那么也不差那10%了，大筆一揮，干脆把所有字符都劃歸為“有效”。

arithmetic

在bitflip變異全部進行完成后，便進入下一個階段：arithmetic。與bitflip類似的是，arithmetic根據目標大小的不同，也分為了多個子階段：

  • arith 8/8，每次對8個bit進行加減運算，按照每8個bit的步長從頭開始，即對文件的每個byte進行整數加減變異
  • 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相同，那么這次變異肯定在上一個階段已經執行過了，此次便不會再執行。

interest

下一個階段是interest，具體可分為：

  • interest 8/8，每次對8個bit進替換，按照每8個bit的步長從頭開始，即對文件的每個byte進行替換
  • 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 };
static s16 interesting_16[] = { INTERESTING_8, INTERESTING_16 };
static s32 interesting_32[] = { INTERESTING_8, INTERESTING_16, INTERESTING_32 };

這些數的定義在config.h文件中：

/* List of interesting values to use in fuzzing. */

#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 \
  -2147483648LL, /* Overflow signed 32-bit when decremented */ \
  -100663046,    /* 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                   */ \
   100663045,    /* Large positive number (endian-agnostic) */ \
   2147483647    /* Overflow signed 32-bit when incremented */

可以看到，用于替換的基本都是可能會造成溢出的數。

與之前類似，effector map仍然會用于判斷是否需要變異；此外，如果某個interesting value，是可以通過bitflip或者arithmetic變異達到，那么這樣的重復性變異也是會跳過的。

dictionary

進入到這個階段，就接近deterministic fuzzing的尾聲了。具體有以下子階段：

  • user extras (over)，從頭開始，將用戶提供的tokens依次替換到原文件中
  • user extras (insert)，從頭開始，將用戶提供的tokens依次插入到原文件中
  • auto extras (over)，從頭開始，將自動檢測的tokens依次替換到原文件中

其中，用戶提供的tokens，是在詞典文件中設置并通過-x選項指定的，如果沒有則跳過相應的子階段。

user extras (over)

對于用戶提供的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. */

      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;

      }

這里的UR(extras_cnt)是運行時生成的一個0到extras_cnt之間的隨機數。所以，如果用戶詞典中一共有400個tokens，那么每個token就有200/400=50%的概率執行替換變異。我們可以修改MAX_DET_EXTRAS的大小來調整這一概率。

由上述代碼也可以看到，effector map在這里同樣被使用了：如果要替換的目標bytes全部是“無效”的，那么就跳過這一段，對下一段目標執行替換。

user extras (insert)

這一子階段是對用戶提供的tokens執行插入變異。不過與上一個子階段不同的是，此時并沒有對tokens數量的限制，所以全部tokens都會從原文件的第1個byte開始，依次向后插入；此外，由于原文件并未發生替換，所以effector map不會被使用。

這一子階段最特別的地方，就是變異不能簡單地恢復。之前每次變異完，在變異位置處簡單取逆即可，例如bitflip后，再進行一次同樣的bitflip就恢復為原文件。正因為如此，之前的變異總體運算量并不大。

但是，對于插入這種變異方式，恢復起來則復雜的多，所以AFL采取的方式是：將原文件分割為插入前和插入后的部分，再加上插入的內容，將這3部分依次復制到目標緩沖區中（當然這里還有一些小的優化，具體可閱讀代碼）。而對每個token的每處插入，都需要進行上述過程。所以，如果用戶提供了大量tokens，或者原文件很大，那么這一階段的運算量就會非常的多。直觀表現上，就是AFL的執行狀態欄中，"user extras (insert)"的總執行量很大，執行時間很長。如果出現了這種情況，那么就可以考慮適當刪減一些tokens。

auto extras (over)

這一項與"user extras (over)"很類似，區別在于，這里的tokens是最開始bitflip階段自動生成的。另外，自動生成的tokens總量會由USE_AUTO_EXTRAS限制（默認為10）。

havoc

對于非dumb mode的主fuzzer來說，完成了上述deterministic fuzzing后，便進入了充滿隨機性的這一階段；對于dumb mode或者從fuzzer來說，則是直接從這一階段開始。

havoc，顧名思義，是充滿了各種隨機生成的變異，是對原文件的“大破壞”。具體來說，havoc包含了對原文件的多輪變異，每一輪都是將多種方式組合（stacked）而成：

  • 隨機選取某個bit進行翻轉
  • 隨機選取某個byte，將其設置為隨機的interesting value
  • 隨機選取某個word，并隨機選取大、小端序，將其設置為隨機的interesting value
  • 隨機選取某個dword，并隨機選取大、小端序，將其設置為隨機的interesting value
  • 隨機選取某個byte，對其減去一個隨機數
  • 隨機選取某個byte，對其加上一個隨機數
  • 隨機選取某個word，并隨機選取大、小端序，對其減去一個隨機數
  • 隨機選取某個word，并隨機選取大、小端序，對其加上一個隨機數
  • 隨機選取某個dword，并隨機選取大、小端序，對其減去一個隨機數
  • 隨機選取某個dword，并隨機選取大、小端序，對其加上一個隨機數
  • 隨機選取某個byte，將其設置為隨機數
  • 隨機刪除一段bytes
  • 隨機選取一個位置，插入一段隨機長度的內容，其中75%的概率是插入原文中隨機位置的內容，25%的概率是插入一段隨機選取的數
  • 隨機選取一個位置，替換為一段隨機長度的內容，其中75%的概率是替換成原文中隨機位置的內容，25%的概率是替換成一段隨機選取的數
  • 隨機選取一個位置，用隨機選取的token（用戶提供的或自動生成的）替換
  • 隨機選取一個位置，用隨機選取的token（用戶提供的或自動生成的）插入

怎么樣，看完上面這么多的“隨機”，有沒有覺得暈？還沒完，AFL會生成一個隨機數，作為變異組合的數量，并根據這個數量，每次從上面那些方式中隨機選取一個（可以參考高中數學的有放回摸球），依次作用到文件上。如此這般喪心病狂的變異，原文件就大概率面目全非了，而這么多的隨機性，也就成了fuzzing過程中的不可控因素，即所謂的“看天吃飯”了。

splice

歷經了如此多的考驗，文件的變異也進入到了最后的階段：splice。如其意思所說，splice是將兩個seed文件拼接得到新的文件，并對這個新文件繼續執行havoc變異。

具體地，AFL在seed文件隊列中隨機選取一個，與當前的seed文件做對比。如果兩者差別不大，就再重新隨機選一個；如果兩者相差比較明顯，那么就隨機選取一個位置，將兩者都分割為頭部和尾部。最后，將當前文件的頭部與隨機文件的尾部拼接起來，就得到了新的文件。在這里，AFL還會過濾掉拼接文件未發生變化的情況。

cycle

于是乎，一個seed文件，在上述的全部變異都執行完成后，就...抱歉，還沒結束。

上面的變異完成后，AFL會對文件隊列的下一個進行變異處理。當隊列中的全部文件都變異測試后，就完成了一個"cycle"，這個就是AFL狀態欄右上角的"cycles done"。而正如cycle的意思所說，整個隊列又會從第一個文件開始，再次進行變異，不過與第一次變異不同的是，這一次就不需要再進行deterministic fuzzing了。

當然，如果用戶不停止AFL，那么seed文件將會一遍遍的變異下去。

總結

從以上介紹內容來看，AFL的文件變異，既有看天吃飯的成分，也有隨著fuzzing啟發式的判斷，結合了這么多種方式和巧妙的思路，不愧是大名鼎鼎的AFL。

Paper 本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/496/