American Fuzzy Lop (AFL)の構造

AFLとは

American Fuzzy Lop (AFL)はファジングツールの一つです．

ファジングとはプログラムの脆弱性検査手法の一つで，簡単に言ってしまえばあるプログラムをランダムな引数で実行することを繰り返して，プログラムがクラッシュするような入力を探そうという方法です．なんとも場当たり的な対応で心許ない気もしますが，実際には洗練されたアルゴリズムを利用することで一般に良く機能します．

世の中ファジングツールは数多く存在しますが，AFLはその利用の簡単さと，何よりも何百何千というバグを実際に見つけている運用実績で有名です．最近は更新が止まっているようですが，AFLはコードが簡潔にまとまっており，AFLを参考に作られてたファジングツールも多く存在します．

AFLの技術的詳細はAFLの作者がtechnical_details.txtにまとめています．これを読むとAFLの概要は分かりますが，実際のコードに関する情報はあまりないように思うので，ここに簡単に書いてみます．

対象のAFLのバージョンは2.52bです． AFLはとりあえず実際に動かしてみた方が以下の文章の理解が進むと思います（とても簡単に利用できます）．

ソースの概要

まず，AFLのソースディレクトリには，afl-xxx.cというファイルがありますが，特にメインになるのは，

afl-gcc.c, afl-as.c, afl-as.h
afl-fuzz.c

です．前者をファジング対象のプログラムのコンパイルに利用，後者を実際のファジングに利用します．

その他のものはAFLの補助ツールになります．引数なしで実行すればそれぞれのツールのhelpが見れます．ここでは各ツールの詳細は省略して，上記の主処理部分をみていきます．

コンパイル処理 / カバレッジ計算

AFLはcoverage-based fuzzingあるいはgray-box fuzzingなどと呼ばれるファジング手法に分類されます．これは，ある入力でプログラムを実行したときのコードカバレッジを測定し，その情報を利用して次の入力を決定していく手法です．

AFLでは条件付分岐を区切りとしたコードのまとまり単位でカバレッジを計算します(branch coverage)．このために，AFLはコンパイル時にカバレッジ計算のコードをプログラムに挿入します．例えば，以下のようなプログラムがあった場合，

if (...) {
    ...
}
...

afl-gccでコンパイルすると，以下のようになります．

__log_coverage()
if (...) {
    __log_coverage()
    ...
}
__log_coverage()
...

AFLはこのcode instrumentationを，アセンブラの段階でおこないます．

afl-gccはgccの単純なラッパーで，アセンブラとしてafl-asを呼び出します． afl-asはadd_instrumentation()で，出力されたアセンブリを行ごとに処理して，条件付ジャンプ命令 (jから始まる命令)の直後にカバレッジ計算のコードを挿入します．この辺り，構文解析している訳ではないので処理がかなりシンプルです．

カバレッジ計算のコードの本体は，afl-as.hで以下のように定義されています．このコードは，適当にレジスタの退避をして，rcxにコンパイル時に生成した値を入れたあとに，__afl_maybe_logを呼び出します．

static const u8* trampoline_fmt_64 =

  "\n"
  "/* --- AFL TRAMPOLINE (64-BIT) --- */\n"
  "\n"
  ".align 4\n"
  "\n"
  "leaq -(128+24)(%%rsp), %%rsp\n"
  "movq %%rdx,  0(%%rsp)\n"
  "movq %%rcx,  8(%%rsp)\n"
  "movq %%rax, 16(%%rsp)\n"
  "movq $0x%08x, %%rcx\n"        # ここの部分($0x%08xはフォーマッタ)にfprintf()で乱数が挿入される
  "call __afl_maybe_log\n"
  "movq 16(%%rsp), %%rax\n"
  "movq  8(%%rsp), %%rcx\n"
  "movq  0(%%rsp), %%rdx\n"
  "leaq (128+24)(%%rsp), %%rsp\n"
  "\n"
  "/* --- END --- */\n"
  "\n";

afl_maybe_logはmain_payload_64内で定義されます．

technical_details.txtに書いてある通り，AFLのカバレッジの計算は以下のようになります．

cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;

ここでまず，共有メモリ(shared_mem)領域は，後述のafl-fuzzがプログラムを実行する際に確保して，環境変数経由（SHM_ENV_VAR）でファジング対象のプログラムと共有します．この共有メモリ上に，プログラムがどこにアクセスしたのかを記録していきますが，AFLでは上記のように，("今の場所" ^ "直前の場所">>1)をキーとして利用します．つまり，AFLではある地点から別の地点への遷移を記録していきます．直前の場所の値をシフトをする理由はA -> B と B -> A の遷移や，A -> A と B -> B の遷移を区別するためです．ドキュメントでは遷移 A -> B は (A, B)と，タプルとして表現されています．

