afl-fuzz.c细节分析之perform_dry_run函数分析

afl-fuzz.c细节分析之perform_dry_run函数分析

1
2
3
4
5
6
7
8
9
/*
直接运行所有的初始testcase来确保程序按照预期运行，这个操作只会进行一次。
    */
static void perform_dry_run(char** argv){
    ......
    while(q){
        ......
    }
}

取队列，并设置cal_failures为0：

1
2
struct queue_entry* q = queue;
u32 cal_failures = 0;

读取环境变量AFL_SKIP_CRASHES为skip_crashes：

1
u8* skip_crashes = getenv("AFL_SKIP_CRASHES");

然后是进入队列的循环：

1
2
3
while(q){
    ......
}

循环内容如下：

打开当前testcase，并判断是否可读：

1
2
3
4
5
6
7
8
9
fd = open(q->fname, O_RDONLY);        //testcase 文件 
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);

校准testcase：

1
res = calibrate_case(argv, q, use_mem, 0, 1);

检查存放q->len的内存空间use_mem没有double free以及堆污染等情况：

1
ck_free(use_mem);

Ctrl+C就结束：

1
if (stop_soon) return;

若校验结果res为crash_mode或者FAULT_NOBITS就打印相关信息：

1
2
3
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);

根据res的值对错误进行判断：

1
2
3
switch(res){
    ......
}

针对以下几种异常类型进行操作：

  • FAULT_NONE：
1
2
3
4
5
6
7
case FAULT_NONE:

    if (q == queue) check_map_coverage();

    if (crash_mode) FATAL("Test case '%s' does *NOT* crash", fn);

    break;

判断q是不是queue的头结点，是则进行check_map_coverage()，检查map覆盖率；然后判断是否处于crash_mode，是则打印相关信息。

  • FAULT_TMOUT：

若定义了timeout_given，则进行判断并打印相关信息。

  • FAULT_CRASH：

若是crash_mode，则退出。

若设置了AFL_SKIP_CRASHES环境变量，则打印警告讯息。

若是mem_limit，则抛出异常，打出相关讯息。

  • FAULT_ERROR：打印异常讯息。

  • FAULT_NOINST：打印异常讯息。

  • FAULT_NOBITS：

1
2
3
4
5
6
7
case FAULT_NOBITS://

    useless_at_start++;

    if (!in_bitmap && !shuffle_queue)
      WARNF("No new instrumentation output, test case may be useless.");

无用路径计数器useless_at_start加1，并输出警告。

根据计数器cal_failures来判断dry run到底是否根据预期情况运行：

1
2
3
4
5
6
7
8
9
10
11
12
13
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!");
}

输出dry run成功讯息：

1
OKF("All test cases processed.");

calibrate_case函数分析

这个函数是AFL的重点函数之一，用于测试一个样例，在perform_dry_run，save_if_interesting，fuzz_one，pilot_fuzzing,core_fuzzing函数中均有调用。

通过检查校验和是否为0检测是否第一次运行testcase：

1
first_run = (q->exec_cksum == 0);

根据from_queue以及resuming_fuzz判断样例是否为队列中的以及是否刚恢复fuzz，若不是队列中的或者刚恢复fuzz，则给出一个宽限的timeout：

1
2
3
if (!from_queue || resuming_fuzz)
use_tmout = MAX(exec_tmout + CAL_TMOUT_ADD,
                exec_tmout * CAL_TMOUT_PERC / 100);

设置阶段名称，并根据fast_cal来设置阶段数目stage_max，这里的fast_cal由环境变量AFL_FAST_CAL给出：

1
2
stage_name = "calibration";
stage_max  = fast_cal ? 3 : CAL_CYCLES;

确保forkserver启动，拷贝trace_bits到first_trace：

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

if (q->exec_cksum) memcpy(first_trace, trace_bits, MAP_SIZE);

获取开始时间：

1
start_us = get_cur_time_us();

然后是循环stage_max次的执行testcase环节。

若不是第一次执行就根据状态刷新频率显示fuzz状态：

1
if (!first_run && !(stage_cur % stats_update_freq)) show_stats();

写入模块化的数据：

1
write_to_testcase(use_mem, q->len);

运行testcase，并将结果赋予fault：

1
fault = run_target(argv, use_tmout);

Ctrl+C或者fault不是crash_mode则进入abort_calibration：

1
if (stop_soon || fault != crash_mode) goto abort_calibration;

