AFL源码分析（搬运）
概念
设计思想
FUZZ基本大家都有一些大概的认识，对于有源码的项目来说我们使用afl-gcc或者alf-g++，这是gcc的wraper(封装)，在编译前向一些关键节点进行插桩，这些桩能够记录程序的执行路径，从而反馈出程序的执行情况。如果我们自己想写个fuzz的程序，最简单的思路莫过于将输入用例做随机变换之后尝试将其作为输入给程序查看执行情况，即调用execv这样的函数，但是这样的代价是很高的，因为在调用exec这个函数之后将产生一个的新程序来代替原进程，当前进程的数据段、代码段和堆栈段都会被改变，且新的进程的PID同原进程相同，我们无法通过PID来标识不同的测试用例，这种方式是很低效的。因此原作者用一种新的结构进行开发，即forserver架构。也就是每次要进行测试的时候就fork出一个子进程进行测试，子进程复制父进程的数据段等，且拥有自己的PID，这就是进程的写时复制。这样的好处就是我们省去了重新装载程序的时间原作者博客。
整体架构
在alf-gcc中先起了一个fork-server，在这个fork出的子进程里调用了execve去执行二进制程序，然后结合afl-as的代码可以看到插桩的桩代码中也包含了fork函数的调用，这样的话就是fuzzer->forkserver->exec target Bin->bin->bin_sub_process(被fuzz的app)，这样看起来fuzzer是最终被fuzz的程序的祖祖父进程，但是execve根据我们之前的介绍是直接将创建的进程替换掉原进程的，除非出错否则不会返回，因此实际上forkserver与target bin可以看作是同一个进程的不同程序，其父进程都是fuzzer，故最终的调用关系是下面这样的
1.png
2.png
这里我之前对forkserver的概念理解的一直不够准确，fuzzer执行fork()得到父进程和子进程，这里的父进程仍然为fuzzer，子进程则为target进程，即将来的fork server。一旦fork server接收到fuzzer的信息，便调用fork()，得到父进程和子进程，子进程是实际执行target的进程，其跳转到__afl_fork_resume。在这里会关闭不再需要的管道，并继续执行：父进程则仍然作为fork server运行，其会将子进程的pid通过状态管道发送给fuzzer，并等待子进程执行完毕；一旦子进程执行完毕，则再通过状态管道，将其结束状态发送给fuzzer；之后再次进入等待状态__afl_fork_wait_loop：
代码覆盖率
代码覆盖率是一种度量代码的覆盖程度的方式，也就是指源代码中的某行代码是否已执行；对二进制程序，还可将此概念理解为汇编代码中的某条指令是否已执行。对fuzz来说，当然希望每句代码都能被检测到，覆盖率越高越好。计量方式主要为三种：函数，基本块，边界 。 为了统计代码覆盖率，会用程序插装的方式，在特定位置加入统计代码覆盖率的代码。
afl-gcc.c
afl-gcc是gcc的一个封装(wrapper)，为了插桩替换了Assembler
find_as(argv[0]); //找到gcc/clang/llvm编译器
edit_params(argc, argv); //处理参数
execvp(cc_params[0], (char**)cc_params);//执行
afl-as.c和afl-as.h
The sole purpose of this wrapper is to preprocess assembly files generated by GCC / clang and inject the instrumentation bits included from afl-as.h. It is automatically invoked by the toolchain when compiling programs using afl-gcc / afl-clang.
处理不同平台设置标志，处理参数等等.重要函数add_instrumentation fprintf将插桩用的汇编用fprintf插如合适的地方，作者也提到了需要插桩的部分有条件跳转和基本块。其中R(MAP_SIZE)等同于random(2^16)，这个是为每个桩分配独有的ID，根据碰撞概率一般不会重复。
static void add_instrumentation（void）{
......
while (fgets(line, MAX_LINE, inf)) {//读取每行
......
fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32,
R(MAP_SIZE));//插入，注意R(MAP_SIZE)
......
//下面是怎么判断合适的地方插入，选择分支
}
}
以32位为例：
static const u8* trampoline_fmt_32 =
"\n"
"/* --- AFL TRAMPOLINE (32-BIT) --- */\n"
"\n"
".align 4\n"
"\n"
"leal -16(%%esp), %%esp\n" //抬高栈
"movl %%edi, 0(%%esp)\n" //保存寄存器
"movl %%edx, 4(%%esp)\n"
"movl %%ecx, 8(%%esp)\n"
"movl %%eax, 12(%%esp)\n"
"movl $0x%08x, %%ecx\n" //保存随机数，作用是标识每一个插桩节点。
"call __afl_maybe_log\n" //调用__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"
"\n"
"/* --- END --- */\n"
"\n";
分支记录
如何判断这条路径（代码）执行过，后面还要根据这些记录对后面变异有帮助。既要节约空间又要有效率，那单链表之类的肯定不能用, AFL用的是二元tuple(跳转的源地址和目标地址)来记录分支信息。
例如：
A->B->C->D->A-B
可以用[A,B] [B,C] [C,D] [D,A]四个二元组表示，只需要记录跳转的源地址和目标地址。并且[A,B]执行了两次，其余执行了一次，这里用hash映射在一张map中。
分支信息处理
共享内存还有个变量trace_bits来记录分支执行次数，fuzzer主要将每个分支处理次数归入count_class_lookup8表中, 比如执行了4-7次的其计数为8，最后用一个hash还判断新测试用例分支数增加没有
classify_counts((u32*)trace_bits);
共享内存
作为fuzzer，AFL并不是像无头苍蝇那样对输入文件无脑地随机变化（其实也支持这种方式，即dumb模式），其最大特点就是会对target进行插桩，以辅助mutated input的生成。具体地，插桩后的target，会记录执行过程中的分支信息；随后，fuzzer便可以根据这些信息，判断这次执行的整体流程和代码覆盖情况。AFL使用共享内存，来完成以上信息在fuzzer和target之间的传递。具体地，fuzzer在启动时，会执行setup_shm()方法进行配置。其首先调用shemget()分配一块共享内存，大小MAP_SIZE为64K。
分配成功后，该共享内存的标志符会被设置到环境变量中，从而之后fork()得到的子进程可以通过该环境变量，得到这块共享内存的标志符。
并且，fuzzer本身，会使用变量trace_bits来保存共享内存的地址，在每次target执行之前，fuzzer首先将该共享内容清零，如果使用了fork server模式，那么上述获取共享内存的操作，是在fork server中进行；随后fork出来的子进程，只需直接使用这个共享内存即可。
forkserver
这是一种为了不使用execve()函数提高效率想出来的办法，省掉动态链接等过程，在lcamtuf的blog上也有详细的介绍。之前在__afl_maybe_log后面还调用了_afl_store这个函数，伪代码：
cur_location = <COMPILE_TIME_RANDOM>; //随机数当前分支
shared_mem[cur_location ^ prev_location]++; //前一分支和当前分支锁表示的随机数异或表示二元tuple映射map
prev_location = cur_location >> 1; //将当前分支再记录
为什么当前分支最后需要向右移一位？比如A->A或者A->B->A这种不右移，会异或为0
afl-fuzz.c
EXP_ST void init_forkserver(char** argv) {
int st_pipe[2], ctl_pipe[2];//命令管道和状态管道
......
execv(target_path, argv); //执行fork server
}
- 怎么高效重复执行测试样例?
- 记录样例的状态?
开始fork service确认创建完毕:
/* Close the unneeded endpoints. */
//关闭不需要的通道
close(ctl_pipe[0]);
close(st_pipe[1]);
//读取通道状态命令
fsrv_ctl_fd = ctl_pipe[1];
fsrv_st_fd = st_pipe[0];
......
rlen = read(fsrv_st_fd, &status, 4);//从状态通道读取4个字节
/* If we have a four-byte "hello" message from the server, we're all set.
Otherwise, try to figure out what went wrong. */
if (rlen == 4) {//判断读取是否成功
OKF("All right - fork server is up.");
return;
}
afl_maybe_log()
.text:0000000000000950 lahf
.text:0000000000000951 seto al
.text:0000000000000954 mov rdx, cs:__afl_area_ptr
.text:000000000000095B test rdx, rdx
.text:000000000000095E jz short __afl_setup
lahf作用是将EFLAGS 寄存器标志位加载到AH,seto为溢出置位，之后判断__afl_area_ptr是否为空，这个指针用来保存共享内存，如果不为空表明已经初始化完成了，直接进入__afl_store，否则先调用__afl_setup初始化
afl_store
这里首先把__afl_prev_loc(之前的位置)同当前位置的key异或，保存在edi寄存器，之后当前的key右移一位，作为下一个的__afl_prev_loc，这个右移是一个很巧妙的设计，如果代码块的跳转为A->B或B->A，直接对两个Key异或结果是一样的，因此右移可以区分出一些特殊情况。下面那个incb代码中edx为map,edi为索引，即map表中对应的索引加一，表明一次hit。
afl_setup
如果__afl_setup_failure的值不为0(0为正常，非零异常)，通过getenv($SHM_ENV_VAR)环境变量来获得共享内存的ID，如果不为空就调用atoi以及shmat，最终将这个地址存储在__afl_area_ptr中方便之后使用(不必再初始化)，下面启动fork_server。
afl_forkserver
fork_server和fuzzer之间是通过管道通信的，在宏定义里可以看到默认的FORKSRV_FD为198，这里读管道为198，写管道为199。开始先通知fuzzer，之后在read处阻塞等待fuzzer的消息，得到fuzzer通知之后父进程fork出一个子进程，在这个子进程里会关闭与fuzzer通信的文件描述符，jmp到__afl_store记录下基本块的hit情况之后向后继续执行main函数。而父进程记录下刚才启动的子进程的pid发送给fuzzer并等待子进程执行完毕，子进程结束之后将其状态告知fuzzer。之后开始新一轮的等待。后面每次基本块都会执行__afl_maybe_log，但由于已经得到了共享内存的位置不会fork新的进程，之后只是记录基本块的跳转情况，这样就大大节约了资源。
afl_fork_wait_loop
-
fork server直到从状态管道read到4个字节表明fuzzer准备好了 -
记录子进程的pid，一旦子进程执行完了，通过状态管道发送到
fuzzer继续执行
afl-fuzz.c
这个是fuzz启动的入口，从main函数开始，先是获取时间/扔随机数种子/解析参数/设置异常处理/设置环境变量/设置banner/检查终端/获取CPU核数，然后到了设置共享内存的函数.
EXP_ST void setup_shm(void) {
u8* shm_str;
if (!in_bitmap) memset(virgin_bits, 255, MAP_SIZE);
//数组用来存储有无见过崩溃/tmouts
memset(virgin_tmout, 255, MAP_SIZE);
memset(virgin_crash, 255, MAP_SIZE);
shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);
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);
ck_free(shm_str);
//shm_id是这块共享内存的标识id，NULL地址让系统自动选择合适的一块进行分配
trace_bits = shmat(shm_id, NULL, 0);
if (!trace_bits) PFATAL("shmat() failed");
}
下面是对不同的执行次数进行划分(比如32次到127次都会认为是64次)
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
};
pivot_input在输出目录中为输入的testcase创建硬链接，其中的mark_as_det_done将一些经过确定性变异的文件放入deterministic_done目录，之后就不会再重复测试。load_extras加载用户自己定义的token，find_timeout设置超时时间，setup_stdio_file设置输入输出目录，check_binary检查二进制文件的合法性(是否是bash文件，是否有ELF头以及是否插桩过了)。
第一次的fuzz,核心函数为perform_dry_run，其功能是将给的所有测试用例跑一遍，确保软件如期工作，故只会跑一遍。需要说明的是这里的文件在初始的时候被抽象到一个自定义的结构体中，且组成了队列。在这个函数中核心的调用为res = calibrate_case(argv, q, use_mem, 0, 1);，之后对res判断确定程序的运行情况(crash or sth)，拿翻译看下，这函数的意思是校准用例，看注释的话意思应该是在输入的时候进行测试，前期发现一些有问题的测试用例。应该一共跑个3次或者8次(取决于是否是快速模式)，如果没启动forkserver那么在这用init_forkserver启动。
然后直接就fork出子进程，为其设置一些资源，拷贝文件描述符，设置环境变量等，最终调用execv(target_path, argv);替换进程去执行Binary，由于execv正常是不会返回的，所以出错后后面会在共享内存那里设置一个EXEC_FAIL_SIG,通过对于管道文件的读取可以判断forkserver是否正常启动，这块就和之前插桩的代码联系了起来，判断方式是说如果正常操作会有一个4字节的Hello信息，确保启动正常就进入waitpid(forksrv_pid, &status, 0)的等待，后面对接收到的status进行判断确定子进程的运行状况。
EXP_ST void init_forkserver(char** argv) {
static struct itimerval it;
int st_pipe[2], ctl_pipe[2];
int status;
s32 rlen;
ACTF("Spinning up the fork server...");
if (pipe(st_pipe) || pipe(ctl_pipe)) PFATAL("pipe() failed");
forksrv_pid = fork();
if (forksrv_pid < 0) PFATAL("fork() failed");
if (!forksrv_pid) {
//子进程
struct rlimit r;
/* Umpf. On OpenBSD, the default fd limit for root users is set to
soft 128. Let's try to fix that... */
if (!getrlimit(RLIMIT_NOFILE, &r) && r.rlim_cur < FORKSRV_FD + 2) {
//设置可以打开的最大的文件描述符的数量
r.rlim_cur = FORKSRV_FD + 2;
setrlimit(RLIMIT_NOFILE, &r); /* Ignore errors */
}
if (mem_limit) {
r.rlim_max = r.rlim_cur = ((rlim_t)mem_limit) << 20;
#ifdef RLIMIT_AS
//进程最大的虚地址内存
setrlimit(RLIMIT_AS, &r); /* Ignore errors */
#else
/* This takes care of OpenBSD, which doesn't have RLIMIT_AS, but
according to reliable sources, RLIMIT_DATA covers anonymous
maps - so we should be getting good protection against OOM bugs. */
setrlimit(RLIMIT_DATA, &r); /* Ignore errors */
#endif /* ^RLIMIT_AS */
}
/* Dumping cores is slow and can lead to anomalies if SIGKILL is delivered
before the dump is complete. */
r.rlim_max = r.rlim_cur = 0;
//4 core
setrlimit(RLIMIT_CORE, &r); /* Ignore errors */
/* Isolate the process and configure standard descriptors. If out_file is
specified, stdin is /dev/null; otherwise, out_fd is cloned instead. */
//为子进程分配新的session id
setsid();
dup2(dev_null_fd, 1);
dup2(dev_null_fd, 2);
if (out_file) {
dup2(dev_null_fd, 0);
} else {
dup2(out_fd, 0);
close(out_fd);
}
/* Set up control and status pipes, close the unneeded original fds. */
if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed");
if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed");
close(ctl_pipe[0]);
close(ctl_pipe[1]);
close(st_pipe[0]);
close(st_pipe[1]);
close(out_dir_fd);
close(dev_null_fd);
close(dev_urandom_fd);
close(fileno(plot_file));
/* This should improve performance a bit, since it stops the linker from
doing extra work post-fork(). */
//非延迟绑定
if (!getenv("LD_BIND_LAZY")) setenv("LD_BIND_NOW", "1", 0);
/* Set sane defaults for ASAN if nothing else specified. */
setenv("ASAN_OPTIONS", "abort_on_error=1:"
"detect_leaks=0:"
"symbolize=0:"
"allocator_may_return_null=1", 0);
/* MSAN is tricky, because it doesn't support abort_on_error=1 at this
point. So, we do this in a very hacky way. */
setenv("MSAN_OPTIONS", "exit_code=" STRINGIFY(MSAN_ERROR) ":"
"symbolize=0:"
"abort_on_error=1:"
"allocator_may_return_null=1:"
"msan_track_origins=0", 0);
execv(target_path, argv);
//失败会到这里来
/* Use a distinctive bitmap signature to tell the parent about execv()
falling through. */
*(u32*)trace_bits = EXEC_FAIL_SIG;
exit(0);
}
//父进程
/* Close the unneeded endpoints. */
close(ctl_pipe[0]);
close(st_pipe[1]);
fsrv_ctl_fd = ctl_pipe[1];
fsrv_st_fd = st_pipe[0];
/* Wait for the fork server to come up, but don't wait too long. */
it.it_value.tv_sec = ((exec_tmout * FORK_WAIT_MULT) / 1000);
it.it_value.tv_usec = ((exec_tmout * FORK_WAIT_MULT) % 1000) * 1000;
setitimer(ITIMER_REAL, &it, NULL);
rlen = read(fsrv_st_fd, &status, 4);
it.it_value.tv_sec = 0;
it.it_value.tv_usec = 0;
setitimer(ITIMER_REAL, &it, NULL);
/* If we have a four-byte "hello" message from the server, we're all set.
Otherwise, try to figure out what went wrong. */
if (rlen == 4) {
OKF("All right - fork server is up.");
return;
}
if (child_timed_out)
FATAL("Timeout while initializing fork server (adjusting -t may help)");
if (waitpid(forksrv_pid, &status, 0) <= 0)
PFATAL("waitpid() failed");
if (WIFSIGNALED(status)) {
if (mem_limit && mem_limit < 500 && uses_asan) {
SAYF("n" cLRD "[-] " cRST
"Whoops, the target binary crashed suddenly, before receiving any inputn"
" from the fuzzer! Since it seems to be built with ASAN and you have an"
" restrictive memory limit configured, this is expected; please readn"
" %s/notes_for_asan.txt for help.n", doc_path);
} else if (!mem_limit) {
SAYF("n" cLRD "[-] " cRST
"Whoops, the target binary crashed suddenly, before receiving any inputn"
" from the fuzzer! There are several probable explanations:nn"
" - The binary is just buggy and explodes entirely on its own. If so, youn"
" need to fix the underlying problem or find a better replacement.nn"
#ifdef __APPLE__
" - On MacOS X, the semantics of fork() syscalls are non-standard and mayn"
" break afl-fuzz performance optimizations when running platform-specificn"
" targets. To fix this, set AFL_NO_FORKSRV=1 in the environment.nn"
#endif /* __APPLE__ */
" - Less likely, there is a horrible bug in the fuzzer. If other optionsn"
" fail, poke <lcamtuf@coredump.cx> for troubleshooting tips.n");
} else {
SAYF("n" cLRD "[-] " cRST
"Whoops, the target binary crashed suddenly, before receiving any inputn"
" from the fuzzer! There are several probable explanations:nn"
" - The current memory limit (%s) is too restrictive, causing then"
" target to hit an OOM condition in the dynamic linker. Try bumping upn"
" the limit with the -m setting in the command line. A simple way confirmn"
" this diagnosis would be:nn"
#ifdef RLIMIT_AS
" ( ulimit -Sv $[%llu << 10]; /path/to/fuzzed_app )nn"
#else
" ( ulimit -Sd $[%llu << 10]; /path/to/fuzzed_app )nn"
#endif /* ^RLIMIT_AS */
" Tip: you can use http://jwilk.net/software/recidivm to quicklyn"
" estimate the required amount of virtual memory for the binary.nn"
" - The binary is just buggy and explodes entirely on its own. If so, youn"
" need to fix the underlying problem or find a better replacement.nn"
#ifdef __APPLE__
" - On MacOS X, the semantics of fork() syscalls are non-standard and mayn"
" break afl-fuzz performance optimizations when running platform-specificn"
" targets. To fix this, set AFL_NO_FORKSRV=1 in the environment.nn"
#endif /* __APPLE__ */
" - Less likely, there is a horrible bug in the fuzzer. If other optionsn"
" fail, poke <lcamtuf@coredump.cx> for troubleshooting tips.n",
DMS(mem_limit << 20), mem_limit - 1);
}
FATAL("Fork server crashed with signal %d", WTERMSIG(status));
}
if (*(u32*)trace_bits == EXEC_FAIL_SIG)
FATAL("Unable to execute target application ('%s')", argv[0]);
if (mem_limit && mem_limit < 500 && uses_asan) {
SAYF("n" cLRD "[-] " cRST
"Hmm, looks like the target binary terminated before we could complete an"
" handshake with the injected code. Since it seems to be built with ASAN andn"
" you have a restrictive memory limit configured, this is expected; pleasen"
" read %s/notes_for_asan.txt for help.n", doc_path);
} else if (!mem_limit) {
SAYF("n" cLRD "[-] " cRST
"Hmm, looks like the target binary terminated before we could complete an"
" handshake with the injected code. Perhaps there is a horrible bug in then"
" fuzzer. Poke <lcamtuf@coredump.cx> for troubleshooting tips.n");
} else {
SAYF("n" cLRD "[-] " cRST
"Hmm, looks like the target binary terminated before we could complete an"
" handshake with the injected code. There are %s probable explanations:nn"
"%s"
" - The current memory limit (%s) is too restrictive, causing an OOMn"
" fault in the dynamic linker. This can be fixed with the -m option. An"
" simple way to confirm the diagnosis may be:nn"
#ifdef RLIMIT_AS
" ( ulimit -Sv $[%llu << 10]; /path/to/fuzzed_app )nn"
#else
" ( ulimit -Sd $[%llu << 10]; /path/to/fuzzed_app )nn"
#endif /* ^RLIMIT_AS */
" Tip: you can use http://jwilk.net/software/recidivm to quicklyn"
" estimate the required amount of virtual memory for the binary.nn"
" - Less likely, there is a horrible bug in the fuzzer. If other optionsn"
" fail, poke <lcamtuf@coredump.cx> for troubleshooting tips.n",
getenv(DEFER_ENV_VAR) ? "three" : "two",
getenv(DEFER_ENV_VAR) ?
" - You are using deferred forkserver, but __AFL_INIT() is nevern"
" reached before the program terminates.nn" : "",
DMS(mem_limit << 20), mem_limit - 1);
}
FATAL("Fork server handshake failed");
}
等启动forkserver完毕之后，又一个核心函数出现了，就是这里的run_target，这个函数在之后每次调用新的二进制程序的时候都会使用，其先检查有无启动forkserver，没有的话就先启动一个，否则我们只注重与forkserver的交互即可(使用ctl_fd写,st_fd读)，因为 binary那边会一直返回子进程的进程号，所以一直等到结果为-1即可中止，最后拿classify_counts((u32*)trace_bits);将结果进行分类。 has_new_bits判断之前的测试有没有增加新的路径(二元的tuple)，逻辑应该就是拿virgin_map这个map同trace_bits进行比较. update_bitmap_score这个函数很有意思，注释里说每当我们发现一个新的路径，都会调用这个函数来判断其是不是更加 favorable，这个favorable的意思是说是否包含最小的路径集合来遍历到所有bitmap中的位，我们专注于这些集合而忽略其他的。核心的比较方式是fav_factor = q->exec_us * q->len;即测试用例执行的时间以及输入长度的乘积，注释说希望找到更快或者规模更小的用例，一旦当前的fav_factor比top_rated[i]要小就会更新这个表，将原来的winner的tc_ref--，当前的插入表中。
至此，我们将perform_dry_run中的函数分析完毕。
cull_queue
下面会调用cull_queue函数，函数前的注释说我们已经进入了第二个阶段，即用routine来遍历top_rated entry，不断寻找之前没见到过的bytes并且将它们标为favored。函数首先判断sore_changed是不是为真,之后拿贪心算法找能够遍历到所有节点的最小测试集合，比如有三个节点n0,n1,n2,n3和3个测试用例s1,s2,s3。top_rated[0]=s0,top_rated[s2]=s2且s0覆盖n0,n1;s1覆盖n2其中初始化temp_v=[1,1,1,1]，1就表示对应节点没有访问到，初始化为都没访问到。开始先判断temp_v[0]=1，说明没访问到，之后就去看top_rated[0]，发现为1，说明存在一个用例能访问到这个n0，因此进一步查看这个用例，得到其覆盖范围trace_mini=[1,1,0]故据此更新temp_v=[0,0,1]，往下看n1，访问过了，再看n2仍未访问到，再去看top_rated得到s2，再看s2的覆盖范围更新temp_v，就这样标注s0和s1为favored，如果他俩还没有被fuzz，还要pending_favored++。完成上述操作之后将无用的用例标为冗余。
再往后就是一个大的循环，也是AFL最最核心的部分，循环开始依然是用cull_queue对队列进行筛选，如果一个cycle都没有新发现尝试更换策略，最终调用skipped_fuzz = fuzz_one(use_argv);这个函数里对测试用例做了变异，下面一节着重分析这个函数AFL的变异策略
变异策略
开始先根据标志位跳过一些测试用例。如果fuzz过或者没有queue_cur->favored标志，会有99%的概率被跳过；如果fuzzed&&no-favored，有90%概率跳过，如果没有fuzz过，有75%概率跳过。之后打开文件，将内容map到in_buf上。
假如之前校准的时候有错误，则还会进行一次校准CALIBRATION，当然校准错误的次数有上限，为三次。
TRIMMING
下面一步为,调用方式为u8 res = trim_case(argv, queue_cur, in_buf);这个函数主要是用来调整测试用例大小的。起始以文件的1/16大小，一直到1/1024为步长，依次删除文件的某一步长(write_with_gap函数)，将得到的check_sum同原来的比较，如果相同说明这部分不会影响测试的结果，删除这部分。之后调用calculate_score为这次测试的质量进行打分，这个分数在之后的havoc_stage使用。下面就是主要的变异策略。
BITFLIP
BITFLIP就是按位翻转，有多种翻转位数/步长的操作，值得一提的是，如果一段连续的序列翻转之后都不会改变(原执行路径破坏)，则可以将这段序列识别为一个token。程序会记录下来为后面变异做准备。之后调用common_fuzz_stuff测试变异后的文件。在8/8模式下，会生成一个eff_map。这个表的意义是如果我们翻转一整个比特都不能得到1(同原执行路径不同)，那么这个字节很有可能属于data而非metadata(元数据)。因而在之后的变异中会跳过这些无用的字节。
ARITHMETIC
是对数据做加减运算，同样有多种步长/翻转长度模式。这次变换就会利用刚才的eff_map筛选，加减的上限为35，变换过程中还会对数据大小端进行判断。
/* Maximum offset for integer addition / subtraction stages: */
#define ARITH_MAX 35
INTERESTING
是做插入/替换等变换，替换成的数字是一些interesting_val，可以看到下面都是一些容易整数溢出的数字。替换的大小也有8/16/32bit
DICTIONARY
是替换/插入token到原文件中，共有user extras (over)/user extras (insert)/auto extras (over)。其中替换是有上限的，数量高于上限就按概率替换。
HAVOC
综合之前的变异方式，引用Seebug一篇文章
随机选取某个bit进行翻转
随机选取某个byte，将其设置为随机的interesting value
随机选取某个word，并随机选取大、小端序，将其设置为随机的interesting value
随机选取某个dword，并随机选取大、小端序，将其设置为随机的interesting value
随机选取某个byte，对其减去一个随机数
随机选取某个byte，对其加上一个随机数
随机选取某个word，并随机选取大、小端序，对其减去一个随机数
随机选取某个word，并随机选取大、小端序，对其加上一个随机数
随机选取某个dword，并随机选取大、小端序，对其减去一个随机数
随机选取某个dword，并随机选取大、小端序，对其加上一个随机数
随机选取某个byte，将其设置为随机数
随机删除一段bytes
随机选取一个位置，插入一段随机长度的内容，其中75%的概率是插入原文中随机位置的内容，25%的概率是插入一段随机选取的数
随机选取一个位置，替换为一段随机长度的内容，其中75%的概率是替换成原文中随机位置的内容，25%的概率是替换成一段随机选取的数
随机选取一个位置，用随机选取的token（用户提供的或自动生成的）替换
随机选取一个位置，用随机选取的token（用户提供的或自动生成的）插入
SPLICING
将2个seed文件随机位置分割开，将当前文件的头同另一个文件的尾拼起来，中间还会检查选取的两个文件的差异性以及拼接之后的文件的变异性。之后再给havoc继续折腾，测试，这个seed搞完再换cycle的下一个，一直到一个cycle结束。然后就是另一个cycle，新的变异(因为上次变异可能找到了新的路径，cull_queue就是发掘新的路径)
网友评论