淺談 AFL - KendyZ

AFL 全稱是 American Fuzzy Lop，是一款基於代碼覆蓋率引導的程序模糊測試工具，通過將用戶給定以及變異（mutation）得到的測試用例輸入程序，獲得程序代碼的覆蓋率，並將覆蓋情況反饋給用例選取和變異過程，從而不斷提升代碼覆蓋率，最終提高發現代碼中出現漏洞的可能性。

先總結一下 AFL 的幾個特點：

通過代碼插樁（instrument）來記錄每個測試用例輸入程序後的代碼覆蓋率。
通過各種手段，對海量的測試用例進行精簡。
類似於遺傳算法，在 Fuzz 過程中對已有的測試用例進行變異，以生成新的用例。

進程交互#

在最簡單的情況下，整個 AFL 的 Fuzz 流程（campaign）由 3 個進程合作完成：

Fuzzer：代碼實現位於 afl-fuzz.c 文件中，是 Fuzz 主程序，負責維護測試用例的隊列，在測試過程中調度用例輸入程序。Fork Server 是 Fuzzer 的子進程，由其 fork 而來，這也是 Fuzz 過程中唯二的 fork 系統調用（除了 dumb mode 之外）。
Fork Server：自身沒有源文件，其代碼由 afl-as 插樁時插入到了 Target 的匯編代碼中。可以看作是被測程序 Target 的一個 wrapper，由 Fuzzer fork 出來以後常駐，與 Fuzzer 之間建立了兩個 pipe 用於雙向通信，此外 Fork Server 會與 Fuzzer 使用一塊共享內存（shared memory）來傳遞代碼覆蓋率信息。
Target：Target 的進程實例由 Fork Server fork 得到。每個分支、循環結構都被插樁，插入的代碼會將代碼執行覆蓋情況寫入共享內存，供 Fuzzer 讀取。

這 3 個角色的流程圖如下所示。

插樁#

程序插樁是一種基礎的動態分析方法，通過在代碼中插入探針（hook）代碼來獲得程序運行時的上下文信息。可以對源碼進行插樁，也可以對中間代碼或者二進制代碼進行插樁。AFL 提供兩種插樁模式：

直接讀取由被測程序源碼編譯成的匯編代碼（.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 調用，包含兩部分功能：
1. 第一次 call __afl_maybe_log，會執行初始化：
  1. Fork Server 通過 pipe 發消息給 Fuzzer 來告知開始了一次新的 fuzz。
  2. 連接（attach）共享內存。
  3. Fork Server fork 新的 Target 進程。
2. 每一次，統計當前代碼位置 ID 的路徑覆蓋信息。

路徑覆蓋統計#

探針代碼會將執行路徑記錄在共享內存的 Map 中，這塊共享內存由 Fuzzer 分配，共享內存 ID 通過環境變量 __AFL_SHM_ID 傳遞給 Fork Server，在初始化步驟讀取並且加載（attach），共享內存地址則直接供 Target 使用（因為 Target 是 Fork Server fork 出來的，二者全局變量取值是相同的）。

AFL 會在內存中開辟一塊區域用作記錄路徑訪問次數的 Map，Map 的 Key 為路徑的 ID，Value 為該次 Fuzz 過程中訪問到該路徑的次數。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 中，對於每個隊列中的 entry，都会傳入該函數進行 fuzz，步驟可以概括為：

精簡用例#

由於輸入空間極為龐大，因此需要對測試用例進行精簡，丟棄掉一部分看似無用的用例。

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，記錄每個路徑所被覆蓋的用例 queue entry，如果該路徑之前已備其他用例覆蓋過，就比較二者的運行時間與 payload 長度的乘積，乘積更小的留在 top_rated 中。AFL 更偏向於執行之間更短、payload 長度更短的用例。
壓縮 queue entry 的覆蓋路徑記錄表 trace_bits 為一個 bitmap，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 中的每個 entry，當次 entry 所能覆蓋的所有路徑中存在還沒有被其他 entry 覆蓋到的，就將該 entry 覆蓋的所有路徑都記錄到 temp_v 中，同時 entry 標記為 favored。
在 fuzz_one 中會以一定概率優先考慮 favored entry。

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

對每個測試用例單獨進行修剪，儘量縮短其長度，以加快 fuzz 速度。
逐個刪除 payload 中的每個固定長度的段，然後嘗試運行，判斷是否產生不同的覆蓋。如果刪除了之後沒有影響，那就將刪除後的 payload 保存到 queue entry 對應的文件中。

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