AFL 源码分析

只要吃透了AFL的源码，就能掌握绝⼤部分fuzzer的要领

前言

源码分析之前需先对AFL有个基本的认识,可以看看这篇文章: https://xidoo.top/2022/01/afl-white-book
本文按照时序对afl-fuzz.c进行分析.相应函数在第一次调用点进行分析.
参考文章:https://eternalsakura13.com/2020/08/23/afl/

调试准备

使用的是Sakura师傅提供的Clion调试环境.
程序调试到fork时会挂掉,提前设置set follow-fork-mode parent来继续跟踪Fuzzer(虽然但是,这个选项不应该是默认行为么…).
可以通过这样的方式加载特定项目的gdb脚本

set auto-load local-gdbinit on
add-auto-load-safe-path [full path to the project root]/.gdbinit

afl-fuzz.c

初始配置

随机数种子

首先调用gettimeofday获取当前时间,根据当前时间异或上当前进程pid后传入srandom作为随机数种子.

处理参数

接下来处理传给afl-fuzz的参数,设定相关flag及配置变量,检查参数合法性.

setup_signal_handlers

设置信号处理函数.

• SIGHUP,SIGINT,SIGTERM: 设置stop_soon=1,向child和fork_server发送SIGKILL.
• SIGALRM: 如设置child_time_out = 1,向child发送SIGKILL,如果child_pid == -1,转而向fork_server发送SIGKILL.
• SIGWINCH: 设置clear_screen=1.
• SIGUSR1: 设置skip_requested=1(使用SIGUSR1作为skip entry的信号)
• SIGTSTP,SIGPIPE(stop signal from tty/write on a pipe with no one to read it): 使用SIG_IGN忽视.

check_asan_opts

读取环境变量中的ASAN_OPTIONS及MSAN_OPTIONS选项,进行检查.

fix_up_sync

修复使用-S,-M选项时(distributed mode)的out_dir和sync_dir.
sync_dir = out_dir
outdir = outdir/sync_id

读取环境变量配置

读取一些环境变量的配置.其中AFL_PRELOAD及AFL_LD_PRELOAD可以指定共享库和加载器的路径

save_cmdline

将command line拷贝一份到orig_cmdline,参数间由空格分隔.

fix_up_banner

Trim and possibly create a banner for the run.

check_if_tty

检查是否需要UI及是否正在使用TTY

get_core_count

读取_SC_NPROCESSORS_ONLN配置获取CPU核数.

bind_to_free_cpu

调用sched_setaffinity将当前进程绑定到(指定的)空闲CPU

check_crash_handling

检查/proc/sys/kernel/core_pattern,确保崩溃产生的核心转储不会发送给某个外部工具,避免fuzzer因延迟过长而将崩溃认为是超时.

check_cpu_governor

检测CPU的调度策略

setup_post

dlopen打开环境变量AFL_POST_LIBRARY指定的库,设置post_handler为库中的alf_postprocess函数

setup_shm

配置共享内存和virgin_bits(Regions yet untouched by fuzzing)

init_count_class16

初始化count_class_lookup16数组,与count_class_lookup8作用相同.将元组(边)实际命中次数映射到某个桶中.
出于效率原因一次读取16bit.

AFL 在检测新元组出现的同时，也粗略地考虑了元组命中次数，它们被分为了如下几个桶 bucket ：
1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+
元组数在每个桶内的变化是可以忽略的；从一个桶到另一个桶的改变将会被认为是程序控制流中的一次有趣的改变，也会指导下一阶段的进化过程 evolutionary process .

不是很好理解,与classify_count结合起来理解.写法挺有意思的,后面has_new_bits还会提到

/* Destructively classify execution counts in a trace. This is used as a
   preprocessing step for any newly acquired traces. Called on every exec,
   must be fast. */

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

};

static u16 count_class_lookup16[65536];

EXP_ST void init_count_class16(void)
{

  u32 b1, b2;

  for (b1 = 0; b1 < 256; b1++)
    for (b2 = 0; b2 < 256; b2++)
      count_class_lookup16[(b1 << 8) + b2] =
          (count_class_lookup8[b1] << 8) |
          count_class_lookup8[b2];
}

#ifdef WORD_SIZE_64