AFLでは，A -> B -> C と A -> C -> B の遷移は区別されます．一方で，時系列情報は含まれていないので，A -> B -> C -> A と B -> C -> A -> B は同じカバレッジとして扱われることになります．

AFLで使用する共有メモリのサイズは64KBです．当然ながらキーが衝突する可能性がありますが，AFLは衝突は無視します（単純に同じ遷移として扱う）．ドキュメントには以下のように分岐の数が10kを超えるプロジェクトでも衝突確率が10%前後ということが書いてあります．

   Branch cnt | Colliding tuples | Example targets
  ------------+------------------+-----------------
        1,000 | 0.75%            | giflib, lzo
        2,000 | 1.5%             | zlib, tar, xz
        5,000 | 3.5%             | libpng, libwebp
       10,000 | 7%               | libxml
       20,000 | 14%              | sqlite
       50,000 | 30%              | -

カバレッジの測定には，コスト（スピードや必要メモリ量）と精度の関係にトレードオフがあります．今回カバレッジを測定する目的は，ファジング実行時の入力選択のアルゴリズムで利用するからであって，それに十分であれば厳密にカバレッジ情報を取得する意味はありません． AFLでは経験的にファジングにいい感じのカバレッジ測定をおこないます．

なお，AFLにはLLVMの中間言語レベルでcode instrumentationするafl-clang-fastや，ソースコードがないプログラムのために，QEMUのuser mode emulationを利用してカバレッジを計算するqemu-mode（ただし遅い）もあります．

ファジング処理

ファジングの本体であるafl-fuzz.cをみていきます．

main関数はおおまかには以下のようになっています．

int main(int argc, char** argv) {
  // 初期化処理
  ...
  setup_shm();
  ...
  read_testcases();
  ...
  perform_dry_run(use_argv);
  ...
  // ファジング処理
  while (1) {
    cull_queue();
    ...
    skipped_fuzz = fuzz_one(use_argv);
    ...
  }
  ...

初期化処理

いくつか主要な処理を以下で説明します．

なお，AFLは一旦中断したファジングを再開することができるので，そのための処理もおこなっています（ここでは説明は省略）．

`setup_shm()`

カバレッジ計算用の共有メモリを確保して，それを環境変数に設定します．

EXP_ST void setup_shm(void) {
  ...
  shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);
  ...
  shm_str = alloc_printf("%d", shm_id);
  if (!dumb_mode) setenv(SHM_ENV_VAR, shm_str, 1);
  ...
  trace_bits = shmat(shm_id, NULL, 0);
  ...
}

trace_bitsが作成した共有メモリで，これにカバレッジの情報が記録されます．この共有メモリのサイズはu8 [65536]です． trace_"bit"という名称ですが，実際には遷移(A,B)のタプルの出現回数を8bitで計数します．

ちなみにdumb_modeはコンパイル時のcode instrumentationを使用しないモードです（当然効率は落ちる）．

`read_testcases()`

inputで指定したディレクトリから全てのテストケースを読み込みます． AFLでは，以下のqueueでテストケースを管理します． queueのエントリはファイルの情報の他に，そのファイルに対するファジングの情報を保持しています．

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

};

`perform_dry_run()`

static void perform_dry_run(char** argv) {
  struct queue_entry* q = queue;
  ...
  while (q) {
    ...
    res = calibrate_case(argv, q, use_mem, 0, 1);
    ...
    q = q->next;
  }
  ...
}

ファジングを始める前にinputのtest caseを使ってターゲットプログラムを実行します．これの目的は，test caseのカバレッジ情報を取得することの他に，inputにクラッシュするようなテストケースがないか（AFLはクラッシュするテストケースは，ファジングの入力候補としては利用しません）や，test caseがタイムアウトしてしまわないか（この場合は，afl-fuzzに与えたタイムアウト条件が厳しすぎるかもしれない）などを調べるためです．

実際にプログラム実行を担当するのは後述のcalibrate_case()です．

`calibrate_case()`

