其他
AFL速通——流程及afl-fuzz.c源码简析
本文为看雪论坛精华文章
看雪论坛作者ID：Azyka
一
source code fuzzing的基本流程
主要内容是Instrument target和Fuzz本体
二
Instrument
afl-gcc插桩分析
#include <string.h>#include <stdio.h>#include <unistd.h>#include <stdlib.h> #define INPUTSIZE 100 int process(char *input){ char *out; char *rest; int len; if (strncmp(input, "u ", 2) == 0) { // upper case command char *rest; len = strtol(input + 2, &rest, 10); // how many characters of the string to upper-case rest += 1; // skip the first char (should be a space) out = malloc(len + strlen(input)); // could be shorter, but play it safe if (len > (int)strlen(input)) { printf("Specified length %d was larger than the input!\n", len); return 1; } else if (out == NULL) { printf("Failed to allocate memory\n"); return 1; } for (int i = 0; i != len; i++) { char c = rest[i]; if (c > 96 && c < 123) // ascii a-z { c -= 32; } out[i] = c; } out[len] = 0; strcat(out, rest + len); // append the remaining text printf("%s", out); free(out); } else if (strncmp(input, "head ", 5) == 0) { // head command if (strlen(input) > 6) { len = strtol(input + 4, &rest, 10); rest += 1; // skip the first char (should be a space) rest[len] = '\0'; // truncate string at specified offset printf("%s\n", rest); } else { fprintf(stderr, "head input was too small\n"); } } else if (strcmp(input, "surprise!\n") == 0) { // easter egg! *(char *)1 = 2; } else { return 1; } return 0;} int main(int argc, char *argv[]){ char *usage = "Usage: %s\n" "Text utility - accepts commands and data on stdin and prints results to stdout.\n" "\tInput | Output\n" "\t------------------+-----------------------\n" "\tu <N> <string> | Uppercased version of the first <N> bytes of <string>.\n" "\thead <N> <string> | The first <N> bytes of <string>.\n"; char input[INPUTSIZE] = {0}; // Slurp input if (read(STDIN_FILENO, input, INPUTSIZE) < 0) { fprintf(stderr, "Couldn't read stdin.\n"); } int ret = process(input); if (ret) { fprintf(stderr, usage, argv[0]); }; return ret;}编译中程序显示对52处位置进行了插桩。
预处理：.c生成.i 编译：.i生成.s，到汇编语言 汇编：.s生成.o，汇编语言到机器语言 链接：由.o生成可执行文件
存在一个判断标准，判断合法地址和非法地址 每个数据只能写在给他分配的位置上 会把原本相邻的变量隔离 需要更长的编译时间
三
Fuzz target
初始化
gettimeofday(&tv, &tz); srandom(tv.tv_sec ^ tv.tv_usec ^ getpid()); while ((opt = getopt(argc, argv, "+i:o:f:m:t:T:dnCB:S:M:x:Q")) > 0) switch (opt) { case 'i': /* input dir */ if (in_dir) FATAL("Multiple -i options not supported"); in_dir = optarg; …………setup_shm()
如果是forkserver，通过管道通信 fork出的子进程通过共享内存传输结果
/s数组定义EXP_ST u8 virgin_bits[MAP_SIZE], /* Regions yet untouched by fuzzing */ virgin_tmout[MAP_SIZE], /* Bits we haven't seen in tmouts */ virgin_crash[MAP_SIZE]; /* Bits we haven't seen in crashes */EXP_ST void setup_shm(void) {………… if (!in_bitmap) memset(virgin_bits, 255, MAP_SIZE); memset(virgin_tmout, 255, MAP_SIZE); memset(virgin_crash, 255, MAP_SIZE);virgin_bits记录尚未覆盖的区域 virgin_tmout记录timeout时的tuple信息 virgin_crash记录crash时的tuple信息
shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);………… trace_bits = shmat(shm_id, NULL, 0);0600权限代表，只有创建者可以进行读写
IPC_CREAT 如果共享内存不存在，则创建一个共享内存，否则打开操作。
IPC_EXCL 只有在共享内存不存在的时候，新的共享内存才建立，否则就产生错误。
Fork Server
由主进程创建的子进程，负责fork出fuzz对象，使用pipe和主进程通信。
管道只能在父子进程间通信，如果要实现祖孙进程通信，需要设置环境变量，孙进程通过环境变量获取文件描述符。
EXP_ST void init_forkserver(char** argv) { static struct itimerval it; int st_pipe[2], ctl_pipe[2]; int status; s32 rlen;forksrv_pid = fork();//子进程为forkserver if (forksrv_pid < 0) PFATAL("fork() failed"); //fork失败 if (!forksrv_pid) { //forkserver执行 ………… setsid(); //让子进程完全独立运行若定义了out_file，则把stdin重定向到dev_null_fd
否则关闭out_fd（间接关闭了stdin）
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);}if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed");if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed");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);/* Close the unneeded endpoints. */close(ctl_pipe[0]);close(st_pipe[1]); fsrv_ctl_fd = ctl_pipe[1];fsrv_st_fd = st_pipe[0];//等待返回消息it.it_value.tv_sec = ((exec_tmout * FORK_WAIT_MULT) / 1000);it.it_value.tv_usec = ((exec_tmout * FORK_WAIT_MULT) % 1000) * 1000; setitimer(ITIMER_REAL, &it, NULL);rlen = read(fsrv_st_fd, &status, 4); it.it_value.tv_sec = 0;it.it_value.tv_usec = 0;setitimer(ITIMER_REAL, &it, NULL);if (rlen == 4) { OKF("All right - fork server is up."); return;}fuzzing策略
存储输入样本 存储每次执行样本后的基本信息 链表连接
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 */ }; static struct queue_entry *queue, /* Fuzzing queue (linked list) */ *queue_cur, /* Current offset within the queue */ *queue_top, /* Top of the list */ *q_prev100; /* Previous 100 marker */static struct queue_entry* top_rated[MAP_SIZE]; /* Top entries for bitmap bytes */cull_queue()
if (dumb_mode || !score_changed) return;q = queue;while (q) { q->favored = 0; q = q->next;}for (i = 0; i < MAP_SIZE; i++) if (top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) { u32 j = MAP_SIZE >> 3; 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++; if (!top_rated[i]->was_fuzzed) pending_favored++; }q = queue; while (q) { mark_as_redundant(q, !q->favored); q = q->next; }queue_cycle++; current_entry = 0; cur_skipped_paths = 0; queue_cur = queue;while (seek_to) { current_entry++; seek_to--; queue_cur = queue_cur->next;}show_stats();if (not_on_tty) { ACTF("Entering queue cycle %llu.", queue_cycle); fflush(stdout); }if (queued_paths == prev_queued) { if (use_splicing) cycles_wo_finds++; else use_splicing = 1; } else cycles_wo_finds = 0; prev_queued = queued_paths;prev_queued = queued_paths;if (sync_id && queue_cycle == 1 && getenv("AFL_IMPORT_FIRST")) sync_fuzzers(use_argv);关键执行函数fuzz_one()
skipped_fuzz = fuzz_one(use_argv);终于到了最关键的地方。
if (pending_favored){ if ((queue_cur->was_fuzzed || !queue_cur->favored) && UR(100) < SKIP_TO_NEW_PROB) return 1;}当前已运行超过2轮，未被fuzz过的，跳过概率75%（就是说第一二次循环就会跳过很大一部分，这是由于perform_dry_run里已经跑过一轮测试了）。
否则，跳过概率95%。
else if (!dumb_mode && !queue_cur->favored && queued_paths > 10) { if (queue_cycle > 1 && !queue_cur->was_fuzzed) { if (UR(100) < SKIP_NFAV_NEW_PROB) return 1; } else { if (UR(100) < SKIP_NFAV_OLD_PROB) return 1; } }orig_in = in_buf = mmap(0, len, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);out_buf = ck_alloc_nozero(len);fuzz_one CALIBRATION
if (queue_cur->cal_failed)只有存在cal_failed被标记才会执行。
若测试时发生crash_mode(-C设置crash_mode为2，否则为0？)以外的fault。
非dumb_mode，且第一次测试运行后trace_bits为空。
设置timeout_given =2，则忽略FAULT_TMOUT。
未设置crash_mode时，设置环境变量AFL_SKIP_CRASHES为1，忽略FAULT_CRASH。
if (cal_failures == queued_paths)if (cal_failures * 5 > queued_paths)res = calibrate_case(argv, queue_cur, in_buf, queue_cycle - 1, 0);出现FAULT_ERROR，说明无法运行，直接放弃抢救，报错。 出现crash_mode，接着往下运行。 其他任何情况都跳过，cur_skipped_paths++。
fuzz_one TRIMMING
if (!dumb_mode && !queue_cur->trim_done){ u8 res = trim_case(argv, queue_cur, in_buf); ………… queue_cur->trim_done = 1; if (len != queue_cur->len) len = queue_cur->len;}memcpy(out_buf, in_buf, len);非dumb_mode且该case尚未trim时执行。
len_p2 = next_p2(q->len);remove_len = MAX(len_p2 / TRIM_START_STEPS, TRIM_MIN_BYTES);while (remove_len >= MAX(len_p2 / TRIM_END_STEPS, TRIM_MIN_BYTES))sprintf(tmp, "trim %s/%s", DI(remove_len), DI(remove_len));while (remove_pos < q->len){write_with_gap(in_buf, q->len, remove_pos, trim_avail);fault = run_target(argv, exec_tmout);cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);if (cksum == q->exec_cksum){……}else remove_pos += remove_len}如果不影响，保存这次缩减。
否则remove_pos后移步长remove_len。
remove_len >>= 1;if (needs_write){ck_write(fd, in_buf, q->len, q->fname);memcpy(trace_bits, clean_trace, MAP_SIZE);update_bitmap_score(q);}fuzz_one PERFORMANCE SCORE
1、调用calculate_score(queue_cur)计算当前queue_cur的score。
2、如果设置了skip_deterministic或者queue_cur->was_fuzzed或者queue_cur->passed_det=1
如果当前的queue_cur->exec_cksum % master_max不等于master_id - 1
跳转havoc_stage
fuzz_one变异
SIMPLE BITFLIP (+dictionary construction)阶段 ARITHMETIC INC/DEC 阶段 INTERESTING VALUES阶段 DICTIONARY STUFF阶段 RANDOM HAVOC阶段 SPLICING阶段
SIMPLE BITFLIP (+dictionary construction)阶段
#define FLIP_BIT(_ar, _b) do { \ u8* _arf = (u8*)(_ar); \ u32 _bf = (_b); \ _arf[(_bf) >> 3] ^= (128 >> ((_bf) & 7)); \ } while (0)bitflip 1/1
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);……}1、第一个翻转会遍历case中的每一位，每次翻转1个bit。
2、如果翻转后，common_fuzz_stuff()返回1，就直接跳过整个case，否则把这个bit再翻转回来。
3、检测token并添加。
maybe_add_auto(a_collect, a_len);从注释上理解token得概念：如果在某一段连续bit上进行连续翻转后，都能让程序产生新的路径，就称连续翻转的这些bit为一个token。
write_to_testcase(out_buf, len);fault = run_target(argv, exec_tmout);if (fault == FAULT_TMOUT) { if (subseq_tmouts++ > TMOUT_LIMIT) { cur_skipped_paths++; return 1; } } else subseq_tmouts = 0;bitflip 2/1
bitflip 4/1
bitflip 8/8
eff_map[0] = 1;if (EFF_APOS(len - 1) != 0) { eff_map[EFF_APOS(len - 1)] = 1; eff_cnt++;}if (cksum != queue_cur->exec_cksum) { eff_map[EFF_APOS(stage_cur)] = 1; eff_cnt++;}if (eff_cnt != EFF_ALEN(len) && eff_cnt * 100 / EFF_ALEN(len) > EFF_MAX_PERC) { memset(eff_map, 1, EFF_ALEN(len)); blocks_eff_select += EFF_ALEN(len);}bitflip 16/8
bitflip 32/8
ARITHMETIC INC/DEC 阶段
arith 8/8
for (i = 0; i < len; i++){u8 orig = out_buf[i];}if (!eff_map[EFF_APOS(i)])for (j = 1; j <= ARITH_MAX; j++)u8 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--;r = orig ^ (orig - j);if (!could_be_bitflip(r)) { stage_cur_val = -j; out_buf[i] = orig - j; ……} else stage_max--;out_buf[i] = orig;arith 16/8
arith 32/8
INTERESTING VALUES阶段
static s8 interesting_8[] = { INTERESTING_8 };static s16 interesting_16[] = { INTERESTING_8, INTERESTING_16 };static s32 interesting_32[] = { INTERESTING_8, INTERESTING_16, INTERESTING_32 };interest 8/8
for (i = 0; i < len; i++)if (!eff_map[EFF_APOS(i)])for (j = 0; j < sizeof(interesting_8); j++)if (could_be_bitflip(orig ^ (u8)interesting_8[j]) || could_be_arith(orig, (u8)interesting_8[j], 1))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;interest 16/8
interest 32/8
DICTIONARY STUFF阶段
user extras (over)
for (i = 0; i < len; i++)for (j = 0; j < extras_cnt; j++)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)))替换token后长度超过case原大小。
case中数据与token一致。
eff_map为0。
last_len = extras[j].len;memcpy(out_buf + i, extras[j].data, last_len); if (common_fuzz_stuff(argv, out_buf, len))memcpy(out_buf + i, in_buf + i, last_len);user extras (insert)
auto extras (over)
if (!queue_cur->passed_det) mark_as_det_done(queue_cur);RANDOM HAVOC阶段
SPLICING阶段
看雪ID：Azyka
https://bbs.pediy.com/user-home-958400.htm
# 往期推荐
4.恭喜ID[飞翔的猫咪]获看雪安卓应用安全能力认证高级安全工程师！
球分享
球点赞
球在看
点击“阅读原文”，了解更多！