浅谈模糊测试基础技术——引导机制

    引导机制是模糊测试技术中的一种重要机制，其核心功能是在动态测试的过程中决定什么样的测试用例可以成为新的种子，通过影响种子的方式来达到引导测试对象向特定方向前进的目的。为了更好地完成测试目标，以更高的概率发现测试目前存在的潜在bug，研究者提出了不同的引导机制。这些方法根据实现原理以及引导思路的不同可以被总结为5大类别：代码覆盖率引导机制、目标距离引导机制、Sanitizer引导机制、状态机引导机制以及神经元覆盖引导机制。表1对现有的5种引导方式及其代表性的工具进行了总结。

表 1 不同模糊器的引导机制

    代码覆盖率引导是目前最常见的一种引导方式。代码覆盖率(Code Coverage)是指的是在测试过程中，被测试对象被覆盖到代码的数目占总数的比例。一般来说，更高的代码覆盖率可以发现更多的漏洞，代码覆盖的判断方式：在源程序中指源代码中某行代码是否执行；在二进制程序中指某条汇编指令是否执行。覆盖率的计量方式有三种常见的方法：基本块(Basic Block)、边(Edge)和路径(Path)覆盖。代表性的工具有AFL、Vuzzer、Angora、CollAFL等。

    目标距离引导是定向模糊测试中常用的一种引导方式。程序中所有代码发现漏洞的概率不相同，绝大部分代码并不存在漏洞，过分追求完整的代码全部覆盖是不实际的，于是就诞生了定向型模糊测试。定向Fuzzer针对程序中有可能会出现bug的特定目标位置，通过计算当前测试用例覆盖的代码到目标的距离来引导程序更快到达这些位置，并着重对这些位置进行测试，以加快暴露漏洞的时间。

    Sanitizer是一个错误检测框架，可以在目标程序中插入各种可能的错误检查（访问越界或者溢出）。一般Fuzzer用Sanitizer主要是为了改进错误检测和分类，但使用Sanitizer并结合定向Fuzzing技术来改进目标程序中的bug覆盖率也是一种新的引导思路。

     状态机的引导方式主要用于协议Fuzzing，协议Fuzzer通常不止收集覆盖率，还会在接收客户端Request时记录当前协议状态（Protocol State）。最后可以生成整个会话期间的状态变化序列，再根据该序列是否触发新状态来引导种子是否加入语料库中。

    神经元覆盖用于针对深度学习模型的Fuzz。对于一个Deep Learning系统来说，其具体逻辑并不完全体现在代码的分支流程图上，而是与具体神经元相关，最后结果实际上受到神经网络中每一个神经元的影响。因此神经元覆盖率是深度学习模型模糊测试领域的一个重要指标。

    下面对每种引导方法的具体思路及代表性工具进行详细介绍。

（1）基本概念

先来了解一下基本块的定义

    基本块（basic block）其实是一段线性代码，缩写为BB，只能从该段代码的入口处进入，其他程序不能通过跳转的方式进入，同时在基本块中也不能跳转出去，只能从这段代码的最后一行离开转移到另外一个基本块。在程序控制流程图中，基本块是其中的节点。在IDA中用 Graph Voverview 打开程序可以比较清晰地看到基本块划分，如下图所示，图中的每一块就代表一个基本块。

    BB是程序执行的最小连贯单元，可以通过第一条指令的地址来识别，BB信息可以通过代码插装和静态分析轻松提取。由于这些优点，BB覆盖信息被Fuzzer广泛使用。而基于BB覆盖引导Fuzzer只跟踪每个块是否被击中，而不跟踪在模糊过程中击中哪个块的顺序，因此会导致细节信息丢失。

（2）代表性工具

    (a) VUzzer

    以VUzzer为例，VUzzer 使用了块覆盖率作为评估对象，它在进行 fuzz 之前对程序进行简单的静态分析来获取每个基本块深度信息，在输入选择阶段为每个基本块进行权重分配。

        VUzzer在静态分析阶段还会找出程序的所有cmp和lea指令，这是为了在动态运行时方便进行插桩。通过cmp指令来找出立即数，也就是magic bytes，取地址指令lea则是用来对输入类型信息进行判断。VUzzer 认为每个分支的两个基本块都有50%的概率运行到达，并以此推算所有的基本块到达概率p，基本块的权重则是用1/p计算得到。这个权重体现了覆盖到此基本块的难易程度，在选择输入时，会优先考虑权重更高的输入，增加覆盖到此基本块的概率，从而提高代码覆盖率。

