整体看的比较匆忙:(

15710161322527

Fuzz流程

  1. afl_fuzz的main函数会解析用户输入命令，检查环境变量的设置、输入输出路径、目标文件。程序定义了结构体queue_entry链表维护fuzz中使用的文件。

  2. 函数perform_dry_run() 会使用初始的测试用例进行测试，确保目标程序能够正常执行,生成初始化的queue和bitmap。

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

  4. 进入while(1)开始fuzz循环

    1
    2
    3
    4
    5
    进入循环后第一部还是 cull_queue() 对queue进行筛选
    判断queue_cur是否为空，如果是，则表示已经完成对队列的遍历，初始化相关参数，重新开始遍历队列
    fuzz_one() 函数会对queue_cur所对应文件进行fuzz，包括(跳过calibrate_case -修剪测试用例 -对用例评分 - 确定性变异或直接havoc&ssplice)
    判断是否结束，更新queue_cur和current_entry
    当队列中的所有文件都经过变异测试了，则完成一次”cycle done”。整个队列又会从第一个文件开始，再次继续进行变异

其主要流程都写在main函数里面了，我们分析一下：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//afl-fuzz.c
int main(int argc, char** argv) {
  ...
  while ((opt = getopt(argc, argv, "+i:o:f:m:t:T:dnCB:S:M:x:Q")) > 0)

    switch (opt) {
	 ...
    }

  if (optind == argc || !in_dir || !out_dir) usage(argv[0]);

  setup_signal_handlers();
  check_asan_opts();
  ...
  save_cmdline(argc, argv);
  fix_up_banner(argv[optind]);
  check_if_tty();
  get_core_count();
#ifdef HAVE_AFFINITY
  bind_to_free_cpu();
#endif /* HAVE_AFFINITY */
  check_crash_handling();
  check_cpu_governor();
  setup_post();
    
  setup_shm();
    
  init_count_class16();
  setup_dirs_fds();
  read_testcases();
  load_auto();
  pivot_inputs();
  if (extras_dir) load_extras(extras_dir);
  if (!timeout_given) find_timeout();
  detect_file_args(argv + optind + 1);
  if (!out_file) setup_stdio_file();
  check_binary(argv[optind]);
  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);

  cull_queue();

  show_init_stats();

  seek_to = find_start_position();

  write_stats_file(0, 0, 0);
  save_auto();

  if (stop_soon) goto stop_fuzzing;

  /* Woop woop woop */

  if (!not_on_tty) {
    sleep(4);
    start_time += 4000;
    if (stop_soon) goto stop_fuzzing;
  }

  while (1) {

    u8 skipped_fuzz;

    cull_queue();

    if (!queue_cur) {

      queue_cycle++;
      current_entry     = 0;
      cur_skipped_paths = 0;
      queue_cur         = queue;

      while (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. */

      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);

    }

    skipped_fuzz = fuzz_one(use_argv);

    if (!stop_soon && sync_id && !skipped_fuzz) {
      
      if (!(sync_interval_cnt++ % SYNC_INTERVAL))
        sync_fuzzers(use_argv);

    }

    if (!stop_soon && exit_1) stop_soon = 2;

    if (stop_soon) break;

    queue_cur = queue_cur->next;
    current_entry++;

  }

  if (queue_cur) show_stats();

  write_bitmap();
  write_stats_file(0, 0, 0);
  save_auto();

stop_fuzzing:

  SAYF(CURSOR_SHOW cLRD "\n\n+++ Testing aborted %s +++\n" cRST,
       stop_soon == 2 ? "programmatically" : "by user");

  /* Running for more than 30 minutes but still doing first cycle? */

  if (queue_cycle == 1 && get_cur_time() - start_time > 30 * 60 * 1000) {

    SAYF("\n" cYEL "[!] " cRST
           "Stopped during the first cycle, results may be incomplete.\n"
           "    (For info on resuming, see %s/README.)\n", doc_path);

  }

  fclose(plot_file);
  destroy_queue();
  destroy_extras();
  ck_free(target_path);
  ck_free(sync_id);

  alloc_report();

  OKF("We're done here. Have a nice day!\n");

  exit(0);
}

