AFL源码分析笔记(一) - 深入理解AFL工作机制

0x00 前言

本文基于zoniony师傅的AFL源码分析笔记，对AFL(American Fuzzy Lop)的核心工作机制进行详细解析，重点包括代码覆盖率、插桩实现、fork server机制以及分支记录等关键技术点。

0x01 代码覆盖率基础

代码覆盖率是fuzz中的基本概念，理解这个概念对后续理解插桩编译等概念至关重要。

代码覆盖率定义

• 代码覆盖率是一种度量代码执行覆盖程度的方式
• 对于源代码：指某行代码是否已执行
• 对于二进制程序：指某条汇编指令是否已执行
• 在fuzz中，覆盖率越高越好，意味着测试用例覆盖了更多代码路径

主要计量方式

1. 函数覆盖率：函数是否被调用
2. 基本块覆盖率：基本块是否被执行
3. 边界覆盖率：代码边界条件是否被测试

0x02 插桩实现机制

插桩(Instrumentation)是实现代码覆盖率统计的关键技术。

afl-gcc分析

afl-gcc是gcc的一个封装(wrapper)，主要功能：

1. find_as(argv[0])：找到gcc/clang/llvm编译器
2. edit_params(argc, argv)：处理参数
3. execvp(cc_params[0], (char **)cc_params)：执行编译命令

典型编译参数示例：

gcc -o test test.c -B /usr/local/lib/afl -g -O3 -funroll-loops -D__AFL_COMPILER=1 -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1

关键参数说明：

• -B <目录>：将目录添加到编译器搜索路径
• -funroll-loops：执行循环强度消除优化
• -D__AFL_COMPILER=1：定义AFL编译标志
• -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1：定义fuzzing模式标志

afl-as分析

afl-as和afl-as.h负责实际的插桩操作，主要功能是预处理GCC/clang生成的汇编文件并插入插桩代码。

关键函数add_instrumentation：

static void add_instrumentation(void) {
    while (fgets(line, MAX_LINE, inf)) { // 读取每行汇编
        // 插入插桩代码
        fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32, R(MAP_SIZE));
    }
}

插桩代码模板（32位和64位）：

32位插桩代码：

/* --- AFL TRAMPOLINE (32-BIT) */
.align 4
leal -16(%%esp), %%esp      ; 抬高栈
movl %%edi, 0(%%esp)        ; 保存寄存器
movl %%edx, 4(%%esp)
movl %%ecx, 8(%%esp)
movl %%eax, 12(%%esp)
movl $0x%08x, %%ecx         ; 保存随机数
call __afl_maybe_log        ; 调用__afl_maybe_log
movl 12(%%esp), %%eax       ; 恢复寄存器
movl 8(%%esp), %%ecx
movl 4(%%esp), %%edx
movl 0(%%esp), %%edi
leal 16(%%esp), %%esp
/* --- END --- */

64位插桩代码：

/* --- AFL TRAMPOLINE (64-BIT) */
.align 4
leaq -(128+24)(%%rsp), %%rsp
movq %%rdx, 0(%%rsp)
movq %%rcx, 8(%%rsp)
movq %%rax, 16(%%rsp)
movq $0x%08x, %%rcx
call __afl_maybe_log
movq 16(%%rsp), %%rax
movq 8(%%rsp), %%rcx
movq 0(%%rsp), %%rdx
leaq (128+24)(%%rsp), %%rsp
/* --- END --- */

0x03 Fork Server机制

Fork Server是一种优化技术，用于避免重复调用execve()的开销，提高fuzz效率。

初始化Fork Server

关键函数init_forkserver：

EXP_ST void init_forkserver(char **argv) {
    int st_pipe[2], ctl_pipe[2];  // 命令管道和状态管道
    execv(target_path, argv);     // 执行fork server
}

Fork Server的两个核心功能：

1. 高效重复执行测试样例
2. 记录样例的执行状态

Fork Server工作流程

1. 创建通信管道后，关闭不需要的通道：

close(ctl_pipe[0]);
close(st_pipe[1]);
fsrv_ctl_fd = ctl_pipe[1];
fsrv_st_fd = st_pipe[0];

2. 等待Fork Server就绪信号：

rlen = read(fsrv_st_fd, &status, 4);  // 从状态通道读取4字节
if (rlen == 4) {                      // 判断读取是否成功
    OKF("All right - fork server is up.");
    return;
}

