Setup

Paths

We need setup three paths: GOPATH, IMAGE and KERNEL.

GOPATH is the working directory for syzkaller

IMAGE is for Linux img and KERNEL is for kernel source and binary.

1
2
3
4
5
6
7
8
9
10
11

vim ~/.zshrc
add the following lines
export GOPATH=~/fuzz/syzkaller
export IMAGE=~/source/image
export KERNEL=~/source/linux

export export PATH=~/bin/gcc-8.1.0/bin:$PATH
export PATH=$GOROOT/bin:$PATH
export GCC=~/bin/gcc-8.1.0
export PATH=~/fuzz/syzkaller/bin:$PATH

Go

1
2
3
4
5
6
7

wget https://mirrors.ustc.edu.cn/golang//go1.13.3.linux-amd64.tar.gz
sha256sum go1.13.3.linux-amd64.tar.gz
tar -xvzf go1.8.1.linux-amd64.tar.gz -C ~/bin/go

add the following paths to .zshrc
export GOROOT=~/bin/go
export PATH=$GOROOT/bin:$PATH

GCC

1
2
3
4
5
6
7
8

wget https://ftp.gnu.org/gnu/gcc/gcc-8.1.0/gcc-8.1.0.tar.gz
tar -zxvf gcc-8.1.0.tar.gz
cd gcc-8.1.0
./configure --prefix=~/bin/gcc-8.1.0
make
make install
gcc --version
which gcc

syzkaller

1
2
3
4
5
6
7
8

set $GOPATH
source ~/.zshrc
go get -u -d github.com/google/syzkaller/...
cd $GOPATH/src/github.com/google/syzkaller
make

find compiled binaries in the $GOPATH/bin dir.

Linux Kernel

1
2

git clone https://mirrors.tuna.tsinghua.edu.cn/git/linux.git
cd ~/source/linux

GCC

1
2

make CC="$GCC/bin/gcc" defconfig
make CC="$GCC/bin/gcc" kvmconfig

Clang

1
2
3
4

make CC="$CLANGBIN/bin/clang" defconfig
make CC="$CLANGBIN/bin/clang" kvmconfig
make CC="$CLANGBIN/bin/clang" oldconfig
make CC="$CLANGBIN/bin/clang" -j64

Edit .config and enable:

1
2
3
4
5
6
7
8

CONFIG_KCOV=y
CONFIG_DEBUG_INFO=y
CONFIG_KASAN=y
CONFIG_KASAN_INLINE=y


CONFIG_CONFIGFS_FS=y
CONFIG_SECURITYFS=y

1
2

make CC="$GCC/bin/gcc" oldconfig
make CC="$GCC/bin/gcc" -j64

Image

Prepare the Linux image file.

1
2
3
4

cd $IMAGE
wget https://raw.githubusercontent.com/google/syzkaller/master/tools/create-image.sh -O create-image.sh
chmod +x create-image.sh\n./create-image.sh
./create-image.sh or ./create-image.sh --distribution wheezy

QEMU

1

sudo apt-get install qemu-system-x86

Test qemu

1
2
3
4
5
6
7
8
9
10
11

qemu-system-x86_64 \
  -kernel $KERNEL/arch/x86/boot/bzImage \
  -append "console=ttyS0 root=/dev/sda debug earlyprintk=serial slub_debug=QUZ"\
  -hda $IMAGE/stretch.img \
  -net user,hostfwd=tcp::10021-:22 -net nic \
  -enable-kvm \
  -nographic \
  -m 2G \
  -smp 2 \
  -pidfile vm.pid \
  2>&1 | tee vm.log

Kill qemu instance

1

kill $(cat vm.pid)

Start Fuzzing

Modify syzkaller configuration:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

{
    "target": "linux/amd64",
    "http": "127.0.0.1:56741",
    "workdir": "~/fuzz/syzkalls/workdir/",
    "kernel_obj": "~/source/linux/",
    "image": "~/source/image/stretch.img",
    "sshkey": "~/source/image/stretch.id_rsa",
    "syzkaller": "~/fuzz/syzkaller",
    "procs": 8,
    "type": "qemu",
    "vm": {
        "count": 4,
        "kernel": "~/source/linux/arch/x86/boot/bzImage",
        "cpu": 2,
        "mem": 2048
    }
}

Then start the syz-manager

1

sudo ./bin/syz-manager -config my.cfg

Set up repo

From Google

1
2
3
4

mkdir ~/bin
PATH=~/bin:$PATH
curl https://storage.googleapis.com/git-repo-downloads/repo > ~/bin/repo
chmod a+x ~/bin/repo

From Tsinghua

1
2
3
4

mkdir ~/bin
PATH=~/bin:$PATH
curl https://mirrors.tuna.tsinghua.edu.cn/git/git-repo > ~/bin/repo
chmod a+x ~/bin/repo

For version 1.25, the SHA-256 checksum for Repo is d06f33115aea44e583c8669375b35aad397176a411de3461897444d247b6c220.

For version 1.26, the SHA-256 checksum for Repo is 0cf5f52bcafb8e1d3ba0271b087312f6117b824af272bedd4ee969d52363a86b.

Config git

1
2

git config --global user.name "Your Name"
git config --global user.email "[email protected]"

Download Source Code

AOSP

Check Build Name: https://source.android.com/setup/start/build-numbers#source-code-tags-and-builds

1
2
3

repo init -u https://android.googlesource.com/platform/manifest -b android-4.0.1_r1
repo init -u https://aosp.tuna.tsinghua.edu.cn/platform/manifest -b android-9.0.0_r47
repo sync