初始准备

get opt

第一个while循环去获取获取各种环境的设置，选项参数等等。其实就是 alf-fuzz --help里面的内容就不赘述了。

紧接着会进行一系列检测操作。

setup_signal_handlers

设置信号句柄

save_cmdline

保存命令行参数

setup_shm

设置共享内存

init_count_class16

初始化计算代码覆盖率的表单

setup_dirs_fds

初始化输出文件夹和fd

read_testcases

从输入文件夹中读取所有文件，然后将它们排队进行测试。

find_timeout

如果有-t的设置了自己的超时，那么会触发这个函数。

detect_file_args

识别参数里面有没有@@，如果有就替换为out_dir/.cur_input，如果没有就返回

dry run

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
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) {
	...
    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) {
           ...
    }

    if (q->var_behavior) WARNF("Instrumentation output varies across runs.");

    q = q->next;

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

执行 input 文件夹下的预先准备的所有 testcase，生成初始化的 queue 和 bitmap。这只对初始输入执行一次，所以叫：dry run。

其实就是简单跑一遍所有的 testcase，然后看看有没有什么异常，比如：crash，无法触发新的路径，以确保样本和 target 的正确性。

然后这里面比较关键的函数是 res = calibrate_case(argv, q, use_mem, 0, 1);

calibrate_case

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
static u8 calibrate_case(char** argv, struct queue_entry* q, u8* use_mem, u32 handicap, u8 from_queue) {
  static u8 first_trace[MAP_SIZE];

  u8  fault = 0, new_bits = 0, var_detected = 0,
      first_run = (q->exec_cksum == 0);

  u64 start_us, stop_us;

  s32 old_sc = stage_cur, old_sm = stage_max;
  u32 use_tmout = exec_tmout;
  u8* old_sn = stage_name;

  /* Be a bit more generous about timeouts when resuming sessions, or when
     trying to calibrate already-added finds. This helps avoid trouble due
     to intermittent latency. */

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

  q->cal_failed++;

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

  /* Make sure the forkserver is up before we do anything, and let's not
     count its spin-up time toward binary calibration. */

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

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

  start_us = get_cur_time_us();

  for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    u32 cksum;

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

    write_to_testcase(use_mem, q->len);

    fault = run_target(argv, use_tmout);

    /* stop_soon is set by the handler for Ctrl+C. When it's pressed,
       we want to bail out quickly. */

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

    if (!dumb_mode && !stage_cur && !count_bytes(trace_bits)) {
      fault = FAULT_NOINST;
      goto abort_calibration;
    }

    cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

    if (q->exec_cksum != cksum) {

      u8 hnb = has_new_bits(virgin_bits);
      if (hnb > new_bits) new_bits = hnb;

      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;

          }

        }

        var_detected = 1;

      } else {

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

      }

    }

  }

  stop_us = get_cur_time_us();

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

  /* OK, let's collect some stats about the performance of this test case.
     This is used for fuzzing air time calculations in calculate_score(). */

  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);

  /* If this case didn't result in new output from the instrumentation, tell
     parent. This is a non-critical problem, but something to warn the user
     about. */

  if (!dumb_mode && first_run && !fault && !new_bits) fault = FAULT_NOBITS;

abort_calibration:

  if (new_bits == 2 && !q->has_new_cov) {
    q->has_new_cov = 1;
    queued_with_cov++;
  }

  /* Mark variable paths. */

  if (var_detected) {

    var_byte_count = count_bytes(var_bytes);

    if (!q->var_behavior) {
      mark_as_variable(q);
      queued_variable++;
    }

  }

  stage_name = old_sn;
  stage_cur  = old_sc;
  stage_max  = old_sm;

  if (!first_run) show_stats();

  return fault;

}

