afl-fuzz.c细节分析之主循环分析

afl-fuzz.c细节分析之主循环分析

cull_queue阶段

afl的dry run环节结束后就会进入cull_queue()：

1
cull_queue();

cull_queue函数分析

该函数用于精简队列。

若处于dumb模式或者没有发现更优的样例就返回：

1
if (dumb_mode || !score_changed) return;

将标记位score_changed改为0：

1
score_changed = 0;

设置temp_v数组中的值为0xff：

1
memset(temp_v, 255, MAP_SIZE >> 3);

设置queued_favored和pending_favored为0：

1
2
queued_favored  = 0;
pending_favored = 0;

遍历queue，将所有样例的favored设置为0：

1
2
3
4
5
6
q = queue;

while (q) {
    q->favored = 0;
    q = q->next;
}

若对某条分支信息，top_rated[i]存在（存在favorable的样例），且在temp_v中对应的bit被置1：

1
2
3
4
for (i = 0; i < MAP_SIZE; i++)
   if (top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {
       ......
   }

trace_mini记录了覆盖的分支信息，这里将temp_v中的内容与其进行与操作，消除掉覆盖到的path，将对应的bit置为0：

1
2
3
while (j--) 
        if (top_rated[i]->trace_mini[j])
          temp_v[j] &= ~top_rated[i]->trace_mini[j];

有关这段难顶的字节运算与莫名其妙的标识符，这个文章解释的很好，实际上就是一个贪心算法，目的是为了择出队列中第一个最优的覆盖足够分支的样例，文章对这段代码解释摘要如下：

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

设置top_rated[i]->favored为1，queued_favored加1：

1
2
top_rated[i]->favored = 1;
queued_favored++;

遍历队列，将不是favored的样例标记成redundant_edges，存放到/queue/.state/redundant_edges/文件夹下。

一些准备工作

这部分在第一篇笔记中记录过了。

  1. 显示快速统计信息以及警告，处理一些硬编码相关的工作等。
1
show_init_stats();
  1. 恢复时找到要开始的队列位置。
1
seek_to = find_start_position();
  1. 更新一些状态。
1
write_stats_file(0, 0, 0);
  1. 自动更新token。
1
save_auto();
  1. ctrl+C就退出。
1
if (stop_soon) goto stop_fuzzing;
  1. 不在TTy退出。
1
2
3
4
5
if (!not_on_tty) {
    sleep(4);
    start_time += 4000;
    if (stop_soon) goto stop_fuzzing;
}

然后进入while(1)的循环。

while (1)循环

首先精简队列：

1
cull_queue();

若queue_cur为0，则说明当前队列已经遍历完毕，进行参数的重新设置，重新开始遍历队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (!queue_cur) {

        queue_cycle++;//所有的queue执行的次数加1
        current_entry     = 0;//设置遍历id为0
        cur_skipped_paths = 0;//设置跳过fuzz的样例数量为0
        queue_cur         = queue;//设置当前样例为队列首个元素

        //若seek_to不为0，则说明是恢复fuzz的情况，找到seek_to对应的样例开始fuzz
        while (seek_to) {
            current_entry++;
            seek_to--;
            queue_cur = queue_cur->next;

            ......
        }

还是上述if分支。

刷新展示信息：

1
show_stats();

不在tty就进行信息展示：

1
2
3
4
if (not_on_tty) {
    ACTF("Entering queue cycle %llu.", queue_cycle);
    fflush(stdout);
}

若queue里的样例数与之前的一样，则说明没有发现新的样例（分支信息），则需要对样例进行重组：

1
2
3
4
5
if (queued_paths == prev_queued) {

    if (use_splicing) cycles_wo_finds++; else use_splicing = 1;

} else cycles_wo_finds = 0;

将样例数量进行更新：

1
prev_queued = queued_paths;

设置了AFL_IMPORT_FIRST且并行进行fuzzer，则会从其他fuzzer中择取样例：

1
2
if (sync_id && queue_cycle == 1 && getenv("AFL_IMPORT_FIRST"))
    sync_fuzzers(use_argv);

若queue_cur不为空，使用fuzz_one函数对queue_cur进行fuzz：

1
skipped_fuzz = fuzz_one(use_argv);

fuzz_one函数

从队列中获取当前样例，对其进行fuzz。如果fuzz成功则返回0，如果跳过或退出则返回1。

若pending_favored不为0，当前样例被fuzz过了或者不是favored的，有99%概率直接返回1：

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

    /* If we have any favored, non-fuzzed new arrivals in the queue,
       possibly skip to them at the expense of already-fuzzed or non-favored
       cases. */

    if ((queue_cur->was_fuzzed || !queue_cur->favored) &&
        UR(100) < SKIP_TO_NEW_PROB) return 1;

}

若pending_favored为0，不是dumb mode，当前样例不是favored，队列中样例总数大于10，则进一步判断循环次数是否大于1且当前样例未被fuzz过，若是，有99%概率直接返回1，不是有95%概率返回1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
else if (!dumb_mode && !queue_cur->favored && queued_paths > 10) {

    /* Otherwise, still possibly skip non-favored cases, albeit less often.
       The odds of skipping stuff are higher for already-fuzzed inputs and
       lower for never-fuzzed entries. */

    if (queue_cycle > 1 && !queue_cur->was_fuzzed) {

      if (UR(100) < SKIP_NFAV_NEW_PROB) return 1;

    } else {

      if (UR(100) < SKIP_NFAV_OLD_PROB) return 1;

    }

}

tty相关处理：

1
2
3
4
5
if (not_on_tty) {
    ACTF("Fuzzing test case #%u (%u total, %llu uniq crashes found)...",
         current_entry, queued_paths, unique_crashes);
    fflush(stdout);
}

打开队列中正在处理的样例：

1
fd = open(queue_cur->fname, O_RDONLY);

获取样例长度：

1
len = queue_cur->len;

将样例映射到内存中，地址赋值给in_buf和orig_in：

1
orig_in = in_buf = mmap(0, len, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);

失败显示信息：

1
if (orig_in == MAP_FAILED) PFATAL("Unable to mmap '%s'", queue_cur->fname);

分配大小为len的内存，地址赋值给out_buf：

1
out_buf = ck_alloc_nozero(len);

初始化运行超过时间的样例个数为0：

1
subseq_tmouts = 0;

初始化当前样例的cur_depth：

1
cur_depth = queue_cur->depth;

CALIBRATION阶段

若样例标记为了校验失败了，且校验次数小于CAL_CHANCES(3)，则再次校验，否则就根据是否即将关闭fuzzer或者是否处于crash_mode来判断是否抛弃样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (queue_cur->cal_failed) {

    u8 res = FAULT_TMOUT;

    if (queue_cur->cal_failed < CAL_CHANCES) {

      res = calibrate_case(argv, queue_cur, in_buf, queue_cycle - 1, 0);

      if (res == FAULT_ERROR)
        FATAL("Unable to execute target application");

    }

    if (stop_soon || res != crash_mode) {
      cur_skipped_paths++;
      goto abandon_entry;
    }

}

TRIMMING阶段

若该样例没有被trim过且不处于dumb模式，则对其进行修剪，然后设置trim_done为1，以防止二次修剪：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (!dumb_mode && !queue_cur->trim_done) {

    u8 res = trim_case(argv, queue_cur, in_buf);

    if (res == FAULT_ERROR)
      FATAL("Unable to execute target application");

    if (stop_soon) {
      cur_skipped_paths++;
      goto abandon_entry;
    }

    /* Don't retry trimming, even if it failed. */

    queue_cur->trim_done = 1;

    if (len != queue_cur->len) len = queue_cur->len;

}

将in_buf中len个字节拷贝到out_buf中：

1
memcpy(out_buf, in_buf, len);
trim_case函数分析

若样例长度小于5字节则不需要修剪：

1
if (q->len < 5) return 0;

设置stage_name为tmp，将修建的长度加上样例长度：

1
2
stage_name = tmp;
bytes_trim_in += q->len;

将长度向上取整2的次方，记录为len_p2：

1
len_p2 = next_p2(q->len);

设置remove_len为len_p2*1/16与4中较大的值，即起始的每次修剪的长度：

1
remove_len = MAX(len_p2 / TRIM_START_STEPS, TRIM_MIN_BYTES);

除非remove_len小于len_p2*1/1024或者4，否则进行循环：

1
2
3
while (remove_len >= MAX(len_p2 / TRIM_END_STEPS, TRIM_MIN_BYTES)) {
    ......
}

循环内容如下。

记录阶段信息：

1
sprintf(tmp, "trim %s/%s", DI(remove_len), DI(remove_len));

当remove_pos < q->len不断裁剪样例，且测试样例：

1
2
3
while (remove_pos < q->len) {
    ......
}

从内存中in_buf偏移为remove_pos开始跳过remove_len个字节，写q->len个字节到input文件夹中：

1
write_with_gap(in_buf, q->len, remove_pos, trim_avail);

然后运行样例：

1
fault = run_target(argv, exec_tmout);

trim_exec计数器加1：

1
trim_execs++;

计算校验和：

1
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

若修剪了以后对其覆盖信息没有影响则就永久修剪：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if (cksum == q->exec_cksum) {

        u32 move_tail = q->len - remove_pos - trim_avail;

        q->len -= trim_avail;
        len_p2  = next_p2(q->len);

        memmove(in_buf + remove_pos, in_buf + remove_pos + trim_avail, 
                move_tail);

        /* Let's save a clean trace, which will be needed by
           update_bitmap_score once we're done with the trimming stuff. */

        if (!needs_write) {

          needs_write = 1;
          memcpy(clean_trace, trace_bits, MAP_SIZE);

        }

}

若不相等则恢复修建部分：

1
else remove_pos += remove_len;

展示信息，计数器stage_cur加1：

1
2
if (!(trim_exec++ % stats_update_freq)) show_stats();
    stage_cur++;

循环的最后增加步长：

1
remove_len >>= 1;

对in_buf做的改变也需要体现在文件上，主要根据needs_write标记改变：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (needs_write) {

    s32 fd;

    unlink(q->fname); /* ignore errors */

    fd = open(q->fname, O_WRONLY | O_CREAT | O_EXCL, 0600);

    if (fd < 0) PFATAL("Unable to create '%s'", q->fname);

    ck_write(fd, in_buf, q->len, q->fname);
    close(fd);

    memcpy(trace_bits, clean_trace, MAP_SIZE);
    update_bitmap_score(q);

}

PERFORMANCE SCORE阶段

计算queue_cur分数并保存：

1
orig_perf = perf_score = calculate_score(queue_cur);

若跳过确定性变异就直接开始havoc：

1
2
3
4
5
if (skip_deterministic || queue_cur->was_fuzzed || queue_cur->passed_det)
    goto havoc_stage;

if (master_max && (queue_cur->exec_cksum % master_max) != master_id - 1)
    goto havoc_stage;

设置doing_det为1：

1
doing_det = 1;
calculate_score函数

根据queue entry的执行速度、覆盖到的path数和路径深度来评估出一个得分，这个得分perf_score在后面havoc的时候使用。

前面是根据上述的一些定义算分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (q->exec_us * 0.1 > avg_exec_us) perf_score = 10;
else if (q->exec_us * 0.25 > avg_exec_us) perf_score = 25;
else if (q->exec_us * 0.5 > avg_exec_us) perf_score = 50;
else if (q->exec_us * 0.75 > avg_exec_us) perf_score = 75;
else if (q->exec_us * 4 < avg_exec_us) perf_score = 300;
else if (q->exec_us * 3 < avg_exec_us) perf_score = 200;
else if (q->exec_us * 2 < avg_exec_us) perf_score = 150;

/* Adjust score based on bitmap size. The working theory is that better
    coverage translates to better targets. Multiplier from 0.25x to 3x. */

if (q->bitmap_size * 0.3 > avg_bitmap_size) perf_score *= 3;
else if (q->bitmap_size * 0.5 > avg_bitmap_size) perf_score *= 2;
else if (q->bitmap_size * 0.75 > avg_bitmap_size) perf_score *= 1.5;
else if (q->bitmap_size * 3 < avg_bitmap_size) perf_score *= 0.25;
else if (q->bitmap_size * 2 < avg_bitmap_size) perf_score *= 0.5;
else if (q->bitmap_size * 1.5 < avg_bitmap_size) perf_score *= 0.75;

......

根据depth算分：

1
2
3
4
5
6
7
8
9
switch (q->depth) {

    case 0 ... 3:   break;
    case 4 ... 7:   perf_score *= 2; break;
    case 8 ... 13:  perf_score *= 3; break;
    case 14 ... 25: perf_score *= 4; break;
    default:        perf_score *= 5;

}

有关深度的一些说明：

每次add_to_queue时将cur_depth加1赋值给depth：

1
q->depth        = cur_depth + 1;

cur_depth初始化时为1。

所以每次有新的样例加入queue就depth加1。

SIMPLE BITFLIP (+dictionary construction) 阶段

比特翻转阶段。

这里就是不断使用下面的宏，对连续的1，2，4，8，16位：

1
2
3
4
5
#define FLIP_BIT(_ar, _b) do { \
    u8* _arf = (u8*)(_ar); \
    u32 _bf = (_b); \
    _arf[(_bf) >> 3] ^= (128 >> ((_bf) & 7)); \
  } while (0)