static u8 calibrate_case(char** argv, struct queue_entry* q, u8* use_mem,
                         u32 handicap, u8 from_queue) {
  ...
  // forkserverの初期化
  if (dumb_mode != 1 && !no_forkserver && !forksrv_pid)
    init_forkserver(argv);
  ...
  for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
    ...
    // ターゲットの実行
    fault = run_target(argv, use_tmout);
    ...
    // カバレッジのbitmapのハッシュ値の比較
    cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

    if (q->exec_cksum != cksum) {

      u8 hnb = has_new_bits(virgin_bits);
      if (hnb > new_bits) new_bits = hnb;

      if (q->exec_cksum) {

        u32 i;

        for (i = 0; i < MAP_SIZE; i++) {

          // 最初のトレース結果と異なるbitmapの箇所はマークする
          // この情報はstatsに使用
          if (!var_bytes[i] && first_trace[i] != trace_bits[i]) {

            var_bytes[i] = 1;
            stage_max    = CAL_CYCLES_LONG;

          }

        }

        var_detected = 1;

      } else {

        // 一番最初の実行結果は`first_trace`に保存
        q->exec_cksum = cksum;
        memcpy(first_trace, trace_bits, MAP_SIZE);

      }

    }

  }
  ...
}

まず，この関数を最初に実行した場合は，init_forkserver()で後述のfork serverの初期化をおこないます．

その後，ループで複数回ターゲットプログラムを実行し，コードのカバレッジや実行時間を測定します．複数回実行する理由は，プログラムによっては同じ入力でも実行する度にコードパスや実行時間が変化する可能性があるからです（例えば内部で何か乱数に応じた処理をしている場合など）．

run_target()を実行すると，trace_bitsに実行したカバレッジのbitmapが格納されます．その後，前に実行したtrace_bitsのハッシュ値と，新規に得られたtrace_bitsのハッシュ値が異なる場合は，has_new_bits(virgin_bits)で新規のパスがカバレッジのbitmapに含まれているかを確認します．

virgin_bitsは最初全て1のglobalなbitmapです． has_new_bits()はtrace_bitsに今まで観測しいていない情報が含まれているかを調べ，もしあったらvirgin_bitsを更新します． has_new_bits()はtrace_bitsに新しいタプル（遷移）が含まれていたら2を，すでにタプルは観測済みだが計数結果が更新された場合は1を返します．

`run_target()`およびfork server

run_target()はファジング対象のプログラムを実行します． fork serverを使う方法と使わない方法がありますが，ここでは使う場合を説明します．

まず，そもそもの話として，ファジング対象のプログラムをどうやって実行するのかという話があります．代表的な方法はfork+execveを使用してファジング対象のプロセスを生成して実行する方法で，AFLもデフォルトでこの方式を利用します．この方式はターゲットのプログラムの修正が必要がなく，簡単に利用できる一方で，fork+execveはオーバヘッドが大きいことで知られており，また，そもそもプログラムの初期化に時間がかかり，ファジングしたい箇所に到達するまでに時間がかかるということもあります．

別の方法として，もしファジングしたい処理が関数として呼び出し可能であれば，それをファジングするプロセスから呼び出すという方法が考えられます．この方式はファジング対象のプログラムを呼び出すための処理を自分で書く必要がありますが，fork+execveや初期化のオーバヘッドが無く，高速にファジング対象を実行することができます．ただし，何か関数がグローバルな状態に依存するような場合は注意が必要です．クラッシュ時の対応も別途考える必要があります．例えばLibFuzzerはデフォルトでこの方式でファジングをします． AFLも，"persistent mode"という名称でこの機能をサポートしています．

さて，前述のようにAFLではデフォルトではfork+execveでプロセスを実行しますが，少しでもオーバヘッドを削減するために，fork serverという仕組みを利用します．これは，fork+execveでターゲットプログラムを実行しますが，ターゲットプログラムはエントリポイント（正確には最初にカバレッジを記録する箇所）でファジング側の指示を待つために停止します．その後，ファジング側の指示を受信すると，ターゲットプログラムはその止まっていた箇所から新たにfork()して，子プロセスが処理を続けます．こうすることで，execveやダイナミックリンクのオーバヘッドを避けてターゲットプログラムを実行することができます．ファジングプロセスとの通信やforkするためのコードはafl-gccでコンパイルした際に仕込みます．

AFLはinit_forkserver()でforkしたのち，メモリ制限などをかけた上でexecveでターゲットプログラムを起動します．このとき，dup(2)を使って制御通信用のfile descriptorを用意しています．