static inline void classify_counts(u64 *mem)
{

  u32 i = MAP_SIZE >> 3;

  while (i--)
  {

    /* Optimize for sparse bitmaps. */

    if (unlikely(*mem))
    {

      u16 *mem16 = (u16 *)mem;

      mem16[0] = count_class_lookup16[mem16[0]];
      mem16[1] = count_class_lookup16[mem16[1]];
      mem16[2] = count_class_lookup16[mem16[2]];
      mem16[3] = count_class_lookup16[mem16[3]];
    }

    mem++;
  }
}

#else

static inline void classify_counts(u32 *mem)
{

  u32 i = MAP_SIZE >> 2;

  while (i--)
  {

    /* Optimize for sparse bitmaps. */

    if (unlikely(*mem))
    {

      u16 *mem16 = (u16 *)mem;

      mem16[0] = count_class_lookup16[mem16[0]];
      mem16[1] = count_class_lookup16[mem16[1]];
    }

    mem++;
  }
}

#endif /* ^WORD_SIZE_64 */

setup_dirs_fds

准备output文件夹及其子目录,和文件描述符.

read_testcases

从输入目录中读取所有的测试样例,加入队列用于后续测试.
如果存在in_dir/queue目录,将in_dir设置为该目录.扫描其并根据文件名进行排序.若设置了shuffle_queue将文件名序列打乱(shuffle).去掉不合法的文件及已经加入到deterministic_done目录的文件(resume)后调用add_to_queue将合法文件加入到队列中.

设置queued_at_start=queued_paths.(queue中元素个数)

load_auto

加载自动生成的词典.

pivot_inputs

在output目录中为输入测试样例创建硬链接(或拷贝).

find_timeout

如果没有用-t指定超时时间且正在恢复会话,则尝试从fuzzer_stats中读取exec_timeout作为超时时间.

detect_file_args

如果参数中有@@ 且没有指定outfile,则将outfile设置为out_dir/.cur_input

setup_stdio_file

删除out_dir/.cur_input再重新创建,保存文件描述符到out_fd.

check_binary

检查要fuzz的二进制程序是否存在且不是shell脚本,同时检查ELF头是否合法以及AFL的插桩证据.并通过程序中的插桩信息配置一些模式,如uses_asan.

获取当前时间作为启动时间

设置fuzz对象的参数

从argv中获取传给fuzz对象的参数,若为qemu_mode将重构参数.

perform_dry_run

遍历初始输入的测试样例进行校准,确保应用程序预期工作.

calibrate_case

校准一个测试样例

init_forkserver

其中会首先调用init_forkserver启动forkserver.

方案

关于forkserver的想法及样例代码在https://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html 中解释.
总结一下:
在传统的fuzzer中,fuuzzer自身不断fork+execve到fuzz目标程序(target),target再读取输入并处理,而Fuzzer通过waitpid获取处理结果.这种情况下,Fuzzer会花费大量时间waitpid来等待进程结束,等待链接器和所有的库初始化例程完成工作.

作者提出的解决方案有:

1. 通过自定义ELF加载器在Fuzzer内部执行target程序,通过mprotect保护Fuzzer本身的内存空间.
2. 在单个子进程中执行并保存快照,稍后通过/proc/pid/mem恢复到快照.
   但这两个方案都需要处理复杂的信号以及文件描述符.

AFL采用的方法是将一段代码插入到target中,在其在加载并完成库的初始化后执行,该段代码诗其停在某个指定处(main),等待fuzzer的信号,接收到信号后fork出子进程,子进程作为target进行处理.而父进程即为forkserver,接收fuzzer的命令并将子进程执行结果发送给fuzzer.由于Copy-On-Write的机制,这将十分高效.

forkserver

当然,从Fuzzer创建forkserver的过程还是要经过一次fork+execve的过程.forkserver创建后,其的标准输出及标准错误均被dup到/dev/null.若此前设置了out_file,将标准输入dup到/dev/null,否则dup到out_fd.关闭Fuzzer自身的文件描述符.
设置ASAN和MSAN的环境变量,若没有指定LD_BIND_LAZY,设置LD_BIND_NOW=1,提前完成所有的加载绑定工作.
最后通过execv加载插桩后的target程序,其将会成为真正的forkserver.

Fuzzer

关闭不再需要的文件描述符.从status管道中读取4个字节,如果成功说明forkserver开始工作.否则进行错误处理.

保存并更新位图