Kernel

1
2
3

repo init -u https://android.googlesource.com/kernel/manifest -b BRANCH
repo init -u https://aosp.tuna.tsinghua.edu.cn/kernel/goldfish -b android-4.14
repo sync

For older version:

1
2
3

git clone https://android.googlesource.com/kernel/goldfish
git checkout -a 
git checkout -b branch_name

AOSP

repo init -u https://aosp.tuna.tsinghua.edu.cn/platform/manifest -b android-9.0.0_r47

repo init -u https://aosp.tuna.tsinghua.edu.cn/platform/manifest -b android-9.0.0_r47

Kernel

repo init -u https://aosp.tuna.tsinghua.edu.cn/kernel/manifest -b common-android-mainline

Build

Docker Config

Project Structure

1
2
3
4
5
6
7

├── android
│   ├── aosp
│   ├── bin
│   └── kernel
└── build_aosp
    ├── Dockerfile
    └── sources.list

Dockerfile

1
2
3
4
5
6
7
8
9
10
11

FROM ubuntu:18.04

WORKDIR /root/
ENV PATH ~/bin:$PATH
ENV TERM xterm
ENV DEBIAN_FRONTEND noninteractive

COPY sources.list /etc/apt/sources.list
RUN apt-get update && apt-get install -y --no-install-recommends apt-utils && apt-get install -y ca-certificates
RUN sed -i 's/http:\/\/mirrors.tuna.tsinghua.edu.cn/https:\/\/mirrors.tuna.tsinghua.edu.cn/g' /etc/apt/sources.list
RUN apt-get update && apt-get -y install git-core gnupg flex bison gperf build-essential zip curl zlib1g-dev gcc-multilib g++-multilib libc6-dev-i386 lib32ncurses5-dev x11proto-core-dev libx11-dev lib32z-dev libgl1-mesa-dev libxml2-utils xsltproc unzip

Build

1
2
3
4
5
6
7
8

docker build -t build_aosp ./build_aosp
docker build --no-cache=true build_aosp ./build_aosp
docker run -it -v ~/android:/root build_aosp /bin/bash

source build/envsetup.sh
m help
m

Transfer File Using rsync

1. native cmd

   rsync -avuz –progress source_dir dest_dir

   • -v, –verbose Verbose output

   • -q, –quiet suppress message output

   • -a, –archive archive files and directory while synchronizing ( -a equal to following options -rlptgoD)
   • -r, –recursive sync files and directories recursively
   • -b, –backup take the backup during synchronization
   • -u, –update don’t copy the files from source to destination if destination files are newer
   • -l, –links copy symlinks as symlinks during the sync
   • -n, –dry-run perform a trial run without synchronization
   • -e, –rsh=COMMAND mention the remote shell to use in rsync
   • -z, –compress compress file data during the transfer
   • -h, –human-readable display the output numbers in a human-readable format
   • –progress show the sync progress during transfer

2. parallelled wrapper

   http://moo.nac.uci.edu/~hjm/parsync/

   ./parsyncfp –NP=6 –startdir = ‘/home/zl/fuzz’ ./ remote_user@remote_ip:remote_dir

目标程序源代码

首先准备测试的目标程序

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

#include <stdio.h> 
#include <stdlib.h> 
#include <unistd.h> 
#include <string.h> 
#include <signal.h> 

int vuln(char *str)
{
    int len = strlen(str);
    //如果输入的字符串的首字符为A并且长度为66，则异常退出
    if(str[0] == 'A' && len == 66)
    {
        raise(SIGSEGV);
    }
    //如果输入的字符串的首字符为F并且长度为6，则异常退出
    else if(str[0] == 'F' && len == 6)
    {
        raise(SIGSEGV);
    }
    else
    {
        printf("\nit is good!\n");
    }
    return 0;
}

int main(int argc, char *argv[])
{
    int i;
    char buf[100]={0};
    printf( "Enter a value :");
    scanf("%d", &i);
    if ((i % 2) == 1) 
    {
        getchar();
        printf("Odd\nPlease enter a string: ");
        gets(buf);//存在栈溢出漏洞
        printf(buf);//存在格式化字符串漏洞
        vuln(buf);
    }
    else
    {
        printf("Even\n");
    }
    return 0;
}

Setup AFL

AFL的安装非常简单

1
2
3
4
5

wget http://lcamtuf.coredump.cx/afl/releases/afl-latest.tgz
tar xvf afl-latest.tgz
cd afl-*
$ make && make install
$ make install

1
2
3
4
5
6
7
8
9
10
11

root@localhost:~/vlun# afl-gcc -g -o vuln vuln.c

afl-cc 2.52b by <[email protected]>
Origin:  afl-gcc -g -o vuln vuln.c
Modified:  gcc -g -o vuln vuln.c -B /usr/local/lib/afl -g -O3 -funroll-loops -D__AFL_COMPILER=1 -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1

afl-as 2.52b by <[email protected]>
as_origin:  /usr/local/lib/afl/as --64 -o /tmp/cc87FEhK.o /tmp/cc6V6Ux0.s
as_modified as --64 -o /tmp/cc87FEhK.o /tmp/.afl-24042-1569464334.s[+] Instrumented 14 locations (64-bit, non-hardened mode, ratio 100%).
/tmp/cc87FEhK.o: In function `main':
/root/vlun/vuln.c:37: warning: the `gets' function is dangerous and should not be used.

Run the fuzzer

首先准备一下fuzz需要的testcase，然后就可以执行fuzz。

1
2
3

mkdir fuzz_in fuzz_out
echo "123\nABC" > fuzz_in/testcase
afl-fuzz -i fuzz_in -o fuzz_out ./vuln