若不处于dumb_mode且为阶段1且共享内存没有任何路径，则赋failt为FAULT_NOINST并进入abort_calibration：

1
2
3
4
5
if (!dumb_mode && !stage_cur && !count_bytes(trace_bits)) {
    fault = FAULT_NOINST;
    goto abort_calibration;
}

根据cksum来判断stage_max的循环中每次执行testcase是否会产生新的路径：

1
2
3
4
5
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

if (q->exec_cksum != cksum) {
    ......
}

if内部结构如下。

首先根据共享内存判断是否有新的路径：

1
u8 hnb = has_new_bits(virgin_bits);

若返回值hnb大于0，则将new_bits设置为hnb：

1
if (hnb > new_bits) new_bits = hnb;

若当前q->exec_cksum不为0，即该queue不是第一次执行，则进入判断当前queue的路径是否为可变的循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (q->exec_cksum) {

    u32 i;

    for (i = 0; i < MAP_SIZE; i++) {

      if (!var_bytes[i] && first_trace[i] != trace_bits[i]) {

        var_bytes[i] = 1;
        stage_max    = CAL_CYCLES_LONG;

      }

    }

这里的判断是否可变的依据就是first_trace[i] != trace_bits[i]，若可变就将stage_max增加到CAL_CYCLES_LONG。

设置路径可变的标记var_detected设置为1：

1
var_detected = 1;

若queue的路径不可变则设置当前queue的校验和为总的cksum，并拷贝first_trace至trace_bits：

1
2
q->exec_cksum = cksum;
memcpy(first_trace, trace_bits, MAP_SIZE);

计算运行时间和总的阶段数：

1
2
3
4
stop_us = get_cur_time_us();

total_cal_us     += stop_us - start_us;
total_cal_cycles += stage_max;

收集阶段信息：

1
2
3
4
5
6
7
8
9
q->exec_us     = (stop_us - start_us) / stage_max;
q->bitmap_size = count_bytes(trace_bits);
q->handicap    = handicap;
q->cal_failed  = 0;

total_bitmap_size += q->bitmap_size;
total_bitmap_entries++;

update_bitmap_score(q);

后面就是告诉用户检测中没有新bits的情况。

init_forkserver()粗析

通过forkserver执行目标程序，具体原理。

创建两个管道，若创建失败提示信息：

1
if (pipe(st_pipe) || pipe(ctl_pipe)) PFATAL("pipe() failed");

创建fuzzer的子进程forkserver：

1
forksrv_pid = fork();

然后就是forkserver执行的内容：

1
2
3
if (!forksrv_pid) {//forkserver
    ......
}

针对OpenBSD更改进程能操控的资源：

能同时打开的文件数量：

1
2
3
4
5
6
if (!getrlimit(RLIMIT_NOFILE, &r) && r.rlim_cur < FORKSRV_FD + 2) {

    r.rlim_cur = FORKSRV_FD + 2;
    setrlimit(RLIMIT_NOFILE, &r); /* Ignore errors */

}

其他一些针对OpenBSD的调整：

1
2
3
4
5
6
7
8
9
    if (mem_limit) {

        r.rlim_max = r.rlim_cur = ((rlim_t)mem_limit) << 20;

#ifdef RLIMIT_AS

      setrlimit(RLIMIT_AS, &r); /* Ignore errors */

#else

有关异常核心的处理：

1
2
3
r.rlim_max = r.rlim_cur = 0;

setrlimit(RLIMIT_CORE, &r); /* Ignore errors */

守护forkserver进程：

1
setsid();

重定向/dev/null到1和2中：

1
2
dup2(dev_null_fd, 1);
dup2(dev_null_fd, 2);

如果指定了out_file则重定向/dev/null到0，否则重定向out_file到0：

1
2
3
4
5
6
7
8
9
10
if (out_file) {

  dup2(dev_null_fd, 0);

} else {

  dup2(out_fd, 0);
  close(out_fd);

}

重定向ctl_pipe[0]到forkserver，st_pipe[1]到forkserver子进程：

1
2
if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed");
if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed");

关闭相关文件描述符：

1
2
3
4
5
6
7
8
9
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));

有关环境变量LD_BIND_LAZY以及LD_BIND_NOW的设置：

1
if (!getenv("LD_BIND_LAZY")) setenv("LD_BIND_NOW", "1", 0);

有关ASAN的设置：

1
2
3
4
setenv("ASAN_OPTIONS", "abort_on_error=1:"
                       "detect_leaks=0:"
                       "symbolize=0:"
                       "allocator_may_return_null=1", 0);