（1）基本概念

        用控制流程图 CFG 来描述一个程序，把图中每一个基本块看作一个节点，那么边(edge)就可以用来表示节点之间的跳转关系。记录边可以了解到基本块和跳转的执行次数，从而可以知晓程序中每个语句和分支的执行次数，通过记录边覆盖可以获得比记录基本块更加细粒度的覆盖率信息。同样下图结合IDA来具体理解一下边的概念。

        为了解决块覆盖精度不够的缺点，边覆盖跟踪每个edge是否被命中，在覆盖粒度上有比较好的提升。边覆盖率作为引导指标的工具有很多，大多数都是在AFL的基础上进行完善和提升，下面结合工具作介绍。

（2）代表性工具

    (a) AFL

    AFL是第一个将边覆盖引入Fuzzing的工具，它通过编译时插桩，模糊测试中获取边缘覆盖率信息，使用进化算法，将边覆盖率作为算法的适应函数，使得模糊测试可以沿着覆盖率增大的方向进行。AFL 使用(branch_src, branch_dst)未作二元组(tuple)来记录当前基本块和前一基本块的信息，元组可以理解为边。在插桩阶段基本块前插入的桩代码本质上等价于：

cur_location：基本块的 ID，由当前时间随机生成；

shared_mem[]：一个 64KB 大小的共享内存，每字节数组成员可以被认为是Fuzzing过程中对待测程序中特定元组的命中(hit)，下标由当前基本块 ID 和前一基本块 ID 进行异或运算得到，数组中对应的值则表示命中次数；

prev_location：前一个基本块 ID，执行完上面两句后，将该变量置为cur_location右移1位后的值。

    位图的大小设定为64KB是平衡测试速度和碰撞率最后做出的折中，很多程序的边缘数在 2k 到 10k 之间，同时它的大小足够小，允许接收端在几微秒内分析位图，匹配 L2 缓存速度。

    通过插桩，AFL主体可以通过进程通信的方式启动桩代码中的 forkserver 来接收AFL的命令请求，从而在运行时获取每个测试样本的边覆盖率，结合进化算法来引导样本进行变异，可以得到相对好的测试样本集合。

    (b) Angora

    与AFL采用上下文无关的边覆盖不同，Angora 选择了上下文敏感的边覆盖率作为它的评估指标。Angora同样记录每个边的命中次数，对于置于不同上下文的相同的边视为不同的边，这里的上下文特指程序执行时候的调用栈。这种方法使得计数对象更加细节，每次Fuzzing都会选择一个未探索的分支并搜索该分支的输入，对程序执行过程中边变化的体现有一定程度上的提高。

    Angora 会确定输入字节流相应的判断，每次修改只针对输入中需要改变的字节。然后将分支上的路径约束视为输入到黑盒函数的约束，采用机器学习中梯度下降算法来解决约束，期间对黑盒函数参数进行评估。

    Angora使用包含上下文信息的元组Tuple来表示边(l_prev,l_cur,context)，上下文context用h(stack)表示，h是哈希函数，stack包含了函数调用栈的状态，这是因为上下文改变后程序到达的同一个分支可能会触发新的内部状态，这样就将处于不同上下文的相同边表示为不同的边。

    (c) CollAFL

    AFL采用粗略的覆盖率信息来实现高效灰盒测试，将命中次数存储在紧凑的位图中，这样的覆盖范围是不准确不完整的，这会导致路径碰撞（path collisions），无法发现新路径来触发新的crashes。如果两个不同路径的hash是一致的，则会发生路径碰撞，后测试的那条路径就会被识别先前测试的那条路径中去，后面的这条路径及其相关路径就得不到相对应的测试。当边缘数达到50000条时，碰撞率可能达到30%[3]，在某些程序中甚至达到75%[17]。另外一个问题就是会影响Fuzzing策略，种子选择策略需要精确的覆盖信息，不精确的覆盖范围会影响这种选择种子的策略。

        对于hash碰撞问题，提高散列空间是最直接的解决方案，但是由于性能和随机性的因素，这并不是一个完美的解决方案。CollAFL生成三个新的hash计算公式，将碰撞率降低至接近0。具体计算公式如下：

    其中x,y,z是来自不同边的参数，对于不同的边，这些参数可能不同。将BBL分为两类，一类有多个先例BB，另一类只有一个先例BB，使用Fmul和Fhash处理第一类BB，Fsingle来处理第二类BB，保证所有边的 hash 值不相同，从而解决路径冲突的问题。再提出三种种子选择策略：第一个策略是，具有更多未触及的相邻分支的种子将优先进行模糊化。第二种政策倾向于选择有更多未受影响的邻居后代的种子。第三种更喜欢具有更多内存访问操作的种子。

