fanson's Blog

AFL漫谈

最近一直在研究fuzz 神器-AFL，但网上的相关资料相对甚少，所以就抽空简略的撸了下源码来了解相对细节的实现的过程以及其中的巧妙之处，所以想写些东西来记录下。

一，AFL 简介

1
AFL(American Fuzzy Lop)是一款开源的fuzzing工具，并且其中巧妙的采用了一个极其简单但是绝对可靠的，插桩代码导向的遗传算法来提升fuzz效率，而他的巧妙之点不止只体现在这一点上。最近我对其代码进行了简要的阅读，大致总结了一些AFL的实现细节以及其中的遗传算法的原理，在这来记录整理。

二，AFL的整个算法逻辑

参考的官网的相关技术白皮书，抛出链接http://lcamtuf.coredump.cx/afl/technical_details.txt

1
2
3
4
5
6
7
8
9
10
11
Simplifying a bit, the overall algorithm can be summed up as:
  1) Load user-supplied initial test cases into the queue,
  2) Take next input file from the queue,
  3) Attempt to trim the test case to the smallest size that doesn't alter
     the measured behavior of the program,
  4) Repeatedly mutate the file using a balanced and well-researched variety
     of traditional fuzzing strategies,
  5) If any of the generated mutations resulted in a new state transition
     recorded by the instrumentation, add mutated output as a new entry in the
     queue.
  6) Go to 2.

实现的具体流程图如下：

三，AFL的整体框架

AFL的fuzz具体代码实现流程

1
2
3
4
5
6
7
8
9
10
11
1. main函数先进行初始化和选项处理；
2. 执行input文件夹下的预先准备的所有testcase（perform_dry_run），生成初始化的queue和bitmap；
3. 通过cull_queue对queue进行精选，减小input的量；
4. 然后进行while(1)循环不断进行fuzz。
每次在fuzz一个queue后，就会进入while(1),并重新调用cull_queue()对队列进行精选，而在while(1)具体实现以下过程：
1. cull_queue()根据top_rated设置queue中的favored标志，对queue进行精选，选出favored；
2. 判断queue_cur是否为NULL，如果是，则表示已经完成对队列的遍历，queue_cycle++,初始化相关参数，重新开始遍历队列；
3. fuzz queue_cur对应的input文件；
4. 判断是否结束，并更新queue_cur和current_entry；
当队列中的所有文件都经过变异测试了，则完成一次”cycle done”; 
整个队列又会从第一个文件开始，再次继续进行变异，不过与第一次变异不同的是，因为没有随机性，这一次变异就不需要再进行deterministic fuzzing了。而至于什么是deterministic fuzzing，我们在下面的fuzz策略中会作介绍；

AFL的fuzz策略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
   总的来讲，AFL维护了一个队列(queue)，每次从这个队列中取出一个文件，对其进行大量变异，并检查运行后是否会引起目标崩溃、发现新路径等结果。变异的主要类型如下：
1.bitflip，按位翻转，1变为0，0变为1
2.arithmetic，整数加/减算术运算
3.interest，把一些特殊内容替换到原文件中
4.dictionary，把自动生成或用户提供的token替换/插入到原文件中
5.havoc，中文意思是“大破坏”，此阶段会对原文件进行大量变异，
6.splice，中文意思是“绞接”，此阶段会将两个文件拼接起来得到一个新的文件
其中，前四项bitflip, arithmetic, interest, dictionary由于其变异方式没有随机性，所以也称为deterministic fuzzing；而havoc和splice则存在随机性，是所有状况的fuzzer（是否dumb mode、主从fuzzer）都会执行的变异。

bitflip变异：
拿到一个原始文件，首先的变异类型就是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做翻转
effector map的生成：完成bitflip 8/8的同时，还生成了effector map，该作用是对byte进行标记，在对每个byte进行翻转变异时，其新的执行路径与原来的路径不一致时，就对该byte标记为1，表示即为有效的，否则标记为0；这样做的优点是如果一个byte完全翻转，都无法带来执行路径的变化，那么这个byte很有可能是属于”data”，而非”metadata”（例如size, flag等），对整个fuzzing的意义不大。所以，在随后的一些变异中，会参考effector map，跳过那些“无效”的byte，从而节省了执行资源。
bitflip 16/8，每次翻转相邻的16个bit，按照每8个bit的步长从头开始，即依次对每个word做翻转
bitflip 32/8，每次翻转相邻的32个bit，按照每8个bit的步长从头开始，即依次对每个dword做翻转

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定义，由于整数存在大端序和小端序两种表示方式，AFL会贴心地对这两种整数表示方式都进行变异。此外，AFL会智能的跳过某些arithmetic,第一种情况就是前面提到的effector map：如果一个整数的所有bytes都被判断为“无效”，那么就跳过对整数的变异。第二种情况是之前bitflip已经生成过的变异：如果加/减某个数后，其效果与之前的某种bitflip相同，那么这次变异肯定在上一个阶段已经执行过了，此次便不会再执行。

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进行替换
其中interest value的值在config.h已经设定好
#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  */
可以看到，用于替换的基本都是可能会造成溢出的数;与之前相同，effector map仍然会用于判断是否需要变异；

