AFL源码阅读笔记
最近读了AFL(american fuzzy lop)的源码，总结一下。
主要分析了afl主程序afl-fuzz.c。
文章内容较多，包含大量代码和注释。
三种模式
afl-fuzz有三种模式：
普通模式：在汇编层面为源程序插桩，适用于gcc和clang。
llvm模式：在编译层面为源程序插桩，适用于clang。
qemu模式：通过修改qemu代码，在模拟程序运行时记录程序运行路径起到类似于插桩的效果。
由于后面两种模式分别涉及到llvm和qemu的相关机制，不再这里深入记录。（后续补充）
wrapper
afl-gcc
普通模式下，我们需要有被测试程序的源代码，然后使用afl-gcc/afl-g++去编译被测试程序，这样就可以给程序正确的插桩。
而afl-gcc/afl-g++又是什么呢.
从AFL项目源码的Makefile中可以看出
afl-gcc: afl-gcc.c $(COMM_HDR) | test_x86
$(CC) $(CFLAGS) $@.c -o $@ $(LDFLAGS)
set -e; for i in afl-g++ afl-clang afl-clang++; do ln -sf afl-gcc $$i; done
afl-as: afl-as.c afl-as.h $(COMM_HDR) | test_x86
$(CC) $(CFLAGS) $@.c -o $@ $(LDFLAGS)
ln -sf afl-as as
afl-gcc是由afl-gcc.c和其他一些依赖文件编译出来的可执行文件，而afl-g++ afl-clang afl-clang++都是最终指向afl-gcc的。
afl-gcc.c:
/*american fuzzy lop - wrapper for GCC and clang*/
...
find_as(argv[0]);//查找afl-as路径，供edit_params使用
edit_params(argc, argv);//设置gcc参数
execvp(cc_params[0], (char**)cc_params);//调用gcc
源代码开头的注释中就提到了，这个afl-gcc就是GNU GCC和clang的一个wrapper，也就是说afl-gcc到最后还是调用gcc进行编译的。可以猜到，代码中最后的execvp就是带着一些参数执行gcc。
在执行gcc之前，afl-gcc还执行了两个比较重要的函数,find_as()和edit_params()
1.find_as()的作用是去找到afl-as的位置,它首先尝试从AFL_PATH环境变量中读取路径并且检查as文件是否存在路径下，如果存在，就设置变量并返回。如果没有从环境变量中找到，它会接着尝试当前运行路径。如果还没有找到，它就会在/usr/local/lib/afl下寻找，这个路径是在Makefile文件中定义的，编译afl-gcc的时候通过-D选项作为宏传递给afl-gcc。如果执行了make install的话，/usr/local/lib/afl下就会有afl-as，否则没有。
如果到这里还没找到afl-as文件的话，那么程序就会报错退出。
2.在找到afl-as文件的路径之后，程序会执行edit_params(argc, argv)来设置参数:
它可以根据用户提供的参数来调整一些编译选项包括：
选择gcc,g++还是gcj来最终进行编译
设置是否启用FORTIFY_SOURCE
设置是否启用ASAN
设置是否启用栈溢出保护
设置是否开启-O3 -funroll-loops -g等优化和调试功能
设置是否禁用内建函数
最终，产生的一个最简单的例子:
gcc -o afltest afltest.c -B /opt/cprogams/fuzzstuff/AFL -g -O3 -funroll-loops -D__AFL_COMPILER=1 -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1
其中 -B 的路径就是findas找到的，是让编译器先去给出的路径里面寻找汇编需要的as，也就是让gcc产生原生的.s汇编文件，再使用afl-as处理.s。
所以，afl-as通过修改gcc产生的.s汇编文件，实现汇编级插桩。
afl-as
当afl-as处理完汇编文件之后，他会把真正的汇编任务交给原本的as，所以说afl-as是一个as的wrapper。
所以说，afl-as的主要功能就是读取目标汇编文件，查看在哪里需要插桩，然后插桩。
插桩的作用是记录执行路径，维护forkserver与fuzzer通信传输路径等信息。
if (getenv("AFL_USE_ASAN") || getenv("AFL_USE_MSAN")) { //HERE 若使用ASAN，降低跳转插桩率到原来的33%(降低对ASAN相关跳转插桩的概率)
sanitizer = 1;
inst_ratio /= 3;
}
if (!just_version) add_instrumentation(); //HERE 插桩
add_instrumentation()插桩的主要规则有:
1.只在text段插桩
2.每个函数的第一个汇编指令之前插桩
3.每次jnz等jmp之后插桩
4.只处理对应位数汇编代码(32 or 64)
5.只处理AT&T语法
6.不处理用户自己编写的内联汇编(#APP到#NOAPP之间的)
7.在.L0: or LBB0_0 等跳转点之后的第一条汇编指令之前插桩。
8.如果出现p2align，则下一个跳转点不插桩
add_instrumentation()中进行插桩的语句是:
//HERE 此行必须tab开头，第二个字符为英文。即必须是汇编指令。
if (!pass_thru && !skip_intel && !skip_app && !skip_csect && instr_ok &&
instrument_next && line[0] == '\t' && isalpha(line[1]))
{
fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32,
R(MAP_SIZE)); //HERE R(x) (random() % (x)) 取范围内随机数 为这个桩插入一个随机数
instrument_next = 0;
ins_lines++;
}
和
if (line[0] == '\t') {//HERE Tab开头
if (line[1] == 'j' && line[2] != 'm' && R(100) < inst_ratio) { //HERE inst_ratio为环境变量传递进来的。可以控制插桩概率。在jnz等跳转命令后插桩。
fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32,
R(MAP_SIZE));
ins_lines++;
}
continue;
}
trampoline_fmt_32 或 trampoline_fmt_64就是要插入的桩，他们被定义在afl-as.h
这里分析32位，64类似。
static const u8* trampoline_fmt_32 =
"\n"
"/* --- AFL TRAMPOLINE (32-BIT) --- */\n"
"\n"
".align 4\n"
"\n"
"leal -16(%%esp), %%esp\n"//HERE 提高栈空间，保存寄存器
"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"//HERE 随机数赋值给ecx
"call __afl_maybe_log\n" /*调用__afl_maybe_log*/
"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"//HERE 从栈里恢复寄存器，恢复栈
"\n"
"/* --- END --- */\n"
"\n";
afl-as会在符合规则的所有位置插入上面的汇编代码。也会在汇编文件的最后插入核心函数(main_payload)。
main_payload是实现fuzzer通信的主要依靠，在后面会介绍.
插桩结束后，afl-as会调用gnu as来对插桩后的汇编文件进行汇编操作。
forkserver
AFL提供了两种fuzzer与被fuzz程序通信的方式：
1.execv
在fuzzer中，每次fuzz都调用execv来运行目标程序进行fuzz。然后等待程序执行结束，获得其执行路径和退出状态。
使用这种方法效率低下。如果目标程序是动态链接的，使用这种方法，每次execv执行程序都会进行内存分配，动态库的链接等过程，无疑是非常耗费时间的。因此AFL默认不会使用这种模式，除非使用特殊选项(AFL_NO_FORKSRV,dumb_mode1)。
2.forkserver
先放一下AFL作者介绍forkserver的一篇文章:https://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html
forkserver的原理是：
fuzzer和forkserver使用两个管道通信，一个控制管道(forkserver读，fuzzer写)，一个数据管道(fuzzer读，forkserver写)
fuzzer会在初始阶段使用execv()，运行一次目标程序，这个运行的程序就被称作forkserver。forkserver会执行到插入的桩(也就上面插入的，第一个碰到的桩应该在main函数入口处)。然后就会运行到插入的main_payload中,其中的逻辑检测到还没有进行的forkserver初始化。就会进行初始化，初始化过程很简单，先是保存共享内存的地址(这个后面再详细说)，然后forkserver会通过数据管道发送4字节的数据告诉fuzzer自己已经准备好了，fuzzer可以随时下达fuzz命令。接着forkserver就会一直等待控制管道中的消息，forkserver也就一直卡在main_payload中，此时正执行到main函数的入口处。
fuzzer这边关闭不需要的管道，在数据管道等待forkserver发来的消息。收到forkserver准备好的消息之后，继续运行。
每当fuzzer想要fuzz时，它会通过控制管道向forkserver下达命令(发送4个字节的数据)，forkserver通过控制管道接受到命令之后。他自己会再fork出一个子进程(forkserver的子进程，也就是fuzzer的孙子进程)，然后它将子进程id通过数据管道发送给fuzzer，使用接着waitpid()等待子进程结束。子进程这边会回到main函数，继续向下执行，往后遇到的所有桩都只会记录路径，直到子进程退出或挂起(当然挂起之后是由fuzzer检测到timeout然后kill掉)。子进程退出后，forkserver waitpid()也就执行完毕，接着它将把获取到的子进程的退出状态通过数据管道发送给fuzzer。然后就又去read控制管道，等待fuzzer的下一个fuzz命令。
forkserver的这种方法使用了copy-on-write:
forkserver用fork()产生的子进程会共享其物理空间，只有当各段的内容要发生变化时，才会将父进程的内容复制一份给子进程。也就是说子进程会继承forkserver创建的共享内存空间地址信息(后面讲作用)等，而且可以最大限度的节约CPU内存等资源。
相关代码和一些注释:
static const u8* main_payload_32 =
"\n"
"/* --- AFL MAIN PAYLOAD (32-BIT) --- */\n"
"\n"
".text\n"
".att_syntax\n"
".code32\n"
".align 8\n"
"\n"
"__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" //HERE 先检查是否设置了共享内存(用于向fuzzer提供路径命中情况)
" testl %edx, %edx\n"
" je __afl_setup\n"//HERE 如果没有设置就跳进__afl_setup
"\n"
"__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"//HERE 将路径信息存入到共享内存中去
" 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"
#endif /* ^SKIP_COUNTS */
"\n"
"__afl_return:\n"//HERE 回到插桩位置继续执行
"\n"
" addb $127, %al\n"
" sahf\n"
" ret\n"
"\n"
".align 8\n"
"\n"
"__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"//HERE 获得fuzzer提供的SHM id
" 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"
"\n"
" pushl $0 /* shmat flags */\n"
" pushl $0 /* requested addr */\n"
" pushl %eax /* SHM ID */\n"
" call shmat\n"//HERE 根据SHM id获取共享内存地址
" addl $12, %esp\n"
"\n"
" cmpl $-1, %eax\n"
" je __afl_setup_abort\n"//HERE 失败则推出
"\n"
" /* Store the address of the SHM region. */\n"
"\n"
" movl %eax, __afl_area_ptr\n"//HERE 把共享内存地址存起来
" movl %eax, %edx\n"
"\n"
" popl %ecx\n"
" popl %eax\n"
"\n"
"__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"//HERE 通过管道通信告诉fuzzer，forkserver准备好了
" addl $12, %esp\n"
"\n"
" cmpl $4, %eax\n"
" jne __afl_fork_resume\n"//HERE 如果失败，重新尝试
"\n"
"__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"//HERE 从管道等待读取fuzzer的命令
" addl $12, %esp\n"
"\n"
" cmpl $4, %eax\n"
" jne __afl_die\n"//HERE 如果没有读取到4个字节，则失败，退出
"\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"
" call fork\n"//HERE fork一个子进程(这个子进程将是fuzzer的孙子进程)
"\n"
" cmpl $0, %eax\n"
" jl __afl_die\n"//HERE 如果fork失败，退出
" je __afl_fork_resume\n"//HERE 如果是子进程，跳到__afl_fork_resume
"\n"
" /* In parent process: write PID to pipe, then wait for child. */\n"
"\n"
" movl %eax, __afl_fork_pid\n"//HERE 如果是父进程，就把子进程id存入__afl_fork_pid
"\n"
" pushl $4 /* length */\n"
" pushl $__afl_fork_pid /* data */\n"
" pushl $" STRINGIFY((FORKSRV_FD + 1)) " /* file desc */\n"
" call write\n"//HERE 通过管道通信,向fuzzer发送子进程id
" addl $12, %esp\n"
"\n"
" pushl $0 /* no flags */\n"
" pushl $__afl_temp /* status */\n"
" pushl __afl_fork_pid /* PID */\n"
" call waitpid\n"//HERE 等待子进程id结束，保存子进程退出状态
" addl $12, %esp\n"
"\n"
" cmpl $0, %eax\n"
" jle __afl_die\n"//HERE 如果等待失败，退出
"\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"//HERE 通过管道通信，向fuzzer发送子进程退出状态
" addl $12, %esp\n"
"\n"
" jmp __afl_fork_wait_loop\n"
"\n"
"__afl_fork_resume:\n"
"\n"
" /* In child process: close fds, resume execution. */\n"
"\n"
" pushl $" STRINGIFY(FORKSRV_FD) "\n" //HERE 子进程关闭所有管道，因为它只需要执行程序，不需要与fuzzer通信
" 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"//HERE 子进程恢复执行
"\n"
"__afl_die:\n"
"\n"
" xorl %eax, %eax\n"
" call _exit\n"
"\n"
"__afl_setup_abort:\n"
"\n"
" /* Record setup failure so that we don't keep calling\n"
" shmget() / shmat() over and over again. */\n"
"\n"
" incb __afl_setup_failure\n"
" popl %ecx\n"
" popl %eax\n"
" jmp __afl_return\n"
"\n"
".AFL_VARS:\n"
"\n"
" .comm __afl_area_ptr, 4, 32\n"
" .comm __afl_setup_failure, 1, 32\n"
#ifndef COVERAGE_ONLY
" .comm __afl_prev_loc, 4, 32\n"
#endif /* !COVERAGE_ONLY */
" .comm __afl_fork_pid, 4, 32\n"
" .comm __afl_temp, 4, 32\n"
"\n"
".AFL_SHM_ENV:\n"
" .asciz \"" SHM_ENV_VAR "\"\n"
"\n"
"/* --- END --- */\n"
"\n";
覆盖率计算，分支记录
AFL通过元组tuple来记录路径,将源基本块和目的基本块的配对组合称为tuple,标识源基本块和目的基本块是插桩时插入的随机数。
所从一个基本块到另外一个基本块的元组是(number1,number2)
假设程序从 基本块A(numA) -> 基本块B(numB) ->基本块C(numC) -> 基本块B(numB)，那么他就会在共享内存中记录
SHM[ (numA >> 1) ^ numB ]++ //第一个元组(A,B)
SHM[ (numB >> 1) ^ numC ]++ //第二个元组(B,C)
SHM[ (numC >> 1) ^ numB ]++ //第三个元组(C,B)
在初始化forkserver之前。fuzzer创建了一块共享内存(SHM)，和其他一些bitmap。
这样当初始化forkserver时，把SHM id通过环境变量传递即可让forkserver也获取到SHM地址，这样forkserver fork()出来的子进程就可以往里面记录路径信息(tuple)了。
在每次fuzz之前，fuzzer都会清空SHM，fuzz结束后读取SHM，把产生的路径存入一个bitmap，此bitmap(代码里名字为virgin_bits)用来记录fuzzer整个运行过程中所有产生的路径。
读取完SHM后会与bitmap进行比较，查看是否发现了新的路径(tuple)(即有没有新地址被赋值或有地址值有变化)，如果发现了新路径，就会把此次fuzz的test case存入到队列queue中，参加变异。
SHM默认大小MAP_SIZE为65536字节
EXP_ST void setup_shm(void) {
u8* shm_str;
if (!in_bitmap) memset(virgin_bits, 255, MAP_SIZE);//HERE 用来储存发现了的路径
memset(virgin_tmout, 255, MAP_SIZE);//HERE 用来储存超时的case的路径
memset(virgin_crash, 255, MAP_SIZE);//HERE 用来储存崩溃的case的路径
shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);//HERE 创建共享内存 MAP_SIZE=65535
if (shm_id < 0) PFATAL("shmget() failed");
atexit(remove_shm);
shm_str = alloc_printf("%d", shm_id);
/* If somebody is asking us to fuzz instrumented binaries in dumb mode,
we don't want them to detect instrumentation, since we won't be sending
fork server commands. This should be replaced with better auto-detection
later on, perhaps? */
if (!dumb_mode) setenv(SHM_ENV_VAR, shm_str, 1);//HERE 把共享内存id存入环境变量，供后面forkserver初始化时使用
ck_free(shm_str);
trace_bits = shmat(shm_id, NULL, 0);//HERE trace_bits储存的是fuzz产生的路径
if (trace_bits == (void *)-1) PFATAL("shmat() failed");
}
当孙子程序运行到插桩点时，它所执行的代码为:
cur_location = <COMPILE_TIME_RANDOM>; //HERE 当前路径，一个随机值
shared_mem[cur_location ^ prev_location]++; //HERE SHM中对应位置值+1
prev_location = cur_location >> 1;//HERE 存prev_location
也就是前面给出的SHM[ (numA >> 1) ^ numB ]++ //第一个元组(A,B)
新路径的检测
当一次fuzz结束后，fuzzer首先会收集SHM信息，把范围内的数都统一，如落在128…255内，都计作命中了128次。
static const u8 count_class_lookup8[256] = {//HERE 按范围分桶。
[0] = 0,
[1] = 1,
[2] = 2,
[3] = 4,
[4 ... 7] = 8,
[8 ... 15] = 16,
[16 ... 31] = 32,
[32 ... 127] = 64,
[128 ... 255] = 128
};
static inline void classify_counts(u32* mem) {/*HERE 4字节一组处理，把范围内的次数放入同一个桶。
如printf("0x%x",count_class_lookup16[0x0106]);
结果为0x108。0x06被放入[4 ... 7] = 8 这个桶里 */
u32 i = MAP_SIZE >> 2;
while (i--) {
/* Optimize for sparse bitmaps. */
if (unlikely(*mem)) {
u16* mem16 = (u16*)mem;
mem16[0] = count_class_lookup16[mem16[0]];//HERE 处理四字节中的低地址两个字节
mem16[1] = count_class_lookup16[mem16[1]];//HERE 处理四字节中的高地址两个字节
}
mem++;
}
}
接着大多数情况下fuzzer会调用has_new_bits()来查看SHM中有没有新的路径出现。具体做法是跟传入的virgin_map进行比较
static inline u8 has_new_bits(u8* virgin_map) {//HERE 有新路径返回2，原有路径命中次数增加返回1，否则返回0
#ifdef WORD_SIZE_64
u64* current = (u64*)trace_bits;
u64* virgin = (u64*)virgin_map;
u32 i = (MAP_SIZE >> 3); //HERE 8字节一组进行处理
#else
u32* current = (u32*)trace_bits; //HERE shm
u32* virgin = (u32*)virgin_map; //HERE 标记哪里有改动的map，所有byte初始值为0xff
u32 i = (MAP_SIZE >> 2);//HERE 4字节一组进行处理.
#endif /* ^WORD_SIZE_64 */
u8 ret = 0;
while (i--) {//HERE 处理每4/8字节
/* Optimize for (*current & *virgin) == 0 - i.e., no bits in current bitmap
that have not been already cleared from the virgin map - since this will
almost always be the case. */
if (unlikely(*current) && unlikely(*current & *virgin)) {//HERE if (*current & *virgin) != 0 优化 , 如果shm相较于virgin map数值有变化则进入.
if (likely(ret < 2)) {
u8* cur = (u8*)current;
u8* vir = (u8*)virgin;
/* Looks like we have not found any new bytes yet; see if any non-zero
bytes in current[] are pristine in virgin[]. */
#ifdef WORD_SIZE_64
if ((cur[0] && vir[0] == 0xff) || (cur[1] && vir[1] == 0xff) ||
(cur[2] && vir[2] == 0xff) || (cur[3] && vir[3] == 0xff) ||
(cur[4] && vir[4] == 0xff) || (cur[5] && vir[5] == 0xff) ||
(cur[6] && vir[6] == 0xff) || (cur[7] && vir[7] == 0xff)) ret = 2;
else ret = 1;
#else
if ((cur[0] && vir[0] == 0xff) || (cur[1] && vir[1] == 0xff) ||
(cur[2] && vir[2] == 0xff) || (cur[3] && vir[3] == 0xff)) ret = 2;
else ret = 1; /*HERE 如果是virgin map中新的byte(0xff)对应位置有变化，则说明命中了新的路径，返回2。否则只是原来路径的hit次数有变化，返回1。*/
#endif /* ^WORD_SIZE_64 */
}
*virgin &= ~*current;//HERE 更新virgin map，每个字节的值为原值减去shm中字节的值
/*>>> hex(0xffffffff & (~0x01010101))
'0xfefefefe'*/
}
current++;
virgin++;
}
if (ret && virgin_map == virgin_bits) bitmap_changed = 1;//如果有变化并且传入的指针为virgin_bits指针则赋值bitmap_changed=1
return ret;
}
队列(queue)
队列元素
用来fuzz的payload是test case。初始test case是从用户指定的-i文件夹中读取得到的，后面经过变异，fuzzer也可以自主生成test case。
所有的test case都是queue_entry结构体，被放入队列queue，形成一个单链表。
队列中元素queue_entry的结构是:
struct queue_entry {
u8* fname; /* File name for the test case */
u32 len; /* Input length */
u8 cal_failed, /* Calibration failed? */
trim_done, /* Trimmed? */
was_fuzzed, /* Had any fuzzing done yet? */
passed_det, /* Deterministic stages passed? */
has_new_cov, /* Triggers new coverage? */
var_behavior, /* Variable behavior? */
favored, /* Currently favored? */
fs_redundant; /* Marked as redundant in the fs? */
u32 bitmap_size, /* Number of bits set in bitmap */
exec_cksum; /* Checksum of the execution trace */
u64 exec_us, /* Execution time (us) */
handicap, /* Number of queue cycles behind */
depth; /* Path depth */
u8* trace_mini; /* Trace bytes, if kept */
u32 tc_ref; /* Trace bytes ref count */
struct queue_entry *next, /* Next element, if any */
*next_100; /* 100 elements ahead */
};
static struct queue_entry *queue, /* Fuzzing queue (linked list) */
*queue_cur, /* Current offset within the queue */
*queue_top, /* Top of the list */
*q_prev100; /* Previous 100 marker */
其中最重要的属性是fname(test case在硬盘上的文件名)和len(test case的长度)
next用来指向链表中的下一个test case，next_100指向下100个test case。
fuzzer维护了四个链表指针，分别是
queue：指向单链表头部的test case
queue_cur：它指向当前进行fuzz的test case
queue_top：指向单链表尾部的test case，也就是最新入列的元素
q_prev100：指向单链表头部的test case，它的next_100跨度100个test case，可以用来快速查找某个test case
测试用例入列
AFL会先遍历用户-i选项中提供的所有test case
read_testcases();//HERE 读取in文件夹测试用例，加入queue
static void read_testcases(void) {//HERE 扫描输入文件夹，把所有test case加入队列
struct dirent **nl;//HERE namelist
s32 nl_cnt;
u32 i;
u8* fn;
/* Auto-detect non-in-place resumption attempts. */
fn = alloc_printf("%s/queue", in_dir);
if (!access(fn, F_OK)) in_dir = fn; else ck_free(fn);
ACTF("Scanning '%s'...", in_dir);
/* We use scandir() + alphasort() rather than readdir() because otherwise,
the ordering of test cases would vary somewhat randomly and would be
difficult to control. */
nl_cnt = scandir(in_dir, &nl, NULL, alphasort);
if (nl_cnt < 0) {//HERE 扫描数量为0，没有有效文件
if (errno == ENOENT || errno == ENOTDIR)
SAYF("\n" cLRD "[-] " cRST
"The input directory does not seem to be valid - try again. The fuzzer needs\n"
" one or more test case to start with - ideally, a small file under 1 kB\n"
" or so. The cases must be stored as regular files directly in the input\n"
" directory.\n");
PFATAL("Unable to open '%s'", in_dir);
}
if (shuffle_queue && nl_cnt > 1) {//HERE 打乱文件顺序
ACTF("Shuffling queue...");
shuffle_ptrs((void**)nl, nl_cnt);
}
for (i = 0; i < nl_cnt; i++) {//HERE 遍历所有文件
struct stat st;
u8* fn = alloc_printf("%s/%s", in_dir, nl[i]->d_name);//HERE 文件路径+名称
u8* dfn = alloc_printf("%s/.state/deterministic_done/%s", in_dir, nl[i]->d_name);//HERE 这个文件是否已经在之前的fuzz中进行了确定性变异
u8 passed_det = 0;
free(nl[i]); /* not tracked */
if (lstat(fn, &st) || access(fn, R_OK))
PFATAL("Unable to access '%s'", fn);
/* This also takes care of . and .. */
if (!S_ISREG(st.st_mode) || !st.st_size || strstr(fn, "/README.txt")) {//HERE 排除一些文件
ck_free(fn);
ck_free(dfn);
continue;
}
if (st.st_size > MAX_FILE) //HERE 文件大小不能超过 默认值100MB
FATAL("Test case '%s' is too big (%s, limit is %s)", fn,
DMS(st.st_size), DMS(MAX_FILE));
/* Check for metadata that indicates that deterministic fuzzing
is complete for this entry. We don't want to repeat deterministic
fuzzing when resuming aborted scans, because it would be pointless
and probably very time-consuming. */
if (!access(dfn, F_OK)) passed_det = 1;//HERE 如果deterministic_done下文件存在，即此case已经进行过确定性变异,在恢复session时这个case会被放弃
ck_free(dfn);
add_to_queue(fn, st.st_size, passed_det);//HERE 加入到queue queue_top和q_prev100队列
}
free(nl); /* not tracked */
if (!queued_paths) {
SAYF("\n" cLRD "[-] " cRST
"Looks like there are no valid test cases in the input directory! The fuzzer\n"
" needs one or more test case to start with - ideally, a small file under\n"
" 1 kB or so. The cases must be stored as regular files directly in the\n"
" input directory.\n");
FATAL("No usable test cases in '%s'", in_dir);
}
last_path_time = 0;
queued_at_start = queued_paths;
}
使用add_to_queue()函数依次将他们加入到队列:
/* Append new test case to the queue. */
static void add_to_queue(u8* fname, u32 len, u8 passed_det) {
struct queue_entry* q = ck_alloc(sizeof(struct queue_entry));
q->fname = fname;
q->len = len;
q->depth = cur_depth + 1;
q->passed_det = passed_det;
if (q->depth > max_depth) max_depth = q->depth;//HERE 更新最大深度
if (queue_top) {//HERE queue_top永远指向新进入队列的case，它没有next
queue_top->next = q;
queue_top = q;
} else q_prev100 = queue = queue_top = q;//HERE 这里将queue和q_prev100指向最先进入队列的case
queued_paths++;//HERE 队列中case数量+1
pending_not_fuzzed++;//HERE 在队列中还没有被fuzz的case数量
cycles_wo_finds = 0;//HERE 更新这个标志着这一轮cycle有新case发现
if (!(queued_paths % 100)) {//HERE q_prev100指向每100个新进入队列的case，并且设置对应case的next_100
q_prev100->next_100 = q;
q_prev100 = q;
}
last_path_time = get_cur_time();//HERE 记录加入队列时当前时间
}
depth表示一个case的深度：
假设有初始测试用例A，B。A和B的depth都为1，由A变异产生的test case C深度就为2，由C产生的D深度为3，由B产生的E深度为2
cycles_wo_finds表示一个cycle中有没有新case入列，一个cycle指的是queue中所有cases都fuzz一轮。
queued_paths表示队列中所有case的数量。
校准测试用例(calibrate_case)
每一个新加入queue的test case都会作为参数传入calibrate_case()函数进行校准运行。
calibrate_case使用test case运行一遍程序，保证其能让程序正常运行，不崩溃，不挂起。
接着将此case产生的路径的checksum存入到此case的q->exec_cksum，用于后面校验变异是否有效。
也会更新一些全局变量。
static u8 calibrate_case(char** argv, struct queue_entry* q, u8* use_mem,u32 handicap, u8 from_queue) {
static u8 first_trace[MAP_SIZE];
u8 fault = 0, new_bits = 0, var_detected = 0,
first_run = (q->exec_cksum == 0);
u64 start_us, stop_us;
s32 old_sc = stage_cur, old_sm = stage_max;//HERE 保存stage
u32 use_tmout = exec_tmout;
u8* old_sn = stage_name;
/* Be a bit more generous about timeouts when resuming sessions, or when
trying to calibrate already-added finds. This helps avoid trouble due
to intermittent latency. */
if (!from_queue || resuming_fuzz) //HERE from_queue default 1
use_tmout = MAX(exec_tmout + CAL_TMOUT_ADD,
exec_tmout * CAL_TMOUT_PERC / 100);
q->cal_failed++;
stage_name = "calibration";
stage_max = fast_cal ? 3 : CAL_CYCLES; //HERE fast_cal通过环境变量设置
/* Make sure the forkserver is up before we do anything, and let's not
count its spin-up time toward binary calibration. */
if (dumb_mode != 1 && !no_forkserver && !forksrv_pid)
init_forkserver(argv);
if (q->exec_cksum) memcpy(first_trace, trace_bits, MAP_SIZE);
start_us = get_cur_time_us();
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
u32 cksum;
if (!first_run && !(stage_cur % stats_update_freq)) show_stats();
write_to_testcase(use_mem, q->len);//HERE 把此条test case内容写入文件中，供孙子进程读取
fault = run_target(argv, use_tmout);//HERE 给forkserver下达命令，让forkserver fork()一个子进程，获取子进程的退出状态
/* stop_soon is set by the handler for Ctrl+C. When it's pressed,
we want to bail out quickly. */
if (stop_soon || fault != crash_mode) goto abort_calibration;//HERE 按下Ctrl+C 火速退出
if (!dumb_mode && !stage_cur && !count_bytes(trace_bits)) {//HERE 第一次跑，一个桩也没触发，直接退出.
fault = FAULT_NOINST;
goto abort_calibration;
}
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);//HERE 计算SHM的hash值 检查有没有新路径，或原有路径数命中次数不同
if (q->exec_cksum != cksum) {
u8 hnb = has_new_bits(virgin_bits);//HERE virgin_bits全局变量。如果有之前未被命中的路径，则返回2。
if (hnb > new_bits) new_bits = hnb;//HERE 如果没有新命中的路径，但是此test case中有路径命中次数比原来的test case中对应路径命中次数多，则返回1。
//HERE 未命中新路径，或命中新路径，命中的次数与之前test case命中对应路径次数相同或少于，返回0。
if (q->exec_cksum) {//HERE 除非同一个test case多次运行命中路径结果不同，不然校准阶段应该不会进入这个分支?
u32 i;
for (i = 0; i < MAP_SIZE; i++) {
if (!var_bytes[i] && first_trace[i] != trace_bits[i]) {
var_bytes[i] = 1;
stage_max = CAL_CYCLES_LONG;
}
}
var_detected = 1;
} else {//HERE 如果是第一次，校准阶段一定进入。
q->exec_cksum = cksum;
memcpy(first_trace, trace_bits, MAP_SIZE);
}
}
}
stop_us = get_cur_time_us();
total_cal_us += stop_us - start_us;
total_cal_cycles += stage_max;
/* OK, let's collect some stats about the performance of this test case.
This is used for fuzzing air time calculations in calculate_score(). */
q->exec_us = (stop_us - start_us) / stage_max;
q->bitmap_size = count_bytes(trace_bits);
q->handicap = handicap; //HERE 表示此case是在第几个cycle入queue的
q->cal_failed = 0;
total_bitmap_size += q->bitmap_size;
total_bitmap_entries++;
update_bitmap_score(q);//HERE 更新全局top_rated[]，为test case创建minibits:只记录test case命中的所有路径，不记录命中次数。
/* If this case didn't result in new output from the instrumentation, tell
parent. This is a non-critical problem, but something to warn the user
about. */
if (!dumb_mode && first_run && !fault && !new_bits) fault = FAULT_NOBITS;//HERE 正常退出 且 未命中新路径等(详细见上has_new_bits处)，返回FAULT_NOBITS
abort_calibration:
if (new_bits == 2 && !q->has_new_cov) {//HERE q->has_new_cov默认为0,含义为是否命中了新路径。如果new_bits==2,则将has_new_cov置为1表示此test case命中了新路径。
q->has_new_cov = 1;
queued_with_cov++;//HERE queued_with_cov表示发现新路径的test case数量+1
}
/* Mark variable paths. */
if (var_detected) {//HERE 除非同一个test case多次运行命中路径结果不同，不然校准阶段应该不会进入?
var_byte_count = count_bytes(var_bytes);
if (!q->var_behavior) {
mark_as_variable(q);//HERE 标记此test case多次运行过程结果不同(改变值?)。
queued_variable++; //HERE 被标记为改变值的test case个数
}
}
stage_name = old_sn;
stage_cur = old_sc;
stage_max = old_sm;
if (!first_run) show_stats();
return fault;
}
命中某路径的最优case
之后会调用update_bitmap_score(q),让此test case参加top_rated[]的评选。
top_rated[]数组中存的是命中某路径的最优case，评价标准是case运行时间 * case长度
static void update_bitmap_score(struct queue_entry* q) {//HERE 把能花最小资源命中某一路径的test case存入top_rated数组对应路径位置中
u32 i;
u64 fav_factor = q->exec_us * q->len;//HERE 资源指的就是test case的执行时间*长度
/* For every byte set in trace_bits[], see if there is a previous winner,
and how it compares to us. */
for (i = 0; i < MAP_SIZE; i++)//HERE 遍历所有路径
if (trace_bits[i]) {//HERE 如果这个路径被此test case命中了。
if (top_rated[i]) {//HERE 如果这一个路径对应的top_rated中有值，则说明之前有一个test case命中过这个路径。需要进一步对比资源消耗。
/* Faster-executing or smaller test cases are favored. */
if (fav_factor > top_rated[i]->exec_us * top_rated[i]->len) continue;//HERE 如果当前test case资源消耗的比之前的多，则不改动。
/* Looks like we're going to win. Decrease ref count for the
previous winner, discard its trace_bits[] if necessary. */
//HERE 如果资源消耗比原来少。减少原来test case的ref次数。释放原来test case中的trace_mini。
if (!--top_rated[i]->tc_ref) {
ck_free(top_rated[i]->trace_mini);
top_rated[i]->trace_mini = 0;
}
}
/* Insert ourselves as the new winner. */
top_rated[i] = q;//HERE 此test case存入top_rated，增加ref次数
q->tc_ref++;
if (!q->trace_mini) {//HERE 如果此test case没有trace_mini，则为其创建一个。
q->trace_mini = ck_alloc(MAP_SIZE >> 3);
minimize_bits(q->trace_mini, trace_bits);
}
score_changed = 1;
}
//HERE 路径未被命中，检查下一个。
}
成功加入top_rated[]的case接着会通过minimize_bits()生成它的trace_mini
trace_mini只记录case是否命中了某路径(0 1),trace_mini会在语料筛选中使用到。
static void minimize_bits(u8* dst, u8* src) {
u32 i = 0;
while (i < MAP_SIZE) {//HERE dst[8192] src[65536]
//只看src中的byte是0还是非0(只记录是否命中路径，不记录命中次数)。8个src中的byte当作bit映射为一个dst的byte
if (*(src++)) dst[i >> 3] |= 1 << (i & 7);
i++;
}
}
语料筛选(cull_queue),favored
将所有用户提供的test cases都进行校准运行之后，fuzzer会调用cull_queue()，对所有queue中的cases进行一次语料筛选，评选出favored case。
所有favored case会组成一个命中所有路径的最小case集合。
所有未被评为favored的cases在后面的变异测试中有大概率会被跳过。
static void cull_queue(void) {//HERE 语料筛选（favored）
struct queue_entry* q;
static u8 temp_v[MAP_SIZE >> 3];//HERE 静态变量，位于.data，函数返回后不释放
u32 i;
if (dumb_mode || !score_changed) return;
score_changed = 0;
memset(temp_v, 255, MAP_SIZE >> 3);
queued_favored = 0;
pending_favored = 0;
q = queue;
while (q) {//HERE 将之前favored信息清空，但是未清空fs_redundant。
q->favored = 0;
q = q->next;
}
/* Let's see if anything in the bitmap isn't captured in temp_v.
If yes, and if it has a top_rated[] contender, let's use it. */
for (i = 0; i < MAP_SIZE; i++)//HERE 遍历所有top_rated中的test case(已经是能命中某路径的最小消耗case)
if (top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {//HERE temp_v记录了所有路径的命中情况，可以指明某一路径是已经被某case命中。
//HERE 只有当case命中了temp_v中没有被记录为命中的路径，才可以被选为favored。
u32 j = MAP_SIZE >> 3;//HERE 65536 >> 3 = 8192 //HERE 最终，所有favored=1的cases组成了一个命中所有可以命中的路径的最小case集合。
/* Remove all bits belonging to the current entry from temp_v. */
while (j--)
if (top_rated[i]->trace_mini[j])
temp_v[j] &= ~top_rated[i]->trace_mini[j];
top_rated[i]->favored = 1;
queued_favored++;
if (!top_rated[i]->was_fuzzed) pending_favored++;
}
q = queue;
while (q) {//HERE 遍历所有case，根据此次cull结果设置是否为不需要的case
mark_as_redundant(q, !q->favored);
q = q->next;
}
}
常规fuzz过程
接着到了AFL fuzz的主要过程，它是一个while(1)循环，在这个循环里会对queue中的cases依次变异，测试。
while 1的每一次循环都指定一个queue_cur进行测试，queue_cur指向queue中的一个case，一个while循环周期结束后通过queue_cur->next找到下一个case，又开始执行。
将queue中所有cases都测试过一遍之后，就叫做完成了一个cycle。
while (1) {
u8 skipped_fuzz;
cull_queue();//HERE 语料筛选更新favored,redundant
if (!queue_cur) {//HERE fuzz刚开始会进入。如果如果所有cases都完成了一轮fuzz，即为完成了一个cycle，也将会进入这个分支。
queue_cycle++;
current_entry = 0;
cur_skipped_paths = 0;
queue_cur = queue;
while (seek_to) {
current_entry++;
seek_to--;
queue_cur = queue_cur->next;
}
show_stats();
if (not_on_tty) {
ACTF("Entering queue cycle %llu.", queue_cycle);
fflush(stdout);
}
/* If we had a full queue cycle with no new finds, try
recombination strategies next. */
if (queued_paths == prev_queued) {//HERE 如果所有queue中的cases经过一轮fuzz都没有新发现，那么下一轮会使用SPLICE变异
if (use_splicing) cycles_wo_finds++; else use_splicing = 1;
} else cycles_wo_finds = 0;
prev_queued = queued_paths;
if (sync_id && queue_cycle == 1 && getenv("AFL_IMPORT_FIRST"))//HERE 如果设置了AFL_IMPORT_FIRST，则在fuzzer运行时先同步其他fuzzer的cases
sync_fuzzers(use_argv);
}
skipped_fuzz = fuzz_one(use_argv);//HERE fuzz当前test case。如果成功fuzz返回0。如果失败或退出返回1.
if (!stop_soon && sync_id && !skipped_fuzz) {//HERE 如果-M或者-S 则进入
if (!(sync_interval_cnt++ % SYNC_INTERVAL))//HERE 同步频率
sync_fuzzers(use_argv);//HERE 同步cases
}
if (!stop_soon && exit_1) stop_soon = 2;
if (stop_soon) break;
queue_cur = queue_cur->next;//HERE 下一个queue中的test case
current_entry++;
}//HERE while (1) ends
进行fuzz的主函数是fuzz_one(use_argv);
测试流程大概是:
fuzz_one();
检查queue_cur是否适合变异
将queue_cur进行A变异
common_fuzz_stuff(argv, out_buf, len);
write_to_testcase(out_buf, len);
run_target(argv, exec_tmout);
save_if_interesting(argv, out_buf, len, fault);
查看run_target执行结果
若变异后不会导致崩溃超时，使用has_new_bits()检测是否命中了新路径，如果命中了，使用addtoqueue将变异后的case加入queue，并且使用calibrate_case()校准之
若导致崩溃，挂起，进行崩溃筛选，筛选通过则把变异后的case写入到输出路径中的crash hang
恢复queue_cur;
记录此变异阶段的成果
将queue_cur进行B变异;
common_fuzz_stuff(argv, out_buf, len);
...
恢复queue_cur
记录此变异阶段的成果
将queue_cur进行C变异;
common_fuzz_stuff(argv, out_buf, len);
...
恢复queue_cur
记录此变异阶段的成果
...
所有变异都结束，返回
回到while(1)中，->next下一个queue_cur，再次执行fuzz_one()
在变异之前，fuzz_one()还会对queue_cur进行一些检查处理，包括：
IGNORE_FINDS
如果设置了IGNORE_FINDS , 就不会非初始case进行变异。
#ifdef IGNORE_FINDS
/* In IGNORE_FINDS mode, skip any entries that weren't in the
initial data set. */
if (queue_cur->depth > 1) return 1;
#else
favored
检测是否为favored case ，如果不是，则大概率跳过此queue_cur，对其next进行fuzz:
if (pending_favored) {//HERE 如果有favored case
/* If we have any favored, non-fuzzed new arrivals in the queue,
possibly skip to them at the expense of already-fuzzed or non-favored
cases. */
if ((queue_cur->was_fuzzed || !queue_cur->favored) &&//HERE 如果当前case被fuzz过或者当前case不是favored，则有99%的概率不对当前case进行fuzz
UR(100) < SKIP_TO_NEW_PROB) return 1;
} else if (!dumb_mode && !queue_cur->favored && queued_paths > 10) {
/* Otherwise, still possibly skip non-favored cases, albeit less often.
The odds of skipping stuff are higher for already-fuzzed inputs and
lower for never-fuzzed entries. */
if (queue_cycle > 1 && !queue_cur->was_fuzzed) {//HERE 如果没有favored case，cycle>1且当前case没有被fuzz过,75%跳过
if (UR(100) < SKIP_NFAV_NEW_PROB) return 1;
} else {
if (UR(100) < SKIP_NFAV_OLD_PROB) return 1;//HERE 被fuzz过，没有favored case,95%跳过
}
}
把case内容map进内存
fd = open(queue_cur->fname, O_RDONLY);
if (fd < 0) PFATAL("Unable to open '%s'", queue_cur->fname);
len = queue_cur->len;
orig_in = in_buf = mmap(0, len, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);//HERE 分配一段空间存储case内容，用于在变异后恢复out_buf等。
if (orig_in == MAP_FAILED) PFATAL("Unable to mmap '%s'", queue_cur->fname);
close(fd);
记录当前case的深度(depth)，查看当前case是否是新加入的，是的话对其进行重新校准
cur_depth = queue_cur->depth;//HERE 记录当前depth，如果在后面的过程中，此case的变异加入了queue，那么它的depth就为此case的depth+1
/*******************************************
* CALIBRATION (only if failed earlier on) *
*******************************************/
if (queue_cur->cal_failed) {//HERE 重新校准（当第一次校准时被意外中断才会在这里再校准一次，从其他fuzzer中同步过来的cases应该也会在这里进行校准）。
u8 res = FAULT_TMOUT;
if (queue_cur->cal_failed < CAL_CHANCES) {
res = calibrate_case(argv, queue_cur, in_buf, queue_cycle - 1, 0);
if (res == FAULT_ERROR)
FATAL("Unable to execute target application");
}
if (stop_soon || res != crash_mode) {
cur_skipped_paths++;
goto abandon_entry;
}
}
测试用例修剪
目的是缩小case长度，把不会影响到路径的部分全部删除
/************
* TRIMMING *
************/
if (!dumb_mode && !queue_cur->trim_done) {//HERE 修剪test case
u8 res = trim_case(argv, queue_cur, in_buf);
if (res == FAULT_ERROR)
FATAL("Unable to execute target application");
if (stop_soon) {
cur_skipped_paths++;
goto abandon_entry;
}
/* Don't retry trimming, even if it failed. */
queue_cur->trim_done = 1;
if (len != queue_cur->len) len = queue_cur->len;//HERE 更新trim后的case长度
}
memcpy(out_buf, in_buf, len);
trim_case是主要实现:
//HERE 语料裁剪
static u8 trim_case(char** argv, struct queue_entry* q, u8* in_buf) {//HERE 从左往右，以 指数级减少的长度和步长 修剪case，查看修剪后的case是否对路径产生影响,若产生了影响，则保留被修剪的部分，向右移动继续修剪.若未产生影响，则在inbuf中将被修剪的部分删除，继续向右移动修剪.若所有trim情况都未产生路径影响，则最后case会被修剪到只剩前4字节
static u8 clean_trace[MAP_SIZE];
u8 needs_write = 0, fault = 0;
u32 trim_exec = 0;
u32 remove_len;
u32 len_p2;
/* Although the trimmer will be less useful when variable behavior is
detected, it will still work to some extent, so we don't check for
this. */
if (q->len < 5) return 0;//HERE 如果case的长度小于五则不进行trim
stage_name = tmp;
bytes_trim_in += q->len;//HERE trim过的cases总长度
/* Select initial chunk len, starting with large steps. */
len_p2 = next_p2(q->len);//HERE len_p2 = 大于qlen的最小2的次方数
remove_len = MAX(len_p2 / TRIM_START_STEPS, TRIM_MIN_BYTES);//HERE TRIM_START_STEPS=16 TRIM_MIN_BYTES=4
/* Continue until the number of steps gets too high or the stepover
gets too small. */
while (remove_len >= MAX(len_p2 / TRIM_END_STEPS, TRIM_MIN_BYTES)) {//HERE TRIM_END_STEPS=1024
u32 remove_pos = remove_len;
sprintf(tmp, "trim %s/%s", DI(remove_len), DI(remove_len));
stage_cur = 0;
stage_max = q->len / remove_len;
while (remove_pos < q->len) {
u32 trim_avail = MIN(remove_len, q->len - remove_pos);
u32 cksum;
write_with_gap(in_buf, q->len, remove_pos, trim_avail);//HERE 进行修剪
fault = run_target(argv, exec_tmout);
trim_execs++;
if (stop_soon || fault == FAULT_ERROR) goto abort_trimming;
/* Note that we don't keep track of crashes or hangs here; maybe TODO? */
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);//HERE 查看修剪后对路径的影响
/* If the deletion had no impact on the trace, make it permanent. This
isn't perfect for variable-path inputs, but we're just making a
best-effort pass, so it's not a big deal if we end up with false
negatives every now and then. */
if (cksum == q->exec_cksum) {//HERE 如果某次修剪后路径命中情况未改变，那么就把修剪掉的部分在inbuf中彻底删除。
u32 move_tail = q->len - remove_pos - trim_avail;
q->len -= trim_avail;
len_p2 = next_p2(q->len);
memmove(in_buf + remove_pos, in_buf + remove_pos + trim_avail, //HERE 删除
move_tail);
/* Let's save a clean trace, which will be needed by
update_bitmap_score once we're done with the trimming stuff. */
if (!needs_write) {
needs_write = 1;
memcpy(clean_trace, trace_bits, MAP_SIZE);//HERE 保存整个修剪过程之前此case的bitmap
}
} else remove_pos += remove_len;
/* Since this can be slow, update the screen every now and then. */
if (!(trim_exec++ % stats_update_freq)) show_stats();
stage_cur++;
}
remove_len >>= 1;
}
计算得分
根据各方面因素计算出一个分数，这个分数用于控制后面havoc变异的次数。
/*********************
* PERFORMANCE SCORE *
*********************/
orig_perf = perf_score = calculate_score(queue_cur);//HERE 根据执行时间，长度，深度，落后cycles数等因素给当前case打分，分数用于havoc_stage
/* Skip right away if -d is given, if we have done deterministic fuzzing on
this entry ourselves (was_fuzzed), or if it has gone through deterministic
testing in earlier, resumed runs (passed_det). */
if (skip_deterministic || queue_cur->was_fuzzed || queue_cur->passed_det)//HERE 如果设置了跳过确定性变异，或者此case确定性变异过一次了，直接跳到havoc阶段
goto havoc_stage;
/* Skip deterministic fuzzing if exec path checksum puts this out of scope
for this master instance. */
if (master_max && (queue_cur->exec_cksum % master_max) != master_id - 1)//HERE 主fuzzer会跳过确定性变异阶段.?
goto havoc_stage;
doing_det = 1;//HERE 标记正在做确定性变异
接着，fuzzone()就运行到了变异阶段..
测试用例变异
确定性变异和havoc，splice变异
确定性变异：
bitflip 1/1
将case中的所有bits都反转并且测试一次，这个阶段还引用了token的启发性检测，详情见注释。
#define FLIP_BIT(_ar, _b) do { \
u8* _arf = (u8*)(_ar); \
u32 _bf = (_b); \
_arf[(_bf) >> 3] ^= (128 >> ((_bf) & 7)); \
} while (0)
/* Single walking bit. */
//HERE 反转1bit，步长为1bit
stage_short = "flip1";
stage_max = len << 3;
stage_name = "bitflip 1/1";
stage_val_type = STAGE_VAL_NONE;
orig_hit_cnt = queued_paths + unique_crashes;
prev_cksum = queue_cur->exec_cksum;//HERE 这里记录下变异之前case的cksum。
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {//HERE 从0到stage_max正好可以把case中的所有bits依次反转一遍
stage_cur_byte = stage_cur >> 3;
FLIP_BIT(out_buf, stage_cur);//HERE 反转
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
FLIP_BIT(out_buf, stage_cur);//HERE 恢复反转
/* While flipping the least significant bit in every byte, pull of an extra
trick to detect possible syntax tokens. In essence, the idea is that if
you have a binary blob like this:
xxxxxxxxIHDRxxxxxxxx
...and changing the leading and trailing bytes causes variable or no
changes in program flow, but touching any character in the "IHDR" string
always produces the same, distinctive path, it's highly likely that
"IHDR" is an atomically-checked magic value of special significance to
the fuzzed format.
We do this here, rather than as a separate stage, because it's a nice
way to keep the operation approximately "free" (i.e., no extra execs).
Empirically, performing the check when flipping the least significant bit
is advantageous, compared to doing it at the time of more disruptive
changes, where the program flow may be affected in more violent ways.
The caveat is that we won't generate dictionaries in the -d mode or -S
mode - but that's probably a fair trade-off.
This won't work particularly well with paths that exhibit variable
behavior, but fails gracefully, so we'll carry out the checks anyway.
*/
//HERE 如果连续反转几个字符，都会导致相同的路径 而且 与变异前的路径不同，那么这些连续的字符就可能是一个token（magic number？）
if (!dumb_mode && (stage_cur & 7) == 7) {//HERE 反转完每个byte的最低bit，进入
u32 cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
if (stage_cur == stage_max - 1 && cksum == prev_cksum) {//HERE 反转到了最后一个字符，还是token，那么就停止，并且尝试把token加入extra。
/* If at end of file and we are still collecting a string, grab the
final character and force output. */
if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];
a_len++;
if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)
maybe_add_auto(a_collect, a_len);
} else if (cksum != prev_cksum) {//HERE 与token产生的路径不同，说明已经不再与token中的字符造成相同路径。
//HERE 已经不再是token中的字符，一个token已经被记录完整，尝试将记录到的token加入extra。并且准备重新记录下一个token。
/* Otherwise, if the checksum has changed, see if we have something
worthwhile queued up, and collect that if the answer is yes. */
if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)
maybe_add_auto(a_collect, a_len);
a_len = 0;
prev_cksum = cksum;
}
/* Continue collecting string, but only if the bit flip actually made
any difference - we don't want no-op tokens. */
if (cksum != queue_cur->exec_cksum) {//HERE 记录token是在这里进行的。前面if elseif的是判断是否到了token的结尾。
//HERE 与变异之前的路径不同，则把字符加入token数组
if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];
a_len++;
}
}
}
new_hit_cnt = queued_paths + unique_crashes;//HERE 队列中的case总数+不同路径crash总数
stage_finds[STAGE_FLIP1] += new_hit_cnt - orig_hit_cnt;//HERE BIT_FLIP1阶段找到的crash总数.
stage_cycles[STAGE_FLIP1] += stage_max;//HERE BIT_FLIP1阶段跑的总次数
maybe_add_auto会检测传入的token，如果合适就会把它加入到a_extra这个数组中，供后面havoc变异阶段使用。
/* Maybe add automatic extra. */
static void maybe_add_auto(u8* mem, u32 len) {//HERE 尝试把一串字符加入a_extra
u32 i;
/* Allow users to specify that they don't want auto dictionaries. */
if (!MAX_AUTO_EXTRAS || !USE_AUTO_EXTRAS) return;//HERE 用户禁止使用auto extra特性则退出。(或许在前面直接不收集token会好一点)
/* Skip runs of identical bytes. */
for (i = 1; i < len; i++)//HERE 如果是一串完全相同的字符，则放弃。
if (mem[0] ^ mem[i]) break;
if (i == len) return;
/* Reject builtin interesting values. */
if (len == 2) {//HERE 如果字符串长度为2，查看是不是与已有的一些字符串相同。是则放弃。
i = sizeof(interesting_16) >> 1;
while (i--)
if (*((u16*)mem) == interesting_16[i] ||
*((u16*)mem) == SWAP16(interesting_16[i])) return;//HERE SWAP可以交换高低字节。如SWAP16(0xaabb)==0xbbaa
}
if (len == 4) {//HERE 如果字符串长度为4，查看是不是与已有的一些字符串相同。是则放弃。
i = sizeof(interesting_32) >> 2;
while (i--)
if (*((u32*)mem) == interesting_32[i] ||
*((u32*)mem) == SWAP32(interesting_32[i])) return;
}
/* Reject anything that matches existing extras. Do a case-insensitive
match. We optimize by exploiting the fact that extras[] are sorted
by size. */
for (i = 0; i < extras_cnt; i++)//HERE 查看字符串是不是已经存在于extras数组，无视大小写。是则放弃。
if (extras[i].len >= len) break;
for (; i < extras_cnt && extras[i].len == len; i++)
if (!memcmp_nocase(extras[i].data, mem, len)) return;
/* Last but not least, check a_extras[] for matches. There are no
guarantees of a particular sort order. */
auto_changed = 1;//HERE a_extra数组被修改
for (i = 0; i < a_extras_cnt; i++) {//HERE 查看字符串是不是已经存在于a_extras数组，无视大小写。是则增加对应extra命中次数，重新对a_extra进行排序并且放弃。
if (a_extras[i].len == len && !memcmp_nocase(a_extras[i].data, mem, len)) {
a_extras[i].hit_cnt++;
goto sort_a_extras;
}
}
/* At this point, looks like we're dealing with a new entry. So, let's
append it if we have room. Otherwise, let's randomly evict some other
entry from the bottom half of the list. */
if (a_extras_cnt < MAX_AUTO_EXTRAS) {//HERE 尝试把字符串加入a_extra数组
a_extras = ck_realloc_block(a_extras, (a_extras_cnt + 1) *
sizeof(struct extra_data));
a_extras[a_extras_cnt].data = ck_memdup(mem, len);
a_extras[a_extras_cnt].len = len;
a_extras_cnt++;
} else {//HERE 没有空闲位置了，尝试随机替换a_extra中一项
i = MAX_AUTO_EXTRAS / 2 +
UR((MAX_AUTO_EXTRAS + 1) / 2);
ck_free(a_extras[i].data);
a_extras[i].data = ck_memdup(mem, len);
a_extras[i].len = len;
a_extras[i].hit_cnt = 0;
}
sort_a_extras:
/* First, sort all auto extras by use count, descending order. */
//HERE 先按命中次数 从大向小 排序
qsort(a_extras, a_extras_cnt, sizeof(struct extra_data),
compare_extras_use_d);
/* Then, sort the top USE_AUTO_EXTRAS entries by size. */
//HERE 再把最多命中次数的元素按大小 从小向大 排序
qsort(a_extras, MIN(USE_AUTO_EXTRAS, a_extras_cnt),
sizeof(struct extra_data), compare_extras_len);
}
bitflip 2/1
反转两个bits，步长为1bit
/* Two walking bits. */
//HERE 反转两个bits，步长为1bit
stage_name = "bitflip 2/1";
stage_short = "flip2";
stage_max = (len << 3) - 1;
orig_hit_cnt = new_hit_cnt;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
stage_cur_byte = stage_cur >> 3;
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
}
new_hit_cnt = queued_paths + unique_crashes;//HERE 记录此阶段的发现。
stage_finds[STAGE_FLIP2] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP2] += stage_max;
bitflip 4/1
反转四个bits 步长1bit
/* Four walking bits. */
//HERE 反转四个bits 步长1bit
stage_name = "bitflip 4/1";
stage_short = "flip4";
stage_max = (len << 3) - 3;
orig_hit_cnt = new_hit_cnt;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
stage_cur_byte = stage_cur >> 3;
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
FLIP_BIT(out_buf, stage_cur + 2);
FLIP_BIT(out_buf, stage_cur + 3);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
FLIP_BIT(out_buf, stage_cur + 2);
FLIP_BIT(out_buf, stage_cur + 3);
}
new_hit_cnt = queued_paths + unique_crashes;//HERE 记录此变异阶段的发现。
stage_finds[STAGE_FLIP4] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP4] += stage_max;
bitflip 8/8
反转每一个字节，这里引入了Effector map概念，当case足够长时，如果对一个字节进行了反转，它没有造成路径的变化，那么把这个位置的字符认做是没有用的、不会影响程序路径的。eff_map会记录对应位置是否有用，用于指导后面的确定性变异方法，不再对这个字节进行变异
/* Effector map setup. These macros calculate:
EFF_APOS - position of a particular file offset in the map.
EFF_ALEN - length of a map with a particular number of bytes.
EFF_SPAN_ALEN - map span for a sequence of bytes.
*/
#define EFF_APOS(_p) ((_p) >> EFF_MAP_SCALE2)//HERE EFF_MAP_SCALE2=3
#define EFF_REM(_x) ((_x) & ((1 << EFF_MAP_SCALE2) - 1))
#define EFF_ALEN(_l) (EFF_APOS(_l) + !!EFF_REM(_l))
#define EFF_SPAN_ALEN(_p, _l) (EFF_APOS((_p) + (_l) - 1) - EFF_APOS(_p) + 1)
/* Initialize effector map for the next step (see comments below). Always
flag first and last byte as doing something. */
eff_map = ck_alloc(EFF_ALEN(len));
eff_map[0] = 1;
if (EFF_APOS(len - 1) != 0) {
eff_map[EFF_APOS(len - 1)] = 1;
eff_cnt++;
}
/* Walking byte. */
//HERE 反转八个bits，即反转每一个字节
stage_name = "bitflip 8/8";
stage_short = "flip8";
stage_max = len;
orig_hit_cnt = new_hit_cnt;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
stage_cur_byte = stage_cur;
out_buf[stage_cur] ^= 0xFF;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
/* We also use this stage to pull off a simple trick: we identify
bytes that seem to have no effect on the current execution path
even when fully flipped - and we skip them during more expensive
deterministic stages, such as arithmetics or known ints. */
if (!eff_map[EFF_APOS(stage_cur)]) {//HERE effmap逻辑：当case足够长时，如果对一个字节进行了反转，它没有造成路径的变化，那么把它认做是没有用的字节，后面的确定性变异方法中不再对这个字节进行变异
u32 cksum;
/* If in dumb mode or if the file is very short, just flag everything
without wasting time on checksums. */
if (!dumb_mode && len >= EFF_MIN_LEN)//HERE EFF_MIN_LEN=128
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
else
cksum = ~queue_cur->exec_cksum;
if (cksum != queue_cur->exec_cksum) {//HERE 如果dumbmode或者case长度不足默认值128
eff_map[EFF_APOS(stage_cur)] = 1;
eff_cnt++;
}
}
out_buf[stage_cur] ^= 0xFF;
}
/* If the effector map is more than EFF_MAX_PERC dense, just flag the
whole thing as worth fuzzing, since we wouldn't be saving much time
anyway. */
if (eff_cnt != EFF_ALEN(len) &&//HERE 如果effmap中的字节占case总字节数90%(默认)以上，那么整个case都放到effmap中，认为是有用的
eff_cnt * 100 / EFF_ALEN(len) > EFF_MAX_PERC) {
memset(eff_map, 1, EFF_ALEN(len));
blocks_eff_select += EFF_ALEN(len);
} else {
blocks_eff_select += eff_cnt;
}
blocks_eff_total += EFF_ALEN(len);
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_FLIP8] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP8] += stage_max;
bitflip 16/8
反转两个字节，步长为一个字节
/* Two walking bytes. */
if (len < 2) goto skip_bitflip;//HERE 首先保证长度>2
stage_name = "bitflip 16/8";
stage_short = "flip16";
stage_cur = 0;
stage_max = len - 1;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len - 1; i++) {
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {//HERE 如果两个字符都不在effmap中，不对他进行变异，检查下两个字符
stage_max--;
continue;
}
stage_cur_byte = i;
*(u16*)(out_buf + i) ^= 0xFFFF;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
*(u16*)(out_buf + i) ^= 0xFFFF;
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_FLIP16] += new_hit_cnt - orig_hit_cnt;//HERE 记录此变异阶段的发现。
stage_cycles[STAGE_FLIP16] += stage_max;
bitflip 32/8
反转四个字节，步长为两个字节
if (len < 4) goto skip_bitflip;//HERE 首先保证长度>4
/* Four walking bytes. */
stage_name = "bitflip 32/8";
stage_short = "flip32";
stage_cur = 0;
stage_max = len - 3;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len - 3; i++) {
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)] &&//HERE 查询effmap
!eff_map[EFF_APOS(i + 2)] && !eff_map[EFF_APOS(i + 3)]) {
stage_max--;
continue;
}
stage_cur_byte = i;
*(u32*)(out_buf + i) ^= 0xFFFFFFFF;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
*(u32*)(out_buf + i) ^= 0xFFFFFFFF;
}
new_hit_cnt = queued_paths + unique_crashes;//HERE 记录发现
stage_finds[STAGE_FLIP32] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP32] += stage_max;
arith 8/8
对一个字节进行加减变换，确保变换后的字节不可以通过bitflip得到和经过effmap指导
/* 8-bit arithmetics. */
stage_name = "arith 8/8";
stage_short = "arith8";
stage_cur = 0;
stage_max = 2 * len * ARITH_MAX;
stage_val_type = STAGE_VAL_LE;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len; i++) {
u8 orig = out_buf[i];
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)]) {//HERE 查询effmap，如果字符不在effmap中则不对他进行变异
stage_max -= 2 * ARITH_MAX;
continue;
}
stage_cur_byte = i;
for (j = 1; j <= ARITH_MAX; j++) {
u8 r = orig ^ (orig + j);
/* Do arithmetic operations only if the result couldn't be a product
of a bitflip. */
//HERE 确保变换后的字节不可以通过bitflip得到(因为如果可以通过bitflip得到，那么就一定在前面的阶段出现过了在这里就没必要进行测试)。
if (!could_be_bitflip(r)) {//HERE 返回1说明加减后的字符不可以通过bitflip获得
stage_cur_val = j;
out_buf[i] = orig + j;//HERE 加一个整数
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
r = orig ^ (orig - j);
if (!could_be_bitflip(r)) {
stage_cur_val = -j;
out_buf[i] = orig - j;//HERE 减一个整数
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
out_buf[i] = orig;
}
}
new_hit_cnt = queued_paths + unique_crashes;//HERE 记录
stage_finds[STAGE_ARITH8] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_ARITH8] += stage_max;
arith 16/8
对两个字节进行区分大小端加减变换，步长为一个字节，确保加减之后能够影响到两个字节。确保变换后的字节不可以通过bitflip得到，经过effmap指导
if (len < 2) goto skip_arith;
stage_name = "arith 16/8";
stage_short = "arith16";
stage_cur = 0;
stage_max = 4 * (len - 1) * ARITH_MAX;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len - 1; i++) {
u16 orig = *(u16*)(out_buf + i);
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {//HERE 查询effmap
stage_max -= 4 * ARITH_MAX;
continue;
}
stage_cur_byte = i;
for (j = 1; j <= ARITH_MAX; j++) {
u16 r1 = orig ^ (orig + j),
r2 = orig ^ (orig - j),
r3 = orig ^ SWAP16(SWAP16(orig) + j),
r4 = orig ^ SWAP16(SWAP16(orig) - j);
/* Try little endian addition and subtraction first. Do it only
if the operation would affect more than one byte (hence the
& 0xff overflow checks) and if it couldn't be a product of
a bitflip. */
stage_val_type = STAGE_VAL_LE; //HERE 小端加法，小端减法
if ((orig & 0xff) + j > 0xff && !could_be_bitflip(r1)) {//HERE 只有运算完之后两个字节都被影响到了才可以(只影响一个字节就跟上面的单字节加减没区别了)
stage_cur_val = j;
*(u16*)(out_buf + i) = orig + j;//HERE 两个字节加一个数
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
if ((orig & 0xff) < j && !could_be_bitflip(r2)) {
stage_cur_val = -j;
*(u16*)(out_buf + i) = orig - j;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
/* Big endian comes next. Same deal. */
stage_val_type = STAGE_VAL_BE;//HERE 大端加法，大端减法
if ((orig >> 8) + j > 0xff && !could_be_bitflip(r3)) {
stage_cur_val = j;
*(u16*)(out_buf + i) = SWAP16(SWAP16(orig) + j);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
if ((orig >> 8) < j && !could_be_bitflip(r4)) {
stage_cur_val = -j;
*(u16*)(out_buf + i) = SWAP16(SWAP16(orig) - j);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
*(u16*)(out_buf + i) = orig;
}
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_ARITH16] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_ARITH16] += stage_max;
arith 32/8
对四个字节进行区分大小端加减变换，步长为一个字节，确保加减之后能够影响到四个字节。确保变换后的字节不可以通过bitflip得到，经过effmap指导
if (len < 4) goto skip_arith;
stage_name = "arith 32/8";//HERE 四字节加减。大小端都处理。
stage_short = "arith32";
stage_cur = 0;
stage_max = 4 * (len - 3) * ARITH_MAX;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len - 3; i++) {
u32 orig = *(u32*)(out_buf + i);
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)] &&//HERE 检查effmap
!eff_map[EFF_APOS(i + 2)] && !eff_map[EFF_APOS(i + 3)]) {
stage_max -= 4 * ARITH_MAX;
continue;
}
stage_cur_byte = i;
for (j = 1; j <= ARITH_MAX; j++) {
u32 r1 = orig ^ (orig + j),
r2 = orig ^ (orig - j),
r3 = orig ^ SWAP32(SWAP32(orig) + j),
r4 = orig ^ SWAP32(SWAP32(orig) - j);
/* Little endian first. Same deal as with 16-bit: we only want to
try if the operation would have effect on more than two bytes. */
stage_val_type = STAGE_VAL_LE;
if ((orig & 0xffff) + j > 0xffff && !could_be_bitflip(r1)) {//HERE 只有运算完之后至少三个字节都被影响到了才可以
stage_cur_val = j;
*(u32*)(out_buf + i) = orig + j;//HERE 小端加法
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
if ((orig & 0xffff) < j && !could_be_bitflip(r2)) {
stage_cur_val = -j;
*(u32*)(out_buf + i) = orig - j;//HERE 小端减法
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
/* Big endian next. */
stage_val_type = STAGE_VAL_BE;
if ((SWAP32(orig) & 0xffff) + j > 0xffff && !could_be_bitflip(r3)) {
stage_cur_val = j;
*(u32*)(out_buf + i) = SWAP32(SWAP32(orig) + j);//HERE 大端加法
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
if ((SWAP32(orig) & 0xffff) < j && !could_be_bitflip(r4)) {
stage_cur_val = -j;
*(u32*)(out_buf + i) = SWAP32(SWAP32(orig) - j);//HERE 大端减法
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
*(u32*)(out_buf + i) = orig;
}
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_ARITH32] += new_hit_cnt - orig_hit_cnt;//HERE 保存发现
stage_cycles[STAGE_ARITH32] += stage_max;
interest 8/8
将一个字节替换为其他数字，步长为一个字节，同样需要确保不可以通过前面的变换得到，经过effmap指导。
可替换的值:
/* 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 */
/* Setting 8-bit integers. */
for (i = 0; i < len; i++) {//HERE 这里是两个for循环，case中的每个字节都会有机会被替换成interesting_8数组中的所有数字
u8 orig = out_buf[i];
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)]) {//HERE 查询effmap
stage_max -= sizeof(interesting_8);
continue;
}
stage_cur_byte = i;
for (j = 0; j < sizeof(interesting_8); j++) {
/* Skip if the value could be a product of bitflips or arithmetics. */
if (could_be_bitflip(orig ^ (u8)interesting_8[j]) ||//HERE 检查是否可以通过bitflip或者加减获得。
could_be_arith(orig, (u8)interesting_8[j], 1)) {
stage_max--;
continue;
}
stage_cur_val = interesting_8[j];
out_buf[i] = interesting_8[j];//HERE 直接替换对应字节
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
out_buf[i] = orig;
stage_cur++;
}
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_INTEREST8] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_INTEREST8] += stage_max;
interest 16/8
将两个字节替换为其他数字（大小端分别替换一次），步长为一个字节，同样需要确保不可以通过前面的变换得到，经过effmap指导。
/* Setting 16-bit integers, both endians. */
if (no_arith || len < 2) goto skip_interest;
stage_name = "interest 16/8";//HERE 每次替换16bits，步长8bits
stage_short = "int16";
stage_cur = 0;
stage_max = 2 * (len - 1) * (sizeof(interesting_16) >> 1);
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len - 1; i++) {
u16 orig = *(u16*)(out_buf + i);
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {//HERE 查询effmap
stage_max -= sizeof(interesting_16);
continue;
}
stage_cur_byte = i;
for (j = 0; j < sizeof(interesting_16) / 2; j++) {
stage_cur_val = interesting_16[j];
/* Skip if this could be a product of a bitflip, arithmetics,
or single-byte interesting value insertion. */
if (!could_be_bitflip(orig ^ (u16)interesting_16[j]) &&//HERE 检查是否可以通过前面的变异获得。
!could_be_arith(orig, (u16)interesting_16[j], 2) &&
!could_be_interest(orig, (u16)interesting_16[j], 2, 0)) {
stage_val_type = STAGE_VAL_LE;
*(u16*)(out_buf + i) = interesting_16[j];//HERE 替换成小端
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
if ((u16)interesting_16[j] != SWAP16(interesting_16[j]) &&
!could_be_bitflip(orig ^ SWAP16(interesting_16[j])) &&
!could_be_arith(orig, SWAP16(interesting_16[j]), 2) &&
!could_be_interest(orig, SWAP16(interesting_16[j]), 2, 1)) {
stage_val_type = STAGE_VAL_BE;
*(u16*)(out_buf + i) = SWAP16(interesting_16[j]);//HERE 替换成大端
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
}
*(u16*)(out_buf + i) = orig;
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_INTEREST16] += new_hit_cnt - orig_hit_cnt;//HERE 记录发现
stage_cycles[STAGE_INTEREST16] += stage_max;
interest 32/8
将四个字节替换为其他数字（大小端分别替换一次），步长为一个字节，同样需要确保不可以通过前面的变换得到，经过effmap指导。
/* Setting 32-bit integers, both endians. */
stage_name = "interest 32/8";//HERE 每次替换32bits，步长8bits
stage_short = "int32";
stage_cur = 0;
stage_max = 2 * (len - 3) * (sizeof(interesting_32) >> 2);
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len - 3; i++) {
u32 orig = *(u32*)(out_buf + i);
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)] &&//HERE 检查effmap
!eff_map[EFF_APOS(i + 2)] && !eff_map[EFF_APOS(i + 3)]) {
stage_max -= sizeof(interesting_32) >> 1;
continue;
}
stage_cur_byte = i;
for (j = 0; j < sizeof(interesting_32) / 4; j++) {
stage_cur_val = interesting_32[j];
/* Skip if this could be a product of a bitflip, arithmetics,
or word interesting value insertion. */
if (!could_be_bitflip(orig ^ (u32)interesting_32[j]) &&//HERE 检查是否可以通过前面的变异获得。
!could_be_arith(orig, interesting_32[j], 4) &&
!could_be_interest(orig, interesting_32[j], 4, 0)) {
stage_val_type = STAGE_VAL_LE;
*(u32*)(out_buf + i) = interesting_32[j];
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
if ((u32)interesting_32[j] != SWAP32(interesting_32[j]) &&//HERE 检查是否可以通过前面的变异获得。
!could_be_bitflip(orig ^ SWAP32(interesting_32[j])) &&
!could_be_arith(orig, SWAP32(interesting_32[j]), 4) &&
!could_be_interest(orig, SWAP32(interesting_32[j]), 4, 1)) {
stage_val_type = STAGE_VAL_BE;
*(u32*)(out_buf + i) = SWAP32(interesting_32[j]);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
}
*(u32*)(out_buf + i) = orig;
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_INTEREST32] += new_hit_cnt - orig_hit_cnt;//HERE 记录发现
stage_cycles[STAGE_INTEREST32] += stage_max;
user extras (over)
尝试把case中所有位置内容替换成用户提供的一些字典
if (!extras_cnt) goto skip_user_extras;//HERE 检查extras数组是否为空，fuzzer可以从用户指定的文件中读取内容并写入这个数组
/* Overwrite with user-supplied extras. */
stage_name = "user extras (over)";//HERE 尝试把case中所有位置内容替换成用户提供的一些字典
stage_short = "ext_UO";
stage_cur = 0;
stage_max = extras_cnt * len;
stage_val_type = STAGE_VAL_NONE;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len; i++) {
u32 last_len = 0;
stage_cur_byte = i;
/* Extras are sorted by size, from smallest to largest. This means
that we don't have to worry about restoring the buffer in
between writes at a particular offset determined by the outer
loop. */
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) ||//HERE 如果extra总数大于上限，则有概率跳过一些extra
extras[j].len > len - i ||//HERE 如果替换后比原case长了 就跳过
!memcmp(extras[j].data, out_buf + i, extras[j].len) ||//HERE 如果将要替换的内容与原内容相同则跳过
!memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, extras[j].len))) {//HERE 如果对应位置不在effmap中，则跳过
stage_max--;
continue;
}
last_len = extras[j].len;
memcpy(out_buf + i, extras[j].data, last_len);//HERE 替换
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
}
/* Restore all the clobbered memory. */
memcpy(out_buf + i, in_buf + i, last_len);//HERE 恢复case
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_EXTRAS_UO] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_EXTRAS_UO] += stage_max;
user extras (insert)
尝试把用户提供的内容插入到case的所有位置中，注意溢出
/* Insertion of user-supplied extras. */
stage_name = "user extras (insert)";//HERE 尝试把用户提供的内容插入到case的所有位置中
stage_short = "ext_UI";
stage_cur = 0;
stage_max = extras_cnt * len;
orig_hit_cnt = new_hit_cnt;
ex_tmp = ck_alloc(len + MAX_DICT_FILE);//HERE 新分配一块区域。这里没用out_buf，防止溢出
for (i = 0; i <= len; i++) {
stage_cur_byte = i;
for (j = 0; j < extras_cnt; j++) {
if (len + extras[j].len > MAX_FILE) {//HERE 插入后的长度不能超过最大限制长度
stage_max--;
continue;
}
/* Insert token */
memcpy(ex_tmp + i, extras[j].data, extras[j].len);//HERE 插入
/* Copy tail */
memcpy(ex_tmp + i + extras[j].len, out_buf + i, len - i);//HERE 补齐插入位置后面的字符串
if (common_fuzz_stuff(argv, ex_tmp, len + extras[j].len)) {
ck_free(ex_tmp);
goto abandon_entry;
}
stage_cur++;
}
/* Copy head */
ex_tmp[i] = out_buf[i];
}
ck_free(ex_tmp);
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_EXTRAS_UI] += new_hit_cnt - orig_hit_cnt;//HERE 记录发现
stage_cycles[STAGE_EXTRAS_UI] += stage_max;
auto extras (over)
bitflip 1/1阶段自动获取到的a_extra数组(token)，替换操作。
尝试把token中的所有内容替换到case的所有位置。
if (!a_extras_cnt) goto skip_extras;
stage_name = "auto extras (over)";//HERE 1bit flip阶段自动获取到的a_extra数组(token)，替换操作。
stage_short = "ext_AO";
stage_cur = 0;
stage_max = MIN(a_extras_cnt, USE_AUTO_EXTRAS) * len;
stage_val_type = STAGE_VAL_NONE;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len; i++) {
u32 last_len = 0;
stage_cur_byte = i;
for (j = 0; j < MIN(a_extras_cnt, USE_AUTO_EXTRAS); j++) {//HERE 如果token太多，就用一部分
/* See the comment in the earlier code; extras are sorted by size. */
if (a_extras[j].len > len - i ||//HERE 防止溢出
!memcmp(a_extras[j].data, out_buf + i, a_extras[j].len) ||//HERE 检查替换后是否相同
!memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, a_extras[j].len))) {//HERE 查询effmap
stage_max--;
continue;
}
last_len = a_extras[j].len;
memcpy(out_buf + i, a_extras[j].data, last_len);//HERE 替换
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
}
/* Restore all the clobbered memory. */
memcpy(out_buf + i, in_buf + i, last_len);//HERE 恢复
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_EXTRAS_AO] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_EXTRAS_AO] += stage_max;
if (!queue_cur->passed_det) mark_as_det_done(queue_cur);//HERE 标记此case已完成确定性变异!
此变异阶段结束后，可以看到使用mark_as_det_done()标记了当前case已完成确定性变异。然后进入随机变异阶段。
随机变异
havoc
前面的阶段都叫做确定性变异阶段(deterministic step)。
havoc这个阶段会对case随机叠加确定性阶段的所有变异方式，产生非常随机的变异case。
首先会根据前面的评分来计算havoc变异的次数。
if (!splice_cycle) {//HERE 设置阶段名，根据前面的评分和一些其他因素计算stage_max
stage_name = "havoc";
stage_short = "havoc";
stage_max = (doing_det ? HAVOC_CYCLES_INIT : HAVOC_CYCLES) *
perf_score / havoc_div / 100;
} else {
static u8 tmp[32];
perf_score = orig_perf;
sprintf(tmp, "splice %u", splice_cycle);
stage_name = tmp;
stage_short = "splice";
stage_max = SPLICE_HAVOC * perf_score / havoc_div / 100;
}
接着记录一些数据，正式开始havoc变异。
默认情况下，变异叠加次数从2^1 2^2 .. 2^7中随机选择一个
if (stage_max < HAVOC_MIN) stage_max = HAVOC_MIN;
temp_len = len;
orig_hit_cnt = queued_paths + unique_crashes;
havoc_queued = queued_paths;
/* We essentially just do several thousand runs (depending on perf_score)
where we take the input file and make random stacked tweaks. */
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {//HERE 根据评分算出来的havoc执行次数
u32 use_stacking = 1 << (1 + UR(HAVOC_STACK_POW2));//HERE 1<<(1+UR(7))，默认情况下，变异叠加次数从2^1 2^2 .. 2^7中随机选择一个
stage_cur_val = use_stacking;
for (i = 0; i < use_stacking; i++) {//HERE 根据变异叠加次数随机叠加不同类型的变异
switch (UR(15 + ((extras_cnt + a_extras_cnt) ? 2 : 0))) {//HERE 随机选择变异方式(确定性变异 或者 拿出extra来覆盖或者插入)
//这里省略了各种变异叠加类型的详细情况，后面写。
}
}
if (common_fuzz_stuff(argv, out_buf, temp_len))
goto abandon_entry;
/* out_buf might have been mangled a bit, so let's restore it to its
original size and shape. */
if (temp_len < len) out_buf = ck_realloc(out_buf, len);//HERE 恢复out_buf 为刚刚入queue时的值
temp_len = len;
memcpy(out_buf, in_buf, len);
/* If we're finding new stuff, let's run for a bit longer, limits
permitting. */
if (queued_paths != havoc_queued) {//HERE 如果在此havoc阶段有新的case加入queue
if (perf_score <= HAVOC_MAX_MULT * 100) {//HERE 增加case的perf_score和stage_max，增加havoc阶段运行次数。
stage_max *= 2;
perf_score *= 2;
}
havoc_queued = queued_paths;
}
}
//HERE END HAVOC
new_hit_cnt = queued_paths + unique_crashes;//HERE 记录状态
if (!splice_cycle) {//HERE 是HAVOC阶段调用的还是SPLICE阶段。
stage_finds[STAGE_HAVOC] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_HAVOC] += stage_max;
} else {
stage_finds[STAGE_SPLICE] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_SPLICE] += stage_max;
}
#ifndef IGNORE_FINDS
havoc变异叠加策略
-
随机一个位置反转bit
-
随机一个字节替换成interesting_8
-
随机端序，随机两字节替换成interesting_16
-
随机端序，随机四字节替换成interesting_32
-
随机位置字节加上一个随机数
-
随机位置字节加上一个随机数
-
随机位置两个字节减去一个随机数
-
随机位置两个字节加上一个随机数
-
随机位置四个字节减去一个随机数
-
随机位置四个字节加上一个随机数
-
随机位置字节替换成随机值，用异或来防止替换成原值
-
随机从一个位置删除一段字符串
-
75%的概率从buf中复制一段插入到随机位置。25%的概率插入一段随机字符.
-
75%的概率从buf中复制一段覆盖到随机位置。25%的概率覆盖一段随机字符.
-
把字典(用户提供 or token)中内容覆盖到buf中某一个位置
-
把字典(用户提供 or token)中内容插入到buf中某一个位置
switch (UR(15 + ((extras_cnt + a_extras_cnt) ? 2 : 0))) {//HERE 随机选择变异方式(确定性变异 或者 拿出extra来覆盖或者插入)
case 0://HERE 随机一个位置反转bit
/* Flip a single bit somewhere. Spooky! */
FLIP_BIT(out_buf, UR(temp_len << 3));
break;
case 1: //HERE 随机一个字节替换成interesting_8
/* Set byte to interesting value. */
out_buf[UR(temp_len)] = interesting_8[UR(sizeof(interesting_8))];
break;
case 2://HERE 随机端序，随机两字节替换成interesting_16
/* Set word to interesting value, randomly choosing endian. */
if (temp_len < 2) break;
if (UR(2)) {
*(u16*)(out_buf + UR(temp_len - 1)) =
interesting_16[UR(sizeof(interesting_16) >> 1)];
} else {
*(u16*)(out_buf + UR(temp_len - 1)) = SWAP16(
interesting_16[UR(sizeof(interesting_16) >> 1)]);
}
break;
case 3://HERE 随机端序，随机四字节替换成interesting_32
/* Set dword to interesting value, randomly choosing endian. */
if (temp_len < 4) break;
if (UR(2)) {
*(u32*)(out_buf + UR(temp_len - 3)) =
interesting_32[UR(sizeof(interesting_32) >> 2)];
} else {
*(u32*)(out_buf + UR(temp_len - 3)) = SWAP32(
interesting_32[UR(sizeof(interesting_32) >> 2)]);
}
break;
case 4://HERE 随机位置字节减去一个随机数
/* Randomly subtract from byte. */
out_buf[UR(temp_len)] -= 1 + UR(ARITH_MAX);
break;
case 5://HERE 随机位置字节加上一个随机数
/* Randomly add to byte. */
out_buf[UR(temp_len)] += 1 + UR(ARITH_MAX);
break;
case 6://HERE 随机位置两个字节减去一个随机数
/* Randomly subtract from word, random endian. */
if (temp_len < 2) break;
if (UR(2)) {
u32 pos = UR(temp_len - 1);
*(u16*)(out_buf + pos) -= 1 + UR(ARITH_MAX);
} else {
u32 pos = UR(temp_len - 1);
u16 num = 1 + UR(ARITH_MAX);
*(u16*)(out_buf + pos) =
SWAP16(SWAP16(*(u16*)(out_buf + pos)) - num);
}
break;
case 7://HERE 随机位置两个字节加上一个随机数
/* Randomly add to word, random endian. */
if (temp_len < 2) break;
if (UR(2)) {
u32 pos = UR(temp_len - 1);
*(u16*)(out_buf + pos) += 1 + UR(ARITH_MAX);
} else {
u32 pos = UR(temp_len - 1);
u16 num = 1 + UR(ARITH_MAX);
*(u16*)(out_buf + pos) =
SWAP16(SWAP16(*(u16*)(out_buf + pos)) + num);
}
break;
case 8://HERE 随机位置四个字节减去一个随机数
/* Randomly subtract from dword, random endian. */
if (temp_len < 4) break;
if (UR(2)) {
u32 pos = UR(temp_len - 3);
*(u32*)(out_buf + pos) -= 1 + UR(ARITH_MAX);
} else {
u32 pos = UR(temp_len - 3);
u32 num = 1 + UR(ARITH_MAX);
*(u32*)(out_buf + pos) =
SWAP32(SWAP32(*(u32*)(out_buf + pos)) - num);
}
break;
case 9://HERE 随机位置四个字节加上一个随机数
/* Randomly add to dword, random endian. */
if (temp_len < 4) break;
if (UR(2)) {
u32 pos = UR(temp_len - 3);
*(u32*)(out_buf + pos) += 1 + UR(ARITH_MAX);
} else {
u32 pos = UR(temp_len - 3);
u32 num = 1 + UR(ARITH_MAX);
*(u32*)(out_buf + pos) =
SWAP32(SWAP32(*(u32*)(out_buf + pos)) + num);
}
break;
case 10://HERE 随机位置字节替换成随机值，用异或来防止替换成原值
/* Just set a random byte to a random value. Because,
why not. We use XOR with 1-255 to eliminate the
possibility of a no-op. */
out_buf[UR(temp_len)] ^= 1 + UR(255);
break;
case 11 ... 12: {//HERE 随机从一个位置删除一段字符串
/* Delete bytes. We're making this a bit more likely
than insertion (the next option) in hopes of keeping
files reasonably small. */
u32 del_from, del_len;
if (temp_len < 2) break;
/* Don't delete too much. */
del_len = choose_block_len(temp_len - 1);//HERE 返回一个一定小于temp_len - 1的随机值。刚开始fuzz时更容易返回比较小的数。
del_from = UR(temp_len - del_len + 1);//HERE 随机选择一个开始删除的位置
memmove(out_buf + del_from, out_buf + del_from + del_len,
temp_len - del_from - del_len);//HERE 删除
temp_len -= del_len;//HERE
break;
}
case 13://HERE 75%的概率从buf中复制一段插入到随机位置。25%的概率插入一段随机字符.
if (temp_len + HAVOC_BLK_XL < MAX_FILE) {//HERE 确定一定不会超过最大限度
/* Clone bytes (75%) or insert a block of constant bytes (25%). */
u8 actually_clone = UR(4);//HERE 随机数，决定复制或插入随机字符
u32 clone_from, clone_to, clone_len;
u8* new_buf;
if (actually_clone) {//HERE 75%
clone_len = choose_block_len(temp_len);//HERE 随机选择复制长度
clone_from = UR(temp_len - clone_len + 1);//HERE 随机选择从哪里复制位置
} else {//HERE 25%
clone_len = choose_block_len(HAVOC_BLK_XL);//HERE 随机插入字符长度
clone_from = 0;
}
clone_to = UR(temp_len);//HERE 随机选择粘贴位置
new_buf = ck_alloc_nozero(temp_len + clone_len);//HERE 用新分配的空间，防止溢出
/* Head */
memcpy(new_buf, out_buf, clone_to);//HERE 先把头放上
/* Inserted part */
if (actually_clone)
memcpy(new_buf + clone_to, out_buf + clone_from, clone_len);//HERE 粘贴过去
else
memset(new_buf + clone_to,
UR(2) ? UR(256) : out_buf[UR(temp_len)], clone_len);//HERE 或者插入一段随机字符(随机字符 或者 随机从buf中选一个字符)
/* Tail */
memcpy(new_buf + clone_to + clone_len, out_buf + clone_to,//HERE 最后把尾接上
temp_len - clone_to);
ck_free(out_buf);//HERE 释放原来的buf
out_buf = new_buf;//HERE 指到新buf
temp_len += clone_len;
}
break;
case 14: {//HERE 75%的概率从buf中复制一段覆盖到随机位置。25%的概率覆盖一段随机字符.
/* Overwrite bytes with a randomly selected chunk (75%) or fixed
bytes (25%). */
u32 copy_from, copy_to, copy_len;
if (temp_len < 2) break;
copy_len = choose_block_len(temp_len - 1);
copy_from = UR(temp_len - copy_len + 1);
copy_to = UR(temp_len - copy_len + 1);
if (UR(4)) {//HERE 75% 从buf中拿一段覆盖到随机位置
if (copy_from != copy_to)
memmove(out_buf + copy_to, out_buf + copy_from, copy_len);
} else memset(out_buf + copy_to,//HERE 25%覆盖为随机字符
UR(2) ? UR(256) : out_buf[UR(temp_len)], copy_len);
break;
}
/* Values 15 and 16 can be selected only if there are any extras
present in the dictionaries. */
case 15: {//HERE 把字典中内容覆盖到buf中某一个位置
/* Overwrite bytes with an extra. */
if (!extras_cnt || (a_extras_cnt && UR(2))) {//HERE 用户没有提供字典 或 用户提供了字典,并且有token,有二分之一概率 进入这个分支
/* No user-specified extras or odds in our favor. Let's use an
auto-detected one. */
u32 use_extra = UR(a_extras_cnt);
u32 extra_len = a_extras[use_extra].len;
u32 insert_at;
if (extra_len > temp_len) break;
insert_at = UR(temp_len - extra_len + 1);//HERE 随机选择覆盖位置
memcpy(out_buf + insert_at, a_extras[use_extra].data, extra_len);
} else {//HERE 用户提供了字典，并且有token，有二分之一几率进入这个分支使用用户提供的字典中的内容。
//HERE 用户提供了字典，而且没有token，一定进入这个分支
/* No auto extras or odds in our favor. Use the dictionary. */
u32 use_extra = UR(extras_cnt);
u32 extra_len = extras[use_extra].len;
u32 insert_at;
if (extra_len > temp_len) break;//HERE 防止溢出
insert_at = UR(temp_len - extra_len + 1);//HERE 随机选择覆盖位置(随机字符 或者 随机从buf中选一个字符)
memcpy(out_buf + insert_at, extras[use_extra].data, extra_len);
}
break;
}
case 16: {//HERE 把字典中内容插入到buf中某一个位置
u32 use_extra, extra_len, insert_at = UR(temp_len + 1);
u8* new_buf;
/* Insert an extra. Do the same dice-rolling stuff as for the
previous case. */
if (!extras_cnt || (a_extras_cnt && UR(2))) {//HERE 跟前面的判断一样
use_extra = UR(a_extras_cnt);
extra_len = a_extras[use_extra].len;
if (temp_len + extra_len >= MAX_FILE) break;
new_buf = ck_alloc_nozero(temp_len + extra_len);//HERE 使用新分配的空间防止溢出
/* Head */
memcpy(new_buf, out_buf, insert_at);
/* Inserted part */
memcpy(new_buf + insert_at, a_extras[use_extra].data, extra_len);
} else {
use_extra = UR(extras_cnt);
extra_len = extras[use_extra].len;
if (temp_len + extra_len >= MAX_FILE) break;
new_buf = ck_alloc_nozero(temp_len + extra_len);//HERE 使用新分配的空间防止溢出
/* Head */
memcpy(new_buf, out_buf, insert_at);
/* Inserted part */
memcpy(new_buf + insert_at, extras[use_extra].data, extra_len);
}
/* Tail */
memcpy(new_buf + insert_at + extra_len, out_buf + insert_at,
temp_len - insert_at);//HERE 插入尾部
ck_free(out_buf);
out_buf = new_buf;
temp_len += extra_len;
break;
}
}
}
SPLICING
一个cycle过后如果没有新发现才在第二个cycle中进入SPLICING阶段
他会从queue中选择一个其他case，将queue_cur和选到的case随机位置首尾相连，然后跳到havoc进行变异。
//HERE 第一个cycle过后如果没有新发现才在第二个cycle中进入这里.
if (use_splicing && splice_cycle++ < SPLICE_CYCLES && queued_paths > 1 && queue_cur->len > 1) {
struct queue_entry* target;
u32 tid, split_at;
u8* new_buf;
s32 f_diff, l_diff;
/* First of all, if we've modified in_buf for havoc, let's clean that
up... */
if (in_buf != orig_in) {//HERE 恢复in_buf
ck_free(in_buf);
in_buf = orig_in;
len = queue_cur->len;
}
/* Pick a random queue entry and seek to it. Don't splice with yourself. */
do { tid = UR(queued_paths); } while (tid == current_entry);//HERE 在所有加入queue的case中随机选择一个，不能选择自己。
splicing_with = tid;//HERE splicing_with指明了进行splice的case的序号(在queue中的位置)
target = queue;//HERE queue指向队列中最开始的case。
while (tid >= 100) { target = target->next_100; tid -= 100; }//HERE 从头上开始一直->next查找，查找到对应的case，让target指向他
while (tid--) target = target->next;
/* Make sure that the target has a reasonable length. */
while (target && (target->len < 2 || target == queue_cur)) {//HERE 如果splice对象长度不足2，那么不要，看下一个
target = target->next;
splicing_with++;
}
if (!target) goto retry_splicing;//HERE 如果找不到合适的，重新尝试。
/* Read the testcase into a new buffer. */
fd = open(target->fname, O_RDONLY);
if (fd < 0) PFATAL("Unable to open '%s'", target->fname);
new_buf = ck_alloc_nozero(target->len);
ck_read(fd, new_buf, target->len, target->fname);//HERE 找到了要splice的case，把它放到new_buf
close(fd);
/* Find a suitable splicing location, somewhere between the first and
the last differing byte. Bail out if the difference is just a single
byte or so. */
locate_diffs(in_buf, new_buf, MIN(len, target->len), &f_diff, &l_diff);//HERE f_diff是两字符串第一个不同字符，l_diff是最后一个不同字符
if (f_diff < 0 || l_diff < 2 || f_diff == l_diff) {
ck_free(new_buf);
goto retry_splicing;
}
/* Split somewhere between the first and last differing byte. */
split_at = f_diff + UR(l_diff - f_diff);//HERE f_diff和l_diff之间随机找个位置
/* Do the thing. */
len = target->len;
memcpy(new_buf, in_buf, split_at);//HERE 当前case放左面，选择splice的case放右边
in_buf = new_buf;
ck_free(out_buf);
out_buf = ck_alloc_nozero(len);
memcpy(out_buf, in_buf, len);//HERE 把连接起来的字符串写入out_buf，跳到havoc
goto havoc_stage;
}
//HERE END SPLICE
执行完上面所有的变异之后，一个case的变异工作就完成了，回到fuzz_one() ， 对next case进行同样的变异测试。
崩溃筛选
从前面稍微了解到了，如果变异的case发现了新路径，或是导致fuzz程序崩溃，挂起，fuzzer会对其进行一些筛选并保存。
这个过程在save_if_interesting()中进行，返回1表示已经保存case，返回0表示没有保存。
首先判断fuzz程序退出状态
- 如果是正常退出(或crashmode下crash掉):
检测是否发现新路径，发现了就把case加入queue、校准和保存到磁盘。
static u8 save_if_interesting(char** argv, void* mem, u32 len, u8 fault) {//HERE 崩溃去重
u8 *fn = "";
u8 hnb;
s32 fd;
u8 keeping = 0, res;
if (fault == crash_mode) {//HERE 如果没有开启crash_mode 且 正常退出则进入。如果开启crashmode 且 crash，则进入.
/* Keep only if there are new bits in the map, add to queue for
future fuzzing, etc. */
if (!(hnb = has_new_bits(virgin_bits))) {//HERE 如果路径击中状态与原来相同
if (crash_mode) total_crashes++;//HERE crashmode下，记录crash总数
return 0;//HERE 没意思 返回
}
#ifndef SIMPLE_FILES
fn = alloc_printf("%s/queue/id:%06u,%s", out_dir, queued_paths,
describe_op(hnb));
#else
fn = alloc_printf("%s/queue/id_%06u", out_dir, queued_paths);
#endif /* ^!SIMPLE_FILES */
add_to_queue(fn, len, 0);//HERE 把变异后的case加入到queue，加入后queue_top就指向它
if (hnb == 2) {//HERE 命中了新路径
queue_top->has_new_cov = 1;//HERE 变异后的case命中了新路径
queued_with_cov++;
}
queue_top->exec_cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);//HERE 更新cksum
/* Try to calibrate inline; this also calls update_bitmap_score() when
successful. */
res = calibrate_case(argv, queue_top, mem, queue_cycle - 1, 0);//HERE 校准新加入queue的case，设置其handicap为当前case位置
if (res == FAULT_ERROR)
FATAL("Unable to execute target application");
fd = open(fn, O_WRONLY | O_CREAT | O_EXCL, 0600);//HERE 变异case带来了新路径，把它放到output/queue/文件夹下
if (fd < 0) PFATAL("Unable to create '%s'", fn);
ck_write(fd, mem, len, fn);
close(fd);
keeping = 1;
}
-
非正常退出
它对trace_bits进行一个简化，只记录路径命中与否(0x80/0x01)。这个简化很巧妙，可以供下面来判断是否丢弃了原有路径。
发现新路径或者没有触发原有路径都会被认为是有意义的case，会将其保存到磁盘
如果超时:
switch (fault) { case FAULT_TMOUT://HERE 变异case导致超时 /* Timeouts are not very interesting, but we're still obliged to keep a handful of samples. We use the presence of new bits in the hang-specific bitmap as a signal of uniqueness. In "dumb" mode, we just keep everything. */ total_tmouts++; if (unique_hangs >= KEEP_UNIQUE_HANG) return keeping;//HERE 是否超过 保存超时挂起case的数量上限。超过上限返回0，不保存 if (!dumb_mode) { #ifdef WORD_SIZE_64 simplify_trace((u64*)trace_bits);//HERE 这个简化很巧妙，他可以供下面来判断是否丢弃了原有路径。不记录路径命中次数了，只记录路径命中与否(0x80/0x01)。 #else simplify_trace((u32*)trace_bits); #endif /* ^WORD_SIZE_64 */ if (!has_new_bits(virgin_tmout)) return keeping;//HERE 如果没有发现新路径(不管原有路径命中次数是否增加)，即使此变异case导致超时，也放弃，不保存。如果发现了新路径返回2，如果缺少了以前的某个路径返回1，这两种情况都当作新hang情况处理 } unique_tmouts++;//HERE 导致超时次数+1 /* Before saving, we make sure that it's a genuine hang by re-running the target with a more generous timeout (unless the default timeout is already generous). */ if (exec_tmout < hang_tmout) {//HERE 用一个更长的timeout重新测试看是不是仍然超时 u8 new_fault; write_to_testcase(mem, len); new_fault = run_target(argv, hang_tmout); /* A corner case that one user reported bumping into: increasing the timeout actually uncovers a crash. Make sure we don't discard it if so. */ if (!stop_soon && new_fault == FAULT_CRASH) goto keep_as_crash;//HERE 如果不超时，但是导致崩溃了，那么就按崩溃处理 if (stop_soon || new_fault != FAULT_TMOUT) return keeping;//HERE 如果不超时，那么没意思，不加入queue，退出 } #ifndef SIMPLE_FILES fn = alloc_printf("%s/hangs/id:%06llu,%s", out_dir, unique_hangs, describe_op(0));//HERE 到这里 一定发现了新路径，所以不用传入2 #else fn = alloc_printf("%s/hangs/id_%06llu", out_dir, unique_hangs); #endif /* ^!SIMPLE_FILES */ unique_hangs++; last_hang_time = get_cur_time();//HERE 记录当前时间导致了最后一次程序挂起 break;如果崩溃:
case FAULT_CRASH://HERE 变异case导致崩溃 keep_as_crash: /* This is handled in a manner roughly similar to timeouts, except for slightly different limits and no need to re-run test cases. */ total_crashes++;//HERE 首先+1总崩溃数量 if (unique_crashes >= KEEP_UNIQUE_CRASH) return keeping;//HERE 是否超过记录上限 if (!dumb_mode) { #ifdef WORD_SIZE_64 simplify_trace((u64*)trace_bits);//HERE 同样的很巧妙的简化 #else simplify_trace((u32*)trace_bits); #endif /* ^WORD_SIZE_64 */ if (!has_new_bits(virgin_crash)) return keeping;//HERE 如果没有发现新路径(不管原有路径命中次数是否增加)，即使此变异case导致崩溃，也放弃，不保存。如果发现了新路径返回2，如果缺少了以前的某个路径返回1，这两种情况都当作新crash情况处理 } if (!unique_crashes) write_crash_readme();//HERE 第一次记录到crash时执行，写了一个README.txt #ifndef SIMPLE_FILES fn = alloc_printf("%s/crashes/id:%06llu,sig:%02u,%s", out_dir, unique_crashes, kill_signal, describe_op(0));//HERE 到这里 一定发现了新路径，所以不用传入2 #else fn = alloc_printf("%s/crashes/id_%06llu_%02u", out_dir, unique_crashes, kill_signal); #endif /* ^!SIMPLE_FILES */ unique_crashes++;//发现了新路径的crash数+1 last_crash_time = get_cur_time(); last_crash_execs = total_execs;//HERE 记录此次crash前面一共运行了多少次 break;其他情况:
case FAULT_ERROR: FATAL("Unable to execute target application");//HERE 无法运行fuzz程序了，报错退出fuzzer default: return keeping;//HERE 返回保存情况 }
判断完之后真正的保存到磁盘
fd = open(fn, O_WRONLY | O_CREAT | O_EXCL, 0600);//HERE 保存对应hang或crash变异case到磁盘
if (fd < 0) PFATAL("Unable to create '%s'", fn);
ck_write(fd, mem, len, fn);
close(fd);
ck_free(fn);
return keeping;//HERE 返回1
主从Fuzzer同步
用户可以使用-M id来指定一个主fuzzer，使用-S id来指定定一个从fuzzer。
主从fuzzer会定期查看其他fuzzer在磁盘上保存的queue，并拿过来自己测试。
启动fuzzer时使用同一个-o out文件夹可以让主从fuzzer拥有相同的sync_dir , 每个fuzzer都会在sync_dir下创建自己的output目录。
fuzzer同步就是通过读取sync_dir下其他fuzzer的输出目录来进行的，主要由sync_fuzzers(use_argv);这个函数实现。
大体步骤：首先确认是其他fuzzer的输出文件夹，然后读取到test case文件，确保文件合法，运行文件，查看是否值得保存，保存。
详细步骤见注释
/* Grab interesting test cases from other fuzzers. */
static void sync_fuzzers(char** argv) {//HERE 同步其他fuzzer在queue路径下保存的cases(没有同步crash和hang???)
DIR* sd;
struct dirent* sd_ent;
u32 sync_cnt = 0;
sd = opendir(sync_dir);//HERE 如果使用了 -M或者-S ，那么sync_dir在这里就是-o指定的路径。out_dir是 -o所指定路径下的fuzzerid文件夹
if (!sd) PFATAL("Unable to open '%s'", sync_dir);
stage_max = stage_cur = 0;
cur_depth = 0;
/* Look at the entries created for every other fuzzer in the sync directory. */
while ((sd_ent = readdir(sd))) {//HERE 读取同步路径下内容，这一层循环的是同步路径下的文件，寻找其他fuzzer的out_dir
static u8 stage_tmp[128];
DIR* qd;
struct dirent* qd_ent;
u8 *qd_path, *qd_synced_path;
u32 min_accept = 0, next_min_accept;
s32 id_fd;
/* Skip dot files and our own output directory. */
if (sd_ent->d_name[0] == '.' || !strcmp(sync_id, sd_ent->d_name)) continue;//HERE 略过隐藏文件和此fuzzerid文件夹
/* Skip anything that doesn't have a queue/ subdirectory. */
qd_path = alloc_printf("%s/%s/queue", sync_dir, sd_ent->d_name);
if (!(qd = opendir(qd_path))) {//HERE 找到并打开其他fuzzer的queue文件夹
ck_free(qd_path);
continue;
}
/* Retrieve the ID of the last seen test case. */
qd_synced_path = alloc_printf("%s/.synced/%s", out_dir, sd_ent->d_name);//HERE sd_ent->d_name是其他fuzzerid
//PS:/.synced/中保存了此fuzzer对于各个其他fuzzer的cases的同步情况(最后同步的那个case的id)。
id_fd = open(qd_synced_path, O_RDWR | O_CREAT, 0600);
if (id_fd < 0) PFATAL("Unable to create '%s'", qd_synced_path);
if (read(id_fd, &min_accept, sizeof(u32)) > 0) //HERE min_accept从/.synced/下对应文件内读取同步的最后一个cases的id
lseek(id_fd, 0, SEEK_SET);
next_min_accept = min_accept;
/* Show stats */
sprintf(stage_tmp, "sync %u", ++sync_cnt);
stage_name = stage_tmp;
stage_cur = 0;
stage_max = 0;
/* For every file queued by this fuzzer, parse ID and see if we have looked at
it before; exec a test case if not. */
while ((qd_ent = readdir(qd))) {//HERE 遍历其他fuzzer的queue文件夹下的test case
u8* path;
s32 fd;
struct stat st;
if (qd_ent->d_name[0] == '.' ||//HERE 略过隐藏文件
sscanf(qd_ent->d_name, CASE_PREFIX "%06u", &syncing_case) != 1 || //HERE 如果cases文件的命名格式不是id:xxxx，则略过
syncing_case < min_accept) continue;//HERE 如果读取到的case id比原来保存的case id小，那么就说明之前处理过这个case,掠过
/* OK, sounds like a new one. Let's give it a try. */
if (syncing_case >= next_min_accept)//HERE 更新/.synced/下指定文件内容为读取的case的id。
next_min_accept = syncing_case + 1;
path = alloc_printf("%s/%s", qd_path, qd_ent->d_name);//HERE qd_ent->d_name就是case文件名
/* Allow this to fail in case the other fuzzer is resuming or so... */
fd = open(path, O_RDONLY);//HERE 打开case文件
if (fd < 0) {
ck_free(path);
continue;
}
if (fstat(fd, &st)) PFATAL("fstat() failed");
/* Ignore zero-sized or oversized files. */
if (st.st_size && st.st_size <= MAX_FILE) {//HERE 确保case文件没有超过大小限制
u8 fault;
u8* mem = mmap(0, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);//HERE 为case分配空间，内容写进去
if (mem == MAP_FAILED) PFATAL("Unable to mmap '%s'", path);
/* See what happens. We rely on save_if_interesting() to catch major
errors and save the test case. */
write_to_testcase(mem, st.st_size);//HERE 运行测试case
fault = run_target(argv, exec_tmout);
if (stop_soon) return;
syncing_party = sd_ent->d_name;//HERE sd_ent->d_name是其他fuzzerid。syncing_party用来标志此case是从其他fuzzer那里同步过来的，在保存到硬盘命名时使用
queued_imported += save_if_interesting(argv, mem, st.st_size, fault);//HERE 查看运行结果，如果保存了打开的其他fuzzer里的case，queued_imported+1
syncing_party = 0;
munmap(mem, st.st_size);//HERE 删除分配的空间
if (!(stage_cur++ % stats_update_freq)) show_stats();
}
ck_free(path);
close(fd);
}
ck_write(id_fd, &next_min_accept, sizeof(u32), qd_synced_path);
close(id_fd);
closedir(qd);
ck_free(qd_path);
ck_free(qd_synced_path);
}
closedir(sd);
}
fuzz恢复
如果运行fuzzer时指定-i - , 那么fuzzer就会检查给出的-o文件夹下的内容，读取fuzzer状态，迁移文件等，尝试恢复到上一次fuzz退出时的状态。
总结
虽然写了这么多字，但还是有很多fuzzer的内部细节没有被介绍到(比如fuzzer如何把测试用例的内容传递给fuzz程序:通过一个隐藏文件)，有的是因为在代码中分布位置太过零散，虽然读的时候做了备注，一时半会还是不太好找，如果后期记不太清细节了想在翻看时，可能会整理起来。