AFL初探

发表于 |

最近在写跟AFL有关的fuzz，因此就大概过了一下AFL的源码。这里大概记录一下自己看的过程。

0x01 AFL基本使用

1.1 使用AFL程序插桩

目标程序

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
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <signal.h>

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

int main(int argc, char *argv[])
{
    char buf[100]={0};
    gets(buf);//存在栈溢出漏洞
    printf(buf);//存在格式化字符串漏洞
    vuln(buf);

    return 0;
}

使用afl-gcc进行插桩编译

afl-gcc -g -o ./zerotest/vuln ./zerotest/vuln.c

1.2 开始fuzz

afl-fuzz -m 300 -i ./zerotest/fuzz_in -o ./zerotest/fuzz_out ./zerotest/vuln -f

PS: 常见参数的含义如下

  • f参数表示：testcase的内容会作为afl_test的stdin
  • m参数表示分配的内存空间
  • i 指定测试样本的路径
  • o 指定输出结果的路径
  • /dev/null 使错误信息不输出到屏幕
  • t：设置程序运行超时值，单位为 ms
  • M：运行主(Master) Fuzzer
  • S：运行从属(Slave) Fuzzer

1.3 fuzz的结果

Image.png

从界面上主要注意以下几点:

  1. last new path 如果报错那么要及时修正命令行参数，不然继续fuzz也是徒劳（因为路径是不会改变的）；
  2. cycles done 如果变绿就说明后面及时继续fuzz，出现crash的几率也很低了，可以选择在这个时候停止
  3. uniq crashes 代表的是crash的数量

1.4 crash分析

Image [2].png

PS: xxd命令的作用就是将一个文件以十六进制的形式显示出来

看起来上面两个crash，第一个大概是栈溢出，第二个看起来是F开头，字符长度为6触发的

0x02 源码阅读

2.1 合法代码插桩——插入调用__afl_maybe_log的汇编码

若pass_thru、skip_intel、skip_app、skip_csect四个标志位均被清除，且instr_ok(这个标志位表征当前读入的行处于.text部分，将在后续设置，初始为清除状态)、instrument_next两个标志位均被设置，且当前行的第一个字符是\\t且第二个字符是字母，则向已插桩的文件写入trampoline_fmt_64/trampoline_fmt_32(取决于use_64bit标志位状态)
经整理最后插入的汇编代码为：

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
/* --- AFL TRAMPOLINE (32-BIT) --- */
.align 4
leal -16(%esp), %esp
movl %edi,  0(%esp)
movl %edx,  4(%esp)
movl %ecx,  8(%esp)
movl %eax, 12(%esp)
movl $0x%08x, %ecx
call __afl_maybe_log
movl 12(%esp), %eax
movl  8(%esp), %ecx
movl  4(%esp), %edx
movl  0(%esp), %edi
leal 16(%esp), %esp
/* --- END --- */

/* --- AFL TRAMPOLINE (64-BIT) --- */
.align 4
leaq -(128+24)(%rsp), %rsp
movq %rdx,  0(%rsp)
movq %rcx,  8(%rsp)
movq %rax, 16(%rsp)
movq $0x%08x, %rcx
call __afl_maybe_log
movq 16(%rsp), %rax
movq  8(%rsp), %rcx
movq  0(%rsp), %rdx
leaq (128+24)(%rsp), %rsp
/* --- END --- */

⚠️：此处的%08x由(random() % ((1 << 16)))生成，在编译期确定。插入结束后，将instrument_next标志位清除，桩代码计数器ins_lines加一。最后将原始的汇编码（即line变量的内容），追加到插桩后文件中。此时检查pass_thru标志位是否被置位，若已置位，则忽略以下流程，继续循环，读取下一行待插桩文件。

2.2 寻找合法有效的待插桩段

这里是真正的插桩函数的核心了，但是在这里我们真正感兴趣的事实上只有.text段

简单概括就是，先找到.text段，不在该段的情况下不会进行打桩操作

然后会在分支跳转（条件分支跳转）的部分插入trampoline_fmt_64/trampoline_fmt_32

注意，JMP表示无条件跳转，因此其另一条分支将永远不会被运行到，那么将不会影响代码覆盖率，因此不在JMP指令后插桩。

识别label以后，会在label的下一行插入trampoline_fmt_64/trampoline_fmt_32

2.3 末尾插桩代码

最后，若桩代码计数器ins_lines不为0，那么将main_payload_64/main_payload_32(取决于use_64bit标志位状态)插入整个汇编文件末尾。

main_payload_64整体逻辑如下

简要概括就是，将随机生成的rcx与一个值做一个抑或，再把以此作为索引的共享区加一。
相当于一个散列表，这样可以知道fuzz是不是经过了一个新的基本块。

0x03 AFL 变异部分源码分析

3.1 fuzz_one

Take the current entry from the queue, fuzz it for a while. This function is a tad too long…