EXP_ST void init_forkserver(char** argv) {
  ...
  forksrv_pid = fork();
  ...
  if (!forksrv_pid) {

    struct rlimit r;

    /* Umpf. On OpenBSD, the default fd limit for root users is set to
       soft 128. Let's try to fix that... */

    if (!getrlimit(RLIMIT_NOFILE, &r) && r.rlim_cur < FORKSRV_FD + 2) {

      r.rlim_cur = FORKSRV_FD + 2;
      setrlimit(RLIMIT_NOFILE, &r); /* Ignore errors */

    }

    if (mem_limit) {

      r.rlim_max = r.rlim_cur = ((rlim_t)mem_limit) << 20;

      setrlimit(RLIMIT_AS, &r); /* Ignore errors */

    }

    /* Dumping cores is slow and can lead to anomalies if SIGKILL is delivered
       before the dump is complete. */

    r.rlim_max = r.rlim_cur = 0;

    setrlimit(RLIMIT_CORE, &r); /* Ignore errors */

    /* Isolate the process and configure standard descriptors. If out_file is
       specified, stdin is /dev/null; otherwise, out_fd is cloned instead. */

    setsid();

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

    }

    /* Set up control and status pipes, close the unneeded original fds. */

    if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed");
    if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed");

    close(ctl_pipe[0]);
    close(ctl_pipe[1]);
    close(st_pipe[0]);
    close(st_pipe[1]);

    close(out_dir_fd);
    close(dev_null_fd);
    close(dev_urandom_fd);
    close(fileno(plot_file));

    /* This should improve performance a bit, since it stops the linker from
       doing extra work post-fork(). */

    if (!getenv("LD_BIND_LAZY")) setenv("LD_BIND_NOW", "1", 0);

    /* Set sane defaults for ASAN if nothing else specified. */

    setenv("ASAN_OPTIONS", "abort_on_error=1:"
                           "detect_leaks=0:"
                           "symbolize=0:"
                           "allocator_may_return_null=1", 0);

    /* MSAN is tricky, because it doesn't support abort_on_error=1 at this
       point. So, we do this in a very hacky way. */

    setenv("MSAN_OPTIONS", "exit_code=" STRINGIFY(MSAN_ERROR) ":"
                           "symbolize=0:"
                           "abort_on_error=1:"
                           "allocator_may_return_null=1:"
                           "msan_track_origins=0", 0);

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

  }

  ...
}

ターゲットプログラム側の処理はafl-as.hで定義されています． run_target()では，init_forkserver()で用意したfile descriptorを利用してターゲットのプロセスにメッセージを送ることで実際のファジングを開始します．

static u8 run_target(char** argv, u32 timeout) {
  ...
    s32 res;

    /* In non-dumb mode, we have the fork server up and running, so simply
       tell it to have at it, and then read back PID. */

    // ターゲットプログラム側に処理実行をリクエスト
    if ((res = write(fsrv_ctl_fd, &prev_timed_out, 4)) != 4) {

      if (stop_soon) return 0;
      RPFATAL(res, "Unable to request new process from fork server (OOM?)");

    }

    if ((res = read(fsrv_st_fd, &child_pid, 4)) != 4) {

      if (stop_soon) return 0;
      RPFATAL(res, "Unable to request new process from fork server (OOM?)");

    }

    if (child_pid <= 0) FATAL("Fork server is misbehaving (OOM?)");
  ...
    // 実行結果のstatus codeをターゲットプログラムから受信する
    if ((res = read(fsrv_st_fd, &status, 4)) != 4) {

      if (stop_soon) return 0;
      RPFATAL(res, "Unable to communicate with fork server (OOM?)");

    }
  ...
  classify_counts((u64*)trace_bits);
}

run_target()では最後にclassify_counts()という関数を読んでいますが，この関数はカバレッジの計数結果を以下の8つに分類します．

  1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+

つまり，AFLでは例えばあるA -> Bという遷移を5回実行したものと，6回実行したものは区別しません．これは例えばたくさんループ処理するような場合で，少しだけループ回数が変わってもそれは別のパスとは考えないということになります．

このfork serverを応用すると，プログラムの途中まで処理を進めておいて，ファジングを開始したい箇所まできたら実行を中断し，あとはafl-fuzzの指示に応じてfork()してファジングするということが考えられます． AFLはこの"deferred mode"をサポートしており，LLVMを利用してinstrumentationする場合に利用できます（参考: llvm_mode）．

ちなみに，fork serverを使ってもファジングを実行する度にforkはすることになります． AFLはマルチコアでのファジングをサポートしていますが，fork（や結果の同期）が遅くてスケールしにくいということが研究で指摘されています[1]．