• process timing
  主要包含了afl运行的时间信息。
• overall results
  包括运行的总周期数、总路径数、崩溃次数、超时次数。
• map coverage
  其中map density是哈希表的密度，如多目标程序分支很多，会导致map density很大，这种情况会产生碰撞，影响fuzz结果。
• stage progress
  当前执行的fuzz变异策略、执行的进度、执行的速度
• findings in depth
  目标程序的路径信息和目标崩溃的统计

Analyze result

在fuzz_out/crashes/下面记录了6个会导致目标程序crash的测试用例：

1
2
3
4
5
6
7

root@localhost:~/vlun# ls fuzz_out/crashes/
id:000000,sig:11,src:000003,op:havoc,rep:4
id:000001,sig:06,src:000000+000003,op:splice,rep:64
id:000002,sig:06,src:000003,op:havoc,rep:8
id:000003,sig:06,src:000003,op:havoc,rep:4
id:000004,sig:06,src:000000,op:havoc,rep:8
id:000005,sig:11,src:000003+000000,op:splice,rep:8

• id:000000,sig:11,src:000003,op:havoc,rep:4

  1 2	root@localhost:~/vlun# xxd fuzz_out/crashes/id:000000,sig:11,src:000003,op:havoc,rep:4 00000000: 3132 330a 46c2 3939 2a1b 123.F.99*.

  输入到目标程序中的字符串为123.F.99.
  这里首先scanf会读取输入123，之后遇到”.”为非法字符，第一个输入即为123程序判断为奇数。之后读取第二个输入为”F.99.”，程序会产生异常信号。

• id:000001,sig:06,src:000000+000003,op:splice,rep:64

  1 2 3 4 5 6 7 8

  root@localhost:~/vlun# xxd fuzz_out/crashes/id:000001,sig:06,src:000000+000003,op:splice,rep:64 00000000: 39cc cccc cccc c7ed edcb f2f2 f274 8787 9............t.. 00000010: 8787 8787 f2f2 f2f2 f2ed eded eded 10ed ................ 00000020: 10fb 3932 3313 031d edfb eded f0ed 0000 ..923........... 00000030: 0400 eded 1bed 10fb 3932 3313 03ff 801b ........923..... 00000040: ed0c ee7e e803 0007 eded eded 10ed 10fb ...~............ 00000050: 3932 3313 031d edfb eded f0ed c7ed e8d4 923............. 00000060: 01f0 eddf ed1f dd00 0002 0011 0d00 ..............

  这里是个溢出的异常。

• id:000002,sig:06,src:000003,op:havoc,rep:8
  还是溢出导致的异常。

• id:000003,sig:06,src:000003,op:havoc,rep:4

  1 2 3 4 5 6 7 8 9

  root@localhost:~/vlun# xxd fuzz_out/crashes/id:000002,sig:06,src:000003,op:havoc,rep:8 00000000: 3132 330a 46c2 eeee eeee eeee eeee eeee 123.F........... 00000010: ffee eeee eeee eeee eeed ffff eeee eeee ................ 00000020: eeee eeee 40ee eeee edee eeff ffee eeee ....@........... 00000030: eeee eeee eeee eeee eeff ffee eeee eeee ................ 00000040: eeee eeee eeee eeed eeee eeee eeee eeee ................ 00000050: eeee eeee eeee edee eeee eeee eeee eeee ................ 00000060: ffff eeee eeee eeee eeee 40ee eeee edee ..........@..... 00000070: eeff ffee eeee eeee 430a ........C.

• id:000004,sig:06,src:000000,op:havoc,rep:8

  1 2	root@localhost:~/vlun# xxd fuzz_out/crashes/id:000003,sig:06,src:000003,op:havoc,rep:4 00000000: 313a 3325 6ec2 430a 1:3%n.C.

  这里是printf的format string漏洞

• id:000005,sig:11,src:000003+000000,op:splice,rep:8

  1 2 3 4 5 6

  root@localhost:~/vlun# xxd fuzz_out/crashes/id:000005,sig:11,src:000003+000000,op:splice,rep:8 00000000: 330a 41a2 a2a2 a2a2 a2a2 a2a2 a2a2 a2a2 3.A............. 00000010: a2a2 a2a2 a2a2 a2a2 a2a2 a2a2 a2a2 a2a2 ................ 00000020: a2a2 a2a2 a2a2 a2a2 a2a2 a2a2 a2a2 a2a2 ................ 00000030: a2a2 a2a2 a2a2 a2a2 a2a2 a29e a2a2 8fa2 ................ 00000040: a2a2 a243 0a ...C.

  输入首字母为A并且长度为66，程序则会产生异常信号退出。

插桩分析

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

gdb-peda$ disassemble main
Dump of assembler code for function main:
   ... ...
   /*main之前插入__afl_maybe_log*/
   0x0000000000400976 <+22>:    mov    rcx,0xfc08
   0x000000000040097d <+29>:    call   0x400eb0 <__afl_maybe_log>
   ... ...
   0x00000000004009f6 <+150>:   je     0x400ace <main+366>
   /*main中的分支插入__afl_maybe_log*/
   0x0000000000400a12 <+178>:   mov    rcx,0x8ee
   0x0000000000400a19 <+185>:   call   0x400eb0 <__afl_maybe_log>


   0x0000000000400a34 <+212>:   mov    edi,0x401370
   0x0000000000400a39 <+217>:   call   0x400860 <puts@plt>
   0x0000000000400a3e <+222>:   xchg   ax,ax
   ... ...
   0x0000000000400a56 <+246>:   mov    rcx,0xadb6
   0x0000000000400a5d <+253>:   call   0x400eb0 <__afl_maybe_log>
   ... ...
   0x0000000000400a7a <+282>:   mov    rbx,QWORD PTR [rsp+0x78]
   0x0000000000400a7f <+287>:   xor    rbx,QWORD PTR fs:0x28
   0x0000000000400a88 <+296>:   jne    0x400b4b <main+491>
   0x0000000000400a8e <+302>:   xchg   ax,ax
   ... ...
