模糊测试中的bypass check研究
在现代二进制漏洞挖掘技术中，应用最为普遍的就是模糊测试技术。其基本原理在于， 每次将一个输入投入到程序中运行，看该程序是否会产生错误。理论上来说，只要运行的次数够多，将整个程序状态空间遍历一遍，就一定可以覆盖所有的路径和状态，并发现程序中潜在的错误和漏洞。但是实际应用中，在fuzz引擎自动探索状态空间的过程中会遇到很多问题，其中一个很重要的问题就是如何绕过各种各样的check，绕过check的能力也成为了衡量模糊测试引擎性能的重要指标。本文主要就模糊测试技术中的bypass check问题进行探讨。
以AFL[1]为代表的传统灰盒模糊测试框架，存在的一个主要问题就是绕过各种各样check的能力很差，这也直接导致了这些模糊测试框架在代码覆盖率上表现不佳（因为只有绕过各种各样的check才能覆盖到新的代码空间）。在真实的应用程序中，check的形式多种多样，check的结果往往也会直接影响控制流跳转的情况。下图1是一种简单的魔术字节检查，这种检查在真实的应用程序中是非常普遍的。
图 1 典型check条件
AFL这类传统灰盒模糊测试框架对于变异过程没有直接的指导的，而是通过遗传算法来筛选优秀的测试用例，从而间接影响变异。所以这类灰盒模糊测试框架的变异过程本质上还是随机的，缺乏方向性和智能性，并不能根据程序自身的特点来做有针对性的变异。因为这一原因，即使是图1所示的这种简单的魔术字节检查，AFL要生成能够绕过这一检查的样本也需要非常大的开销。因此，AFL等框架探索深层代码空间的能力往往较差（越深的代码空间往往意味着要通过越多的条件检查）。这种结果是由fuzzer的变异方式简单与真实程序的check条件复杂共同导致的。
针对模糊测试过程中如何高效bypass check的问题，许多研究者都进行了研究并提出了各种优秀的思路来解决这一问题。本文接下来将这些方法分成三类来进行介绍。
基于符号执行的方法的思路是将从起始点到达指定代码区域的所有的check分支条件都提取出来，做一层抽象，提取符号值，把这些条件当做约束，再通过求解器来求解得出最终的可以到达指定代码区域的具体值。
符号执行的优势在于，能够高效的找到特定的输入以覆盖到指定的代码。但是其存在的主要问题是路径爆炸和约束不可解。
发表于NDSS2016的Driller[4]缓解了符号执行的问题，并在DARPA CGC竞赛中取得了很好的成绩。其基本思路是将AFL和angr[2]（符号执行框架）相结合，并不对所有的分支条件都做符号执行，而是周期性使用符号执行来求解那些卡住路径的约束。这样一来，就可以大大提高符号执行的效率。
发表于USENIX Security2018的QSYM[6]为了缓解符号执行的问题，用x86指令来重新实现一遍angr，从而加速符号执行求解速度，其整体框架如图2所示。QSYM使用部分符号执行的思路，不将程序执行路径上每个约束都进行求解，而是选取部分约束进行求解。这样做的好处在于可以极大地减少符号执行求解失败的情况。同时，由于模糊测试其实并不是一定需要完全精确的输入才能到达目的代码块，所以模糊测试过程中可以通过在部分求解的基础上进行变异来最终达到目的代码块。
图 2 QSYM架构图
总结来说，Driller以及QSYM这两种方法核心的思路就是提高符号执行的效率。但是问题在于，尽管这样，还是不能适应现实世界中的代码规模较大的程序。
发表于NDSS2017的VUZZER[8] 利用传统的动态污点分析技术，通过hook比较指令，获得输入的指定偏移和某个约束条件的对应关系，从而解决了在哪里变异，怎么变异的问题，极大提高了变异的目标导向性。
其主要缺点在于：
1.全部变量都跟踪，导致很多不必要的开销。
实际上很多变量不涉及到条件分支。
2.变异不够精确。
采用了将输入部分进行直接操作的办法来变异，比如，直接对input的某一偏移范围进行字节删除、替换或者插入。但是实际情况中，还存在很多非直接的操作，比如编码。
为了解决这些问题，发表于NDSS2019的redqueen[7]提出了input-to-state的思想。
图 3 redqueen的变异规则
如图3所示，Redqueen通过hook比较指令，得到一系列的变异规则。
这个变异规则将在模糊测试的变异阶段应用。这个方式相当于间接的污点分析得到输入偏移与比较指令操作数的对应关系，但是这个方法只关注于输入点和比较指令两个点，也就是input-to-state的思想。因此，减小了传统动态污点分析的开销，大大提高了分析的效率。
此外，redqueen还加入了编码机制，在获得了变异规则以后，可以通过一些常见的编码，对输入进行处理，比如大小端字节序、16进制编码、无符号与有符号转换、base64等，进一步提高了变异的适用性。
同时，为了减少应用变异规则时替换过多的输入，采用了着色机制，来增加输入中的随机字节数。效果相当于对输入偏移进行了一次编号，做替换时就可以不需要每个都替换，只需要替换指定编号的匹配输入即可。
redqueen的主要缺点在于：
1.没有直接地考虑偏移位置，而为了弥补这一缺点而采用的着色阶段的开销又很大，所以不够高效。
2.没有考虑到间接复制问题。除了常见编码以外，还存在很多变量经过某些操作后的比较。
发表于USENIX Security2020的greyone[5]在此基础上又做了一些提升。
相比较于redqueen和vuzzer，greyone用优化的字节级污点推断（FTI）来推断偏移依赖关系，解决了where/what问题，也就是在哪里变异、怎么样变异。具体来说，这个FTI就相当于尝试阶段。在这个阶段中，每次只变异一个字节，并监控哪个check变量变了，从而获得input[offset]->value的依赖关系。这个方式解决了隐式流和外部调用的问题，不需要人工指定污点传播规则，如图4所示。
图 4 FTI 工作模式
此外，为了引导变异出符合约束条件的输入，greyone新设计了一种模式，即一致性导向模式。这种模式直接在遗传算法中将筛选种子的策略由覆盖率导向变为一致性导向。所谓一致性，通俗来讲就是在执行比较指令时，两边操作数的一致程度。并由操作数一致性，生成基本块一致性，并最终生成总体的种子一致性，通过保留一致性高的种子，使得模糊测试过程最终向目标点收敛。Greyone在一致性提高很少或者种子分配过多能量的情况下又切换回传统的覆盖率导向模式，从而获得一个总体的平衡。
Laf-intel-pass[3]将magic bytes多字节比较条件，转换为嵌套的单字节比较条件。如下所示：
if(!strcmp(directive, "crash")) {
programbug()
}
代码1 多字节比较
if(directive[0] == 'c') {
if(directive[1] == 'r') {
if(directive[2] == 'a') {
if(directive[3] == 's') {
if(directive[4] == 'h') {
if(directive[5] == 0) {
programbug()
}
代码2 单字节嵌套比较
其思路是在llvm编译过程中，加入pass，从而在编译时就将复杂条件分解为简单条件。对于这种简单条件，AFL这类灰盒fuzz可以很容易满足最外层条件，并且由于其覆盖率引导，满足最外层的种子会被保留，进而继续往深处引导，一定程度上解决了复杂条件问题。但是缺点也很明显，只能顺序引导随机变异，并且变异模块不知道应该在哪里变异，也不知道应该变异成什么，变异不够高效。
发表于S&P2018的angora[9]把约束求解问题近似转化为最优化问题，用梯度下降搜索最优解。通过字节级污点跟踪获得输入结构（size和offset）和依赖关系。（哪几个字节一起使用，即作为一个变量。方便后续做梯度下降）。
具体来说，约束转化如下图所示。通过将两元比较的约束满足转化为一元函数，实现梯度下降。
图 5 二元比较转化为一元函数
求导过程为给定输入分别运行两次，其中第二次输入在第一次的基础上，对某个污点分析推测出来的变量加一个比较小的数，来获得一个函数值的差，进而用函数值的差比上变化量（一个比较小的数）来近似代表其梯度。如下图所示。
图 6 近似梯度和导数计算
Angora的问题在于，不一定收敛，可能落入局部最优。并且梯度计算过程中，可能由于两次运行走的路径不一样导致无法计算梯度。另外就是传统污点分析中，每个变量都跟踪导致的高开销问题。
总结
本文对bypass check问题以及现有的代表性解决思路进行了介绍。Check难以通过的核心原因在于，传统灰盒模糊测试的变异方式简单，而实际应用场景中，各种check规则，各种约束条件又非常复杂。这两者间的矛盾导致了很多分支难以到达，覆盖率始终难以提高。而对此，解决方式就是一方面想办法减少check复杂性，如分解复杂约束。另一方面，想办法减少变异的随机性，比如获取更多的关键信息来指导模糊测试的变异，而不是盲目的在一大片搜索空间里随机地搜索。
参考文献
[1]american fuzzy lop[EB/OL].[2021-08-07] .https://lcamtuf.coredump.cx/afl/.
[2]angr[EB/OL].[2021-08-07] .https://angr.io/.
[3]Circumventing Fuzzing Roadblocks with Compiler Transformations – laf-intel[EB/OL].[2021-08-05] .https://lafintel.wordpress.com/2016/08/15/circumventing-fuzzing-roadblocks-with-compiler-transformations/.
[4]STEPHENS N, GROSEN J, SALLS C, et al. Driller: Augmenting Fuzzing Through Selective Symbolic Execution [C]//Proceedings 2016 Network and Distributed System Security Symposium. San Diego, CA:, Internet Society, 2016.
[5]GAN S, ZHANG C, CHEN P, et al. GREYONE: Data Flow Sensitive Fuzzing [C]//29th USENIX Security Symposium (USENIX Security 20). USENIX Association, 2020 : 2577–2594.
[6]YUN I, LEE S, XU M, et al. QSYM : A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing [C]//27th USENIX Security Symposium (USENIX Security 18). Baltimore, MD:, USENIX Association, 2018 : 745–761.
[7]ASCHERMANN C, SCHUMILO S, BLAZYTKO T, et al. REDQUEEN: Fuzzing with Input-to-State Correspondence [C]//Proceedings 2019 Network and Distributed System Security Symposium. San Diego, CA:, Internet Society, 2019.
[8]RAWAT S, JAIN V, KUMAR A, et al. VUzzer: Application-aware Evolutionary Fuzzing [C]//Proceedings 2017 Network and Distributed System Security Symposium. San Diego, CA:, Internet Society, 2017.
[9]CHEN P, CHEN H. Angora: Efficient Fuzzing by Principled Search[C]//2018 IEEE Symposium on Security and Privacy (SP).2018 : 711–725.
微信:
FuzzWiki
原文始发于微信公众号（FuzzWiki）：fuzzing check分支概述
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论