未语之痕
未语之痕

AFL源码阅读

Ghostasky Ghostasky 收录于 Technology
 约 16500 字 预计阅读 33 分钟 

阅读源码的主要目标应该是：

  1. 理清静态插桩过程（gcc、clang、llvm mode）
  2. 理清 fuzz 过程：如何变异、如何将 input 传递给程序、如何收集覆盖度信息
  3. 理清 qemu mode 的插桩和执行过程

因此，我们决定阅读顺序：

  1. 阅读 afl-gcc.c 和 afl-as.c，即静态插桩相关代码
  2. 阅读 afl-tmin.c ，这个工具的用途是「将一个 input case 缩小，但与原 input 拥有相同的覆盖度」。它会完整地演示如何收集程序的覆盖度信息，而不涉及 afl-fuzz.c 中的其他流程。这将给我们提供一个绝佳的切面，以研究 AFL 收集覆盖度的方法
  3. 阅读 afl-fuzz.c

afl_gcc

afl-gcc 是 gcc, g++, clang, clang++ 的包装器。它的作用是设置一些编译参数，然后调用这些编译器

编译出来的 afl-clang, afl-g++ 等文件都是指向 afl-gcc 的软链接。

main 

int main(int argc, char **argv)
{
    if (isatty(2) && !getenv("AFL_QUIET"))
        SAYF(cCYA "afl-cc " cBRI VERSION cRST " by <lcamtuf@google.com>\n");
    else
        be_quiet = 1;
    if (argc < 2)
    {
        .....
    }
    // 从环境变量中获取afl-as的路径
    find_as(argv[0]);
    // 编辑参数
    edit_params(argc, argv);
    /*在CC前打印下参数：*/
    for (int i = 0; i < cc_par_cnt; i++)
        printf("\targ:%d : %s ", i, cc_params[i]);
    // 执行下游编译器
    execvp(cc_params[0], (char **)cc_params);
    FATAL("Oops, failed to execute '%s' - check your PATH", cc_params[0]);
    return 0;
}

find_as

主要工作：

  • 检查AFL_PATH环境变量是否存在，之后检查该目录下as文件，如果存在，赋值给as_path，返回
  • 如果环境变量和该文件都不存在，检查argv0变量，检查该目录下afl-as文件是否存在并且可访问，赋值后返回。
  • 都不存在，抛出异常，返回

edit_params

最关键的一步是加入了 -B as_path 这个 flag，使得下游编译器在汇编过程中，以 afl-as 替换了原生的汇编器。而具体的插桩过程，则是 afl-as 负责实现

主要工作：

  • 使用ck_alloc分配内存，大小为(argc+128)*sizeof(u8 *)
  • 检查argv[0]中是否存在\，如果没有，直接赋值给name；如果有，找到最后的\，并将后面的字符串给name
  • 将name与afl-clang比较（判断下游编译器是否是afl-clang）
    • 如果相同，置clang_mode为1，并将环境变量CLANG_ENV_VAR置1，之后比较name与afl-clang++
      • 如果相同，取环境变量AFL_CXX给cc_params[0]，如果环境变量不存在，则赋值clang++给cc_params[0]
      • 如果不同，取环境变量AFL_CC给cc_params[0]，如果环境变量不存在，则赋值clang给cc_params[0]
    • 如果不相同（判断下游编译器是否是afl-g++和afl-gcj）
      • 将name与afl-g++比较，如果相同，取环境变量AFL_CXX给cc_params[0]，如果环境变量不存在，则赋值g++给cc_params[0]
      • 如果不相同，继续将name与afl-gcj比较，取环境变量AFL_GCJ给cc_params[0]，如果环境变量不存在，则赋值gcj给cc_params[0]
      • 如果还不相同，取环境变量AFL_CC给cc_params[0]，如果环境变量不存在，则赋值gcc给cc_params[0]
  • 之后遍历argv参数
    • 跳过-B/integrated-as/-pipe
    • 如果存在-fsanitize=address或者-fsanitize=memory，置asan_set为1
    • 如果存在FORTIFY_SOURCE，置fortify_set为1
    • cc_params[cc_par_cnt++] = cur
  • 接下来设置cc_params的其他参数
    • 取之前设置的as_path，然后设置-B as_path
    • 如果clang_mode设置，则设置-no-integrated-as
    • 如果环境变量AFL_HARDEN存在，则设置-fstack-protector-all，进一步，如果fortify_set未设置，则设置-D_FORTIFY_SOURCE=2
    • 判断asan_set是否已设置，
      • 如果已设置，则设置环境变量AFL_USE_ASAN为1
      • 如果未设置，获取环境变量AFL_USE_ASAN，判断环境变量AFL_USE_MSAN和AFL_HARDEN是否存在，若都存在，设置-U_FORTIFY_SOURCE和-fsanitize=address
      • 如果未设置AFL_USE_ASAN环境变量，则获取AFL_USE_MSAN环境变量，并判断AFL_USE_ASAN和AFL_HARDEN环境变量是否设置，如果都存在，则设置-U_FORTIFY_SOURCE和-fsanitize=memory
    • 如果不存在AFL_DONT_OPTIMIZE环境变量，则设置-g -O3 -funroll-loops -D__AFL_COMPILER=1 -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1
    • 如果存在AFL_NO_BUILTIN环境变量，则设置xxxxxxxxxxx等
    • 最后设置cc_params[cc_par_cnt] = NULL终止编辑

afl_as

afl-as 是原生 GNU as 的 包装器

main

主要工作流程

  1. 初始化随机数种子
  2. 在汇编指令序列上插桩
  3. 修改 as 参数(edit_params)
  4. 调用 as 生成可执行文件，并清理现场

