AFL使用与源码分析

建议Fuzz的哥们都从这儿入门，AFL可是一己之力造就了Fuzzing的辉煌时代~

AFL

基于覆盖率为导向的模糊测试工具

fuzzing 101

exercise 1 CVE-2019-13288

学习AFL工具的基础使用

# AFL工具下载
sudo apt-get update
sudo apt-get install -y build-essential python3-dev automake git flex bison libglib2.0-dev libpixman-1-dev python3-setuptools
sudo apt-get install -y lld-11 llvm-11 llvm-11-dev clang-11 || sudo apt-get install -y lld llvm llvm-dev clang 
sudo apt-get install -y gcc-$(gcc --version|head -n1|sed 's/.* //'|sed 's/\..*//')-plugin-dev libstdc++-$(gcc --version|head -n1|sed 's/.* //'|sed 's/\..*//')-dev

cd $HOME
git clone https://github.com/AFLplusplus/AFLplusplus && cd AFLplusplus
export LLVM_CONFIG="llvm-config-12"
make distrib		#网络不好可能会报错，部分模式可能用不了，例如unicorn
sudo make install

# 使用afl-gcc编译目标程序，这是因为通过afl编译，会在目标程序中插桩，反馈程序运行状态信息。
# 去到目标程序目录
export LLVM_CONFIG="llvm-config-12"
# C程序编译器选择为afl-clang-fast C++程序编译器选择为afl-clang-fast++ --prefix选项是选择编译后可执行文件及依赖存放的位置
CC=$HOME/AFLplusplus/afl-clang-fast CXX=$HOME/AFLplusplus/afl-clang-fast++ ./configure --prefix="$HOME/fuzzing_xpdf/install/"
make
make install

# 使用Afl开始进行fuzz
afl-fuzz -i $HOME/fuzzing_xpdf/pdf_examples/ -o $HOME/fuzzing_xpdf/out/ -s 123 -- $HOME/fuzzing_xpdf/install/bin/pdftotext @@ $HOME/fuzzing_xpdf/output

# 如果出现"core_pattern" 错误
sudo su
echo core >/proc/sys/kernel/core_pattern
exit
SHELL

参数说明：

-i 指示输入文件目录

-o 指示存储变异文件的目录，包括crash等等

-s 指示要使用的静态随机种子

@@

gdb的使用

# 在编译时加相关参数
CFLAGS="-g -O0" CXXFLAGS="-g -O0" ./configure --prefix="$HOME/fuzzing_xpdf/install"
make
make install

# gdb调试
gdb --args <调试的程序名> <输入>
SHELL

exercise 2 CVE-2009-3895

学习AFL++的lto模式

LTO模式需要LLVM和clang版本大于11，该模式通常是最佳的。随后依次是afl-clang-fast/afl-clang-fast++和afl-gcc-fast/afl-g++-fast。关于为什么LTO模式通常是最佳的，在未来源码阅读时应该能解释。

1	`# 同样的过程，只不过在编译插桩时，使用afl-clang-lto进行编译即可` SHELL

exercise 3 CVE-2017-13028

使用ASan

ASan时AddressSanitizer的一个C和C++的内存错误检查工具，包含一个编译器插桩模块和一个运行时库，可以发现对堆、栈和全局对象的越界访问、释放后重利用、双重释放和内存泄漏等错误。

# 使用ASan
# 指定AFL_USE_ASAN=1 编译选项再使用afl-clang-lto即可
AFL_USE_ASAN=1 CC=$HOME/AFLplusplus/afl-clang-lto ./configure --prefix=$HOME/fuzzing_tcpdump/tcpdump_install/
AFL_USE_ASAN=1 make
AFL_USE_ASAN=1 make install
SHELL

ASan这个工具，对于FUZZ来说其实是一个负面的作用，因为它的存在，再进行插桩时会造成内存的严重消耗。但是它的主要作用是在crash分析上，我们可以无需经过动态调试(gdb)，就可以得到cransh的相关信息和数据。

1
2

# 注意，在运行afl-fuzz的时候，如果开启了ASan，那么就需要使用参数-m none
afl-fuzz -m none -i $HOME/fuzzing_tcpdump/tcpdump-tcpdump-4.9.2/tests/ -o $HOME/fuzzing_tcpdump/out/ -s 123 -- $HOME/fuzzing_tcpdump/tcpdump_install/sbin/tcpdump -vvvvXX -ee -nn -r @@
SHELL

-m none是取消内存限制，因为ASan会使用大量的内存

使用ASan后，gdb调试时就不需要再编译了，直接把crash文件作为参数传入即可

exercise 4 CVE-2016-9297

lcov工具的使用

lcov是gcc测试覆盖率的前端图形展示工具。它通过收集多个源文件的行、函数和分支的代码覆盖信息（程序执行之后生成gcda、gcno文件）并且将收集后的信息生成HTML页眉。

# 第一步是需要在编译时，选择参数 --coverage
CFLAGS="--coverage" LDFLAGS="--coverage" ./configure --prefix="$HOME/fuzzing_tiff/install/" --disable-shared
make
make install

# 第二步是利用lcov生成覆盖率信息
cov --zerocounters --directory ./
lcov --capture --initial --directory ./ --output-file app.info
$HOME/fuzzing_tiff/install/bin/tiffinfo -D -j -c -r -s -w $HOME/fuzzing_tiff/tiff-4.0.4/test/images/palette-1c-1b.tiff
lcov --no-checksum --directory ./ --capture --output-file app2.info
SHELL

lcov --zerocounters --directory ./ : 重置之前的计数

lcov --capture --initial --directory ./ --output-file app.info : -c捕获，-i初始化,-d应用的目录，-o输出文件

$HOME/fuzzing_tiff/install/bin/tiffinfo -D -j -c -r -s -w $HOME/fuzzing_tiff/tiff-4.0.4/test/images/palette-1c-1b.tiff：执行目标程序，以及目标程序的输入文件。

lcov --no-checksum --directory ./ --capture --output-file app2.info：将当前覆盖状态保存到app2.info中

1
2
3

# 最后使用genhtml将覆盖率信息转为html文件
genhtml --highlight --legend -output-directory ./html-coverage/ ./app2.info
# 最后打开这个html文件，即可看到更直观的代码覆盖率信息
SHELL

exercise 5 CVE-2017-9048

多实例进行fuzz

# master instance
./afl-fuzz -i afl_in -o afl_out -M Master -- ./program @@
# N-1 number of slaves
./afl-fuzz -i afl_in -o afl_out -S Slave1 -- ./program @@
./afl-fuzz -i afl_in -o afl_out -S Slave2 -- ./program @@
...
./afl-fuzz -i afl_in -o afl_out -S SlaveN -- ./program @@
SHELL

afl的字典功能——dictionary

字典就是告诉AFL应该基于什么模板去进行变异，变异后的数据要符合模板的相关结构。这样能大大提高变异后数据有效性

1
2

# afl使用-x指定字典
afl-fuzz -m none -i ./afl_in -o afl_out -s 123 -x $HOME/AFLplusplus/dictionaries/xml.dict -D -M master -- ./xmllint --memory --noenc --nocdata --dtdattr --loaddtd --valid --xinclude @@
SHELL

exercise 6 CVE-2016-4994

afl的persistent模式

在persistent模式下，AFL++在单个fork进程中对目标进行多次模糊测试，而不是为每次模糊测试执行fork一个新进程。该模式可以将模糊测试速度提高20倍。

exercise 8 CVE-2019-14776

之前都是白盒，有源码的。现在使用afl的qemu-mode对可执行文件进行fuzz

-Q 选项开启QEMU mode

ACRO_INSTALL_DIR=/opt/Adobe/Reader9/Reader ACRO_CONFIG=intellinux LD_LIBRARY_PATH=$LD_LIBRARY_PATH:'/opt/Adobe/Reader9/Reader/intellinux/lib' afl-fuzz -Q -i ./afl_in/ -o ./afl_out/ -t 2000 -- /opt/Adobe/Reader9/Reader/intellinux/bin/acroread -toPostScript @@
SHELL

AFL Source Code Analysis

afl-gcc.c

第一个函数为find_as

AFL_PATH环境变量存在，检查其目录下/as文件是否可以访问。可访问则赋值给as_path

AFL_PATH环境变量不存在，检查argv[0]参数（存储afl-gcc.c的文件目录+文件名称），取目录为dir，并且检查dir/afl-as是否可访问，若可访问则dir赋值给as_path

第二个函数为edit_params

该函数的主要作用是设置参数，设置编译器(gcc/g++/clang/clang++)。对各个参数进行设置，例如如果存在-fsanitize=address，就设置asan_set为1

main函数

调用以上函数，并调用execvp函数来执行目标文件。

Assembly Language x86

汇编文件后缀.s，用汇编器(Assembler)as把汇编程序中的助记符翻译成机器指令，随机生成目标文件后缀.o。之后使用链接器(linker)将目标文件链接成可执行文件。

# 注释

.section 在汇编程序中由.开头的名称并不是助记符，不会被编译成机器指令，而是用于给汇编器一些指令，称为汇编指示或伪操作。其中section是用于便于汇编器将程序分段，之后被操作系统加载到不同的页，给不同的段设置不同的权限。

.data 用于声明变量的，相当于C语言中的全局变量。

.text 是用于存放代码的段，是只读、可执行的。其后的指令都属于.text段

.globl _start 声明了一个符号，_start是一个符号，符号在汇编语言中代表一个地址，可以用在指令中，在汇编之后所有的符号都会被替换为相应的地址，就像在C语言中我们用变量名来访问变量，其实就是在访问变量所在的地址，调用函数，就是跳转到函数的第一条指令所在的地址，所以变量名和函数名都是符号，代表相应的地址。.globl指示是用于告诉汇编器，_start要被链接器用到，所以在目标文件的表中标记它是一个全局符合。_start就相当于C语言中的main函数，是程序的入口，需要使用.globl声明，链接器在链接过程中要去寻找_start作为程序入口。如果一个符号没有用.globl声明，那么就不会被链接器用到。

_start: 程序入口

afl-as.c

afl-as是afl使用的汇编器，主要是用来给代码插桩。

第一个函数为edit_params

检查并修改参数传递给as。主要是设置as_params的值，以及use_64bit/modified_file的值

第二个函数为add_instrumentation

明确一点，插桩只在.text部分才会进行。插桩是为了反应程序执行状态，所以必须放在汇编.text部分，才能被执行，插桩才是有效的。

而这个函数主要是读取汇编程序，然后逐行分析，是否该行后是否需要插桩。而插桩的条件十分简单粗暴

插桩的条件：

^func:			- 函数入口点
^.L0:			- GCC 的分支标签
^.LBB0_0:		- calng 的分支标签
^\tjnz foo		- 条件分支语句，例如循环，判断语句等
ASSEMBLY

通过判断汇编的前导符号/标签来判断这是否是一个分支或者函数，然后插入instrumentation trampoline.

main函数

设置inst_ratio_str，控制插桩密度等

主要作用是设置各种环境变量

afl-clang-fast.c

afl-clang-fast.c其实就是clang的一层封装(wrapper)，与之前的afl-gcc一样，指示定义了一些宏，传递了一些参数给真正的clang而已。

因为AFL对于之前afl-gcc的插桩做法不建议，并提供了更好的工具afl-clang-fast，通过llvm pass来插桩。

第一个函数find_obj

主要是调用afl-clang-fast，三种方式：

获取环境变量AFL_PATH的值，如果存在则读取AFL_PATH/afl-llvm-rt.o，如果可以访问该文件则设置该目录为obj_path

如果没有环境变量，则检查arg0是否存在/，因为通过终端形式调用afl-clang-fast也很常见。读取该目录下afl-llvm-rt.o文件，此时认为最后一个/之前的目录为obj_path。

默认的AFL的MakeFile在编译时会定义一个名为AFL_PATH的宏，其指向/usr/local/lib/afl，则在此处寻找afl-llvm-rt.o文件，如果能够访问，同理设置obj_path。

三种方式行不通，则抛出异常Unable to find 'afl-llvm-rt.o' or 'afl-llvm-pass.so'. Please set AFL_PATH

第二个函数edit_params

根据环境变量，用户指定参数来设置参数、宏等。

main函数

寻找obj_path路径

编辑cc_params参数：选择clang,clang++等

AFL++

CmpLog

To Finish…

记一次Fuzzing(使用ShapFuzz) - Debug

一次完整的Fuzzing过程，从main函数处打断点。执行记录如下

调用afl-common.c文件中的get_map_size()

这个函数通过获取环境变量中的”AFL_MAP_SIZE”和”AFL_MAPSIZE”的值并将其返回。本次运行时，map_size的值为0x800000

调用完成，回到主函数，继续获取环境变量中的”AFL_NO_COLOR”和”AFL_NO_COLOUR”

switch colored console output off 关闭彩色控制台输出。

随后调用afl-common.c文件中的argv_cpy_dup(argc,argv_orig);用一个char **ret存储了所有的argv。最后返回ret。

使用calloc给afl_state_t类型的变量指针变量*afl开辟空间

1 2	`//指针afl指向一个afl_state_t的内存块，该内存块大小为sizeof(afl_state_t) afl_state_t *afl = calloc(1, sizeof(afl_state_t));` C

随后调用函数afl-common.c文件中的get_afl_env()来判断”AFL_DEBUG”环境变量是否被设置，若被设置，那么debug=afl->debug=1。

随后调用afl-fuzz-state.c文件中的afl_state_init(afl,map_size)对afl_state_t这个结构体进行初始化。

先执行memset(afl, 0, sizeof(afl_state_t));对afl指向的地址块赋0；

afl->shm.map_size = map_size?map_size:MAP_SIZE对结构体的shm.map_size进行赋值操作。选取map_size和全局变量MAP_SIZE中较大的那个。

afl->w_init=0.9;afl->w_end=0.3;afl->g_max=5000;afl->period_pilot_tmp=5000.0初始化这些变量，现在还不知道它们干嘛的。

afl->schedule = FAST;能量调度方式，默认为FAST

afl->havoc_max_mult = HAVOC_MAX_MULT;havoc变异时，每个字节的最大修改次数。

剩余的初始化代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
afl->clear_screen = 1;                /* Window resized?                  */
afl->havoc_div = 1;                   /* Cycle count divisor for havoc    */
afl->stage_name = "init";             /* Name of the current fuzz stage   */
afl->splicing_with = -1;              /* Splicing with which test case?   */
afl->cpu_to_bind = -1;
afl->havoc_stack_pow2 = HAVOC_STACK_POW2; //控制havoc变异策略用于存储变异操作的栈的大小。
afl->hang_tmout = EXEC_TIMEOUT;
afl->exit_on_time = 0;
afl->stats_update_freq = 1;
afl->stats_avg_exec = 0;
afl->skip_deterministic = 1;
afl->cmplog_lvl = 2;
afl->min_length = 1;
afl->max_length = MAX_FILE;
#ifndef NO_SPLICING
afl->use_splicing = 1;
#endif
afl->q_testcase_max_cache_size = TESTCASE_CACHE_SIZE * 1048576UL;
afl->q_testcase_max_cache_entries = 64 * 1024;

C
HAVOC_STACK_POW2：havoc变异策略会对输入数据进行一系列的随机修改，以生成新的测试用例。为了提高效率，AFL++会在havoc过程中维护一个栈，用于存储一系列的变异操作。而HAVOC_STACK_POW2可控制着这个栈的大小，这个栈的大小决定了AFL++在一次havoc变异过程中可以执行的变异操作的最大数量。

