首页
论坛
课程
招聘
[原创]AFL速通——流程及afl-fuzz.c源码简析
2022-7-12 22:46 6611

[原创]AFL速通——流程及afl-fuzz.c源码简析

2022-7-12 22:46
6611

目录

 

前言
这是我读了部分AFL源码的产物,有些地方很可能表述或理解地并不准确,欢迎交流和指教。

source code fuzzing的基本流程

图片描述
(图片引用自AFL++文档
主要内容是Instrument target和Fuzz本体

Instrument

根据compiler的选择不同会影响后续fuzzing效率

  • LTO mode (afl-clang-lto/afl-clang-lto++)

    LTO(Link Time Optimization)链接时优化是链接期间的程序优化,多个中间文件通过链接器合并在一起,并将它们组合为一个程序,缩减代码体积,因此链接时优化是对整个程序的分析和跨模块的优化。

    需要llvm 11+,这是当前afl支持的效率最高的选择(理论上,实际情况会受未知因素影响,比如fuzzing libxml2的时候),也意味着编译要花更长时间

  • LLVM mode (afl-clang-fast/afl-clang-fast++)

    依赖LLVM的optimizer,稳定性较高的编译器,用的比较多,可以跨平台(non-x86)编译

    实现了编译级插桩,效果比汇编级插桩更好

  • GCC_PLUGIN mode (afl-gcc-fast/afl-g++-fast)

    效果和LLVM mode差不多,不过依赖的是GCC_plugin,也比较推荐

  • GCC mode (afl-gcc/afl-g++) (or afl-clang/afl-clang++ for clang)

    相较其他编译器,没别的特色,基本用不到

从编译的实现流程上理解插桩模式差异

 

图片描述

afl-gcc插桩分析

考虑到afl的插桩方式随编译器的选择而变化,从最简单的afl-gcc开始入手。

 

先把一个简单程序用afl-gcc编译,代码来源

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
#include <string.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
 
#define INPUTSIZE 100
 
int process(char *input)
{
    char *out;
    char *rest;
    int len;
    if (strncmp(input, "u ", 2) == 0)
    { // upper case command
        char *rest;
        len = strtol(input + 2, &rest, 10); // how many characters of the string to upper-case
        rest += 1;                            // skip the first char (should be a space)
        out = malloc(len + strlen(input));    // could be shorter, but play it safe
        if (len > (int)strlen(input))
        {
            printf("Specified length %d was larger than the input!\n", len);
            return 1;
        }
        else if (out == NULL)
        {
            printf("Failed to allocate memory\n");
            return 1;
        }
        for (int i = 0; i != len; i++)
        {
            char c = rest[i];
            if (c > 96 && c < 123) // ascii a-z
            {
                c -= 32;
            }
            out[i] = c;
        }
        out[len] = 0;
        strcat(out, rest + len); // append the remaining text
        printf("%s", out);
        free(out);
    }
    else if (strncmp(input, "head ", 5) == 0)
    { // head command
        if (strlen(input) > 6)
        {
            len = strtol(input + 4, &rest, 10);
            rest += 1;          // skip the first char (should be a space)
            rest[len] = '\0'; // truncate string at specified offset
            printf("%s\n", rest);
        }
        else
        {
            fprintf(stderr, "head input was too small\n");
        }
    }
    else if (strcmp(input, "surprise!\n") == 0)
    {
        // easter egg!
        *(char *)1 = 2;
    }
    else
    {
        return 1;
    }
    return 0;
}
 
int main(int argc, char *argv[])
{
    char *usage = "Usage: %s\n"
                  "Text utility - accepts commands and data on stdin and prints results to stdout.\n"
                  "\tInput             | Output\n"
                  "\t------------------+-----------------------\n"
                  "\tu <N> <string>    | Uppercased version of the first <N> bytes of <string>.\n"
                  "\thead <N> <string> | The first <N> bytes of <string>.\n";
    char input[INPUTSIZE] = {0};
 
    // Slurp input
    if (read(STDIN_FILENO, input, INPUTSIZE) < 0)
    {
        fprintf(stderr, "Couldn't read stdin.\n");
    }
 
    int ret = process(input);
    if (ret)
    {
        fprintf(stderr, usage, argv[0]);
    };
    return ret;
}

很显然,只要输出指定字符串,程序就会访问到非法内存,同时程序根据输入头部的不同产生多个分支,从而测试AFL输入样本的变异过程
编译中程序显示对52处位置进行了插桩
图片描述

 

把编译得到的文件丢进IDA,可以发现编译生成的函数中有多个__afl_maybe_log,显然他们由afl-gcc的插桩产生。
图片描述
当执行到这段代码,fuzzer知道这段代码被触发,从而统计每次输入样本的边缘覆盖率。

 

正常生成可执行文件过程为

  • 预处理:.c生成.i
  • 编译:.i生成.s,到汇编语言
  • 汇编:.s生成.o,汇编语言到机器语言
  • 链接:由.o生成可执行文件

IR:高级语言到汇编的中间语言,可以解决平台间的差异

 

llvm负责IR到汇编语言的转化,并在此过程中进行插桩

 

插桩的代码执行时与更新共享内存中的执行信息,从而对代码覆盖率进行统计

 

使用afl-clang-fast编译,产生的函数__sanitizer_cov_trace_pc_guard,就是llvm插桩的经典例子
图片描述

 

ASAN(Address Sanitizer):在数据前后添加禁止访问区域,访问到后报错

  • 存在一个判断标准,判断合法地址和非法地址
  • 每个数据只能写在给他分配的位置上
  • 会把原本相邻的变量隔离
  • 需要更长的编译时间

Fuzz target

源代码比较长,我就挑了几个重要函数的源码进行分析

初始化

进入main函数,首先获取时间,循环读取参数

1
2
3
4
5
6
7
8
9
10
11
12
gettimeofday(&tv, &tz);
  srandom(tv.tv_sec ^ tv.tv_usec ^ getpid());
 
  while ((opt = getopt(argc, argv, "+i:o:f:m:t:T:dnCB:S:M:x:Q")) > 0)
 
    switch (opt) {
 
      case 'i': /* input dir */
 
        if (in_dir) FATAL("Multiple -i options not supported");
        in_dir = optarg;
        …………

下面接了一大堆目录处理和前期检查的函数

setup_shm()

forkserver、主进程、fork出的子进程间存在共享内存,这段共享内存由内核管理,其中存储数组,记录每次样本执行访问到的代码路径

  • 如果是forkserver,通过管道通信
  • fork出的子进程通过共享内存传输结果

该函数用于配置共享内存和virgin_bits

1
2
3
4
5
6
7
8
9
/s数组定义
EXP_ST u8  virgin_bits[MAP_SIZE],     /* Regions yet untouched by fuzzing */
           virgin_tmout[MAP_SIZE],    /* Bits we haven't seen in tmouts   */
           virgin_crash[MAP_SIZE];    /* Bits we haven't seen in crashes  */
EXP_ST void setup_shm(void) {
…………
  if (!in_bitmap) memset(virgin_bits, 255, MAP_SIZE);
  memset(virgin_tmout, 255, MAP_SIZE);
  memset(virgin_crash, 255, MAP_SIZE);

将三个状态数组全部初始化为255(0~65535)

  • virgin_bits记录尚未覆盖的区域
  • virgin_tmout记录timeout时的tuple信息
  • virgin_crash记录crash时的tuple信息
1
2
3
  shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);
…………
  trace_bits = shmat(shm_id, NULL, 0);

int shmget(key_t key, size_t size, int shmflg)申请共享大小为65536的共享内存

  • 第一参数为 IPC_PRIVATE,使用IPC_PRIVATE创建的IPC对象, key值属性为0,和IPC对象的编号就没有了对应关系。这样毫无关系的进程,就不能通过key值来得到IPC对象的编号(因为这种方式创建的IPC对象的key值都是0)。因此,这种方式产生的IPC对象,和无名管道类似,不能用于毫无关系的进程间通信。但也不是一点用处都没有,仍然可以用于有亲缘关系的进程间通信。
  • 第二参数 MAP_SIZE 为65536,是这一段内存的大小。
  • 第三参数 IPC_CREAT | IPC_EXCL | 0600,代表这段内存的权限
    • 0600权限代表,只有创建者可以进行读写
    • IPC_CREAT 如果共享内存不存在,则创建一个共享内存,否则打开操作。
    • IPC_EXCL 只有在共享内存不存在的时候,新的共享内存才建立,否则就产生错误。

void shmat(int shm_id, const void shm_addr, int shmflg) 访问共享内存

  • 第一参数指定这一段共享内存的id

  • 第二参数为NULL一般,shm_addr指定共享内存连接到当前进程中的地址位置,通常为空,表示让系统来选择共享内存的地址。

  • 第三参数shm_flg是一组标志位,通常为0。

  • 返回一个指向共享内存起始位置的指针,存入trace_bits

Fork Server

forkserver功能

  • 由主进程创建的子进程,负责fork出fuzz对象,使用pipe和主进程通信
  • 管道只能在父子进程间通信,如果要实现祖孙进程通信,需要设置环境变量,孙进程通过环境变量获取文件描述符

调用链perform_dry_run(use_argv) -> calibrate_case(argv, q, use_mem, 0, 1) -> init_forkserver(argv)

 

perform_dry_run():每个测试用例都执行一次,仅对初始输入执行一次测试,以确保程序按预期运行

 

calibrate_case():校准一个新的测试用例,只在处理输入目录和发现新路径是执行

 

init_forkserver():用于初始化forkserver

  1. 初始参数中st_pipe[2], ctl_pipe[2]分别为状态管道和控制管道

    1
    2
    3
    4
    5
    6
    EXP_ST void init_forkserver(char** argv) {
     
     static struct itimerval it;
     int st_pipe[2], ctl_pipe[2];
     int status;
     s32 rlen;
  2. 接着fork出子进程forkserver并使其脱离主进程

    1
    2
    3
    4
    5
    6
    7
    forksrv_pid = fork();//子进程为forkserver
     
    if (forksrv_pid < 0) PFATAL("fork() failed");  //fork失败
     
    if (!forksrv_pid) {   //forkserver执行
     …………
      setsid();  //让子进程完全独立运行
  3. 重定向forkserver的stdout、stderr到dev_null_fd

    视情况重定向stdin

    • 若定义了out_file,则把stdin重定向到dev_null_fd
    • 否则关闭out_fd(间接关闭了stdin)

    完成后对FORKSRV_FD和FORKSRV_FD + 1进行重定向

    linux之dup和dup2函数解析

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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);
    }
    if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed");
    if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed");
  4. 执行execv之前还有一系列参数设置,这里先略过,如果execv执行失败,那么主进程将通过trace_bits = EXEC_FAIL_SIG(位于bitmap)获得信息。

    1
    2
    3
    4
    5
    6
    7
    execv(target_path, argv);
     
    /* Use a distinctive bitmap signature to tell the parent about execv()
       falling through. */
     
    *(u32*)trace_bits = EXEC_FAIL_SIG;
    exit(0);
  5. 主进程的pipe为fsrv_ctl_fd = ctl_pipe[1]用于写;fsrv_st_fd = st_pipe[0]用于读; 设置完成后等待forkserver的返回状态信号

    • 如果长度正好为4(exit),一切正常,直接返回
    • 否则分类处理异常信号,打印消息并退出
      • crash
      • timeout
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /* Close the unneeded endpoints. */
    close(ctl_pipe[0]);
    close(st_pipe[1]);
     
    fsrv_ctl_fd = ctl_pipe[1];
    fsrv_st_fd  = st_pipe[0];
    //等待返回消息
    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);
    if (rlen == 4) {
      OKF("All right - fork server is up.");
      return;
    }

fuzzing策略

各种初始设置完成后进入while循环,执行fuzzing主程序

 

先来看一个比较重要的数据结构queue_entry的特点

  • 存储输入样本
  • 存储每次执行样本后的基本信息
  • 链表连接
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
struct queue_entry {
 
  u8* fname;                          /* File name for the test case      */
  u32 len;                            /* Input length                     */
 
  u8  cal_failed,                     /* Calibration failed?              */
      trim_done,                      /* Trimmed?                         */
      was_fuzzed,                     /* Had any fuzzing done yet?        */
      passed_det,                     /* Deterministic stages passed?     */
      has_new_cov,                    /* Triggers new coverage?           */
      var_behavior,                   /* Variable behavior?               */
      favored,                        /* Currently favored?               */
      fs_redundant;                   /* Marked as redundant in the fs?   */
 
  u32 bitmap_size,                    /* Number of bits set in bitmap     */
      exec_cksum;                     /* Checksum of the execution trace  */
 
  u64 exec_us,                        /* Execution time (us)              */
      handicap,                       /* Number of queue cycles behind    */
      depth;                          /* Path depth                       */
 
  u8* trace_mini;                     /* Trace bytes, if kept             */
  u32 tc_ref;                         /* Trace bytes ref count            */
 
  struct queue_entry *next,           /* Next element, if any             */
                     *next_100;       /* 100 elements ahead               */
 
};
 
static struct queue_entry *queue,     /* Fuzzing queue (linked list)      */
                          *queue_cur, /* Current offset within the queue  */
                          *queue_top, /* Top of the list                  */
                          *q_prev100; /* Previous 100 marker              */
static struct queue_entry*
  top_rated[MAP_SIZE];                /* Top entries for bitmap bytes     */

其中top_rated里面存放的是bitmap中每个位置当前最短路径

cull_queue()

功能:每次执行fuzz_one之前,简化队列

  1. 如果是dumb_mode或者score_changed为0(即上一次fuzz没有产生更好的路径),直接返回

    1
    if (dumb_mode || !score_changed) return;
  2. 遍历队列,还原favored设置

    1
    2
    3
    4
    5
    q = queue;
    while (q) {
      q->favored = 0;
      q = q->next;
    }
  3. 循环取出处于top_rate中并且被temp_v标记的用例,每取出一个,清除temp_v中所有属于这个entry的bit,并设置它的favored位,令queued_favored,如果这个用例还没被fuzz过,令pending_favored++,标记优先执行

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for (i = 0; i < MAP_SIZE; i++)
      if (top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {
        u32 j = MAP_SIZE >> 3;
        while (j--)
          if (top_rated[i]->trace_mini[j])
            temp_v[j] &= ~top_rated[i]->trace_mini[j];
     
        top_rated[i]->favored = 1;
        queued_favored++;
        if (!top_rated[i]->was_fuzzed) pending_favored++;
      }
  4. 简化队列,标记冗余项

    1
    2
    3
    4
    5
    q = queue;
      while (q) {
        mark_as_redundant(q, !q->favored);
        q = q->next;
      }

if (!queue_cur)

功能:判断一次循环是否结束,是则初始化队列

 

queue_cur指向当前队列中元素,为空说明遍历到结尾

 

不为空则直接下一步

  1. 记录轮数、重置状态

    1
    2
    3
    4
    queue_cycle++;
       current_entry     = 0;
      cur_skipped_paths = 0;
       queue_cur         = queue;
  2. seek_to的值来源于find_start_position(),找到fuzzer重启后的开始位置

    (只在fuzzer重启的第一个循环里用到)这里把queue_cur抬高到seek_to位置,恢复重启前的状态

    1
    2
    3
    4
    5
    while (seek_to) {
      current_entry++;
      seek_to--;
      queue_cur = queue_cur->next;
    }
  3. 展示状态,就是命令行面板,每次状态更新或在其他状况下就会调用一次

    1
    show_stats();
  4. 非终端模式下输出循环数

    1
    2
    3
    4
    if (not_on_tty) {
            ACTF("Entering queue cycle %llu.", queue_cycle);
            fflush(stdout);
          }
  5. queue_path不变,说明一整个循环未发现新路径,设置cycles_wo_finds+1或者use_splicing=1,他注释说会更换策略,但如果设置了-d参数,其实本来用的就是splicing,直接计数就行,cycles_wo_finds只是根据它的数量判断现在是否可以结束fuzzing,没别的影响

    1
    2
    3
    4
    5
    6
    if (queued_paths == prev_queued) {
     
            if (use_splicing) cycles_wo_finds++; else use_splicing = 1;
     
          } else cycles_wo_finds = 0;
          prev_queued = queued_paths;
  6. 设置prev_queued为上一次的结果

    1
    prev_queued = queued_paths;
  7. 如果设置了相关参数,sync_fuzzers()可以从其他fuzzer获取测试用例

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

关键执行函数fuzz_one()

1
skipped_fuzz = fuzz_one(use_argv);

终于到了最关键的地方

 

fuzz_one从当前队列中取一个用例执行

 

fuzz成功返回0,跳过或bailed out返回1

  1. 进来先判断是否有favored, non-fuzzed用例需要执行

    如果有,则有99%的概率跳过在它之前的用例

    1
    2
    3
    4
    if (pending_favored){
       if ((queue_cur->was_fuzzed || !queue_cur->favored) &&
            UR(100) < SKIP_TO_NEW_PROB) return 1;
    }
  2. 即使没有需要优先fuzz的用例,非dumb_mode下,当前用例不是favored,队列中超过10个元素的情况下

    • 当前已运行超过2轮,未被fuzz过的,跳过概率75%(就是说第一二次循环就会跳过很大一部分,这是由于perform_dry_run里已经跑过一轮测试了)
    • 否则,跳过概率95%
    1
    2
    3
    4
    5
    6
    7
    else if (!dumb_mode && !queue_cur->favored && queued_paths > 10) {
        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;
        }
      }
  3. 直接把当前测试用例映射到内存,提高效率

    1
    orig_in = in_buf = mmap(0, len, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
  4. out_buf不是从文件读,这里相当于直接用了malloc(len+1),即使mmap也不能提高效率

    1
    out_buf = ck_alloc_nozero(len);

fuzz_one CALIBRATION

1
if (queue_cur->cal_failed)

只有存在cal_failed被标记才会执行

 

cal_failed在calibrate_case()中,发生以下情况会+1

  • 若测试时发生crash_mode(-C设置crash_mode为2,否则为0?)以外的fault
  • 非dumb_mode,且第一次测试运行后trace_bits为空

同时afl允许我们通过设置,即使发生上述情况,也不在此阶段执行CALIBRATION(通过令cal_failed=3)

 

该判定位于perform_dry_run()

  • 设置timeout_given =2,则忽略FAULT_TMOUT
  • 未设置crash_mode时,设置环境变量AFL_SKIP_CRASHES为1,忽略FAULT_CRASH
1
2
if (cal_failures == queued_paths)
if (cal_failures * 5 > queued_paths)

然而,出现上述问题会使cal_failures++,若报错比例过高,就会要求你检查设置

 

回到fuzz_one,若校准错误小于3

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

让存在校准问题的用例再次校准

  • 出现FAULT_ERROR,说明无法运行,直接放弃抢救,报错
  • 出现crash_mode,接着往下运行
  • 其他任何情况都跳过,cur_skipped_paths++

fuzz_one TRIMMING

1
2
3
4
5
6
7
if (!dumb_mode && !queue_cur->trim_done){
 u8 res = trim_case(argv, queue_cur, in_buf);
 …………
 queue_cur->trim_done = 1;
 if (len != queue_cur->len) len = queue_cur->len;
}
memcpy(out_buf, in_buf, len);

非dumb_mode且该case尚未trim时执行

 

最后结果存储在out_buf

 

trim_case(char** argv, struct queue_entry* q, u8* in_buf)

  1. 长度小于5直接返回
  2. len_p2=2^x > q->len

    remove_len取len_p2/16与4的最大值

    1
    2
    len_p2 = next_p2(q->len);
    remove_len = MAX(len_p2 / TRIM_START_STEPS, TRIM_MIN_BYTES);
  3. 循环判断remove_len是否大于最小步长max(len_p2 /1024,4),满足则继续

    否则跳转到7

    1
    while (remove_len >= MAX(len_p2 / TRIM_END_STEPS, TRIM_MIN_BYTES))
  4. 格式化remove_len到tmp

    1
    sprintf(tmp, "trim %s/%s", DI(remove_len), DI(remove_len));
  5. 内部循环,根据 remove_pos, trim_avail生成新case

    1
    2
    3
    4
    5
    6
    7
    while (remove_pos < q->len){
    write_with_gap(in_buf, q->len, remove_pos, trim_avail);
    fault = run_target(argv, exec_tmout);
    cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
    if (cksum == q->exec_cksum){……}
    else remove_pos += remove_len
    }

    static void write_with_gap(void* mem, u32 len, u32 skip_at, u32 skip_len)

    功能:删除skip_at开始skip_len长度的内容,新内容存储于mem(此处为in_buf)

    运行一次新case,确认当前删除是否影响bitmap

    • 如果不影响,保存这次缩减
    • 否则remove_pos后移步长remove_len
  6. remove_len/2,回到3进行判断

    1
    remove_len >>= 1;
  7. needs_write为1(在5的if中设置)说明case需要更新,把in_buf内容写入文件,并更新bitmap信息

    1
    2
    3
    4
    5
    if (needs_write){
    ck_write(fd, in_buf, q->len, q->fname);
    memcpy(trace_bits, clean_trace, MAP_SIZE);
    update_bitmap_score(q);
    }

fuzz_one PERFORMANCE SCORE

  1. 调用calculate_score(queue_cur)计算当前queue_cur的score
  2. 如果设置了skip_deterministic或者queue_cur->was_fuzzed或者queue_cur->passed_det=1

    如果当前的queue_cur->exec_cksum % master_max不等于master_id - 1

    跳转havoc_stage

fuzz_one变异

考虑到这部分代码比较长,我主要从功能上入手,结合部分代码分析

 

变异分为6个阶段

  • SIMPLE BITFLIP (+dictionary construction)阶段
  • ARITHMETIC INC/DEC 阶段
  • INTERESTING VALUES阶段
  • DICTIONARY STUFF阶段
  • RANDOM HAVOC阶段
  • SPLICING阶段

SIMPLE BITFLIP (+dictionary construction)阶段

按位翻转,每次都是比特位级别的操作,从 1bit 到 32bit

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)

_ar是操作对象,_br指明操作第几个字节(_bf) >> 3中的第几个bit(128 >> ((_bf) & 7))(从高位到低位)

 

一个异或相当于实现了对一个指定bit位的翻转

bitflip 1/1

1
2
3
4
5
6
7
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);
……
}
  1. 第一个翻转会遍历case中的每一位,每次翻转1个bit
  2. 如果翻转后,common_fuzz_stuff()返回1,就直接跳过整个case,否则把这个bit再翻转回来
  3. 检测token并添加

    1
    maybe_add_auto(a_collect, a_len);

    从注释上理解token得概念:如果在某一段连续bit上进行连续翻转后,都能让程序产生新的路径,就称连续翻转的这些bit为一个token