首先把testcase映射在内存中，主要是把testcase里的内容读进in_buf里

1
2
3
4
5
6
7
8
9
10
11
12
13
/* Map the test case into memory. */

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

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

  len = queue_cur->len;

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

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

  close(fd);

接着对testcase进行一个裁剪的过程，然后把in_buf里的内容拷贝到out_buf里

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
/************
   * TRIMMING *
   ************/

  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;

  }

  memcpy(out_buf, in_buf, len);

计算performance score ,这个值的计算方法有点复杂，先留个坑，暂且不深究

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

  orig_perf = perf_score = calculate_score(queue_cur);

  /* Skip right away if -d is given, if we have done deterministic fuzzing on
     this entry ourselves (was_fuzzed), or if it has gone through deterministic
     testing in earlier, resumed runs (passed_det). */

  if (skip_deterministic || queue_cur->was_fuzzed || queue_cur->passed_det)
    goto havoc_stage;

  /* Skip deterministic fuzzing if exec path checksum puts this out of scope
     for this master instance. */

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

  doing_det = 1;

第一阶段的Bitflip 也就是 bitflip 1/1 ，可以看到 stage_max = len << 3; 然后进行了stage_max次数的循环，也就是每字节会做8次bitflip，逐个字节逐个比特进行反转。

反转后调用common_fuzz_stuff 函数，进行fuzz，fuzz过后再次把比特反转回复过来。

在这个阶段还实现了采集token的功能。即如果连续几个字节，反转其最后一个比特后其执行路径相同，且与初始路径不同。那么这连续的几个字节很大概率是有特殊语义的token ，属于关键字性质的。

例如，PNG文件中用IHDR作为起始块的标识，那么就会存在类似于以下的内容

1
........IHDR........

当翻转到字符I的最高位时，因为IHDR被破坏，此时程序的执行路径肯定与处理正常文件的路径是不同的；随后，在翻转接下来3个字符的最高位时，IHDR标识同样被破坏，程序应该会采取同样的执行路径。由此，AFL就判断得到一个可能的token：IHDR，并将其记录下来为后面的变异提供备选。

AFL采取的这种方式是非常巧妙的：就本质而言，这实际上是对每个byte进行修改并检查执行路径；但集成到bitflip后，就不需要再浪费额外的执行资源了。此外，为了控制这样自动生成的token的大小和数量，AFL还在config.h中通过宏定义了限制：

1
2
3
4
5
6
7
/* Length limits for auto-detected dictionary tokens: */

#define MIN_AUTO_EXTRA 3 #define MAX_AUTO_EXTRA 32 
/* Maximum number of auto-extracted dictionary tokens to actually use in fuzzing (first value), and to keep in memory as candidates. The latter should be much higher than the former. */

#define USE_AUTO_EXTRAS 10 
#define MAX_AUTO_EXTRAS (USE_AUTO_EXTRAS * 10)

对于一些文件来说，我们已知其格式中出现的token长度不会超过4，那么我们就可以修改MAX_AUTO_EXTRA为4并重新编译AFL，以排除一些明显不会是token的情况。遗憾的是，这些设置是通过宏定义来实现，所以不能做到运行时指定，每次修改后必须重新编译AFL。

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
/*********************************************
   * SIMPLE BITFLIP (+dictionary construction) *
   *********************************************/

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

  /* Single walking bit. */

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

  stage_val_type = STAGE_VAL_NONE;

  orig_hit_cnt = queued_paths + unique_crashes;

  prev_cksum = queue_cur->exec_cksum;

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

    stage_cur_byte = stage_cur >> 3;

    FLIP_BIT(out_buf, stage_cur);

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

    FLIP_BIT(out_buf, stage_cur);

    /* While flipping the least significant bit in every byte, pull of an extra
       trick to detect possible syntax tokens. In essence, the idea is that if
       you have a binary blob like this:

       xxxxxxxxIHDRxxxxxxxx

       ...and changing the leading and trailing bytes causes variable or no
       changes in program flow, but touching any character in the "IHDR" string
       always produces the same, distinctive path, it's highly likely that
       "IHDR" is an atomically-checked magic value of special significance to
       the fuzzed format.

       We do this here, rather than as a separate stage, because it's a nice
       way to keep the operation approximately "free" (i.e., no extra execs).
       
       Empirically, performing the check when flipping the least significant bit
       is advantageous, compared to doing it at the time of more disruptive
       changes, where the program flow may be affected in more violent ways.

       The caveat is that we won't generate dictionaries in the -d mode or -S
       mode - but that's probably a fair trade-off.

       This won't work particularly well with paths that exhibit variable
       behavior, but fails gracefully, so we'll carry out the checks anyway.

      */

    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;

      }

      /* Continue collecting string, but only if the bit flip actually made
         any difference - we don't want no-op tokens. */

      if (cksum != queue_cur->exec_cksum) {

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

      }

    }

  }

  new_hit_cnt = queued_paths + unique_crashes;

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