End of assembler dump.

AFL对程序出现je，jne的地方进行了插桩，赋值给rcx的随机数用于对代码快进行定位。
mov rcx,0xXXXX

References

1. Finding bugs using AFL
2. 初探Fuzz-AFL
3. Internals of AFL fuzzer - Compile Time Instrumentation

AFL 源码学习

最近学习了由Google安全工程师Michał Zalewski开发的一款开源fuzzing测试工具American Fuzzy Lop。这里总结一下阅读源码中的收获和使用的相关技巧。

AFL安装和使用

AFL的安装非常简单，仅仅需要下载源码然后进行编译安装。

1
2
3
4
5

wget http://lcamtuf.coredump.cx/afl/releases/afl-latest.tgz
tar xvf afl-latest.tgz
cd afl-*
$ make && make install
$ make install

编译目标程序

AFL有afl-gcc和llvm两种模式

1.afl-gcc

AFL提供了两种常见编译器的wrapper，afl-gcc和afl-g++，在进行编译的时候，仅需指定编译器为afl-gcc/afl-g++即可

1
2

./configure CC="afl-gcc" 
./configure CXX="afl-g++"

2.llvm

使用llvm模式进行编译可以提高fuzzing的速率，在llvm_mode目录中进行编译安装，之后使用afl-clang-fast构建目标程序。

1
2
3

cd llvm_mode
export LLVM_CONFIG=`which llvm-config` && make && cd ..
./configure --disable-shared CC="afl-clang-fast" or CXX="afl-clang-fast++" 

运行Fuzzing

afl-fuzz程序是AFL进行fuzzing的主程序，安装成功后使用afl-fuzz命令便可查看相关命令。

1
2
3
4
5
6
7
8
9

root@localhost:~# afl-fuzz
afl-fuzz 2.52b by <[email protected]>

afl-fuzz [ options ] -- /path/to/fuzzed_app [ ... ]

Required parameters:

  -i dir        - input directory with test cases
  -o dir        - output directory for fuzzer findings

1

echo core >/proc/sys/kernel/core_pattern

1

afl-fuzz -i afl_in -o afl_out /path/to/target [params]

• -i：输入测试用例
• -o：输出结果
• -t：设置程序执行的超时
• -d：quick & dirty 模式

输出结果

运行fuzzing后，会在输出文件夹中产生三个文件夹queue，crashes，hangs

• queue: 每个文件代表了afl-fuzz在fuzzing过程中获得的所有路径，每条路径不重复并且每条新路径都被修剪(trim)过
• crashed: 会导致目标程序crash的输入用例
• hangs: 导致目标程序超时的输入用例

AFL工作流程