[1] Wen Xu et al., Designing New Operating Primitives to Improve Fuzzing Performance, https://taesoo.kim/pubs/2017/xu:os-fuzz.pdf, CCS'17.

Culling

AFLはキューの先頭から一つ一つ順番に入力を選択し，ファジングをしていきます．そして，ファジングによって新しいカバレッジを持つを入力が得られたらそれをキューに新規に追加します．

AFLは一度追加したエントリを削除することはしませんが，効率良くファジングを実行するために，エントリの中で特に有力そうなものをfavoredとして優先的に処理するようにチェックします．この処理をcullingと呼び，cull_queue()および，update_bitmap_score() (この関数はcalibrate_case()から呼ばれる)がその処理を実行します．アルゴリズムはtechnical_details.txtの4 Culling the corpusに書いてあります．

ざっくりというと，AFLは (プログラムの実行時間) * (入力のサイズ)をスコアとして，それぞれのカバレッジのbitに対して，そのスコアが最も小さいものをfavoredであるとします．

culling処理は新規に入力がキューに追加される度にに実行されます．

ファジング処理

fuzz_one() がファジング処理の本体です． AFLは遺伝的アルゴリズムをベースとして，おおまかには以下のようにファジング処理をおこないます．

fuzz_one(){
    1. favoredなtest caseが存在するかを確認
    2. calibration
    3. input trimming
    4. performance scoreの計算
    5. deterministic phase
       - bitflip
       - interest
       - dctionary
    6. non-deterministic phase
       - havoc
       - splice
}

AFLは，ファジングで使用する入力を一つキューから選択した後，その入力に対して，ある変換を適用+ファジング対象のプログラムを実行する，ということを複数回おこないます．そして，得られたカバレッジが今まで観測してたことのないパスを含んでいた場合にのみ，その新しい入力をキューに追加します．名前が紛らわしいかもしれまんせんが，fuzz_one()では一回だけ入力を改変して実行する，ということをおこなっている訳ではありません．

一般的な遺伝的アルゴリズムでは，世代ごとにどんどん個体が入れ替わっていきますが，AFLでは積極的にtest caseを入れ替えることはしません．実験的にその方が結果が良いようです．

以下でそれぞれの処理を説明します．

favoredなtest caseが存在するかを確認

前述したculling処理で，キューのエントリはそれぞれfavoredであるかどうかチェックされています．もしfavoredでない場合は，一定確率に応じてその入力に対するファジングをスキップします．

calibration

perform_dry_runで実行したcalibrationと同じです．事前のcalibrate_case()が失敗した場合，もう一度ここでcalibrationを試みるようです．それでもcalibrationに失敗したら，このtest caseについてはファジングを諦めます．

input trimming

ファジングの入力はサイズが小さい方が，一般にターゲットプログラムの実行時間が短くなるので望ましいです． fuzz_one()ではこの後なんどもファジングをしていくので，その前に入力のファイルサイズの削減を試みます．これは単純に適当の連続領域を削除して，実行のカバレッジのハッシュ値が同じであったら実行結果が同じと判断するという戦略になっています．

なお，afl-tmin.cにもう少し良いアルゴリズム（ただし時間がかかる）が実装されています．

performance scoreの計算

平均実行時間などからperformance scoreを計算します．この値は後述のhavoc stageで入力の改変のパラメータとして利用されます．（実行時間が長いと，havoc stageの回数を減らす）．

Deterministic / Non-deterministic phase

ここからいよいよファジングを実行していきます．

AFLが施す入力に対する変換は，決定的なもの(deterministic)と，非決定的なものの二種類に分けられます．決定的な処理にはbitflipであったり，事前に与えたdictionaryの情報を使った書き換えなどをします．この決定的な処理によって，効率よく入力のmagic number領域や，データ領域を推定することができます．非決定的な処理は，一般の遺伝的アルゴリズムに近い，ランダムな変換処理をおこないます．

この処理はAFLで一番重要とも言える処理ですが，具体的なアルゴリズムは参考文献に詳しく書いてあるので，そちらを参照してください．

一度deterministic phaseをおこなうと，キューのpassed_detが1になるので，それに対しては今後deterministic phaseはおこなわなくななります．

`common_fuzz_stuff()`

deterministic phase, non-deterministic phaseともに，common_fuzz_stuff()という関数で実際のファジング処理を実行します．この関数は前述のrun_target()でターゲットプログラムを実行したのち，save_if_interesting()で実行結果を確認します．

