Fuzz入门

先以一篇综述学习Fuzz的基本流程
《模糊测试技术综述》 任泽众 《计算机研究与发展》
本文总结了Fuzz工作流程,并将其作为行文脉络,详细介绍了各个阶段中的相关技术。
重点介绍了AFL及其改进研究,简要介绍了Fuzz的多种应用场景,以及反Fuzz和Fuzz+ML等新的研究方向。

image-20211209143254411

预处理

搜集目标相关信息(输入格式、内部结构),并制订模糊测试的策略,为监控目标在测试中的运行状态做必要的准备。
通常依赖于插桩、符号执行以及五点分析这类程序分析技术。

挑战:使用什么样的程序分析技术,对目标内部达到什么程度的了解。

分析技术与信息获取

插桩

向目标代码中的合适位置添加预设好的代码,获取程序的静态或动态执行信息,如程序的抽象语法树、覆盖率和函数内变量取值。

静态插桩

在源码或者中间代码的编译过程中进行插桩

通过GCC在汇编语言上插桩,通过LLVM在生成的中间语言上插桩。

节省时间、速度快,依赖源代码

动态插桩

利用QEMU等模拟技术进行插桩,获取程序的运行时信息。

资源开销大。

符号执行

将程序行为的推理归结为逻辑领域的推理,通过构建一个表示程序执行的逻辑公式,可以同时推断一个程序在不同输入上的行为。该方法可以是模糊测试获得较好的覆盖率,并且可以深入到程序深处探测漏洞。

静态符号执行

通常会因为循环和递归的存在陷入到路径爆炸中,还会因为hash之类操作的存在导致约束求解失败。

动态符号执行

针对路径爆炸和非线性约束求解失败的问题,更多使用的是动态符号执行。

动态符号执行通过对程序进行实际执行符号化执行,维护程序的实际状态符号化状态,通过将难以求解的约束替换为实际值,缓解静态符号执行的问题,并按照深度优先的搜索策略对目标程序进行了探索。

问题
由于程序分支的存在,路径爆炸的问题仍然存在。程序越复杂,路径爆炸问题越严重。一种解决办法是使用启发式搜索优先探索重要的路径。
使用实际值替换方法解决了部分静态符号执行无法解决的约束求解问题,但是可能会丢失部分路径,造成探索结果不完整。
所有的符号执行技术都受限于约束求解方法的能力,比如如何处理取余操作这类的非线性约束,仍然是符号执行面临的挑战。

污点分析

五点分析技术会观测程序中哪些数据受到预置污染源(如输入)的污染,目的是跟踪污染源和汇聚点(如敏感数据)之间信息流。

将污点分析应用到模糊测试中,并降低其资源消耗是最近的重要研究方向。

静态污点分析

获取程序控制流图、抽象语法树等信息,依据数据流以及依赖关系精选污点分析。
静态污点分析也会有路径爆炸的问题,而简化后的污点分析可能有过度污染的问题。

动态污点分析

在程序实际执行的过程中,利用程序的动态执行信息进行污点分析。
动态污点资源代价大,分析可信度更高,但是检测结果是否全面取决于污点分析对程序的覆盖情况。

其他程序分析技术

面向不同场景的模糊测试研究

IoT、内核、Android、USB、蓝牙协议、算法复杂度……

模糊测试在预处理阶段的类型划分

黑盒模糊测试

又称输入输出驱动的测试、数据驱动的测试,不能对目标内部状态以及结构进行分析、只能获得输入数据等与内部无关的信息。
无法跟踪目标内部的执行状态,只能通过检测目标的输出数据,对目标的状态进行判断。
适用于输入数据高度结构化的目标,以及复杂且难以分析的目标,在网络、文件、内核以及IoT模糊测试上都是重要应用。

意义:不是所有目标都是开源的;黑盒测试工具设计简单,开发和检测速度快。

问题:由于没有目标内部信息,会生成大量无效输入,导致测试的覆盖率相对偏低,检测生成漏洞的能力有限。

白盒模糊测试

