今天主要會介紹 trimming 以及 mutation，並了解 function run_target() 的執行過程，而 run_target() 其實是用來通知 fork server 執行 target 的重要 function。
Function run_target() 在多個檔案中都有定義 (afl-fuzz.c, afl-analyze.c ...)，不過在 afl-fuzz 使用的是 afl-fuzz.c 當中的 run_target()，因此如果讀者在自己追 code 時請注意不要看錯地方。
run_target() 會傳遞指令給 fork server 執行 target，並且等待執行結束，再來用結束的狀態來判斷是否發生異常，最後回傳狀態結果，程式碼如下：
static u8 run_target(char** argv, u32 timeout)
{
// 初始化紀錄 coverage 的 memory
memset(trace_bits, 0, MAP_SIZE);
MEM_BARRIER();
// 發送指令給 fork server，而 fork server 在收到指令後會
// fork 一個 child 來執行原本的程式邏輯
write(fsrv_ctl_fd, &prev_timed_out, 4);
read(fsrv_st_fd, &child_pid, 4);
// 設置 timer，如果 timeout 就會收到 SIGALRM，
it.it_value.tv_sec = (timeout / 1000);
it.it_value.tv_usec = (timeout % 1000) * 1000;
setitimer(ITIMER_REAL, &it, NULL);
// 等待執行結束
read(fsrv_st_fd, &status, 4));
// 分類各個 edge 走到的次數，簡單化運算操作
// 0 -> class1, ..., 3 -> class4, 4~7 -> class5, ...
// 同個 class 的 edge 數會被設為相同，
// 舉例來說分類到 class5 的 edge 次數都會被設為 8
classify_counts((u64*)trace_bits);
// 如果 target 是因為 signal 所終止，
// 有可能就是觸發 segfault，或者是 ASAN 發現異常
if (WIFSIGNALED(status)) {
kill_signal = WTERMSIG(status);
// 如果不是因為 timeout 而被 kill，就代表發生 crash
if (child_timed_out && kill_signal == SIGKILL) return FAULT_TMOUT;
return FAULT_CRASH;
}
// MSAN 發現異常
if (uses_asan && WEXITSTATUS(status) == MSAN_ERROR) {
kill_signal = 0;
return FAULT_CRASH;
}
return FAULT_NONE;
}fuzz_one() 在校正完 input 後，會準備開始執行 mutation，不過在此之前還會先將 input 做修剪 (trim)，刪除 input 當中不必要的部分：
// 如果該 input 過去沒有做修剪
if (!queue_cur->trim_done) {
u8 res = trim_case(argv, queue_cur, in_buf);
queue_cur->trim_done = 1;
}
// 將修剪後的 input 複製到 <output_dir>/.cur_input 當中
memcpy(out_buf, in_buf, queue_cur->len);Trimming 的目的為在不影響 coverage 的情況下，將 input 大小縮小以減少 overhead，舉例來說，如果 input "AAAABBBBCCCC" 與 "AAAACCCC" 所產生的 coverage 相同，則會將 "AAAABBBBCCCC" trim 成 "AAAACCCC"。
trim_case() 負責處理 trimming，程式碼如下：
static u8 trim_case(char** argv, struct queue_entry* q, u8* in_buf)
{
// 如果 input 本身資料就不多，則不需要刪減
if (q->len < 5) return 0;
// 求得 input len 的 pow of 2
len_p2 = next_p2(q->len);
// 移除的大小至少要為 4，也就是 trim 的最小單位
// 而後以 input len 的 pow of 2 將 input 拆成 16 份，
// 每份的長度則是 "remove_len"
remove_len = MAX(len_p2 / 16, 4);
while (remove_len >= MAX(len_p2 / 16, 4)) {
// 初始的刪除位置為 "remove_len"
u32 remove_pos = remove_len;
while (remove_pos < q->len) {
// 因為當初長度有做 pow of 2 ceiling，
// 因此有可能最後一個部分的大小不足 "remove_len"
u32 trim_avail = MIN(remove_len, q->len - remove_pos);
u32 cksum;
// 將 input 內容根據要刪除的位置與大小，將資料複製到
// <output_dir>/.cur_input 對應到的 fd 當中
write_with_gap(in_buf, q->len, remove_pos, trim_avail);
// 執行 target 並取得 bitmap 的 checksum
fault = run_target(argv, exec_tmout);
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
// 兩次的 coverage 相同，代表 input 可以做修剪
if (cksum == q->exec_cksum) {
// 變數 "move_tail" 計算出來後為後面沒有更新的資料的大小
u32 move_tail = q->len - remove_pos - trim_avail;
// 更新 input 內容與長度
q->len -= trim_avail;
// 將沒更新到的資料複製到前面，覆蓋掉已經被 trim 的資料
memmove(in_buf + remove_pos, in_buf + remove_pos + trim_avail,
move_tail);
// 更新 pow of 2 長度
len_p2 = next_p2(q->len);
// 需要更新至檔案當中
needs_write = 1;
} else
// 不相同的話則嘗試刪除下一個部分
remove_pos += remove_len;
}
// 降低粒度，做更細緻的 trim
remove_len >>= 1;
}
// 如果 input 已經被修剪，則同步至檔案當中
if (needs_write) {
s32 fd;
unlink(q->fname);
fd = open(q->fname, O_WRONLY | O_CREAT | O_EXCL, 0600);
ck_write(fd, in_buf, q->len, q->fname);
close(fd);
}
return fault;
}trim_case() 的程式碼相較複雜，不過核心概念就是嘗試將 input 每固定長度刪除，如果 coverage 相同就可以將其移除，藉此減少 input 大小。
當 trimming 確保 input 只留下重要的部分後，會進入到 mutation stage，也就是反覆執行 "更新 input、執行 target、評估結果" 的循環。AFL 的 mutation strategy 會先讓新的 input 執行固定的變異，之後才會做真正隨機化的更新，因此又被稱作 deterministic step。
各變異的名稱與行為如下：
- bitflip1/1：一次翻 1 bit
- bitflip2/1：一次翻 2 bits
- bitflip4/1：一次翻 4 bits
- bitflip8/8：一次翻 1 byte
- bitflip16/8：一次翻 2 bytes
- bitflip32/8：一次翻 4 bytes
- Arith8/8：對每 byte 做 +-1, +-2, +-3, ..., +-35
- Arith16/8：對每 2 bytes 做 +-1, +-2, +-3, ..., +-35
- Arith32/8：對每 4 bytes 做 +-1, +-2, +-3, ..., +-35
- interest8/8：將某 byte 替換成 interest value 的值，而 interest value 是 edge case 的 value，如 MAX_INT、0
- interest16/8：將某 2bytes 替換成 interest value 的值
- interest32/8：將某 4bytes 替換成 interest value 的值
最後一組的變異是將隨機執行上述介紹的方法，因此很有可能產生差異很大的 input：
- havoc：會對 input 做許多次隨機 mutation
而因為變異很多，因此 fuzz_one() 的程式碼大部分都在處理 mutation，不過基本上概念大同小異，只需要知道其中一個怎麼做就好，以下為執行操作 "bitflip2/1" 的程式碼片段：
// queued_path 為所有 queued testcases 的數量
// unique_crashes 為獨立的 crash 數量
new_hit_cnt = queued_paths + unique_crashes;
// stage 名稱
stage_name = "bitflip 2/1";
// 每 2 bits 為一組，一共有幾組
stage_max = (len << 3) - 1;
// 紀錄原先的 fuzzing 狀態 (testcases 數量 + crash 數量)
orig_hit_cnt = new_hit_cnt;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
// 翻過去
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
// 執行 target
common_fuzz_stuff(argv, out_buf, len);
// 翻回來
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
}
// 更新在 bitflip 2/1 的過程中是否有新的 crash，
// 或是新增了新的 testcases
new_hit_cnt = queued_paths + unique_crashes;
// 更新此 stage 的成效 (new - old)
stage_finds[STAGE_FLIP2] += new_hit_cnt - orig_hit_cnt;mutation 的程式碼非常直觀且好懂，不過仍有些變異需要比較複雜的處理，在此就不多做說明，至於 common_fuzz_stuff() 是怎麼執行的，會在明天做介紹。