Zenn
Open7

aflを読み解く

ファジング
afl
hysok2hysok2

update_bitmap_scoreのコメント の開始行

AFLのファジング戦略の一つの「favorables」を紹介。ファジングを行う元のシードの中から「favorables」というよりすぐりのシードたちを選定しそれらを優先しファジングする。
Favorablesなシードでプログラムを実行すると、過去のファジングで通った組（カバレッジ）すべてを通る。
そのような過去のファジングで通った組（カバレッジ）すべてを通るシードの集合を考えたとき、その中で最小のものがfavorablesとなるようメンテされる。

hysok2hysok2

Culling the corupus
ファジングの効率を上げるため、シードの実行時間やシードのサイズが小さいものが、favorablesに選ばれる。

ファジングはfavorablesなシードを優先し行われる。favorablesでないシードは削除されない。低い確率でファジングに利用される。

  • favorablesなものがある場合、favorableでないシードをスキップされる確率は99%
  • favorablesがない場合、現在のfavorableでないシードが以前にファジングされたものである場合、スキップされる確率は95%。
  • favorablesがない場合、現在のfavorableでないシードが以前にファジングされていないものである場合、スキップされる確率は75%。
hysok2hysok2

Ctrl-cで停止する処理
afl-fuzz.c 2624

    /* stop_soon is set by the handler for Ctrl+C. When it's pressed,
       we want to bail out quickly. */

    if (stop_soon || fault != crash_mode) goto abort_calibration;

    if (!dumb_mode && !stage_cur && !count_bytes(trace_bits)) {
      fault = FAULT_NOINST;
      goto abort_calibration;
    }
hysok2hysok2

1015行

static u32 count_bytes(u8* mem) {

概要：trace_bitsをみて、カバレッジがたった箇所数を計算。count_bytesの結果が高いテスト入力が望ましいとされファジング元と選ばれやすい。

hysok2hysok2

https://github.com/google/AFL/blob/master/afl-fuzz.c#L1316

static void cull_queue(void)

/* The second part of the mechanism discussed above is a routine that
   goes over top_rated[] entries, and then sequentially grabs winners for
   previously-unseen bytes (temp_v) and marks them as favored, at least
   until the next run. The favored entries are given more air time during
   all fuzzing steps. */
static void cull_queue(void) {

  struct queue_entry* q;
  static u8 temp_v[MAP_SIZE >> 3];
  u32 i;

  if (dumb_mode || !score_changed) return;

  score_changed = 0;

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

  queued_favored  = 0;
  pending_favored = 0;

  q = queue;

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

  /* Let's see if anything in the bitmap isn't captured in temp_v.
     If yes, and if it has a top_rated[] contender, let's use it. */

  for (i = 0; i < MAP_SIZE; i++)
// top_rated[i] に入力が記録されていて、i番目tupleに当たるtemp_vのbitが１
//（該当tupleがまだtemp_vに記録されていない）
    if (top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {

      u32 j = MAP_SIZE >> 3;

      /* Remove all bits belonging to the current entry from temp_v. */

      while (j--) 
        if (top_rated[i]->trace_mini[j])
// top_rated[i]の入力が触るtupleをtemp_vに記録。
// 以降、temp_vに記録されたtupleのtop_ratedは、スルーされる。
//top_rated[i]から触られるため。
          temp_v[j] &= ~top_rated[i]->trace_mini[j];

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

      if (!top_rated[i]->was_fuzzed) pending_favored++;

    }

  q = queue;

  while (q) {
    mark_as_redundant(q, !q->favored);
    q = q->next;
  }

}