1 前言
大部分只读了主要部分，更详细的信息可以参考一下看雪论坛的这篇文章。由于笔者能力有限，许多内容也是就着下面这篇文章以及作者的英文注释进行阅读并记录，所以存在引用该处的内容部分。同时也感谢前辈们的阅读记录！有错误还请指正。
AFL afl_fuzz.c 详细分析 - 看雪学院 - 微信公众号文章
源码获取地址https://github.com/google/AFL
参考了以下文章
AFL-fuzz工具分析_Chen_zju的博客-CSDN博客_afl-fuzz coreutils
2 结构
AFL的主要函数内容如下：
2.1 main函数
2.1.1 包含从命令行中获取参数配置运行模式
while ((opt = getopt(argc, argv, "+i:o:f:m:t:T:dnCB:S:M:x:Q")) > 0)
switch (opt) {
case 'i': /* input dir */
if (in_dir) FATAL("Multiple -i options not supported");
in_dir = optarg;
if (!strcmp(in_dir, "-")) in_place_resume = 1;
break;
case 'o': /* output dir */
if (out_dir) FATAL("Multiple -o options not supported");
out_dir = optarg;
break;
case 'M': { /* master sync ID */
u8* c;
if (sync_id) FATAL("Multiple -S or -M options not supported");
sync_id = ck_strdup(optarg);
if ((c = strchr(sync_id, ':'))) {
*c = 0;
if (sscanf(c + 1, "%u/%u", &master_id, &master_max) != 2 ||
!master_id || !master_max || master_id > master_max ||
master_max > 1000000) FATAL("Bogus master ID passed to -M");
}
force_deterministic = 1;
}
break;
case 'S':
if (sync_id) FATAL("Multiple -S or -M options not supported");
sync_id = ck_strdup(optarg);
break;
case 'f': /* target file */
if (out_file) FATAL("Multiple -f options not supported");
out_file = optarg;
break;
case 'x': /* dictionary */
if (extras_dir) FATAL("Multiple -x options not supported");
extras_dir = optarg;
break;
case 't': { /* timeout */
u8 suffix = 0;
if (timeout_given) FATAL("Multiple -t options not supported");
if (sscanf(optarg, "%u%c", &exec_tmout, &suffix) < 1 ||
optarg[0] == '-') FATAL("Bad syntax used for -t");
if (exec_tmout < 5) FATAL("Dangerously low value of -t");
if (suffix == '+') timeout_given = 2; else timeout_given = 1;
break;
}
case 'm': { /* mem limit */
u8 suffix = 'M';
if (mem_limit_given) FATAL("Multiple -m options not supported");
mem_limit_given = 1;
if (!strcmp(optarg, "none")) {
mem_limit = 0;
break;
}
if (sscanf(optarg, "%llu%c", &mem_limit, &suffix) < 1 ||
optarg[0] == '-') FATAL("Bad syntax used for -m");
switch (suffix) {
case 'T': mem_limit *= 1024 * 1024; break;
case 'G': mem_limit *= 1024; break;
case 'k': mem_limit /= 1024; break;
case 'M': break;
default: FATAL("Unsupported suffix or bad syntax for -m");
}
if (mem_limit < 5) FATAL("Dangerously low value of -m");
if (sizeof(rlim_t) == 4 && mem_limit > 2000)
FATAL("Value of -m out of range on 32-bit systems");
}
break;
case 'd': /* skip deterministic */
if (skip_deterministic) FATAL("Multiple -d options not supported");
skip_deterministic = 1;
use_splicing = 1;
break;
case 'B': /* load bitmap */
/* This is a secret undocumented option! It is useful if you find
an interesting test case during a normal fuzzing process, and want
to mutate it without rediscovering any of the test cases already
found during an earlier run.
To use this mode, you need to point -B to the fuzz_bitmap produced
by an earlier run for the exact same binary... and that's it.
I only used this once or twice to get variants of a particular
file, so I'm not making this an official setting. */
if (in_bitmap) FATAL("Multiple -B options not supported");
in_bitmap = optarg;
read_bitmap(in_bitmap);
break;
case 'C': /* crash mode */
if (crash_mode) FATAL("Multiple -C options not supported");
crash_mode = FAULT_CRASH;
break;
case 'n': /* dumb mode */
if (dumb_mode) FATAL("Multiple -n options not supported");
if (getenv("AFL_DUMB_FORKSRV")) dumb_mode = 2; else dumb_mode = 1;
break;
case 'T': /* banner */
if (use_banner) FATAL("Multiple -T options not supported");
use_banner = optarg;
break;
case 'Q': /* QEMU mode */
if (qemu_mode) FATAL("Multiple -Q options not supported");
qemu_mode = 1;
if (!mem_limit_given) mem_limit = MEM_LIMIT_QEMU;
break;
default:
usage(argv[0]);
}
第一行为从命令行中读取参数
while ((opt = getopt(argc, argv, "+i:o:f:m:t:T:dnCB:S:M:x:Q")) > 0)
AFL提供的指令选项和其对应的功能如下，且在代码相应块也进行了注释
之后一部分代码涉及到根据命令行参数进行了设置，如没有源码的情况下，使用dumb mode对二进制程序进行打桩。（对应源码后面的一堆if）
2.1.2 预处理
save_cmdline(argc, argv); /*保存命令行参数*/
fix_up_banner(argv[optind]); /*修剪并且创建一个运行横幅*/
check_if_tty(); /*检查是否在TTy终端上运行，修改not_on_tty的值*/
之后是一系列对cpu的检查
get_core_count();
#ifdef HAVE_AFFINITY
bind_to_free_cpu();
#endif /* HAVE_AFFINITY */
check_crash_handling();
check_cpu_governor();
setup_post(); /*加载后处理器*/
setup_shm(); /*设置共享内存块，影响参数g_shm_file_path，g_shm_fd，_shm_base，trace_bits。trace_bits参数就是在这里设置并初始化置零的*/
init_count_class16();
2.1.3 执行testcase生成初始化的queue和bitmap
setup_dirs_fds();
read_testcases(); /*读取测试用例*/
load_auto(); /*自动生成附加负载*/
pivot_inputs(); /*static void pivot_inputs(void)在输出目录中为输入测试用例创建硬链接，选择好名称并相应地旋转。
使用函数link_or_copy重新命名并且拷贝；使用函数mark_as_det_done为已经经过确定性变异（deterministic）阶段的testcase文件放入deterministic_done文件夹。这样经过deterministic的testcase就不用浪费时间进行重复。*/
if (extras_dir) load_extras(extras_dir); /*加载token*/
if (!timeout_given) find_timeout();
start_time = get_cur_time(); /*获取当前时间作为开始时间*/
if (qemu_mode)
use_argv = get_qemu_argv(argv[0], argv + optind, argc - optind);
else
use_argv = argv + optind;
perform_dry_run(use_argv); /*执行input文件下预先准备的所有testcase*/
其中关键函数是perform_dry_run，将在2.3节中分析。
2.1.4 主循环前处理
cull_queue(); /*放在2.2中分析*/
show_init_stats(); /*处理完输入文件后显示提示信息*/
seek_to = find_start_position(); /*找到队列开始的位置*/
write_stats_file(0, 0, 0);
save_auto(); /*自动更新token*/
if (stop_soon) goto stop_fuzzing;
/* Woop woop woop */
if (!not_on_tty) {
sleep(4);
start_time += 4000;
if (stop_soon) goto stop_fuzzing;
}
2.1.5 主循环
也是最重要的一个部分，大致包括以下步骤
1）判断queue_cur是否为空，如果是，则表示已经完成对队列的遍历，初始化相关参数，重新开始遍历队列
2）找到queue入口的testcase，对seek_to在主循环前seek_to = find_start_position()；进行了赋值，直接跳到该testcase
3）如果一整个队列循环都没新发现，尝试重组策略。
if (!queue_cur) { /*步骤1*/
queue_cycle++;
current_entry = 0;
cur_skipped_paths = 0;
queue_cur = queue;
while (seek_to) { /*步骤2，其中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. 也就是步骤3*/
if (queued_paths == prev_queued) {
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"))
sync_fuzzers(use_argv);
}
4）调用关键函数fuzz_one()对该testcase进行fuzz。fuzz_one()函数参见2.4。
5）上面的变异完成后，AFL会对文件队列的下一个进行变异处理。当队列中的全部文件都变异测试后，就完成了一个”cycle”，这个就是AFL状态栏右上角的”cycles done”。而正如cycle的意思所说，整个队列又会从第一个文件开始，再次进行变异，不过与第一次变异不同的是，这一次就不需要再进行deterministic fuzzing了。如果用户不停止AFL，那么seed文件将会一遍遍的变异下去。
其中核心部分在fuzz_one()中，将在2.4节中讨论。
2.2 cull_queue()
这个函数主要是用来修剪队列的，它尝试找到更小的测试用例子集进行使用，同时保证这个子集仍然能覆盖到目前的所有元组。
检查toprated[]类目，以此前未见过的byte依次争夺优胜者，然后把他们标记为favored在下次开始跑之前。根据top_rated设置queue中的favored标志。在fuzz的过程中favored 条目将会给与更多的时间。
static void cull_queue(void) {
struct queue_entry* q;
static u8 temp_v[MAP_SIZE >> 3];
u32 i;
if (dumb_mode || !score_changed) return; /*如果是dumb模式或者score_changed没有改变，则没有出现新的"favored"竞争者，无须校准直接返回。*/
score_changed = 0;
memset(temp_v, 255, MAP_SIZE >> 3);
queued_favored = 0;
pending_favored = 0;
q = queue;
while (q) {
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++) 、/*遍历bitmap中的每个Byte*/
if (top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) { /*判断每个byte的top_rated是否存在 该byte对应的temp_v是否被置为1。*/
u32 j = MAP_SIZE >> 3;
/* 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) {
mark_as_redundant(q, !q->favored);
q = q->next;
}
}
这里有一个favored标记，详细用例可以参照以下实例
tuple t0,t1,t2,t3,t4；seed s0,s1,s2 初始化temp_v=[1,1,1,1,1]
s1可覆盖t2,t3 | s2覆盖t0,t1,t4，并且top_rated[0]=s2，top_rated[2]=s1
开始后判断temp_v[0]=1，说明t0没有被访问
top_rated[0]存在(s2) -> 判断s2可以覆盖的范围 -> trace_mini=[1,1,0,0,1]
更新temp_v=[0,0,1,1,0]
标记s2为favored
继续判断temp_v[1]=0，说明t1此时已经被访问过了，跳过
继续判断temp_v[2]=1，说明t2没有被访问
top_rated[2]存在(s1) -> 判断s1可以覆盖的范围 -> trace_mini=[0,0,1,1,0]
更新temp_v=[0,0,0,0,0]
标记s1为favored
此时所有tuple都被覆盖，favored为s1,s2
同时，update_bitmap_score()会在trim_case()和calibrate_case()中调用，来维护一个最小favored的测试用例集合（top_rated[i]）。
最后对queue中，没有被标记为favored的testcase进行冗余标记，使用函数mark_as_redundant
2.3 perform_dry_run
static void perform_dry_run(char** argv) {
struct queue_entry* q = queue;
u32 cal_failures = 0;
u8* skip_crashes = getenv("AFL_SKIP_CRASHES");
while (q) { ... }
if (cal_failures) {
if (cal_failures == queued_paths)
FATAL("All test cases time out%s, giving up!",
skip_crashes ? " or crash" : "");
WARNF("Skipped %u test cases (%0.02f%%) due to timeouts%s.", cal_failures,
((double)cal_failures) * 100 / queued_paths,
skip_crashes ? " or crashes" : "");
if (cal_failures * 5 > queued_paths)
WARNF(cLRD "High percentage of rejected test cases, check settings!");
}
OKF("All test cases processed.");
}
其中最主要部分就是这里的while(q)循环。
while (q) {
u8* use_mem;
u8 res;
s32 fd;
u8* fn = strrchr(q->fname, '/') + 1;
ACTF("Attempting dry run with '%s'...", fn);
fd = open(q->fname, O_RDONLY);
if (fd < 0) PFATAL("Unable to open '%s'", q->fname);
use_mem = ck_alloc_nozero(q->len);
if (read(fd, use_mem, q->len) != q->len)
FATAL("Short read from '%s'", q->fname);
close(fd);
res = calibrate_case(argv, q, use_mem, 0, 1);
ck_free(use_mem);
if (stop_soon) return;
if (res == crash_mode || res == FAULT_NOBITS)
SAYF(cGRA " len = %u, map size = %u, exec speed = %llu us\n" cRST,
q->len, q->bitmap_size, q->exec_us);
switch (res) {
case FAULT_NONE:
if (q == queue) check_map_coverage();
if (crash_mode) FATAL("Test case '%s' does *NOT* crash", fn);
break;
case FAULT_TMOUT:
if (timeout_given) {
/* The -t nn+ syntax in the command line sets timeout_given to '2' and
instructs afl-fuzz to tolerate but skip queue entries that time
out. */
if (timeout_given > 1) {
WARNF("Test case results in a timeout (skipping)");
q->cal_failed = CAL_CHANCES;
cal_failures++;
break;
}
SAYF("\n" cLRD "[-] " cRST
"The program took more than %u ms to process one of the initial test cases.\n"
" Usually, the right thing to do is to relax the -t option - or to delete it\n"
" altogether and allow the fuzzer to auto-calibrate. That said, if you know\n"
" what you are doing and want to simply skip the unruly test cases, append\n"
" '+' at the end of the value passed to -t ('-t %u+').\n", exec_tmout,
exec_tmout);
FATAL("Test case '%s' results in a timeout", fn);
} else {
SAYF("\n" cLRD "[-] " cRST
"The program took more than %u ms to process one of the initial test cases.\n"
" This is bad news; raising the limit with the -t option is possible, but\n"
" will probably make the fuzzing process extremely slow.\n\n"
" If this test case is just a fluke, the other option is to just avoid it\n"
" altogether, and find one that is less of a CPU hog.\n", exec_tmout);
FATAL("Test case '%s' results in a timeout", fn);
}
case FAULT_CRASH:
if (crash_mode) break;
if (skip_crashes) {
WARNF("Test case results in a crash (skipping)");
q->cal_failed = CAL_CHANCES;
cal_failures++;
break;
}
if (mem_limit) {
SAYF("\n" cLRD "[-] " cRST
"Oops, the program crashed with one of the test cases provided. There are\n"
" several possible explanations:\n\n"
" - The test case causes known crashes under normal working conditions. If\n"
" so, please remove it. The fuzzer should be seeded with interesting\n"
" inputs - but not ones that cause an outright crash.\n\n"
" - The current memory limit (%s) is too low for this program, causing\n"
" it to die due to OOM when parsing valid files. To fix this, try\n"
" bumping it up with the -m setting in the command line. If in doubt,\n"
" try something along the lines of:\n\n"
#ifdef RLIMIT_AS
" ( ulimit -Sv $[%llu << 10]; /path/to/binary [...] <testcase )\n\n"
#else
" ( ulimit -Sd $[%llu << 10]; /path/to/binary [...] <testcase )\n\n"
#endif /* ^RLIMIT_AS */
" Tip: you can use http://jwilk.net/software/recidivm to quickly\n"
" estimate the required amount of virtual memory for the binary. Also,\n"
" if you are using ASAN, see %s/notes_for_asan.txt.\n\n"
#ifdef __APPLE__
" - On MacOS X, the semantics of fork() syscalls are non-standard and may\n"
" break afl-fuzz performance optimizations when running platform-specific\n"
" binaries. To fix this, set AFL_NO_FORKSRV=1 in the environment.\n\n"
#endif /* __APPLE__ */
" - Least likely, there is a horrible bug in the fuzzer. If other options\n"
" fail, poke <lcamtuf@coredump.cx> for troubleshooting tips.\n",
DMS(mem_limit << 20), mem_limit - 1, doc_path);
} else {
SAYF("\n" cLRD "[-] " cRST
"Oops, the program crashed with one of the test cases provided. There are\n"
" several possible explanations:\n\n"
" - The test case causes known crashes under normal working conditions. If\n"
" so, please remove it. The fuzzer should be seeded with interesting\n"
" inputs - but not ones that cause an outright crash.\n\n"
#ifdef __APPLE__
" - On MacOS X, the semantics of fork() syscalls are non-standard and may\n"
" break afl-fuzz performance optimizations when running platform-specific\n"
" binaries. To fix this, set AFL_NO_FORKSRV=1 in the environment.\n\n"
#endif /* __APPLE__ */
" - Least likely, there is a horrible bug in the fuzzer. If other options\n"
" fail, poke <lcamtuf@coredump.cx> for troubleshooting tips.\n");
}
FATAL("Test case '%s' results in a crash", fn);
case FAULT_ERROR:
FATAL("Unable to execute target application ('%s')", argv[0]);
case FAULT_NOINST:
FATAL("No instrumentation detected");
case FAULT_NOBITS:
useless_at_start++;
if (!in_bitmap && !shuffle_queue)
WARNF("No new instrumentation output, test case may be useless.");
break;
}
if (q->var_behavior) WARNF("Instrumentation output varies across runs.");
q = q->next;
}
它遍历之前生成的input_queue（链表），先取出q->fname 读取该文件q->len到use_mem中，然后关闭fd。
接着它调用了calibrate_case函数对用例进行校准，返回res。这个函数在perform_dry_run, save_if_interesting，fuzz_one，pilot_fuzzing,core_fuzzing函数中均有调用。
根据res的返回值来进行错误判断，有如下几种类型
enum {
/* 00 */ FAULT_NONE,
/* 01 */ FAULT_TMOUT,
/* 02 */ FAULT_CRASH,
/* 03 */ FAULT_ERROR,
/* 04 */ FAULT_NOINST,
/* 05 */ FAULT_NOBITS };
然后打印错误信息。
2.4 fuzz_one()
大概1600行，这里就不贴所有代码了。主要是对testcase进行fuzz，如果成功
就返回0，否则1。
1）根据是否有pending_favored和queue_cur的情况按照概率进行跳过；有pending_favored, 对于fuzz过的或者non-favored的以概率99%跳过；无pending_favored，95%跳过fuzzed&non-favored，75%跳过not fuzzed&non-favored，不跳过favored。
原作者也在相应处进行了注释：如果我们有一个标记为favored且没有被fuzz过的新用例进入队列，可能会以牺牲在已经执行过或者没有favored标记的执行花销为代价，跳转去执行这些用例。即使没有，仍然会有可能跳过已执行或没有favored标记的用例，虽然概率会低一些（已执行跳过的概率较无标记跳过的概率更高）
if (pending_favored) {
/* 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) &&
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) {
if (UR(100) < SKIP_NFAV_NEW_PROB) return 1;
} else {
if (UR(100) < SKIP_NFAV_OLD_PROB) return 1;
}
}
2）假如当前项有校准错误，并且校准错误次数小于CAL_CHANCES(3)次，那么就用calibrate_case进行测试。
if (queue_cur->cal_failed) {
u8 res = FAULT_TMOUT;
if (queue_cur->cal_failed < CAL_CHANCES) {
/* Reset exec_cksum to tell calibrate_case to re-execute the testcase
avoiding the usage of an invalid trace_bits.
For more info: https://github.com/AFLplusplus/AFLplusplus/pull/425 */
queue_cur->exec_cksum = 0; /*重置exc_cksum，告诉calibrate_case去重新执行这个用例，避免trace_bits的无效使用*/
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;
}
}
3）如果测试用例没有修剪过，那么调用函数trim_case对测试用例进行修剪。
修剪完毕之后，使用calculate_score对每个测试用例进行打分。
if (!dumb_mode && !queue_cur->trim_done) {
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;
}
memcpy(out_buf, in_buf, len);
orig_perf = perf_score = calculate_score(queue_cur);
4）如果该queue已经完成deterministic阶段或给定了-d等（参考代码中的注释），则直接跳到havoc阶段
/* 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)
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)
goto havoc_stage;
doing_det = 1;
5）deterministic阶段变异4个stage，变异过程中会多次调用函数common_fuzz_stuff函数，保存interesting的种子，具体有以下4种确定性变异：
（1）bitflip，按位翻转，1变为0，0变为1
（2）arithmetic，整数加/减算术运算
（3）interest，把一些特殊内容替换到原文件中
（4）dictionary，把自动生成或用户提供的token替换/插入到原文件中
具体变异策略在第3节详细叙述。
这四个stage完成没有在中间跳到havoc_stage或者abandon_entry，在.state/中这样标记
/* If we made this to here without jumping to havoc_stage or abandon_entry,
we're properly done with deterministic steps and can mark it as such
in the .state/ directory. */
if (!queue_cur->passed_det) mark_as_det_done(queue_cur);
5）RANDOM HAVOC和SPLICING，这是两种非确定性变异。对于dumb mode的主fuzzer来说，是直接跳过上述四种变异策略，直接从这个开始的。
random havoc即随机破坏，这一破坏具体是指在原文件上生成各种随机的变异。由于后面的splicing也涉及到了这种方法，所以在一开头进行了一个判断。
Splicing可以理解为拼接。在完整执行一轮后没有得到findings后引发，它将当前的input文件（seed）与随机选择的另一个input（seed），在某个偏移位置将二者拼接在一起，然后基于havoc对其进行变异。
这两种具体变异策略也将在第3节中讲解
6）然后这个testcase就算完成了
3 变异策略
这一章直接参考了
https://blog.csdn.net/Chen_zju/article/details/80791268
的内容
3.1 确定性变异策略
确定性变异策略一共有四种，分别是bitflip、arithmetic、interest、dictionary；
3.1.1 bitflip
基本原理：bitflip，按位翻转，1变为0，0变为1。
拿到一个原始文件，打头阵的就是bitflip，而且还会根据翻转量/步长进行多种不同的翻转，按照顺序依次为：
- bitflip 1/1，每次翻转1个bit，按照每1个bit的步长从头开始
- bitflip 2/1，每次翻转相邻的2个bit，按照每1个bit的步长从头开始
- bitflip 4/1，每次翻转相邻的4个bit，按照每1个bit的步长从头开始
- bitflip 8/8，每次翻转相邻的8个bit，按照每8个bit的步长从头开始，即依次对每个byte做翻转
- bitflip 16/8，每次翻转相邻的16个bit，按照每8个bit的步长从头开始，即依次对每个word做翻转
- bitflip 32/8，每次翻转相邻的32个bit，按照每8个bit的步长从头开始，即依次对每个dword做翻转
作为精妙构思的fuzzer，AFL不会放过每一个获取文件信息的机会。这一点在bitflip过程中就体现的淋漓尽致。具体地，在上述过程中，AFL巧妙地嵌入了一些对文件格式的启发式判断。包括自动检测token和生成effector map。
自动检测token
在进行bitflip 1/1变异时，对于每个byte的最低位(least significant bit)翻转还进行了额外的处理：如果连续多个bytes的最低位被翻转后，程序的执行路径都未变化，而且与原始执行路径不一致(检测程序执行路径的方式可见上篇文章中“分支信息的分析”一节)，那么就把这一段连续的bytes判断是一条token。
例如，PNG文件中用IHDR作为起始块的标识，那么就会存在类似于以下的内容：
........IHDR........
当翻转到字符I的最高位时，因为IHDR被破坏，此时程序的执行路径肯定与处理正常文件的路径是不同的；随后，在翻转接下来3个字符的最高位时，IHDR标识同样被破坏，程序应该会采取同样的执行路径。由此，AFL就判断得到一个可能的token：IHDR，并将其记录下来为后面的变异提供备选。
AFL采取的这种方式是非常巧妙的：就本质而言，这实际上是对每个byte进行修改并检查执行路径；但集成到bitflip后，就不需要再浪费额外的执行资源了。此外，为了控制这样自动生成的token的大小和数量，AFL还在config.h中通过宏定义了限制：
/* Length limits for auto-detected dictionary tokens: */
#define MIN_AUTO_EXTRA 3 #define MAX_AUTO_EXTRA 32
/* Maximum number of auto-extracted dictionary tokens to actually use in fuzzing (first value), and to keep in memory as candidates. The latter should be much higher than the former. */
#define USE_AUTO_EXTRAS 10
#define MAX_AUTO_EXTRAS (USE_AUTO_EXTRAS * 10)
对于一些文件来说，我们已知其格式中出现的token长度不会超过4，那么我们就可以修改MAX_AUTO_EXTRA为4并重新编译AFL，以排除一些明显不会是token的情况。遗憾的是，这些设置是通过宏定义来实现，所以不能做到运行时指定，每次修改后必须重新编译AFL。
生成effector map
在进行bitflip 8/8变异时，AFL还生成了一个非常重要的信息：effector map。这个effector map几乎贯穿了整个deterministic fuzzing的始终。
具体地，在对每个byte进行翻转时，如果其造成执行路径与原始路径不一致，就将该byte在effector map中标记为1，即“有效”的，否则标记为0，即“无效”的。
这样做的逻辑是：如果一个byte完全翻转，都无法带来执行路径的变化，那么这个byte很有可能是属于”data”，而非”metadata”（例如size, flag等），对整个fuzzing的意义不大。所以，在随后的一些变异中，会参考effector map，跳过那些“无效”的byte，从而节省了执行资源。
由此，通过极小的开销（没有增加额外的执行次数），AFL又一次对文件格式进行了启发式的判断。看到这里，不得不叹服于AFL实现上的精妙。
不过，在某些情况下并不会检测有效字符。第一种情况就是dumb mode或者从fuzzer，此时文件所有的字符都有可能被变异。第二、第三种情况与文件本身有关：
/* Minimum input file length at which the effector logic kicks in: */
#define EFF_MIN_LEN 128
/* Maximum effector density past which everything is just fuzzed unconditionally (%): */
#define EFF_MAX_PERC 90
即默认情况下，如果文件小于128 bytes，那么所有字符都是“有效”的；同样地，如果AFL发现一个文件有超过90%的bytes都是“有效”的，那么也不差那10%了，大笔一挥，干脆把所有字符都划归为“有效”。
3.1.2 arithmetic
在bitflip变异全部进行完成后，便进入下一个阶段：arithmetic。与bitflip类似的是，arithmetic根据目标大小的不同，也分为了多个子阶段：
- arith 8/8，每次对8个bit进行加减运算，按照每8个bit的步长从头开始，即对文件的每个byte进行整数加减变异
- arith 16/8，每次对16个bit进行加减运算，按照每8个bit的步长从头开始，即对文件的每个word进行整数加减变异
- arith 32/8，每次对32个bit进行加减运算，按照每8个bit的步长从头开始，即对文件的每个dword进行整数加减变异
加减变异的上限，在config.h中的宏ARITH_MAX定义，默认为35。所以，对目标整数会进行+1, +2, …, +35, -1, -2, …, -35的变异。特别地，由于整数存在大端序和小端序两种表示方式，AFL会贴心地对这两种整数表示方式都进行变异。
此外，AFL还会智能地跳过某些arithmetic变异。第一种情况就是前面提到的effector map：如果一个整数的所有bytes都被判断为“无效”，那么就跳过对整数的变异。第二种情况是之前bitflip已经生成过的变异：如果加/减某个数后，其效果与之前的某种bitflip相同，那么这次变异肯定在上一个阶段已经执行过了，此次便不会再执行。
1.2.7 interest
下一个阶段是interest，具体可分为：
- interest 8/8，每次对8个bit进替换，按照每8个bit的步长从头开始，即对文件的每个byte进行替换
- interest 16/8，每次对16个bit进替换，按照每8个bit的步长从头开始，即对文件的每个word进行替换
- interest 32/8，每次对32个bit进替换，按照每8个bit的步长从头开始，即对文件的每个dword进行替换
而用于替换的”interesting values”，是AFL预设的一些比较特殊的数：
static s8 interesting_8[] = { INTERESTING_8 };
static s16 interesting_16[] = { INTERESTING_8, INTERESTING_16 };
static s32 interesting_32[] = { INTERESTING_8, INTERESTING_16, INTERESTING_32 };
这些数的定义在config.h文件中：
/* List of interesting values to use in fuzzing. */
#define INTERESTING_8 \ -128, /* Overflow signed 8-bit when decremented */ \ -1, /* */ \ 0, /* */ \ 1, /* */ \ 16, /* One-off with common buffer size */ \ 32, /* One-off with common buffer size */ \ 64, /* One-off with common buffer size */ \ 100, /* One-off with common buffer size */ \ 127 /* Overflow signed 8-bit when incremented */
#define INTERESTING_16 \ -32768, /* Overflow signed 16-bit when decremented */ \ -129, /* Overflow signed 8-bit */ \ 128, /* Overflow signed 8-bit */ \ 255, /* Overflow unsig 8-bit when incremented */ \ 256, /* Overflow unsig 8-bit */ \ 512, /* One-off with common buffer size */ \ 1000, /* One-off with common buffer size */ \ 1024, /* One-off with common buffer size */ \ 4096, /* One-off with common buffer size */ \ 32767 /* Overflow signed 16-bit when incremented */
#define INTERESTING_32 \ -2147483648LL, /* Overflow signed 32-bit when decremented */ \ -100663046, /* Large negative number (endian-agnostic) */ \ -32769, /* Overflow signed 16-bit */ \ 32768, /* Overflow signed 16-bit */ \ 65535, /* Overflow unsig 16-bit when incremented */ \ 65536, /* Overflow unsig 16 bit */ \ 100663045, /* Large positive number (endian-agnostic) */ \ 2147483647 /* Overflow signed 32-bit when incremented */
可以看到，用于替换的基本都是可能会造成溢出的数。
与之前类似，effector map仍然会用于判断是否需要变异；此外，如果某个interesting value，是可以通过bitflip或者arithmetic变异达到，那么这样的重复性变异也是会跳过的。
3.1.3 dictionary
进入到这个阶段，就接近deterministic fuzzing的尾声了。具体有以下子阶段：
- user extras (over)，从头开始，将用户提供的tokens依次替换到原文件中
- user extras (insert)，从头开始，将用户提供的tokens依次插入到原文件中
- auto extras (over)，从头开始，将自动检测的tokens依次替换到原文件中
其中，用户提供的tokens，是在词典文件中设置并通过-x选项指定的，如果没有则跳过相应的子阶段。
1）user extras (over)
对于用户提供的tokens，AFL先按照长度从小到大进行排序。这样做的好处是，只要按照顺序使用排序后的tokens，那么后面的token不会比之前的短，从而每次覆盖替换后不需要再恢复到原状。
随后，AFL会检查tokens的数量，如果数量大于预设的MAX_DET_EXTRAS（默认值为200），那么对每个token会根据概率来决定是否进行替换：
for (j = 0; j < extras_cnt; j++) {
/* Skip extras probabilistically if extras_cnt > MAX_DET_EXTRAS. Also skip them if there's no room to insert the payload, if the token is redundant, or if its entire span has no bytes set in the effector map. */
if ((extras_cnt > MAX_DET_EXTRAS && UR(extras_cnt) >= MAX_DET_EXTRAS) ||
extras[j].len > len - i ||
!memcmp(extras[j].data, out_buf + i, extras[j].len) ||
!memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, extras[j].len))) {
stage_max--;
continue;
}
这里的UR(extras_cnt)是运行时生成的一个0到extras_cnt之间的随机数。所以，如果用户词典中一共有400个tokens，那么每个token就有200/400=50%的概率执行替换变异。我们可以修改MAX_DET_EXTRAS的大小来调整这一概率。
由上述代码也可以看到，effector map在这里同样被使用了：如果要替换的目标bytes全部是“无效”的，那么就跳过这一段，对下一段目标执行替换。
2）user extras (insert)
这一子阶段是对用户提供的tokens执行插入变异。不过与上一个子阶段不同的是，此时并没有对tokens数量的限制，所以全部tokens都会从原文件的第1个byte开始，依次向后插入；此外，由于原文件并未发生替换，所以effector map不会被使用。
这一子阶段最特别的地方，就是变异不能简单地恢复。之前每次变异完，在变异位置处简单取逆即可，例如bitflip后，再进行一次同样的bitflip就恢复为原文件。正因为如此，之前的变异总体运算量并不大。
但是，对于插入这种变异方式，恢复起来则复杂的多，所以AFL采取的方式是：将原文件分割为插入前和插入后的部分，再加上插入的内容，将这3部分依次复制到目标缓冲区中（当然这里还有一些小的优化，具体可阅读代码）。而对每个token的每处插入，都需要进行上述过程。所以，如果用户提供了大量tokens，或者原文件很大，那么这一阶段的运算量就会非常的多。直观表现上，就是AFL的执行状态栏中，”user extras (insert)”的总执行量很大，执行时间很长。如果出现了这种情况，那么就可以考虑适当删减一些tokens。
3）auto extras (over)
这一项与”user extras (over)”很类似，区别在于，这里的tokens是最开始bitflip阶段自动生成的。另外，自动生成的tokens总量会由USE_AUTO_EXTRAS限制（默认为10）。
3.2 非确定性变异
因为这类变异较多是随机生成的，所以为非确定性变异，具体为havoc和splice
3.2.1 havoc
对于非dumb mode的主fuzzer来说，完成了上述deterministic fuzzing后，便进入了充满随机性的这一阶段；对于dumb mode或者从fuzzer来说，则是直接从这一阶段开始。
havoc，顾名思义，是充满了各种随机生成的变异，是对原文件的“大破坏”。具体来说，havoc包含了对原文件的多轮变异，每一轮都是将多种方式组合（stacked）而成：
随机选取某个bit进行翻转
随机选取某个byte，将其设置为随机的interesting value
随机选取某个word，并随机选取大、小端序，将其设置为随机的interesting value
随机选取某个dword，并随机选取大、小端序，将其设置为随机的interesting value
随机选取某个byte，对其减去一个随机数
随机选取某个byte，对其加上一个随机数
随机选取某个word，并随机选取大、小端序，对其减去一个随机数
随机选取某个word，并随机选取大、小端序，对其加上一个随机数
随机选取某个dword，并随机选取大、小端序，对其减去一个随机数
随机选取某个dword，并随机选取大、小端序，对其加上一个随机数
随机选取某个byte，将其设置为随机数
随机删除一段bytes
随机选取一个位置，插入一段随机长度的内容，其中75%的概率是插入原文中随机位置的内容，25%的概率是插入一段随机选取的数
随机选取一个位置，替换为一段随机长度的内容，其中75%的概率是替换成原文中随机位置的内容，25%的概率是替换成一段随机选取的数
随机选取一个位置，用随机选取的token（用户提供的或自动生成的）替换
随机选取一个位置，用随机选取的token（用户提供的或自动生成的）插入
怎么样，看完上面这么多的“随机”，有没有觉得晕？还没完，AFL会生成一个随机数，作为变异组合的数量，并根据这个数量，每次从上面那些方式中随机选取一个（可以参考高中数学的有放回摸球），依次作用到文件上。如此这般丧心病狂的变异，原文件就大概率面目全非了，而这么多的随机性，也就成了fuzzing过程中的不可控因素，即所谓的“看天吃饭”了。
3.2.2 splice
历经了如此多的考验，文件的变异也进入到了最后的阶段：splice。如其意思所说，splice是将两个seed文件拼接得到新的文件，并对这个新文件继续执行havoc变异。
具体地，AFL在seed文件队列中随机选取一个，与当前的seed文件做对比。如果两者差别不大，就再重新随机选一个；如果两者相差比较明显，那么就随机选取一个位置，将两者都分割为头部和尾部。最后，将当前文件的头部与随机文件的尾部拼接起来，就得到了新的文件。在这里，AFL还会过滤掉拼接文件未发生变化的情况。
cycle
于是乎，一个seed文件，在上述的全部变异都执行完成后，就…抱歉，还没结束。
上面的变异完成后，AFL会对文件队列的下一个进行变异处理。当队列中的全部文件都变异测试后，就完成了一个”cycle”，这个就是AFL状态栏右上角的”cycles done”。而正如cycle的意思所说，整个队列又会从第一个文件开始，再次进行变异，不过与第一次变异不同的是，这一次就不需要再进行deterministic fuzzing了。
当然，如果用户不停止AFL，那么seed文件将会一遍遍的变异下去。