1. afl_fuzz的main函数会解析用户输入命令，检查环境变量的设置、输入输出路径、目标文件。程序定义了结构体queue_entry链表维护fuzz中使用的文件。
2. 函数perform_dry_run()会使用初始的测试用例进行测试，确保目标程序能够正常执行,生成初始化的queue和bitmap。

   1 2 3 4 5 6 7 8 9 10 11 12

   perform_dry_run(char** argv) { struct queue_entry* q = queue; while (q) { //调用calibrate_case()函数对用例进行测试，验证输入用例是否会引发目标程序crash res = calibrate_case(argv, q, use_mem, 0, 1); switch (res) { case FAULT_NONE: case FAULT_TMOUT: case FAULT_CRASH: } } }

3. 函数 cull_queue() 会对初始队列进行筛选（更新favored entry）。遍历top_rated[]中的queue，然后提取出发现新edge的entry，并标记为favored，使得在下次遍历queue时，这些entry能获得更多执行fuzz的机会。

   这里使用greedy来进行筛选。首先初始化temp_v(previously-unseen bytes)并且设置queue_entry中的所有favored为0(q->favored = 0)。之后判断是否在top_rated中并且有被temp_v命中的bitmap，如果是便将其设置为favored(top_rated[i]->favored = 1)。

**More Detail:** 这里需要结合update_bitmap_score()进行理解。update_bitmap_score在trim_case和calibrate_case中被调用，用来维护一个最小(favored)的测试用例集合(top_rated[i])。这里会比较执行时间*种子大小，如果当前用例更小，则会更新top_rated。
1
2
3
4
5
6
7
8
9
10
11
12
e.g. 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

4. 进入while(1)开始fuzz循环
   • 进入循环后第一部还是 cull_queue() 对queue进行筛选
   • 判断queue_cur是否为空，如果是，则表示已经完成对队列的遍历，初始化相关参数，重新开始遍历队列
   • fuzz_one() 函数会对queue_cur所对应文件进行fuzz

     1 2 3 4 5 6 7 8 9 10 11 12 13

     [1] 根据是否有pending_favored和queue_cur的情况按照概率进行跳过 有pending_favored, 对于fuzz过的或者non-favored的以概率99%跳过 无pending_favored，95%跳过fuzzed&non-favored，75%跳过not fuzzed&non-favored，不跳过favored (跳过概率的宏定义在config.h中) [2] fd加载测试用例，如果之前calibrate失败，则重新进行calibrate_case() [3] 修剪测试用例，减小input大小 [4] calculate_score(queue_cur)得到performance score，如果该queue已经完成deterministic fuzzing，则直接跳到havoc阶段 [5] 接下来会进行四种deterministic的变异 bitfilp：按位翻转，1变为0，0变为1 arithmetic：整数加/减算术运算 interest：把一些特殊内容替换到原文件中 dictionary：把自动生成或用户提供的token替换/插入到原文件中 [6] havoc 多种变异方式的组合 [7] splice：拼接，2个seed进行拼接，并进行havoc

   • 判断是否结束，更新queue_cur和current_entry

     1 2	queue_cur = queue_cur->next; current_entry++;

   • 当队列中的所有文件都经过变异测试了，则完成一次”cycle done”。整个队列又会从第一个文件开始，再次继续进行变异，不过与第一次变异不同的是，因为没有随机性，这一次变异就不需要再进行deterministic fuzzing了。

afl-fuzz.c

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

int main(int argc, char** argv) {
  // 加载变异数据修正模块
  setup_post();
  if (!in_bitmap) memset(virgin_bits, 255, MAP_SIZE); // MAP_SIZE --> 0x00010000
  setup_shm();  // 设置共享内存
  init_count_class16();

  setup_dirs_fds(); // 设置模糊测试过程中的文件存放位置
  read_testcases();  // 读取测试用例到队列

  // 首先跑一遍所有的测试用例， 记录信息到样本队列
  perform_dry_run(use_argv);

  // 模糊测试主循环
  while (1) {
    u8 skipped_fuzz;
    // 每次循环从样本队列里面取测试用例
    cull_queue();
    
    // 判断是否完成遍历
    if (!queue_cur)
    {
        show_stats(); // 更新显示fuzzing状态信息
    }

    // 对测试用例进行测试
    skipped_fuzz = fuzz_one(use_argv);

    queue_cur = queue_cur->next;
    current_entry++;
  }
}

AFL变异

1. AFL中实现了6种变异方式：
2. bitfilp：按位翻转，1变为0，0变为1

   按位翻转，1变为0，0变为1。AFL中会根据翻转量/步长进行多种不同的翻转，按照顺序依次为：
   bitflip 1/1，每次翻转1个bit，按照每1个bit的步长从头开始
   这里也会对syntax tokens进行检测
   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做翻转

3. 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相同，那么这次变异肯定在上一个阶段已经执行过了，此次便不会再执行。

4. 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已经设定好。可以看到，用于替换的基本都是可能会造成溢出的数；与之前相同，effector map仍然会用于判断是否需要变异；

5. dictionary：把自动生成或用户提供的token替换/插入到原文件中

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

6. 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（用户提供的或自动生成的）插入

7. splice：拼接，2个seed进行拼接，并进行havoc

calculate_score()

根据execution speed, bitmap size, handicap, input depth来对case评分，用来调整在havoc阶段的用时。使得执行时间短，代码覆盖高，新发现的，路径深度深的case拥有更多havoc变异的机会。

AFL插桩

AFL插桩部分源码主要有三个，afl-gcc.c、afl-as.h、afl-as.c

afl-gcc.c

该文件可以看做是一个gcc的wrapper，同时也会完成对用户指令的解析，然后将结果传递给gcc，完成目标程序的编译。
main中主要调用了三个函数：

1
2
3

find_as(argv[0]);    //找到gcc/clang/llvm编译器
edit_params(argc, argv);    //处理参数
execvp(cc_params[0], (char**)cc_params);    //执行解析后的命令

1
2

for (int i = 0; i < cc_par_cnt; i ++)
      SAYF(" %s", cc_params[i]);

Origin: /root/afl/afl-2.52b/afl-gcc -g -o hello hello.c

Modified: gcc -g -o hello hello.c -B /root/afl/afl-2.52b -g -O3 -funroll-loops -D__AFL_COMPILER=1 -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1

afl-gcc实际执行了gcc编译命令，但是增加了几条命令。
-B \<directory>: Add \<directory> to the compiler’s search paths

插桩流程

从source code -> executable file要经过预处理(preprocessing))->编译(compilation)->汇编(assembly)->连接(linking)的流程。

1. 编译预处理程序对源文件进行预处理，生成预处理文件(.i文件)
2. 编译插桩程序对.i文件进行编译，生成汇编文件(.s文件)
   afl在这一步骤会对目标程序进行插桩
3. 汇编程序(as)对.s文件进行汇编，生成目标文件(.o文件)
4. 链接程序(ld)对.o文件进行连接，生成可执行文件(.out/.elf文件)
   compiler (language -> assembly), assembler (assembly -> object code), linker (object code -> executable/library)

在Linux机器上使用gcc进行编译的时候，默认会使用GNU as作为汇编器，这里使用-B参数指定使用afl-as。之后afl-as读取并且parse输入的.s文件，添加instrumentation trampoline和main payload。
依旧可以打印出实际执行的命令进行观察：

as_origin: /usr/local/lib/afl/as –64 -o /tmp/cczZQfJ3.o /tmp/ccPZDPvs.s

as_modified: as –64 -o /tmp/cczZQfJ3.o /tmp/.afl-15696-1568785903.s

afl-as在插入完成后，还是会调用实际的as完成汇编。

afl-as.c

1
2
3
4
5
6
7
8
9
10
11
12

int main(int argc, char** argv) {
    u8* inst_ratio_str = getenv("AFL_INST_RATIO");
    edit_params(argc, argv);
    if (getenv("AFL_USE_ASAN") || getenv("AFL_USE_MSAN")) {
        sanitizer = 1;
        inst_ratio /= 3;
    }
    if (!just_version) add_instrumentation();
    if (!(pid = fork())) execvp(as_params[0], (char**)as_params);

  }
}

