AFLについての簡単な考察

AFL の全称は American Fuzzy Lop で、コードカバレッジに基づいたプログラムのファジングテストツールです。ユーザーが指定したテストケースと変異（mutation）によって得られたテストケースをプログラムに入力することで、プログラムコードのカバレッジを取得し、そのカバレッジ状況をテストケースの選択と変異プロセスにフィードバックすることにより、コードカバレッジを継続的に向上させ、最終的にはコード内の脆弱性を発見する可能性を高めます。

まず、AFL のいくつかの特徴をまとめます：

コードインストゥルメンテーション（instrument）を通じて、各テストケースがプログラムに入力された後のコードカバレッジを記録します。
様々な手段を用いて、大量のテストケースを精選します。
遺伝的アルゴリズムに似ており、Fuzz プロセス中に既存のテストケースを変異させて新しいケースを生成します。

プロセスの相互作用#

最も単純な場合、AFL の Fuzz プロセス（campaign）は 3 つのプロセスが協力して実行されます：

Fuzzer：コード実装は afl-fuzz.c ファイルにあり、Fuzz のメインプログラムです。テストケースのキューを維持し、テスト中にケースをプログラムに入力するためにスケジュールします。Fork Server は Fuzzer の子プロセスであり、Fuzzer からフォークされます。これは Fuzz プロセス中の唯一の 2 つのフォークシステムコールです（ダムモードを除く）。
Fork Server：自身にソースファイルはなく、そのコードは afl-as によって Target のアセンブリコードに挿入されます。これはテスト対象プログラム Target のラッパーと見なすことができ、Fuzzer からフォークされた後に常駐し、Fuzzer との間に双方向通信のための 2 つのパイプを確立します。さらに、Fork Server は Fuzzer と共有メモリ（shared memory）を使用してコードカバレッジ情報を伝達します。
Target：Target のプロセスインスタンスは Fork Server からフォークされます。各分岐、ループ構造はインストゥルメンテーションされ、挿入されたコードはコード実行のカバレッジ状況を共有メモリに書き込み、Fuzzer が読み取ります。

これら 3 つの役割のフローチャートは以下の通りです。

インストゥルメンテーション#

プログラムのインストゥルメンテーションは基本的な動的分析手法であり、コードにプローブ（hook）コードを挿入することでプログラム実行時のコンテキスト情報を取得します。ソースコードに対してインストゥルメンテーションを行うことも、中間コードやバイナリコードに対して行うこともできます。AFL は 2 つのインストゥルメンテーションモードを提供します：

テスト対象プログラムのソースコードからコンパイルされたアセンブリコード（.s）ファイルを直接読み取り、重要な命令 / 擬似命令の後にインストゥルメンテーションするコードを挿入します。
インストゥルメンテーションプロセスを LLVM の Pass として実装します（私のローカルで llvm-mode をコンパイルするのに何度も失敗したため、ここでは省略します）。

AFL はインストゥルメンテーションを通じてコード実行のパスカバレッジを取得します。パスカバレッジは、コード実行の各パスをカバーすることを要求し、異なる分岐の組み合わせからなるパスは異なるものと見なされます。ループ内の文については、ループの異なる回数も異なるパスと見なされます。パスカバレッジは分岐カバレッジや条件カバレッジよりも粒度が細かく、プログラム内に含まれる大量の分岐やループ構造によりパス爆発の問題が発生する可能性があり、実際のプログラムコードにとっては過度に厳しいと言えます。

AFL のインストゥルメンテーションの主なコードは afl-as.c の **add_instrumentation ()** 関数にあり、挿入されるプローブコードは afl-as.h にあります：

アセンブリコードを行ごとに読み取り、文字列比較を通じてコードセクション（.text）に到達したかを判断します。
コードセクションに入った場合、潜在的なインストゥルメンテーション領域に入ります。afl-as はこれらの行に重点を置きます：
- コロン（：）を含む関数名。
- .Lなどの gcc および clang 下の分岐ラベル。
- jnz などの条件ジャンプ文（無条件ジャンプ jmp は含まれません）。
上記の重要な文を読み取った後、すぐにその後に以下のコードを挿入します。各重要な位置にはこのプローブコードが含まれています：

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

ここで、%08x は fprintf によってランダムな数に置き換えられ、このコード位置の ID を表します。以降はこれらの ID の組み合わせを用いてコード実行パスを表現します。

すべての行を読み終えた後、アセンブリファイルの最後に別のアセンブリコードセクション main_payload_64 を挿入します。このコードはプローブコード内の call __afl_maybe_log によって呼び出され、2 つの機能を含みます：
1. 最初の call __afl_maybe_log は初期化を実行します：
  1. Fork Server がパイプを通じて Fuzzer に新しいファジングが始まったことを通知します。
  2. 共有メモリに接続（attach）します。
  3. Fork Server が新しい Target プロセスをフォークします。
2. 毎回、現在のコード位置 ID のパスカバレッジ情報を統計します。

パスカバレッジ統計#

プローブコードは実行パスを共有メモリの Map に記録します。この共有メモリは Fuzzer によって割り当てられ、共有メモリ ID は環境変数__AFL_SHM_ID を通じて Fork Server に渡され、初期化ステップで読み取られ、ロード（attach）されます。共有メモリアドレスは Target が直接使用します（Target は Fork Server からフォークされたため、両者のグローバル変数の値は同じです）。

AFL はメモリ内にパスアクセス回数を記録するための領域を確保し、Map の Key はパスの ID、Value はそのファジングプロセス中にそのパスにアクセスした回数です。AFL は ID を最大パス数（MAP_SIZE）でモジュロ演算して、ID の値を制限します。最も基本的な配列（連続メモリ）で Map の機能を実現できます。