这里((_bf) & 7)可以得到{0,1,2,3,4,5,6,7}(_bf > 7)的循环数组，128进行移位操作后得到了以下这些数：

1
2
3
4
5
6
7
8
1000 0000
0100 0000
0010 0000
0001 0000
0000 1000
0000 0100
0000 0010
0000 0001

arf[(_bf)>>3]与上面这些数进行抑或操作相当于翻转了上面这些数中为1位置的比特。

bitflip 1/1环节设定stage_max为len << 3：

1
2
3
stage_short = "flip1";
stage_max   = len << 3;
stage_name  = "bitflip 1/1";

_ar赋值为out_buf，_b赋值为[0,len << 3)：

1
2
3
4
5
6
7
8
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    stage_cur_byte = stage_cur >> 3;

    FLIP_BIT(out_buf, stage_cur);

    ......
}

这里进行的是对out_buf中每个比特的翻转，循环中的操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
将第一个字节的第一个比特（从左至右数的第一个）翻转；
将第一个字节的第二个比特翻转；
将第一个字节的第三个比特翻转；
将第一个字节的第四个比特翻转；
将第一个字节的第五个比特翻转；
将第一个字节的第六个比特翻转；
将第一个字节的第七个比特翻转；

将第二个字节的第一个比特翻转；
将第二个字节的第二个比特翻转；
将第二个字节的第三个比特翻转；
将第二个字节的第四个比特翻转；
将第二个字节的第五个比特翻转；
将第二个字节的第六个比特翻转；
将第二个字节的第七个比特翻转；

