AFL 遗传思想分析

Fuzz的中间结果是如何影响变异过程.
主要内容摘抄自AFL 源码分析

基本思想还是变异+执行, 判断覆盖率的变化.

总结

总结下来就这几种.

queue_entry->favored: 决定用例被fuzz的概率
eff_map: 决定变异过程中侧重变异的比特位
save_if_interesting: 变异出的用例是否加入队列
a_extras: 位翻转界面产生的字典

相关过程

首先调用add_to_queue, 在queue_entry中记录文件元信息.

struct queue_entry* q = ck_alloc(sizeof(struct queue_entry));

q->depth        = cur_depth + 1;
q->passed_det   = passed_det;

queued_paths++; /* Total number of queued testcases */
pending_not_fuzzed++;  /* Queued but not done yet          */

cycles_wo_finds = 0;  /* Cycles without any new paths     */

last_path_time = get_cur_time();

然后在perform_dry_run过程中调用calibrate_case对其进行校准.

calibrate_case循环运行stage_max次, 记录该用例的first_trace和在同一用例下多次运行表现出不同覆盖率的路径var_bytes.
一个用例校准完成后的相关更新:

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 (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++;
  }

}

其中一个与遗传算法相关的函数是update_bitmap_score,直接看之前写的分析:

/* When we bump into a new path, we call this to see if the path appears
   more "favorable" than any of the existing ones. The purpose of the
   "favorables" is to have a minimal set of paths that trigger all the bits
   seen in the bitmap so far, and focus on fuzzing them at the expense of
   the rest.

   The first step of the process is to maintain a list of top_rated[] entries
   for every byte in the bitmap. We win that slot if there is no previous
   contender, or if the contender has a more favorable speed x size factor. */

static void update_bitmap_score(struct queue_entry* q) {

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

判断是否更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

然后进行cull_queue, 挑选出fav_factor高且能覆盖所有已发现路径的测试样例.
采用的是贪心算法,依次遍历到的每条路径都选最好的测试样例,有些路径在此前遍历中挑选出的测试样例已经能产生了,则不再遍历. 并标记top_related[i]->favored = 1.

在fuzz_one中,

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

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

在bitflip 8/8过程中会同时完成effector map的构造,具体来说,如果一个将一个字节翻转后路径信息发生改变,将effector map中对应的位置置1,表示有效,否则置0,表示无效.在之后开销更大的阶段将会跳过这些无效字节.
如果最后有效字节的密度大于90%,则将map全部标记为有效,因为跳过并不会节约太多时间.