__afl_maybe_log分析

__afl_maybe_log是插桩代码调用的核心函数，其汇编实现主要逻辑：

1. 检查共享内存是否已分配：

mov rdx, cs:__afl_area_ptr
test rdx, rdx
jz short __afl_setup

2. 如果未分配，则调用__afl_setup进行初始化

__afl_forkserver分析

__afl_forkserver是Fork Server的核心实现：

1. 发送就绪信号：

mov rdx, 4                  ; n
lea rsi, __afl_temp         ; buf
mov rdi, 0C7h               ; fd
call _write

2. 等待fuzzer指令循环：

__afl_fork_wait_loop:
    mov rdx, 4              ; nbytes
    lea rsi, __afl_temp     ; buf
    mov rdi, 0C6h           ; status
    call _read
    cmp rax, 4
    jnz __afl_die
    call _fork
    cmp rax, 0
    jl __afl_die
    jz short __afl_fork_resume

3. 处理子进程：

mov cs:__afl_fork_pid, eax
mov rdx, 4                  ; n
lea rsi, __afl_fork_pid     ; buf
mov rdi, 0C7h               ; fd
call _write
mov rdx, 0                  ; options
lea rsi, __afl_temp         ; stat_loc
mov rdi, qword ptr cs:__afl_fork_pid ; pid
call _waitpid
cmp rax, 0
jle __afl_die
mov rdx, 4                  ; n
lea rsi, __afl_temp         ; buf
mov rdi, 0C7h               ; fd
call _write
jmp __afl_fork_wait_loop

对应的伪代码：

if (write(0xC7, &_afl_temp, 4uLL) == 4) {
    while (1) {
        v25 = 0xC6;
        if (read(0xC6, &_afl_temp, 4uLL) != 4) break;
        LODWORD(v26) = fork();
        if (v26 < 0) break;
        if (!v26) goto __afl_fork_resume;
        _afl_fork_pid = v26;
        write(0xC7, &_afl_fork_pid, 4uLL);
        v25 = _afl_fork_pid;
        LODWORD(v27) = waitpid(_afl_fork_pid, &_afl_temp, 0);
        if (v27 <= 0) break;
        write(199, &_afl_temp, 4uLL);
    }
    _exit(v25);
}

Fuzzer端处理

fuzzer端的处理逻辑：

// 启动fork server
if ((res = write(fsrv_ctl_fd, &prev_timed_out, 4)) != 4);
if ((res = read(fsrv_st_fd, &child_pid, 4)) != 4)

// 报告执行结果
if (WIFSIGNALED(status) && !stop_soon) {
    kill_signal = WTERMSIG(status);
    if (child_timed_out && kill_signal == SIGKILL) return FAULT_TMOUT;
    return FAULT_CRASH;
}

0x04 分支记录机制

AFL使用高效的二元tuple(跳转的源地址和目标地址)来记录分支执行信息。

分支表示方法

例如执行路径：A->B->C->D->A->B
可以用四个二元组表示：

• [A,B]
• [B,C]
• [C,D]
• [D,A]

其中[A,B]执行了两次，其余执行了一次。

__afl_store分析

__afl_store函数负责记录分支信息：

__afl_store:
    xor rcx, cs:__afl_prev_loc
    xor cs:__afl_prev_loc, rcx
    shr cs:__afl_prev_loc, 1
    inc byte ptr [rdx+rcx]

对应的伪代码：

cur_location = <COMPILE_TIME_RANDOM>;  // 当前分支的随机数
shared_mem[cur_location ^ prev_location]++;  // 前一分支和当前分支异或作为索引
prev_location = cur_location >> 1;  // 更新前一分支位置

为什么右移一位？

将当前分支右移一位的目的是：

1. 避免A->A或A->B->A这样的路径异或结果为0
2. 减少共享内存(MAP_SIZE=64K)中的碰撞概率

官方提供的碰撞概率数据：

分支信息处理

共享内存使用trace_bits记录分支执行次数，通过classify_counts函数进行处理：

classify_counts((u32 *)trace_bits);

执行次数被归入以下分类表：

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

例如：

• 执行4-7次的计数为8
• 执行8-15次的计数为16

最后使用hash值判断新测试用例是否增加了分支：

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

参考链接

1. Fuzzing binaries without execve()