可以获得充足的目标内部信息,通常采用符号执行的方法。
可以生成高质量输入数据,在覆盖率以及程序的深层漏洞检测上有更好的表现。
但是在实践中,仍然有路径爆炸的问题,同时伴有大量资源消耗,影响效率。

在不影响模糊测试效率的前提下,如何获取详细的目标内部信息,是一个重要的研究方向。
Driller: 使用AFL检索程序浅层漏洞,当AFL随机生成的输入无法深入探测程序时,转而进行符号执行。
QSYM: 使用动态二进制转换,将符号执行与本地执行紧密集成,实现了更为细粒度的指令集符号执行,解决了路径约束缓慢、甚至无法形成正确的约束的问题。
DigFuzz: 如何快速而准确地判断哪些程序的路径应该是符号执行技术,是一个混合模糊测试器的优化问题。DigFuzz量化了处理每条路径的困难程度,将难以通过随机种子到达的路径转而交给符号执行,较好地优化了在模糊测试中使用符号执行的策略。

灰盒模糊测试

灰盒模糊测试是白盒模糊测试的变体,只能获得部分程序内部信息。

思想:对程序内部进行细致而全面的分析,并不是获取良好测试结果的必要条件,仅依靠有限的与测试目标相关的信息,在配合良好的测试策略,仍然可以获得令人满意的测试结果。

灰盒模糊测试中,最重要的研究成果是AFL。
AFL通过在编译时插桩,搜集模糊测试中边缘覆盖率信息;使用进化算法将边覆盖率作为算法的适应函数,使得测试沿着边覆盖率增大的方向进行,极大改善了模糊测试效果。

小结

黑盒测试:轻量级测试工具,设计简单,测试速度快,但是检测效果不理想,难以进行深层探测。适用于难以进行内部探测的目标,以及开发和测试时间有限的场景。
白盒测试:重量级测试工具,更加智能,效果更好,能较好探测深层漏洞,但是开发和测试工作都跟为复杂且耗时。适用于可以分析内部结构的目标,以及对深层漏洞有较高检测要求的任务。
灰盒测试:没有明确的定位。从数据的角度,其“灰度”取决于利用的内部信息的多少;从设计的角度,体现了灰盒测试在检测能力与检测代价之间的平衡,达到最佳的检测效果。

AFL及其改进

image-20211209205542644 image-20211209205622938

实际测试环节

输入构造

首先获取一定数量的种子,随后确定种子的能量分配策略、种子的优先级以及种子的突变策略,最后根据这些信息获取大量的输入数据。

挑战:在尽量满足语法语义检查的情况下,短时间生成大量的输入,用以对目标做全面而深入的分析。
目前普遍的方法是:得到一个数据集S(Seed),然后根据S按照一定的策略进行一定册数的便宜,获得大量新数据I(Input),最后将I输入到被测试对象中进行测试。

为了获得足量的高质量输入数据,需要经过种子获取、种子筛选、种子突变三个阶段。

种子获取

直接使用准备好的高质量数据集、通过模型生成、按照策略从执行过的数据中选取。

挑战与研究方向
无目标语言的语法时,如何生成有效数据;
面向特定的场景和目标,要有针对性的生成方法;(FANS for Android)
直接生成模糊测试模型;
按照策略从执行过的输入数据中选取作为种子;(AFL的进化算法及其改进)

种子筛选

种子的能量分配

对种子池中的备选种子划分权重,以确定每个种子要用来生成多少输入,也即一个种子的能量。

在AFL中,没有考虑到程序不同执行路径频率上的差异,造成种子能量分配不合理。
具体来说,模糊测试进行一段时间后,部分难以到达的路径只有少数种子能够到达而执行频率过低,这些种子显然需要更多的能量。AFL在这方面的缺陷,导致低频路径上的漏洞需要更多的时间才会被模糊测试出来。