• 如果该测试样例不是第一次校准
  • 将当前trace_bits拷贝到first_trace.
  • 调用has_new_bits更新virgin_bits,hnb及new_bits

has_new_bits(virgin_bits)

笔者认为分析该函数的实现有利于理解trace_bits及之前提到的所谓”将元组(边)实际命中次数映射到某个桶中”.
该函数的目的是检测trace_bits中有新的bit被置位(新的bit被置位有两种情况,一是有新的路径(元组)产生,二是某元组的命中次数进入到下一个桶中),并更新virgin_bits位图.
由于该函数会频繁调用,所以需要提高其的运行效率.
详见下方注释.

/* 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); //以8字节(WORD_SIZE)为一个大的检测单位.

#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--) //以WORD_SIZE遍历整个位图
  {

    /* 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))
        /* (*current & *virgin) == 0的优化版本
        检测该字长的trace_bits中是否有virgin_bits中仍置1的比特位.
        可以把virgin_bits理解为用来check trace_bits的掩码.
        */
    {

      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))
        /* 注意一下运算符优先级.依次检查单个字节中 
        1.trace_bits是否至少有一个比特位置位(当前该路径是否被发现)
        2.virgin_bits是否每个比特仍置位(该路径之前未被发现)
        满足上述两个条件则说明有新的路径被发现,返回2
        */
          ret = 2;
        else
        //否则说明是该WORDSIZE代表的路径中,命中次数进入了下一个桶.
          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; //更新该WORDSIZE的virgin_bits
    }

    current++;
    virgin++;
  }

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

  return ret;
}

进入校准阶段(calibration stage)

循环运行stage_max = fast_cal ? 3 : CAL_CYCLES(8)次

write_to_testcase

将本次queue_entry对应的样例内容写入out_file

run_target

执行target程序并监控.若dumb_mode=1或no_forkserver=1,使用传统的fork-exec方案进行测试.否则向forkserver发送命令并读取forkserver传回的target’s pid.等待target执行完成读取forkserver传回的status.
计算本次的执行时间.
对本次产生的新trace_bits进行classify_counts(上文中分析过).
返回本次测试的结果保存到fault.

初步分析执行结果

• 如果fault!=crash_mode(crash_mode默认是FAULT_NONE,指定-C后是FAULT_CRASH),跳转到abort_calibration标签.
• 如果不是dumb_mode且是该测试样例是第一次运行且运行后共享内存没有任何字节被置位(!count_bytes(trace_bits)),更新fault为FAULT_NOINST后跳转到abort_calibration.
• 计算hash32(trace_bits, MAP_SIZE, HASH_CONST)的结果保存到cksum中,若该测试样例是第一次运行或与上次cksum不同(路径可变的queue),
  • 调用has_new_bits分析执行结果,更新virgin_bits,hnb及new_bits
  • 如果是路径可变的queue,遍历整个位图,if (!var_bytes[i] && first_trace[i] != trace_bits[i])
    • 设置var_byte[i] = 1,更新循环次数stage_max=CAL_CYCLES_LONG(40).这将使得该样例被持续测试直到不再使trace_bits产生未出现过的变化.
    • 设置var_detected=1(路径可变的queue)
  • 否则意味着是第一次运行,保存本次cksum到q->exec_cksum,复制trace_bits到first_trace.

评估校准表现

计算该样例在整个校准阶段的用时和循环次数.
保存一些统计信息到该queue_entry中.

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

检查是否出现了更”favorable”的路径.这是为了拥有一个最小的路径集来触发目前位图中出现的所有位,然后专注于fuzz这个集合.

判断是否更favorable的fav_factor是由q->exec_us(校准时间)*q->len(样例长度)得到的.

• 遍历trace_bits中存在的每一条路径,
  • 如果有更小的fav_factor
    • 减少以前该路径对应的评分最高queue_entry的引用.设置当前queue_entry为评分最高,并引用+1.如果该queue_entry还没有创建trace_mini,分配一个并调用minimize_bits将当前trace_bits压缩存入.压缩将丢失路径的计数信息,即一条路径从一个字节(8位)压缩到1位空间.设置score_changed = 1

如果该样例是第一次校准且结果是FAULT_NONE且!new_bits

设置fault = FAULT_NOBITS

abort_calibration