（1）基本概念

    先了解一下路径覆盖引导跟踪整个执行路径，包括边与边之间的序列，这能提供最全面的代码覆盖信息。然而一个路径的长度可以很长，并且在大型应用程序中路径的数量巨大，因此追踪路径覆盖对于系统开销和内存开销是十分庞大的。在实际运用中，对于路径覆盖率引导这种方式常常导致路径爆炸问题，现阶段对于路径引导的研究很少，多数研究都主要集中于对块覆盖率引导与边覆盖率引导这两个方向。

（2）代表性工具

    (a) PathAFL

    某些漏洞只能在特定的执行路径下触发。仅使用BB或Edge覆盖可能会忽略此类路径，并且无法触发漏洞。路径覆盖信息提供了更准确的执行跟踪知识。从理论上讲，这些信息可以更好地指导模糊者。为此PathAFL平衡了路径信息粒度和模糊测试性能开销。将发现的新路径分为两种：

• e-path：包含未击中边的路径，e表示edge;

• h-path：其中所有边都被击中过的路径，h表示该路径的哈希值有变化;

    PathAFL在编译时插入代码。这些代码在程序执行期间自动计算路径散列，并将其存储在共享内存中，PathAFL可以从中读取以检索程序执行路径的散列值。这样就避免了记录整个路径的详细信息。PathAFL仅通过跟踪较大的函数和内存操作函数来执行选择性检测。该方法减少了实际跟踪的路径数量。PathAFL设计了一个快速路径过滤算法来确定哪些路径的测试样例需要添加到种子队列中，这里参考并改进了CollAFL的一个关键点，根据未触及的相邻分支的数量和分支中的函数调用动态计算路径的权重。只有当新发现的路径的权重较高时，与该路径对应的测试用例才会添加到种子队列中。在能量调度算法中，为权重高的路径分配更多能量。

（1）基本概念

定向Fuzz的应用场景很多，比如一些平台通用的引擎被曝出漏洞，那么这些平台相应代码中很可能会出现类似的漏洞；当一个程序打补丁修复bug时，可以针对打补丁的那部分代码，检测是否完全修复bug或该补丁是否引入新的bug。以上情况都能用到定向Fuzz来对用户指定的特定位置的代码区进行Fuzzing。定向Fuzz的主要引导机制是目标距离引导，最先由AFLGo提出。

（2）代表性工具

    (a) AFLGO

    论文Directed Greybox Fuzzing 中第一次被提出Directed fuzzing这个概念，在 AFL 的基础上，开源了一个名为 AFLGo 的工具。AFLGo可以快速到达指定目标点的模糊测试工具。后来相关定向灰盒模糊测试(DGF)的研究基本都基于AFLGo的基础上展开。

    AFLGO整个过程分为了编译准备阶段和运行阶段。在编译阶段，首先提取CG和CFG。对于每一个BB，计算到达目标位置的距离。在运行阶段，会统计运行过的基本块集合，计算种子距离。根据整个种子运行的轨迹距离目标target的距离，来为种子分配能量。这样就可以使得那些离目标点近的种子分配到更多能量，提高Fuzzer发现漏洞的可能；距离目标较远的种子则分配较少能量，以免在重要性低的地方花费过多时间。

    AFLGO 首先根据 CG 计算函数层面 (function-level) 的距离，然后基于 CFG 计算基本块层面 (basic-block level) 的距离，最后将基本块的距离作为插桩时使用的距离。AFLGo支持标记多目标，在距离计算时需要将每个基本块到多个目标的距离做一个加和，这里采用的是对到每个目标的距离和取调和平均数。

    在Fuzzing前期，AFLGo尽可能扩大代码覆盖率，当覆盖率到一定程度再使用，较优的种子来进行变异，从而实现目标距离引导。为了不让Fuzzing陷入局部最优解的困境，AFLGo在种子打分阶段加入模拟退火算法，，以时间和距离为指标对种子打分，该分数影响到每个种子的Fuzzing时长。运行时间越长，距离越近的种子得分越高，该种子得到的Fuzzing时长更多。

    (b) Hawkeye

    Hawkeye认为AFLGO中所定义的距离过于简单了，没有办法让一些有潜力能够到达目标位置区域的种子获得更多的能量，提出了目标函数轨迹相似度的概念（target function trace similarity)。

    Hawkeye重新定义了距离函数，应用静态分析结果来增强相邻函数的距离，认为函数级别和基本块级别的距离应该基于增强的函数距离来模拟函数之间的亲和力，计算基本块追踪距离和执行跟踪与目标函数的覆盖函数相似度。

    Hawkeye修改了能量调度算法，结合基本块追踪距离和覆盖函数相似性引导种子排序。距离越小的种子应该被分配更多的能量，距离更接近的应该放在前面。