dictionary变异：
user extras (over)，从头开始，将用户提供的tokens依次替换到原文件中
user extras (insert)，从头开始，将用户提供的tokens依次插入到原文件中
auto extras (over)，从头开始，将自动检测的tokens依次替换到原文件中
tokens:在进行bitflip 1/1变异时，对于每个byte的最低位(least significant bit)翻转还进行了额外的处理：如果连续多个bytes的最低位被翻转后，程序的执行路径都未变化，而且与原始执行路径不一致，那么就把这一段连续的bytes判断是一条token。

havoc变异：
随机选取某个bit进行翻转
随机选取某个byte，将其设置为随机的interesting value
随机选取某个word，并随机选取大、小端序，将其设置为随机的interesting value
随机选取某个dword，并随机选取大、小端序，将其设置为随机的interesting value
随机选取某个byte，对其减去一个随机数
随机选取某个byte，对其加上一个随机数
随机选取某个word，并随机选取大、小端序，对其减去一个随机数
随机选取某个word，并随机选取大、小端序，对其加上一个随机数
随机选取某个dword，并随机选取大、小端序，对其减去一个随机数
随机选取某个dword，并随机选取大、小端序，对其加上一个随机数
随机选取某个byte，将其设置为随机数
随机删除一段bytes
随机选取一个位置，插入一段随机长度的内容，其中75%的概率是插入原文中随机位置的内容，25%的概率是插入一段随机选取的数
随机选取一个位置，替换为一段随机长度的内容，其中75%的概率是替换成原文中随机位置的内容，25%的概率是替换成一段随机选取的数
随机选取一个位置，用随机选取的token（用户提供的或自动生成的）替换
随机选取一个位置，用随机选取的token（用户提供的或自动生成的）插入

Fuzzer dictionaries 

1
2
刚开始我们或许都有个疑惑，afl的最显眼的局限之一是如何解决的，afl的变异引擎是语法盲，并针对紧凑数据格式（即，图像，多媒体，压缩数据，正则表达式语法或shell脚本）进行了优化，但是它不太适合特别冗长，冗余并且带有语法的的语言 - 尤其包括HTML，SQL或JavaScript。
为了避免构建语法感知工具的麻烦，afl-fuzz提供了一种使用语言关键字，magic header或其他与目标数据类型相关联的特殊表示的可选字典为模糊过程提供种子的方法 - 并且使用它来重建底层语法

forkserver

1
编译 target 完成后，就可以通过 afl-fuzz 开始 fuzzing了。其大致思路是，对输入的 seed 文件不断地变化，并将这些 mutated input 喂给 target 执行，检查是否会造成崩溃。因此，fuzzing 涉及到大量的 fork 和执行 target 的过程。 为了更高效地进行上述过程，AFL 实现了一套 fork server 机制。其基本思路是：启动 target 进程后，target 会运行一个 fork server；fuzzer 并不负责 fork 子进程，而是与这个 fork server 通信，并由 fork server 来完成fork 及继续执行目标的操作。这样设计的最大好处，就是不需要调用execve()，从而节省了载入目标文件和库、解析符号地址等重复性工作。 接下来，我们来看看 fork server 的具体运行原理。

内存共享

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    作为fuzzer，AFL并不是毫无目的对输入文件无脑地随机变化（其实也支持这种方式，即dumb模式），它会对target进行插桩，以辅助mutated input的生成。具体地，插桩后的target，会记录执行过程中的分支信息；随后，fuzzer便可以根据这些信息，判断这次执行的整体流程和代码覆盖情况。 
AFL使用共享内存，来完成以上信息在fuzzer和target之间的传递。

