https://abiondo.me/2018/09/21/improving-afl-qemu-mode/
作为我最喜欢的fuzzer工具，AFL健全有效，由覆盖率引导，还支持使用qemu模式来fuzz闭源二进制程序，然而qemu模式所带来的就是明显的性能花费。所以，是否可以改进一下呢？
2018-9-22更新：感谢@domenuk建议在parent里缓存chains，博客相应更新了，我们现在可以做到3-4倍的提速效果了。
在开始之前，我们首先需要来看看QEMU的一些基础。QEMU的目标是能够在host（宿主机）上模拟target（目标机），而这两个机器的架构可能完全不同。最简单的实现方式就是针对目标机的指令集写一个解释器，然后在宿主机上编译，但是显然这样的方式会非常缓慢。一个更聪明一点的方式则是使用jit编译：把目标机器的代码翻译为宿主机器的指令，然后使用原生的速度去执行，这也是QEMU所采用的方法。
直接从宿主机翻译到目标机的方法扩展起来效果并不好，因为这样意味着对于所有的(目标机，宿主机)元组都要实现一个翻译器，所以，与计算机科学的任何问题一样，我们可以通过引入一个间接层来解决问题，也就是：Tiny Code Generator（小代码生成器），简称TCG。一个TCG前端将目标机原生指令lift（提升）到架构无关的中间表示（IR），而一个TCG后端则将IR降级到原生宿主机指令。想要加一个新的目标架构？只需要写一个前端就可以了。新的宿主机架构？加一个后端，非常简单。翻译是在基本块等级模拟的时候同时进行的，而因为翻译的过程代价较大，翻译块(TB)会被存储在TCG缓存里，这样如果再次执行到，就可以执行使用。
当你在进行这种翻译的时候，你需要考虑到翻译后的代码可能并不一定和原来的代码内存布局相同，这样的话，你就需要修理好对内存地址的引用，比如我们来考虑一下终结一个块的控制流指令：如果是一个直接跳转，那么其跳转地址是已知的，所以我们可以马上修正好，把跳转翻译成跳转到后继的原生跳转，这样就完全没有运行时的额外代价。QEMU将这种情况称为块chain(block chaining)。而如果是间接跳转，我们就无法在翻译的时候确定跳转目标（即使我们尝试去做分析，这也不是一个可以保证出结果的情况），所以我们跳转到QEMU核心的一个回调，这个回调函数就会去翻译还没有翻译的目标块，然后转移控制，之后继续模拟，显然这种情况就会有性能消耗。
AFL，作为一个由覆盖率引导的fuzzer，需要执行轨迹插桩来获取程序控制流的信息，我在这里不会去解释太原始的一些细节，可以从AFL技术白皮书里去看，如果你想知道具体里面都是怎么工作的话。如果你有程序源码，你可以用AFL的插桩编译器重新编译一下，这个编译器会在每一个基本块之前加入一小段代码。如果你只有二进制文件，你就可以用AFL的QEMU模式：二进制会在一个被打过补丁的QEMU里执行，然后收集覆盖信息，并传递给AFL。
AFL的QEMU补丁工作如下：在qemu_mode/patches/afl-qemu-cpu-inl.h文件里包含了实际的实现，包含了两个主要部分，一个是forkserver，另外一个是执行轨迹的插桩。forkserver是AFL用来优化初始化额外消耗的一种方法，因为在每次程序开始执行前forkserver会先启动，所以子进程都只有空的TCG缓存，这样的话，AFL采用了一种机制，子进程在有新的翻译块的时候通知父进程，这样父进程就可以在他自己的缓存里边翻译这个块，然后为未来的子进程做准备。
插桩在QEMU核心的accel/tcg/cpu-exec.c进行了hook，这个patch主要是在cpu_tb_exec里插入了一段，cpu_tb_exec在每次TB被模拟器执行的时候都会被调用。patch调用了afl_maybe_log，该函数会检查块是否在trace边界以内，如果在，就会将控制流记录下来，然后传递到AFL的边图(edge map)里。
然而这样有个问题：跳转到chain的块不会调用到模拟器里，因为这样的情况不会经过整个cpu_tb_exec，AFL的解决办法是，直接取消chain。
/* Workaround for a QEMU stability glitch. */
setenv("QEMU_LOG", "nochain", 1);的确，通过cpu_tb_exec的插桩，如果你不取消chain就会导致比较低的稳定性，但是那是由于你完全没有追踪直接跳转造成的，所以其实我不会把它称作一种“瑕疵“，不管怎么说，取消chain都是一个非常大的性能影响，所以我们能够想个办法解决这个问题么？
我的想法是通过把插桩直接移入到编译后的代码中，通过在每一个TB前都注入一段TCG IR来实现。这样的话，插桩就直接变成了模拟的程序的一部分，所以我们不需要让模拟器每次都跳回去，而且也可以重新打开chain。
这里是原来的qemu_mode/patches/afl-qemu-cpu-inl.h里的afl_maybe_log：
/* The equivalent of the tuple logging routine from afl-as.h. */
static inline void afl_maybe_log(abi_ulong cur_loc) {
static __thread abi_ulong prev_loc;
/* Optimize for cur_loc > afl_end_code, which is the most likely case on
Linux systems. */
if (cur_loc > afl_end_code || cur_loc < afl_start_code || !afl_area_ptr)
return;
/* Looks like QEMU always maps to fixed locations, so ASAN is not a
concern. Phew. But instruction addresses may be aligned. Let's mangle
the value to get something quasi-uniform. */
cur_loc = (cur_loc >> 4) ^ (cur_loc << 8);
cur_loc &= MAP_SIZE - 1;
/* Implement probabilistic instrumentation by looking at scrambled block
address. This keeps the instrumented locations stable across runs. */
if (cur_loc >= afl_inst_rms) return;
afl_area_ptr[cur_loc ^ prev_loc]++;
prev_loc = cur_loc >> 1;
}所有依赖cur_loc的都可以在翻译时完成，因为cur_loc是当前块的地址，所以简单来说我们只需要对最后两行去生成TCG IR，所以我写了这么一段：
tatic void afl_gen_trace(target_ulong cur_loc)
{
static __thread target_ulong prev_loc;
TCGv index, count, new_prev_loc;
TCGv_ptr prev_loc_ptr, count_ptr;
/* 针对cur_loc > afl_end_code 进行优化，这种情况也是linux系统上的大多数情况 */
/* Optimize for cur_loc > afl_end_code, which is the most likely case on
Linux systems. */
if (cur_loc > afl_end_code || cur_loc < afl_start_code || !afl_area_ptr)
return;
/* 好像QEMU总是会映射到固定位置，所以ASAN不太需要去注意，还好。但是指令地址必须要对齐，那我们把值混一下来得到点拟均匀的东西。 */
/* Looks like QEMU always maps to fixed locations, so ASAN is not a
concern. Phew. But instruction addresses may be aligned. Let's mangle
the value to get something quasi-uniform. */
cur_loc = (cur_loc >> 4) ^ (cur_loc << 8);
cur_loc &= MAP_SIZE - 1;
/* 通过去查看扰乱的块地址来实现概率插桩，这样使得每次运行插桩位置稳定 */
/* Implement probabilistic instrumentation by looking at scrambled block
address. This keeps the instrumented locations stable across runs. */
if (cur_loc >= afl_inst_rms) return;
/* index = prev_loc ^ cur_loc */
prev_loc_ptr = tcg_const_ptr(&prev_loc);
index = tcg_temp_new();
tcg_gen_ld_tl(index, prev_loc_ptr, 0);
tcg_gen_xori_tl(index, index, cur_loc);
/* afl_area_ptr[index]++ */
count_ptr = tcg_const_ptr(afl_area_ptr);
tcg_gen_add_ptr(count_ptr, count_ptr, TCGV_NAT_TO_PTR(index));
count = tcg_temp_new();
tcg_gen_ld8u_tl(count, count_ptr, 0);
tcg_gen_addi_tl(count, count, 1);
tcg_gen_st8_tl(count, count_ptr, 0);
/* prev_loc = cur_loc >> 1 */
new_prev_loc = tcg_const_tl(cur_loc >> 1);
tcg_gen_st_tl(new_prev_loc, prev_loc_ptr, 0);
}在每次翻译一个块之前都需要调用这一段，TB IR的生成在tb_gen_code(accel/tcg/translate-all.c)里进行的，在里边调用了目标机前端的gen_intermediate_code函数：
tcg_ctx.cpu = ENV_GET_CPU(env);
gen_intermediate_code(cpu, tb);
tcg_ctx.cpu = NULL;所以我们hook一下，来在每一个块之前插入我们的IR：
tcg_ctx.cpu = ENV_GET_CPU(env);
afl_gen_trace(pc);
gen_intermediate_code(cpu, tb);
tcg_ctx.cpu = NULL;现在我们就可以从AFL(afl-analyze.c, afl-fuzz.c, afl-showmap.c, afl-tmin.c)里去掉setenv("QEMU_LOG", "nochain", 1)之后测试了。
如同我之前提到的，AFL使用了一个forkserver策略来减少初始化的额外消耗，基本上说，forkserver在初始化之后启动，然后根据AFL的请求来fork出子进程。每一个子进程都执行一个test case，这样的方法是可以消除QEMU初始化的消耗的，但是会导致严重的TCG 缓存颠簸(thrashing)，因为父进程在初始化之后的缓存是空的，所以会导致子进程都以空缓存状态开始启动。为了避免这个情况，AFL的patch在父进程和子进程之间建立了一个管道，子进程使用这个管道来在每一次新的基本块翻译的时候提醒父进程，父进程之后就在自己的缓存里翻译这个块，这样未来的子进程就可以使用这个缓存了（这样的话，每个块会翻译两次，我也不觉得为了避免翻译两次而采用非常复杂的序列化有什么价值）
为了做到这个，AFL patch了accel/tcg/cpu-exec.c里的tb_find，在tb_gen_code后面插入了一个afl_request_tsl的调用，来翻译这个块。afl_request_tsl函数会把需要用来标识TB的信息（地址，CS基地址，flags）发给父进程，父进程此时正在afl_wait_tsl里等待，最终afl_wait_tsl会调用tb_gen_code来在父进程的缓存中翻译一个块。
tb_find函数接受几个参数，last_tb和tb_exit，这两个参数可以分别标识前一个TB和前一个TB的最后一条指令使我们到达现在位置的的jump slot。在翻译之后，如果请求的块不是已经被处理过，tb_find就通过patch前一个块的jump slot来进行chain：
/* 看下我们是否可以patch正在调用的TB */
/* See if we can patch the calling TB. */
if (last_tb && !qemu_loglevel_mask(CPU_LOG_TB_NOCHAIN)) {
if (!have_tb_lock) {
tb_lock();
have_tb_lock = true;
}
if (!tb->invalid) {
tb_add_jump(last_tb, tb_exit, tb);
}
}然而afl_wait_tsl没有这么做，也就是说在TB间的chain不会被缓存。我实现了patch后的jump slot的缓存，基本上是通过在我们到达tb_add_jump块的时候通知父进程来实现的。为了实现这个做了一点重构，细节这里就不再说了，可以看看后面的补丁。
我没时间来进行非常详尽的测试，但是我在32和64位x86目标机上做了一下测试（在64 x86宿主机上），第一版没有chain缓存的，大概是原来速度的1.5到3倍，加上chain缓存，可以达到3到4倍的速度。路径计数和afl-showmap看起来可以确认trace是正确的，所以我还是很自信它应该是按照想象的情况工作的。
TCG插桩已经在我的AFL fork，build和运行qemu模式都和平常一样，我的fork还包含一个导致GNU libc >= 2.27时编译错误的memfd_create的patch，所以在linux上build应该很容易。如果你测试了，并且有更好的性能比较，issue，任何问题，都可以留个评论！