TESTCASE_CACHE_SIZE:AFL++中用于控制测试用例缓存大小的环境变量。AFL++使用了一个缓存来存储已经执行过的测试用例，以便在下次执行时快速检索，避免重复执行。默认值是8MB。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
afl->virgin_bits = ck_alloc(map_size);
afl->virgin_tmout = ck_alloc(map_size);
afl->virgin_crash = ck_alloc(map_size);
afl->var_bytes = ck_alloc(map_size);	// 存储在fuzzing过程中用到的变异字节数据，一个u8类型数组的指针。
afl->top_rated = ck_alloc(map_size * sizeof(void *)); // 存储经过排序的测试用例的指针
afl->clean_trace = ck_alloc(map_size);
afl->clean_trace_custom = ck_alloc(map_size);
afl->first_trace = ck_alloc(map_size);
afl->map_tmp_buf = ck_alloc(map_size);

afl->fsrv.use_stdin = 1;
afl->fsrv.map_size = map_size;
// afl_state_t is not available in forkserver.c
afl->fsrv.afl_ptr = (void *)afl;
afl->fsrv.add_extra_func = (void (*)(void *, u8 *, u32)) & add_extra;
afl->fsrv.exec_tmout = EXEC_TIMEOUT;
afl->fsrv.mem_limit = MEM_LIMIT;
afl->fsrv.dev_urandom_fd = -1;
afl->fsrv.dev_null_fd = -1;
afl->fsrv.child_pid = -1;
afl->fsrv.out_dir_fd = -1;
C
virgin_bits，virgin_tmout,virgin_crash分别是初始状态下，目标程序执行过程中覆盖的代码分支，目标程序的执行时间和目标程序是否崩溃。

afl->fsrv_t结构体，用于管理AFL++的Fork Server。

fsrv_t 结构体包含了 Fork Server 的各种配置和状态信息，包括：

use_stdin: 表示是否使用标准输入 (stdin) 来接收测试用例，默认为 1。

map_size: 表示用于存储执行路径信息的映射表的大小。

afl_ptr: 指向 afl_state_t 结构体的指针，用于在 Fork Server 中访问 afl_state_t 结构体中的信息。

add_extra_func: 指向一个函数指针，用于添加额外的测试用例。

exec_tmout: 表示每个测试用例的执行超时时间。

mem_limit: 表示目标程序的内存使用限制。

dev_urandom_fd: 表示随机数设备文件的描述符。

dev_null_fd: 表示空设备文件的描述符。

child_pid: 表示子进程的进程 ID。

out_dir_fd: 表示输出目录的文件描述符。

随后会调用read_afl_environment()函数，根据诸多环境对afl_state_t这个结构体进行初始化赋值。

doc_path被初始化为：$(PREFIX)/share/doc/afl。然后调用gettimeofday(&tv,&tz)获取当前时间，并存入tv和tz两个结构体中。

执行rand_set_seed(afl, tv.tv_sec ^ tv.tv_usec ^ getpid());该函数在afl-performance.c文件。基于时间生成随机数，存于afl->init_seed,afl->rand_seed[0,1,2]中。

再设置afl->shmem_testcase_mode为1，默认使用共享内存来传递测试用例。

随后是一个循环，调用getopt函数解析命令行参数，并根据参数设置相应的配置选项。