改进方法:
引入马尔科夫链,使得更倾向于访问低频区域。(AFLFast)
引入多臂老虎机模型,使用基于平均损耗的自适应能量分配策略,有效降低能量损耗,在有限时间内实现了覆盖率最大化。(EcoFuzz)
使用基于模拟退火的能量调度方法,逐渐将能量分配到距离目标更近的种子上,实现对目标程序给定位置的模糊测试。在探测给定目标程序上取得了更好的效果,但是可能遗漏潜在的漏洞。(AFLGo)
为克服这个问题,Hawkeye使用静态分析技术,全面收集与目标程序位置相关的调用图、函数以及基本块层面的距离信息;再使用与AFLGo相同的基本块路径距离和覆盖函数相似度这两个指标,指定能量分配策略。对应覆盖函数相似度越大、基本块路径越小的种子将会被分配到更大的能量,产生更多的测试数据。(Hawkeye)

AFLFast的能量分配策略不能提高模糊测试能力极限,而是缩短到达极限的时间。
AFLGo和Hawkeye的能量分配策略是为了引导模糊测试的方向,而不能提高覆盖率。

种子的优先级

种子的优先级决定了模糊测试从种子池中选择种子的顺序。

AFL引入进化算法,使用适应度函数对输入进行评估,选取最佳输入放入种子池。种子池实质上是一个队列,种子按照入队顺序进行测试,一段时候后,队列内种子不再变化。(AFL)
AFLFast不在严格遵循FIFO队列策略,而是适当提升较少被执行、能量较低的种子的优先级,尽量平衡不同路径上的模糊测试密度。(AFLFast)
对于定向灰盒测试,Hawkeye会根据种子是否出发新的执行路径、种子与目标种子的相似度、种子是否包含目标函数,将种子分配到3个等级的队列中。(Hawkeye)

值得注意的是,种子的长度是影响种子优先级的重要因素:
输入数据越短、内存占用越小、测试速度越快。因此,在覆盖率增加相同的情况下,短输入的优先级更高。
在维持覆盖率不变的情况下,AFL反复删除种子的不同部分,试图缩短种子的长度。

更多的种子筛选策略:Rebert et al., Optimizing seed selection for fuzzing. [USENIX]

种子突变

获得了大量种子和对应的能量分配策略以及优先级策略之后,接下来需要在突变策略的指引下快速生成大量输入数据。
变异策略直接影响生成数据的质量,保守策略呆滞覆盖率偏低,激进策略导致大量无效输入。

基本突变方式

比特翻转:按照一定的步长,连续反转几个比特位;在随即或特定的位置,反转固定宽度的比特位。
简单算数运算:按照8b的步长,依次按照8b、16b、32b的宽度,从头开始加减操作。(AFL)
覆盖:使用预设的值,将种子中的一些部分进行覆盖。
插入:使用预设的值,插入到种子种的一些位置。
删除:删除种子的某些部分。
拼接:选择2个差异较大的种子进行拼接。

黑盒突变

不依赖目标相关信息,按照随机突变策略对种子进行突变。
可以快速大量生成输入。(AFL)

导向型突变

程序状态导向型突变
通过程序分析技术,得到种子与程序状态的关系,以此指定突变策略,针对感兴趣的程序状态生成相应的测试数据。(VUzzer,Angora)

如何确定突变位置:通常使用污点分析技术,寻找输入与程序状态之间的关系,进而确定突变位置。(Angora,VUzzer,REDQUEEN)
输入格式高度结构化的目标:需要保证种子的结构,防止突变对关键字段的修改。Skyfire只选择种子的特定位置进行突变;ProFuzzer分析模糊测试中对发现漏洞至关重要的输入字段,进而调整策略重点突变这些字段。
覆盖、替换、插入时预置字段的有效性:LangFuzz分析目标语法和足量有效输入样例。

性能导向型突变
根据输入数据同模糊测试评估指标的关系制订突变的策略。

AFL在进行连续字节翻转时,会衡量每个字节对覆盖率提升的程度。如果没有提升,则认为该字节对覆盖率提升无意义。据此,获得一个effectmap,用于保存种子中所有字节的有效性(0或1),以此确定是否进行突变。

输入选择

尝试通过提前过滤掉无效的输入数据,以节省模糊测试的时间。
(似乎这个环节适合使用机器学习技术来完成模式识别任务)