• 如果校准产生了新的路径且!q->has_new_cov,设置q->has_new_cov = 1并将queued_with_cov++.
• 如果是可变路径的样例,计算本次校准中产生变化的路径数
  • 该样例对应var_behavior未置1
    • var_behavior置1,创建符号链接out_dir/queue/.state/variable_behavior/fname,queued_variable++.
• 恢复到校准前的stage.(stage_name,stage_cur,stage_max)
• 如果该样例不是第一次校准
  • show_stats
• 返回fault.

处理本次校准结果

• FAULT_NONE:
  • 如果当前是第一个样例，则check_map_coverage，用以评估map coverage
    • 若trace_bits中发现的路径小于100，就直接返回
    • trace_bits的数组后半段，如果有值就直接返回。
    • 否则出警告WARNF(“Recompile binary with newer version of afl to improve coverage!”)
  • 如果是crash_mode,抛出异常FATAL(“Test case ‘%s’ does NOT crash”, fn).
• FAULT_TMOUT:
  • 若指定了-t nn+,则设置q->cal_failed = CAL_CHANCES,cal_failures++(容忍超时并跳过该样例),否则抛出异常.
• FAULT_CRASH:
  • 除了崩溃探索(-C)以外,直接造成Crash的初始输入是不合规的.
  • 如果指定了-C或AFL_SKIP_CRASHES,跳过该样例.后者还会设置q->cal_failed = CAL_CHANCES,cal_failures++
  • 否则抛出异常.
• FAULT_ERROR:
  • FATAL(“Unable to execute target application (‘%s’)”, argv[0]);
• FAULT_NOINST:
  • FATAL(“No instrumentation detected”);
• FAULT_NOBITS:
  • useless_at_start++.
  • 如果没有-B指定初始in_bitmap且没有设置AFL_SHUFFLE_QUEUE
    • WARNF(“No new instrumentation output, test case may be useless.”);

计算所有初始输入样例的校准结果

如果cal_failures == queued_paths抛出异常,cal_failures * 5 > queued_paths抛出警告

cull_queue

精简队列,挑选出fav_factor高且能覆盖所有已发现路径的测试样例.
采用的是贪心算法,依次遍历到的每条路径都选最好的测试样例,有些路径在此前遍历中挑选出的测试样例已经能产生了,则不再遍历.

• 如果是dumb_mode或没有评分改变(!score_changed)则直接返回
• 设置score_changed = 0;queued_favored = 0;pending_favored = 0;初始化一个temp_v数组,作用和virgin_bits相似,不过每条路径只占一比特(去除计数信息).
• 遍历所有测试样例,设置q->favored=0
• 遍历top_rated的每个字节(每条路径已发现的评分最高样例),若该路径在temp_v中仍置位
  • 在temp_v中去掉该样例的trace_mini中的路径.
  • 设置该样例的favored=1,queued_favored++.
  • 如果该样例还没有进行过fuzz
    • pending_favored++
• 遍历所有测试样例,设置q->fs_redundant=!favored,根据是否冗余创建或删除out_dir/queue/.state/redundant_edges/fname.

show_init_stats

在处理输入目录的末尾显示统计信息，以及一堆警告,以及几个硬编码的常量

find_start_position

如果是resuming_fuzz,则尝试恢复要开始的队列位置保存到seek_to.这仅在resume时以及当我们可以找到原始的fuzzer_stats时才有意义.

• if(in_place_resume)
  • 从out_dir/fuzzer_stats恢复
• 否则从in_dir/../fuzzer_stats中恢复
• 读取文件内容寻找cur_path,若未找到或cur_path大于当前队列长度,返回0,否则返回cur_path.

write_stats_file

更新统计信息文件outdir/fuzzer_stats