while (
(opt = getopt(
  argc, argv,
  "+Ab:B:c:CdDe:E:hi:I:f:F:g:G:l:L:m:M:nNOo:p:RQs:S:t:T:UV:WXx:YZwku")) >
      0) {
C

"+Ab:B:c:CdDe:E:hi:I:f:F:g:G:l:L:m:M:nNOo:p:RQs:S:t:T:UV:WXx:YZwku"字符串用于指定命令行参数的选项和参数类型。getopt函数每次调用都会解析下一个命令行参数。

afl->in_dir // 种子池
afl->out_dir // 输出文件夹
afl->fixed_seed // 默认值为0，即AFL++使用随机种子，每次运行fuzzing时，都会产生不同的变异序列。为1时，AFL++使用固定的种子，每次运行fuzzing时都会产生相同的变异序列。
afl->fsrv.mem_limit //为0取消内存限制，其余值即限制内存大小（单位为字节）
C

跳出循环后，使用unlikely判断afl->afl_env.afl_persistent_record是否为空指针。若不为空则FATAL错误。

afl_persistent_record指针指向afl_persistent_record_t结构体，通过这个指针，AFL++可以访问和更新持久化数据，持久化的意思是，下次启动AFL++能继续使用。此外，通过这个指针还能恢复执行状态，记录Crash等。

随后调用函数parse_afl_kill_signal_env()函数用来分析终止信号环境变量，FATALs和ERROR等，如果未设置env,则将信号处理程序的env设置未default。并返回default_signal。

终止进程，当AFL++主进程需要终止process时，它会向fsrv模块发送终止命令，fsrv会使用kill_signal中存储的信号值来终止相应的process。

执行setup_signal_handlers()函数，也就是信号处理函数，保证了AFL++能够对各种信号进行适当的处理。执行check_asan_opts()函数，设置内存检测工具ASAN。设置afl->power_name为FAST（默认）。随后同步模式运行AFL++，将auto_sync设置为1，设置afl->sync_id为default，表示这是一个自动配置的同步示例。afl->is_secondary_node=1表示这是一个次级节点，用于接收来自主节点的同步信息。

判断是否禁用测试用例的“修剪功能”，即afl->disable_trim=1禁用。

测试用例修剪：在AFL++中，测试用例修剪是指通过分析测试用例的执行过程，移除那些对代码覆盖率没有影响的部分，从而所见测试用例的大小，提高模糊测试的效率。当afl->disable_trim=1是，表示禁用修剪功能，AFL++不会对测试用例进行修剪，而是使用完整的测试用例进行模糊测试。

若afl->afl_env.afl_statsd不为空，则调用statsd_setup_format(afl)函数。

afl->afl_env.afl_statsd是AFLpp中用来配置StatsD统计数据发送的变量，用户可以将AFL++的统计数据发送到StatsD服务器，方便监控和分析模糊测试过程，提高模糊测试效率。

而statsd_setup_format()函数根据AFL_STATSD_TAGS_FLAVOR环境变量的标签类型，选择相应的格式，以便AFL++可以将统计数据以正确的格式发送到StatsD服务器。格式有：dogstatsd，librato，influxdb，signalfx等。

afl->use_banner值默认为True，控制着是否在启动时显示欢迎信息。

随后判断是否为AFLFast~RARE模式之间，是的话，对afl->n_fuzz进行开辟空间。

随后，又是一波环境变量初始化操作。接下来是判断是否启用自动恢复功能，自动恢复功能是指当AFL++进程意外终止时，它会尝试恢复之前的运行状态，例如恢复测试用例队列、代码覆盖率信息以及其他相关数据。当afl->afl_env.afl_autoresume为true时，启用自动恢复功能。

然后也是一系列的初始化值，初始化时都默认为0所以都跳过了。

afl->afl_env.afl_max_det_extras用来控制AFL++在执行确定性模糊测试时，最多生成多少个额外的测试用例。AFL++可以执行两种类型的模糊测试：随机模糊测试和确定性模糊测试。确定性模糊测试会系统地尝试所有可能的变异操作，以确保覆盖所有可能的输入数据。额外的测试用例是指在执行确定性模糊测试时，除了初始的测试用例之外，还会生成一些额外的测试用例，用于覆盖一些特殊的输入情况。

如果没设置这个变量的话，那么会默认为256个。

由于进行基本的Fuzzing，那么初始化时afl->afl_env的成员变量全被赋值为0，因此大部分初始化操作都会跳过。执行到生成fuzz data时，需要开辟缓存空间。使用AFL_BUF_PARAM宏定义，用于定义测试用例缓冲区大小。afl_realloc(AFL_BUF_PARAM(in_scratch), min_alloc);这个语句的作用是使用afl_realloc()函数，为in_scratch指向的测试用例缓冲区重新分配内存，分配的内存大小为min_alloc。

后续也是一系列初始化行动。执行至setup_custom_mutators()，该函数负责从用户指定的库文件或命令行参数中加载自定义变异器，并将它们添加到AFL++的变异器列表中。随后的write_setup_file()通过将当前模糊测试的环境变量和命令行参数写入fuzzer_setup文件，记录当前模糊测试的配置信息。fuzzer_cmdline()函数是将当前命令行参数写入文件中。read_testcases()函数用于从输入目录读取所有测试用例，并将它们排队等待测试。pivot_inputs()函数的主要作用是为输入测试用例创建硬链接，并根据需要调整文件名。

随后的if (!afl->fsrv.out_file) 语句内容，是在命令行参数中查找包含”@@”的参数，并根据需要设置输出文件路径。check_binary(afl, argv[optind]);这个函数的主要目的是确保目标二进制文件存在且可执行，并且在某些模式下跳过进一步的检查。 setup_testcase_shmem(afl)函数是为AFL++配置共享内存，以便在模糊测试过程中使用共享内存来存储和传递测试用例数据。

跳过一些初始化空间以及为一些模式做初始化的操作后（本次测试并未启用任何其他模式）

后续检查共享内存的大小，如果小于等于全局变量DEFAULT_SHMEM_SIZE，将其设置为共享内存大小，并将其值存储在环境变量AFL_MAP_SIZE中。load_auto(afl)用于加载字典。deunicode_extras()函数旨在处理额外数据。（此次运行并没有额外数据）

afl->in_bitmap记录已经测试过的输入数据的特征信息，其实际也是一个位图，每个位代表一个特定的输入特征。当AFL++测试一个新的输入数据时，会根据该输入数据计算出一些特征信息，并将对应的位图设置为1，表示该特征已经被测试过。AFL++能够根据afl->in_bitmap来判断新的输入数据是否已经测试过，避免重复测试或类似的输入数据，从而提高测试效率。

而afl->virgin_bits是一个用来记录程序尚未覆盖的执行路径的位图。它是一个字节数组，每个字节代表8个不同的执行路径分支。当AFL++执行一个测试用例时，它会根据程序执行的路径更新afl->virgin_bits，将对应路径的位设置为0，表示该路径已经被覆盖。初始化时，其被设置为255。

perform_dry_run(afl);
/*
函数首先遍历afl数据结构中的所有队列项，对于每一项检查该项是否被有效且未被禁用。如果该项有效，尝试打开与测试用例关联的文件并将其内容读入内存。然后关闭文件，使用`calibrate_case`函数校准测试用例。
通过dry_run，确保所有初始测试用例都已正确处理，并为后续的fuzzing做好准备。
*/
C

随后，为缓存数组afl->q_testcase_cache分配一个大小为afl->q_testcase_max_cache_entries的内存块。

执行cull_queue函数通过标记和优化队列中的测试用例，确保在模糊测试过程中优先处理那些对覆盖率有贡献的测试用例。

cull_queue首先检查afl->score_changed是否为0，如果为0 则直接返回，表明未发生改变。否则，执行cull_queue，首先初始化变量，重置所有队列项的favored标志：

1
2
3

for(i = 0; i < afl->queued_itedms; i++){
afl->queue_buf[i]->favored = 0;
}
C

标记新的favored条目：

/*
遍历afl->fsrv.map_size中的每个字节。如果afl->top_rated[i]存在且temp_v中对应的位被设置，则将afl->top_rated[i]标记为favored，并更新temp_v，移除当前条目对应的所有位。
*/		
for(i = 0; i < afl->fsrv.map_size; ++i){
if (afl->top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {
	u32 j = len;
	while (j--) {
	if (afl->top_rated[i]->trace_mini[j]) {
	temp_v[j] &= ~afl->top_rated[i]->trace_mini[j];
	}
}
if (!afl->top_rated[i]->favored) {
afl->top_rated[i]->favored = 1;
++afl->queued_favored;
if (!afl->top_rated[i]->was_fuzzed) { ++afl->pending_favored; }
}
}
}
C

标记冗余条目：

for (i = 0; i < afl->queued_items; i++) {
if (likely(!afl->queue_buf[i]->disabled)) {
mark_as_redundant(afl, afl->queue_buf[i], !afl->queue_buf[i]->favored);
}
}
// 遍历所有队列项，如果队列项未被禁用，则调用mark_as_redundant()函数，将其标记为冗余或者非冗余，具体取决于其favored标志。
C

随后循环queue_buf，确保存在一个合法(没有被禁用)种子。

函数show_init_stat主要目的是在AFL++ 处理输入目录后，显示一些统计信息和警告，调整一些参数以优化模糊测试执行。接下来是判断是否有上一次种子的选择。此次执行为全新执行，因此无。且后续判断是否为恢复执行，也无。

随后会记录状态，执行函数write_stats_file，更新统计文件。它记录了各种运行时的统计数据，包括执行次数，覆盖率，稳定性等。并在调试模式下记录额外的信息。

执行函数maybe_update_plot_file，更新AFL的plot file，记录各种统计数据。包括相对时间、周期数、当前条目、队列项数、未模糊测试的项数、保存的Crashes、保存的挂起数、最大深度、每秒执行次数等。

随后调用函数save_auto，这个函数保存自动生成的额外输入。本次执行无额外输入，即进入函数则返回。

随后进入Fuzzing的主体循环。while(likely(!afl->stop_soon))，likely是一个宏，用于优化代码的执行效率，它告诉编译器，循环条件很有可能为true。编译器会根据这个提示对代码进行优化。

afl->stop_soon是AFL++中用于控制模糊测试过程是否停止的标志位。允许用户根据需要手动停止模糊测试，或设置时间限制和目标漏洞等条件，从而更有效地进行模糊测试。

循环第一行执行一个cull_queue(afl)。第一次循环，afl->score_changed依然为1，因此不执行cull_queue主体。直接返回。

接下来是if (unlikely((!afl->old_seed_selection && runs_in_current_cycle > afl->queued_items) || (afl->old_seed_selection && !afl->queue_cur)))一个判断，

条件!afl->old_seed_selection && runs_in_current_cycle > afl->queued_items：如果没有使用旧的种子选择策略，并且当前循环中的运行周期超过了队列中的种子数量。则进入执行体。

条件afl->old_seed_selection && !afl->queue_cur：如果使用了旧的种子选择策略，并且当前队列指针为空的话，那么进入执行体。

unlikely说明这个条件很少为真。

本次执行，第一个条件为真，进入执行体。

紧接着是第二个if语句。

// 第一个条件afl->last_sync_cycle < afl->queue_cycle:如果上次同步周期小于当前队列周期 !afl->queue_cycle && afl->afl_env.afl_import_first:如果当前队列周期为0，并且环境变量afl_import_first被设置。两个条件都被满足即进入执行体。
// 第二个条件 afl->sync_id:同步id是否存在。
if (unlikely((afl->last_sync_cycle < afl->queue_cycle ||
                (!afl->queue_cycle && afl->afl_env.afl_import_first)) &&
               afl->sync_id)) {
    sync_fuzzers(afl);
}
// 这个同步id应该是多个afl++进程被执行时需要同步。
// 本次执行只有一个afl++主体， 因此不用执行。
// sync_fuzzers(afl)是用来同步fuzzers的函数
C

进入后续if执行体，紧接着是几个赋值语句：

// 更新队列周期和重置变量
++afl->queue_cycle;
runs_in_current_cycle = (u32)-1;
afl->cur_skipped_items = 0;
C

随后是一个if语句处理旧的种子选择策略。

      if (unlikely(afl->old_seed_selection)) {
        afl->current_entry = 0;
        while (unlikely(afl->current_entry < afl->queued_items &&
                        afl->queue_buf[afl->current_entry]->disabled)) {
          ++afl->current_entry;
        }
        if (afl->current_entry >= afl->queued_items) { afl->current_entry = 0; }
        afl->queue_cur = afl->queue_buf[afl->current_entry];
        if (unlikely(seek_to)) {
          if (unlikely(seek_to >= afl->queued_items)) {
            // This should never happen.
            FATAL("BUG: seek_to location out of bounds!\n");
          }
          afl->current_entry = seek_to;
          afl->queue_cur = afl->queue_buf[seek_to];
          seek_to = 0;
        }
      }
//主要是更新`current_entry`和`queue_cur`
C

接下来是一个if语句

if (unlikely(afl->not_on_tty)) {

  ACTF("Entering queue cycle %llu.", afl->queue_cycle);
  fflush(stdout);

}
C

这个语句会先判断afl->not_on_tty，也就是当其值为true时，表示AFL++不是在tty终端上运行。在环境变量AFL_NO_UI的值，如果为真，则设置not_on_tty为true.

本次由于在调试环境，因此也没有开启UI，所以此值为1，进入执行体，将输出当前周期。接下来是一个大的if语句。外层循环如下：

// 如果整个队列循环结束后都没有发现新的测试用例，那么接下来尝试使用重组策略。
if (unlikely(afl->queued_items == prev_queued
             /* FIXME TODO BUG: && (get_cur_time() - afl->start_time) >= 3600 */
             ))
// 这个判断条件即是，如果当前队列项（种子池中的种子数量）== 先前队列项。那么进入执行体。
C

由于这是第一次执行，因此pre_queued的值为0，而初始种子数量为2，当前afl->queued_items为2。因此会跳过这个if。来到else部分：

else {

        afl->cycles_wo_finds = 0;
}
// 即一个完整的队列周期内发现了新的测试用例，则将`cycles_wo_finds`计数器置0
C

接下来是判断cycle_schedules, /* cycle power schedules? */，其值为0；那么跳过这个执行体。跳过能量调度策略的选择。

这个大if的执行体最后一个语句：

1 2	`// 将当前种子池的种子数量赋给prev_queued，用来判断下次循环时，是否生成新的测试用例。 prev_queued = afl->queued_items;` C

跳出if后，执行++runs_in_current_cycle;这个runs_in_current_cycle的值初始化为(u32)-1，那么经过加1后，变成了0。

接下来是一个do-while循环体。第一段代码为一个if判断：

// 检查是否使用旧的种子选择策略。      
if (likely(!afl->old_seed_selection)) {
    // 如果有新的测试实例，或者需要重新初始化alias 表。
    if (unlikely(prev_queued_items < afl->queued_items || afl->reinit_table)) {
        // we have new queue entries since the last run, recreate alias table
        prev_queued_items = afl->queued_items; // 更新prev_queued_items
        create_alias_table(afl); // 新建alias_table
    }
    // 选择下一个队列条目
    afl->current_entry = select_next_queue_entry(afl);
    // 更新当前队列条目指针
    afl->queue_cur = afl->queue_buf[afl->current_entry];
}
C

select_next_queue_entry是一个内联函数，用于从队列中选择下一个条目。它使用了一种称为别名方法(alias method)的算法来实现快速选择。

/* select next queue entry based on alias algo - fast! */
inline u32 select_next_queue_entry(afl_state_t *afl) {
// 生成一个在[0,afl->queue_items-1]范围内的随机数s，表示初步选择的队列条目索引。
u32    s = rand_below(afl, afl->queued_items);
// 生成一个在[0.0, 1.0]范围内的随机浮点数p，表示一个随机概率。
double p = rand_next_percent(afl);
/*
fprintf(stderr, "select: p=%f s=%u ... p < prob[s]=%f ? s=%u : alias[%u]=%u"
" ==> %u\n", p, s, afl->alias_probability[s], s, s, afl->alias_table[s], p <
afl->alias_probability[s] ? s : afl->alias_table[s]);
*/
// afl->alias_probability[s]这是一个概率数组，存储了每个条目的选择概率。
// afl->alias_table[s]这是一个别名数组，存储了每个条目的别名索引
// 如果随机概率p小于s条目的选择概率，则返回s；否则返回s条目的别名索引
return (p < afl->alias_probability[s] ? s : afl->alias_table[s]);

}
C

随后进入fuzzing函数fuzz_one_original(afl)，这个函数是afl-fuzz-one.c中的函数。这个函数很长…

执行完一些变量的初始化后，来到该函数的第一个if判断：

// afl->custom_mutators_count 是一个整数变量，用于记录用户自定义变异器的数量。
if(unlikely(afl->custom_mutators_count)){
/* The custom mutator will decide to skip this test case or not. */
LIST_FOREACH(&afl->custom_mutator_list, struct custom_mutator, {
    if (el->afl_custom_queue_get &&
        !el->afl_custom_queue_get(el->data, afl->queue_cur->fname)) {

      return 1;

    }

  });
}
// 本次执行没有custom_mutators，因此会跳过这个执行体。
C

接下来就是第二个if判断pending_favored, /* Pending favored paths 。

// afl->pending_favored用于统计当前待处理的优先测试用例数量，也就是favored的还未测试的测试用例数量，这里为2。
if (likely(afl->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. */
	// afl->queue_cur->fuzz_level:当前条目的模糊迭代次数。如果这个值为非零，表示该条目已经被模糊测试过。
    // afl->queue_cur->favored:当前队列条目是否为优先。如果这个值为真，表示该条目是优先条目。
    // 生成一个0-99的整数，并检查它是否小于SKIP_TO_NEW_PROB(这个宏指跳到新条目的概率)
    if ((afl->queue_cur->fuzz_level || !afl->queue_cur->favored) &&
        likely(rand_below(afl, 100) < SKIP_TO_NEW_PROB)) {
        
      return 1;

    }

  }
C

这个if的逻辑是，如果当前条目已经被模糊测试过，或者（当前条目不是优先条目，且生成的随机数小于SKIP_TO_NEW_PROB），则返回1，表示跳过当前条目，可能跳到一个新的优先条目。在本次执行中，afl->queue_cur->fuzz_level为0，且当前队列条目为优先。会跳过这个if。跳过后，没有其他语句，上一层if (likely(afl->pending_favored))便也结束了。

接下来，来到if(unlikely(afl->not_on_tty))判断，也就是继续往终端输出一些信息了。

信息输入完成后，执行语句orig_in = in_buf = queue_testcase_get(afl, afl->queue_cur);

inline u8 *queue_testcase_get(afl_state_t *afl, struct queue_entry *q) {
    // 保存队列条目q的长度
    u32 len = q->len;
    /* first handle if no testcase cache is configured */
    // afl->q_testcase_max_cache_size表示测试用例缓存的最大大小。如果未配置缓存（即为0），则进入这个分支。
    if (unlikely(!afl->q_testcase_max_cache_size)) {
        // buf:用于存储测试用例数据的缓冲区指针
        u8 *buf;
        // 如果当前队列条目是afl->queue_cur，则重新分配afl->testcase_buf
        if (unlikely(q == afl->queue_cur)) {
            // testcase_buf用于存储当前测试用例数据
            buf = afl_realloc((void **)&afl->testcase_buf, len);
        } else { // 否则，重新分配afl->splicecase_buf
            // splicecase_buf用于 存储拼接后的测试用例数据
            buf = afl_realloc((void **)&afl->splicecase_buf, len);
        }
        // 检查内存是否分配成功
        if (unlikely(!buf)) {
            PFATAL("Unable to malloc '%s' with len %u", q->fname, len);
    }
    // 打开文件并读取数据
    int fd = open(q->fname, O_RDONLY);
    if (unlikely(fd < 0)) { PFATAL("Unable to open '%s'", q->fname); }
    // 从文件描述符fd中取len字节的数据到缓冲区buf中
    ck_read(fd, buf, len, q->fname);
    close(fd);
    return buf;
}
C

接下来是记录当前队列的长度len = afl->queue_cur->len；随后给out_buf 分配len长度的空间。

再重置afl->subseq_tmouts=0；subseq_tmouts的值记录着连续超时的次数。如果一个测试用例运行超时，计数器会增加。

afl->cur_depth = afl->queue_cur->depth;afl->cur_depth这个成员变量表示当前测试用例在输入队列中的深度。而afl->queue_cur->depth是当前队列条目的深度，每个队列条目代表一个测试用例，depth表示该测试用例在输入队列中的深度。当前执行的测试用例的深度赋值给afl的全局变量，为后续测试方便使用这个深度信息。

接下来是一个if语句if (unlikely(afl->queue_cur->cal_failed))，对于成员变量afl->queue_cur->cal_failed，其中afl-queue_cur是一个指向当前正在处理的队列条目的指针。每个队列条目代表一个测试用例。cal_failed是一个布尔类型成员变量，用于指示当前测试用例的校准是否失败。

 if (unlikely(afl->queue_cur->cal_failed)) {
   // 初始化一个变量res为FSRV_RUN_TMOUT，表示运行超时
   u8 res = FSRV_RUN_TMOUT;
   // 检查校准失败的次数是否小于预定义的阈值CAL_CHANCES
   if (afl->queue_cur->cal_failed < CAL_CHANCES) {
// 如果失败次数小于阈值，则将当前队列项的执行校验和重置
     afl->queue_cur->exec_cksum = 0;
// 调用calibrate_case函数重新校准，将结果存在res中。
     res =
         calibrate_case(afl, afl->queue_cur, in_buf, afl->queue_cycle - 1, 0);
// 如果再次校准失败，则报错。
     if (unlikely(res == FSRV_RUN_ERROR)) {

       FATAL("Unable to execute target application");

     }

   }
// 检查是否需要停止fuzzing或者校准结果是否与afl->crash_mode一致。
   if (unlikely(afl->stop_soon) || res != afl->crash_mode) {
// 增加跳过测试实例数量
     ++afl->cur_skipped_items;
   // 跳转到abandon_entry标签
     goto abandon_entry;

   }

 }
C

随后是“修剪”操作，接下来的if语句判断是否需要对当前队列进行修剪操作。修剪操作用于减少输入的大小，同时保持其有效性，以提高模糊测试效率。以下对这个if语句进行详细解释：

// afl->non_instrumented_mode 为1表示处于非插桩模式，0表示处于插桩模式
// afl->queue_cur->trim_done 为1表示当前队列项已经完成修剪，0表示未完成
// afl->disable_trim 为1表示禁用修剪操作，0表示启用修剪操作
if (unlikely(!afl->non_instrumented_mode && !afl->queue_cur->trim_done &&
               !afl->disable_trim)) {
	// 当前模式是插桩模式，当前队列项没有完成修剪，修剪操作是启用状态，则执行循环体。
    // 保存当前队列项的长度（当前测试实例的长度）
    u32 old_len = afl->queue_cur->len;
	// 调用trim_case函数执行修剪操作，下面有对trim_case的详细说明
    u8 res = trim_case(afl, afl->queue_cur, in_buf);
    orig_in = in_buf = queue_testcase_get(afl, afl->queue_cur);

    if (unlikely(res == FSRV_RUN_ERROR)) {

      FATAL("Unable to execute target application");

    }

    if (unlikely(afl->stop_soon)) {

      ++afl->cur_skipped_items;
      goto abandon_entry;

    }

    /* Don't retry trimming, even if it failed. */

    afl->queue_cur->trim_done = 1;

    len = afl->queue_cur->len;

    /* maybe current entry is not ready for splicing anymore */
    // 如果当前测试实例的长度小于或等于4并且修剪前的长度大于4，那么，当前条目不进行拼接变异。
    if (unlikely(len <= 4 && old_len > 4)) --afl->ready_for_splicing_count;

  }
C

如何进行“修剪”操作？trim_case函数做了什么？

trim_case函数很长，大概步骤如下：
保存原始长度

自定义变异器修剪

如果，afl->custom_mutators_count>=1则尝试使用用户自定义的变异器进行修剪。如果修剪成功，返回修剪结果。

trimmed_case用于存储修剪结果，custom_trimmed用于标记是否进行了自定义变异器修剪。随后遍历自定义变异器列表，检查并调用自定义修剪函数trim_case_custom。

这里就是对于每个自定义变异器，检查其是否实现了afl_custom_trim函数，如果实现了，调用trim_case_custom函数进行修剪，并将结果存储在trimmed_case中，同时将custom_trimmed标记为true。然后，如果自定义变异器的修剪成功，恢复原始测试用例，返回修剪结果。

处理初始种子长度小于5的情况

对满足条件的种子，为map分配空间，并初始化。为mutated_pos分配空间，并初始化。

对测试实例进行修剪

循环执行，直到remove_len >= MAX(len_p2 / TRIM_END_STEPS, (u32)TRIM_MIN_BYTES)；其中，remove_len表示要移除的字节数，len_p2是大于等于q->len的最小2的幂次方。TRIM_END_STEPS是一个常量，表示修剪开始时的步长。TRIM_MIN_BYTES表示修建时的最小字节数。

随后初始化remove_pos为remove_len，表示从这个位置开始尝试删除数据。下一步进入内层循环while(remove_pos < q->len)，进入内层循环遍历输入数据，尝试从remove_pos开始删除remove_len字节的数据。写入带有间隙的数据：write_with_gap(afl, in_buf, q->len, remove_pos, trim_avail);将输入数据写入目标程序，带有间隙（即删除部分的数据不写入目标程序）。再调用fuzz_run_target函数运行目标程序。随后检查运行结果，如果发生错误或需要停止，则跳转到abort_trimming标签进行放弃修剪。若正常运行，则计算执行路径的哈希值cksum=hash64(afl->fsrv.trace_bits, afl->fsrv.map_size, HASH_CONST);。然后使用该hash值与测试实例的hash值进行比对，如果相同，代表删除数据后的执行路径与原始路径相同，则认为删除是有效的，更新输入数据和相关信息。

随后，减少删除长度remove_len >>= 1;，每次循环结束后，进入新循环前，将remove_len减半，以便在下次循环中尝试删除更小的数据块。
修剪结束后，检查是否需要写回操作

也就是if语句的判断条件needs_write；如果needs_write为真，表示in_buf已经被修改，需要更新磁盘上的测试用例文件。也就是上述修剪成功后更新输入数据的操作改变in_buf。相应地，需要修改磁盘上的文件。但是这其中调用update_bitmap_score函数进行更新位图和得分。是为啥？

关于update_bitmap_score()函数逻辑作如下说明：
首先定义三个变量

i:用于循环遍历AFL的位图；fav_factor:当前路径的评分因子；fuzz_p2:当前路径的模糊测试优先级。
计算fuzz_p2
1
2
3
4
5
6
if (unlikely(afl->schedule >= FAST && afl->schedule < RARE))
  fuzz_p2 = 0;  // Skip the fuzz_p2 comparison
else if (unlikely(afl->schedule == RARE))
  fuzz_p2 = next_pow2(afl->n_fuzz[q->n_fuzz_entry]);
else
  fuzz_p2 = q->fuzz_level;
C
根据AFL的调度策略，计算fuzz_p2。如果调度策略在FAST和RARE之间，跳过fuzz_p2比较。设置为0.如果调度策略是RARE，使用next_pow2函数计算fuzz_p2。其他所有情况下的fuzz_p2设置为q->fuzz_level；
计算fuzz_factor
1
2
3
4
5
if (unlikely(afl->schedule >= RARE) || unlikely(afl->fixed_seed)) {
  fav_factor = q->len << 2;
} else {
  fav_factor = q->exec_us * q->len;
}
C
根据调度策略和是否使用固定种子（afl->fixed_seed），计算fav_factor。如果调度策略是RARE或使用固定种子，fav_factor为q->len << 2。其他所有情况下的fav_factor设置为q->exec_us * q->len。
for循环遍历afl->fsrv.trace_bits数组

遍历trace_bits数组，当满足trace_bits[i]>=1时，也就是这条分支被覆盖了。当满足afl->top_rated[i]>=1时，执行接下来的执行体：根据afl->schedule和afl->fixed_seed的值计算top_rated_fav_factor和top_rated_fuzz_p2。

对trace_bits数组和top_rated数组作如下解释：

trace_bits数组的每一位对应一个分支的映射关系。其通过插桩代码来实现，具体来说，AFL的编译工具在编译被测试程序时，会在每个分支处插入代码，每个分支都有一个唯一ID，这个ID会被用来计算trace_bits数组的索引。当程序执行到某个分支时，插桩代码会更具该分支的ID计算出trace_bits数组的索引，并设置相应的位。

top_rated数组存储每个分支（路径）上最有价值的测试用例。具体来说，它记录了在模糊测试过程中，每个分支覆盖率最高或发现路径最多的测试用例。top_rated是一个指向queue_entry结构体的指针数组。每个数组元素对应一个分支，存储的是在该分支上最有价值的测试用例。当一个新的测试用例发现新的路径或覆盖更多的分支时，如果新的测试用例比当前存储的测试用例更有价值，AFL会将新的测试用例存储到top_rated数组中。

计算结束后，比较fuzz_p2和top_fuzz_p2的值，如果相等的话，根据afl->schedule和afl->fixed_seed的值，进一步比较fav_factor和afl->top_rated[i]的属性值。

更新top_rated[i]的trace_mini变量，将当前测试用例q插入最后插入新的top_rated，增加其引用计数。如果q->trace_mini为空或0，则分配内存并最小化trace_bits数组，最后，设置afl->score_changed为1.

循环结束
trim函数结束后，是queue_testcase_get()函数，这个函数的主要功能是从文件中读取测试用例，并根据是否配置了缓存来决定是直接读取还是从缓存中读取。如果缓存已经满，则会驱逐一个旧的缓存条目以腾出空间。

随后来到afl->queue_cur->trim_done=1;表明当前队列条目已经完成修剪，无论其是否修剪成功，不再执行修剪。至此，修剪的第一个if语句结束。

memcpy(out_buf, in_buf, len);将in_buf中长度为len的内容复制到out_buf中。

u64 fuzz_time = ((afl->prev_run_time + get_cur_time() - afl->start_time) / 1000);计算fuzz_time。

随后，执行以下语句：

// 如果队列中的种子数量大于中心种子数量，并且队列中的种子数量大于等于两倍的中心相关种子数量
if(afl->queued_items > afl->centers_num && (afl->queued_items >= 2 * afl->last_centers_realted_seeds)){
    // 执行kmeans_main函数，进行聚类分析
    kmeans_main(afl);
	// 更新中心相关种子为当前队列中的种子数量
    afl->last_centers_realted_seeds = afl->queued_items;
    // 更新中心相关种子生成时间为当前模糊测试时间
    afl->centers_gen_time = fuzz_time;
	// 遍历队列中的每个种子
    for (u32 c = 0; c < afl->queued_items; c++) {
        // queue_buf存储模糊测试队列中的所有条目，它是一个动态增长的数组，可以根据需要增加大小。
      struct queue_entry * cur_node = afl->queue_buf[c];
        // 如果当前种子的初始种子存在并且当前种子经过变异。
      if(cur_node->initial_seed && cur_node->mutated_pos_num != -1){
          // 那么变异当前种子的每一个字节
        for(u32 i = 0;i < cur_node->len;i++){
            // 判断当前种子第i个字节是否发生变异
          if(cur_node->mutated_pos[i].flag >= 1){
              // 如果发生变异，则释放该字节的A和b矩阵（这是CMAB中的内容）
            M_free(cur_node->mutated_pos[i].A);
            M_free(cur_node->mutated_pos[i].b);
			  // 重新分配A,b的资源
              // A即是一个初始化为1，长宽都为centers_num的矩阵
              // b即是一个初始化为0，长宽都为centers_num的矩阵
            cur_node->mutated_pos[i].A = M_I(afl->centers_num);
            cur_node->mutated_pos[i].b = M_Zeros(afl->centers_num,1);
          }
        }
      }
    }
  }
C

上述是Shapfuzz中添加的代码，本次执行由于是第一次，输入只有两个种子。因此会跳过。来到下述代码：

// 如果中心种子的生成时间（在执行聚类函数后生成）大于当前队列中向量更新时间  
if(afl->centers_gen_time > afl->queue_cur->vec_update_time){
    // 初始化cur数组
    u32 map_size = afl->fsrv.map_size;
    float* cur = (float *)malloc(sizeof(float) * map_size);
    memset(cur, 0 ,sizeof(float) * map_size);
	// 执行模糊测试
    common_fuzz_stuff(afl, out_buf, len);
    u32 j = 0;
    u8 *src = afl->fsrv.trace_bits;
    // 填充cur数组
    // 遍历位图数组，将非0值转换为浮点数并存储于cur数组中。
    while (j < map_size) {
      u8 v = *src;
      if(v){
        cur[j] = (float)v;
      }
      src++;
      ++j;
    }
	// 计算距离并更新特征向量
    for(u32 i = 0;i < afl->centers_num;i++){
        // 遍历中心节点（种子）数组，计算cur数组与每个中心的距离，并将结果存储在当前队列条目的特征向量中。
      double distance = (double)cal_distance(cur, afl->centers[i], map_size);
      afl->queue_cur->feature_vec->data[i] = distance;
    }
	// 更新向量更新时间
    afl->queue_cur->vec_update_time = afl->centers_gen_time;
    
  }
C

由于本次为Fuzzing的第一轮，因此afl->centers_gen_time为0，且afl->queue_cur->vec_update_time也为0。因此上述执行体会被跳过，来到以下执行：

// 如果当前队列长度大于afl已知的最大长度  
if(afl->queue_cur->len > afl->max_len){
    // 如果历史变异序列不为空
    if(afl->history_mutation_sequence){
        // 则释放以下两个数组的空间
      free(afl->history_mutation_sequence);
      free(afl->new_mutation_sequence);
    }
	// 重新分配历史和新变异序列的内存
    afl->history_mutation_sequence = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));
    afl->new_mutation_sequence = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));
	// 如果afl->max_len不为0
    if(afl->max_len != 0){
      // 释放以下数组内存
      free(afl->dataset_reward);
      free(afl->hit_nums);
      free(afl->tmp_mutated_pos);
      free(afl->tmp_mutated_pos_flag);
    }
    // 为以下数组开辟新的空间
    afl->dataset_reward = (double *)calloc(afl->queue_cur->len, sizeof(double));
    afl->hit_nums = (double *)calloc(afl->queue_cur->len, sizeof(double));
    afl->tmp_mutated_pos = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));
    afl->tmp_mutated_pos_flag = (u8 *)calloc(afl->queue_cur->len, sizeof(u8));

    afl->max_len = afl->queue_cur->len;
}else{
    // 将dataset_reward等数组重置
    memset(afl->dataset_reward, 0, afl->max_len * sizeof(double));
    memset(afl->hit_nums, 0, afl->max_len * sizeof(double));
    memset(afl->tmp_mutated_pos_flag, 0, afl->max_len * sizeof(u8));
  }