以FuzzGuard为例,Zong Peiyuan et al., FuzzGuard filtering out unreachable inputs in directed grey-box fuzzing through deep learning. [USENIX]

FuzzGuard使用机器学习技术,预测新产生的输入能否使得程序执行到有漏洞的代码处,删除预测为不可达的输入。论文中还讨论了机器学习应用到Fuzz中需要面对的一些问题:数据集不平衡、突变后种子执行路径的随机性。

评估

设计合适的实验,依照评估指标对模糊测试进行评估。
合适的评估指标,可以反映出模糊测试的真实的执行结果,话可以反应模糊测试方法的实际性能。
一个合适的模糊测试实验需要选择合适的模糊测试方法作为对比、合适的对象作为模糊测试的目标、合适的重复测试次数和超时时间。

目前主要聚焦于覆盖率暴露漏洞平均时间

覆盖率

在测试过程中,对象被覆盖到的数目占总数的比例。
通常而言,高覆盖率更可能发现更多的隐藏漏洞,因此众多研究聚焦于覆盖率的提升。

AFL使用上下文无关的边覆盖率作为评估指标;
Angora使用上下文敏感的分支覆盖率作为评估指标;
VUzzer使用块覆盖率作为评估指标;

问题
如何完成对复杂程序的覆盖信息统计;(CollAFL)
一味提升覆盖率,可能导致在一些无漏洞的正常边块上浪费过多时间,更容易受到反模糊测试的影响;(TortoiseFuzz)
如何降低覆盖率统计工作的巨大开销;(UnTracer)

暴露漏洞平均时间

(AFLGo)
覆盖率这一指标是基于“覆盖率更高可能触发更多漏洞”的假设。
如果需要复现某个漏洞,且考虑到漏洞在代码中分布不均匀,单纯的覆盖率指标会导致测试在无关部分浪费资源。

验证实验设计

(Klees的4个标准)
[1]进行多次实验,并进行统计与检验,获取结果的分布;
[2]应该使用如CGC/LAVA等具有确定错误的测试集,或使用具有已知漏洞的程序作为被测试对象;
[3]应该尝试各种种子输入,如空种子;
[4]超时时间至少为24h,或者尝试不同的超时时间;

结果分析

模糊测试获得的结果无法被直接使用,需要对测试结果进行重现、复现、分析以及威胁性评估等工作,最终确定是否发现了有价值的漏洞。

模糊测试的挑战与机遇

反模糊测试

目前主流的模糊测试技术基于4个前提条件,反模糊测试也可以从这些条件入手:
[1]单次执行速度要足够快 ~ 低频路径插入延时代码
[2]模糊工具可以获得覆盖率的反馈 ~ 用无意义代码填充覆盖率图
[3]目标中的路径约束可以被符号求解 ~ 使用hash运算干扰混合执行,隐式数据传递
[4]崩溃可以被模糊工具检测到

相关文章:https://securitygossip.com/blog/2019/11/08/fuzzification-anti-fuzzing-techniques/

模糊工具集成

整合不同模糊测试工具,构造一个通用模糊测试平台。

与机器学习结合

有效输入的模式识别

问题:数据源、数据集不平衡、性能问题。

其他发展方向

提高自动化程度

与虚拟机技术结合

测试效果的评估方案改进

一些问题

看了上述笔记,似乎对Fuzz有了大致的了解,但是细细一想,又好像没学到什么东西。
要不然先来回答以下问题:

插桩、符号执行、污点分析的具体实现原理是什么?有哪些优化工作?
clone下来AFL++的代码,再拿到一个样本,怎么上手跑一次Fuzz流程?
对于一些术语:覆盖率、路径、基本块、逻辑符号、约束条件等等,准确的定义是什么?

针对以上问题,我的计划:
继续看相关文献,对诸如符号执行、污点分析等技术,对着论文写笔记,学习理论知识。
打开入门实践课,开始动手实践。
打开Google,搜索相关术语的定义,或者去相关论文里面找。

基本块、路径和覆盖率

待添加

Welcome to my other publishing channels