1. Introduction
fuzz技术应用很受欢迎，已成为prominent vendors安全部门的保留项目。
然而很多fuzzer的描述文档很不完善，而且不同的fuzzer在命名方面碎片化严重，举个例子：AFL将减小crashing input的size技术命名为' “test case minimization'，funfuzz却命名为'test case reduction'，而一个BFF中名叫'crash minimization'的技术的意思却是最小化原始测试输入和crashing input的区别(hamming distance??)
文章要统一fuzz技术中的术语并建立一个统一的fuzzing模型。
2. SYSTEMIZATION, TAXONOMY, AND TEST PROGRAMS
2.1 Fuzzing & Fuzz Testing
介绍了Fuzzing，Fuzz Testing，Fuzzer，Fuzz Campaign，Bug Oracle，Fuzz Configuration的定义，其中:
Fuzz Campaign: 在特定安全策略下的一轮fuzz，目的是发现违反安全策略的bug。
Bug Oracle：检测程序执行是否违反安全策略的一种机制。
Fuzz Configuration：控制Fuzz算法的参数值，该配置的类型由Fuzz算法的性质决定。
seed: 一般是一个对受测程序精心构造的输入，被用于变异生成多种测试用例。Fuzz工具一般都维护一一系列种子，一些Fuzz工具的每轮Fuzz都会进化自己的种子池。
2.2 Paper Selection Criteria
参考的都是些很牛逼的会议
2.3 Fuzz Testing Algorithm
算法1以一系列fuzz configuration C，和限定时间t作为输入，以发现的bug B作为输出。
算法分为两个部分，第一个是preprocess的部分，在fuzz campaign的开头执行，第二个部分是五个函数的循环：
schedule,inputGen, inputEval，confUpdate，continue。
每次循环为一个fuzz迭代, 循环中的inputEval函数执行fuzz测试的过程叫做fuzz run。
根据用户输入的fuzz configuration来生成potentially-modified的fuzz configurations，其中的操作根据具体的fuzz算法来定，可能的操作包括给代码插桩，测量原始fuzz文件的执行时间等。
根据当前时间和deadline从输入的fuzz configurations选择一个进行fuzz迭代。
根据选择的fuzz configuration生成测试用例。
用tcs(用例)测试，通过bug oracle(嵌入在fuzzer中)检查本次执行是否违反了安全策略。输出bugs和每次fuzz run得到的信息execinfos。
根据现有的configuration和执行信息更新(优化)fuzz configurations。
根据现有fuzz configurations判断是否该运行新的迭代，主要用于白盒测试中路径已遍历完整情况。
2.4 Taxonomy of Fuzzers
3中fuzzer，提出异于传统的灰盒fuzz
2.4.1 Black-box Fuzzer
2.4.2 White-box Fuzzer
2.4.3 Grey-box Fuzzer
不完全解析程序语义，而是执行轻量级的静态分析或收集执行的动态信息(如代码覆盖率)。灰盒牺牲了信息的完整性来换取速度和测试输入数量。
早期的灰盒fuzzer有EFS，算法根据每次fuzz收集的代码覆盖率信息来生成测试用例。Randoop也类似，不过它不是针对安全漏洞的fuzzer。
AFL和VUzzer是灰盒业界标杆。
2.5 Fuzzer Genealogy and Overview
图1中都是耳熟能详的或在Github上100星以上的fuzzers，左半边为黑盒，右半边为灰盒和白盒。然后每个大类根据测试输入细分为file, network, UI, web, kernel I/O, or threads (in the case of concurrency fuzzers)
表1是根据之前介绍fuzz模型的五个函数的实现与否归纳的。除此之外，杂项列(Misc.)还列举了fuzzer的源码是否开源和是否要求被测程序源码的信息。
像SymFuzz这种‘白+黑’的，就是在preprocessing 阶段进行白盒分析，为的是优化黑盒fuzz的性能。
第5列为fuzzer是否能影响fuzz模型，第6列为fuzzers是否在preprocess阶段同时支持动态和静态分析， 第7列表示fuzzer是否支持处理多种seeds和perform scheduling，mutation列表示fuzzer是否通过输入变异来生成测试用例，用黑白圆来表示fuzzer根据执行反馈信息来进行输入变异的方式。INPUTEVAL部分表示fuzzers是根据stack hasing还是代码覆盖率来进行崩溃分类？(crash triage) 最后confUpdate栏第1列表示fuzzer是否在confUpdate过程更新种子库，第2列表示fuzzer是否在线更新输入模型，最后一列表示是否从种子库中移除无关种子。
3. PREPROCESS
包括插桩，去除冗余configuration，修剪种子，生成驱动程序，还有准备生成输入的模型。
3.1 Instrumentation
白盒和灰盒fuzz的插桩可以收集fuzz执行时得到的或通过fuzz runtime内存得到的程序反馈。(收到程序反馈的量决定了这是什么颜色的fuzzer)
插桩分为动态和静态，其中动态插桩在本
算法的inputEval部分。
插桩又分为源码插桩和二进制插桩。
动态插桩的好处在于容易对动态链接库进行插桩，工具例如DynInst , DynamoRIO , Pin , Valgrind, and QEMU.
一些fuzzer既可以动态插桩也可以静态插桩，AFL正常模式即为静态源码插桩，利用QEMU工具课进行动态二进制插桩。动AFL还能记录外部库函数的路径。
3.1.1 Execution Feedback
路径覆盖：AFL，CollAFL
节点覆盖：LibFuzzer，Syzkaller
3.1.2 In-Memory Fuzzing
对于需要启动一段时间后再接收输入文件的一些大程序来说，每次fuzz都要启动一遍效率很低，解决方案为将以就绪接收输入文件状态的程序打快照进内存，然后每次迭代直接从访问内存中快照的状态进行。此方法亦适用于有大型通讯流的网络应用。
一些fuzzers 执行in-memory fuzzing每次迭代时不需要重现受测程序的初始状态，这种技术叫in-memory API fuzzing。AFL的persistent mode就是可以实现fuzz loop却不用重启进程
缺点：bugs不好复现，多次重复执行一种函数带来的副作用，主要依赖于被测程序的入口函数，不是很好找。
3.1.3 Thread Scheduling
Race condition(由于两个或者多个进程竞争使用不能被同时访问的资源，使得这些进程有可能因为时间上推进的先后原因而出现问题，这叫做竞争条件)的bugs比较难以触发，因为这种bugs触发条件为不确定的行为。插桩技术可以通过精确控制线程调度来触发程序的不确定行为。
3.2 Seed Selection
怎样减小初始种子库大小的问题称为种
子选择问题。
找到最小的种子集，以使覆盖率（例如节点覆盖率）最大化，此过程称为计算最小集(minset)。
例如：两个种子s1,s2覆盖了PUT中的地址
{s1 → {10, 20} , s2 → {20, 30}}，如果第三个种子为s3 → {10, 20, 30}且速度与s1和s2相同，则替换掉，可以省一半时间
3.3 Seed Trimming
较小的种子可能会消耗较少的内存并引发更高的吞吐量，所以一些fuzzers在fuzz之前减小种子的大小，这便是种子修剪。
它可以发生在preprocess或confUpdate过程中。
AFL的种子修剪使用代码覆盖率工具迭代地删除一部分种子，同时保证了修改后的种子有相同的覆盖率。
3.4 Preparing a Driver Application
难以直接测试PUT时，安排一个driver来fuzz是说得通的。例如要fuzz一个库，我们写一个调用了库中函数的driver程序，再来fuzz driver程序。
4 SCHEDULING
在fuzz过程中每次迭代选用哪个fuzz configuration的工作叫做调度。
BFF和AFLFast，有着创新的调度算法。