// 初始化一些成员变量
  afl->history_mutation_sequence_idx = 0;
  afl->new_mutation_sequence_idx = 0;
  afl->tmp_mutated_pos_idx = 0;
  afl->from_splicing = 0;
C

Shapfuzz部分代码结束，接下来对当前队列进行性能评分。

// 判断是否使用旧的种子选择策略
if (likely(!afl->old_seed_selection))
    // 直接给两个变量赋值，当前队列的性能分数
    orig_perf = perf_score = afl->queue_cur->perf_score;  
else
    // 否则，则调用caculate_score函数重新计算当前队列条目的性能评分，并将其赋值给afl->queue_cur->perf_score
    afl->queue_cur->perf_score = orig_perf = perf_score =
        calculate_score(afl, afl->queue_cur);
C

接下来是判断当前队列是否放弃，即性能分数小于等于零并且队列活跃种子数量大于1，则放弃当前队列。

本次执行不会放弃，来到后续的cmplog功能判断，由于未开启cmplog因此，不会执行。

// 如果当前队列条目已经通过了确定性测试 或者 跳过确定性测试的全局变量被设置 或者 当前队列条目的性能分数小于某个阈值，这个阈值是MIN(当前队列深度的30倍，Havoc阶段的最大倍数)
if (likely(afl->queue_cur->passed_det) || likely(afl->skip_deterministic) ||
    likely(perf_score <
           (afl->queue_cur->depth * 30 <= afl->havoc_max_mult * 100
                ? afl->queue_cur->depth * 30
                : afl->havoc_max_mult * 100))) {
// 满足条件则跳转到`custom_mutator_stage`标签，从而跳过确定性测试阶段。
  goto custom_mutator_stage;

}
C

程序执行来到custom_mutator_stage标签处，第一句为if (likely(!afl->custom_mutators_count)) { goto havoc_stage; }，因此再次跳转到havoc_stage阶段。

havoc变异阶段主要用于对输入数据进行大量随机变异，以发现潜在的漏洞。

afl->stage_cur_byte = -1;初始化当前字节位置为-1，表示还没有开始变异。随后判断是否在拼接文件周期内，需要生成相应的描述，本次不在splice 变异中，因此执行一些指纹操作。其中有 afl->stage_max = (doing_det ? HAVOC_CYCLES_INIT : HAVOC_CYCLES) * perf_score / afl->havoc_div / 100;根据是否在进行确定性测试，设置stage_max，即最大变异次数。

接下来就是对最大变异次数做一个判断：if (afl->stage_max < HAVOC_MIN) { afl->stage_max = HAVOC_MIN; }本次执行，stage_max值为0x100。而Havoc_MIN=12U，因此不会执行赋值操作。然后，接下去是初始化一些变量：

temp_len = len; // 记录长度

orig_hit_cnt = afl->queued_items + afl->saved_crashes; // 记录种子池种子+Crash数量

havoc_queued = afl->queued_items; // 种子池中种子数量
C

接下来是一个if语句，用于处理自定义变异器的变异频率，本次执行不会执行。跳过后，计算r_max，一个随机选择的最大范围，根据不同的条件动态调整这个范围值。接下来又是Shapfuzz中的内容。初始化一些变量后，第一个判断if(afl->history_mode && afl->queue_cur->ancestor_seed && afl->from_splicing == 0 && afl->queue_cur->vec_update_time)其中，afl->queue_cur->vec_update_time为0，因此跳过。

第二个判断if(afl->new_mode && afl->queue_cur->related_num && afl->from_splicing == 0)，前两个条件都为0，因此跳过。

接下来执行一个循环：