fprintf(f, "start_time        : %llu\n"
           "last_update       : %llu\n"
           "fuzzer_pid        : %u\n"
           "cycles_done       : %llu\n"
           "execs_done        : %llu\n"
           "execs_per_sec     : %0.02f\n"
           "paths_total       : %u\n"
           "paths_favored     : %u\n"
           "paths_found       : %u\n"
           "paths_imported    : %u\n"
           "max_depth         : %u\n"
           "cur_path          : %u\n" /* Must match find_start_position() */
           "pending_favs      : %u\n"
           "pending_total     : %u\n"
           "variable_paths    : %u\n"
           "stability         : %0.02f%%\n"
           "bitmap_cvg        : %0.02f%%\n"
           "unique_crashes    : %llu\n"
           "unique_hangs      : %llu\n"
           "last_path         : %llu\n"
           "last_crash        : %llu\n"
           "last_hang         : %llu\n"
           "execs_since_crash : %llu\n"
           "exec_timeout      : %u\n" /* Must match find_timeout() */
           "afl_banner        : %s\n"
           "afl_version       : " VERSION "\n"
           "target_mode       : %s%s%s%s%s%s%s\n"
           "command_line      : %s\n"
           "slowest_exec_ms   : %llu\n",
        start_time / 1000, get_cur_time() / 1000, getpid(),
        queue_cycle ? (queue_cycle - 1) : 0, total_execs, eps,
        queued_paths, queued_favored, queued_discovered, queued_imported,
        max_depth, current_entry, pending_favored, pending_not_fuzzed,
        queued_variable, stability, bitmap_cvg, unique_crashes,
        unique_hangs, last_path_time / 1000, last_crash_time / 1000,
        last_hang_time / 1000, total_execs - last_crash_execs,
        exec_tmout, use_banner,
        qemu_mode ? "qemu " : "", dumb_mode ? " dumb " : "",
        no_forkserver ? "no_forksrv " : "", crash_mode ? "crash " : "",
        persistent_mode ? "persistent " : "", deferred_mode ? "deferred " : "",
        (qemu_mode || dumb_mode || no_forkserver || crash_mode ||
         persistent_mode || deferred_mode) ? "" : "default",
        orig_cmdline, slowest_exec_ms);

save_auto

保存自动生成的extras

Fuzz执行

Fuzz主循环

cull_queue

如果第一次循环或是一轮循环结束,进行新一轮fuzz的初始化

详见注释

if (!queue_cur)
{

  queue_cycle++; //进行fuzz的轮数
  current_entry = 0; 
  cur_skipped_paths = 0; 
  queue_cur = queue;

  while (seek_to) //如果是resume,从seek_to指示的位置开始fuzz
  {
    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. */
     
  /*经过上一轮fuzz后,队列中样例数没有变化
    接下来尝试重组策略
  */
  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);//从其他Fuzzer中获取有趣的测试样例(distributed mode).
}

sync_fuzzers

从其他Fuzzer的queue中读取测试样例并执行,通过save_if_interesting决定是否导入到自己的queue中.

fuzz_one

从列表中取出当前条目进行一段时间的模糊测试.成功返回0,跳过或退出返回1.

在这里插入对common_fuzz_stuff函数的提前分析,该函数会在后续变异fuzz中大量使用.

common_fuzz_stuff

• 如果在setup_post中设置了post_handler,那么这里将先调用post_handler来处理out_buf.用于在写入testcase之前，对写入内容进行封装或者映射。

  afl-fuzz适合基于字节粒度变异的fuzz，但并不是所有目标都可以直接进行字节粒度的fuzz。有些是因为文件解析部分的代码不能单独抽出来，有些是因为文件解析仅仅是逻辑的开始。那么为变异器加层就是在这方面扩展afl-fuzz的最简单方法。
  一个示例的代码可以参考gitlab/wangxin/afl-wasm/，这是一个可以为WebAssembly的wasm文件变异加层的fuzzer。这个工具产生的样本如下所示，其中变异的部分是wasmCode中的字节码，而外围的JavaScript代码需要手动编写，而且要求外围代码应该尽量复杂。

• 调用write_to_testcase将变异出的数据写入out_file
• 调用run_target执行程序,保存返回值到fault.
• 接下来处理fault
  • FAULT_TMOUT:
    • 如果subseq_tmouts++ > TMOUT_LIMIT
      • cur_skipped_paths++,返回1
    • 否则设置subseq_tmouts = 0
• 如果用户通过SIGUSR1要求丢弃当前输入,cur_skipped_paths++并返回1.
• queued_discovered += save_if_interesting(argv, out_buf, len, fault).
• 返回0.

save_if_interesting

/* Check if the result of an execve() during routine fuzzing is interesting,
   save or queue the input test case for further analysis if so. Returns 1 if
   entry is saved, 0 otherwise. */