......

将第(len)个字节的第七个比特翻转；

翻转完成进行一轮common_fuzz_stuff操作：

1
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

然后翻转回来：

1
FLIP_BIT(out_buf, stage_cur);

在进行单个比特翻转时，还进行token的处理，这里token的含义就是一段连续的字节，若改变了之后路径与原始路径相比发生了变化，而这些改变后产生的路径都一样，那就把这段字节成为token：

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
if (!dumb_mode && (stage_cur & 7) == 7) {

      u32 cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

      if (stage_cur == stage_max - 1 && cksum == prev_cksum) {

        /* If at end of file and we are still collecting a string, grab the
           final character and force output. */

        if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];
        a_len++;

        if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)
          maybe_add_auto(a_collect, a_len);

      } else if (cksum != prev_cksum) {

        /* Otherwise, if the checksum has changed, see if we have something
           worthwhile queued up, and collect that if the answer is yes. */

        if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)
          maybe_add_auto(a_collect, a_len);

        a_len = 0;
        prev_cksum = cksum;

    }

    if (cksum != queue_cur->exec_cksum) {

        if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];        
        a_len++;

      }

}

这段解释这篇文章讲的非常好：

比如对于SQL的SELECT *，如果SELECT被破坏，则肯定和正确的路径不一致，而被破坏之后的路径却肯定是一样的，比如AELECT和SBLECT，显然都是无意义的，而只有不破坏token，才有可能出现和原始执行路径一样的结果，所以AFL在这里就是在猜解关键字token。token默认最小是3，最大是32，每次发现新token时，通过maybe_add_auto添加到a_extras数组里。