for (afl->stage_cur = 0; afl->stage_cur < afl->stage_max; ++afl->stage_cur) {
  {
    history_mode = 0;
    new_mode = 0;
    random_mode = 0;
    double decrease = 0;
      // 计算decrease
    if(per_exec_global > 0 && afl->stats_avg_exec > 0 && per_exec_global >  2 * afl->stats_avg_exec){
      
      decrease = 1.0 * (per_exec_global - afl->stats_avg_exec) / per_exec_global;
      if(decrease > 0.3) decrease = 0.3; // 限定decrease的值最大为0.3
    }
      // 根据`history_able`和`new_able`的值，代码被分为四种情况
      // 情况一：history_able == 0 && new_able == 0
    if(history_able == 0 && new_able == 0){
        // 计算average和weight_random
      double average = 1.0 * afl->found_all / afl->exec_all;
      weight_random = 1.0 * afl->queue_cur->found_by_random / afl->queue_cur->exec_random;
      if(afl->queue_cur->initial_seed == 0 && weight_random < average * (0.7 + decrease)){
        break;
      } 
      random_mode = 1;
    }
      // 情况二：history_able == 0 && new_able == 1
    else if(history_able == 0 && new_able == 1){
      weight_new = 1.0 * afl->queue_cur->found_by_new / afl->queue_cur->exec_new;
      weight_random = 1.0 * afl->queue_cur->found_by_random / afl->queue_cur->exec_random;

      double average = 1.0 * afl->found_all / afl->exec_all;
      if(weight_new < average * (0.7 + decrease) && weight_random < average * (0.7 + decrease)){
        break;
      } 

      new_line = weight_new;
      random_line = new_line + weight_random;

      double tmp = ((double)rand()/RAND_MAX) * random_line;
      if(tmp < weight_new) new_mode = 1;
      else random_mode = 1;
      // 情况三：history_able == 1 && new_able == 0
    }else if(history_able == 1 && new_able == 0){
      weight_history = 1.0 * afl->queue_cur->found_by_history / afl->queue_cur->exec_history;
      weight_random = 1.0 * afl->queue_cur->found_by_random / afl->queue_cur->exec_random;

      double average = 1.0 * afl->found_all / afl->exec_all;
      if(weight_history < average * (0.7 + decrease) && weight_random < average * (0.7 + decrease)){
        break;
      } 

      history_line = weight_history;
      random_line = history_line + weight_random;

      double tmp = ((double)rand()/RAND_MAX) * random_line;
      if(tmp < weight_history) history_mode = 1;
      else random_mode = 1;
      // 情况四：history_able == 1 && new_able == 1
    }else if(history_able && new_able){
      weight_history = 1.0 * afl->queue_cur->found_by_history / afl->queue_cur->exec_history;
      weight_new = 1.0 * afl->queue_cur->found_by_new / afl->queue_cur->exec_new;
      weight_random = 1.0 * afl->queue_cur->found_by_random / afl->queue_cur->exec_random;

      double average = 1.0 * afl->found_all / afl->exec_all;
      if(weight_history < average * (0.7 + decrease) && weight_new < average * (0.7 + decrease) && weight_random < average * (0.7 + decrease)){
        break;
      } 

      history_line = weight_history;
      new_line = weight_history + weight_new;
      random_line = new_line + weight_random;

      double tmp = ((double)rand()/RAND_MAX) * random_line;
      if(tmp < weight_history) history_mode = 1;
      else if(tmp < weight_new) new_mode = 1;
      else random_mode = 1;
    }
  }
C

这段for循环，有那么点抽象，从逻辑上来看，每次都貌似只会执行一次；本次执行只执行了一次，就break了。这段循环执行后，来到各种模式的判断。结果是history_mode,new_mode,random_mode全为0.则全跳过。

随后，设置afl->use_splice_mutator = 0;即不使用拼接变异。生成一个随机的2的幂次方值，将其存储于afl->stage_cur_val中。再afl->splice_num=0;不使用拼接变异。随后通过之前for循环后对模式的判定，将afl->record_flag置0或1。本次执行置为0.随后一个很长的for循环进行随机选择变异器进行变异，变异次数由using_stacking控制，也就是之前的1<<(1+rand_below(afl, afl->havoc_stack_pow2));生成的一个区间在[2,2*afl->havoc_stack_pow2]中的随机数。本次执行，这个随机数为8，接下来会对一个种子进行8次变异。

跳过第一个if语句，对自定义变异器的使用。接下来初始化一个r：

   // 如果使用改变长度的变异器，则r是一个[0,r_max-1]的值，否则是一个[0,46]的值
if(afl->time_to_use_length_mutator == 0){
     r = rand_below(afl, 47);
   }else{
     r = rand_below(afl, r_max);
   }
C

最后执行下来，r的值为0x11。接下来是一个switch语句，对r做出区间划分。

case 0 ... 3: {

  /* Flip a single bit somewhere. Spooky! */

  #ifdef INTROSPECTION
  snprintf(afl->m_tmp, sizeof(afl->m_tmp), " FLIP_BIT1");
  strcat(afl->mutation, afl->m_tmp);
  #endif
	// 如果启用了using_feature_mode和history_mode则执行以下代码
  if(using_feature_mode && history_mode){
      // 根据概率分布，选择种子的一个字节位置
    pos_tmp = select_position_based_on_distribution(afl);
      // 计算要翻转的bit位置
    tmp = (pos_tmp << 3) + rand_below(afl, 8);
      // 将选中的位置进行相应更新
    update(afl, pos_tmp);
  } // 如果启用了using_feature_mode和new_mode
  else if(using_feature_mode && new_mode){
    pos_tmp = afl->cur_mutation_sequence[rand_below(afl, afl->cur_mutation_sequence_idx)];
      // 计算要翻转的bit位置
    tmp = (pos_tmp << 3) + rand_below(afl, 8);
  } else {
    tmp = rand_below(afl, temp_len << 3);
  }
    // 翻转比特位
  FLIP_BIT(out_buf, tmp);
    // 缓冲区已经更改 标志位
  buf_changed = 1;
  break;

}
C

剩余的情况分别为：

r 在 4 … 7区间内

将pos_tmp位置的字节进行修改。
r 在 8 … 9区间内

将(outbuf+pos_tmp)位置的字节进行修改。

*(u16 *)(out_buf + pos_tmp) = interesting_16[rand_below(afl, sizeof(interesting_16) >> 1)];
r 在 10 … 11区间内

将(outbuf+pos_tmp)位置的字节进行修改。

*(u16 *)(out_buf + pos_tmp) = SWAP16(interesting_16[rand_below(afl, sizeof(interesting_16) >> 1)]);
r 还有很多区间，不同的是Shapfuzz将改变长度的变异器都放在r值在47以后的区间了。

对一个种子变异结束后，执行common_fuzz_stuff(afl, out_buf, temp_len);

common_fuzz_stuff()会写入一个变异后的测试用例，运行目标程序，并处理结果。

write_to_testcase()函数，写入测试用例，因为启用shm模式，所以会将变异后的测试用例写入共享内存中。

fuzz_run_target()函数，调用afl_fsrv_run_target()函数进行执行，并接受返回结果。

afl_fsrv_run_target()函数，执行目标程序，监控是否超时。返回反馈信息。并且在执行时，会自动更新位图。

save_if_interesting()函数，如果测试实例是”interesting”的，那么就保存到种子池。

接下来对save_if_interesting()函数进行详细解释。

// 如果有发现新的边，并且当前测试实例有原始种子，并且from_splicing==0，并且启用的变异器中有拼接变异器，并且没有启动mini_mode
if(afl->new_edges_found_idx && afl->queue_cur->ancestor_seed && afl->from_splicing == 0 && afl->use_splice_mutator == 1 && afl->mini_mode == 0){
      // 保存长度和当前测试实例于init_len和init
      u32 init_len = len;
      u8* init = ck_alloc(len);
      memcpy(init, (u8*)mem, len);
	  // 给afl->out_test分配内存，指针*u8_mem也指向这块内存，并将当前测试实例copy给u8_mem
      u8 *u8_mem = afl_realloc(AFL_BUF_PARAM(out_test), init_len);
      if (unlikely(!u8_mem)) { PFATAL("alloc"); }
      u32 len_test = init_len;
      memcpy(u8_mem, (u8*)mem, init_len);
	  // i == 拼接次数 - 1
      int i = afl->splice_num - 1;
      // 当存在拼接变异，根据拼接栈，进行复原。也就是将更改种子长度的变异操作给撤销。
      while (i >= 0)
      {
          
        u32 type = afl->splice_stack[i][0];
        u32 start = afl->splice_stack[i][1];
        u32 mutation_length = afl->splice_stack[i][2];
        if(type == 1){ 
          u32 del_from = start;
          u32 del_len = mutation_length;
          memmove(u8_mem + del_from, u8_mem + del_from + del_len,
                  len_test - del_from - del_len);

          len_test -= del_len;
        }else{
          u32 clone_to = start;
          u32 clone_len = mutation_length;
          u8* clone_from = (u8*)(&(afl->splice_stack[i][3]));
          u8 *new_buf =
              afl_realloc(AFL_BUF_PARAM(out_scratch), len_test + clone_len);
          if (unlikely(!new_buf)) { PFATAL("alloc"); }
          memcpy(new_buf, u8_mem, clone_to);
          memcpy(new_buf + clone_to, clone_from, clone_len);
          memcpy(new_buf + clone_to + clone_len, u8_mem + clone_to,
                  len_test - clone_to);

          u8_mem = new_buf;
          afl_swap_bufs(AFL_BUF_PARAM(out_test), AFL_BUF_PARAM(out_scratch));
          len_test += clone_len;
        }

        i--;
      }
		// 经过撤销后，现在种子的长度与初始种子的长度一致，处于同一个family中。
      u8 new_fault;
    	// 再将这个撤销操作后的测试实例执行
      len_test = write_to_testcase(afl, u8_mem, len_test, 0);
      new_fault = fuzz_run_target(afl, &afl->fsrv, afl->hang_tmout);
        // 判断是否发现新路径
      classify_counts(&afl->fsrv);

      u8 unchanged = 1;
    	
      for(u32 i = 0;i < afl->new_edges_found_idx;i++){
        u32 cur_edge = afl->new_edges_found[i];
          // 检查所有发现的新边，对于撤销长度变异后的执行结果，只要有没发现上次发现的边，则置0
        if(!(afl->fsrv.trace_bits)[cur_edge]) unchanged = 0;
      }
		// unchanged为1，说明撤销长度变异，不改变覆盖结果
    	// 那么将保存撤销长度变异后的测试实例
      if(unchanged && len_test == afl->queue_cur->len){
        afl->use_splice_mutator = 0;
        
        u8 *new_buf = afl_realloc(AFL_BUF_PARAM(out), len_test);
        if (unlikely(!new_buf)) { PFATAL("alloc"); }
        memcpy(new_buf, u8_mem, len_test);
        len = len_test;
        mem = new_buf;
      }else{
          // 说明撤销长度变异无法到达之前的结果
          // 将撤销长度变异前，也就是当前测试实例保存于mem中
        u8 *new_buf = afl_realloc(AFL_BUF_PARAM(out), init_len);
        if (unlikely(!new_buf)) { PFATAL("alloc"); }
        len = init_len;
        memcpy(new_buf, init, init_len);
        mem = new_buf;
		// 将reset置1
        u8 reset = 1;
        for(u32 i = 0;i < afl->new_edges_found_idx;i++){
          u32 cur_edge = afl->new_edges_found[i];
            // 遍历所有新发现的边，如果这条自新边重置次数大于8次，那么不再重置
          if(afl->queue_cur->ancestor_seed->reset_times[cur_edge] > 8) reset = 0;
        }
			// 重置操作
        if(reset){
          u8 new_fault;
            // 将测试实例写入共享内存
          len = write_to_testcase(afl, mem, len, 0);
            // 运行目标程序
          new_fault = fuzz_run_target(afl, &afl->fsrv, afl->hang_tmout);
          classify_counts(&afl->fsrv);
            // 当前队列不为空 并且 当前测试实例存在原始种子 并且 afl->from_splicing为0
          if(afl->queue_cur && !(afl->queue_cur->ancestor_seed == NULL || afl->from_splicing)){
              // 则获取原始种子的virgin_bits，再遍历所有自新边
            u8* virgin_local = (u8 *)afl->queue_cur->ancestor_seed->virgin_bits;
            for(u32 i = 0;i < afl->new_edges_found_idx;i++){
                // 将所有自新边的重置次数+1
              u32 cur_edge = afl->new_edges_found[i];
              afl->queue_cur->ancestor_seed->reset_times[cur_edge]++;
                // 这个数组与位图每一字节进行“或”的操作
              virgin_local[cur_edge] |= (afl->fsrv.trace_bits)[cur_edge];
            }
          }
        }
      }
    }
C

随后在打印一些数据后，执行open函数打开一个文件句柄,执行ck_write(fd, mem, len, queue_fn);将测试实例给保存起来。随后有两个if，分别是new_bits==2的情况，以及AFLFast调度下，更新n_fuzz的queue_entry。随后计算一个afl->queue_top->exec_cksum哈希值。然后调用函数calibrate_case，该函数通过多次运行测试用例，检测其稳定性和变量行为，并更新相关的统计信息和状态。随后是执行queue_testcase_store_mem()函数，将当前队列顶部的测试实例加入到缓存中。

接下来就是对传入的fault进行判断，也就是本函数接收的，上一层经过执行的结果。对结果进行判断。根据fault的结果进入不同的分支：

FAULT_TMOUT
- 设置total_tmouts计数器加一。如果unique_hangs的个数超过能保存的最大数量KEEP_UNIQUE_HANG，就直接返回keeping的值，如果不是dumb mode，就simplify_trace((u64 *) trace_bits)进行规整。如果没有发现新的超时路径，就直接返回keeping，否则，代表发现了新的超时路径，unique_tmouts计数器加一
- 如果hang_tmout大于exec_tmout，则以hang_tmout为timeout，重新执行一次runt_targe
  - 如果结果不是FAULT_TMOUT，就返回keeping，否则就使unique_hangs计数器加一，然后更新last_hang_time的值，并保存到alloc_printf("%s/hangs/id:%06llu,%s", out_dir, unique_hangs, describe_op(0))文件。
  - 如果结果为FAULT_CRASH，就跳转到keep_as_crash
FAULT_CRASH
FAULT_ERROR
其他情况，直接返回keeping，也就是1。

至此，save_if_interesting函数结束，回到common_fuzz_stuff函数处执行。调用show_stats(afl)函数。该函数刷新screen；至此，common_fuzz_stuff执行完成。

执行完成后，执行stat_analysis函数，该函数主要做的工作是，计算reward，也就是收益R。根据发现的自新边，统计必要字节数量，最后计算字节Shapley值。

执行stat_analysis()后，恢复out_buf的初始状态。

  memset(afl, 0, sizeof(afl_state_t));

  afl->shm.map_size = map_size ? map_size : MAP_SIZE;

  afl->w_init = 0.9;
  afl->w_end = 0.3;
  afl->g_max = 5000;
  afl->period_pilot_tmp = 5000.0;
  afl->schedule = FAST;                 /* Power schedule (default: FAST)   */
  afl->havoc_max_mult = HAVOC_MAX_MULT;

  afl->clear_screen = 1;                /* Window resized?                  */
  afl->havoc_div = 1;                   /* Cycle count divisor for havoc    */
  afl->stage_name = "init";             /* Name of the current fuzz stage   */
  afl->splicing_with = -1;              /* Splicing with which test case?   */
  afl->cpu_to_bind = -1;
  afl->havoc_stack_pow2 = HAVOC_STACK_POW2;
  afl->hang_tmout = EXEC_TIMEOUT;
  afl->exit_on_time = 0;
  afl->stats_update_freq = 1;
  afl->stats_avg_exec = 0;
  afl->skip_deterministic = 1;
  afl->cmplog_lvl = 2;
  afl->min_length = 1;
  afl->max_length = MAX_FILE;
#ifndef NO_SPLICING
  afl->use_splicing = 1;
#endif
  afl->q_testcase_max_cache_size = TESTCASE_CACHE_SIZE * 1048576UL;
  afl->q_testcase_max_cache_entries = 64 * 1024;

#ifdef HAVE_AFFINITY
  afl->cpu_aff = -1;                    /* Selected CPU core                */
#endif                                                     /* HAVE_AFFINITY */

  afl->virgin_bits = ck_alloc(map_size);
  afl->virgin_tmout = ck_alloc(map_size);
  afl->virgin_crash = ck_alloc(map_size);
  afl->var_bytes = ck_alloc(map_size);
  afl->top_rated = ck_alloc(map_size * sizeof(void *));
  afl->clean_trace = ck_alloc(map_size);
  afl->clean_trace_custom = ck_alloc(map_size);
  afl->first_trace = ck_alloc(map_size);
  afl->map_tmp_buf = ck_alloc(map_size);

  afl->fsrv.use_stdin = 1;
  afl->fsrv.map_size = map_size;
  // afl_state_t is not available in forkserver.c
  afl->fsrv.afl_ptr = (void *)afl;
  afl->fsrv.add_extra_func = (void (*)(void *, u8 *, u32)) & add_extra;
  afl->fsrv.exec_tmout = EXEC_TIMEOUT;
  afl->fsrv.mem_limit = MEM_LIMIT;
  afl->fsrv.dev_urandom_fd = -1;
  afl->fsrv.dev_null_fd = -1;
  afl->fsrv.child_pid = -1;
  afl->fsrv.out_dir_fd = -1;

  init_mopt_globals(afl);

  list_append(&afl_states, afl);


C

#ifdef __linux__
  fsrv->nyx_handlers = NULL;
  fsrv->out_dir_path = NULL;
  fsrv->nyx_mode = 0;
  fsrv->nyx_parent = false;
  fsrv->nyx_standalone = false;
  fsrv->nyx_runner = NULL;
  fsrv->nyx_id = 0xFFFFFFFF;
  fsrv->nyx_bind_cpu_id = 0xFFFFFFFF;
#endif

  // this structure needs default so we initialize it if this was not done
  // already
  fsrv->out_fd = -1;
  fsrv->out_dir_fd = -1;
  fsrv->dev_null_fd = -1;
  fsrv->dev_urandom_fd = -1;

  /* Settings */
  fsrv->use_stdin = true;
  fsrv->no_unlink = false;
  fsrv->exec_tmout = EXEC_TIMEOUT;
  fsrv->init_tmout = EXEC_TIMEOUT * FORK_WAIT_MULT;
  fsrv->mem_limit = MEM_LIMIT;
  fsrv->out_file = NULL;
  fsrv->kill_signal = SIGKILL;

  /* exec related stuff */
  fsrv->child_pid = -1;
  fsrv->map_size = get_map_size();
  fsrv->real_map_size = fsrv->map_size;
  fsrv->use_fauxsrv = false;
  fsrv->last_run_timed_out = false;
  fsrv->debug = false;
  fsrv->uses_crash_exitcode = false;
  fsrv->uses_asan = false;

  fsrv->init_child_func = fsrv_exec_child;
  list_append(&fsrv_list, fsrv);

C

difference between Shapfuzz and AFLpp

afl_state_init()

来到初始化afl_state_t数据结构，也就是调用函数afl_state_init()，有shapfuzz以下成员变量被额外初始化

 afl->new_edges_found_idx = 0;
 afl->read_flag = 1;
 afl->write_flag = 0;
 afl->mini_mode = 0;
 afl->time_to_use_length_mutator = 0;

 afl->cur_mutation_sequence_idx = 0;
 afl->cmp_states = ck_alloc(65536);
 memset(afl->cmp_states, 0, 65536);

 afl->exec_history_all = 0;
 afl->found_by_history_all = 0;
 afl->exec_new_all = 0;
 afl->found_by_new_all = 0;
 afl->exec_random_all = 0;
 afl->found_by_random_all = 0;
 afl->exec_all = 0;
 afl->found_all = 0;
// 中心节点的数量
 afl->centers_num = 20;
// 存储着各个中心节点
 afl->centers = ck_alloc(afl->centers_num * sizeof(float *));
 memset(afl->centers, 0, afl->centers_num * sizeof(float *));

 afl->exist_centers = 0;
 afl->centers_gen_time = 0;
 afl->last_centers_realted_seeds = 0;
// 特征图
 afl->feature_map = ck_alloc(map_size * sizeof(u32));
// 置0
 memset(afl->feature_map, 0, map_size * sizeof(u32));
 afl->num_edge = 1;
// 收益R
 afl->dataset_reward = NULL;
 afl->hit_nums = NULL;
 afl->tmp_mutated_pos = NULL;
 afl->tmp_mutated_pos_flag = NULL;
 afl->tmp_mutated_pos_idx = 0;
 afl->cur_n_fuzz_idx = 0;
 afl->dataset_size = 0;
 afl->record_flag = 0;
 afl->last_show_time = 0;

 afl->history_mutation_sequence = NULL;
 afl->history_mutation_sequence_idx = 0;
 afl->new_mutation_sequence = NULL;
 afl->new_mutation_sequence_idx = 0;
 afl->max_len = 0;

 afl->before = 0;

 afl->family_record_time = 0;
C

afl_fsrv_init

初始化afl->fsrv的成员变量

read_afl_environment()

将原本aflpp中的AFL_PIZZA_MODE删除。删除部分如下：

else if (!strncmp(env, "AFL_PIZZA_MODE", afl_environment_variable_len)) {
    afl->afl_env.afl_pizza_mode =atoi((u8 *)get_afl_env(afl_environment_variables[i]));
    if (afl->afl_env.afl_pizza_mode == 0) {
        afl->afl_env.afl_pizza_mode = 1;
    } else {
        afl->pizza_is_served = 1;
    }
}
C

循环获取命令行参数

Shapfuzz多了两个个参数，分别为:-w,-k，它们分别做的操作有：

case 'w':
	afl->history_mode = 1;
	break;
case 'k':
	afl->new_mode = 1;
	break;
LIVESCRIPT

各种模式的初始化操作

afl->power_name = power_names[afl->schedule]; 这里被赋值成了fast，是因为初始化afl->schedule被赋值成了3；默认是fast模式。以及，以下两个成员变量被赋值。

1 2	`afl->sync_id = ck_strdup("default"); afl->is_secondary_node = 1;` ABNF

if ((afl->schedule >= FAST && afl->schedule <= RARE) || afl->history_mode) {

  afl->n_fuzz = ck_alloc(N_FUZZ_SIZE * sizeof(u32));

}
C

启用history模式或者符合条件的模式，会给afl->n_fuzz分配空间。

1	`afl->max_det_extras = MAX_DET_EXTRAS; // 这个常量值为256` C

再初始化测试的cache：

if (!afl->afl_env.afl_testcache_size || !afl->afl_env.afl_testcache_entries) {
    afl->afl_env.afl_testcache_entries = 0;
    afl->afl_env.afl_testcache_size = 0;
}
C

初始化forkserver超时时间

1	`afl->fsrv.init_tmout = afl->fsrv.exec_tmout * FORK_WAIT_MULT; // 初始化做过一次，重复执行了。` C

为buf分配空间

afl_realloc(AFL_BUF_PARAM(in_scratch), min_alloc); // in_scratch_buf
afl_realloc(AFL_BUF_PARAM(in), min_alloc);		// in_buf
afl_realloc(AFL_BUF_PARAM(out_scratch), min_alloc);	// out_scratch_buf
afl_realloc(AFL_BUF_PARAM(out), min_alloc);			// out_buf
afl_realloc(AFL_BUF_PARAM(eff), min_alloc);			// eff_buf
afl_realloc(AFL_BUF_PARAM(ex), min_alloc);			// ex_buf
C

1	`afl->fsrv.use_fauxsrv = afl->non_instrumented_mode == 1 \|\| afl->no_forkserver;//给use_fauxsrv赋值为 afl->no_forkserver` C

setup_dirs_fds()

afl->fsrv.out_dir_fd = open(afl->out_dir, O_RDONLY);
afl->fsrv.plot_file = fdopen(fd, "w");
afl->fsrv.dev_null_fd = open("/dev/null", O_RDWR);
afl->fsrv.dev_urandom_fd = open("/dev/urandom", O_RDONLY);
C

read_testcases()

调用add_to_queue(),将当前输入添加到队列中。

  q->fname = fname;
  q->len = len;
  q->depth = afl->cur_depth + 1;
  q->passed_det = passed_det;
  q->trace_mini = NULL;
  q->testcase_buf = NULL;
  q->mother = afl->queue_cur;
afl->max_depth = q->depth;
afl->queue = afl->queue_top = q;
afl->ready_for_splicing_count++; // 0 -> 2
  ++afl->queued_items;			// 0 -> 2
  ++afl->active_items;			// 0 -> 2
  ++afl->pending_not_fuzzed;	// 0 -> 2  因为初始输入中存在两个文件
  afl->cycles_wo_finds = 0;
afl->last_find_time = get_cur_time();
C

最后，结束read_testcases()时。

1 2	`afl->last_find_time = 0; afl->queued_at_start = afl->queued_items;` XL

afl->tmp_dir = afl->out_dir;

确定.cur_input文件路径

1 2	`afl->fsrv.use_stdin = 0; afl->fsrv.out_file = alloc_printf("%s/.cur_input", afl->tmp_dir); // "/home/dog/fuzzing_xpdf/out/default/.cur_input"` C

check_binary()

1	`afl->fsrv.target_path = ck_strdup(fname); // "/home/dog/fuzzing_xpdf/build/bin/pdftotext"` C

setup_testcase_shmem()

afl->shm_fuzz = ck_alloc(sizeof(sharedmem_t));
afl->shm_fuzz->shmemfuzz_mode = 1;
shm->shm_id =
      shmget(IPC_PRIVATE, map_size == MAP_SIZE ? map_size + 8 : map_size,
             IPC_CREAT | IPC_EXCL | DEFAULT_PERMISSION);
shm->map = shmat(shm->shm_id, NULL, 0);
shm->map_size = map_size;
C

主函数中执行了afl->start_time = get_cur_time();afl->argv = use_argv;

afl_shm_init()

1 2	`afl->fsrv.trace_bits = afl_shm_init(&afl->shm, afl->fsrv.map_size, afl->non_instrumented_mode);` C

为位图开辟了一个共享内存空间。

主函数执行以下：

afl->fsrv.map_size = DEFAULT_SHMEM_SIZE;  // dummy temporary value 其实没变

memset(afl->virgin_bits, 255, map_size); // 为virgin_bits置255
memset(afl->virgin_tmout, 255, map_size); //置255
memset(afl->virgin_crash, 255, map_size); //置255
C

perform_dry_run()

遍历所有队列项，将队列项都dry_run完成后，需要重置一些数据结构。

for (idx = 0; idx < afl->queued_items; idx++) {
  q = afl->queue_buf[idx];
  if (q && !q->disabled && q->len > 256){
    u32 map_size = afl->fsrv.map_size;			
    q->virgin_bits = ck_alloc(map_size);		// 将virgin_bits重置，以便下次运行时使用
    memset(q->virgin_bits, 255, map_size);

    q->reset_times = ck_alloc(map_size);		// 将reset_times重置。
    memset(q->reset_times, 0, map_size);		
  }else if(q){
    q->initial_seed = 0;
    q->ancestor_seed = NULL;
    q->splice = 1;
  }

}
C

calibrate_case()

在calibrate_case函数中会有以下赋值

1 2	`q->exec_cksum = cksum; // 校验和赋值 memcpy(afl->first_trace, afl->fsrv.trace_bits, afl->fsrv.map_size); // 位图赋给first_trace` C

afl->total_cal_us += diff_us;			// 校验时间 
afl->total_cal_cycles += afl->stage_max;	// 校验轮次
q->exec_us = diff_us / afl->stage_max;	// 执行时间
q->bitmap_size = count_bytes(afl, afl->fsrv.trace_bits);	// 位图大小
q->handicap = handicap;				// 这个没变
q->cal_failed = 0;					// 失败次数归0

afl->total_bitmap_size += q->bitmap_size;	//总位图大小
++afl->total_bitmap_entries;				// 位图数量+1
C

  if (new_bits == 2 && !q->has_new_cov) {		// new_bits == 2说明发现了新的路径

    q->has_new_cov = 1;						// 发现新边标志位置1
    ++afl->queued_with_cov;					// 新覆盖字节的路径+1

  }
// 要退出calibrate_case()函数了，因此恢复其特征标志。
  afl->stage_name = old_sn; 		// "init"
  afl->stage_cur = old_sc;			// 0
  afl->stage_max = old_sm;			// 0
C

has_new_bits()

差异如下：

if(afl->read_flag && afl->write_flag && afl->mini_mode == 0){ //开头多的
  afl->new_edges_found_idx = 0;			// dryrun里，这个不会执行
}
u32 tmp_edge = 0;


if (unlikely(ret) && likely(virgin_map == afl->virgin_bits))// 结尾多的
  afl->bitmap_changed = 1;						// dryrun里，这个会执行。
C

update_bitmap_score()

遍历位图的每一位，因为位图的每一位都代表着一个边，该位的值不为0，则代表边被覆盖，那么检查其top_rated是否存在。如果存在，那么使用AFLFast的方式更新top_rated[]数组；如果不存在，那么当前测试实例就暂时是其top_rated种子。queue队列的top_rated数组的每一位对应位图每一位。而该数组存储的是覆盖该路径的所有种子中的最好种子。

从perform_dry_run()结束后

if (afl->q_testcase_max_cache_entries) {

  afl->q_testcase_cache =
      ck_alloc(afl->q_testcase_max_cache_entries * sizeof(size_t));
  if (!afl->q_testcase_cache) { PFATAL("malloc failed for cache entries"); }

}
C

cull_queue()

精简队列,获得一个能覆盖现有路径的最小queue_entry

  afl->queued_favored = 0;	
  afl->pending_favored = 0;
// 遍历队列，将当前所有测试实例的favored都变为0
  for (i = 0; i < afl->queued_items; i++) {

    afl->queue_buf[i]->favored = 0;

  }
// 迭代
  for (i = 0; i < afl->fsrv.map_size; ++i) {
	// 判断该位的路径有没有被设置
    if (afl->top_rated[i] && (temp_v[i >> 3] & (1 << (i & 7)))) {
	// 如果top_rated[i]有值，且该路径在temp_v里被置位了，则更新temp_v
      u32 j = len;

      /* Remove all bits belonging to the current entry from temp_v. */

      while (j--) {
		
        if (afl->top_rated[i]->trace_mini[j]) {
			
          temp_v[j] &= ~afl->top_rated[i]->trace_mini[j];

        }

      }
	// 如果该条目之前没有被标记为favored，则标记并增加。
      if (!afl->top_rated[i]->favored) {
		// 设置favored位1，queue_favored计数器+1
        afl->top_rated[i]->favored = 1;
        ++afl->queued_favored;
		// 如果 WAS_FUZZED字段为0，代表其还没有被fuzz过，则将pending_favored计数器加一
        if (!afl->top_rated[i]->was_fuzzed) { ++afl->pending_favored; }

      }

    }

  }
	// 遍历queue队列，标记队列中的冗余条目
  for (i = 0; i < afl->queued_items; i++) {

    if (likely(!afl->queue_buf[i]->disabled)) {
		
      mark_as_redundant(afl, afl->queue_buf[i], !afl->queue_buf[i]->favored);

    }

  }
C

maybe_update_plot_file()

主循环体

 ++afl->queue_cycle;					// cycle+1
runs_in_current_cycle = (u32)-1;		// 重置为(u32) - 1
afl->cur_skipped_items = 0;				// 跳过测试用例数量置 0 

afl->cycles_wo_finds = 0;				// 当前周期发现新路径的数量 置 0

runs_in_current_cycle++;				// ++ 变成0了

C

1
2
3

// 调用完create_alias_table()函数后，会产生一个alias表，表中记录着测试实例的分数，与概率。
afl->current_entry = select_next_queue_entry(afl);	// 根据alia算法，选出下一个种子
afl->queue_cur = afl->queue_buf[afl->current_entry];	// 根据选出的种子，赋给当前queue
C

create_alias_table()

create the alias table that allows weighted random selection - expensive

afl->alias_table =
    (u32 *)afl_realloc((void **)&afl->alias_table, n * sizeof(u32));
afl->alias_probability = (double *)afl_realloc(
    (void **)&afl->alias_probability, n * sizeof(double));
C

fuzz_one_original()

  afl->subseq_tmouts = 0;				// 超时数量

  afl->cur_depth = afl->queue_cur->depth;	// 记录深度

  afl->stage_name = afl->stage_name_buf;	// stage名称
  afl->bytes_trim_in += q->len;				// 记录修剪字节数

afl->queue_cur->trim_done = 1;				// 修剪结束标志
C

在trim结束后，根据条件判断，进入聚类函数。以下是shapfuzz中的内容。

u64 fuzz_time = ((afl->prev_run_time + get_cur_time() - afl->start_time) / 1000);  
if(afl->queued_items > afl->centers_num && (afl->queued_items >= 2 * afl->last_centers_realted_seeds)){
    // 聚类函数
  kmeans_main(afl);

  afl->last_centers_realted_seeds = afl->queued_items;
  afl->centers_gen_time = fuzz_time;

  for (u32 c = 0; c < afl->queued_items; c++) {
    struct queue_entry * cur_node = afl->queue_buf[c];
    if(cur_node->initial_seed && cur_node->mutated_pos_num != -1){
      for(u32 i = 0;i < cur_node->len;i++){
        if(cur_node->mutated_pos[i].flag >= 1){
          M_free(cur_node->mutated_pos[i].A);
          M_free(cur_node->mutated_pos[i].b);

          cur_node->mutated_pos[i].A = M_I(afl->centers_num);
          cur_node->mutated_pos[i].b = M_Zeros(afl->centers_num,1);
        }
      }
    }
  }
}

if(afl->centers_gen_time > afl->queue_cur->vec_update_time){
  u32 map_size = afl->fsrv.map_size;
  float* cur = (float *)malloc(sizeof(float) * map_size);
  memset(cur, 0 ,sizeof(float) * map_size);

  common_fuzz_stuff(afl, out_buf, len);
  u32 j = 0;
  u8 *src = afl->fsrv.trace_bits;
  while (j < map_size) {
    u8 v = *src;
    if(v){
      cur[j] = (float)v;
    }
    src++;
    ++j;
  }

  for(u32 i = 0;i < afl->centers_num;i++){
    double distance = (double)cal_distance(cur, afl->centers[i], map_size);
    afl->queue_cur->feature_vec->data[i] = distance;
  }

  afl->queue_cur->vec_update_time = afl->centers_gen_time;
  
}


if(afl->queue_cur->len > afl->max_len){
  if(afl->history_mutation_sequence){
    free(afl->history_mutation_sequence);
    free(afl->new_mutation_sequence);
  }

  afl->history_mutation_sequence = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));
  afl->new_mutation_sequence = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));

  if(afl->max_len != 0){
    free(afl->dataset_reward);
    free(afl->hit_nums);
    free(afl->tmp_mutated_pos);
    free(afl->tmp_mutated_pos_flag);
  }
  

  afl->dataset_reward = (double *)calloc(afl->queue_cur->len, sizeof(double));
  afl->hit_nums = (double *)calloc(afl->queue_cur->len, sizeof(double));
  afl->tmp_mutated_pos = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));
  afl->tmp_mutated_pos_flag = (u8 *)calloc(afl->queue_cur->len, sizeof(u8));

  afl->max_len = afl->queue_cur->len;
}else{
  memset(afl->dataset_reward, 0, afl->max_len * sizeof(double));
  memset(afl->hit_nums, 0, afl->max_len * sizeof(double));
  memset(afl->tmp_mutated_pos_flag, 0, afl->max_len * sizeof(u8));
}
afl->history_mutation_sequence_idx = 0;
afl->new_mutation_sequence_idx = 0;
afl->tmp_mutated_pos_idx = 0;
afl->from_splicing = 0;
C