• 如果fault == crash_mode(FAULT_NONE,若指定了-C则为FAULT_CRASH)
  • 调用has_new_bits分析执行结果并更新virgin_bits.
  • 如果本次运行没有导致新的virgin_bits置位
    • 如果指定了-C,total_crashes++
    • 否则返回0
  • 否则调用add_to_queue加入队列.
  • 如果新的virgin_bits置位的原因是有新的路径产生
    • queue_top->has_new_cov=1,queued_with_cov++.(queue_top就是刚加入的变异样例)
  • 根据当前trace_bits计算queue_top->exec_cksum
  • 调用calibrate_case对当前样例进行校准(calibrate)
  • 写入到out_dir/queue/id:queued_paths,describe_op(hnb)s文件中
  • kepping = 1
• 根据fault的值进行处理:
  • FAULT_TMOUT:
    • total_tmouts++.
    • 如果unique_hangs数量>=KEEP_UNIQUE_HANG(500),直接返回keeping.
    • 如果不在dumb_mode中
      • 调用simplify_trace简化trace_bits(为1则该字节对应的路径未发现,为128则该字节对应的路径已发现).
      • 以virgin_tmout(Bits we haven’t seen in tmouts)作为掩码对简化后的trace_bis进行has_new_bits分析(由于已经简化,此次分析对hit_count不敏感).
      • 如果没有新bit置位,则直接返回keeping.
    • unique_tmouts++(到这说明这是一个发现新路径的hang样例)
    • 在保存该样例到hang目录之前,设置更长的超时时间(EXEC_TIMEOUT)再次执行,确保该样例真正使程序挂起.
    • 如果二次执行出现了Crash,跳转到keep_as_crash.
    • 如果第二次执行不再超时,返回keeping.
    • 否则保存到hangs目录中并记录当前时间作为last_hang_time.
  • FAULT_CRASH(keep_as_crash)
    • 如果unique_crashes数量>=KEEP_UNIQUE_CRASH(5000),直接返回keeping.
    • 如果不在dumb_mode中
      • 调用simplify_trace简化trace_bits(为1则该字节对应的路径未发现,为128则该字节对应的路径已发现).
      • 以virgin_crash(Bits we haven’t seen in crashes)作为掩码对简化后的trace_bis进行has_new_bits分析(由于已经简化,此次分析对hit_count不敏感).
      • 如果没有新bit置位,则直接返回keeping.
    • 如果是发现的第一个unique_crash,调用write_crash_readme记录命令行到readme文件中
    • 保存到crashes目录中并记录当前时间作为last_crash_time.
  • FAULT_ERROR:
    • 抛出异常
  • default:返回keeping

以一定概率跳过当前样例

!fuzz_one的处理流程从这里开始!

• 如果队列中有favored且未fuzz过的样例
  • 如果当前样例已经fuzz过且不为favored,则有99%的概率被跳过
• 如果队列中没有favored的样例且队列中样例数>10且不为dumb_mode
  • 如果当前样例没有fuzz过且不为第一轮fuzz,有75%的概率被跳过
  • 否则有95%的概率被跳过

将当前测试样例读入到mmap开辟的origin_in缓冲区中.

CALIBRATION阶段(仅当早前校准失败)

• 如果当前样例之前校准失败且失败次数小于CAL_CHANCES(3)
  • 设置queue_cur->exec_cksum = 0;并调用calibrate_case进行校准.

TRIMMING阶段

如果不为dumb_mode且当前样例没有修剪完成,调用trim_case进行修建

trim_case

• 如果样例长度小于5,直接返回
• 一些初始化工作

    stage_name = tmp; //将stage_name指向tmp缓冲区
    bytes_trim_in += q->len; //被修剪过的字节数+=q->len
  
    /* Select initial chunk len, starting with large steps. */
  
    len_p2 = next_p2(q->len); //将q->len向上对齐到2的幂.
  
  //设置单次修剪长度为len_p2/16,最小为4.
    remove_len = MAX(len_p2 / TRIM_START_STEPS, TRIM_MIN_BYTES);