（1）基本概念

    Fuzzing的关键问题之一是在哪里寻找漏洞，由于代码覆盖率与漏洞覆盖率相关，基于代码覆盖率的Fuzzing不断提升自身覆盖率，但代码覆盖率通常高于漏洞覆盖率，这会导致错误的漏洞平均发现时间TTE。ParmeSan是第一个提出Sanitizer引导的Fuzzer，依靠现成的Sanitizer程序检查来自动最大化目标错误类别的错误覆盖率。与盲目提高覆盖率的Fuzzer不同，ParmeSan致力于发现代码中的bug，将Fuzzing探索引导至重要的执行路径，从而有最大的机会在最短的时间内触发错误。

（2）代表性工具

    (a) ParmeSan

    ParmeSan通过将程序的带有Sanitizer的版本与基准进行比较，从而以黑盒的方式定位Sanitizer检查，并使用修剪启发法清除不感兴趣的检查。使用自动化动态构建控制流图CFG的方法将Fuzzing引导至目标。ParmeSan通过采用两阶段定向的模糊测试策略，在该策略中，模糊测试器交错两个阶段（针对CFG构建进行模糊测试，对目标点进行模糊测试）并利用两者之间的协同作用。例如，由于第一个CFG构建阶段需要数据流分析（DFA），因此作者使用可用的DFA信息来加快第二个错误查找阶段。基于DFA的模糊测试不仅有助于查找新代码，类似于最新的覆盖范围指导的模糊测试，而且还可以有效地翻转sanitizer检查并触发错误。

（1）基本概念

服务器的行为及其漏洞取决于一段时间内交换的一系列消息，这些消息决定了服务器的状态。状态机由状态和转换状态的输入组成，由于协议的复杂性，代码覆盖率不再满足协议模糊测试的需求，协议Fuzzer通常向状态机中逐渐添加新的状态来推断状态机。初始状态机根据变异输入来探索新的状态。协议漏洞通常基于状态机进行分析，旨在搜索易受攻击的状态转换。

（2）代表性工具

    (a) AFLNET

    AFLNet是一款灰盒协议fuzz工具，采用了代码覆盖率反馈、种子变异以及状态反馈等技术。与传统的基于生成的协议Fuzzer，它采用了Server和Client之间的通信消息数据作为种子，无需任何的协议规范。本质上是模拟一个Client来发送一系列消息到Server，并保留可以触发新的代码执行路径或者响应状态的变异数据。研究人员可以自定义消息解析器输入AFLNet来提取协议状态信息，使用Server端的响应码来识别消息序列触发的不同状态，从而构建状态机。根据这种反馈，AFLNet可以尽可能向有效的状态区域靠近。

    (b) StateAFL

    StateAFL在AFLNet的基础上进行改进，提出了分析内存的方式来获取状态和状态转变信息，这种方法不需要研究人员自定义消息解析器提取状态协议信息，实现了一种完全自动化的方案。

具体实现方式是在插桩时添加调用代码，在服务器程序启动和结束、内存分配与释放的相关函数进行插桩，调用一些用于记录内存的自定义函数来记录状态和状态转移，从而实现状态机的构建。

（1）基本概念

深度学习（DL）系统的神经元覆盖（neuron coverage）率类似于传统代码覆盖率，但由于DL系统中大多数规则是从训练数据中学习的，与传统手工编写的软件存在偏差，所以代码覆盖率并不是评估DL模型的良好指标。一般来说可以将测试输入所激活的神经元与DL系统中神经元总数的比率认作为神经元覆盖率。