1	`orig_perf = perf_score = afl->queue_cur->perf_score;` C

trim_case()

shapfuzz:

if (q->len < 5) { 
    // 如果测试实例长度小于5，且是原始种子
  if(q->initial_seed){

    if(q->initial_seed){
        
      q->map = (u64 *)malloc(sizeof(u64) * q->len);
        // 初始化q->map为i
      for(u32 i = 0;i < q->len;i++) (q->map)[i] = (u64)i;
      q->mutated_pos = (struct arm *)malloc(sizeof(struct arm) * q->len);
        // 遍历当前队列项
      for(u32 i = 0;i < q->len;i++){
          // 初始化每一个字节
        q->mutated_pos[i].SV = 0;
        q->mutated_pos[i].add = 0;

        q->mutated_pos[i].flag = 0;
        q->mutated_pos[i].A = NULL;
        q->mutated_pos[i].b = NULL;
      }
        // 重置变异字节数量
      q->mutated_pos_num = 0;
    }
  }
  
  return 0; }
C

aflpp

1	`if (q->len < 5) { return 0; }` C

以xpdf为目标测试，修剪中目标程序执行了0x7F8次

变量详解

初始化后，正式执行中：

//除却前面给变量分配看空间，并初始化0外，以下为xpdf测试期间，w模式开启下的变量修改位置与意义。
// afl-fuzz-one.c 4137行，函数fuzz_one_original()内
afl->write_flag = 1;
// afl-fuzz-one.c 4141行，函数fuzz_one_original()内
if(cur_time > 1200) afl->time_to_use_length_mutator = 1; // 本次执行，变为1，因为cur_time=1331
else afl->time_to_use_length_mutator = 0;  
// afl->fuzz-one.c 4279行，函数fuzz_one_original()内
afl->use_splice_mutator = 0;
// 当一个种子的变异次数r在splice变异器区间的话，以下变量用于存储变异
// afl->fuzz-one.c 函数fuzz_one_original()内
if(afl->splice_num < 512){
    afl->splice_stack[afl->splice_num][0] = 1;        // splice变异标志位
    afl->splice_stack[afl->splice_num][1] = clone_to; // 变异起始位置
    afl->splice_stack[afl->splice_num][2] = clone_len;// 变异长度
    afl->splice_num++;								  // splice变异次数
}