• 进入大循环,直到remove_len小于len_p2/1024,每次循环修剪长度会/2.
  • 内层循环的初始化工作
    • remove_pos=remove_len. stage_cur = 0;stage_max = q->len / remove_len;
  • 内层循环,直到remove_pos>=q->len为止.
    • 更新本次课修剪的长度为MIN(remove_len,q->len-remove_pos)
    • 调用write_with_gap,跳过从remove_pos开始长度为trim_avail的部分写入out_file
    • 调用run_target执行一次程序,trim_execs++.
    • 分析本次执行结果
      • 计算cksum,若未发生改变,意味着本次修剪对该样例产生的路径信息无影响
        • 保留修剪结果.更新q->len并重新计算len_p2.
        • 如果是第一次修剪成功(cksum不改变),保存本次执行的trace_bits至clean_trace用于之后的评分.
      • 否则remove_pos+=remove_len,修剪下一位置.
    • 每执行修剪stats_update_freq次,调用一次show_stats.
    • stage_cur++
  • 本轮修剪完成,设置下一轮修剪长度,remove_len >> = 1.
• 大循环结束,如果有修剪成功的结果,写回原队列文件(之前写入的是out_file).
• 将clean_trace拷贝到trace_bits,调用update_bitmap_score对更新后的队列进行评分.

设置queue_cur->trim_done=1,更新queue_cur->len.拷贝in_buf到out_buf

PERFORMANCE SCORE阶段

calculate_score

没啥分析的,直接引用一下Sakura师傅.

根据queue entry的执行速度、覆盖到的path数和路径深度来评估出一个得分，这个得分perf_score在后面havoc的时候使用。
前面的没什么好说的，这里的q->depth解释一下，它在每次add_to_queue的时候，会设置为cur_depth+1，而cur_depth是一个全局变量，一开始的初始值为0。
处理输入时
在read_testcases的时候会调用add_to_queue，此时所有的input case的queue depth都会被设置为1。
fuzz_one时
然后在后面fuzz_one的时候，会先设置cur_depth为当前queue的depth，然后这个queue经过mutate之后调用save_if_interesting,如果是interesting case，就会被add_to_queue，此时就建立起了queue之间的关联关系，所以由当前queue变异加入的新queue，深度都在当前queue的基础上再增加。

判断是否需要进行 deterministic fuzz

如果指定了-d选项或者该样例已经进行过fuzz或在早期(恢复)中经过了deterministic fuzz,或者是分布式模式的从fuzzer则直接进入havoc_stage阶段.

设置 doing_det = 1;

SIMPLE BITFLIP (+dictionary construction)阶段

这一阶段通过反转样例的比特位进行变异,翻转的宏如下,但看宏不好理解,结合宏调用来理解.
_bf取值为[0-len<<3],则每8次循环(_bf&7)将产生[0,1,…8]的移位序列,而^=(128 >> ((_bf)&7))即将一个字节的比特位从高到低依次翻转.
_bf>>3将stage_max重新映射回len的长度.

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

//下面为提取出的宏调用,便于理解宏.
stage_max = len << 3;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++)
    FLIP_BIT(out_buf, stage_cur);

maybe_add_auto

在这里插入对maybe_add_auto函数的提前分析.
该函数用来保存关键字到字典.

• 跳过连续的相同字节.
• 如果该关键字的值是预设的intesting value,直接返回.
• 进行大小写不敏感的查找,如果该关键字与预设的关键字重复则直接返回.
• 进行大小写不敏感的查找,如果该关键字与此前自动生成的关键字重复则增加其的hit_cnt后进行sort_a_extras.
• 否则将其加入a_extras(自动生成的关键字数组).如果已满则替换掉下标为 MAX_AUTO_EXTRAS / 2 +UR((MAX_AUTO_EXTRAS + 1) / 2)的关键字.
• sort_a_extras:
  • 先将a_extras按照hit_cnt进行递减排序(保证发生替换时被替换的关键字hit_count较小).
  • 再按len对前USE_AUTO_EXTRAS(50)个关键字进行递增排序.

bitflip 1/1

SIMPLE BITFLIP (+dictionary construction)阶段从这里开始!
bitflip 1/1会额外进行字典的构建.假设关键字具有这样的特性:当某关键字中的任意一个字节(最低有效位)发生改变,会使得程序走向与原输入不同的路径,且任意字节的改变都导致走向相同的路径.