后面跟着的就是2比特2比特的逐个翻转，4比特4比特位移是1位的逐个翻转，然后是1字节1字节的翻转等等等。。。。总之是长度不一，步长不同的比特反转。

在进行bitflip 8/8变异时，AFL还生成了一个非常重要的信息：effector map。这个effector map几乎贯穿了整个deterministic fuzzing的始终。

具体地，在对每个byte进行翻转时，如果其造成执行路径与原始路径不一致，就将该byte在effector map中标记为1，即“有效”的，否则标记为0，即“无效”的。

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

由此，通过极小的开销（没有增加额外的执行次数），AFL又一次对文件格式进行了启发式的判断。看到这里，不得不叹服于AFL实现上的精妙。

不过，在某些情况下并不会检测有效字符。第一种情况就是dumb mode或者从fuzzer，此时文件所有的字符都有可能被变异。第二、第三种情况与文件本身有关：

1
2
3
4
5
6
/* Minimum input file length at which the effector logic kicks in: */

#define EFF_MIN_LEN 128 
/* Maximum effector density past which everything is just fuzzed unconditionally (%): */

#define EFF_MAX_PERC 90

即默认情况下，如果文件小于128 bytes，那么所有字符都是“有效”的；同样地，如果AFL发现一个文件有超过90%的bytes都是“有效”的，那么也不差那10%了，大笔一挥，干脆把所有字符都划归为“有效”。

后面仍有arithmetic，interest，dictionary，havoc，splice，cycle等变异手段。具体可以参考https://rk700.github.io/2018/01/04/afl-mutations/ 此处不再赘述。

总而言之，AFL的变异策略既有逐位变异的运气成分，同时也合理运用了覆盖率反馈的信息来启发性的创造token 和 effort map 等概念，帮助算法更好的进行变异。

3.2 save_if_interesting

覆盖率反馈信息除了一定程度上可以启发性的指导变异以外，最大作用就是在这个函数内实现的选种功能。

如果这个has_new_bits返回为0的话，那么该函数直接返回0，程序继续进行下一次的fuzz。但是如果发现了新的cov信息或者bb信息，那么就会将产生新路径的testcase保存为新的种子。

1
2
3
4
if (!(hnb = has_new_bits(virgin_bits))) {
      if (crash_mode) total_crashes++;
      return 0;
    }

代表current 是刚刚返回的覆盖率信息,virgin_map是当前我们的覆盖率状态。可以注意到virgin_map在setup_shm过程中被初始化成了全 1 , 代表current的trace_bits 初始化状态是全0的状态。根据插桩部分的逻辑，每有新的覆盖率信息，会在相应的trace_bits索引位置加一。

1
2
memset(virgin_bits, 255, MAP_SIZE);
memset(trace_bits, 0, MAP_SIZE);

每个trace_bits对应索引里的值其实就代表着走到这条路径的次数，当第1，4，8，128次走到这条路径时，current里的值就是0，而virgin_map里的值则是ff，此时函数将返回2。其余情况都会返回1。最后将current里的值取反，然后与vrigin相与，更新virgin的状态。

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
/* Check if the current execution path brings anything new to the table.
   Update virgin bits to reflect the finds. Returns 1 if the only change is
   the hit-count for a particular tuple; 2 if there are new tuples seen. 
   Updates the map, so subsequent calls will always return 0.

   This function is called after every exec() on a fairly large buffer, so
   it needs to be fast. We do this in 32-bit and 64-bit flavors. */

static inline u8 has_new_bits(u8* virgin_map) {

#ifdef WORD_SIZE_64

  u64* current = (u64*)trace_bits;
  u64* virgin  = (u64*)virgin_map;

  u32  i = (MAP_SIZE >> 3);

#else

  u32* current = (u32*)trace_bits;
  u32* virgin  = (u32*)virgin_map;

  u32  i = (MAP_SIZE >> 2);

#endif /* ^WORD_SIZE_64 */

  u8   ret = 0;

  while (i--) {

    /* Optimize for (*current & *virgin) == 0 - i.e., no bits in current bitmap
       that have not been already cleared from the virgin map - since this will
       almost always be the case. */

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

      if (likely(ret < 2)) {

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

        /* Looks like we have not found any new bytes yet; see if any non-zero
           bytes in current[] are pristine in virgin[]. */

#ifdef WORD_SIZE_64

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

#else

        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;

#endif /* ^WORD_SIZE_64 */

      }

      *virgin &= ~*current;

    }

    current++;
    virgin++;

  }

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

  return ret;

}

0x04 参考

AFL源码分析（I）——白盒模式下的afl-gcc分析 - 安全客，安全资讯平台 (anquanke.com)

[AFL内部实现细节小记](

-------------本文结束感谢您的阅读-------------
+ +