calibrate_case首先也会进行一些初始化操作，比较重要的是要检查一下 fork_server是否已经初始化，如果没有则先初始化 fork_server。每个测试样例都会执行3次或8次，而不是简单的执行一次，执行多次并记录tuple的信息。具体取决于是否快速校准

write_to_testcase() ：将测试样例写入文件。如果 use_stdin 被清除了，那么取消旧文件链接并创建一个新文件。否则，prog_in_fd 将被缩短。将 testcase 写入到文件中去。

run_target()：运行程序，见下文。

hash32(trace_bits, MAP_SIZE, HASH_CONST)：计算trace_bits的checksums，即当前tuple的hash值

if...else：如果是第一次运行则记录cksum的值，下次将该次cksum的值和上一次进行比较，如果相同则忽略，如果不同则调用has_new_bits()和我们的总表virgin_bits 对比。

后续进行一些信息的记录

update_bitmap_score(q) ：对这个测试用例的每一个byte进行排序，用一个top_rate[]来维护它的最佳入口。维护完成之后，我们这个函数在

总结：calibratecase该函数主要用途是init_forkserver，检查case的可用性，用update_bitmap_score进行初始的byte排序。

init_forkserver()

记录在上一篇文章了

https://0xfocu5.github.io/posts/53fcd800/

run_target()

memset(trace_bits, 0, MAP_SIZE)：清空共享内存

  • 如果是dumb模式：如果dumb_mode等于1，且no_forkserver，则直接fork出一个子进程，然后让子进程execv去执行target，如果execv执行失败，则向trace_bits写入EXEC_FAIL_SIG

  • 否则，就向控制管道写入prev_timed_out的值，命令Fork server开始fork出一个子进程进行fuzz，然后从状态管道读取fork server返回的fork出的子进程的ID到child_pid

接下来无论那种模式，如果超过用户所设置的超时时间限制，则杀死程序，并设置child_timed_out为1。

target执行结束，如果是dumb_mode，target执行结束的状态码将直接保存到status中，如果不是dumb_mode，则从状态管道中读取target执行结束的状态码。然后调用classify_counts((u64 *) trace_bits)去更新代码覆盖率。

has_new_bits()

检查当前执行路径是否为表带来了新内容。更新原始位以反映发现。如果唯一更改的是特定元组的命中计数，则返回1;如果有新的元组出现，则返回2。更新映射，因此后续调用将始终返回0。
这个函数是在相当大的缓冲区上的每个exec()之后调用的，因此它需要非常快。我们以32位和64位的方式做这件事。因此它需要非常快。我们以32位和64位的方式做这件事。

update_bitmap_score

当碰到一条新路径时，我们将看这条路径是否比别的存在路径更加有利。“favorables”的目的是拥有一组最小的路径集（testcase）来触发到目前为止在位图中看到的所有位，并专注于fuzz这些testcase，而牺牲了其余的。这个过程的第一步是bitmap中的每个字节维护一个top_rating[]条目列表。

  • 首先计算出这个case的fav_factor，计算方法是q->exec_us * q->len即执行时间和样例大小的乘积，以这两个指标来衡量权重。

  • 遍历trace_bits数组，如果该字节的值不为0，则代表这是已经被覆盖到的path

    然后检查对应于这个path的top_rated是否存在

    • static struct queue_entry *top_rated[MAP_SIZE]; /* Top entries for bitmap bytes */

    • 如果存在，就比较fav_factor > top_rated[i]->exec_us * top_rated[i]->len，即比较执行时间和样例大小的乘积，哪个更小。

      • 如果top_rated[i]的更小，则代表top_rated[i]的更优，不做任何处理，继续遍历下一个path。
      • 如果q更小，就将top_rated[i]原先对应的queue entry的tc_ref字段减一，并将其trace_mini字段置为空。
      • u8 *trace_mini; /* Trace bytes, if kept */
      • u32 tc_ref; /* Trace bytes ref count */

    • 然后设置top_rated[i]为q，即当前case，然后将其tc_ref的值加一

    • 如果q->trace_mini为空，则将trace_bits经过minimize_bits压缩，然后存到trace_mini字段里

    • 设置score_changed为1.

