afl-fuzz源码分析下篇
[TOC]
前言
- 本篇作为fuzz的最后一篇，核心是fuzz大循环中的内容
- fuzz_one函数很长，笔者将其分为了几个大的过程分析
- 个人认为的重点
cull_queue 精简队列，和top_rated有关，重要
sync_fuzzers 同步fuzzer，这部分现在还没那么重要，但是fuzz实操时为了效率这部分可能会比较重要，初学看看就行
save_if_interesting 这个函数和之前很多内容相关，重要
fuzz_one及其相关函数 核心函数，重要之重要
fuzz大循环
while (1) {
u8 skipped_fuzz;
//精简队列
cull_queue();
if (!queue_cur) {
queue_cycle++;
current_entry = 0;
cur_skipped_paths = 0;
queue_cur = queue;
//如果是resume则根据seek_to来找到对应的位置
while (seek_to) {
current_entry++;
seek_to--;
queue_cur = queue_cur->next;
}
//ui
show_stats();
if (not_on_tty) {
ACTF("Entering queue cycle %llu.", queue_cycle);
fflush(stdout);
}
/* If we had a full queue cycle with no new finds, try
recombination strategies next. */
if (queued_paths == prev_queued) {
// 如果整轮没有新发现，则考虑打开 use_splicing
if (use_splicing) cycles_wo_finds++; else use_splicing = 1;
} else cycles_wo_finds = 0;
prev_queued = queued_paths;
// 设置环境变量 AFL_IMPORT_FIRST，可以让 AFL 在工作之前先与其他 fuzzer 同步一次
if (sync_id && queue_cycle == 1 && getenv("AFL_IMPORT_FIRST"))
sync_fuzzers(use_argv);
}
skipped_fuzz = fuzz_one(use_argv);
// 若这个用例没有被跳过，且处于并行模式
if (!stop_soon && sync_id && !skipped_fuzz) {
// 每发生 5 次这样的事件，就执行 sync_fuzzers()
if (!(sync_interval_cnt++ % SYNC_INTERVAL))
sync_fuzzers(use_argv);
}
if (!stop_soon && exit_1) stop_soon = 2;
if (stop_soon) break;
// 轮到下一个testcase
queue_cur = queue_cur->next;
current_entry++;
}
//以下就是fuzz结束的一些处理，分析略
if (queue_cur) show_stats();
/* If we stopped programmatically, we kill the forkserver and the current runner.
If we stopped manually, this is done by the signal handler. */
if (stop_soon == 2) {
if (child_pid > 0) kill(child_pid, SIGKILL);
if (forksrv_pid > 0) kill(forksrv_pid, SIGKILL);
}
/* Now that we've killed the forkserver, we wait for it to be able to get rusage stats. */
if (waitpid(forksrv_pid, NULL, 0) <= 0) {
WARNF("error waitpid\n");
}
write_bitmap();
write_stats_file(0, 0, 0);
save_auto();
stop_fuzzing:
SAYF(CURSOR_SHOW cLRD "\n\n+++ Testing aborted %s +++\n" cRST,
stop_soon == 2 ? "programmatically" : "by user");
/* Running for more than 30 minutes but still doing first cycle? */
if (queue_cycle == 1 && get_cur_time() - start_time > 30 * 60 * 1000) {
SAYF("\n" cYEL "[!] " cRST
"Stopped during the first cycle, results may be incomplete.\n"
" (For info on resuming, see %s/README.)\n", doc_path);
}
fclose(plot_file);
destroy_queue();
destroy_extras();
ck_free(target_path);
ck_free(sync_id);
alloc_report();
OKF("We're done here. Have a nice day!\n");
exit(0);
cull_queue
- temp_v用来表示哪些位置没有被覆盖，遍历top_reted数组，对于top_rated数组中的每一个q，利用其trace_mini来更新temp_v。temp_v中的每一位为0表示被覆盖，为1表示没有被覆盖
- 注意区分!和~。!是逻辑非（NOT）运算符，~是按位取反（Bitwise NOT）运算符，对于temp_v[j] &= ~top_rated[i]->trace_mini[j];这一步，正好就实现了上述功能。同时temp_v和trace_mini是路径压缩后的结果，只表示是否被覆盖，不管次数
/* 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;
// temp_v 是一个 bitmap，表示哪些位置还未被覆盖
static u8 temp_v[MAP_SIZE >> 3];
u32 i;
//只有update_bitmap_score得分更新了，才会进行下面的步骤
if (dumb_mode || !score_changed) return;
score_changed = 0;
memset(temp_v, 255, MAP_SIZE >> 3);
queued_favored = 0;
pending_favored = 0;
q = queue;
//把queue中所有的favored设置为0
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++)
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. */
// 用偏爱用例更新 temp_v
while (j--)
if (top_rated[i]->trace_mini[j])
temp_v[j] &= ~top_rated[i]->trace_mini[j];
top_rated[i]->favored = 1;
queued_favored++;
// 若这个偏爱用例还从来没被 fuzz 过，则增加 pending_favored 计数器
if (!top_rated[i]->was_fuzzed) pending_favored++;
}
q = queue;
while (q) {
mark_as_redundant(q, !q->favored);
q = q->next;
}
}
mark_as_redundant
- 根据传入的state数值，如果不被favored就加入到out_dir/queue/.state/redundant_edges/中，否则就unlink这个文件(删除指定路径名的文件)
/* Mark / unmark as redundant (edge-only). This is not used for restoring state,
but may be useful for post-processing datasets. */
static void mark_as_redundant(struct queue_entry* q, u8 state) {
u8* fn;
s32 fd;
if (state == q->fs_redundant) return;
q->fs_redundant = state;
fn = strrchr(q->fname, '/');
fn = alloc_printf("%s/queue/.state/redundant_edges/%s", out_dir, fn + 1);
if (state) {
fd = open(fn, O_WRONLY | O_CREAT | O_EXCL, 0600);
if (fd < 0) PFATAL("Unable to create '%s'", fn);
close(fd);
} else {
if (unlink(fn)) PFATAL("Unable to remove '%s'", fn);
}
ck_free(fn);
}
sync_fuzzers
- 用于在各个 fuzzer 之间同步状态
#include <dirent.h>
struct dirent {
ino_t d_ino; // 文件的索引节点号 (inode number)
off_t d_off; // 目录文件中的偏移量（在某些系统中未使用）
unsigned short d_reclen; // 此目录项的长度
unsigned char d_type; // 文件类型
char d_name[256]; // 文件名（以 null 结尾的字符串）
};
#define CASE_PREFIX "id:"
/* Grab interesting test cases from other fuzzers. */
static void sync_fuzzers(char** argv) {
DIR* sd;
//sync_dir_entry
struct dirent* sd_ent;
u32 sync_cnt = 0;
sd = opendir(sync_dir);
if (!sd) PFATAL("Unable to open '%s'", sync_dir);
stage_max = stage_cur = 0;
cur_depth = 0;
/* Look at the entries created for every other fuzzer in the sync directory. */
while ((sd_ent = readdir(sd))) {
// 枚举 sync_dir 下的每一个目录或文件
static u8 stage_tmp[128];
DIR* qd;
struct dirent* qd_ent;
u8 *qd_path, *qd_synced_path;
u32 min_accept = 0, next_min_accept;
s32 id_fd;
/* Skip dot files and our own output directory. */
if (sd_ent->d_name[0] == '.' || !strcmp(sync_id, sd_ent->d_name)) continue;
/* Skip anything that doesn't have a queue/ subdirectory. */
//跳过没有queue/子目录的任何内容
qd_path = alloc_printf("%s/%s/queue", sync_dir, sd_ent->d_name);
if (!(qd = opendir(qd_path))) {
ck_free(qd_path);
continue;
}
/* Retrieve the ID of the last seen test case. */
qd_synced_path = alloc_printf("%s/.synced/%s", out_dir, sd_ent->d_name);
id_fd = open(qd_synced_path, O_RDWR | O_CREAT, 0600);
if (id_fd < 0) PFATAL("Unable to create '%s'", qd_synced_path);
if (read(id_fd, &min_accept, sizeof(u32)) > 0)
lseek(id_fd, 0, SEEK_SET);
next_min_accept = min_accept;
/* Show stats */
sprintf(stage_tmp, "sync %u", ++sync_cnt);
stage_name = stage_tmp;
stage_cur = 0;
stage_max = 0;
/* For every file queued by this fuzzer, parse ID and see if we have looked at
it before; exec a test case if not. */
//遍历sync_dir/sd_ent->d_name/queue/
while ((qd_ent = readdir(qd))) {
u8* path;
s32 fd;
struct stat st;
if (qd_ent->d_name[0] == '.' ||
sscanf(qd_ent->d_name, CASE_PREFIX "%06u", &syncing_case) != 1 ||
syncing_case < min_accept) continue;
/* OK, sounds like a new one. Let's give it a try. */
if (syncing_case >= next_min_accept)
next_min_accept = syncing_case + 1;
//sync_dir/sd_ent->d_name/queue/qd_ent->d_name
path = alloc_printf("%s/%s", qd_path, qd_ent->d_name);
/* Allow this to fail in case the other fuzzer is resuming or so... */
fd = open(path, O_RDONLY);
if (fd < 0) {
ck_free(path);
continue;
}
if (fstat(fd, &st)) PFATAL("fstat() failed");
/* Ignore zero-sized or oversized files. */
if (st.st_size && st.st_size <= MAX_FILE) {
u8 fault;
u8* mem = mmap(0, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
if (mem == MAP_FAILED) PFATAL("Unable to mmap '%s'", path);
/* See what happens. We rely on save_if_interesting() to catch major
errors and save the test case. */
write_to_testcase(mem, st.st_size);
fault = run_target(argv, exec_tmout);
if (stop_soon) return;
//表示同步方是当前sync_dir文件夹下的哪个文件
syncing_party = sd_ent->d_name;
queued_imported += save_if_interesting(argv, mem, st.st_size, fault);
syncing_party = 0;
munmap(mem, st.st_size);
if (!(stage_cur++ % stats_update_freq)) show_stats();
}
ck_free(path);
close(fd);
}
ck_write(id_fd, &next_min_accept, sizeof(u32), qd_synced_path);
close(id_fd);
closedir(qd);
ck_free(qd_path);
ck_free(qd_synced_path);
}
closedir(sd);
}
save_if_interesting
- 看这个函数之前先复习一些内容
run_target 函数返回值是：
FAULT_NONE(0)，表示 child 正常结束。
FAULT_TMOUT(1)，表示超时。
FAULT_CRASH(2)，表示程序崩溃。
FAULT_ERROR(3)，表示 fuzzer 本身出现问题。
virgin_bits，常规 fuzz 过程的探索情况
virgin_tmout，超时用例的探索情况
virgin_crash，crash 用例的探索情况
- 根据run_target跑的结果判断这个用例是否有趣,判断是否产生新的覆盖位或者路径，没有直接返回0.否则加到queue中，计算刚才run_target后的trace_bits的hash32存到queue_top->exec_cksum中
- 再次校准该testcase
- 在考虑完要不要把一个元素加入 queue 后，再考虑要不要将其保存到文件系统
/* 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) {
u8 *fn = "";
u8 hnb;
s32 fd;
u8 keeping = 0, res;
// 若 fault = crash_mode = 2，则处于 crash exploration 模式且崩溃了
// 若 fault = crash_mode = 0，则处于普通模式，且没有崩溃或超时
if (fault == crash_mode) {
/* Keep only if there are new bits in the map, add to queue for
future fuzzing, etc. */
// 如果没发现新的路径，就忽略
// has_new_bits 返回值：0 表示无成果；1 表示 hit count 变动；2 表示发现了新的边
if (!(hnb = has_new_bits(virgin_bits))) {
if (crash_mode) total_crashes++;
return 0;
}
// 这是用例的文件名，描述了 id、来历
fn = alloc_printf("%s/queue/id:%06u,%s", out_dir, queued_paths,
describe_op(hnb));
//把这个用例加到队列中，这个用例是queue_top
add_to_queue(fn, len, 0);
if (hnb == 2) {
queue_top->has_new_cov = 1;
queued_with_cov++;
}
queue_top->exec_cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
/* Try to calibrate inline; this also calls update_bitmap_score() when
successful. */
//校准这个用例
res = calibrate_case(argv, queue_top, mem, queue_cycle - 1, 0);
if (res == FAULT_ERROR)
FATAL("Unable to execute target application");
fd = open(fn, O_WRONLY | O_CREAT | O_EXCL, 0600);
if (fd < 0) PFATAL("Unable to create '%s'", fn);
ck_write(fd, mem, len, fn);
close(fd);
keeping = 1;
}
switch (fault) {
//**********************************************超时*******************************************
case FAULT_TMOUT:
/* Timeouts are not very interesting, but we're still obliged to keep
a handful of samples. We use the presence of new bits in the
hang-specific bitmap as a signal of uniqueness. In "dumb" mode, we
just keep everything. */
total_tmouts++;
if (unique_hangs >= KEEP_UNIQUE_HANG) return keeping;
if (!dumb_mode) {
// simplify_trace 函数是只保留「是否命中」而不保留 count，这和路径压缩的trace_mini有点像
simplify_trace((u32*)trace_bits);
// 若在 timeout 用例中，没有发现新的边，则丢弃
if (!has_new_bits(virgin_tmout)) return keeping;
}
unique_tmouts++;
/* Before saving, we make sure that it's a genuine hang by re-running
the target with a more generous timeout (unless the default timeout
is already generous). */
if (exec_tmout < hang_tmout) {
u8 new_fault;
write_to_testcase(mem, len);
new_fault = run_target(argv, hang_tmout);
/* A corner case that one user reported bumping into: increasing the
timeout actually uncovers a crash. Make sure we don't discard it if
so. */
// 重跑结果是 crash
if (!stop_soon && new_fault == FAULT_CRASH) goto keep_as_crash;
// 重跑正常结束了，丢弃
if (stop_soon || new_fault != FAULT_TMOUT) return keeping;
}
fn = alloc_printf("%s/hangs/id:%06llu,%s", out_dir,
unique_hangs, describe_op(0));
unique_hangs++;
last_hang_time = get_cur_time();
break;
//************************************************crash***********************************
case FAULT_CRASH:
keep_as_crash:
/* This is handled in a manner roughly similar to timeouts,
except for slightly different limits and no need to re-run test
cases. */
total_crashes++;
if (unique_crashes >= KEEP_UNIQUE_CRASH) return keeping;
if (!dumb_mode) {
simplify_trace((u32*)trace_bits);
// 若这与其他的 crash 本质相同，则丢弃
if (!has_new_bits(virgin_crash)) return keeping;
}
if (!unique_crashes) write_crash_readme();
fn = alloc_printf("%s/crashes/id:%06llu,sig:%02u,%s", out_dir,
unique_crashes, kill_signal, describe_op(0));
unique_crashes++;
last_crash_time = get_cur_time();
last_crash_execs = total_execs;
break;
case FAULT_ERROR: FATAL("Unable to execute target application");
default: return keeping;
}
/* If we're here, we apparently want to save the crash or hang
test case, too. */
fd = open(fn, O_WRONLY | O_CREAT | O_EXCL, 0600);
if (fd < 0) PFATAL("Unable to create '%s'", fn);
ck_write(fd, mem, len, fn);
close(fd);
ck_free(fn);
return keeping;
}
fuzz_one 相关函数
common_fuzz_stuff
- 可以看到这就是个集成函数，把write_to_testcase,run_target,save_if_interesting集成到一起，方便fuzz_one使用
/* Write a modified test case, run program, process results. Handle
error conditions, returning 1 if it's time to bail out. This is
a helper function for fuzz_one(). */
EXP_ST u8 common_fuzz_stuff(char** argv, u8* out_buf, u32 len) {
u8 fault;
//这个和afl_postprocess有关，之前已经分析过了
if (post_handler) {
out_buf = post_handler(out_buf, &len);
if (!out_buf || !len) return 0;
}
//将testcase写入target
write_to_testcase(out_buf, len);
//run_target运行
fault = run_target(argv, exec_tmout);
if (stop_soon) return 1;
//超时处理
if (fault == FAULT_TMOUT) {
if (subseq_tmouts++ > TMOUT_LIMIT) {
cur_skipped_paths++;
return 1;
}
} else subseq_tmouts = 0;
/* Users can hit us with SIGUSR1 to request the current input
to be abandoned. */
if (skip_requested) {
skip_requested = 0;
cur_skipped_paths++;
return 1;
}
/* This handles FAULT_ERROR for us: */
//将save_if_interesting函数的返回值加入到queued_discovered
queued_discovered += save_if_interesting(argv, out_buf, len, fault);
//ui
if (!(stage_cur % stats_update_freq) || stage_cur + 1 == stage_max)
show_stats();
return 0;
}
calculate_score
- 这个是给testcase打分的一个函数，分数的定义都比较主观，也可能是根据经验，这个地方显然是可以根据实际情况优化修改打分机制，进而更好的fuzz
/* Calculate case desirability score to adjust the length of havoc fuzzing.
A helper function for fuzz_one(). Maybe some of these constants should
go into config.h. */
static u32 calculate_score(struct queue_entry* q) {
// 全局平均校准时间
u32 avg_exec_us = total_cal_us / total_cal_cycles;
// 全局平均 bitmap 大小
u32 avg_bitmap_size = total_bitmap_size / total_bitmap_entries;
u32 perf_score = 100;
/* Adjust score based on execution speed of this path, compared to the
global average. Multiplier ranges from 0.1x to 3x. Fast inputs are
less expensive to fuzz, so we're giving them more air time. */
// 用例跑得越快，得分越高
if (q->exec_us * 0.1 > avg_exec_us) perf_score = 10;
else if (q->exec_us * 0.25 > avg_exec_us) perf_score = 25;
else if (q->exec_us * 0.5 > avg_exec_us) perf_score = 50;
else if (q->exec_us * 0.75 > avg_exec_us) perf_score = 75;
else if (q->exec_us * 4 < avg_exec_us) perf_score = 300;
else if (q->exec_us * 3 < avg_exec_us) perf_score = 200;
else if (q->exec_us * 2 < avg_exec_us) perf_score = 150;
/* Adjust score based on bitmap size. The working theory is that better
coverage translates to better targets. Multiplier from 0.25x to 3x. */
// 用例覆盖度越高，得分越高
if (q->bitmap_size * 0.3 > avg_bitmap_size) perf_score *= 3;
else if (q->bitmap_size * 0.5 > avg_bitmap_size) perf_score *= 2;
else if (q->bitmap_size * 0.75 > avg_bitmap_size) perf_score *= 1.5;
else if (q->bitmap_size * 3 < avg_bitmap_size) perf_score *= 0.25;
else if (q->bitmap_size * 2 < avg_bitmap_size) perf_score *= 0.5;
else if (q->bitmap_size * 1.5 < avg_bitmap_size) perf_score *= 0.75;
/* Adjust score based on handicap. Handicap is proportional to how late
in the game we learned about this path. Latecomers are allowed to run
for a bit longer until they catch up with the rest. */
// 如果用例发现得比较晚，则多给一些得分
if (q->handicap >= 4) {
perf_score *= 4;
q->handicap -= 4;
} else if (q->handicap) {
perf_score *= 2;
q->handicap--;
}
/* Final adjustment based on input depth, under the assumption that fuzzing
deeper test cases is more likely to reveal stuff that can't be
discovered with traditional fuzzers. */
// 该用例深度越大，分数越高
switch (q->depth) {
case 0 ... 3: break;
case 4 ... 7: perf_score *= 2; break;
case 8 ... 13: perf_score *= 3; break;
case 14 ... 25: perf_score *= 4; break;
default: perf_score *= 5;
}
/* Make sure that we don't go over limit. */
// 最多给 1600 分
if (perf_score > HAVOC_MAX_MULT * 100) perf_score = HAVOC_MAX_MULT * 100;
return perf_score;
}
trim_case
- 此函数用于fuzz_one的TRIMMING阶段
/* Trim all new test cases to save cycles when doing deterministic checks. The
trimmer uses power-of-two increments somewhere between 1/16 and 1/1024 of
file size, to keep the stage short and sweet. */
static u8 trim_case(char** argv, struct queue_entry* q, u8* in_buf) {
static u8 tmp[64];
static u8 clean_trace[MAP_SIZE];
u8 needs_write = 0, fault = 0;
u32 trim_exec = 0;
u32 remove_len;
u32 len_p2;
/* Although the trimmer will be less useful when variable behavior is
detected, it will still work to some extent, so we don't check for
this. */
// 不裁剪长度小于 5 的用例
if (q->len < 5) return 0;
stage_name = tmp;
bytes_trim_in += q->len;
/* Select initial chunk len, starting with large steps. */
len_p2 = next_p2(q->len);
// 把输入分成 16 块。最小块长度是 4
remove_len = MAX(len_p2 / TRIM_START_STEPS, TRIM_MIN_BYTES);
/* Continue until the number of steps gets too high or the stepover
gets too small. */
// 尝试以 remove_len 为块长进行裁剪
while (remove_len >= MAX(len_p2 / TRIM_END_STEPS, TRIM_MIN_BYTES)) {
u32 remove_pos = remove_len;
sprintf(tmp, "trim %s/%s", DI(remove_len), DI(remove_len));
stage_cur = 0;
stage_max = q->len / remove_len;
while (remove_pos < q->len) {
u32 trim_avail = MIN(remove_len, q->len - remove_pos);
u32 cksum;
// 裁掉这块，写入 out_file
write_with_gap(in_buf, q->len, remove_pos, trim_avail);
//调用run_target运行
fault = run_target(argv, exec_tmout);
trim_execs++;
//运行出错直接终止trim
if (stop_soon || fault == FAULT_ERROR) goto abort_trimming;
/* Note that we don't keep track of crashes or hangs here; maybe TODO? */
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
/* If the deletion had no impact on the trace, make it permanent. This
isn't perfect for variable-path inputs, but we're just making a
best-effort pass, so it's not a big deal if we end up with false
negatives every now and then. */
// 若行为不变，则可以裁剪
if (cksum == q->exec_cksum) {
u32 move_tail = q->len - remove_pos - trim_avail;
q->len -= trim_avail;
len_p2 = next_p2(q->len);
memmove(in_buf + remove_pos, in_buf + remove_pos + trim_avail,
move_tail);
/* Let's save a clean trace, which will be needed by
update_bitmap_score once we're done with the trimming stuff. */
if (!needs_write) {
needs_write = 1;
memcpy(clean_trace, trace_bits, MAP_SIZE);
}
} else remove_pos += remove_len;
/* Since this can be slow, update the screen every now and then. */
if (!(trim_exec++ % stats_update_freq)) show_stats();
stage_cur++;
}
// 块长度减半
remove_len >>= 1;
}
/* If we have made changes to in_buf, we also need to update the on-disk
version of the test case. */
if (needs_write) {
s32 fd;
unlink(q->fname); /* ignore errors */
fd = open(q->fname, O_WRONLY | O_CREAT | O_EXCL, 0600);
if (fd < 0) PFATAL("Unable to create '%s'", q->fname);
ck_write(fd, in_buf, q->len, q->fname);
close(fd);
memcpy(trace_bits, clean_trace, MAP_SIZE);
update_bitmap_score(q);
}
abort_trimming:
bytes_trim_out += q->len;
return fault;
}
fuzz_one准备工作
- 总体流程如下
1.根据testcase的属性，来决定跳过这次fuzz的概率，favored用例永远是优先的
2.将testcase内容mmap到地址空间用in_buf存储，out_buf存储变异出来的用例
3.CALIBRATION阶段，如果queue_cur->cal_failed存在，且次数不超过CAL_CHANCES，再次进行校准
4.TRIMMING阶段，如果用例没有被trim，则进行此阶段
5.PERFORMANCE SCORE，调用calculate_score函数计算当前testcase的得分
s32 len, fd, temp_len, i, j;
u8 *in_buf, *out_buf, *orig_in, *ex_tmp, *eff_map = 0;
u64 havoc_queued, orig_hit_cnt, new_hit_cnt;
u32 splice_cycle = 0, perf_score = 100, orig_perf, prev_cksum, eff_cnt = 1;
u8 ret_val = 1, doing_det = 0;
u8 a_collect[MAX_AUTO_EXTRA];
u32 a_len = 0;
// 若有暂未被 fuzz 过的 favored 用例
if (pending_favored) {
/* If we have any favored, non-fuzzed new arrivals in the queue,
possibly skip to them at the expense of already-fuzzed or non-favored
cases. */
// 若当前用例已经被 fuzz 过了，或当前用例并非 favored，则以 99% 的概率跳过，让新 favored 用例先 fuzz
if ((queue_cur->was_fuzzed || !queue_cur->favored) &&
UR(100) < SKIP_TO_NEW_PROB) return 1;
} else if (!dumb_mode && !queue_cur->favored && queued_paths > 10) {
// 所有 favored 用例都被 fuzz 过，且当前用例并非 favored，且 corpus 大小超过 10
/* Otherwise, still possibly skip non-favored cases, albeit less often.
The odds of skipping stuff are higher for already-fuzzed inputs and
lower for never-fuzzed entries. */
if (queue_cycle > 1 && !queue_cur->was_fuzzed) {
// 若当前用例没有被 fuzz 过，以 75% 的概率跳过
if (UR(100) < SKIP_NFAV_NEW_PROB) return 1;
} else {
// 若当前用例被 fuzz 过，则以 95% 的概率跳过
if (UR(100) < SKIP_NFAV_OLD_PROB) return 1;
}
}
if (not_on_tty) {
ACTF("Fuzzing test case #%u (%u total, %llu uniq crashes found)...",
current_entry, queued_paths, unique_crashes);
fflush(stdout);
}
/* Map the test case into memory. */
fd = open(queue_cur->fname, O_RDONLY);
if (fd < 0) PFATAL("Unable to open '%s'", queue_cur->fname);
len = queue_cur->len;
// 调用 mmap 把文件挂进地址空间
orig_in = in_buf = mmap(0, len, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
if (orig_in == MAP_FAILED) PFATAL("Unable to mmap '%s'", queue_cur->fname);
close(fd);
/* We could mmap() out_buf as MAP_PRIVATE, but we end up clobbering every
single byte anyway, so it wouldn't give us any performance or memory usage
benefits. */
// out_buf 用来存储变异出来的用例，要交由目标程序执行
out_buf = ck_alloc_nozero(len);
subseq_tmouts = 0;
cur_depth = queue_cur->depth;
/*******************************************
* CALIBRATION (only if failed earlier on) *
*******************************************/
if (queue_cur->cal_failed) {
u8 res = FAULT_TMOUT;
if (queue_cur->cal_failed < CAL_CHANCES) {
/* Reset exec_cksum to tell calibrate_case to re-execute the testcase
avoiding the usage of an invalid trace_bits.
For more info: https://github.com/AFLplusplus/AFLplusplus/pull/425 */
queue_cur->exec_cksum = 0;
res = calibrate_case(argv, queue_cur, in_buf, queue_cycle - 1, 0);
if (res == FAULT_ERROR)
FATAL("Unable to execute target application");
}
if (stop_soon || res != crash_mode) {
cur_skipped_paths++;
goto abandon_entry;
}
}
/************
* TRIMMING *
************/
if (!dumb_mode && !queue_cur->trim_done) {
u8 res = trim_case(argv, queue_cur, in_buf);
if (res == FAULT_ERROR)
FATAL("Unable to execute target application");
if (stop_soon) {
cur_skipped_paths++;
goto abandon_entry;
}
/* Don't retry trimming, even if it failed. */
queue_cur->trim_done = 1;
if (len != queue_cur->len) len = queue_cur->len;
}
memcpy(out_buf, in_buf, len);
/*********************
* PERFORMANCE SCORE *
*********************/
orig_perf = perf_score = calculate_score(queue_cur);
/* Skip right away if -d is given, if we have done deterministic fuzzing on
this entry ourselves (was_fuzzed), or if it has gone through deterministic
testing in earlier, resumed runs (passed_det). */
if (skip_deterministic || queue_cur->was_fuzzed || queue_cur->passed_det)
goto havoc_stage;
/* Skip deterministic fuzzing if exec path checksum puts this out of scope
for this master instance. */
if (master_max && (queue_cur->exec_cksum % master_max) != master_id - 1)
goto havoc_stage;
doing_det = 1;
fuzz_one变异阶段
- 先复习一下之前全局变量的相关内容
static u64 stage_finds[32], /* Patterns found per fuzz stage */
stage_cycles[32]; /* Execs per fuzz stage */
/* Interesting values, as per config.h */
//**********************确定性变异的内容*************************
static s8 interesting_8[] = { INTERESTING_8 };
static s16 interesting_16[] = { INTERESTING_8, INTERESTING_16 };
static s32 interesting_32[] = { INTERESTING_8, INTERESTING_16, INTERESTING_32 };
/* Fuzzing stages */
//****************************变异所处的阶段*****************************
enum {
/* 00 */ STAGE_FLIP1,
/* 01 */ STAGE_FLIP2,
/* 02 */ STAGE_FLIP4,
/* 03 */ STAGE_FLIP8,
/* 04 */ STAGE_FLIP16,
/* 05 */ STAGE_FLIP32,
/* 06 */ STAGE_ARITH8,
/* 07 */ STAGE_ARITH16,
/* 08 */ STAGE_ARITH32,
/* 09 */ STAGE_INTEREST8,
/* 10 */ STAGE_INTEREST16,
/* 11 */ STAGE_INTEREST32,
/* 12 */ STAGE_EXTRAS_UO,
/* 13 */ STAGE_EXTRAS_UI,
/* 14 */ STAGE_EXTRAS_AO,
/* 15 */ STAGE_HAVOC,
/* 16 */ STAGE_SPLICE
};
/* Stage value types */
enum {
/* 00 */ STAGE_VAL_NONE,
/* 01 */ STAGE_VAL_LE,
/* 02 */ STAGE_VAL_BE
};
simple bitflip
- 解释bitflip一些内容 ，a/b 的意思是翻转连续的 a 个 bit、步长为 b
#define FLIP_BIT(_ar, _b): 这是一个宏定义，定义了一个名为 FLIP_BIT 的宏。这个宏接受两个参数：_ar 和 _b。
u8* _arf = (u8*)(_ar);: 将输入参数 _ar 转换为一个指向无符号8位整数 (u8) 的指针，并将其赋值给 _arf。_ar 通常是一个数组或者指向数据的指针。
u32 _bf = (_b);: 将输入参数 _b 赋值给 _bf。_b 是表示要翻转的比特位位置的整数。
_arf[(_bf) >> 3] ^= (128 >> ((_bf) & 7));:
(_bf) >> 3: 这一步将 _bf 右移3位，相当于将 _bf 除以8。因为一个字节有8个比特，所以这个操作计算出 _bf 所在的字节的索引。
_arf[(_bf) >> 3]: 根据前一步的结果，找到对应的字节。
(_bf) & 7: 这个操作取 _bf 的后3位（因为 7 的二进制是 111），它表示 _bf 在字节中的具体位置（0到7）。
(128 >> ((_bf) & 7)): 128 的二进制表示为 10000000，这个操作右移 _bf & 7 位，以得到要翻转的比特位的掩码。例如，如果 _bf & 7 为 0，结果是 10000000；如果 _bf & 7 为 1，结果是 01000000。
_arf[...] ^= ...: 最后使用 XOR 运算符 (^=) 对找到的字节中的指定比特位进行翻转。如果该比特位原来是 1，则变成 0；如果原来是 0，则变成 1。
- 这里重点分析bitflip 1/1(其他都和它类似),bitflip 8/1(因为有个创建 eff_map 空间的步骤)
bitflip 1/1
- 从头到尾，步长为 1 bit，每次翻转 1 bit
- 调用 common_fuzz_stuff() 去实验，自动寻找 extra，构建词典(此部分在afl-fuzz源码分析上篇中已经分析过，和maybe_add_auto函数有关)。
/*********************************************
* SIMPLE BITFLIP (+dictionary construction) *
*********************************************/
//翻转 _ar 的第 b 个 bit
#define FLIP_BIT(_ar, _b) do { \
u8* _arf = (u8*)(_ar); \
u32 _bf = (_b); \
_arf[(_bf) >> 3] ^= (128 >> ((_bf) & 7)); \
} while (0)
/* Single walking bit. */
stage_short = "flip1";
//注意这里是左移3位，那么stage_cur就代表每一个bit，也就是逐bit
stage_max = len << 3;
stage_name = "bitflip 1/1";
stage_val_type = STAGE_VAL_NONE;
orig_hit_cnt = queued_paths + unique_crashes;
prev_cksum = queue_cur->exec_cksum;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
//计算出字节地址
stage_cur_byte = stage_cur >> 3;
FLIP_BIT(out_buf, stage_cur);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
FLIP_BIT(out_buf, stage_cur);
//每第八次翻转并执行之后，都会检查 trace_bits 的改变情况
if (!dumb_mode && (stage_cur & 7) == 7) {
u32 cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
/*
如果翻转一个字节的 LSB，发现程序行为与原用例不同，则这个字节可能属于一个 extra token。
如果翻转这个字节的 LSB，程序行为与翻转前一个 LSB 的行为不同，则说明这里是 token 的分界点。
*/
//如果都到了testcase的最后，并且cksum==prev_cksum，调用maybe_add_auto(a_collect, a_len);
if (stage_cur == stage_max - 1 && cksum == prev_cksum) {
/* If at end of file and we are still collecting a string, grab the
final character and force output. */
//这个地方是之前分析过的autodictionary
if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];
a_len++;
if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)
maybe_add_auto(a_collect, a_len);
//如果cksum!=prev_cksum，则将之前已经在a_collect的内容添加到autodictionary中，但是由于这次变化后导致cksum不同
//说明这次变化是token 的分界点，需要让a_len=0
} else if (cksum != prev_cksum) {
/* Otherwise, if the checksum has changed, see if we have something
worthwhile queued up, and collect that if the answer is yes. */
if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)
maybe_add_auto(a_collect, a_len);
a_len = 0;
prev_cksum = cksum;
}
/* Continue collecting string, but only if the bit flip actually made
any difference - we don't want no-op tokens. */
if (cksum != queue_cur->exec_cksum) {
if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];
a_len++;
}
}
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_FLIP1] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP1] += stage_max;
bitflip 2/1
- 从头到尾，步长为 1 bit，每次翻转相邻的 2 bit
/* Two walking bits. */
stage_name = "bitflip 2/1";
stage_short = "flip2";
stage_max = (len << 3) - 1;
orig_hit_cnt = new_hit_cnt;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
stage_cur_byte = stage_cur >> 3;
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_FLIP2] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP2] += stage_max;
bitflip 4/1
- 从头到尾，步长为 1 bit，每次翻转相邻的 4 bit
/* Four walking bits. */
stage_name = "bitflip 4/1";
stage_short = "flip4";
stage_max = (len << 3) - 3;
orig_hit_cnt = new_hit_cnt;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
stage_cur_byte = stage_cur >> 3;
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
FLIP_BIT(out_buf, stage_cur + 2);
FLIP_BIT(out_buf, stage_cur + 3);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
FLIP_BIT(out_buf, stage_cur);
FLIP_BIT(out_buf, stage_cur + 1);
FLIP_BIT(out_buf, stage_cur + 2);
FLIP_BIT(out_buf, stage_cur + 3);
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_FLIP4] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP4] += stage_max;
bitflip 8/8
- 从头到尾，步长为 1 byte，每次翻转相邻的 1 byte
//这个宏将位置 _p 右移 EFF_MAP_SCALE2 位。EFF_MAP_SCALE2 是一个常量，通常设置为 3，这意味着位置 _p 被除以 8。该宏用于计算输入数据在 eff_map 中的字节偏移量。
#define EFF_APOS(_p) ((_p) >> EFF_MAP_SCALE2)
//这个宏计算 _x 除以 8 后的余数。它用于判断 _x 在当前字节中的具体位置。
#define EFF_REM(_x) ((_x) & ((1 << EFF_MAP_SCALE2) - 1))
#define EFF_ALEN(_l) (EFF_APOS(_l) + !!EFF_REM(_l))
#define EFF_SPAN_ALEN(_p, _l) (EFF_APOS((_p) + (_l) - 1) - EFF_APOS(_p) + 1)
/* Initialize effector map for the next step (see comments below). Always
flag first and last byte as doing something. */
//effector map
//创建 eff_map 空间，长度为测试用例字节数，并将头尾置 1，其余为 0
eff_map = ck_alloc(EFF_ALEN(len));
eff_map[0] = 1;
if (EFF_APOS(len - 1) != 0) {
eff_map[EFF_APOS(len - 1)] = 1;
eff_cnt++;
}
/* Walking byte. */
stage_name = "bitflip 8/8";
stage_short = "flip8";
stage_max = len;
orig_hit_cnt = new_hit_cnt;
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
stage_cur_byte = stage_cur;
out_buf[stage_cur] ^= 0xFF;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
/* We also use this stage to pull off a simple trick: we identify
bytes that seem to have no effect on the current execution path
even when fully flipped - and we skip them during more expensive
deterministic stages, such as arithmetics or known ints. */
if (!eff_map[EFF_APOS(stage_cur)]) {
u32 cksum;
/* If in dumb mode or if the file is very short, just flag everything
without wasting time on checksums. */
//翻转后检查 eff_map ，如果此字节对应项为 0 ，则检查翻转以后是否带来了路径变化，是则置 1.
if (!dumb_mode && len >= EFF_MIN_LEN)
cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);
else
cksum = ~queue_cur->exec_cksum;
// 用来区分一些无效byte，为后面的阶段做准备,通过一个eff_map 来标记有效byte
if (cksum != queue_cur->exec_cksum) {
eff_map[EFF_APOS(stage_cur)] = 1;
eff_cnt++;
}
}
out_buf[stage_cur] ^= 0xFF;
}
/* If the effector map is more than EFF_MAX_PERC dense, just flag the
whole thing as worth fuzzing, since we wouldn't be saving much time
anyway. */
/*
当整个 byte 的改变都没有带来任何路径变化时， AFL 认为这个 byte 是没有价值的，后续会根据 eff_map 来选择性跳过。
白皮书指出，这样的字节可能只是单纯的非元数据。
*/
if (eff_cnt != EFF_ALEN(len) &&
eff_cnt * 100 / EFF_ALEN(len) > EFF_MAX_PERC) {
// 如果eff_map 大于 EFF_MAX_PERC ,那么直接把整个testcase标记为值得fuzz的
memset(eff_map, 1, EFF_ALEN(len));
blocks_eff_select += EFF_ALEN(len);
} else {
blocks_eff_select += eff_cnt;
}
blocks_eff_total += EFF_ALEN(len);
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_FLIP8] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP8] += stage_max;
bitflip 16/8
- 从头到尾，步长为 1 byte，每次翻转相邻的 2 byte
/* Two walking bytes. */
if (len < 2) goto skip_bitflip;
stage_name = "bitflip 16/8";
stage_short = "flip16";
stage_cur = 0;
stage_max = len - 1;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len - 1; i++) {
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {
stage_max--;
continue;
}
stage_cur_byte = i;
*(u16*)(out_buf + i) ^= 0xFFFF;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
*(u16*)(out_buf + i) ^= 0xFFFF;
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_FLIP16] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP16] += stage_max;
bitflip 32/8
- 从头到尾，步长为 1 byte，每次翻转相邻的 4 byte
/* Four walking bytes. */
stage_name = "bitflip 32/8";
stage_short = "flip32";
stage_cur = 0;
stage_max = len - 3;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len - 3; i++) {
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)] &&
!eff_map[EFF_APOS(i + 2)] && !eff_map[EFF_APOS(i + 3)]) {
stage_max--;
continue;
}
stage_cur_byte = i;
*(u32*)(out_buf + i) ^= 0xFFFFFFFF;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
*(u32*)(out_buf + i) ^= 0xFFFFFFFF;
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_FLIP32] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_FLIP32] += stage_max;
arithmetic inc/dec
- 这一阶段对测试用例做加减法变异。config.h 中将宏 ARITH_MAX 定义为 35，代表了算术运算范围为 -35 到 +35.
- 其中用 could_be_bitflip 来检查是否此步骤会产生和 bitflip 一样的结果（用位比较做到的），以减少重复执行。同时， eff_map 也指导了此步骤
- arith 16/8与arith 32/8和arith 8/8没有太多区别，就不贴源码了
arith 8/8
- 从头到尾，步长为 1 byte，对每个字节都从 -35 一直试到 +35
/* 8-bit arithmetics. */
stage_name = "arith 8/8";
stage_short = "arith8";
stage_cur = 0;
stage_max = 2 * len * ARITH_MAX;
stage_val_type = STAGE_VAL_LE;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len; i++) {
u8 orig = out_buf[i];
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)]) {
stage_max -= 2 * ARITH_MAX;
continue;
}
stage_cur_byte = i;
for (j = 1; j <= ARITH_MAX; j++) {
u8 r = orig ^ (orig + j);
/* Do arithmetic operations only if the result couldn't be a product
of a bitflip. */
if (!could_be_bitflip(r)) {
stage_cur_val = j;
out_buf[i] = orig + j;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
r = orig ^ (orig - j);
if (!could_be_bitflip(r)) {
stage_cur_val = -j;
out_buf[i] = orig - j;
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
} else stage_max--;
out_buf[i] = orig;
}
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_ARITH8] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_ARITH8] += stage_max;
arith 16/8
- 从头到尾，步长为 1 byte，对每个 word 都从 -35 一直试到 +35
arith 32/8
- 从头到尾，步长为 1 byte，对每个 dword 都从 -35 一直试到 +35
interesting values
- 这一阶段用一些特殊的常数对测试用例做替换操作，could_be_arith 与上一阶段去重。并且，这一阶段同样受 eff_map 影响
interest 8/8
- 从头到尾，步长为 1 byte，用 INTERESTING_8 中的每个数替换测试用例 1 byte
stage_name = "interest 8/8";
stage_short = "int8";
stage_cur = 0;
stage_max = len * sizeof(interesting_8);
stage_val_type = STAGE_VAL_LE;
orig_hit_cnt = new_hit_cnt;
/* Setting 8-bit integers. */
for (i = 0; i < len; i++) {
u8 orig = out_buf[i];
/* Let's consult the effector map... */
if (!eff_map[EFF_APOS(i)]) {
stage_max -= sizeof(interesting_8);
continue;
}
stage_cur_byte = i;
for (j = 0; j < sizeof(interesting_8); j++) {
/* Skip if the value could be a product of bitflips or arithmetics. */
if (could_be_bitflip(orig ^ (u8)interesting_8[j]) ||
could_be_arith(orig, (u8)interesting_8[j], 1)) {
stage_max--;
continue;
}
stage_cur_val = interesting_8[j];
out_buf[i] = interesting_8[j];
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
//复原
out_buf[i] = orig;
stage_cur++;
}
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_INTEREST8] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_INTEREST8] += stage_max;
interest 16/8
- 从头到尾，步长为 1 byte，用 INTERESTING_16 中的每个数替换测试用例 1 word
interest 32/8
- 从头到尾，步长为 1 byte，用 INTERESTING_32 中的每个数替换测试用例 1 dword
dictionary stuff
- 这一阶段用字典内容对测试用例进行替换
user extras (over)
- extras在之前就按长度从小到大排了。从头到尾，步长为 1 byte，用 extras 中的每个字符串替换测试用例相同长度（这是个双重循环）。受 eff_map 影响。
if (!extras_cnt) goto skip_user_extras;
/* Overwrite with user-supplied extras. */
stage_name = "user extras (over)";
stage_short = "ext_UO";
stage_cur = 0;
stage_max = extras_cnt * len;
stage_val_type = STAGE_VAL_NONE;
orig_hit_cnt = new_hit_cnt;
for (i = 0; i < len; i++) {
u32 last_len = 0;
stage_cur_byte = i;
/* Extras are sorted by size, from smallest to largest. This means
that we don't have to worry about restoring the buffer in
between writes at a particular offset determined by the outer
loop. */
for (j = 0; j < extras_cnt; j++) {
/* Skip extras probabilistically if extras_cnt > MAX_DET_EXTRAS. Also
skip them if there's no room to insert the payload, if the token
is redundant, or if its entire span has no bytes set in the effector
map. */
if ((extras_cnt > MAX_DET_EXTRAS && UR(extras_cnt) >= MAX_DET_EXTRAS) ||
extras[j].len > len - i ||
!memcmp(extras[j].data, out_buf + i, extras[j].len) ||
!memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, extras[j].len))) {
stage_max--;
continue;
}
last_len = extras[j].len;
memcpy(out_buf + i, extras[j].data, last_len);
if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
stage_cur++;
}
/* Restore all the clobbered memory. */
memcpy(out_buf + i, in_buf + i, last_len);
}
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_EXTRAS_UO] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_EXTRAS_UO] += stage_max;
user extras (insert)
- 这一步是插入extras，和上一个替换还不太一样
- 从头到尾，步长为 1 byte，将 extras 中的每个字符串尝试插入测试用例（用了ex_tmp 变量）。不受 eff_map 影响。
- 这一阶段复原相比于上述阶段更耗时，涉及到空间分配、拷贝、复原等操作。
/* Insertion of user-supplied extras. */
stage_name = "user extras (insert)";
stage_short = "ext_UI";
stage_cur = 0;
stage_max = extras_cnt * (len + 1);
orig_hit_cnt = new_hit_cnt;
ex_tmp = ck_alloc(len + MAX_DICT_FILE);
for (i = 0; i <= len; i++) {
stage_cur_byte = i;
for (j = 0; j < extras_cnt; j++) {
if (len + extras[j].len > MAX_FILE) {
stage_max--;
continue;
}
/* Insert token */
memcpy(ex_tmp + i, extras[j].data, extras[j].len);
/* Copy tail */
memcpy(ex_tmp + i + extras[j].len, out_buf + i, len - i);
if (common_fuzz_stuff(argv, ex_tmp, len + extras[j].len)) {
ck_free(ex_tmp);
goto abandon_entry;
}
stage_cur++;
}
/* Copy head */
ex_tmp[i] = out_buf[i];
}
ck_free(ex_tmp);
new_hit_cnt = queued_paths + unique_crashes;
stage_finds[STAGE_EXTRAS_UI] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_EXTRAS_UI] += stage_max;
auto extras (over)
- 上文提到 bitflip 时会产生字典。在这一步将使用这个字典。从头到尾，步长为 1 byte，用其中的每个字符串替换测试用例相同长度。受 eff_map 影响。
random havoc
- 很随机的进行变异操作，所以也有不少论文对这里进行优化
- 总体有如下操作
随机选取某个 bit 进行翻转
随机选取某个 byte，将其设置为随机的 interesting value
随机选取某个 word，并随机选取大、小端序，将其设置为随机的 interesting value
随机选取某个 dword，并随机选取大、小端序，将其设置为随机的 interesting value
随机选取某个 byte，对其减去一个随机数
随机选取某个 byte，对其加上一个随机数
随机选取某个 word，并随机选取大、小端序，对其减去一个随机数
随机选取某个 word，并随机选取大、小端序，对其加上一个随机数
随机选取某个 dword，并随机选取大、小端序，对其减去一个随机数
随机选取某个 dword，并随机选取大、小端序，对其加上一个随机数
随机选取某个 byte，将其设置为随机数
随机删除一段 bytes
随机选取一个位置，插入一段随机长度的内容，其中 75% 的概率是插入原文中随机位置的内容，25% 的概率是插入一段随机选取的数
随机选取一个位置，替换为一段随机长度的内容，其中 75% 的概率是替换成原文中随机位置的内容，25% 的概率是替换成一段随机选取的数
随机选取一个位置，用随机选取的 token（用户提供的或自动生成的）替换
随机选取一个位置，用随机选取的 token（用户提供的或自动生成的）插入
变异后调用common_fuzz_stuff跑出结果，如果发现了新成果，那么剩余的 havoc 执行次数会翻倍
#define HAVOC_CYCLES_INIT 1024
#define HAVOC_CYCLES 256
#define SPLICE_HAVOC 32
#define HAVOC_MIN 16
#define HAVOC_STACK_POW2 7
havoc_stage:
//给一些变量赋初值然后进行havoc
stage_cur_byte = -1;
/* The havoc stage mutation code is also invoked when splicing files; if the
splice_cycle variable is set, generate different descriptions and such. */
if (!splice_cycle) {
stage_name = "havoc";
stage_short = "havoc";
// 决定 havoc 实验次数
stage_max = (doing_det ? HAVOC_CYCLES_INIT : HAVOC_CYCLES) *
perf_score / havoc_div / 100;
} else {
static u8 tmp[32];
perf_score = orig_perf;
sprintf(tmp, "splice %u", splice_cycle);
stage_name = tmp;
stage_short = "splice";
stage_max = SPLICE_HAVOC * perf_score / havoc_div / 100;
}
if (stage_max < HAVOC_MIN) stage_max = HAVOC_MIN;
temp_len = len;
orig_hit_cnt = queued_paths + unique_crashes;
havoc_queued = queued_paths;
/* We essentially just do several thousand runs (depending on perf_score)
where we take the input file and make random stacked tweaks. */
// 执行 havoc 阶段
for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
u32 use_stacking = 1 << (1 + UR(HAVOC_STACK_POW2));
stage_cur_val = use_stacking;
for (i = 0; i < use_stacking; i++) {
switch (UR(15 + ((extras_cnt + a_extras_cnt) ? 2 : 0))) {
//随机选取某个 bit 进行翻转
case 0:
/* Flip a single bit somewhere. Spooky! */
FLIP_BIT(out_buf, UR(temp_len << 3));
break;
//随机选取某个 byte，将其设置为随机的 interesting value
case 1:
/* Set byte to interesting value. */
out_buf[UR(temp_len)] = interesting_8[UR(sizeof(interesting_8))];
break;
//随机选取某个 word，并随机选取大、小端序，将其设置为随机的 interesting value
case 2:
/* Set word to interesting value, randomly choosing endian. */
if (temp_len < 2) break;
if (UR(2)) {
*(u16*)(out_buf + UR(temp_len - 1)) =
interesting_16[UR(sizeof(interesting_16) >> 1)];
} else {
*(u16*)(out_buf + UR(temp_len - 1)) = SWAP16(
interesting_16[UR(sizeof(interesting_16) >> 1)]);
}
break;
//随机选取某个 dword，并随机选取大、小端序，将其设置为随机的 interesting value
case 3:
/* Set dword to interesting value, randomly choosing endian. */
if (temp_len < 4) break;
if (UR(2)) {
*(u32*)(out_buf + UR(temp_len - 3)) =
interesting_32[UR(sizeof(interesting_32) >> 2)];
} else {
*(u32*)(out_buf + UR(temp_len - 3)) = SWAP32(
interesting_32[UR(sizeof(interesting_32) >> 2)]);
}
break;
//随机选取某个 byte，对其减去一个随机数
case 4:
/* Randomly subtract from byte. */
out_buf[UR(temp_len)] -= 1 + UR(ARITH_MAX);
break;
//随机选取某个 byte，对其加上一个随机数
case 5:
/* Randomly add to byte. */
out_buf[UR(temp_len)] += 1 + UR(ARITH_MAX);
break;
//随机选取某个 word，并随机选取大、小端序，对其减去一个随机数
case 6:
/* Randomly subtract from word, random endian. */
if (temp_len < 2) break;
if (UR(2)) {
u32 pos = UR(temp_len - 1);
*(u16*)(out_buf + pos) -= 1 + UR(ARITH_MAX);
} else {
u32 pos = UR(temp_len - 1);
u16 num = 1 + UR(ARITH_MAX);
*(u16*)(out_buf + pos) =
SWAP16(SWAP16(*(u16*)(out_buf + pos)) - num);
}
break;
//随机选取某个 word，并随机选取大、小端序，对其加上一个随机数
case 7:
/* Randomly add to word, random endian. */
if (temp_len < 2) break;
if (UR(2)) {
u32 pos = UR(temp_len - 1);
*(u16*)(out_buf + pos) += 1 + UR(ARITH_MAX);
} else {
u32 pos = UR(temp_len - 1);
u16 num = 1 + UR(ARITH_MAX);
*(u16*)(out_buf + pos) =
SWAP16(SWAP16(*(u16*)(out_buf + pos)) + num);
}
break;
//随机选取某个 dword，并随机选取大、小端序，对其减去一个随机数
case 8:
/* Randomly subtract from dword, random endian. */
if (temp_len < 4) break;
if (UR(2)) {
u32 pos = UR(temp_len - 3);
*(u32*)(out_buf + pos) -= 1 + UR(ARITH_MAX);
} else {
u32 pos = UR(temp_len - 3);
u32 num = 1 + UR(ARITH_MAX);
*(u32*)(out_buf + pos) =
SWAP32(SWAP32(*(u32*)(out_buf + pos)) - num);
}
break;
//随机选取某个 dword，并随机选取大、小端序，对其加上一个随机数
case 9:
/* Randomly add to dword, random endian. */
if (temp_len < 4) break;
if (UR(2)) {
u32 pos = UR(temp_len - 3);
*(u32*)(out_buf + pos) += 1 + UR(ARITH_MAX);
} else {
u32 pos = UR(temp_len - 3);
u32 num = 1 + UR(ARITH_MAX);
*(u32*)(out_buf + pos) =
SWAP32(SWAP32(*(u32*)(out_buf + pos)) + num);
}
break;
//随机选取某个 byte，将其设置为随机数
case 10:
/* Just set a random byte to a random value. Because,
why not. We use XOR with 1-255 to eliminate the
possibility of a no-op. */
out_buf[UR(temp_len)] ^= 1 + UR(255);
break;
//随机删除一段 bytes
case 11 ... 12: {
/* Delete bytes. We're making this a bit more likely
than insertion (the next option) in hopes of keeping
files reasonably small. */
u32 del_from, del_len;
if (temp_len < 2) break;
/* Don't delete too much. */
del_len = choose_block_len(temp_len - 1);
del_from = UR(temp_len - del_len + 1);
memmove(out_buf + del_from, out_buf + del_from + del_len,
temp_len - del_from - del_len);
temp_len -= del_len;
break;
}
//随机选取一个位置，插入一段随机长度的内容，其中 75% 的概率是插入原文中随机位置的内容，25% 的概率是插入一段随机选取的数
case 13:
if (temp_len + HAVOC_BLK_XL < MAX_FILE) {
/* Clone bytes (75%) or insert a block of constant bytes (25%). */
u8 actually_clone = UR(4);
u32 clone_from, clone_to, clone_len;
u8* new_buf;
if (actually_clone) {
clone_len = choose_block_len(temp_len);
clone_from = UR(temp_len - clone_len + 1);
} else {
clone_len = choose_block_len(HAVOC_BLK_XL);
clone_from = 0;
}
clone_to = UR(temp_len);
new_buf = ck_alloc_nozero(temp_len + clone_len);
/* Head */
memcpy(new_buf, out_buf, clone_to);
/* Inserted part */
if (actually_clone)
memcpy(new_buf + clone_to, out_buf + clone_from, clone_len);
else
memset(new_buf + clone_to,
UR(2) ? UR(256) : out_buf[UR(temp_len)], clone_len);
/* Tail */
memcpy(new_buf + clone_to + clone_len, out_buf + clone_to,
temp_len - clone_to);
ck_free(out_buf);
out_buf = new_buf;
temp_len += clone_len;
}
break;
//随机选取一个位置，替换为一段随机长度的内容，其中 75% 的概率是替换成原文中随机位置的内容，25% 的概率是替换成一段随机选取的数
case 14: {
/* Overwrite bytes with a randomly selected chunk (75%) or fixed
bytes (25%). */
u32 copy_from, copy_to, copy_len;
if (temp_len < 2) break;
copy_len = choose_block_len(temp_len - 1);
copy_from = UR(temp_len - copy_len + 1);
copy_to = UR(temp_len - copy_len + 1);
if (UR(4)) {
if (copy_from != copy_to)
memmove(out_buf + copy_to, out_buf + copy_from, copy_len);
} else memset(out_buf + copy_to,
UR(2) ? UR(256) : out_buf[UR(temp_len)], copy_len);
break;
}
/* Values 15 and 16 can be selected only if there are any extras
present in the dictionaries. */
//随机选取一个位置，用随机选取的 token（用户提供的或自动生成的）替换
case 15: {
/* Overwrite bytes with an extra. */
if (!extras_cnt || (a_extras_cnt && UR(2))) {
/* No user-specified extras or odds in our favor. Let's use an
auto-detected one. */
u32 use_extra = UR(a_extras_cnt);
u32 extra_len = a_extras[use_extra].len;
u32 insert_at;
if (extra_len > temp_len) break;
insert_at = UR(temp_len - extra_len + 1);
memcpy(out_buf + insert_at, a_extras[use_extra].data, extra_len);
} else {
/* No auto extras or odds in our favor. Use the dictionary. */
u32 use_extra = UR(extras_cnt);
u32 extra_len = extras[use_extra].len;
u32 insert_at;
if (extra_len > temp_len) break;
insert_at = UR(temp_len - extra_len + 1);
memcpy(out_buf + insert_at, extras[use_extra].data, extra_len);
}
break;
}
//随机选取一个位置，用随机选取的 token（用户提供的或自动生成的）插入
case 16: {
u32 use_extra, extra_len, insert_at = UR(temp_len + 1);
u8* new_buf;
/* Insert an extra. Do the same dice-rolling stuff as for the
previous case. */
if (!extras_cnt || (a_extras_cnt && UR(2))) {
use_extra = UR(a_extras_cnt);
extra_len = a_extras[use_extra].len;
if (temp_len + extra_len >= MAX_FILE) break;
new_buf = ck_alloc_nozero(temp_len + extra_len);
/* Head */
memcpy(new_buf, out_buf, insert_at);
/* Inserted part */
memcpy(new_buf + insert_at, a_extras[use_extra].data, extra_len);
} else {
use_extra = UR(extras_cnt);
extra_len = extras[use_extra].len;
if (temp_len + extra_len >= MAX_FILE) break;
new_buf = ck_alloc_nozero(temp_len + extra_len);
/* Head */
memcpy(new_buf, out_buf, insert_at);
/* Inserted part */
memcpy(new_buf + insert_at, extras[use_extra].data, extra_len);
}
/* Tail */
memcpy(new_buf + insert_at + extra_len, out_buf + insert_at,
temp_len - insert_at);
ck_free(out_buf);
out_buf = new_buf;
temp_len += extra_len;
break;
}
}
}
//变异后调用common_fuzz_stuff跑出结果，如果发现了新成果，那么剩余的 havoc 执行次数会翻倍
if (common_fuzz_stuff(argv, out_buf, temp_len))
goto abandon_entry;
/* out_buf might have been mangled a bit, so let's restore it to its
original size and shape. */
if (temp_len < len) out_buf = ck_realloc(out_buf, len);
temp_len = len;
memcpy(out_buf, in_buf, len);
/* If we're finding new stuff, let's run for a bit longer, limits
permitting. */
if (queued_paths != havoc_queued) {
if (perf_score <= HAVOC_MAX_MULT * 100) {
stage_max *= 2;
perf_score *= 2;
}
havoc_queued = queued_paths;
}
}
new_hit_cnt = queued_paths + unique_crashes;
if (!splice_cycle) {
stage_finds[STAGE_HAVOC] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_HAVOC] += stage_max;
} else {
stage_finds[STAGE_SPLICE] += new_hit_cnt - orig_hit_cnt;
stage_cycles[STAGE_SPLICE] += stage_max;
}
splicing
- 随机选取一个足够长、且差异足够大的杂交目标，然后随机选择分割点，把本用例的前面一段和杂交目标的后面一段拼接起来。这样会形成一个新的用例，将这个新用例拿去执行 havoc 阶段变异
/************
* SPLICING *
************/
/* This is a last-resort strategy triggered by a full round with no findings.
It takes the current input file, randomly selects another input, and
splices them together at some offset, then relies on the havoc
code to mutate that blob. */
#define SPLICE_CYCLES 15
retry_splicing:
// SPLICE_CYCLES 被定义为 15
if (use_splicing && splice_cycle++ < SPLICE_CYCLES &&
queued_paths > 1 && queue_cur->len > 1) {
struct queue_entry* target;
u32 tid, split_at;
u8* new_buf;
s32 f_diff, l_diff;
/* First of all, if we've modified in_buf for havoc, let's clean that
up... */
if (in_buf != orig_in) {
ck_free(in_buf);
in_buf = orig_in;
len = queue_cur->len;
}
/* Pick a random queue entry and seek to it. Don't splice with yourself. */
// 随机选择一个杂交对象
do { tid = UR(queued_paths); } while (tid == current_entry);
splicing_with = tid;
// 在链表中跳转，找到目标
target = queue;
while (tid >= 100) { target = target->next_100; tid -= 100; }
while (tid--) target = target->next;
// 杂交目标要足够长
/* Make sure that the target has a reasonable length. */
while (target && (target->len < 2 || target == queue_cur)) {
target = target->next;
splicing_with++;
}
if (!target) goto retry_splicing;
// 读入杂交目标
/* Read the testcase into a new buffer. */
fd = open(target->fname, O_RDONLY);
if (fd < 0) PFATAL("Unable to open '%s'", target->fname);
new_buf = ck_alloc_nozero(target->len);
ck_read(fd, new_buf, target->len, target->fname);
close(fd);
/* Find a suitable splicing location, somewhere between the first and
the last differing byte. Bail out if the difference is just a single
byte or so. */
// 找到两个串第一个、最后一个不同的位置
locate_diffs(in_buf, new_buf, MIN(len, target->len), &f_diff, &l_diff);
// 如果两个串差异只有一两个字节，则重新选择
if (f_diff < 0 || l_diff < 2 || f_diff == l_diff) {
ck_free(new_buf);
goto retry_splicing;
}
/* Split somewhere between the first and last differing byte. */
// 分割点，生成一个新用例 A[:split_at] + B[split_at:]
split_at = f_diff + UR(l_diff - f_diff);
/* Do the thing. */
len = target->len;
memcpy(new_buf, in_buf, split_at);
in_buf = new_buf;
ck_free(out_buf);
out_buf = ck_alloc_nozero(len);
memcpy(out_buf, in_buf, len);
// 执行一遍 havoc
goto havoc_stage;
}
locate_diffs
static void locate_diffs(u8* ptr1, u8* ptr2, u32 len, s32* first, s32* last) {
s32 f_loc = -1;
s32 l_loc = -1;
u32 pos;
for (pos = 0; pos < len; pos++) {
if (*(ptr1++) != *(ptr2++)) {
if (f_loc == -1) f_loc = pos;
l_loc = pos;
}
}
*first = f_loc;
*last = l_loc;
return;
}
心得体会
至此afl-fuzz的相关源码全部分析完了，以下是一些心得体会
这是笔者第一次读中型项目的源代码，花了很多时间和精力去阅读，首先感谢前辈们的知识分享，站在巨人的肩膀上，才让我学习fuzz源码更加得心应手，这里贴出一些主要参考过的博客，感谢这些师傅们的无私分享 https://v3rdant.cn/Fuzz.AFL-All-in-One/ https://www.ruanx.net/afl-source-6/ https://xidoo.top/2022/01/afl-rsc4/ https://www.iotsec-zone.com/article/199#218-setup_stdio_file https://xidoo.top/2022/01/afl-white-book/
不论学习什么新的东西，信息收集是很重要的一步，先是搜到了好多学习资料，在他人理解的基础上入门，再形成自己的理解，这是一个很重要的过程。如果能力很强的师傅，也可以就靠自己去读源码，但是笔者认为读源码还是多搜资料，结合已有的文章去学习领悟
读源码要搞清楚自己的目的，因为源码有很多技术规范，还有一些和目的不相关的函数，要学会分辨哪些是不重要的，绕开这些，直奔核心目的很重要。同时对于这些代码，如果只是看表面，这就是一些字母和数字的集合，给变量赋值，调用函数，但如果浮在这个表面是什么都学不到的。要形成自己的理解，比如看到某个变量就知道它和哪一步相关，fuzz源码中testcase是个什么结构(队列)，一些函数有什么作用(比如update_bitmap_score函数，我一看到这个就立刻能想起来它和top_rated有关，再比如save_if_interesting函数，一下子就能想到这个和是否产生新覆盖有关)，以及整个函数的流程(比如fuzz_one函数，无非是准备阶段，加上变异阶段，准备阶段又有好几步，变异阶段有好几种变异)。
总的来说上述是一种抽象能力，这种能力是很重要的。因为源码有些细节很快就会忘记，但是把它抽象出来，这种就很难忘记，也利于整体把握。读完fuzz源码后应该会进行一些fuzz实操的尝试了，也可以读读fuzz相关论文，进一步的学习