common_fuzz_stuff(char** argv, u8* out_buf, u32 len)

  1. 用新的case运行程序,获取fault

    1
    2
    write_to_testcase(out_buf, len);
    fault = run_target(argv, exec_tmout);
  2. 检测fault值

    1
    2
    3
    4
    5
    6
    if (fault == FAULT_TMOUT) {
        if (subseq_tmouts++ > TMOUT_LIMIT) {
          cur_skipped_paths++;
          return 1;
        }
      } else subseq_tmouts = 0;
    • 如果FAULT_TMOUT并且subseq_tmouts(fuzz每个case时置零)未超出限制,返回1

    • 若不是FAULT_TMOUT,subseq_tmouts=0

  3. 用户要求进程终止,返回1
  4. save_if_interesting()
  5. 返回0

bitflip 2/1

每次连续反转2个bit,步长为1bit

bitflip 4/1

每次连续反转2个bit,步长为1bit

bitflip 8/8

增加了effector map,每次连续反转8个bit,步长为8bit

 

与之前找token的方式相似,如果byte翻转生成了新路径,就让这个byte在effector map中位置为1,否则为0。目的也是让后续变异参考,确认哪些位置是关键的参数,绕过无用的数据。

1
2
3
4
5
eff_map[0] = 1;
if (EFF_APOS(len - 1) != 0) {
  eff_map[EFF_APOS(len - 1)] = 1;
  eff_cnt++;
}