有关MSAN的设置：

1
2
3
4
5
setenv("MSAN_OPTIONS", "exit_code=" STRINGIFY(MSAN_ERROR) ":"
                       "symbolize=0:"
                       "abort_on_error=1:"
                       "allocator_may_return_null=1:"
                       "msan_track_origins=0", 0);

执行目标程序(forkserver)，除非失败不然不会返回：

1
execv(target_path, argv);

使用一个标记0xfee1dead告诉父进程子进程运行失败：

1
2
*(u32*)trace_bits = EXEC_FAIL_SIG;
exit(0);

父进程fuzzer执行的内容：

关闭一些描述符：

1
2
3
4
5
close(ctl_pipe[0]);
close(st_pipe[1]);

fsrv_ctl_fd = ctl_pipe[1];
fsrv_st_fd  = st_pipe[0];

等待forkserver启动以及打印相关信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 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);

......

异常处理：

1
......

write_to_testcase函数分析

首先判断是否存在了文件，若存在用作fuzz的文件则将其unlink掉，并创建一个新的文件：

1
2
3
4
5
6
7
8
9
  if (out_file) {

  unlink(out_file); /* Ignore errors. */

  fd = open(out_file, O_WRONLY | O_CREAT | O_EXCL, 0600);

  if (fd < 0) PFATAL("Unable to create '%s'", out_file);

} else lseek(fd, 0, SEEK_SET);

将数据写入用于fuzz的文件中：

1
ck_write(fd, mem, len, out_file);

修剪文件：

1
2
3
4
5
6
if (!out_file) {

    if (ftruncate(fd, len)) PFATAL("ftruncate() failed");
    lseek(fd, 0, SEEK_SET);

} else close(fd);

run_target函数分析

函数会运行目标程序，监控其运行时间，并返回状态信息。调用该函数的程序将更新当前的tuple。

清零共享内存并防止任何其他行为读写该内存：

1
2
memset(trace_bits, 0, MAP_SIZE);
MEM_BARRIER();

dumb模式下没有forkserver，进行类似init_forkserver中的处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
......
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);

}
......
execv(target_path, argv);
......

若不是dumb模式，并且forkserver开启了，向控制管道写入控制的运行时间：

1
2
3
4
5
6
if ((res = write(fsrv_ctl_fd, &prev_timed_out, 4)) != 4) {

    if (stop_soon) return 0;
    RPFATAL(res, "Unable to request new process from fork server (OOM?)");

}

读取child_pid：

1
2
3
4
5
6
if ((res = read(fsrv_st_fd, &child_pid, 4)) != 4) {

    if (stop_soon) return 0;
    RPFATAL(res, "Unable to request new process from fork server (OOM?)");

}

forkserver创建失败显示信息：

1
if (child_pid <= 0) FATAL("Fork server is misbehaving (OOM?)");

设置timeout：

1
2
3
4
it.it_value.tv_sec = (timeout / 1000);
it.it_value.tv_usec = (timeout % 1000) * 1000;

setitimer(ITIMER_REAL, &it, NULL);

分情况保存status：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  if (dumb_mode == 1 || no_forkserver) {

      if (waitpid(child_pid, &status, 0) <= 0) PFATAL("waitpid() failed");

  } else {

  s32 res;

  if ((res = read(fsrv_st_fd, &status, 4)) != 4) {

      if (stop_soon) return 0;
      RPFATAL(res, "Unable to communicate with fork server (OOM?)");

  }

}

检查子进程是否正常退出：

1
if (!WIFSTOPPED(status)) child_pid = 0;

设置timeout：

1
2
3
4
it.it_value.tv_sec = 0;
it.it_value.tv_usec = 0;

setitimer(ITIMER_REAL, &it, NULL);

区分x86和x86-64设置共享内存：

1
2
3
4
5
#ifdef __x86_64__
    classify_counts((u64*)trace_bits);
#else
    classify_counts((u32*)trace_bits);
#endif /* ^__x86_64__ */

有关状态的信息设置：

1
2
3
4
5
6
7
8
9
10
if (WIFSIGNALED(status) && !stop_soon) {

    kill_signal = WTERMSIG(status);

    if (child_timed_out && kill_signal == SIGKILL) return FAULT_TMOUT;

return FAULT_CRASH;

}
......

正常run返回FAULT_NONE，有异常返回FAULT_CRASH，dumb mode下有错误返回FAULT_ERROR。