// afl->fuzz-one.c 418行，函数stat_analysis()内
afl->read_flag = 1;
afl->mini_mode = 1;

// 对每个必要字节:
u32 ii = (afl->queue_cur->map)[i];
// 这里的afl->queue_cur->ancestor_seed代表着一个family，也指向某个初始种子。
if(afl->queue_cur->ancestor_seed->mutated_pos[ii].flag < 1){
    afl->queue_cur->ancestor_seed->mutated_pos[ii].flag += 1;
    if(afl->queue_cur->ancestor_seed->mutated_pos[ii].flag >= 1){
        afl->queue_cur->ancestor_seed->mutated_pos[ii].A = M_I(afl->centers_num);
        afl->queue_cur->ancestor_seed->mutated_pos[ii].b = M_Zeros(afl->centers_num,1);
        afl->queue_cur->ancestor_seed->mutated_pos_num++;
    }
}
afl->queue_cur->ancestor_seed->mutated_pos[ii].add = 1;

// 在控制生成的测试实例数量每次循环后，会将对应变异模式所执行的数量+1
if(random_mode){			// random_mode，后续还有两个模式，就不一一列举。
    afl->queue_cur->found_by_random++;
    afl->found_by_random_all++;
}
C

以上是第一次执行变异的过程所修改的变量，其中有大量路径没有执行，因为初始种子数量不够，无法生成中心种子。因此第一次执行是采取random_mode。接下来是第一次变异执行后的收尾：

afl->write_flag = 0;	// 写标志置0
new_hit_cnt = afl->queued_items + afl->saved_crashes;
if (!splice_cycle) {	// 当前不处于splice_cycle
    // 用数组记录当前是哪个阶段，以及当前阶段所保存下来的测试实例数量，执行的测试实例数量。
    afl->stage_finds[STAGE_HAVOC] += new_hit_cnt - orig_hit_cnt;
  	afl->stage_cycles[STAGE_HAVOC] += afl->stage_max;
}
C

接下来进入retry_splicing阶段

retry_splicing:
// 根据fuzzing的执行时间，与队列周期决定要不要使用splice变异器
  if(((afl->prev_run_time + get_cur_time() - afl->start_time) / 1000) > 1200 && afl->queue_cycle <= 1){
    u32 tmp = rand_below(afl, 4);
    if(tmp == 1){
      afl->use_splicing = 1;
    }else{
      afl->use_splicing = 0;
    }
  }
C

splice阶段，将种子池中的某个种子，进行拼接变异后，存入afl->in中，并跳转到havoc_stage对这个种子进行随机变异。

进入splice_cycle中的havoc阶段，同样的havoc流程。本次执行了两次splicing_havoc。由一个随机值控制splicing_havoc的次数：

  if(((afl->prev_run_time + get_cur_time() - afl->start_time) / 1000) > 1200 && afl->queue_cycle <= 1){
    u32 tmp = rand_below(afl, 4);
    if(tmp == 1){
      afl->use_splicing = 1;
    }else{
      afl->use_splicing = 0;
    }
  }
// 在queue_cycle>1后的周期内，都会置splice为1
  else if(afl->queue_cycle > 1){
    afl->use_splicing = 1;
  }else{
    afl->use_splicing = 0;
  }
// 随后还有一个判断，slice_cycle要小于15，也就是不会连续splice_havoc变异超过15次。
  if (afl->use_splicing && splice_cycle++ < SPLICE_CYCLES &&
      afl->ready_for_splicing_count > 1 && afl->queue_cur->len >= 4)
C

然后进入abandon_entry阶段：

abandon_entry:
  afl->splicing_with = -1;
  if (!afl->stop_soon && !afl->queue_cur->cal_failed &&
      !afl->queue_cur->was_fuzzed && !afl->queue_cur->disabled) {
	
    --afl->pending_not_fuzzed;				// Queued but not done yet 
    afl->queue_cur->was_fuzzed = 1;         // historical, but needed for MOpt
    afl->reinit_table = 1;					// reinit the queue weight table
    if (afl->queue_cur->favored) { --afl->pending_favored; }//Pending favored paths

  }
++afl->queue_cur->fuzz_level;				// Number of fuzzing iterations
C

重新一次循环阶段：

在trimming之后，这一次会执行kmeans_main(afl)。

kmeans_main(afl)

1 2	`// 首先会调用update_feature_map(afl) update_feature_map(afl);` C

void update_feature_map(afl_state_t *afl){
  u32 *ptr = (u32 *)afl->virgin_bits;		// afl->virgin_bits记录着未被fuzzing区域
  u32  i = ((afl->fsrv.real_map_size + 3) >> 2);
  u32  ret = 0;
  u32 id = 0;
  memset(afl->feature_map, 0, afl->fsrv.map_size * sizeof(u32));
  afl->num_edge = 1;
  // 对于afl->virgin_bits中的每4个字节为单位进行判断
  while (i--) {
    u32 v = *(ptr++);
	
    if (likely(v == 0xffffffffU)) {
      id +=4;
      continue; 
    }
    if ((v & 0x000000ffU) != 0x000000ffU) {			// 最低字节不等于ff
      afl->feature_map[id + 0] = afl->num_edge;
      afl->num_edge++;
    }
    if ((v & 0x0000ff00U) != 0x0000ff00U) {			// 次低字节不等于ff
      afl->feature_map[id + 1] = afl->num_edge;
      afl->num_edge++;
    }
    if ((v & 0x00ff0000U) != 0x00ff0000U) {			// 次高字节不等于ff
      afl->feature_map[id + 2] = afl->num_edge;
      afl->num_edge++;
    }
    if ((v & 0xff000000U) != 0xff000000U) {			// 最高字节不等于ff
      afl->feature_map[id + 3] = afl->num_edge;
      afl->num_edge++;
    }

    id +=4;
  }
// 也就是说afl->num_edge记录着未被覆盖区域的每个不等于ff字节(或许是有效字节)的数量
// 并且afl->feature_map存储着，这个字节是第几个不等于ff的字节。
} // 本次执行后，afl->num_edge = 2061
C

对feature_map进行更新后，除却一些初始化的操作以外。进入循环中：

// 这是内层循环，外层循环是循环1次，貌似永远执行一次，还不知循环的目的。内存循环遍历种子池队列queue_items
	for (u32 i = 0; i < observations_size; i++) {
      u32 tid;
      tid = rand_below(afl, afl->queued_items);		// 首先获得一个[0,queue_items-1]区间的随机数
      if (likely(!afl->queue_buf[tid]->disabled)) { // 判断这个种子是否被设置禁用
        u8* out_buf = queue_testcase_get(afl, afl->queue_buf[tid]);  // 获得这个种子的数据存入out_buf
        u32 len = afl->queue_buf[tid]->len;
        common_fuzz_stuff(afl, out_buf, len);				// 以out_buf为输入，执行目标程序

        u32 j = 0;
        u8 *src = afl->fsrv.trace_bits;						// 存着反馈信息，也就是更新后的位图
        while (j < map_size) {
          u8 v = *src;										// 遍历位图
          if(v){											// 对于覆盖的边
            u32 idx = afl->feature_map[j];					// 未被探索的第几条边或者已经被探索则为0
            observations[i][idx] = (float)v;				// idx是未被探索的边的id
          }													// v是已经被探索的边的id
          src++;											// 因此，observations记录着本次发现的新边在原未被探索边中的id，即记录哪些未被覆盖的边，经过这次执行，被覆盖了。
          ++j;
        }
      }
    }
centers = km_new(observations, k, observations_size, vector_size); // 调用km_new（开源库函数），得出中心节点
C

算出中心节点后：

for(int i = 0;i < k;i++){
  if(afl->centers[i]) free(afl->centers[i]);				// 如果这个中心节点为空的话，free掉空间。

  float* tmp = (float *)malloc(sizeof(float) * map_size); 
  memset(tmp, 0, sizeof(float) * map_size);
  for(int j = 0;j < map_size;j++){						// 遍历向量图，也就是位图那么大
    u32 idx = afl->feature_map[j];						// 未探索边的id
    if(centers[i][idx] != 0){								// 
      tmp[j] = centers[i][idx];							// 
    } 
  }
  afl->centers[i] = tmp;									// afl->centers保存的是中心种子的路径
}
C

随后释放observations的空间即退出kmeans_main()函数。

回到修剪后：

if(afl->queued_items > afl->centers_num && (afl->queued_items >= 2 * afl->last_centers_realted_seeds)){
  kmeans_main(afl);											// 从这儿执行结束后，中心种子已经选取结束。

  afl->last_centers_realted_seeds = afl->queued_items;		// 这个变量就记录着上一次计算中心种子用到的种子数量
  afl->centers_gen_time = fuzz_time;							// 中心种子生成所消耗的时间

  for (u32 c = 0; c < afl->queued_items; c++) {				// 遍历种子池
    struct queue_entry * cur_node = afl->queue_buf[c];		// 
    if(cur_node->initial_seed && cur_node->mutated_pos_num != -1){ //重置初始种子
      for(u32 i = 0;i < cur_node->len;i++){						// 遍历每个字节位置，重新初始化一些变量。
        if(cur_node->mutated_pos[i].flag >= 1){				
          M_free(cur_node->mutated_pos[i].A);
          M_free(cur_node->mutated_pos[i].b);

          cur_node->mutated_pos[i].A = M_I(afl->centers_num);
          cur_node->mutated_pos[i].b = M_Zeros(afl->centers_num,1);
        }
      }
    }
  }
}
C

紧接着是：

if(afl->centers_gen_time > afl->queue_cur->vec_update_time){			// 如果中心生成时间大于向量更新时间
  u32 map_size = afl->fsrv.map_size;
  float* cur = (float *)malloc(sizeof(float) * map_size);
  memset(cur, 0 ,sizeof(float) * map_size);

  common_fuzz_stuff(afl, out_buf, len);							// 以in_buf(out_buf与in_buf相等)执行目标程序
  u32 j = 0;
  u8 *src = afl->fsrv.trace_bits;
  while (j < map_size) {
    u8 v = *src;
    if(v){
      cur[j] = (float)v;										// cur记录着已经覆盖的边
    }
    src++;
    ++j;
  }

  for(u32 i = 0;i < afl->centers_num;i++){					// 遍历每个中心种子
    double distance = (double)cal_distance(cur, afl->centers[i], map_size);// 计算当前种子路径与中心种子路径的余弦相似度
    afl->queue_cur->feature_vec->data[i] = distance;						// 特征向量feature_vec->data记录着余弦相似度
  }

  afl->queue_cur->vec_update_time = afl->centers_gen_time;			// 最后更新一下向量更新时间与中心种子生成时间一致
  
}
C

最后一个收尾工作：

if(afl->queue_cur->len > afl->max_len){
  if(afl->history_mutation_sequence){
    free(afl->history_mutation_sequence);
    free(afl->new_mutation_sequence);
  }

  afl->history_mutation_sequence = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));
  afl->new_mutation_sequence = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));

  if(afl->max_len != 0){
    free(afl->dataset_reward);
    free(afl->hit_nums);
    free(afl->tmp_mutated_pos);
    free(afl->tmp_mutated_pos_flag);
  }
  

  afl->dataset_reward = (double *)calloc(afl->queue_cur->len, sizeof(double));
  afl->hit_nums = (double *)calloc(afl->queue_cur->len, sizeof(double));
  afl->tmp_mutated_pos = (u32 *)calloc(afl->queue_cur->len, sizeof(u32));
  afl->tmp_mutated_pos_flag = (u8 *)calloc(afl->queue_cur->len, sizeof(u8));

  afl->max_len = afl->queue_cur->len;
}else{
  memset(afl->dataset_reward, 0, afl->max_len * sizeof(double));
  memset(afl->hit_nums, 0, afl->max_len * sizeof(double));
  memset(afl->tmp_mutated_pos_flag, 0, afl->max_len * sizeof(u8));
}
afl->history_mutation_sequence_idx = 0;
afl->new_mutation_sequence_idx = 0;
afl->tmp_mutated_pos_idx = 0;
afl->from_splicing = 0;
C

收尾结束后，进入测试实例生成的循环中，会执行以下新代码：

if(afl->history_mode && afl->queue_cur->ancestor_seed && afl->from_splicing == 0 && afl->queue_cur->vec_update_time){
  generate_mutation_sequence(afl);									// 生成变异序列
  if(afl->history_mutation_sequence_idx){								// 如果有变异字节出现
    history_able = 1;													// histroy模式标志位
    history_mini_pos = temp_len;										// temp_len为afl->cur_queue->len
    for(u32 e = 0;e < afl->history_mutation_sequence_idx;e++){		// 遍历变异序列
      if(history_mini_pos > afl->history_mutation_sequence[e]) history_mini_pos = afl->history_mutation_sequence[e];											// 找到一个位置最小的变异字节
    }
  }

  if(afl->distribution) free(afl->distribution);						// 如果已经有分布，那么清空。
  afl->distribution = (double *)malloc(sizeof(double) * afl->history_mutation_sequence_idx);//分配空间
  memset(afl->distribution, 0, sizeof(double) * afl->history_mutation_sequence_idx);// 初始化为0
  afl->distribution_sum = 0;													// 置0
  afl->distribution_analyzed = 0;	
}
C

以下是generate_mutation_sequence(afl);

void generate_mutation_sequence(afl_state_t *afl){
  afl->history_mutation_sequence_idx = 0;
  for(u32 i = 0;i < afl->queue_cur->len;i++){
    u64 ii = (afl->queue_cur->map)[i];							// 在add_to_queue中将q->map[i]=i {0..len}
    if(ii > 1000000 || ii >= afl->queue_cur->ancestor_seed->len){
      exit(0);
    } 
    if(afl->queue_cur->ancestor_seed->mutated_pos[ii].flag >= 1){
      afl->history_mutation_sequence[afl->history_mutation_sequence_idx] = i;	// 这个记录的就是哪些位置的字节发生了变异
      afl->history_mutation_sequence_idx++;	//记录着发生变异的数量
    }
  }
}// 本次执行afl->history_mutation_sequence_idx为217，意味着这个种子有217个字节位置发生了变异。它们的位置都被记录在afl->history_mutation_sequence数组中。
C

接下来进入对同一个测试实例的变异次数循环体，由于之前history_able被设置为1了，因此执行以下代码段