fuzz循环

cull_queue()

精简队列。

为了优化模糊工作，AFL使用快速算法定期重新评估队列，该算法选择一个较小的测试用例子集，该子集仍覆盖到目前为止所看到的每个元组，并且其特征使它们对Fuzzing特别有利。该算法通过为每个队列条目分配与其执行延迟和文件大小成正比的分数来工作;然后为每个tuples选择最低得分候选者。
cull_queue()遍历top_rated[]中的queue，然后提取出发现新的edge的entry，并标记为favored，使得在下次遍历queue时，这些entry能获得更多执行fuzz的机会。
这里本质上采用了贪婪算法，如果top_rated[i]存在，且对应temp_v[]中对应bit位还没抹去，即这一轮选出的queue还没覆盖bit_map[i]对应的边，则取出这个top_rated[i]。抹去temp_v中top_rated[i]能访问到的位。最后将这个top_rated[i]标记为favored,如果这个queue还没fuzzed，pending_favored++.

准备工作

  1. static void show_init_stats(void)在处理输入目录的末尾显示快速统计信息，并添加一系列警告。
    一些校准的东西也在这里结束了，还有一些硬编码的常量。也许最终会清理干净。
  2. static u32 find_start_position(void)在恢复时，尝试找到要开始的队列位置。只有在恢复时，以及在可以找到原始fuzzer_stats时，这才有意义。
  3. static void write_stats_file(double bitmap_cvg, double stability, double eps)更新一些状态稳健。
  4. static void save_auto(void)自动更新token，目录/queue/.state/autoextras/auto。
  5. 循环开始前，调用cull_queue() 对queue进行筛选

while(1)

  1. 判断queue_cur是否为空，如果是，则表示已经完成对队列的遍历，初始化相关参数，重新开始遍历队列
  2. 找到queue入口的testcase，seek_to = find_start_position()；直接跳到该testcase
  3. 如果一整个队列循环都没新发现，尝试重组策略。
  4. 调用关键函数fuzz_one()对该testcase进行fuzz。fuzz_one()函数参见3.4。
  5. 上面的变异完成后，AFL会对文件队列的下一个进行变异处理。当队列中的全部文件都变异测试后，就完成了一个”cycle”，这个就是AFL状态栏右上角的”cycles done”。而正如cycle的意思所说，整个队列又会从第一个文件开始，再次进行变异，不过与第一次变异不同的是，这一次就不需要再进行deterministic fuzzing了。如果用户不停止AFL，那么seed文件将会一遍遍的变异下去。

fuzz_one()

static u8 fuzz_one_original(char** argv)从队列中取出当前testcase并模糊。这个函数太长了…如果fuzzed成功，返回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。

  2. 假如当前项有校准错误，并且校准错误次数小于3次，那么就用calibrate_case进行测试。

  3. 如果测试用例没有修剪过，那么调用函数trim_case对测试用例进行修剪。

  4. 修剪完毕之后，使用calculate_score对每个测试用例进行打分。

  5. 如果该queue已经完成deterministic阶段，则直接跳到havoc阶段

  6. deterministic阶段变异4个stage，变异过程中会多次调用函数

    1
    common_fuzz_stuff

    保存interesting 的种子：

    bitflip，按位翻转，1变为0，0变为1
    arithmetic，整数加/减算术运算
    interest，把一些特殊内容替换到原文件中
    dictionary，把自动生成或用户提供的token替换/插入到原文件中

  7. havoc，中文意思是“大破坏”，此阶段会对原文件进行大量变异。

  8. splice，中文意思是“绞接”，此阶段会将两个文件拼接起来得到一个新的文件。

  9. 该 testcase完成。 The

参考

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

https://eternalsakura13.com/2020/08/23/afl/

https://hicookie.me/2019/09/18/AFL-Learning/

https://xz.aliyun.com/t/4628#toc-12