afl源码分析
afl-gcc.c分析
首先看到main函数,里面包含
1 | find_as(argv[0]); |
这几个主要函数,下面我们逐个分析
find_as
寻找as和afl-as是否存在且可执行
edit_params
将参数传给gcc
1 | pwndbg> p *cc_params@20 |
execvp
执行被包装的gcc
总结
afl-gcc是gcc的一个包装,给gcc设置参数并运行它。
afl-fuzz.c
首先看到main函数
while ((opt = getopt(argc, argv, “+i:o:f:m:t:T:dnCB:S:M:x:Q”)) > 0)
这个循环获取各种环境的设置,选项参数等等
各种模式 参数选项
usage(argv[0])
显示用法提示
setup_signal_handlers();
设置信号处理程序
check_asan_opts();
检查ASAN选项
fix_up_sync
使用-S时验证并修复out_dir和sync_dir。
一堆检查等
1 | if (!strcmp(in_dir, out_dir))//检查输入输出路径是否一致 |
save_cmdline(argc, argv);
复制当前命令行
fix_up_banner(argv[optind]);
修整并创建run时的banner
check_if_tty();
检查是否在TTy终端上面运行。影响not_on_tty。
cpu检查
1 | get_core_count();//获取核心数量 |
setup_post();
加载后处理器,如果可用的话
setup_shm();
设置共享内存块,trace_bits参数就是在这里设置并初始化置零的。
init_count_class16();
初始化count_class_lookup16数组,该数组的作用是帮助快速归类统计路径覆盖的数量
setup_dirs_fds();
创建所有的输出目录,打开部分全局的文件句柄。创建输出目录queue、crashes、hangs等,打开文件句柄dev_null_fd、dev_urandom_fd以及plot_file等。
read_testcases();
逐个读取种子目录下的输入文件列表,并调用add_to_queue函数将相关信息(文件名称、大小等)存入到全局的种子队列queue当中,作为后续模糊测试的种子来源。单个种子信息保存在结构体queue_entry当中,形成单链表。
1 | if (!access(dfn, F_OK)) passed_det = 1; |
检查这个种子是否有贡献(比如是否产生了新路径,运行的时间长短来判断),pass_det这一项就置为1表示循环fuzz的时候将跳过该种子。
add_to_queue(fn, st.st_size, passed_det);
将新的测试用例插入队列,并初始化fname文件名称,增加cur_depth深度++ queued_paths测试用例数量++,pending_not_fuzzed没被fuzzed测试用例数量++,更新last_path_time = get_cur_time()。
load_auto();
加载自动生成的附加组件
1 | if (len >= MIN_AUTO_EXTRA && len <= MAX_AUTO_EXTRA) |
pivot_inputs();
根据相应的种子文件路径在输出目录下创建链接或拷贝至该目录下,形成orignal文件,文件命名的规则是%s/queue/id:%06u,orig:%s”, out_dir, id, use_name,并更新至对应的种子信息结构体queue_entry中。
使用函数link_or_copy重新命名并且拷贝;使用函数mark_as_det_done为已经经过确定性变异(deterministic)阶段的testcase文件放入deterministic_done文件夹。这样经过deterministic的testcase就不用浪费时间进行重复。
load_extras
如果指定了-x参数(字典模式),加载对应的字典到全局变量extras当中,用于后续字典模式的变异当中。
find_timeout
如果有-t的设置了自己的超时,那么会触发这个函数。
detect_file_args
检测输入的命令行中是否包含@@参数,如果包含的话需要将@@替换成目录文件”%s/.cur_input”, out_dir,使得模糊测试目标程序的命令完整;同时将目录文件”%s/.cur_input”路径保存在out_file当中,后续变异的内容保存在该文件路径中,用于运行测试目标文件。
setup_stdio_file
如果目标程序的输入不是来源于文件而是来源于标准输入的话,则将目录文件”%s/.cur_input”文件打开保存在out_fd文件句柄中,后续将标准输入重定向到该文件中;结合detect_file_args函数实现了将变异的内容保存在”%s/.cur_input”文件中,运行目标测试文件并进行模糊测试。
check_binary(argv[optind]);
搜索路径,找到目标二进制文件,检查文件是否存在,是否为shell脚本,同时检查ELF头以及程序是否被插桩。
检查
用start_time=get_cur_time() 获取开始时间;
检查是不是QEMU_MODE
★开始第一遍fuzz —— perform_dry_run
执行input文件夹下的预先准备的所有testcase(perform_dry_run),生成初始化的queue和bitmap。这只对初始输入执行一次,所以叫:dry run。
a. 第一个是个while循环,遍历之前生成的input_queue 也就是queue链表。该while(q) loop 的前面,准备工作:从队列中取出q->fname 读取该文件q->len 大小到use_mem 中,关闭fd
b. 接着调用calibrate_case函数对该case进行校准。该函数内调用方式res = calibrate_case(argv, q, use_mem, 0, 1);
c. 根据校准的返回值res ,查看是哪种错误并进行判断。一共有一下几种错误类型。
1 | enum { |
d. 打印一些错误信息,退出函数。
★perform_dry_run -> calibrate_case函数
校准一个新的测试用例。这是在处理输入目录时完成的,以便在早期就警告有问题的测试用例;当发现新的路径来检测变量行为等等。
这个函数是AFL的重点函数之一,在perform_dry_run,save_if_interesting,fuzz_one,pilot_fuzzing,core_fuzzing函数中均有调用。
步骤:
a. 进行一系列参数设置,包括当前阶段stage_cur,阶段名称stage_name,新比特new_bit等初始化设置。
b. 最后一个参数from_queue,判断是否是为队列中的||刚恢复fuzz 以此设置较长的时间延迟。testcase参数q->cal_failed++ 是否校准失败参数++
c. 判断是否已经启动forkserver ,调用函数init_forkserver()启动fork服务。
d. 拷贝trace_bits到first_trace,并获取开始时间start_us;
e. -loop- 该loop循环多次执行这个testcase,循环的次数 8次或者3次,取决于是否快速校准。对同一个初始testcase多次运行的意义可能是,觉得有些targetApp执行同一个testcase可能也会出现不同的路径(这是我的猜测)
f. static void write_to_testcase(void* mem, u32 len) 将修改后的数据写入文件进行测试。如果use_stdin被清除了,那么取消旧文件链接并创建一个新文件。否则,prog_in_fd将被缩短。将testcase写入到文件中去。该函数较简单,不做单独解释。
g. run_target作用是通知forkserver可以开始fork并且fuzz了。
h. cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST)校验此次运行的trace_bits,检查是否出现新的情况。hash32函数较为简单,不多做分析。
i. 这段代码的主要意思是先用cksum也就是本次运行的出现trace_bits哈希和本次testcase q->exec_cksum对比。如果发现不同,则调用has_new_bits函数和我们的总表virgin_bits 对比。
j. 判断q->exec_cksum 是否为0,不为0那说明不是第一次执行。后面运行的时候如果,和前面第一次trace_bits结果不同,则需要多运行几次。这里把校准次数设为40…
k. -loop-end-
l. 接着收集一些关于这个测试用例性能的统计数据。比如执行时间延迟,校准错误?,bitmap大小等等。
m. update_bitmap_score(q) 对这个测试用例的每一个byte进行排序,用一个top_rate[]来维护它的最佳入口。维护完成之后,我们这个函数在
n. 如果这种情况没有从检测中得到new_bit,则告诉父程序。这是一个无关紧要的问题,但是需要提醒用户注意。
★perform_dry_run -> calibrate_case -> init_forkserver
★ perform_dry_run -> calibrate_case -> run_target()
★perform_dry_run -> calibrate_case -> has_new_bits()
★perform_dry_run -> calibrate_case -> update_bitmap_score()
★cull_queue()
static void cull_queue(void) 精简队列,上面第二个被讨论的机制是:检查toprated[]类目,以此前未见过的byte依次争夺优胜者,然后把他们标记为favored在下次开始跑之前。根据top_rated设置queue中的favored标志。在fuzz的过程中favored 条目将会给与更多的时间。
为了优化模糊工作,AFL使用快速算法定期重新评估队列,该算法选择一个较小的测试用例子集,该子集仍覆盖到目前为止所看到的每个元组,并且其特征使它们对Fuzzing特别有利。该算法通过为每个队列条目分配与其执行延迟和文件大小成正比的分数来工作;然后为每个tuples选择最低得分候选者。
cull_queue()遍历top_rated[]中的queue,然后提取出发现新的edge的entry,并标记为favored,使得在下次遍历queue时,这些entry能获得更多执行fuzz的机会。
这里本质上采用了贪婪算法,如果top_rated[i]存在,且对应temp_v[]中对应bit位还没抹去,即这一轮选出的queue还没覆盖bit_map[i]对应的边,则取出这个top_rated[i]。抹去temp_v中top_rated[i]能访问到的位。最后将这个top_rated[i]标记为favored,如果这个queue还没fuzzed,pending_favored++。
具体步骤:
a. 如果是dumb模式或者score_changed没有改变,也就是没有出现新的“favored”竞争者,那么函数直接返回,因为没有校准的意义。
b. 挨个遍历bitmap中的每个byte;核心代码如下:
1 | or (i = 0; i < MAP_SIZE; i++) |
这里需要结合update_bitmap_score()进行理解。update_bitmap_score在trim_case和calibrate_case中被调用,用来维护一个最小(favored)的测试用例集合(top_rated[i])。这里会比较执行时间*种子大小,如果当前用例更小,则会更新top_rated。结合以下事例更容易理解。
1 | tuple t0,t1,t2,t3,t4;seed s0,s1,s2 初始化temp_v=[1,1,1,1,1] |
c. 将queue中冗余的testcase进行标记 ,使用函数mark_as_redundant,位置/queue/.state/redundant_edges/中。
sync_fuzzers()
读取其他fuzz的queue中的case文件,然后保存到自己的queue里
★ fuzz_one()
static u8 fuzz_one_original(char** argv)从队列中取出当前testcase并模糊。这个函数太长了…如果fuzzed成功,返回0;如果跳过或退出,返回1。
步骤:
根据是否有pending_favored和queue_cur的情况按照概率进行跳过;有pending_favored, 对于fuzz过的或者non-favored的以概率99%跳过;无pending_favored,95%跳过fuzzed&non-favored,75%跳过not fuzzed&non-favored,不跳过favored。
假如当前项有校准错误,并且校准错误次数小于3次,那么就用calibrate_case进行测试。
如果测试用例没有修剪过,那么调用函数[trim_case](★ trim_case())对测试用例进行修剪。
修剪完毕之后,使用calculate_score对每个测试用例进行打分
如果该queue已经完成deterministic阶段,则直接跳到havoc阶段:
1
2
3
4
5
6
7
8
9/* 如果给定了-d,如果我们自己对此条目进行了确定性模糊处理(was_fuzize),或者如果它在之前的恢复运行中经过了确定性测试(passed_det),请立即跳过。*/
if (skip_deterministic || queue_cur->was_fuzzed || queue_cur->passed_det)
goto havoc_stage;
/* 如果exec路径校验和超出了此主实例的范围,则跳过确定性模糊。 */
if (master_max && (queue_cur->exec_cksum % master_max) != master_id - 1)
goto havoc_stage;deterministic阶段变异4个stage,变异过程中会多次调用函数common_fuzz_stuff函数见3.8,保存interesting 的种子:
bitflip,按位翻转,1变为0,0变为1
arithmetic,整数加/减算术运算
interest,把一些特殊内容替换到原文件中
dictionary,把自动生成或用户提供的token替换/插入到原文件中
havoc,中文意思是“大破坏”,此阶段会对原文件进行大量变异。
splice,中文意思是“绞接”,此阶段会将两个文件拼接起来得到一个新的文件。详细变异策略见3.7。
该 testcase完成。
★ trim_case()
static u8 trim_case(char** argv, struct queue_entry* q, u8* in_buf)在进行确定性检查时,修剪所有新的测试用例以节省周期。修剪器使用文件大小的1/16到1/1024之间的2次方增量,速度和效率的折中。
step:
- 首先取testcase长度2的指数倍
- 第一个while循环,从文件大小1/16的步长开始,慢慢到文件大小的1/1024倍步长。
- 第二个while循环,嵌套在第一个内,从文件头开始按步长cut testcase,然后target_run();如果删除之后对文件执行路径没有影响那么就将这个删除保存至实际文件中。再删除之前会将trace_bits保存到起来。删除完成之后重新拷贝。如果不清楚看下面代码。
1 | static u8 trim_case(char** argv, struct queue_entry* q, u8* in_buf) { |
文件大小对模糊性能有很大影响,这是因为大文件使目标二进制文件变得更慢,并且因为它们减少了突变将触及重要的格式控制结构而不是冗余数据块的可能性。这在perf_tips.txt中有更详细的讨论。
用户可能会提供低质量的起始语料库,某些类型的突变可能会产生迭代地增加生成文件的大小的效果,因此应对这一趋势是很重要的。
幸运的是,插装反馈提供了一种简单的方法来自动删除输入文件,同时确保对文件的更改不会对执行路径产生影响。
在afl-fuzz中内置的修边器试图按可变长度和stepover顺序删除数据块;任何不影响跟踪映射校验和的删除都被提交到磁盘。修剪器的设计并不是特别彻底;相反,它试图在精度和在进程上花费的execve()调用的数量之间取得平衡,选择块大小和stepover来匹配。每个文件的平均增益大约在5%到20%之间。
独立的afl-tmin工具使用了更详尽的迭代算法,并尝试在修剪过的文件上执行字母标准化。afl-tmin的操作如下。
首先,工具自动选择操作模式。如果初始输入崩溃了目标二进制文件,afl-tmin将以非插装模式运行,只需保留任何能产生更简单文件但仍然会使目标崩溃的调整。如果目标是非崩溃的,那么这个工具使用一个插装的模式,并且只保留那些产生完全相同的执行路径的微调。