1.fuzzer在启动时，会执行setup_shm()方法进行配置。其首先调用shemget()分配一块共享内存，大小MAP_SIZE为64K:
shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);
2.分配成功后，该共享内存的标志符会被设置到环境变量中，从而之后fork()得到的子进程可以通过该环境变量，得到这块共享内存的标志符：
shm_str = alloc_printf("%d", shm_id);
if (!dumb_mode) setenv(SHM_ENV_VAR, shm_str, 1);
并且，fuzzer本身，会使用变量trace_bits来保存共享内存的地址：
trace_bits = shmat(shm_id, NULL, 0);
3.在每次target执行之前，fuzzer首先将该共享内容清零：
memset(trace_bits, 0, MAP_SIZE); 
4.target获取并使用这块共享内存的。相关代码同样也在上面提到的方法__afl_maybe_log()中。首先，会检查是否已经将共享内存映射完成：__afl_area_ptr中保存的就是共享内存映射到target的内存空间中的地址，如果其不是NULL，便保存在ebx中继续执行；否则进一步跳转到__afl_setup。__afl_setup处会做一些错误检查，然后获取环境变量AFL_SHM_ENV的内容并将其转为整型。查看其定义便可知，这里获取到的，便是之前fuzzer保存的共享内存的标志符。
5.最后，通过调用shmat()，target将这块共享内存也映射到了自己的内存空间中，并将其地址保存在__afl_area_ptr及edx中。由此，便完成了fuzzer与target之间共享内存的设置。

注记：如果使用了fork server模式，那么上述获取共享内存的操作，是在fork server中进行；随后fork出来的子进程，只需直接使用这个共享内存即可。

四，使用afl-dyninst fuzz无源码的二进制程序

通常来讲，afl-fuzz需要对待fuzz程序重编译，重而对其进行插桩,这就要求拥有待fuzz程序的完整源代码。而afl-dyninst提供了一种静态无源码插桩的手段使得可以对无源码二进制程序插桩。

下载编译首先需要安装以下软件:sudo apt-get

下载&&编译

1
sudo apt-get install libelf-dev libelf1 libiberty-dev libboost-all-dev

afl-dyninst是基于dyninst的,所以需要下载&&编译&&安装dyninst:

1
2
3
4
5
6
7
git clone https://github.com/dyninst/dyninst.git
cd dyninst
mkdir build
cd build
cmake -DBOOST_LIBRARYDIR=/usr/lib/x86_64-linux-gnu
make
sudo make install

下载&&编译afl-dyninst

1
2
3
4
5
6
7
git clone https://github.com/talos-vulndev/afl-dyninst.git
cd afl-dyninst
make
sudo cp afl-dyninst /usr/bin/
sudo cp libAflDyninst.so /usr/local/lib/
echo "/usr/local/lib" > /etc/ld.so.conf.d/dyninst.conf && ldconfig
echo "export DYNINSTAPI_RT_LIB=/usr/local/lib/libdyninstAPI_RT.so" >> ~/.bashrc

使用

1
2
3
4
5
6
7
8
9
10
11
12
13
Usage: ./afl-dyninst -i <binary> -o <binary> -l <library> -e <address> -s <number>
             -i: Input binary 
             -o: Output binary
             -l: Library to instrument (repeat for more than one)
             -e: Entry point address to patch (required for stripped binaries)
             -r: Runtime library to instrument (path to, repeat for more than one)
             -s: Number of basic blocks to skip
             -v: Verbose output
example:
afl-dyninst -i testbin -o testbin_ins
to fuzz:
export AFL_SKIP_BIN_CHECK=1
afl-fuzz -i in -o out testbin_ins

五，AFL的优化改进方向

​ 这几天通过对源码的阅读学习，领略了该神级工具的设计巧妙与功能强大之处，当然在实现的过程中，也存在些许不足，会想尝试能不能自己去做一个优化或者改进，让他能具有一定的针对性或者更强的fuzz能力，参考了各位大牛的paper，结合afl的不足，总结下优化改进的一些点

1
2
3
4
5
6
1.coverage的碰撞问题
   AFL要用到一个64KB bitmap来保存Coverage的信息，在这个过程，它是通过给边算出来hash值，用hash代表边来更新bitmap,而在hash算法中则存在碰撞问题，它而影响这个Fuzzer的判断，这个Fuzzer会根据bitmap来判断当前这个种子是不是好的优秀的种子，判断这个种子是不是走了新的边，如果碰撞了，它是看不出来这是新的边。如果新的边出现了，它的哈希值与前哈希值是一样的，那么Fuzzer认为这个边是测过的边，认为这个种子没用，进而扔掉了实际很好的种子。甚至会漏掉一些crash.
2.变异阶段的随机性问题
    变异的类型可分为bitflip，arithmetic，interest，dictionary，havoc，splice六种，而在这六种类型中后面俩种havoc和splice都是没有针对性的，存在一定的随机性，而这些部分也就成了不折不扣的“看天吃饭”，所以，可以在变异策略上优化减少这种随机性，尽量去变异那些更重要的字符。
3.改进种子的选择策略
    可以改进优先选择对Coverage有贡献的种子

六，参考文献

【1】https://rk700.github.io/2018/01/04/afl-mutations/

【2】http://chao.100871.net/papers/oakland18.pdf

【3】https://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html

【4】https://blog.csdn.net/Chen_zju/article/details/80791268

fuzz tools