初始只有第一个、最后一个位置为1

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

每次发现新路径设置1

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

发现有效位超过90%直接全为1

 

注意,如果采用dumb mode或从fuzzer后续不会用到effector map的结果

bitflip 16/8

每次连续反转16个bit,步长为8bit

bitflip 32/8

每次连续反转32个bit,步长为8bit

ARITHMETIC INC/DEC 阶段

目的是测试易于整数溢出的数据

 

与位翻转不同,从 8bit 级别开始,而且每次进行的是加减运算操作

arith 8/8

每次对8bit进行加减运算,步长8bit

  1. case遍历

    1
    2
    3
    for (i = 0; i < len; i++){
    u8 orig = out_buf[i];
    }

    orig为每次操作的位置

  2. effector map为0直接跳过

    1
    if (!eff_map[EFF_APOS(i)])
  3. 循环进行前后异或,一共ARITH_MAX=35轮

    1
    for (j = 1; j <= ARITH_MAX; j++)
  4. org与orig+j进行异或

    1
    u8 r = orig ^ (orig + j);
  5. 要求每次产生的case不能与bitflip产生的相同,否则直接跳过

    通过orig+j的方式生成新的case进行测试

    1
    2
    3
    4
    5
    6
    7
    8
    9
    if (!could_be_bitflip(r)) {
     
      stage_cur_val = j;
      out_buf[i] = orig + j;
     
      if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
      stage_cur++;
     
    } else stage_max--;
  6. 与上一步相似,使用org-j生成新的case进行测试

    1
    2
    3
    4
    5
    6
    r =  orig ^ (orig - j);
    if (!could_be_bitflip(r)) {
      stage_cur_val = -j;
      out_buf[i] = orig - j;
      ……
    } else stage_max--;
  7. 恢复原case

    1
    out_buf[i] = orig;