EXP_ST u8 common_fuzz_stuff(char** argv, u8* out_buf, u32 len) {
  ...
  fault = run_target(argv, exec_tmout);
  ...
  queued_discovered += save_if_interesting(argv, out_buf, len, fault);
  ...
}

save_if_interesting()は前述したhas_new_bits()で実行結果が新しいコードパスを含んでいるかどうかを調べ，そうであればキューに新規にエントリを追加します．また，このタイミングでcalibrate_case()でcalibrationもおこないます．

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

static u8 save_if_interesting(char** argv, void* mem, u32 len, u8 fault) {
    ...
    if (!(hnb = has_new_bits(virgin_bits))) {
      if (crash_mode) total_crashes++;
      return 0;
    }    
    ...
    add_to_queue(fn, len, 0);
    ...
    res = calibrate_case(argv, queue_top, mem, queue_cycle - 1, 0);
    ...
}

ここでは省略していますが，もしクラッシュした場合は，その旨を記録します．

まとめ

AFLの構造について簡単に説明しました．ソースを見ればわかる通り，AFLは効率的なファジングのために様々なヒューリスティクスの塊となっています．ファジングのアルゴリズム本体以外にも，どう効率よくファジングをするかという工夫が随所に入っており，非常に面白いと思います．

最近はAFLよりももっと活発に開発され，より効率の良いとされるファジングツールもありますが，AFLは非常に使いやすく，まだまだ十分有用だと思います．

AFLの拡張

最後にAFLを拡張したものについて，いくつか紹介します，

近年AFLをベースにしたファジングツールの研究・開発が多く存在します．ソースが公開されていて著名なものには以下のようなものがあります（他にもあります）．

aflfast
- Marcel Boehme et al., Coverage-based Greybox Fuzzing as Markov Chain, CCS'16
- AFLのシード選択方法（スケジューラ）の改善
driller
- Nick Stephens et al., Driller: Augmenting Fuzzing Through Selective Symbolic Execution, NDSS'16
- AFLとSymbolic executionの組み合わせ
aflgo
- Marcel Boehme et al., Directed graybox fuzzing, CCS'17
FairFuzz
- Caroline Lemieux et al., FairFuzz: A Targeted Mutation Strategy for Increasing Greybox Fuzz Testing Coverage, ASE'18
aflsmart
- Van-Thuan Pham et al., Smart Greybox Fuzzing, https://arxiv.org/abs/1811.09447, 2018.
- AFLをgrammar（ファイルの構造）awareに拡張
winafl
- Windows用のAFL fork

AFL以外にもファジングツールは多く存在します．例えばgithubで検索すればたくさん見つかります． AFLは一般のユーザランドアプリケーションが対象ですが，最近は他の用途に特化したもの，例えばネットワークプロトコルや，Javascriptエンジン，さらにはカーネル向けのものなど，様々なものが開発されています．

参考文献

AFLのdocs
- 特にtechnical_details.txt
作者のBlog
- AFLを含むエントリ
AFLのmutation戦略について
- Michal Zalewski, Binary fuzzing strategies: what works, what doesn't, https://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html
- shimasyaro, American Fuzzy Lop internals, http://shimasyaro.hatenablog.com/entry/2018/03/26/184415
  - 貴重な日本語でのAFLのmutation戦略の解説．詳しい．
- rk700, AFL内部实现细节小记, http://rk700.github.io/2017/12/28/afl-internals/
- rk700, AFL文件变异一览, http://rk700.github.io/2018/01/04/afl-mutations/
  - 中国語だけどgoogle 翻訳すれば割と読める．わかりやすい．
その他
- Brendan Dolan-Gavitt, Fuzzing with AFL is an Art, http://moyix.blogspot.com/2016/07/fuzzing-with-afl-is-an-art.html
  - AFLの構造というよりかは，AFLを使用する場合（というか一般にファジングをする場合に）気をつけるべき点やテクニックが書いてある

AFLとは

ソースの概要

コンパイル処理 / カバレッジ計算

ファジング処理

初期化処理

setup_shm()

read_testcases()

perform_dry_run()

calibrate_case()

run_target()およびfork server

Culling

ファジング処理

favoredなtest caseが存在するかを確認

calibration

input trimming

performance scoreの計算

Deterministic / Non-deterministic phase

common_fuzz_stuff()

まとめ

AFLの拡張

参考文献

`setup_shm()`

`read_testcases()`

`perform_dry_run()`

`calibrate_case()`

`run_target()`およびfork server

`common_fuzz_stuff()`