这里主要有几个步骤，首先是获得一个重要的参数AFL_INST_RATIO，即指令插入的速度。
edit_params会生成实际要执行的as命令。
在使用ASAN或MSAN的情况下，会将指令插入速度调慢。
之后就是实际进行的插桩(add_instrumentation)工作。
最后fork进程执行as命令完成汇编。

add_instrumentation()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

static void add_instrumentation(void) {
    // 打开汇编代码文件
    outfd = open(modified_file, O_WRONLY | O_EXCL | O_CREAT, 0600);
    outf = fdopen(outfd, "w");
    while (fgets(line, MAX_LINE, inf)) {
        if (!pass_thru && !skip_intel && !skip_app && !skip_csect && instr_ok && instrument_next && line[0] == '\t' && isalpha(line[1])) {
            write_trampoline_fmt_64/32 //这里会写入trampoline和使用宏定义生成的随机数
        }
        fputs(line, outf); //写入原来的指令
        //定位到代码段
        if (strstr(line, ".code")) {
            //判断32位/64位
        }
        if (line[0] == '\t') {
            if (line[1] == 'j' && line[2] != 'm' && R(100) < inst_ratio) {
                write_trampoline_fmt_64/32
                ins_lines++;
            }  
        }
    if (ins_lines)
        write_main_payload_64/32
    }

}

根据程序中的注释，这里会匹配main函数，GCC中的branch label，clang中的branch label和conditional branches，然后插入相应指令。

trampoline

trampoline的源码定义在afl-as.h中，对应的有32位和64位两个版本。
在64位系统下，使用afl-gcc编译生成hello-word并且使用gdb进行反汇编结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

gdb-peda$ disassemble main
Dump of assembler code for function main:
   0x00000000004006e0 <+0>:	lea    rsp,[rsp-0x98]
   0x00000000004006e8 <+8>:	mov    QWORD PTR [rsp],rdx
   0x00000000004006ec <+12>:	mov    QWORD PTR [rsp+0x8],rcx
   0x00000000004006f1 <+17>:	mov    QWORD PTR [rsp+0x10],rax
   0x00000000004006f6 <+22>:	mov    rcx,0xdf40
   0x00000000004006fd <+29>:	call   0x400838 <__afl_maybe_log>
   0x0000000000400702 <+34>:	mov    rax,QWORD PTR [rsp+0x10]
   0x0000000000400707 <+39>:	mov    rcx,QWORD PTR [rsp+0x8]
   0x000000000040070c <+44>:	mov    rdx,QWORD PTR [rsp]
   0x0000000000400710 <+48>:	lea    rsp,[rsp+0x98]
   0x0000000000400718 <+56>:	sub    rsp,0x8
   0x000000000040071c <+60>:	mov    esi,0x400cb4
   0x0000000000400721 <+65>:	mov    edi,0x1
   0x0000000000400726 <+70>:	xor    eax,eax
   0x0000000000400728 <+72>:	call   0x400680 <__printf_chk@plt>
   0x000000000040072d <+77>:	xor    eax,eax
   0x000000000040072f <+79>:	add    rsp,0x8
   0x0000000000400733 <+83>:	ret
End of assembler dump.

1
2

#define MAP_SIZE_POW2       16
#define MAP_SIZE            (1 << MAP_SIZE_POW2)

1

define R(x) (random() % (x))

1

fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32, R(MAP_SIZE));

结合afl-as.h中的源码可以更加直观的理解R(MAP_SIZE)的含义：

1
2

movq $0x%08x, %%rcx
call __afl_maybe_log

Fork Server

afl使用fork server来提高fuzz的速度，在目标程序编译成功后，需要使用afl-fuzz进行fuzz。这里afl会根据用户的原始输入，再进行一系列的mutate，然后将结果传入目标程序，并且分析程序运行是否正常。这里为了节约反复使用execve()加载目标程序造成的额外开销(载入目标文件和库、解析符号地址)，afl实现了fork server来完成目标程序的反复执行。
afl作者在博客中提到，原本fork server的实现有两种思路：
[1] 实现一个ELF loader
[2] snapshot子进程
但是这两种实现在处理signal和file descriptors时会遇到困难。

结合之前的alf-fuzz进行分析，calibrate_case()函数会调用init_forkserver()来完成forkserver的初始化。

1
2

if (dumb_mode != 1 && !no_forkserver && !forksrv_pid)
    init_forkserver(argv);

init_forkserver()

该函数主要会执行fork()得到父进程和子进程，父进程为afl-fuzz，子进程为forkserver。
主要步骤如下

1. 创建2个管道:
   ctl_pipe传递控制: 父进程写 -> 子进程读
   st_pipe传递状态: 子进程写 -> 父进程读
2. 调用fork()
3. 子进程: 绑定输入流输出流到FORKSRV_FD
   ctl_pipe[0] -> FORKSRV_FD 输入流
   st_pipe[1] -> FORKSRV_FD + 1 输出流
   execv(target_path, argv)创建新进程，执行目标程序。

   这里使用dup2来绑定绑定管道到FORKSRV_FD上
   dup(oldfd) -> fcntl(oldfd, F_DUPFD, 0)
   dup2(oldfd, newfd) -> close(oldfd)；fcntl(oldfd, F_DUPFD, newfd)；

   1 2 3 4

   if (!forksrv_pid) { if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed"); if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed"); execv(target_path, argv);