arith 16/8

每次对16bit进行加减运算,步长8bit,对小端、大端加减法都进行测试

arith 32/8

每次对32bit进行加减运算,步长8bit,对小端、大端加减法都进行测试

INTERESTING VALUES阶段

使用“interesting values”对文件内容进行替换,替换内容为一系列确定的值

1
2
3
static s8  interesting_8[]  = { INTERESTING_8 };
static s16 interesting_16[] = { INTERESTING_8, INTERESTING_16 };
static s32 interesting_32[] = { INTERESTING_8, INTERESTING_16, INTERESTING_32 };

图片描述

interest 8/8

每次对8bit进行替换变异,步长8bit

  1. case遍历

    1
    for (i = 0; i < len; i++)
  2. eff_map检验不为0

    1
    if (!eff_map[EFF_APOS(i)])
  3. 替换内容遍历

    1
    for (j = 0; j < sizeof(interesting_8); j++)
  4. 要求新case不能被bitfilp和arith生成过

    1
    2
    if (could_be_bitflip(orig ^ (u8)interesting_8[j]) ||
              could_be_arith(orig, (u8)interesting_8[j], 1))
  5. 朴实无华的执行并恢复原case

    1
    2
    3
    4
    stage_cur_val = interesting_8[j];
    out_buf[i] = interesting_8[j];
    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
    out_buf[i] = orig;