new_hit_cnt赋值为queued_path + unique_crashes：

1
new_hit_cnt = queued_paths + unique_crashes;

统计得到的有效样例以及循环次数：

1
2
stage_finds[STAGE_FLIP1]  += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP1] += stage_max;

bitflip 2/1环节设定stage_max为(len << 3) - 1：

1
2
3
stage_name  = "bitflip 2/1";
stage_short = "flip2";
stage_max   = (len << 3) - 1;

连续翻转两个比特位：

1
2
3
4
5
6
7
8
9
10
11
12
13
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    stage_cur_byte = stage_cur >> 3;

    FLIP_BIT(out_buf, stage_cur);
    FLIP_BIT(out_buf, stage_cur + 1);

    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

    FLIP_BIT(out_buf, stage_cur);
    FLIP_BIT(out_buf, stage_cur + 1);

}

记录信息：

1
2
3
4
new_hit_cnt = queued_paths + unique_crashes;

stage_finds[STAGE_FLIP2]  += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP2] += stage_max;

bitflip 4/1环节是连续翻转四个比特位，记录信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    stage_cur_byte = stage_cur >> 3;

    FLIP_BIT(out_buf, stage_cur);
    FLIP_BIT(out_buf, stage_cur + 1);
    FLIP_BIT(out_buf, stage_cur + 2);
    FLIP_BIT(out_buf, stage_cur + 3);

    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

    FLIP_BIT(out_buf, stage_cur);
    FLIP_BIT(out_buf, stage_cur + 1);
    FLIP_BIT(out_buf, stage_cur + 2);
    FLIP_BIT(out_buf, stage_cur + 3);

}