详细：

  • 读环境变量AFL_INST_RATIO的值
  • 初始化随机数种子
  • 设置环境变量AS_LOOP_ENV_VAR为1
  • 读取环境变量AFL_USE_ASAN和AFL_USE_MSAN的值，如果其中有一个为1，则设置sanitizer为1，且将inst_ratio除3，这是因为AFL无法在插桩的时候识别出ASAN specific branches，所以会插入很多无意义的桩，为了降低这种概率，粗暴的将整个插桩的概率都除以3
  • edit_params(argc, argv)
  • add_instrumentation()
  • fork出一个子进程，让子进程来执行execvp(as_params[0], (char **) as_params);
  • (waitpid(pid, &status, 0)
  • 读取环境变量AFL_KEEP_ASSEMBLY的值，如果没有设置这个环境变量，就unlink掉modified_file
int main(int argc, char **argv)
{
    s32 pid;
    u32 rand_seed;
    int status;
    u8 *inst_ratio_str = getenv("AFL_INST_RATIO");
    struct timeval tv;
    struct timezone tz;
    clang_mode = !!getenv(CLANG_ENV_VAR);
    if (isatty(2) && !getenv("AFL_QUIET"))
    {
        SAYF(cCYA "afl-as " cBRI VERSION cRST " by <lcamtuf@google.com>\n");
    }
    else
        be_quiet = 1;
    if (argc < 2)
    {
        SAYF("\n"
             "This is a helper application for afl-fuzz. It is a wrapper around GNU 'as',\n"
             "executed by the toolchain whenever using afl-gcc or afl-clang. You probably\n"
             "don't want to run this program directly.\n\n"
             "Rarely, when dealing with extremely complex projects, it may be advisable to\n"
             "set AFL_INST_RATIO to a value less than 100 in order to reduce the odds of\n"
             "instrumenting every discovered branch.\n\n");
        exit(1);
    }
    gettimeofday(&tv, &tz);                        // 获取当前时间
    rand_seed = tv.tv_sec ^ tv.tv_usec ^ getpid(); // 用于随机数生成的种子
    srandom(rand_seed);                            // 设置随机数种子
    edit_params(argc, argv);                       // 处理参数
    if (inst_ratio_str)
    {
        if (sscanf(inst_ratio_str, "%u", &inst_ratio) != 1 || inst_ratio > 100) // inst_ratio 为 0-100 之间的整数
            FATAL("Bad value of AFL_INST_RATIO (must be between 0 and 100)");
    }
    if (getenv(AS_LOOP_ENV_VAR))
        FATAL("Endless loop when calling 'as' (remove '.' from your PATH)");
    setenv(AS_LOOP_ENV_VAR, "1", 1);
    /* When compiling with ASAN, we don't have a particularly elegant way to skip
       ASAN-specific branches. But we can probabilistically compensate for
       that...
       zh: 当使用 ASAN 时，我们没有一个特别优雅的方法来跳过 ASAN 特定的分支。但是我们可以以概率补偿这一点...
       */
    // ASAN/MSAN 会插入一些分支，这里设置 inst_ratio 为原来的 1/3
    if (getenv("AFL_USE_ASAN") || getenv("AFL_USE_MSAN"))
    {
        sanitizer = 1;
        inst_ratio /= 3;
    }
    if (!just_version)
        add_instrumentation(); // 添加插桩
    if (!(pid = fork()))
    {
        execvp(as_params[0], (char **)as_params);
        FATAL("Oops, failed to execute '%s' - check your PATH", as_params[0]);
    }
    if (pid < 0)
        PFATAL("fork() failed");
    if (waitpid(pid, &status, 0) <= 0) // 等待子进程结束
        PFATAL("waitpid() failed");
    if (!getenv("AFL_KEEP_ASSEMBLY"))
        unlink(modified_file);
    exit(WEXITSTATUS(status));
}

edit_params

与afl_gcc的修改参数的逻辑类似：读入原来的汇编代码，生成一个插了桩的新汇编代码（存放在临时目录），调用 GNU as 来将新汇编代码转化成机器码。

  • 使用ck_alloc分配空间，大小为(argc + 32) * sizeof(u8 *)
  • 设置as_params参数，如果AFL_AS环境变量存在，则赋值给as_params，如果不存在，则设置为as
  • 获取临时目录给tmp_dir
  • 遍历argv[1]开始,到argv[argc-1]参数
    • 判断参数，如果是--64，则use_64bit置1，如果是--32，则use_64bit置0
    • as_params[as_par_cnt++] = argv[i];设置as_params的值为argv对应的参数值
  • 设置其他参数：
    • 读取argv[argc - 1]的值,赋给input_file的值,也就是传递的最后一个参数的值作为input_file
    • 比较input_file和tmp_dir//var/tmp///tmp/的前strlen(tmp_dir)/9/5个字节是否相同，如果不相同，就设置pass_thru为1
    • 设置modified_file的值为alloc_printf("%s/.afl-%u-%u.s", tmp_dir, getpid(),(u32) time(NULL));,简单的说就是tmp_dir/.afl-pid-time.s这样的字符串。
    • 设置as_params[as_par_cnt++] = modified_file
    • as_params[as_par_cnt] = NULL;

add_instrumentation

插桩过程的核心部分

可以写一段简单代码测试：

##include <stdio.h>

void work() {
    for(int i=1; i<=10; i++) {
        printf("Hello, world %d\n", i);
    }
}

int main(void) {
    work();
    return 0;
}

// AFL_DONT_OPTIMIZE=1 ../afl-gcc target.c -o target -O0 -fno-asynchronous-unwind-tables

之后观察插桩前后的汇编代码，可以看到在每一个基本块入口处，afl-as 插入了一段代码，除此之外，在整个程序的末尾，插入了一段 300 多行的 AFL main payload。

在每个 branch 开始的位置插入的代码，这类代码形如：

/* --- AFL TRAMPOLINE (64-BIT) --- */
.align 4

leaq -(128+24)(%rsp), %rsp
movq %rdx,  0(%rsp)
movq %rcx,  8(%rsp)
movq %rax, 16(%rsp)
movq $0x000078e0, %rcx
call __afl_maybe_log
movq 16(%rsp), %rax
movq  8(%rsp), %rcx
movq  0(%rsp), %rdx
leaq (128+24)(%rsp), %rsp
/* --- END --- */

AFL 白皮书中说，上述代码本质上实现了如下逻辑：

cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++; 
prev_location = cur_location >> 1;
__afl_maybe_log:
  lahf
  seto %al

  movq  __afl_area_ptr(%rip), %rdx
  testq %rdx, %rdx
  je    __afl_setup

//先检查共享内存区域是否已经映射，如果没有映射，就跳转到__afl_setup进行初始化；如果已经映射，就继续执行__afl_store，rdx指向共享内存区域

__afl_store:
  xorq __afl_prev_loc(%rip), %rcx
  xorq %rcx, __afl_prev_loc(%rip)
  shrq $1, __afl_prev_loc(%rip)

  incb (%rdx, %rcx, 1)

/*
执行流程：

1. 将目前存储着cur_loc的rcx与prev_loc进行异或
2. 将 prev_loc 设为 cur_loc （这里利用了异或运算的自反性）
3. 将 prev_loc 右移一位
4. 增加hit count

执行完后，恢复 eflags 并返回
*/
桩代码将几个寄存器的值保存在栈上，然后调用 __afl_maybe_log ；__afl_maybe_log 首先保存当前 EFLAGS 寄存器状态，然后检查 shm 区域是否准备好；如果已经准备好，则进入 __afl_store 过程，给 shm 区域增加 hit count 后返回。

处理输入文件，生成modified_file，将instrumentation插入所有适当的位置。

  • 如果input_file不为空，则打开；如果为空，则读取标准输
  • 打开modified_file对应的临时文件，
  • 从输入的文件逐行读取，并保存到line数组，每行最多读MAX_LINE(8192)，从line数组里将读取的内容写入到outf对应的文件里。

接下来是真正有趣的地方，首先，只想在.text段中插桩

  • 检查instrument_next和instr_ok是否都为 1，以及line是否以\t开始，且line[1]是否为字母
    • 如果都满足，向outf中写入trampoline_fmt，并将插桩计数器ins_lines++
    • 这其实是因为我们想要插入instrumentation trampoline到所有的标签，宏，注释之后
  • 首先要设置instr_ok的值，这个值是一个flag，instr_ok 为 1 表示当前处于 .text 段中，否则就不在。于是如果instr_ok为1，就会在分支处执行插桩逻辑，否则就不插桩。
  • 如果line的值为\t.[text\n|section\t.text|section\t__TEXT,__text|section __TEXT,__text]...其中之一，置instr_ok为1，然后跳到while头读下一行数据到line数组
  • 如果line的值为\t.[section\t|section |bss\n|data\n]...之一，则置instr_ok为0，然后跳到while头读下一行数据到line数组

            zh: 如果我们的mood适合插桩，检查函数名称或条件标签。这有点混乱，但本质上，我们想捕获:
                ^main:      - 函数入口点（始终插桩）
                ^.L0:       - GCC 分支标签
                ^.LBB0_0:   - clang 分支标签（但仅在 clang 模式下）
                ^\tjnz foo  - 条件分支
            ...但不是:
                ^# BB#0:    - clang 注释
                ^ # BB#0:   - 同上
                ^.Ltmp0:    - clang 非分支标签
                ^.LC0       - GCC 非分支标签
                ^.LBB0_0:   - 同上（在 GCC 模式下）
                ^\tjmp foo  - 非条件跳转
            此外，MacOS X 上的 clang 和 GCC 遵循不同的约定，标签没有前导点，因此稍后的 #ifdefs 中有奇怪的迷宫。

  • 插桩^\tjnz foo指令

    • 如果line的值为\tj[!m]...，且R(100) < inst_ratio，R(100)会返回一个100以内的随机数，inst_ratio是之前设置的插桩密度，默认为100，如果设置了asan之类的就会默认设置成30左右。
    • 根据use_64bit判断插桩内容，
      • define R(x) (random() % (x))，可能产生碰撞
      • 这里的R(x)实际上是用来区分每个桩的，也就是是一个标识
    • ins_lines++;

  • 检查该行中是否包含:，并以.开始

    • 如果以.开始，则代表想要插桩^.L0:或者^.LBB0_0:这样的 branch label，即style jump destination
      • 如果结果为真，则设置instrument_next = 1
    • 否则表示这是一个function，插桩^func:function entry point

  • 如果插桩计数器ins_lines不为0，完全拷贝input_file之后，依据架构，像outf中写入main_payload_64或者main_payload_32，然后关闭这两个文件

afl插桩就是通过汇编的前导命令来判断这是否是一个分支或者函数，之后插入instrumentation trampoline（插桩跳板），后面将讲这个东西

afl_tmin

afl-tmin 是一个简单的测试用例最小化器，它接受输入文件并尝试删除尽可能多的数据，同时使二进制文件保持崩溃状态或生成一致的仪器输出（该模式是根据最初观察到的行为自动选择的）。

它拿到一个 input 文件，尝试删除其中尽可能多的内容，但同时保持覆盖度。

有两个工作模式：

  • non-crash 模式，目标程序必须被插桩。afl-tmin 在缩小 input 的过程中，维持覆盖度不变。
  • crash 模式，目标程序可以被插桩，也可以不被插桩。afl-tmin 将保持程序 crash。

main

主要是 parse 一下输入参数，并做一些初始化工作

  • 根据 argv，设置变量。这包括原始 input 位置、优化结果的输出位置、目标程序运行时的输入文件该放在哪里（如果不是从 stdin 输入的话）、是否只考虑 edge 覆盖率而不考虑 hit count、是否将非 0 返回码视为 crash、程序内存限制、程序运行时间限制、是否使用 qemu 模式，以及一个神秘的 -B 选项，具体用途见注释。

  • 初始化shm

    • 其中的shmget函数，size 为 MAP_SIZE，它被预设为 (1 << 16)，即 65536 字节。

  • 设置几个信号处理函数，例如当用户按下 Ctrl+C 时，要优雅地结束程序。

  • 处理环境变量

  • 分析将要传递给目标程序的 argv（也就是 afl-tmin 自己的命令行中， – 之后的那部分）；如果有 @@，则把它覆写为输入文件位置 prog_in

  • 设置 qemu 相关参数。与我们无关。

  • 看一眼初始 input 文件。如果大于 10MB，就喷我们一句「Input file is too large」。

  • 调用 run_target() 进行一次 dry run。主要看是否超时、是否 crash。

  • 调用 minimize() 执行优化。

  • 删除 prog_in 文件并输出优化结果。

run_target

首先是fork之前：

static struct itimerval it;
int status = 0;

s32 prog_in_fd;
u32 cksum;

memset(trace_bits, 0, MAP_SIZE);// trace_bits就是共享内存区域
MEM_BARRIER();//告知编译器「not re-order memory accesses across the barrier」。这大概是作者在某次实验中，发现编译器的激进优化违反了自己意图（默认条件下是 -O3 编译的），故加这一句话来约束编译器。

//将 input 内容写进 prog_in 文件中，记录 fd
//由于父子进程共享 fd，故子进程也可以使用这个 fd。
//write_to_file的作用是删除prog_in 文件、重新创建prog_in 文件并以 rw 模式打开，所以父进程写入、子进程读取是没问题的。
prog_in_fd = write_to_file(prog_in, mem, len);

child_pid = fork();

if (child_pid < 0) PFATAL("fork() failed");

if (!child_pid) {
  // ... 子进程代码
}

接下来是fork之后的逻辑： 子进程部分：

  • 如果目标程序是吃 stdin 输入的，则将 stdin 重定向到 prog_in_fd，否则将 stdin 重定向到 /dev/null 。
  • 另外，将 stdout 和 stderr 重定向到 /dev/null。
  • 创建新的进程组，自己为 leader。
  • 设置内存限制。
  • execv 到目标程序。
  • 若 execv 调用失败，则把 shm 的前四个字节设为 0xfee1dead 并退出。
    if (!child_pid) // 子进程
    {
        struct rlimit r;
        // stdin 指向输入文件，stdout 和 stderr 指向 /dev/null
        if (dup2(use_stdin ? prog_in_fd : dev_null_fd, 0) < 0 ||
            dup2(dev_null_fd, 1) < 0 ||
            dup2(dev_null_fd, 2) < 0)
        {
            *(u32 *)trace_bits = EXEC_FAIL_SIG;
            PFATAL("dup2() failed");
        }
        close(dev_null_fd);
        close(prog_in_fd);
        setsid();
        if (mem_limit) // 设置内存限制
        {
            r.rlim_max = r.rlim_cur = ((rlim_t)mem_limit) << 20;
##ifdef RLIMIT_AS
            setrlimit(RLIMIT_AS, &r); /* Ignore errors */
##else
            setrlimit(RLIMIT_DATA, &r); /* Ignore errors */
##endif /* ^RLIMIT_AS */
        }
        r.rlim_max = r.rlim_cur = 0;
        setrlimit(RLIMIT_CORE, &r); /* Ignore errors */
        execv(target_path, argv); // 执行目标程序
        // 如果执行到这里，说明 execv() 失败了，将 shm 的前 4 个字节设置为 EXEC_FAIL_SIG
        *(u32 *)trace_bits = EXEC_FAIL_SIG;
        exit(0);
    }

于是，父进程只需要监控子进程的退出状态，即可知道目标程序是否崩溃；另外，从 shm 的前 4 字节，能得知 execv 调用是否失败。

父进程：

  • 给子进程定时，并等待子进程结束。
  • 对 hit count 分桶，并计算 hash，与原始 input 的运行 hash 比对。若一致，则本 input 有效。
    close(prog_in_fd);
	// 设置 timeout
    child_timed_out = 0;
    it.it_value.tv_sec = (exec_tmout / 1000);
    it.it_value.tv_usec = (exec_tmout % 1000) * 1000;
	// SIGALRM 的 handler 此前已被设为「kill 掉 child_pid」
    setitimer(ITIMER_REAL, &it, NULL);
    // 等待子进程结束
    if (waitpid(child_pid, &status, 0) <= 0)
        FATAL("waitpid() failed");
    child_pid = 0;
    it.it_value.tv_sec = 0;
    it.it_value.tv_usec = 0;

    setitimer(ITIMER_REAL, &it, NULL);

    MEM_BARRIER();
    // execv 是否成功执行
    if (*(u32 *)trace_bits == EXEC_FAIL_SIG)
        FATAL("Unable to execute '%s'", argv[0]);

    classify_counts(trace_bits);                       // 对 hit count 分桶
    apply_mask((u32 *)trace_bits, (u32 *)mask_bitmap); // 将 mask 应用到 hit count 上
    total_execs++;
    if (stop_soon)
    {

        SAYF(cRST cLRD "\n+++ Minimization aborted by user +++\n" cRST);
        close(write_to_file(out_file, in_data, in_len));
        exit(1);
    }
    // 如果执行超时，则返回 0，表示这个 input 应该忽略
    if (child_timed_out)
    {

        missed_hangs++;
        return 0;
    }
    // 如果发现目标程序 crash
    if (WIFSIGNALED(status) ||
        (WIFEXITED(status) && WEXITSTATUS(status) == MSAN_ERROR) ||
        (WIFEXITED(status) && WEXITSTATUS(status) && exit_crash))
    {

        if (first_run) // 如果是第一次执行，那么就将 crash_mode 设置为 1
            crash_mode = 1;

        if (crash_mode) // 如果是 crash mode，且不要求 crash 路径与原 input 相同，则立即报告 input 有效，该保留
        {
            if (!exact_mode)
                return 1;
        }
        else
        {
            // 是 non-crash mode，但现在 crash 了，说明这个 input 与原 input 路径不同，该丢弃
            missed_crashes++;
            return 0;
        }
    }
    else
        /* Handle non-crashing inputs appropriately. */
        if (crash_mode)
        {
            // 发现目标程序没有 crash，而目前处于 crash mode，则本 input 与原 input 路径不同，该丢弃
            missed_paths++;
            return 0;
        }
    // 对 shm 计算 hash，注意这里的 shm 已经是 hit count 分桶处理之后的了
    cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

    if (first_run)
        orig_cksum = cksum;
    // 若本 input 的 shm hash 与原始 input 相同，则本 input 有效，予以保留
    if (orig_cksum == cksum)
        return 1;
    missed_paths++;
    return 0;

classify_counts 函数负责将 hit count 分桶

AFL 的思路是这两个方案的折中——既要避免 corpus 爆炸，又要在循环次数增加的过程中给一些奖励。所以，AFL 设计了 8 个 hit count 桶 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+

classify_counts 函数的意图就很明确了：若没有打开 -e 开关，则将 hit count 分桶；若打开了 -e 开关，则只关心是否命中，不关心命中多少次。

classify_counts() 过程结束后，本质相同的 input，其生成的 shm 也相同了。接下来， apply_mask() 过程是配合 -B 开关用的，只留下我们所关心的那些 edge 的 hit count 信息。由于正常情况下，我们关心所有 edge，故 apply_mask() 对我们没有影响。 前文提到，shm 的大小是 65536 字节。如果将 shm 的全文都保留下来用于比较，会产生很大的开销（afl-fuzz 运行时，要把新 input 的运行路径与所有 corpus 的运行路径相比较）。因此，我们不妨用 shm 的「消息摘要」来代替它的全文。AFL 采用的 hash32() 是一个自创的简单算法，我们无需关心其细节。总之，它从 65536 字节的 shm 中，计算出 4 字节的消息摘要，用来代表这个 input 的执行路径。如果本 input 的 hash 与原始 input 相同，则本 input 是有效的；否则丢弃本 input。

minimize

结构：

  • 先做一遍 block normalization
  • 循环执行 block deletion、alphabet minimization、character minimization 三个优化，直到无法再进一步优化为止。
static void minimize(char** argv) {
  // ... BLOCK NORMALIZATION

next_pass:
  // ... BLOCK DELETION
  
  // ... ALPHABET MINIMIZATION

  // ... CHARACTER MINIMIZATION

  if (changed_any) goto next_pass;

finalize_all:

  // 输出结果
}

block normalization

  • 首先，输入被划分为大约 128 个块（除了最后一个块外，块长度为 2 的幂次）
  • 对于每个块，afl-tmin 尝试将其改为全 ‘0’，若其运行路径与原始 input 相同，则保留该更改。

block normalization 的意义在于，如果 input 中有一部分内容是不敏感的（例如，一个负责报告 bmp 图片尺寸的程序，显然不会关心像素颜色），则这部分不敏感内容块会被以 ‘0’ 代替。这对后续进行的优化有好处

block deletion

  • 首先将 input 分为 16 个块
  • 然后从前往后尝试删除每一个块
  • 结束一轮之后，将块大小减半，再尝试上述步骤，直到块大小为 1

另外，有一个小小的加速逻辑：从前往后删除块的过程中，若前一个块不可删除，且这个块与前一个块一模一样，则直接推断这个块也不可删除，不必去实际运行程序。由于 block normalization 过程过程产生了大量的连续 ‘0’，故这个加速逻辑是可以取得一定效果的。

alphabet minimization

这是一个非常简单的优化，旨在缩小 input 文件的字符集。其逻辑是：对于每种字符（共有 256 种），尝试在 input 中将其替换为 ‘0’。

character minimization

这个优化比字符集优化更简单：从前往后扫描 input 中的每个字节，尝试将其替换为 ‘0’。

afl-fast-clang

AFL对于上述通过afl-gcc来插桩这种做法已经属于不建议，并提供了更好的工具afl-clang-fast，通过llvm pass来插桩。

Clang wrapper

afl-clang-fast.c这个文件其实是clang的一层封装，和之前的afl-gcc一样，只是定义了一些宏，和传递了一些参数给真正的clang。

find_obj

尝试找到运行时库，如果失败则终止。

  • 获取AFL_PATH 环境变量的值，并检查该目录下afl-llvm-rt.o文件是否存在，存在就设置为obj_path，返回
  • 如果没有这个环境变量，检查arg0中是否存在/，例如可能是通过/home/xxx/AFL/afl-clang-fast去调用afl-clang-fast的，所以它此时就认为最后一个/之前的/home/sakura/AFL是AFL的根目录，然后读取其下的afl-llvm-rt.o文件，看是否能够访问，如果可以就设置这个目录为obj_path，然后直接返回。
  • 如果还是没有，在AFL_PATH这个宏的目录下找afl-llvm-rt.o文件，然后返回
  • 如果都没有，抛出异常然后返回

edit_params(未完成，)

将 argv 复制到 cc_params，进行必要的编辑。

  • 分配(argc + 128) * sizeof(u8 *)大小的内存给cc_params
  • 首先根据我们执行的是afl-clang-fast还是afl-clang-fast++来决定cc_params[0]的值是clang++还是clang。
    • 如果执行的是afl-clang-fast++，读取环境变量AFL_CXX，如果存在，就将其值设置为cc_params[0]，如果不存在，就直接设置成clang++
    • 如果执行的是afl-clang-fast，读取环境变量AFL_CC，如果存在，就将其值设置为cc_params[0]，如果不存在，就直接设置成clang
  • 默认情况下，我们通过afl-llvm-pass.so来注入instrumentation，但是现在也支持trace-pc-guard模式，可以参考llvm的文档 然后如果定义了USE_TRACE_PC宏，就将-fsanitize-coverage=trace-pc-guard -mllvm -sanitizer-coverage-block-threshold=0添加到参数里 如果没有定义，就依次将-Xclang -load -Xclang obj_path/afl-llvm-pass.so -Qunused-arguments 依次读取我们传给afl-clang-fast的参数，并添加到cc_params里，不过这里会做一些检查和设置。 如果传入参数里有-m32或者armv7a-linux-androideabi，就设置bit_mode为32 如果传入参数里有-m64，就设置bit_mode为64 如果传入参数里有-x，就设置x_set为1 如果传入参数里有-fsanitize=address或者-fsanitize=memory，就设置asan_set为1 如果传入参数里有-Wl,-z,defs或者-Wl,–no-undefined，就直接pass掉，不传给clang。 读取环境变量AFL_HARDEN，如果存在，就在cc_params里添加-fstack-protector-all 如果参数里没有-fsanitize=address/memory，即asan_set是0，就读取环境变量AFL_USE_ASAN，如果存在就添加-fsanitize=address到cc_params里，环境变量AFL_USE_MSAN同理 如果定义了USE_TRACE_PC宏，就检查是否存在环境变量AFL_INST_RATIO，如果存在就抛出异常AFL_INST_RATIO not available at compile time with ’trace-pc’. 读取环境变量AFL_DONT_OPTIMIZE，如果不存在就添加-g -O3 -funroll-loops到参数里 读取环境变量AFL_NO_BUILTIN，如果存在就添加-fno-builtin-strcmp等。 添加参数-D__AFL_HAVE_MANUAL_CONTROL=1 -D__AFL_COMPILER=1 -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1，定义一些宏

main

  • 寻找obj_path路径
  • 编辑参数cc_params
  • 替换进程空间，执行要调用的clang和为其传递参数
    • execvp(cc_params[0], (char**)cc_params);

afl-llvm-pass

关于llvm不懂的可以看CSCD70，顺便可以学一下优化，这里放一下我之前抽空做的笔记, 以及这篇文章可以列为查询和参考.

afl-llvm-pass里只有一个Transform pass AFLCoverage，其继承自ModulePass，所以我们主要分析一下它的runOnModule函数，这里简单的介绍一下llvm里的一些层次关系，粗略理解就是Module相当于你的程序，里面包含所有Function和全局变量，而Function里包含所有BasicBlock和函数参数，BasicBlock里包含所有Instruction,Instruction包含Opcode和Operands。

registerAFLPass

这些都是向PassManager来注册新的pass，每个pass彼此独立，通过PM统一注册和调度，更加模块化。

具体的可以参考定义，我摘取了必要的代码和注释，请仔细阅读。

简单的理解就是当我创建了一个类RegisterStandardPasses之后，就会调用它的构造函数，然后调用PassManagerBuilder::addGlobalExtension，这是一个静态函数，这个函数会创建一个tuple保存Ty和Fn还有一个id，并将其添加到一个静态全局vector里，以供PassManagerBuilder在需要的时候，将其添加到PM里。 而这个添加的时机就是ExtensionPointTy来指定的。

static void registerAFLPass(const PassManagerBuilder &, legacy::PassManagerBase &PM)
{

    PM.add(new AFLCoverage());
}

static RegisterStandardPasses RegisterAFLPass(PassManagerBuilder::EP_ModuleOptimizerEarly, registerAFLPass);

static RegisterStandardPasses RegisterAFLPass0(PassManagerBuilder::EP_EnabledOnOptLevel0, registerAFLPass);

runOnModule

  • 通过getContext来获取LLVMContext，其保存了整个程序里分配的类型和常量信息。
  • 通过这个Context来获取type实例Int8Ty和Int32Ty
  • 读取环境变量AFL_INST_RATIO给变量inst_ratio，其值默认为100，这个值代表一个插桩概率，本来应该每个分支都必定插桩，而这是一个随机的概率决定是否要在这个分支插桩。
  • 获取全局变量中指向共享内存的指针，以及上一个基础块的编号。（获取SHM区域和上一个位置的全局变量）
  • 遍历每个基本块，找到此基本块中适合插入instrument的位置，后续通过初始化IRBuilder的一个实例进行插入
  • 随机创建一个当前基本块的编号，并通过插入load指令来获取前一个基本块的编号
  • 通过插入load指令来获取共享内存的地址，并通过CreateGEP函数来获取共享内存里指定index的地址，这个index通过cur_loc和prev_loc取xor计算得到。
  • 通过插入load指令来读取对应index地址的值，并通过插入add指令来将其加一，然后通过创建store指令将新值写入，更新共享内存

afl-llvm-rt

AFL LLVM_Mode中存在着三个特殊的功能。这三个功能的源码位于afl-llvm-rt.o.c中。

afl-showmap

afl-showmap 用于运行一遍目标程序，并以「人类可读的方式」展示 hit count。

##include <stdio.h>
##include <unistd.h>

int main(void) {
    char s[50];
    read(0, s, 100);
    int len = -1;
    do {
        len++;
    } while(s[len] == 'a');
    printf("%d\n", len);
    return 0;
}
// 编译指令：AFL_DONT_OPTIMIZE=1  ../afl-gcc app.c -o app -g

/*
echo 'aaaaaaabbbc' > in
afl-showmap -o trace -- ./app < in
## afl-showmap 2.57b by <lcamtuf@google.com>
## [*] Executing './app'...
## 
## -- Program output begins --
## 7
## -- Program output ends --
## [+] Captured 4 tuples in 'trace'.


006783:1
015732:1
035029:1
050165:4
050892:1
*/

050165这个边命中了4次：

image-20231215233518269

afl-as 插入的每条桩代码都有一个 id，它在编译器随机生成。而「前一个 id」与「后一个 id」的组合，即可代表一条边。hit count 更新方法如下：

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

个循环体中的桩代码 id 为 0x82A6，按上面的逻辑计算一下

>>> 0x82A6 ^ ( 0x82A6 >> 1)
50165

可见 50165 确实是指的这一条回跳边。但为什么 trace 中，这条边的数据是「4」而非实际的跳转次数 7 次呢？这得等到看代码的时候才能明白

afl-showmap 的大部分函数与 afl-tmin 中的几乎一样，不过 run_target 过程中，给 hit count 分桶的逻辑有细微区别：

/* Classify tuple counts. Instead of mapping to individual bits, as in
   afl-fuzz.c, we map to more user-friendly numbers between 1 and 8. */
static const u8 count_class_human[256] = {
  [0]           = 0,
  [1]           = 1,
  [2]           = 2,
  [3]           = 3,
  [4 ... 7]     = 4,
  [8 ... 15]    = 5,
  [16 ... 31]   = 6,
  [32 ... 127]  = 7,
  [128 ... 255] = 8
};
static const u8 count_class_binary[256] = {
  [0]           = 0,
  [1]           = 1,
  [2]           = 2,
  [3]           = 4,
  [4 ... 7]     = 8,
  [8 ... 15]    = 16,
  [16 ... 31]   = 32,
  [32 ... 127]  = 64,
  [128 ... 255] = 128
};
static void classify_counts(u8* mem, const u8* map) {
  u32 i = MAP_SIZE;
  if (edges_only) {
    while (i--) {
      if (*mem) *mem = 1;
      mem++;
    }
  } else {
    while (i--) {
      *mem = map[*mem];
      mem++;
    }
  }
}

在分桶时，有两种分桶方案：binary mode 下，桶 id 与 afl-tmin 是一致的；人类可读模式下，桶 id 是从 0 到 8 的自然数。因此，我们刚刚实验中遇到的问题——为什么那条边的 trace 数据是 4 而不是 7——便得到解答了。hit count 为 7 次时，它的桶 id 是 4。若循环被执行 8 次，那桶 id 就该是 5 了。

至于为什么在人类可读模式下输出这样的 id，推测作者是希望保证输出中每一行的长度都相等。

write_results

把所有命中过的边都输出。这里作者使用了 %06u:%u 占位符。所以 afl-showmap 的输出文件，其每一行长度都是 8 个字节。这不仅便于人类阅读，也便于机器阅读。

afl-analyze

afl-analyze 的用途是分析一个输入文件，猜测它各个部分的语义——例如 magic number、checksum、length 等。我们提到过，AFL 面对 magic number 和 checksum 比较无力，因此找到这些特殊结构有助于我们进一步 fuzz。

为做实验，先来设计一个文件格式。

image-20231213230030759.png

  • 头部 4 个字节为 haha
  • 接下来 4 个字节为小端序的 uint32 数据，表示数据长度
  • 接下来 len 个字节，为用户数据
  • 接下来 4 个字节为 done
  • 接下来 4 个字节为用户数据的 checksum，文件到此为止

为这个文件格式写一个 parser：

##include <stdio.h>
##include <stdlib.h>
##include <string.h>
##include <unistd.h>

int main(void) {
    char s[300];
    int file_len = read(0, s, 400);

    if(strncmp(s, "haha", 4)) {
        puts("header error");
        exit(0);
    }

    int len = *(unsigned int*)(&s[4]);

    if(file_len != len + 16) {
        puts("len error");
        exit(0);
    }

    unsigned int sum=0;
    for(int i=0; i<len; i++) {
        sum += (unsigned char)s[8 + i];
    }
    if(strncmp(s + 8 + len, "done", 4)) {
        puts("header error");
        exit(0);
    }
    if(*(unsigned int*)(&s[12 + len]) != sum) {
        puts("checksum error");
        exit(0);
    }
    puts("accepted");
    return 0;
}
python -c 'open("in", "wb").write(b"haha" + b"\x50\x00\x00\x00" + b"a" * 0x50 + b"done\x50\x1e\x00\x00")'

afl-analyze -i in -- ./check

image-20231213230200293.png 可见 afl-analyze 顺利找出了两个 magic、一个 length，并发现了被计算 checksum 的用户数据字段。然而，afl-analyze 认为文件末尾不是 checksum 值，而是 magic。不过这样的结果已经足够好了

analyze

对于 input 文件中的每一个位置，将 a 改为a^0xff、a^0x01、a+0x10、a-0x10 这四个数，分别运行实验。分类讨论实验结果：

  • 四次实验的运行路径全部与原始路径相同。说明这个位置对程序没什么影响。（典型例子是，一个负责输出图片 exif 信息的程序不会管每个像素是什么颜色）
  • 有至少一次实验的运行路径与原始路径相同。说明这个位置不太重要，可以改。（例如，这个位置是什么不太重要，但唯独不能是 \x00 ，因为会造成截断）
  • 四次实验的运行路径与原始路径不同，且这四次实验的路径一致。说明这个位置不能改。（典型例子是 magic number 检查，只要 magic 不对，程序就结束）
  • 四次实验都与原始路径不同，且各自路径不一致。说明这个地方严重影响控制流，应该狠狠地改。（典型例子是 type 字段，决定程序接下来如何处理数据）

另外，对于每个位置，如果对它的修改造成的影响，与修改前一个字节完全不一样，则认为它与前一个字节分别属于不同的 field。这是有道理的，例如 uint32 magic number 的第二、第三个字节被修改后的行为，肯定是完全一样的。而当前后两个字节分属不同的 field 时，对它们的修改大概率会产生完全不同的效果。

上面的代码把文件划分成了若干个 field，并给每个字节标注了「不重要 / 不太重要 / 不能改 / 敏感」四种标签。那么，afl-analyzer 是如何进一步标记 length、magic、checksum 等字段的呢？来继续看 dump_hex 函数。

static void analyze(char **argv)
{

    u32 i;
    u32 boring_len = 0, prev_xff = 0, prev_x01 = 0, prev_s10 = 0, prev_a10 = 0;

    u8 *b_data = ck_alloc(in_len + 1);
    u8 seq_byte = 0;

    b_data[in_len] = 0xff; /* Intentional terminator. */

    ACTF("Analyzing input file (this may take a while)...\n");

##ifdef USE_COLOR
    show_legend();
##endif /* USE_COLOR */

    for (i = 0; i < in_len; i++)
    {

        u32 xor_ff, xor_01, sub_10, add_10;
        u8 xff_orig, x01_orig, s10_orig, a10_orig;

        /* Perform walking byte adjustments across the file. We perform four
           operations designed to elicit some response from the underlying
           code. */

        in_data[i] ^= 0xff;
        xor_ff = run_target(argv, in_data, in_len, 0);

        in_data[i] ^= 0xfe;
        xor_01 = run_target(argv, in_data, in_len, 0);

        in_data[i] = (in_data[i] ^ 0x01) - 0x10;
        sub_10 = run_target(argv, in_data, in_len, 0);

        in_data[i] += 0x20;
        add_10 = run_target(argv, in_data, in_len, 0);
        in_data[i] -= 0x10;

        /* Classify current behavior. */
		// 观察 4 次运行路径与原始路径是否相同
        xff_orig = (xor_ff == orig_cksum);
        x01_orig = (xor_01 == orig_cksum);
        s10_orig = (sub_10 == orig_cksum);
        a10_orig = (add_10 == orig_cksum);

        if (xff_orig && x01_orig && s10_orig && a10_orig)
        {
			// 4 次变异都不改变路径，则这个位置不重要
            b_data[i] = RESP_NONE;
            boring_len++;
        }
        else if (xff_orig || x01_orig || s10_orig || a10_orig)
        {
			// 有至少一个不改变路径的变异，说明这个位置不关键，可以变异
            b_data[i] = RESP_MINOR;
            boring_len++;
        }
        else if (xor_ff == xor_01 && xor_ff == sub_10 && xor_ff == add_10)
        {
			// 4 次实验都与原路径不同，且这 4 次实验的路径一致，说明这个地方不能改
		    // 典型场景是 magic 检查，magic 不对就退出程序
            b_data[i] = RESP_FIXED;
        }
        else // 4 次实验都与原路径不同，且各次实验的执行路径也不一致，说明这位置对控制流很重要
            b_data[i] = RESP_VARIABLE;

        /* When all checksums change, flip most significant bit of b_data. */
		// 看这个位置与前一个位置的行为是否完全不一样，给 field 划定边界
        if (prev_xff != xor_ff && prev_x01 != xor_01 &&
            prev_s10 != sub_10 && prev_a10 != add_10)
            seq_byte ^= 0x80;

        b_data[i] |= seq_byte;
        prev_xff = xor_ff;
        prev_x01 = xor_01;
        prev_s10 = sub_10;
        prev_a10 = add_10;
    }
    dump_hex(in_data, in_len, b_data);
    SAYF("\n");
    OKF("Analysis complete. Interesting bits: %0.02f%% of the input file.",
        100.0 - ((double)boring_len * 100) / in_len);
    if (exec_hangs)
        WARNF(cLRD "Encountered %u timeouts - results may be skewed." cRST,
              exec_hangs);
    ck_free(b_data);
}

dump_hex

dump_hex 函数不仅负责输出十六进制数据，还给各个 field 打上了细化的标签

可见，被标为「不能改」的块会被细分，其他块（不重要、不太重要、敏感）则保持原标签。具体而言，对于一个被标为「不能改」的块，其处理逻辑如下：

若长度为 2 字节，且值比输入数据总长度小，则认为是 length 字段 若长度为 2 字节，且两个字节之差大于 32，则认为是 checksum 字段 若长度为 4 字节，且值比输入数据总长度小，则认为是 length 字段 若长度为 4 字节，且第一个字节的 MSB 与其他三个字节不同，则认为是 checksum 字段 若长度为小于 32 的奇数，则继续认为是 magic ，不改标签 如果以上情况都不是，则认为是被计算 checksum 的字段

afl-fuzz

afl-fuzz.c 这份文件中，混杂了终端 UI、种子变异策略、队列维护、fork server 通讯等各种逻辑

参数：

  • -i in_dir：表示初始 corpus 目录。
  • -o out_dir：表示工作目录。这里存放 fuzz 过程中的各种信息、当前的 corpus、crash 用例等。
  • -M sync_id：表示以 master 身份运行。在这种模式下，deterministic（确定性）变异会被打开。
  • -S sync_id：表示以 slave 身份运行。在这种模式下，deterministic 变异会被关闭。
  • -f out_file：如果目标程序需要从某个特定文件读入（例如 /etc/nginx/nginx.conf），可以用这个选项指定 AFL 将变异出的输入写入那个文件。
  • -x extras_dir：如果有 dictionary，可以用此选项将其提供给 AFL。
  • -t exec_tmout：设置执行超时时间。
  • -m ...：设置内存限制。
  • -b cpu：绑定指定的 CPU 核。
  • -d：跳过 deterministic 变异阶段。
  • -B：秘密选项，与 afl-tmin 的 -B 类似，让 fuzzer 只关心共享内存（shm）中的某些位置。
  • -C：打开 crash exploration（崩溃探索）模式。根据白皮书，此模式用于探索某个 crash 的潜力。输入一个 crash 用例，fuzzer 将生成许多相关的 crash。
  • -n：打开 dumb 模式（黑盒模式），不进行插桩运行。在此模式下，目标程序不挂载共享内存（shm）。如果没有设置环境变量 AFL_DUMB_FORKSRV，则也不使用 fork server。
  • -T：给用户界面换一个 banner。
  • -Q：qemu 模式，与当前情境暂时不相关。

main

  • 获取时间，与pid异或后做为种子

  • 接下来是个while，从argv中获取并准备参数

  • setup_signal_handlers()设置一些信号的 handler，例如 alarm 响了就要关闭 child 进程

  • 检测asan设置

    • 如果用户设置了 ASAN_OPTIONS 环境变量，那就必须使用 abort_on_error=1 和 symbolize=0
    • 若用户设置了 MSAN_OPTIONS 环境变量，那就必须设置 exit_codd=86 和 symbolize=0。

  • 从环境变量获取并设置某些值

  • 将 fuzzer 运行参数存进 orig_cmdline

  • fix_up_banner：修改ui相关

  • check_if_tty：检查终端是否为tty（若有环境变量 AFL_NO_UI，则 not_on_tty = 1）

    • 由于 AFL 默认的 ui 会定期刷新，我们可以用 AFL_NO_UI 来让它不画 ui，而是逐行输出日志。

  • get_core_count：获取核心数量

  • check_cpu_governor：若发现 cpu 频率可调，则唆使用户把 cpu 定在最高频率

  • setup_post：设置后处理函数

  • setup_shm：初始化 shm，若处于 dumb 模式则不设置 __AFL_SHM_ID

  • init_count_class16：初始化 16bit 查找表（性能优化用途）

    • 这里的 16bit 查找表是为了进一步加速——afl-fuzz 的 classify_counts 函数比 afl-tmin 那个版本要更快。
    • 在 afl-tmin 中，是逐字节将 hit count 替换为桶 id；
    • 在 afl-fuzz 中，是逐双字节替换，还使用了循环展开等其他优化技巧
    • 16bit 查找表的大小是 65536 字节，也可以装在 L2 缓存里面。这是一个非常用心的优化。

  • setup_dirs_fds：在工作目录下创建一些文件夹，并打开一些 fd 备用，例如 /dev/urandom setup_dirs_fds();

  • read_testcases：把初始 corpus 读入 queue

  • load_auto：读入自动生成的 extra（如果有）

  • pivot_inputs：把初始 corpus 复制到工作目录的 queue 文件夹下

  • perform_dry_run(use_argv)：对所有测试用例执行试运行，以确认该应用程序按照预期正常运行。仅对初始输入执行此操作，并且仅执行一次。

  • cull_queue()：精简队列

  • find_start_position():

    • 只有在resuming_fuzz时才起作用。
    • 打开out_dir/fuzzer_stats，读4095字节到tmp中。查找子串"cur_path : “的位置为off。设置ret = atoi(off + 20);

  • write_stats_file():更新统计信息文件以进行无人值守的监视。

  • 如果设置了stop_soon，跳转到stop_fuzzing

  • 如果是tty启动（终端），那么先sleep 4 秒，start_time += 4000。

    • 再检测如果设置了stop_soon，跳转到stop_fuzzing

接下来是fuzz的主循环

  • cull_queue():再次简化队列
  • queue_cur指向当前队列中的元素
  • 判断一次循环是否结束，是则初始化队列，queue_cur指向当前队列的元素，为空说明遍历到结尾
    • queue_cycle队列循环次数加一
    • current_entry=0，cur_skipped_paths=0，queue_cur指向队列头
    • 如果seek_to不为0，（用于指定开始位置，把queue_cur抬高到seek_to位置，恢复重启前的状态）
    • show_stats()：显示状态
    • 如果不是终端模式，输出当前是第几个循环
    • 如果经历了一个完整的扫描周期后都没有新的路径发现，那么尝试调整策略。

perform_dry_run

afl-fuzz 的 dry run 比 afl-tmin 的 dry run 要复杂，因为它不是只运行目标程序一次，而是用 queue 中的所有用例跑一遍程序；另外，它使用了 fork server。在代码中，这种 dry run 称为「calibrate（校准）」

对于 queue 中的每一个用例，调用 calibrate_case 函数进行校准。用例会被运行多次（默认是 8 次，这个函数的具体细节我们下文讨论）。对于校准结果：

  • 若 timeout 了，且 -t 参数里面没有容忍超时、也不处于 resume 模式，则直接退出。
  • 若 crash 了，则直接退出（除非有 AFL_SKIP_CRASHES 环境变量）。
  • 若无法执行目标程序，或目标程序没被插桩，则直接退出。
  • 另外，若该用例多次运行的行为不一致，则向用户抱怨两句。

在执行完所有用例的校准之后，若存在校准失败的用例（例如超时或 crash 但被容忍），则向用户报告情况。

calibrate_case

校准用例

calibrate_case 函数的运行时机至少有两个：

  • 一是程序运行之初，用于校准初始 corpus；

  • 二是发现了新路径，将有趣的用例加入 queue 时。

总结一句：进了 queue 的用例，都要被运行一遍calibrate_case 函数。

校准过程是多次运行用例（默认是 8 次），统计各次运行的结果。

  • 若 fork server 没有准备好，就调用 init_forkserver() 初始化 fork server
  • 多次调用 run_target() 运行目标程序，观察结果。若没有任何 hit count 命中，则认为程序未插桩，报告错误。
  • 如果发现对某用例多次运行程序，其表现不一致，则将执行次数提升到 40 次，并更新 var_bytes[] （这个全局变量表示 shm 中哪些位置存在不一致性）。另外，将 queue entry 的 var_behavior 标记设为 1。
  • 更新 queue entry 信息，例如将 exec_us 字段设为校准过程中的执行时间均值。
  • 给这个用例打分，并更新 top_rated 指针数组。

update_bitmap_score

「打分」算法

这个还有点看不懂，之后再说

cull_queue

精简队列

fuzz_one

大致过程：

static u8 fuzz_one(char** argv) {
  // 决定是否直接跳过这个用例

  // 准备用例文件
  // 校准（若有必要）
  // 用例裁剪
  // 计算 perf_score
  // 决定是否要跳过 deterministic 阶段

  // 下面开始 deterministic 阶段
  // ..................
  // ..................

  // 下面开始 havoc 阶段
  // ..................
  // ..................

  // 下面开始 splicing 阶段
  // ..................
  // ..................

  // 打扫现场
}

上述代码的功能是概率性地跳过 non-favored 用例。白皮书中提到，当考虑 fuzz 一个 non-favored 用例时：

  • 若队列中存在一个从来没被 fuzz 过的 favored 用例，则以 99% 概率跳过当前用例（要尽快去 fuzz 全新 favored 用例）
  • 若没有全新的 favored 用例，且当前用例已经被 fuzz 过，则以 95% 概率跳过
  • 若没有全新的 favored 用例，而当前用例没被 fuzz 过，则以 75% 概率跳过

于是，在 fuzz 运行后期，一个 non-favored 用例被跳过的几率高达 95%。这节省下来的时间，投入到 favored 用例的 fuzz 去了。这究竟是否合理，有待商榷（事实上 favored 集的选取过程也不是无懈可击）——存在很多论文，通过改进 AFL 对各个种子的资源分配，提升了挖漏洞的效率。AFLFast 就是其代表

把用例文件 mmap 进地址空间，并给 out_buf 分配内存。这个 out_buf 用于存储变异出来的用例

afl-fuzz 中的用例裁剪算法，就是 afl-tmin 的子集。它只使用了 afl-tmin 中的 block deletion 优化，而没有使用 alphabet minimization 和 character(字符) minimization。这显然是为了提升 fuzz 效率，尽量少浪费时间

评分标准。简而言之，跑得越快、覆盖度越高、深度越大，分数就会越高，在 havoc 阶段就会有更多资源来尝试变异。

bitflip a/b 的意思是翻转连续的 a 个 bit、步长为 b。例如 bitflip 2/1 就是翻转所有连续 2bit，bitflip 8/8 是每隔 8 个 bit 尝试翻转连续 8bit，也就是尝试翻转每一个字节

从代码中可以看到，arith 变异就是给每个 uint8、uint16、uint32 加上和减去一个量（1 到 35 之间），进行实验。另外，如果 bitflip 已经覆盖到了，则不重复实验。由于 arith 变异对每个位置要尝试大约 35×3 次实验，耗时很长

interest 8/8 就是对于每个字节，把它替换成有趣的值。8bit 的有趣的值包括： -128, -1, 0, 1, 16, 32, 64, 100, 127。不敏感的位置不参与这个变异，被 bitflip 和 arith 覆盖过的也不再重复实验。

interest 16/8 和 32/8 大致逻辑与 8/8 相同，但大小端都会尝试。16bit 的有趣值，是在 8bit 有趣值的基础上添加 -32768, -129, 128, 255, 256, 512, 1000, 1024, 4096, 32767。32bit 的有趣值是在 8bit、16bit 的基础上添加 -2147483648LL, -100663046, -32769, 32768, 65535, 65536, 100663045, 2147483647。

user extras (over) 变异，对于每一个位置，尝试将那里替换为用户词典中的每一个元素

如果某次实验发现了新成果，那么剩余的 havoc 执行次数会翻倍，

splicing 阶段执行「杂交」操作。也就是说，将这个用例的一部分拼接上其他用例的一部分

REF

https://eternalsakura13.com/2020/08/23/afl/

https://bbs.kanxue.com/thread-265936.htm#msg_header_h2_5

https://www.ruanx.net/afl-source-1/ https://xidoo.top/2022/01/afl-white-book/

http://rk700.github.io/2018/01/04/afl-mutations/

更新于 2023-09-16 
CC BY-NC-SA 4.0
AFL
返回 | 主页
0%