4. 父进程：主要做些错误处理相关的工作，通过管道读取子进程返回状态，来确定server是否正常运行起来了

   1 2 3 4 5 6 7

   fsrv_ctl_fd = ctl_pipe[1]; fsrv_st_fd = st_pipe[0]; rlen = read(fsrv_st_fd, &status, 4); if (rlen == 4) { OKF("All right - fork server is up."); return; }

   fuzzer <-> fork_server

简化的流程图如下：

首先alf-fuzz会创建两个管道(init_forkserver())，然后会去执行afl-gcc编译出来的目标程序。结合之前的分析，目标程序的main函数位置已经被插桩，程序的控制流会交到_afl_maybe_log手中。如fuzz是第一次运行，则此时的程序便成为了fuzz server，之后运行的目标程序都是由该server fork出来的子进程。fuzz进行的时候，fuzz server会一直fork子进程，并且将子进程的结束状态通过pipe传递给afl-fuzz。
这里有几点需要注意：afl在这里利用了fork()的特性(creates a new process by duplicating the calling process)来实现目标程序反复执行。实际的fuzz server(_afl_maybe_log)由afl事先插桩在目标程序中，在进入main函数之前，fuzz server便会fork()新的进程，进行fuzz。

这里afl_fuzz进程与fork server是父子关系，fork server与目标程序的进程是父子关系。fork server使用waitpid()等待目标程序执行完成，然后通过pipe将执行状态返回给afl_fuzz。

fuzzer <-> target

在fuzz进行的过程中，还有一个问题需要解决：如何根据程序运行的状态来动态调整测试用例(test case mutateion)。在上面的分析中，我们已经知道afl_fuzz可以通过管道命令来获取目标程序的运行状态，但是仅仅知道程序的exit code并不能满足要求。因此，afl使用了共享内存的方法，实现afl_fuzz和目标程序之间的信息传递。
afl-fuzz在启动时，会调用setup_shm()来分配一块大小为MAP_SIZE的内存空间。

1
2
3
4
5
6
7
8
9

EXP_ST void setup_shm(void) {
      shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);
      shm_str = alloc_printf("%d", shm_id);
      // 判断运行的模式，将共享内存id写入环境变量
      if (!dumb_mode) setenv(SHM_ENV_VAR, shm_str, 1);
      // trace_bits为共享内存地址
      trace_bits = shmat(shm_id, NULL, 0);

}

1
2
3
4
5

leaq .AFL_SHM_ENV(%rip), %rdi
CALL_L64("getenv")

testq %rax, %rax
je    __afl_setup_abort

1
2
3
4
5
6

afl_fuzz.c
static u8 run_target(char** argv, u32 timeout) {
    ...
    memset(trace_bits, 0, MAP_SIZE);
    ...
    }

[1] check __afl_area_ptr

在目标程序中，首先会判断afl_area_ptr是否为空，若为空则跳转afl_setup

1
2
3
4

/* Check if SHM region is already mapped. */
movl __afl_area_ptr, %edx
testl %edx, %edx
je __afl_setup

[2] setup ptr

afl_setup首先会判断之前setup是否成功，若之前setup失败，则直接跳过。之后判断afl_global_area_ptr指针是否存在:
若存在->将afl_global_area_ptr存入rdx寄存器，并且调用afl_store
若不存在->调用afl_setup_first

1
2
3
4
5
6
7
8

__afl_setup:
cmpb $0, __afl_setup_failure(%rip)
jne __afl_return
movq  __afl_global_area_ptr(%rip), %rdx
testq %rdx, %rdx
je    __afl_setup_first
movq %rdx, __afl_area_ptr(%rip)
jmp  __afl_store

1
2
3
4
5
6
7
8
9

__afl_setup_first:
leaq -352(%rsp), %rsp
movq %rax,   0(%rsp)
movq %rcx,   8(%rsp)
movq %rdi,  16(%rsp)
        ...
        ...
movq %xmm14, 320(%rsp)
movq %xmm15, 336(%rsp)

1
2
3
4
5
6
7
8

pushq %r12
movq  %rsp, %r12
subq  $16, %rsp
andq  $0xfffffffffffffff0, %rsp
leaq .AFL_SHM_ENV(%rip), %rdi
CALL_L64("getenv")
testq %rax, %rax
je    __afl_setup_abort

1
2
3
4
5
6
7
8

movq  %rax, %rdi
CALL_L64("atoi")
xorq %rdx, %rdx    /* shmat flags    */
xorq %rsi, %rsi    /* requested addr */
movq %rax, %rdi    /* SHM ID         */
CALL_L64("shmat")
cmpq $-1, %rax
je   __afl_setup_abort

1
2
3
4
5
6
7
8
9
10

/* Store the address of the SHM region. */
movq %rax, %rdx
movq %rax, __afl_area_ptr(%rip)
#ifdef __APPLE__
    movq %rax, __afl_global_area_ptr(%rip)
#else
    movq __afl_global_area_ptr@GOTPCREL(%rip), %rdx
    movq %rax, (%rdx)
#endif
movq %rax, %rdx

[3] afl_forkserver

首先会写入管道，通知父进程。

1
2
3
4
5
6
7
8
9

__afl_forkserver:
    pushq %rdx
    pushq %rdx
    movq $4, %rdx
    leaq __afl_temp(%rip), %rsi
    movq $" STRINGIFY((FORKSRV_FD + 1)) ", %rdi
CALL_L64("write")
    cmpq $4, %rax
    jne  __afl_fork_resume

__afl_fork_wait_loop:

