前言
熟悉pwn、漏洞挖掘等领域的同学,对于AFL应该不会陌生。目前最新一代的活跃在漏洞挖掘一线的各种Fuzzer,大多都是基于AFL改进的,或是借鉴了AFL的设计思想(准确来说应该还有libfuzzer和hongfuzz,不过核心思想上这三者是差不多的)。所以AFL比Peach等上一代Fuzzer有何优势,或者换句话说,AFL的核心的设计思想是什么,让它在现在有如此大的影响力?
如果忽略掉一些细节,那么AFL的工作流程可以近似的用上图表示。简单来说,AFL把一堆测试用例经过变异后生成一些新的测试用例,把这些新的测试用例输入到被测试程序中执行。然后保留那些让代码覆盖率增加的新的测试用例,用于继续变异,如果不人为中断的话,这个过程会一直持续下去。当受测试程序崩溃后,就证明触发了漏洞,则保留触发了崩溃的测试用例。
再进一步的抽象来看,这个过程的核心就是遗传算法的一个应用。即AFL根据初始的测试用例不断变异产生一些新的测试用例,然后保留下“较好”的测试用例继续变异。在遗传算法中,评价某个新生成个体的好坏的标准为适应度函数(fitness function),在这里就是有没有增加程序的代码覆盖率。在这个适应度函数的指引下,AFL会不断产生新的测试用例,去执行那些还未执行过的代码。
由于在Fuzz过程中仅仅收集了程序的代码覆盖率信息,这种介于不收集程序信息与完全收集程序信息之间的模式也被称为灰盒模糊测试,与黑盒、白盒模糊测试相对应。这种应用了遗传算法的灰盒模式也让AFL等新一代Fuzzer战胜了Peach等上一代黑盒Fuzzer,成为了现在进行模糊测试的主流方法。
但是成功不意味着完美,AFL所导向的更多的代码覆盖率可以与更多的漏洞画等号吗?仔细想一想,似乎可以划等号又不完全可以划等号。
更多的代码覆盖率≈更多的漏洞
一般来说,更多的代码覆盖率是可以带来更多的漏洞的。很显然,那些未执行过的地方肯定暗藏着还未触发过的漏洞,如果没有效果的话这种以代码覆盖率为适应度函数的做法也不会有这么广泛的应用。
但是有些漏洞的触发并不意味着更多的代码覆盖率。例如这个走迷宫的小游戏,迷宫的地图存放在二维数组maze中,当x与y的坐标到达迷宫出口时,才会触发bug。如果让AFL来进行Fuzz,无论这个循环执行多少次,也不会带来覆盖率的增加。所以,以代码覆盖率为适应度函数是存在问题(不够完美)的。
实际上,最完美的适应度函数应该是程序状态的覆盖率。这里的程序状态(state)的具体定义为内存与寄存器的一种配置(configuration)。即当程序运行时,程序所在的内存中的数据、寄存器中的值都不断在变化,但是当确定某一时刻时,这些数据和值都是一定的,而这些值就确定了一个程序状态。进而,程序的状态空间就是程序可能处于的所有可能状态的集合。不难理解,当我们探索完整个程序的状态空间时,程序中的bug必然会被触发,因为bug本质上就是一个程序出错时的状态。
但是在实际应用中,使用是否触发了新的程序状态作为Fuzz中的适应度函数是基本不可能的。因为程序状态是一个十分细粒度的描述方式,我们需要探索的状态空间将十分的巨大,几乎不可能在可接受的时间内探索完毕。所以,人们使用了代码覆盖率——程序状态的一个子集作为适应度函数,来近似的模拟程序状态空间。这样做虽然可以大大减少我们需要探索的状态空间,但是很显然,也会使我们探索不到一些程序bug。
解决方案
明确了问题的所在,我们就可以开始思考如何为这个不完美的程序覆盖率适应度函数来打上一些补丁。我个人浅显的将学界对这一问题的解决分为两个流派。
第一种流派是希望提出一个比较好的解决方案,一劳永逸的解决这个问题,主要代表为IJON[1]与FuzzFactory[2],二者的实现方式几乎一致。他们认为,使用覆盖率作为适应度函数效果很好,可以遍历很大一部分的程序状态,应当保留。而对于那些剩余的存在bug的程序状态,应该引入人工,具体问题具体分析解决。他们的做法是设计一种注释脚本,来方便安全人员来快速的实现一个特定的适应度函数,来引导Fuzzer快速达到那些存在bug的程序状态。
举例来说,对于上图所描述的迷宫小游戏,在IJON的解决方案下,当人工分析后,可以引入这样一条注释语句,即当有一个新的x与y的组合时,保留当前的种子。其中实现的底层原理本质上也是借助了AFL内部的bitmap机制,可以简单理解为将x与y取个hash,然后将bitmap的hash值的那一位置1。当然这里肯定还有一些细节,比如hash函数的实现,以及bitmap冲突的问题,这里就不再深究了。这样做的效果就是,当一个变异出来的新种子产生了一个新的x与y的组合时,等同于触发了一个新的代码覆盖率,然后会被保留下来继续变异。所以就会指导Fuzzer一步步的探索完所有的x与y的组合,直到走完迷宫。
当然,在具体的论文实现里,作者还给出了许多种注释语句,可以满足不同情况下的不同需要。还有,虽然这里举例所使用的是IJON,但是FuzzFactory所提出的解决方案从思想上与原理上其实与IJON是大同小异。
第二种流派则是针对于特定的问题具体问题具体分析,提出一个针对性的适应度函数以指导Fuzzer来触发某种类型的bug,或是达到难以到达的代码路径。其中的一些解决方案虽然并不是从改进当前适应度函数缺陷的角度出发的,但实际上也是干的这件事情。
较为经典的就是对于魔数问题的解决,例如上图,在进行多字节比较时,由于中间状态并不触发新的代码覆盖率(即输入"MAGI1234"与“MAGICHD1"所触发的代码覆盖率相同),因而难以一下子在输入出变异出"MAGICHDR"这个字符串,所以难以通过这个比较。学界主流对这个问题的一种解决方案就是重新构造适应度函数,将比较时触发了新的中间状态的种子也保留下来,例如Steelix[3]、LAF-INTEL[4]、InsFuzz[5]等。
或者针对于算法复杂性漏洞,SlowFuzz[6]增加了指令数量与资源用量作为适应度函数,指引Fuzzer去产生占用资源更多,执行更多指令的输入;PerfFuzz[7]则增加了malloc语句分配字节数、I/O操作数以及cache misses或page faults数等适应度函数,来更好的引导触发算法复杂性漏洞。
其他的还有一些零散的研究,例如MEMFUZZ[8]这篇文章是增加了是否进行了新的内存读写的适应度函数,来Fuzz产生更多位置的内存读写。而AFL-HR[9]则是基于输入到触发漏洞的距离的适应性函数,来更快的触发堆栈溢出等漏洞。
尾声
在我个人看来,实现一个比较完美的普适性方案来解决代码覆盖率的缺陷问题,还是比较困难的,当前的解决方案已经比较完善了,但依旧离不开人工的参与。更多的情况下,还是需要针对于特定的程序或者特定的漏洞类型进行具体分析,去做更定制化的工作。那么我们对于这一问题,未来的研究中可以继续寻找归纳某类特定的程序或者漏洞,进而继续提出一种新的适应度函数来更好的Fuzz这类特定的程序或者更快的触发某类的漏洞。
最后,笔者才疏学浅,如本文能抛砖引玉,博君一笑,则不胜荣幸。倘若文中存在一些纰漏,还请各位斧正。
参考文献
[1] C. Aschermann, S. Schumilo, A. Abbasi and T. Holz, "Ijon: Exploring Deep State Spaces via Fuzzing," 2020 IEEE Symposium on Security and Privacy (SP), 2020, pp. 1597-1612, doi: 10.1109/SP40000.2020.00117.
[2] Rohan Padhye, Caroline Lemieux, Koushik Sen, Laurent Simon, and Hayawardh Vijayakumar. 2019. FuzzFactory: domain-specific fuzzing with waypoints. Proc. ACM Program. Lang. 3, OOPSLA, Article 174 (October 2019), 29 pages. DOI:https://doi.org/10.1145/3360600
[3] Yuekang Li, Bihuan Chen, Mahinthan Chandramohan, Shang-Wei Lin, Yang Liu, and Alwen Tiu. 2017. Steelix: program-state based binary fuzzing. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2017). Association for Computing Machinery, New York, NY, USA, 627–637. DOI:https://doi.org/10.1145/3106237.3106295
[4] https://lafintel.wordpress.com
[5] H. Zhang, A. Zhou, P. Jia, L. Liu, J. Ma and L. Liu, "InsFuzz: Fuzzing Binaries With Location Sensitivity," in IEEE Access, vol. 7, pp. 22434-22444, 2019, doi: 10.1109/ACCESS.2019.2894178.
[6] Theofilos Petsios, Jason Zhao, Angelos D. Keromytis, and Suman Jana. 2017. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS '17). Association for Computing Machinery, New York, NY, USA, 2155–2168. DOI:https://doi.org/10.1145/3133956.3134073
[7] Caroline Lemieux, Rohan Padhye, Koushik Sen, and Dawn Song. 2018. PerfFuzz: automatically generating pathological inputs. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2018). Association for Computing Machinery, New York, NY, USA, 254–265. DOI:https://doi.org/10.1145/3213846.3213874
[8] N. Coppik, O. Schwahn and N. Suri, "MemFuzz: Using Memory Accesses to Guide Fuzzing," 2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST), 2019, pp. 48-58, doi: 10.1109/ICST.2019.00015.
[9] Raveendra Kumar Medicherla, Raghavan Komondoor, and Abhik Roychoudhury. 2020. Fitness Guided Vulnerability Detection with Greybox Fuzzing. In Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops (ICSEW'20). Association for Computing Machinery, New York, NY, USA, 513–520. DOI:https://doi.org/10.1145/3387940.3391457