interest 16/8

每次对16bit进行替换变异,步长8bit

interest 32/8

每次对32bit进行替换变异,步长8bit

DICTIONARY STUFF阶段

用户提供的字典里有token,用来替换要进行变异的文件内容,如果用户没提供就使用 bitflip 自动生成的 token

user extras (over)

以8bit为步长,标记起始位置开始,替换为token

  1. 每个字节都替换一遍

    1
    for (i = 0; i < len; i++)
  2. 遍历用户字典

    1
    for (j = 0; j < extras_cnt; j++)
  3. 出现以下情况,直接下一条token

    1
    2
    3
    4
    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)))
    • 字典token数>200,随机生成一个小于字典token数,仍>=200
    • 替换token后长度超过case原大小
    • case中数据与token一致
    • eff_map为0
  4. 替换,执行

    1
    2
    3
    last_len = extras[j].len;
    memcpy(out_buf + i, extras[j].data, last_len);
     if (common_fuzz_stuff(argv, out_buf, len))
  5. 所有token结束后恢复,跳回步骤1

    1
    memcpy(out_buf + i, in_buf + i, last_len);

user extras (insert)

以8bit为步长,标记起始位置插入token

auto extras (over)

以8bit为步长,标记起始位置开始,替换为在bitflip阶段生成的token

 