之后进入loop，读取管道中的内容，如果不为4，就会跳转afl_die。

1
2
3
4
5
6
7

__afl_fork_wait_loop:
  movq $4, %rdx               /* length    */
  leaq __afl_temp(%rip), %rsi /* data      */
  movq $" STRINGIFY(FORKSRV_FD) ", %rdi             /* file desc */
CALL_L64("read")
  cmpq $4, %rax
  jne  __afl_die

1
2
3
4

CALL_L64("fork")
  cmpq $0, %rax
  jl   __afl_die
  je   __afl_fork_resume

1
2
3
4
5

  movl %eax, __afl_fork_pid(%rip)
  movq $4, %rdx                   /* length    */
  leaq __afl_fork_pid(%rip), %rsi /* data      */
  movq $" STRINGIFY((FORKSRV_FD + 1)) ", %rdi   /* file desc */
CALL_L64("write")

1
2
3
4
5
6
7
8
9
10
11

  movq $0, %rdx                   /* no flags  */
  leaq __afl_temp(%rip), %rsi     /* status    */
  movq __afl_fork_pid(%rip), %rdi /* PID       */
CALL_L64("waitpid")
  cmpq $0, %rax
  jle  __afl_die
  movq $4, %rdx               /* length    */
  leaq __afl_temp(%rip), %rsi /* data      */
  movq $" STRINGIFY((FORKSRV_FD + 1)) ", %rdi    /* file desc */
CALL_L64("write")
  jmp  __afl_fork_wait_loop

####afl_fork_resume
关闭管道，恢复寄存器，跳转afl_store存储路径。

1
2
3
4
5
6
7
8
9
10
11
12
13

__afl_fork_resume:
  movq $" STRINGIFY(FORKSRV_FD) ", %rdi
CALL_L64("close")
  movq $" STRINGIFY((FORKSRV_FD + 1)) ", %rdi
CALL_L64("close")
  popq %rdx
  popq %rdx
  movq %r12, %rsp
  popq %r12
  movq  0(%rsp), %rax
  ... ...
  leaq 352(%rsp), %rsp
  jmp  __afl_store

__afl_die

出错则退出

1
2
3

__afl_die:
  xorq %rax, %rax
CALL_L64("_exit")

__afl_store:

AFL是根据二元tuple(跳转的源地址+目标地址)来记录分支信息，从而获取目标程序的执行流程和代码覆盖情况。
cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;

1. 为了简化连接复杂对象的过程和保持XOR输出平均分布，当前位置是随机产生的。
2. share_mem[]数组是一个调用者传给被instrument程序的64KB的共享内存区域，数组的元素是Byte。数组中的每个元素，都被编码成一个(branch_src, branch_dst)，相当于存储路径的bitmap。这个数组的大小要应该能存2K到10K个分支节点，这样即可以减少冲突，也可以实现毫秒级别的分析。
   这种形式的覆盖率，相对于简单的基本块覆盖率来说，对程序运行路径提供了一个更好的描述。以下面两个路径产生的tupes为例：
   A -> B -> C -> D -> E (tuples: AB, BC, CD, DE)
   A -> B -> D -> C -> E (tuples: AB, BD, DC, CE)
   这更有助于发现代码的漏洞，因为大多数安全漏洞经常是一些没有预料到的状态转移，而不是因为没有覆盖那一块代码。
3. 最后一行右移操作是用来保持tuples的定向性。如果没有右移操作，A ^ B和B ^ A就没办法区别了，同样A ^ A和B ^ B也是一样的。Intel CPU缺少算数指令，左移可能会会导致级数重置为0，但是这种可能性很小，用左移纯粹是为了效率。

计算并储存代码命中位置，afl_prev_loc是前一次跳转位置，rcx为当前跳转位置，将afl_prev_loc的值与rcx的值进行交换，然后__afl_prev_loc右移一位。rdx为共享内存的地址。

1
2
3
4
5
6
7
8
9
10
11
12

__afl_store:
#ifndef COVERAGE_ONLY
  xorq __afl_prev_loc(%rip), %rcx
  xorq %rcx, __afl_prev_loc(%rip)
  shrq $1, __afl_prev_loc(%rip)
#endif /* ^!COVERAGE_ONLY */

#ifdef SKIP_COUNTS
  orb  $1, (%rdx, %rcx, 1)
#else
  incb (%rdx, %rcx, 1)
#endif /* ^SKIP_COUNTS */

覆盖率计算

这里蓝色块代表程序执行过程中的基本块，黄色块代表相应的用于统计的探针代码，因而我们可以完整记录程序的执行路径，即：A -> C -> F -> H -> Z。另外，在AFL中为了更方便的描述边界（edge），将源基本块和目的基本块的配对组合称为tuple，即下图路径中有 4 个 tuple（AC，CF，FH，HZ)。

很自然，通过记录tuple信息就可以统计边界覆盖率了，AFL通过一个bitmap来记录这些信息，不过bitmap是以byte而非bit作为单位，因为程序还要记录tuple的命中数，而命中数又被划分成如下bucket：

1	1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+

References

1. afl-fuzz-crash-exploration-mode
2. Technical “whitepaper” for afl-fuzz
3. afl-fuzz on different file systems
4. Internals of AFL fuzzer - Compile Time Instrumentation
5. Fuzzing random programs without execve()
6. 漏洞挖掘技术之 AFL 项目分析
7. afl-fuzz技术白皮书
8. Fuzz之AFL
9. http://zeroyu.xyz/2019/05/15/how-to-use-afl-fuzz/
10. AFL内部实现细节小记
11. AFL源码分析