设置effector map的前置工作：

1
2
3
4
5
6
7
8
9
10
11
12
  /* Effector map setup. These macros calculate:

     EFF_APOS      - position of a particular file offset in the map.文件偏移
     EFF_ALEN      - length of a map with a particular number of bytes.特殊字符的长度
     EFF_SPAN_ALEN - map span for a sequence of bytes.一个字节序列的映射

   */

#define EFF_APOS(_p)          ((_p) >> EFF_MAP_SCALE2)
#define EFF_REM(_x)           ((_x) & ((1 << EFF_MAP_SCALE2) - 1))
#define EFF_ALEN(_l)          (EFF_APOS(_l) + !!EFF_REM(_l))
#define EFF_SPAN_ALEN(_p, _l) (EFF_APOS((_p) + (_l) - 1) - EFF_APOS(_p) + 1)

初始化effector map：

1
2
eff_map    = ck_alloc(EFF_ALEN(len));
eff_map[0] = 1;

由于8比特翻转实则就是单字节翻转，所以可以通过一个启发式判断节省执行资源：

这样做的逻辑是：如果一个byte完全翻转，都无法带来执行路径的变化，那么这个byte很有可能是属于”data”，而非”metadata”（例如size, flag等），对整个fuzzing的意义不大。所以，在随后的一些变异中，会参考effector map，跳过那些“无效”的byte，从而节省了执行资源。

这里判断是否执行路径变化的方式就是检查校验和：

1
2
3
4
if (cksum != queue_cur->exec_cksum) {
    eff_map[EFF_APOS(stage_cur)] = 1;
    eff_cnt++;
}

若afl发现文件小于128字节，那么就认为整个文件都是有效的；若afl发现文件中90%的字节都是有效的，那么也认为整个文件都是有效的：

1
2
3
4
5
6
7
8
9
10
11
12
if (eff_cnt != EFF_ALEN(len) &&
    eff_cnt * 100 / EFF_ALEN(len) > EFF_MAX_PERC) {

    memset(eff_map, 1, EFF_ALEN(len));

    blocks_eff_select += EFF_ALEN(len);

} else {

    blocks_eff_select += eff_cnt;

}

这里以及之后的字节翻转就比较简单，直接和0xFF抑或即可，然后使用common_fuzz_stuff跑一遍，最后再翻转回来：

1
2
3
4
5
6
7
8
9
10
11
12
13
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    stage_cur_byte = stage_cur;

    out_buf[stage_cur] ^= 0xFF;

    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

    ......//effector map的处理

    out_buf[stage_cur] ^= 0xFF;

}

双字节翻转是和0xFFFF抑或：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for (i = 0; i < len - 1; i++) {

    /* Let's consult the effector map... */

    if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {
      stage_max--;
      continue;
    }

    stage_cur_byte = i;

    *(u16*)(out_buf + i) ^= 0xFFFF;

    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
    stage_cur++;

    *(u16*)(out_buf + i) ^= 0xFFFF;


}