这是deterministic steps的最后一步

1
if (!queue_cur->passed_det) mark_as_det_done(queue_cur);

我们可以在这里设置完成状态

RANDOM HAVOC阶段

进行很大程度的杂乱破坏,随机组合,规则比较杂,但目的一致

SPLICING阶段

通过将两个case按一定规则进行拼接,得到一个新case

 

HAVOC和SPLICING是相结合的,拼接case后会回到havoc进行随机变异

 

参考文章:

  1. AFL源码阅读笔记之gcc与fuzz部分https://bbs.pediy.com/thread-265936.htm
  2. AFL 源码分析https://blog.csdn.net/song_lee/article/details/108244627
  3. 漏洞挖掘技术之 AFL 项目分析https://bbs.pediy.com/thread-249912.htm

看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

最后于 2022-7-25 18:27 被Azyka编辑 ,原因: 增加图片引用
收藏
点赞15
打赏
分享
打赏 + 100.00雪花
打赏次数 1 雪花 + 100.00
 
赞赏  Editor   +100.00 2022/07/28 恭喜您获得“雪花”奖励,安全圈有你而精彩!
最新回复 (6)
雪    币: 2381
活跃值: 活跃值 (2219)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
genliese 活跃值 1 2022-7-15 17:29
2
0
支持
雪    币: 1015
活跃值: 活跃值 (962)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
huangjw 活跃值 2022-7-16 14:53
3
0
还没接触到这块的技术
雪    币: 1271
活跃值: 活跃值 (773)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
Azyka 活跃值 1 2022-7-19 20:40
5
0

感谢各位的支持和建议:)

最后于 2022-7-19 20:41 被Azyka编辑 ,原因:
雪    币: 9696
活跃值: 活跃值 (9569)
能力值: ( LV12,RANK:240 )
在线值:
发帖
回帖
粉丝
pureGavin 活跃值 2 2022-7-20 13:40
6
0
感谢分享
雪    币: 8607
活跃值: 活跃值 (884)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
suiwinder 活跃值 2022-7-22 08:48
7
0
对新手来说,难度比较大。
游客
登录 | 注册 方可回帖
返回