count_bytes函数分析

用于计算字节的数目。

每次读取mem中的四个字节，通过每个字节与0xff进行与运算来判断当前字节是否为0x00，不是则统计数目的变量ret加1：

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

static u32 count_bytes(u8* mem) {

    u32* ptr = (u32*)mem;//4 bytes max = 2^32
    u32  i   = (MAP_SIZE >> 2);//2^14 
    u32  ret = 0;

    while (i--) {

        u32 v = *(ptr++);

        if (!v) continue;
        if (v & FF(0)) ret++;
        if (v & FF(1)) ret++;
        if (v & FF(2)) ret++;
        if (v & FF(3)) ret++;

  }

  return ret;

}

has_new_bits函数分析

用于检查当前的运行路径是否为位图带来了新的内容（区分了x86和x86-64的情况）。

若current不为0且*current & *virgin不为0则说明发现了新路径或者某条路径的执行次数和之前有所不同：

1
if (unlikely(*current) && unlikely(*current & *virgin))

若继续比较发现ret小于2，比较当前取出的4个字节，若有不为0则将ret设置为2：

1
2
3
4
5
6
7
8
9
10
if (likely(ret < 2)) {

    u8* cur = (u8*)current;
    u8* vir = (u8*)virgin;

    if ((cur[0] && vir[0] == 0xff) || (cur[1] && vir[1] == 0xff) ||
        (cur[2] && vir[2] == 0xff) || (cur[3] && vir[3] == 0xff)) ret = 2;
    else ret = 1;

}

若virgin_map == virgin_bits且ret不为0则设置bitmap_changed为1，说明bitmap更新了：

1
if (ret && virgin_map == virgin_bits) bitmap_changed = 1;

update_bitmap_score函数分析

通过维护一个top_rated[]数组来判断当前的路径是否是”favorable”，这个”favorable”的含义就是当前测试用例覆盖了足够多的分支信息，且长度相对较小，运行时间相对较短，这样的测试用例是需要着重fuzz的。

计算测试用例的fav_factor的值：

1
u64 fav_factor = q->exec_us * q->len;//执行时间和大小的乘积

遍历分支信息记录的数组：

1
2
3
for (i = 0; i < MAP_SIZE; i++){
    ......
}

若该分支信息被记录了，就说明这个测试样例覆盖了相同的分支信息，那么就检查该分支信息的top_rate信息是否记录过，来判断该样例是否为favorable：

1
2
3
4
5
6
if (trace_bits[i]) {

       if (top_rated[i]) {
           ......
       }
}

若该样例对这个分支信息来说不是更优的就继续判断下一个分支信息：

1
if (fav_factor > top_rated[i]->exec_us * top_rated[i]->len) continue;

若当前样例对这条分支信息来说更优，则将被替换的掉的样例的tc_ref减一，将其trace_mini字段置为空：

1
2
3
4
if (!--top_rated[i]->tc_ref) {
    ck_free(top_rated[i]->trace_mini);
    top_rated[i]->trace_mini = 0;
}

将当前样例放入top_rated数组，并让其tc_ref加1：

1
2
top_rated[i] = q;
q->tc_ref++;

如果当前样例的trace_mini为空，则调用minimize_bits将当前样例中记录的累计数据丢弃：

1
2
3
4
if (!q->trace_mini) {
    q->trace_mini = ck_alloc(MAP_SIZE >> 3);
    minimize_bits(q->trace_mini, trace_bits);
}

trace_mini的组织方式：trace_mini的大小为MAP_SIZE / 8，即每个bit对应了bit_map中的一个byte；如果这个queue访问了bit_map中的一个byte(即访问了一个edge)，trace_mini中对应的bit位就置一。

设置score_changed为1：

1
score_changed = 1;

classify_counts函数分析

fuzzer对分支信息保存方式使用classify_counts处理，这里仅分析x86的情况。

fuzzer将分支信息根据分支执行次数保存在下面的bucket中：

1
2
3
4
5
6
7
8
9
10
11
12
13
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

};

某分支执行了1次，那么落入第2个bucket，其计数byte仍为1；如果某分支执行了4次，那么落入第5个bucket，其计数byte将变为8，等等。

这样就可以相对避免一些因为循环次数的微小区别，而误判为不同执行结果的情况。

参考文章：

http://rk700.github.io/2017/12/28/afl-internals/

https://www.anquanke.com/post/id/213431

https://bbs.pediy.com/thread-254705.htm