四字节翻转是和0xFFFFFFFF抑或：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (i = 0; i < len - 3; i++) {

    /* Let's consult the effector map... */
    if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)] &&
        !eff_map[EFF_APOS(i + 2)] && !eff_map[EFF_APOS(i + 3)]) {
        stage_max--;
        continue;
    }

    stage_cur_byte = i;

    *(u32*)(out_buf + i) ^= 0xFFFFFFFF;

    if (common`_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
    stage_cur++;

    *(u32*)(out_buf + i) ^= 0xFFFFFFFF;

}

比特翻转环节执行完毕后进入数学运算环节。

ARITHMETIC INC/DEC阶段

使用数学运算的方式分别对文件每1/2/4个字节做加或者减的运算。

加或减的上限由宏定义限制，然后在每个计算方式中得出：

1
2
3
4
5
6
7
8
9
10
#define ARITH_MAX           35

//1 byte
stage_max   = 2 * len * ARITH_MAX;

//2 byte
stage_max   = 4 * (len - 1) * ARITH_MAX;

//4 byte
stage_max   = 4 * (len - 3) * ARITH_MAX;

单字节数学计算包括加和减：

1
2
3
4
5
6
7
8
9
10
11
12
13
//加
stage_cur_val = j;
out_buf[i] = orig + j;

if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;

//减
stage_cur_val = -j;
out_buf[i] = orig - j;

if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;

2字节的数学计算包括加和减（这里是小端）：

1
2
3
4
5
6
7
8
9
10
11
stage_cur_val = j;
*(u16*)(out_buf + i) = orig + j;

if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;

stage_cur_val = -j;
*(u16*)(out_buf + i) = orig - j;

if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;

还对大端的情况进行了设置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if ((orig >> 8) + j > 0xff && !could_be_bitflip(r3)) {

    stage_cur_val = j;
    *(u16*)(out_buf + i) = SWAP16(SWAP16(orig) + j);

    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
    stage_cur++;

} else stage_max--;

if ((orig >> 8) < j && !could_be_bitflip(r4)) {

    stage_cur_val = -j;
    *(u16*)(out_buf + i) = SWAP16(SWAP16(orig) - j);

    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
    stage_cur++;

}else stage_max--;

四字节数学计算的与2字节相同，也设置了对大小端的情况区分：

1
2
3
4
5
6
7
if ((orig & 0xffff) + j > 0xffff && !could_be_bitflip(r1)) {
    ......
}

if ((SWAP32(orig) & 0xffff) + j > 0xffff && !could_be_bitflip(r3)) {
    ......
}

此外，AFL还会智能地跳过某些arithmetic变异。第一种情况就是前面提到的effector map：如果一个整数的所有bytes都被判断为”无效”，那么就跳过对整数的变异。第二种情况是之前bitflip已经生成过的变异：如果加/减某个数后，其效果与之前的某种bitflip相同，那么这次变异肯定在上一个阶段已经执行过了，此次便不会再执行。

INTERESTING VALUES阶段

特殊值替换阶段，对每1/2/4个字节替换为”interesting value”。

插入的内容定义在了config.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
#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  */

#define INTERESTING_16 \
  -32768,        /* Overflow signed 16-bit when decremented */ \
  -129,          /* Overflow signed 8-bit                   */ \
   128,          /* Overflow signed 8-bit                   */ \
   255,          /* Overflow unsig 8-bit when incremented   */ \
   256,          /* Overflow unsig 8-bit                    */ \
   512,          /* One-off with common buffer size         */ \
   1000,         /* One-off with common buffer size         */ \
   1024,         /* One-off with common buffer size         */ \
   4096,         /* One-off with common buffer size         */ \
   32767         /* Overflow signed 16-bit when incremented */

#define INTERESTING_32 \
  -2147483648LL, /* Overflow signed 32-bit when decremented */ \
  -100663046,    /* Large negative number (endian-agnostic) */ \
  -32769,        /* Overflow signed 16-bit                  */ \
   32768,        /* Overflow signed 16-bit                  */ \
   65535,        /* Overflow unsig 16-bit when incremented  */ \
   65536,        /* Overflow unsig 16 bit                   */ \
   100663045,    /* Large positive number (endian-agnostic) */ \
   2147483647    /* Overflow signed 32-bit when incremented */

这里就分析下1字节的情况，即插入interesting_8。

循环内首先还是检查effector map中对应的字节为1/0，跳过无效的byte：

1
2
3
4
if (!eff_map[EFF_APOS(i)]) {
      stage_max -= sizeof(interesting_8);
      continue;
 }

跳过与前两个阶段变异后覆盖路径重合的字节：

1
2
3
4
5
if (could_be_bitflip(orig ^ (u8)interesting_8[j]) 
    ||could_be_arith(orig, (u8)interesting_8[j], 1)) {
    stage_max--;
    continue;
}

替换字节后common fuzz：

1
2
3
out_buf[i] = interesting_8[j];

if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

替换回来，stage_cur加1：

1
2
out_buf[i] = orig;
stage_cur++;

统计期间获得的crash：

1
new_hit_cnt = queued_paths + unique_crashes;

后面的2字节和4字节的特殊值替换的变异方式与上述的1字节替换类似。

DICTIONARY STUFF

确定性变异最后的阶段就是字典阶段，将特殊token插入样例。

该阶段分为以下几个小阶段：

1
2
3
user extras (over)，从头开始，将用户提供的tokens依次替换到原文件中
user extras (insert)，从头开始，将用户提供的tokens依次插入到原文件中
auto extras (over)，从头开始，将自动检测的tokens依次替换到原文件中

token存储在了extra数组中，由load_extras_file函数将用户自定义的token导入，用户token相关阶段开始会检查用户是否使用-x进行字典的设置，没有就会跳过用户token阶段：

1
if (!extras_cnt) goto skip_user_extras;
user extras (over)

循环内部首先对token数量进行判断，若token的数量大于MAX_DET_EXTRAS，则会根据概率插入一定数量的token，若样例没有空间插入这些token，就会跳过token：

1
2
3
4
5
6
7
8
9
if ((extras_cnt > MAX_DET_EXTRAS && UR(extras_cnt) >= MAX_DET_EXTRAS) ||
          extras[j].len > len - i ||
          !memcmp(extras[j].data, out_buf + i, extras[j].len) ||
          !memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, extras[j].len))) {

    stage_max--;
    continue;

}

向样例头部开始替换token，然后common fuzz：

1
2
3
memcpy(out_buf + i, extras[j].data, last_len);

if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
user extras (insert)

这里只会检查添加token后样例长度大于预设的最大值：

1
2
3
4
 if (len + extras[j].len > MAX_FILE) {
    stage_max--; 
    continue;
}

插入token然后common fuzz：

1
2
3
4
5
6
7
8
9
memcpy(ex_tmp + i, extras[j].data, extras[j].len);

/* Copy tail */
memcpy(ex_tmp + i + extras[j].len, out_buf + i, len - i);

if (common_fuzz_stuff(argv, ex_tmp, len + extras[j].len)) {
    ck_free(ex_tmp);
    goto abandon_entry;
}
auto extras (over)

该阶段也是跳过用户token进入的阶段，且若没有token也会跳过该阶段：

1
2
3
4
5
6
7
8
9
skip_user_extras:

if (!a_extras_cnt) goto skip_extras;

stage_name  = "auto extras (over)";
stage_short = "ext_AO";
stage_cur   = 0;
stage_max   = MIN(a_extras_cnt, USE_AUTO_EXTRAS) * len;

该阶段与用户token覆盖阶段相似，不过插入的自动检测出的token，插入后还是会commom fuzz：

1
2
3
memcpy(out_buf + i, a_extras[j].data, last_len);

if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

至此确定性变异阶段结束，进入havoc阶段。

RANDOM HAVOC

以下摘自：http://rk700.github.io/2018/01/04/afl-mutations/

对于非dumb mode的主fuzzer来说，完成了上述deterministic fuzzing后，便进入了充满随机性的这一阶段；对于dumb mode或者从fuzzer来说，则是直接从这一阶段开始。

havoc，顾名思义，是充满了各种随机生成的变异，是对原文件的”大破坏”。具体来说，havoc包含了对原文件的多轮变异，每一轮都是将多种方式组合（stacked）而成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
随机选取某个bit进行翻转
随机选取某个byte，将其设置为随机的interesting value
随机选取某个word，并随机选取大、小端序，将其设置为随机的interesting value
随机选取某个dword，并随机选取大、小端序，将其设置为随机的interesting value
随机选取某个byte，对其减去一个随机数
随机选取某个byte，对其加上一个随机数
随机选取某个word，并随机选取大、小端序，对其减去一个随机数
随机选取某个word，并随机选取大、小端序，对其加上一个随机数
随机选取某个dword，并随机选取大、小端序，对其减去一个随机数
随机选取某个dword，并随机选取大、小端序，对其加上一个随机数
随机选取某个byte，将其设置为随机数
随机删除一段bytes
随机选取一个位置，插入一段随机长度的内容，其中75%的概率是插入原文中随机位置的内容，25%的概率是插入一段随机选取的数
随机选取一个位置，替换为一段随机长度的内容，其中75%的概率是替换成原文中随机位置的内容，25%的概率是替换成一段随机选取的数
随机选取一个位置，用随机选取的token（用户提供的或自动生成的）替换
随机选取一个位置，用随机选取的token（用户提供的或自动生成的）插入

AFL会生成一个随机数，作为变异组合的数量，并根据这个数量，每次从上面那些方式中随机选取一个（可以参考高中数学的有放回摸球），依次作用到文件上。如此这般丧心病狂的变异，原文件就大概率面目全非了，而这么多的随机性，也就成了fuzzing过程中的不可控因素，即所谓的”看天吃饭”了。

SPLICING

该阶段对两个样例裁剪后拼接。

这里会找一个合理的拼接位置：

1
2
3
4
5
6
7
8
locate_diffs(in_buf, new_buf, MIN(len, target->len), &f_diff, &l_diff);

if (f_diff < 0 || l_diff < 2 || f_diff == l_diff) {
    ck_free(new_buf);
    goto retry_splicing;
}

split_at = f_diff + UR(l_diff - f_diff);

拼接：

1
2
3
4
5
6
7
len = target->len;
memcpy(new_buf, in_buf, split_at);
in_buf = new_buf;

ck_free(out_buf);
out_buf = ck_alloc_nozero(len);
memcpy(out_buf, in_buf, len);

拼接完成后进行havoc：

1
goto havoc_stage;

至此AFL中的确定性以及随机性变异都已经结束，后面是扫尾阶段，并被设置为abandon_entry：

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

    splicing_with = -1;

    /* Update pending_not_fuzzed count if we made it through the calibration
        cycle and have not seen this entry before. */

    if (!stop_soon && !queue_cur->cal_failed && !queue_cur->was_fuzzed) {
        queue_cur->was_fuzzed = 1;
        pending_not_fuzzed--;
        if (queue_cur->favored) pending_favored--;
    }

    munmap(orig_in, queue_cur->len);

    if (in_buf != orig_in) ck_free(in_buf);
    ck_free(out_buf);
    ck_free(eff_map);

    return ret_val;
common_fuzz_stuff函数

该函数广泛的用于变异阶段中对变异后样例的fuzz。

将out_buf写入文件并执行，然后处理结果，如果出现错误，就返回1。

写入文件：

1
write_to_testcase(out_buf, len);

运行样例：

1
fault = run_target(argv, exec_tmout);

对运行时间的判断：

1
2
3
4
if (subseq_tmouts++ > TMOUT_LIMIT) {
    cur_skipped_paths++;
    return 1;
}

若用户发送SIGUSR1信号就跳过当前样例：

1
2
3
4
5
6
7
if (skip_requested) {

    skip_requested = 0;
    cur_skipped_paths++;
    return 1;

}

保存发现了新的分支路径的种子：

1
queued_discovered += save_if_interesting(argv, out_buf, len, fault);

展示信息并返回：

1
2
3
4
if (!(stage_cur % stats_update_freq) || stage_cur + 1 == stage_max)
    show_stats();

return 0;

while(1)尾部

fuzz_one结束后会根据是否使用了并行的fuzzer来将其他fuzzer的queue保存到自己的queue中：

1
2
3
4
5
6
if (!stop_soon && sync_id && !skipped_fuzz) {
      
      if (!(sync_interval_cnt++ % SYNC_INTERVAL))
        sync_fuzzers(use_argv);

}

一些阶段性参数的设置：

1
2
3
4
5
6
if (!stop_soon && exit_1) stop_soon = 2;

if (stop_soon) break;

queue_cur = queue_cur->next;
current_entry++;

main函数扫尾

这部分简单流程已说过，这里不多说了。

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

总结

最后总结下，while(1)循环的主要内容就是fuzz_one函数，对种子进行变异然后测试。

确定性变异阶段通过使用update_bitmap_score设置的评分，effector map子集对有效字节的判断，启发式的进行了整个变异的过程。

随机性变异阶段主要使用了havoc以及splice两种方式，对种子进行混乱的变异。

参考文章：

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

http://rk700.github.io/2018/01/04/afl-mutations/

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

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

https://blog.csdn.net/weixin_43820701/article/details/110427004