基本信息
原文名称 Path transitions tell more: optimizing fuzzing schedules via runtime program states
原文作者 Kunpeng Zhang；Xi Xiao；Xiaogang Zhu等
原文链接 https://dl.acm.org/doi/10.1145/3510003.35
10063
发表期刊 ICSE '22: Proceedings of the 44th International Conference on Software Engineering
一、引言
模糊测试是如今广泛使用的一种漏洞挖掘技术，用于探测测试目标的安全问题。其中，基于覆盖率引导的灰盒模糊测试(Coverage-guided Greybox Fuzzing, CGF)是目前最为典型的模糊测试方法，它根据种子的覆盖率信息决定模糊测试过程中后续的选择和变异，引导模糊测试探索更多的代码覆盖。现有的提高CGF效率的解决方案主要有两种：①通过推断输入字节和路径约束的关系来减少输入的搜索空间；②通过设定模糊过程和建立概率分布来优化种子的能量调度。两种方法都有各自的不足：前者属于主观推断，推断结果可能包含路径约束外的额外字节；后者只关注于种子的能量调度，而忽略了种子中的字节调度。
本文结合以上两种方案，提出了一种轻量级的CGF优化方案——Truzz，主要思想是利用路径转换之间的差异，从字节分析和种子优先级两个方面优化CGF，做出了以下研究：
01
提出轻量级的CGF优化框架Truzz，利用可以指示目标程序属性（如验证检查和未发现的代码区域）的路径差异来提高CGF的性能。
02
通过实验验证Truzz中字节分析调度的有效性，并设计对比实验，比较引入Truzz框架的模糊器与原模糊器的性能，边覆盖率平均增加24.75%，识别了6个没有被原模糊器探测出来的漏洞。
二、 路径转换间的差异
首先简单介绍模糊测试中路径转换(Path Transition)的概念：设种子
（1）如果路径转换导致路径明显缩短，该转换很可能与验证检查相关。其中，验证检查(validation check)是指保护错误处理代码(error-handling code)的路径约束。例如图1中的验证检查Ⅰ和验证检查Ⅱ分别保护了错误处理代码Ⅰ和错误处理代码Ⅱ。从图中可以发现，如果一个输入验证检查Ⅰ失败，该输入的执行路径仅仅只有10条边；但如果该输入通过了验证检查Ⅰ，执行路径的长度必定不止10条边。与此同时，通过验证检查Ⅱ与否也会带来这样的结果。这是因为错误处理代码往往会导致程序进程的提前终止，使得执行错误处理代码的路径比执行函数功能代码的路径短很多。
（2）如果路径转换发现了包含新边的执行路径，则说明其很可能会探索到未发现的区域。换言之，路径中覆盖更多新边可能会引导模糊器找到更多未发现后代，触及更多的新代码区域。如图1所示，如果一个种子的执行路径为ACFJLN，其新边为CF、FJ、JL、LN，则该路径未被发现的基本块有I、K、M、O、P；而另一个种子执行路径为ABDG，其新边为BD、DG，则该路径未被发现的基本块只有H。显然，第一个种子具有探索更多未发现代码区域的潜力。因此，在模糊过程中，对于执行路径包含更多未发现的新边的种子，给予其更高的优先级可能会进一步提高代码覆盖率。
图 1 路径转换间差异示例
举一个例子以显示模糊测试中对字节分析调度的需求。图2为一段验证检查代码，第2行是一个验证检查，保护了第8行的错误处理代码。为了测试函数功能代码，必须通过第二行的验证检查。图2中输入长度为5字节，如果单纯使用随机变异，可能会产生个新输入，其中大部分都不能通过第2行的验证检查。如果模糊器可以推断出第一个字节与验证检查相关，那么其最多只需要256次变异就可以绕过该约束。
然而，一般的基于推理的模糊器在推理约束的相关字节时，可能会由于推理依赖于执行状态的变化，受到用于该路径约束的额外字节的影响。例如图2中第3行的约束条件会显式受到变量b影响，隐式受到变量a影响，因此基于推理的模糊器的输入与第3行的条件相关字节为input[0:4]，这会导致模糊器在解析第3行约束时变异字节input[0]，使得输入可能最终流向错误处理代码，导致进程提前终止。所以我们需要关注验证检查相关的input[0]字节变异，减少进程提前退出的概率，提高模糊测试效率。Truzz通过路径转换间的差异，识别与验证检查相关的字节，并在变异阶段保护该字节以缓解上述问题。
图 2 验证检查
三、 Truzz框架与方法
1 Truzz概述
Truzz是一个轻量级框架，没有利用复杂的污点分析来获取相关字节位置。如图3所示，主要由字节分析和种子优先级两部分构成，分别利用上述的路径转换间差异，针对与验证检查相关的字节和能发现更多新边的种子，对CGF进行性能优化。Truzz会对每个种子进行排名，能够发现更多新边的种子具有更高的优先级。每当一个种子被选择后，Truzz会执行字节分析，识别出于验证检查相关的字节，在随后的变异阶段，会给这些字节较低的变异概率。
图 3 Truzz流程概述图
2 字节分析
在字节分析阶段，Truzz根据路径转换过程中两种执行路径之间的差异为输入字节建立概率分布，并利用概率分布选择要变异的字节。如果一个字节更可能与验证检查相关，则该字节在变异阶段被选中的概率更低。Truzz会为选定种子的字节与验证检查的可能性度量为一个适应度值，以二分法优化字节分析的过程以提高效率，最后根据适应度值为字节分配一个变异概率。字节分析只对每个种子执行一次，在AFL框架下，主要是在确定性变异阶段的bitflip中实现。
（1）字节适应度
上文分析已经指出，如果路径转换导致路径明显缩短，该转换很可能与验证检查相关。为衡量一个字节与验证检查相关的可能性，Truzz首先会对每个字节进行变异，并根据路径转换的长度差异计算种子适应度。计算中路径长度以路径中边的数目衡量，具体公式如下：
以图1为例计算适应度
若变异字节
若变异字节
对比发现
（2）二分法
程序中的验证检查比较稀疏，即只有小部分输入字节与验证检查相关，大部分的输入字节流入功能代码中。因此，逐个字节地计算适应度相当耗时，本文使用二分法提高适应度计算的效率。具体算法如图4所示。
图 4 二分法计算适应度
简单来说，二分字节区间，分别变异并计算区间适应度值：如果属于当前段的字节变异导致适应度低于阈值(与验证检查无关)或段的大小已足够小(精确到单字节)，则将该段中所有字节设置为相同的适应度；否则继续二分，直到识别出与验证检查相关的字节。每轮二分法中，Truzz最多能够在一个变异输入中处理一半的字节，因此是一种高效的字节适应度分配计算方法。
可以用图3上半部分为例，较为形象地说明二分法。被选择的种子为03AC，共四个字节。在字节分析阶段，首先对前两个字节03进行变异，生成新输入3AAC。图中可以看到变异前后种子执行路径没有改变，故前两个种子适应度为0，肯定低于阈值。而对后两个AC变异后生成新输入03E1，执行路径明显缩短，计算出较大的适应度，因此继续对该部分字节进行二分。按照相同方法，Truzz将AC字段分为A和C两部分，推断出最后一个字节C与验证检查相关。基于二分法，Truzz只需要进行约
（3）字节变异概率
为了保护与验证检查相关的字节，Truzz会根据适应度为每个字节分配变异概率，决定是否变异当前字节，以小概率对验证检查相关的字节进行变异，尽可能减少执行错误处理代码导致进程提前终止的情况，提高模糊测试效率。概率计算公式如下：
从计算公式可以看出，字节适应度越大，变异概率越小。同时，Truzz设置了一个概率下界
3 种子优先级
根据上文研究，对于执行路径包含更多未发现的新边的种子，给予其更高的优先级可能会进一步提高代码覆盖率。因此，Truzz根据新发现的执行路径中的新边数对每个种子进行优先级排名，新边的数量越多，选择对应种子的优先级越高。Truzz会在模糊测试过程中动态地对每个种子的优先级排名进行更新，例如以AFL为框架的模糊器，Truzz会在每一轮fuzz_one后更新下轮模糊测试队列。具体算法如图5所示。
图 5 种子优先级算法
该算法的重点是如何确定新边数量。Truzz会初始化一个位图
四、 实验设计及结果
（一）实验目标
实验阶段主要通过回答以下三个问题来验证Truzz的性能：
01
RQ1：字节分析在引导更多生成的输入进入函数功能代码方面是否有效？
02
RQ2：该框架提高模糊测试效率的效果如何？
03
RQ3：该框架可以（唯一）发现多少bug？
（二）实验设置
本实验在NEUZZ、GreyOneFTI、AFL、AFLFast、MOPT、FuzzFactory六个模糊器上集成Truzz，并将其性能与相应的原模糊器进行对比。在8个目标程序运行每个模糊器24小时，重复实验5次。需要注意的是，NEUZZ和GreyOne是基于推理的模糊器，可以推断字节约束关系解析约束。测试目标程序如表1所示。
所有实验的环境都是Ubuntu 18.04、Intel(R) Xeon(R) Gold 6230R CPU与4个NVIDIA GeForce RTX 2080 Ti gpu。
表 1 目标程序
（三）具体实验
1 RQ1：字节分析的有效性
Truzz使用字节分析识别与验证检查相关的字节，更少地更改与验证检查相关的字节，因此Truzz严重依赖于字节分析的准确性。
本实验将分析Truzz字节分析的准确性：手动分析实验中使用的5个程序，标记这些程序中所有的错误处理路径，程序包括nm、objdump、readelf、size、strip。分析方法上，扫描每个错误函数的定义，并检查它们是否可以通过返回错误代码或空指针触发错误。每次生成和执行变异输入时，需要确定输入是否执行错误处理路径，并在模糊处理期间计算这些路径数量。如果一个输入通过所有的验证检查并没有触发任何错误处理代码，则被认为是有效的。
为避免种子优先级对结果的影响，本实验只使用字节分析实现Truzz，以NEUZZ和TRUZZ(NEUZZ)为例说明字节分析准确性。实验结果如表2所示，TRUZZ(NEUZZ)生成的有效样本平均比NEUZZ多16.14%，其中nm和objdump提升效果最为明显。
表 2 字节分析有效性实验对比
实验表明，在相同的实验条件下，Truzz相比原模糊器可以产生更多有效样本。
2 RQ2：代码覆盖率发现
在八个程序运行两个版本模糊器，持续24小时(5次)，利用AFL的AFL-showmap计算代码覆盖率，比较边覆盖率。如图6所示，除tiff2bw和tiffsplit，配置Truzz的模糊器实现了更好的边覆盖。
图 6 不同模糊器针对8个程序运行24小时的边覆盖
其次，比较配置Truzz的模糊器和原模糊器的新边发现数。如表2所示，配置Truzz的模糊器发现的新边比原模糊器平均多24.75%。然而，在Truzz中分别进行字节分析和种子优先级排序实验，发现字节分析对于性能的提高只对基于推理的模糊器较为有效，如表4所示。
表 3 不同模糊器运行24小时的发现新边数
表 4 字节分析和种子优先级排序分别对新边发现数的影响
实验表明，Truzz可以显著提高覆盖率和新边发现数，且字节分析更适合基于推理的模糊器（如NEUZZ和Greyone）。
3 RQ3：bug发现
本实验比较配置Truzz的模糊器和原模糊器发现真实程序的bug的能力。使用GDB和afl-collect分析模糊器发现bug的数量：
01
使用afl-collect去除无效crash样本，实现去冗余。
02
使用gdb手动分析每个bug的程序逻辑，删除具有相同根源的bug。
表5显示了在真实程序中发现unique crash（在5次运行中累计）的数量，原模糊器和配置Truzz的模糊器分别在四个应用程序发现10个和13个crash，剩下四个程序中，所有模糊器在24小时内无法识别出漏洞。
表 5 不同模糊器发现bug的数量
实验表明，配置Truzz的模糊器发现bug的能力优于原模糊器，在实验中识别了8个目标程序的13个crash，其中6个是原模糊器无法识别的。
五、 总结
本文主要针对CGF优化这一研究目标，利用路径转换间的差异，识别能够探索更多新边的种子以及种子中与验证检查相关的字节，改进字节调度和种子优先级排名，实现了CGF性能的优化。然而，Truzz存在一定的局限性，这些局限性主要存在于字节分析这部分，有以下两点：
01
字节分析在模糊器性能的提升上对基于推理的模糊器更起作用，对普通的以AFL为框架的模糊器的性能提升效果并不好。第一个原因是基于推理的模糊器能够选出“有趣的输入”进行变异，这在一定程度上避免了初始字节可能已经指向错误处理代码的情况，而普通的模糊器可能存在初始输入直接执行错误处理代码，影响字节分析的问题。第二个原因是以AFL为框架的模糊器在字节分析上依赖于确定性阶段的bitflip变异，目前研究已经表明确定性变异本身性能就不如非确定性变异，进入确定性阶段会调用其他变异方式，影响模糊测试过程的效率。
02
字节分析仅仅根据路径长度来判定与验证检查相关的字节。然而，如果程序在错误处理代码具有复杂逻辑，这种方法可能无法正确识别与验证检查相关的字节。
参考文献
1.
Zhang K, Xiao X, Zhu X, et al. Path Transitions Tell More: Optimizing Fuzzing Schedules via Runtime Program States[J]. arXiv preprint arXiv:2201.04441, 2022.
2.
Michal Zalewski. American Fuzzy Lop (2.52b). http://lcamtuf.coredump.cx/afl, 2019.
3.
She D, Pei K, Epstein D, et al. Neuzz: Efficient fuzzing with neural program smoothing[C]//2019 IEEE Symposium on Security and Privacy (SP). IEEE, 2019: 803-817.
4.
Gan S, Zhang C, Chen P, et al. {GREYONE}: Data flow sensitive fuzzing[C]//29th USENIX Security Symposium (USENIX Security 20). 2020: 2577-2594.
5.
Lyu C, Ji S, Zhang C, et al. {MOPT}: Optimized mutation scheduling for fuzzers[C]//28th USENIX Security Symposium (USENIX Security 19). 2019: 1949-1966.
6.
Padhye R, Lemieux C, Sen K, et al. Fuzzfactory: domain-specific fuzzing with waypoints[J]. Proceedings of the ACM on Programming Languages, 2019, 3(OOPSLA): 1-29.
原文始发于微信公众号（FuzzWiki）：TRUZZ：利用路径转换之间的差异优化覆盖率引导灰盒模糊测试丨技术进展
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论