（2）代表性工具

    (a) Deepxplore

    DL系统在当下应用越来越广泛，而现有的DL测试很大程度上依赖于手工标记数据，因此往往无法完全测试到所有情况，导致DL系统在实际运行中会在某些边缘情况可能存在误判。DeepXplore框架针对这个问题提出解决方案，该框架引入神经元覆盖，系统地测量由测试输入执行的DL系统的部分，并利用多个具有类似功能的DL系统作为交叉引用预言，以避免手动检查。

对于DL系统来说，最后的结果实际上受到神经网络中每个神经元的影响。简单来看，神经元输出越大则对最终结果影响越大，因此作者提出设置一个threshold，如果神经元输出超过这个threshold则算是激活。因此，测试用例生成的目的则是最大化被激活的neuron总量。

    (b) DeepGauge

    DeepGauge是一套用于深度学习系统的多粒度测试标准，这其中就包含了神经元级别的覆盖标准，分别是K多节神经元覆盖(KMNC)、神经元边界覆盖(NBC)和强神经元激活覆盖(SNAC)。

K多节神经元覆盖，把每个神经元的输出最低到最高切出k个section，每个神经元n的K多节覆盖可以表示为：

进一步可以将DNN的K多节覆盖可以表示为：

    神经元边界覆盖，被定义为被覆盖corner-case与corner-case总数的比率，用于度量给定测试输入集t覆盖了多少corner-case区域（上边界和下边界值）。其定义为覆盖角盒数与角盒总数的比率把负无穷到最低值和最高值到正无穷之间的输出都归类：

    强神经元激活覆盖，衡量给定测试输入t覆盖了多少个corner-case，只看UpperCornerNeuron的输出：

    以上就是对常见引导机制的一些简要介绍。在实际运用中，由于应用程序和缺陷的复杂性，针对不同类型的应用程序实现自动化的模糊测试依然面临许多挑战，其中选取合适的引导机制是提高实际漏洞挖掘效率的关键之一。

[1] MichaÅĆ Zalewski. 2021. AFL (american fuzzy lop). https://github.com/google/AFL accessed 21-January-2021

[2] Shuitao Gan, Chao Zhang, Xiaojun Qin, Xuwen Tu, Kang Li, Zhongyu Pei, and Zuoning  Chen. 2018. CollAFL: Path sensitive fuzzing. In IEEE Symposium on Security and Privacy  (S&P). IEEE, 679-696.

[3] Peng Chen and Hao Chen. 2018. Angora: Eicient Fuzzing by Principled Search. In IEEE Symposium on Security and Privacy (S&P). 711-725.

[4] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giufrida, and Herbert Bos. 2017. VUzzer: Application-aware evolutionary fuzzing. In The Network and Distributed System Security Symposium (NDSS). 1-15.

[5] Yan S, Wu C, Li H, et al. Pathafl: Path-coverage assisted fuzzing[C]//Proceedings of the 15th ACM Asia Conference on Computer and Communications Security. 2020: 598-609.

[6] Pham V T, Böhme M, Roychoudhury A. AFLNet: a greybox fuzzer for network protocols[C]//2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST). IEEE, 2020: 460-465.

[7] Natella R. StateAFL: Greybox Fuzzing for Stateful Network Servers[J]. arXiv preprint arXiv:2110.06253, 2021.

[8] Pei K, Cao Y, Yang J, et al. Deepxplore: Automated whitebox testing of deep learning systems[C]//proceedings of the 26th Symposium on Operating Systems Principles. 2017: 1-18.

[9] Österlund S, Razavi K, Bos H, et al. {ParmeSan}: Sanitizer-guided Greybox Fuzzing[C]//29th USENIX Security Symposium (USENIX Security 20). 2020: 2289-2306.

[10] Chen H, Xue Y, Li Y, et al. Hawkeye: Towards a desired directed grey-box fuzzer[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 2095-2108.

[11] Böhme M, Pham V T, Nguyen M D, et al. Directed greybox fuzzing[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 2329-2344.

[12] Ma L, Juefei-Xu F, Zhang F, et al. Deepgauge: Multi-granularity testing criteria for deep learning systems[C]//Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering. 2018: 120-131.