else if(history_able == 1 && new_able == 0){
    // 计算两个权重值
    weight_history = 1.0 * afl->queue_cur->found_by_history / afl->queue_cur->exec_history;
    weight_random = 1.0 * afl->queue_cur->found_by_random / afl->queue_cur->exec_random;
	// 计算平均值
    double average = 1.0 * afl->found_all / afl->exec_all;
    if(weight_history < average * (0.7 + decrease) && weight_random < average * (0.7 + decrease)){
       break;
    } 
	// 
    history_line = weight_history;
    random_line = history_line + weight_random;
	// 产生一个随机数
    double tmp = ((double)rand()/RAND_MAX) * random_line;
    if(tmp < weight_history) history_mode = 1;			//如果随机数小于weight_history权重值，则进入history_mode，否则进入random_mode模式。
    else random_mode = 1;					
}
C

由于本次执行时，随机数小于权重值，因此又进入了random_mode，则变异阶段结束后的stat_analysis()函数主体没有执行，执行以下分支：

 if(afl->new_edges_found_idx == 0 || afl->queue_cur->ancestor_seed == NULL || afl->use_splice_mutator || afl->from_splicing){
   afl->mini_mode = 0;    
   u32 after = count_non_255_bytes(afl, afl->virgin_bits);				// 获得afl->virgin_bits中不是255的字节数量，表示覆盖的边的数量
   afl->queue_cur->found_edges += (after - afl->before);				// afl->before存储的是执行之前的覆盖的边的数量，两个数值相减则得到本次fuzzing所得到的新覆盖的边的数量。
   afl->before = after;			// 调整游标
// 如果当前种子splice置1，当前种子发现的新边大于8，并且当前种子的长度大于512
   // 那么重置一些变量
   if(afl->queue_cur->splice == 1 && afl->queue_cur->found_edges > 8 && afl->queue_cur->len > 512){
     struct queue_entry* q = afl->queue_cur;

     u32 map_size = afl->fsrv.map_size;
     q->virgin_bits = ck_alloc(map_size);
     memset(q->virgin_bits, 255, map_size);

     q->reset_times = ck_alloc(map_size);
     memset(q->reset_times, 0, map_size);

     q->initial_seed = 1;
     q->ancestor_seed = q;
     q->splice = 0;
     q->incre = 1;
     q->map = (u64 *)malloc(sizeof(u64) * q->len);
     for(u32 i = 0;i < q->len;i++) (q->map)[i] = i;

     q->mutated_pos = (struct arm *)malloc(sizeof(struct arm) * q->len);
     for(u32 i = 0;i < q->len;i++){
       q->mutated_pos[i].flag = 0;
       q->mutated_pos[i].A = NULL;
       q->mutated_pos[i].b = NULL;
     }
     q->mutated_pos_num = 0;
   }
   return;
 }
C

接下来的循环，第二次执行就进入了history_mode，置history_mode为1，afl->record_flag为1。那么进入stat_analysis后，执行函数主体

if(afl->record_flag && afl->tmp_mutated_pos_idx != 0){		// record_flag表示执行非random_mode，tmp_mutated_pos_idx表示执行了update()函数，这个函数在进入变异算子的时候会执行。下面有对这个函数的具体解释。
    double average_reward;
    if(afl->queue_cur->n_fuzz_entry != afl->cur_n_fuzz_idx){ // 也就是当前队列种子的覆盖路径与上次执行的路径哈希不一致。即输入种子与变异后的种子覆盖路径不一致。
      average_reward = (1 - (double)((double)afl->n_fuzz[afl->cur_n_fuzz_idx] / (double)afl->fsrv.total_execs))/(afl->tmp_mutated_pos_idx * afl->tmp_mutated_pos_idx);// 使用公式计算收益
    } 
    else{
      average_reward = 0;
    }
	// 遍历当前种子所有变异字节
    for(u32 i = 0; i < afl->tmp_mutated_pos_idx;i++){
      u32 target_pos = afl->tmp_mutated_pos[i];
      afl->dataset_reward[target_pos] += average_reward;	// afl->dataset_reward存储着各个字节的收益
      afl->hit_nums[target_pos]++;							// 记录着该字节执行分析的次数
      afl->dataset_size++;									// 记录总共分析多少字节，也即dataset_reward的大小

      afl->tmp_mutated_pos_flag[target_pos] = 0;			// 复原flag，以便下次执行
      afl->tmp_mutated_pos[i] = 0;							// 复原
    }
    if(afl->tmp_mutated_pos_idx == 0) exit(0);				// 没有变异字节，即退出
    afl->tmp_mutated_pos_idx = 0;							// 遍历结束后，置0，便于下次执行判断。
  }

C

void update(afl_state_t *afl, u32 target_pos){
  if(afl->tmp_mutated_pos_flag[target_pos] == 0){					// 给当前变异种子的位置标志置1
    afl->tmp_mutated_pos_flag[target_pos] = 1;						// 
    afl->tmp_mutated_pos[afl->tmp_mutated_pos_idx] = target_pos;	// 记录变异位置，模拟一个队列
    afl->tmp_mutated_pos_idx++;
  }
}
C

// 如果是Fast调度的话，那么会存在这个n_fuzz数据结构
// cksum是当前位图的Hash值
// n_fuzz存储着覆盖路径的执行次数
if (afl->n_fuzz[cksum % N_FUZZ_SIZE] < 0xFFFFFFFF)
 afl->n_fuzz[cksum % N_FUZZ_SIZE]++;
afl->cur_n_fuzz_idx = cksum % N_FUZZ_SIZE;		// 存储最近一次执行的种子的路径hash值，也是n_fuzz的索引
afl->queue_top->n_fuzz_entry = cksum % N_FUZZ_SIZE;		// n_fuzz_entry是种子的成员变量，因此该种子存储着路径在n_fuzz中的索引
afl->n_fuzz[afl->queue_top->n_fuzz_entry] = 1;
C

O.o 终于到最后了！！！！根据概率分布选择变异字节

u32 select_position_based_on_distribution(afl_state_t *afl){
  if(afl->distribution_sum == 0 && afl->history_mutation_sequence_idx){ // distribution_sum为0，说明本次是第一次进行概率分布，afl->history_mutation_sequence_idx不为0，说明有变异字节
    afl->distribution_analyzed++;								// 记录概率分布分析的次数

    double tmp = 0;
    for(u32 i = 0;i < afl->history_mutation_sequence_idx;i++){  // 遍历所有变异字节的位置
      u32 cur_pos = afl->history_mutation_sequence[i];			// 将这个位置值赋予cur_pos

      struct queue_entry * ancestor_node = afl->queue_cur->ancestor_seed;	// 记录一个初始种子指向当前种子的初始种子
      u32 ii = (afl->queue_cur->map)[cur_pos];								// ii现在就等于cur_pos
      double result;
      if(ancestor_node->mutated_pos[ii].flag >= 1){	//如果初始种子的这个字节flag不为0，也就是该字节为必要字节
        Matrix* feature_vec_copy = Matrix_copy(afl->queue_cur->feature_vec);// 复制一个特征矩阵，这个矩阵存储着余弦相似值，调用cal_distance函数得出。
        Matrix* A_copy = Matrix_copy(ancestor_node->mutated_pos[ii].A);		// 复制该必要字节的A值
        Matrix* b_copy = Matrix_copy(ancestor_node->mutated_pos[ii].b);		// 复制该必要字节的b值

        Matrix* A_Inverse = M_Inverse(A_copy);								// A的逆矩阵
        Matrix* theta = M_mul(A_Inverse,b_copy);							// A的逆矩阵与b矩阵相乘
        Matrix* theta_T = M_T(theta);										// 乘矩阵的转置矩阵
        Matrix* r1 = M_mul(theta_T,feature_vec_copy);						// 乘矩阵的转置矩阵与特征向量矩阵相乘

        Matrix* feature_vec_T = M_T(feature_vec_copy);						// 特征向量矩阵的转置矩阵
        Matrix* m1 = M_mul(feature_vec_T,A_Inverse);						// 转置矩阵与A逆矩阵相乘
        Matrix* m2 = M_mul(m1,feature_vec_copy);							// 再与特征矩阵相乘
        double m3 = 0.5 * sqrt(m2->data[0]);								// m3等于0.5倍的根号m2[0]的值
        result = r1->data[0] + m3 + ancestor_node->mutated_pos[ii].SV;	// 计算公式。

        if(m2->data[0] < 0 || isnan(result)){
          printf("feature_vec_copy\n");
          M_print(feature_vec_copy);
          printf("A_copy\n");
          M_print(A_copy);
          printf("b_copy\n");
          M_print(b_copy);

          printf("A_Inverse\n");
          M_print(A_Inverse);
          printf("theta\n");
          M_print(theta);
          printf("theta_T\n");
          M_print(theta_T);
          printf("r1\n");
          M_print(r1);

          printf("feature_vec_T\n");
          M_print(feature_vec_T);
          printf("m1\n");
          M_print(m1);
          printf("m2\n");
          M_print(m2);
          
          printf("m3:%lf\n", m3);
          printf("result:%lf\n", result);
          exit(0);
        }

        M_free(A_Inverse);
        M_free(theta);
        M_free(theta_T);
        M_free(r1);
        M_free(feature_vec_T);
        M_free(m1);
        M_free(m2);

        M_free(feature_vec_copy);
        M_free(A_copy);
        M_free(b_copy);

      }else{
        result = 0;
      }

      if(result < 0) result = 0.05;			// 有一个最大下限
      tmp += result;						// tmp用于累加所有的result值
      afl->distribution[i] = tmp;			// 每个字节的分布值为当前字节的result
    }
    afl->distribution_sum = tmp;			// 将循环结束后的累加值赋予概率分布sum
  }

  if(afl->distribution_sum){				// 若分布和不为0的话
    double choose = ((double)rand()/RAND_MAX) * afl->distribution_sum; // 产生一个随机选择临界值choose
    for(u32 i = 0;i < afl->history_mutation_sequence_idx;i++){
      if(afl->distribution[i] >= choose){							// 选择第一个概率权重值大于等于choose的字节
        return afl->history_mutation_sequence[i];					// 将这个字节返回
      }
    }

    // for(u32 i = 0;i < afl->history_mutation_sequence_idx;i++){
    //   printf("%u:%u -> %f\n", i, afl->history_mutation_sequence[i], afl->distribution[i]);
    // }
    return afl->cur_mutation_sequence[rand_below(afl, afl->cur_mutation_sequence_idx)];// 找不到大于choose的字节，则在变异序列中随机返回一个字节
  }else{ // 分布和为0的话，也随机返回一个字节。
    return afl->cur_mutation_sequence[rand_below(afl, afl->cur_mutation_sequence_idx)];
  }
  
}
C

对于A和b的说明：

1
2
3

// 在stat_analysis()中，对A和b的值作初始化
afl->queue_cur->ancestor_seed->mutated_pos[ii].A = M_I(afl->centers_num);
afl->queue_cur->ancestor_seed->mutated_pos[ii].b = M_Zeros(afl->centers_num,1);
C

最后，执行完分析后还有一段，对data_set的操作

if(afl->dataset_size){ 
    float max_reward = 0;
    float min_reward = 999999999999999;
    for(u32 i = 0; i < afl->queue_cur->len;i++){
      if(afl->hit_nums[i]){												// 记录着变异字节被变异的次数
        if(afl->dataset_reward[i]/afl->hit_nums[i] > max_reward) max_reward = afl->dataset_reward[i]/afl->hit_nums[i];
        else if(afl->dataset_reward[i]/afl->hit_nums[i] < min_reward) min_reward = afl->dataset_reward[i]/afl->hit_nums[i];
      }																	// 获得最大的R和最小的R(收益)
    }
    if(max_reward != 0 && min_reward != 999999999999999 && max_reward != min_reward){
      for(u32 i = 0; i < afl->queue_cur->len;i++){			// 遍历当前执行的初始种子每个字节
        if(afl->hit_nums[i]){								
          afl->dataset_reward[i] = (afl->dataset_reward[i]/afl->hit_nums[i] - min_reward)/(max_reward - min_reward);												// 给每个字节的收益进行赋值
        }
      }
    }

    if(max_reward != min_reward){
        struct queue_entry * ancestor_node = afl->queue_cur->ancestor_seed;
        u32 cnt = 0;
        // 这个循环是为了计算原始种子每个字节的mutated_pos[].A,mutated_pos[].b
        for(u32 i = 0;i < afl->queue_cur->len;i++){
          u32 ii = (afl->queue_cur->map)[i];
          if(ancestor_node->mutated_pos[ii].flag >= 1 && afl->hit_nums[i]){
            cnt++;
            Matrix* feature_vec_copy = Matrix_copy(afl->queue_cur->feature_vec);
            Matrix* feature_vec_T = M_T(feature_vec_copy);
            Matrix* Mul = M_mul(feature_vec_copy,feature_vec_T);
            Matrix* old = ancestor_node->mutated_pos[ii].A;
            ancestor_node->mutated_pos[ii].A = M_add_sub(1,old, -1,Mul);
            M_free(feature_vec_T);
            M_free(Mul);
            M_free(old);

            M_free(feature_vec_copy);
            feature_vec_copy = Matrix_copy(afl->queue_cur->feature_vec);
            Matrix* Mul_b = M_numul(feature_vec_copy, afl->dataset_reward[i]);
            Matrix* old_b = ancestor_node->mutated_pos[ii].b;
            ancestor_node->mutated_pos[ii].b = M_add_sub(1,old_b, -1,Mul_b);

            if(isinf(ancestor_node->mutated_pos[ii].b->data[0])){
              printf("====== %u -> b ======\n", i);
              printf("feature_vec_copy\n");
              M_print(feature_vec_copy);
              printf("dataset_reward:%f\n", afl->dataset_reward[i]);
              printf("Mul_b\n");
              M_print(Mul_b);
              printf("old_b\n");
              M_print(old_b);
              printf("ancestor_node->mutated_pos[ii].b\n");
              M_print(ancestor_node->mutated_pos[ii].b);
              exit(0);
            }

            M_free(Mul_b);
            M_free(old_b);
          }
        }
    }
  }
C

Shapfuzz以C++重构思路：

trimming后，进行判断是否计算中心种子

调用kmeans_main()函数，得到afl->centers，并且初始化mutated_pos[].A和mutated_pos[].b
再根据中心的生成时间与特征向量矩阵的更新时间来决定是否对特征向量矩阵进行更新

更新主要是计算各个种子路径与中心种子的余弦相似度。
初始化后面Shapley分析要用到的成员变量

这里的if判断是为了确保分配的空间足够装得下种子
然后直接来到havoc_stage
进入变异循环体前，首先判断是否需要生成变异序列。

如果需要的话，那么调用generate_mutation_sequence()函数生成，并找到最小的变异位置。随后重置distribution数组，distribution_sum和distribution_analyzed。
进入变异生成测试实例循环体

首先计算decrease，然后进入模式的判断。random_mode是原本aflpp的，history_mode是使用Shapley的。

随后，确定好各个模式后，对相应变量初始化。
进入变异次数控制循环体

生成的随机数r会选择某个变异器进行变异。这里会调用select_position_based_on_distribution()函数，选择一个字节位置进行变异。
测试实例生成好后，执行即可。
执行完毕后，调用stat_analysis()函数

该函数对所有的必要字节进行操作，将其mutated_pos[].A和mutated_pos[].b和mutated_pos[].flag都计算得出。

随后，根据执行结果，势必有一些必要字节。对每一个必要字节都+(float)afl->new_edges_found_idx/necessary_nums;作为Shapley值。每一次执行的所有必要字节的Shapley Value是相同的。
本次执行的最后，有一个收尾工作。

如果本轮执行，使用到了Shapley分析，那么计算一下原始种子的A和b
进入下一测试实例生成轮次。即跳转到6，直至变异执行阶段结束后，进入下一轮次的选种策略。

Fuzz

#Fuzz

AFL使用与源码分析

https://loboq1ng.github.io/2024/08/21/AFL使用与源码分析/

作者

Lobo Q1ng

发布于

2024年8月21日

许可协议

pwn.college: Assembly Crash Course 上一篇

二进制安全-基础下一篇