AFL はコード位置 ID を用いてパス ID を計算する方法も興味深いです：

path_id = previous_location_id **xor** current_location_id
previous_location_id = (path_id **xor** previous_location_id) **>>** 1
map[path_id] ++

右に 1 ビットシフトする理由は、A→B と B→A を異なるものとして扱い、A→A と B→B も異なるものとして扱う必要があるからです。

Fuzz#

AFL のコアプロセスは 1600 行以上の関数 fuzz_one にあり、キュー内の各エントリはこの関数に渡されてファジングされます。手順は以下のように要約できます：

テストケースの精選#

入力空間が非常に広大であるため、テストケースを精選し、一見無用と思われるケースを捨てる必要があります。

update_bitmap_score#

for (i = 0; i < MAP_SIZE; i++) {
	if (trace_bits[i]) {
		if (top_rated[i]) {
			if (q->exec_us * q->len > top_rated[i]->exec_us * top_rated[i]->len) continue;
		}
		top_rated[i] = q;
	}
	q->trace_mini = ck_alloc(MAP_SIZE >> 3);
	minimize_bits(q->trace_mini, trace_bits);
}

配列 top_rated を維持し、各パスをカバーするテストケースのキューエントリを記録します。もしそのパスが以前に他のテストケースによってカバーされている場合、両者の実行時間とペイロード長の積を比較し、積が小さい方を top_rated に残します。AFL は実行時間が短く、ペイロード長が短いテストケースを好みます。
キューエントリのカバレッジパス記録表 trace_bits をビットマップに圧縮し、trace_bits には各パスへのアクセス回数が記録され、trace_mini には各パスがアクセスされたかどうかが記録されます。

cull_queue#

for (i = 0; i < MAP_SIZE; i++) {
	if (top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {
		/* Remove all bits belonging to the current entry from temp_v. */
	}
	top_rated[i]->favored = 1;
}

top_rated 内の各エントリを遍歴し、そのエントリがカバーできるすべてのパスの中に他のエントリによってまだカバーされていないものがあれば、そのエントリがカバーするすべてのパスを temp_v に記録し、エントリを favored としてマークします。
fuzz_one 内では、一定の確率で favored エントリを優先的に考慮します。

trim_case#

remove_len = next_p2(q->len) / 16;
while (remove_len >= next_p2(q->len) / 1024) {
	u32 remove_pos = remove_len;
	while(remove_pos < q->len) {
		write_with_gap(in_buf, q->len, remove_pos, remove_len);
		fault = run_target();
		cksum = hash32(trace_bits);
		if (cksum == q->exec_cksum) {
			/* If the deletion had no impact on the trace, make it permanent. */
			......
		} else remove_pos += remove_len;
	}
	remove_len >>= 1;
}

各テストケースを個別に修剪し、できるだけ短くしてファジング速度を向上させます。
ペイロード内の各固定長セグメントを逐次削除し、実行して異なるカバレッジが生成されるかを判断します。削除後に影響がなければ、削除後のペイロードをキューエントリに対応するファイルに保存します。

calibrate_case#

for (stage_cur = 0; stage_cur < 16; stage_cur++) {
	write_to_testcase(use_mem, q->len);
	fault = run_target();
	cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
	if (q->exec_cksum != cksum) {
		hnb = has_new_bits(virgin_bits);
		for (i = 0; i < MAP_SIZE; i++) {
			if (!var_bytes[i] && first_trace[i] != trace_bits[i]) {
				var_bytes[i] = 1;
				stage_max    = 40;
			}
		}
	} else {
		q->exec_cksum = cksum;
		memcpy(first_trace, trace_bits, MAP_SIZE);
	}
	update_bitmap_score(q);
	/* Mark q->has_new_cov or mark_as_variable(q)
}

calibrate 関数はテストケースが複数回の実行で異なるカバレッジを生成するかを検証します。各テストケースはデフォルトで 8 回繰り返され、もしある回のパスカバレッジ結果が変化した場合、繰り返し実行回数を 40 回に増やします。
新しいカバレッジが生成された場合、q->has_new_cov に記録されますが、実際にこの変数が使用されているコードは見つかりませんでした。

変異#

bitflip：各 1/2/4 ビットを反転させ、各 1/2/4 バイトを反転させます。
arith：各 1/2/4 バイトに 1-35 の整数を加算 / 減算します。
interest：各 1/2/4 バイトを定義された特別な値に置き換えます。
extras：末尾に追加 / 中間に定義されたトークンを挿入します。
havoc（大破壊）：ランダムな回数のランダムな変異操作を重ねます。
splice：キュー内の別の入力をランダムに選択し、適切な長さのサブストリングを現在のペイロードに結合します。

まとめ#

ファジングの多くのツールの中で、AFL は比較的早く登場したため、その作業はまだ比較的単純ですが、8000 行を超える C コードや手続き型プログラミングのパラダイム（1600 行を超える単一の関数や様々な goto を含む）により、ファジングを始めたばかりの私には頭を悩ませるものでした。

参考資料#

afl 源码阅读_最爱・american fuzzy lop_学习才是永恒的博客 - CSDN 博客

AFL 二三事 —— 源码分析 - FreeBuf 网络安全行业门户

sakura の AFL 源码全注释

AFL 插桩（一）概述与普通插桩 | HotSpurzzZ

[原创] AFL afl_fuzz.c 详细分析 - 二进制漏洞 - 看雪 - 安全社区 | 安全招聘 | kanxue.com