• 设置prev_cksum=queue_cur->exec_cksum
• 循环stage_max(len<<3)次,即遍历样例中的每一个比特位
  • 将该比特位翻转后调用一次common_fuzz_stuff(详见前文分析).再翻转回来.
  • 如果不在dumb_mode,则尝试收集关键字.
    • 每当翻转一个字节的最低有效位时,进行特殊处理
      • 如果cksum!=prev_cksum,说明可能进入了一个关键字或离开了一个关键字,若a_len在规定的关键字长度限制之内,调用maybe_add_auto尝试保存当前a_collect中的关键字,更新a_len=0,prev_cksum=cksum.
      • 如果ck_sum!=queue->exec_cksum,则在MAX_AUTO_EXTRA的长度限制内保存当前字节到a_collect.a_len++.
      • 如果是最后一次循环,直接调用maybe_add_auto尝试保存当前a_collect中的关键字.
  • 更新一些记录

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

bitflip 2/1

和bitflip 1/1类似,一次翻转2位.

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

bitflip 4/1

和bitflip 1/1类似,一次翻转4位.

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

bitflip 8/8

和bitflip 1/1类似,一次翻转1字节.
在这一过程中会同时完成effector map的构造,具体来说,如果一个将一个字节翻转后路径信息发生改变,将effector map中对应的位置置1,表示有效,否则置0,表示无效.在之后开销更大的阶段将会跳过这些无效字节.

如果最后有效字节的密度大于90%,则将map全部标记为有效,因为跳过并不会节约太多时间.

bitflip 16/8

和bitflip 1/1类似,一次翻转2字节,但跳过effector map中两个连续的无效字节.

bitflip 32/8

和bitflip 1/1类似,一次翻转4字节,但跳过effector map中四个连续的无效字节.

ARITHMETIC INC/DEC阶段

arith 8/8

对每一个byte,分别加上及减去从0到ARITH_MAX(35)的整数后进行common_fuzz_stuff.其中会跳过effector map中指示无效的和之前已经由bitflip阶段产生过的输入.

判断是否产生过是通过could_be_bitflip函数,方法是将原数据异或上运算后的数据得到结果val,将其右移直到最低有效位为1(即原数据与运算后数据不同的第一个比特位).此时根据val中连续为1的比特位位数是否对应翻转阶段的步长(1,2,4,8,….)来判断此数据是否已经产生过.

arith 16/8

对每一个word,分大端序和小端序两种情况,均分别加上及减去从0到ARITH_MAX(35)的整数后进行common_fuzz_stuff.其中会跳过effector map中指示无效的和之前已经由bitflip阶段产生过的输入以及加减后仅影响最低1字节的(此情况已在arith 8/8中处理).

arith 32/8

对每一个dword,分大端序和小端序两种情况,均分别加上及减去从0到ARITH_MAX(35)的整数后进行common_fuzz_stuff.其中会跳过effector map中指示无效的和之前已经由bitflip阶段产生过的输入以及加减后仅影响最低2字节的(此情况已在arith 16/8中处理).

INTERESTING VALUES阶段

interest 8/8

以byte为单位将原数据替换为interest.跳过之前阶段中产生过的数据.

interest是一些特殊的数据

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

interest 16/8

以word为单位将原数据替换为interest.跳过之前阶段中产生过的数据.

interest 32/8

以dword为单位将原数据替换为interest.跳过之前阶段中产生过的数据.

DICTIONARY STUFF阶段

user extras (over)

• 遍历原输入中的每一个字节作为起始替换点
  • 遍历所有预设关键字
    • 如果下列条件满足其一 1)当前替换点没有足够空间进行替换 2)当前将要被替换的数据与当前关键字重复 3)将要被替换的数据在effector map中标记为无效 4 )extras_cnt > MAX_DET_EXTRAS && UR(extras_cnt) >= MAX_DET_EXTRAS)
      • 跳过本次替换.
    • 否则进行替换并进行common_fuzz_stuff

user extras (insert)

• 遍历原输入中每一个字节作为插入点
  • 遍历所有预设关键字
    • 如果插入后长度不超过MAX_FILE
      • 插入并调用common_fuzz_stuff

auto extras (over)

• 遍历原输入中的每一个字节作为起始替换点
  • 遍历所有自动生成的关键字
    • 如果下列条件满足其一 1)当前替换点没有足够空间进行替换 2)当前将要被替换的数据与当前关键字重复 3)将要被替换的数据在effector map中标记为无效
      • 跳过本次替换.
    • 否则进行替换并进行common_fuzz_stuff

RANDOM HAVOC阶段

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

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

SPLICING阶段

• 如果use_splicing=1
  • 尝试拼接两个测试样例中的内容，拼接之后重新走一遍RANDOM HAVOC阶段