FUZZ 论文总结(一)

前言

前天晚上失眠的时候想到最近自己虽然看了很多篇的论文,但是感觉只是看了就看了。昨天和sc聊天,他说他每看完一篇论文都会在论文的最开头写上总结,然后思考一会儿,这真是个好习惯,学习学习。
这里主要是整理下最近看的论文。

论文总结

1. Automated Whitebox Fuzz Testing

论文地址Automated Whitebox Fuzz Testing

总体概述:这篇论文很早,是2008年的。当时的研究现状是怎样让程序在测试的时候运行效率更高。采用的fuzzing策略都是向目标程序发送随机数据,但是这样的效率非常低,代码覆盖率也很低。这篇论文将符号执行结合进来,通过对程序运行时状态的分析,记录程序所走过的分支语句。在进行fuzzing过程中,通过上一步的分支选择,去指导修改测试样例,使程序下一次去执行另外一条分支,提高代码覆盖率。
总结:上面这个方法在理论上可以覆盖所有的代码,但是对于一些大型的程序,存在路径爆炸问题,所以做到覆盖到所有路径基本上是不可能的。还有就是符号执行的速度非常慢,fuzzing效率不高。并且上面的方法只有在有源码的情况下才可行,具有局限性。

2. Taint-based Directed Whitebox Fuzzing

论文地址Taint-based Directed Whitebox Fuzzing

总体概述:这篇论文将动态污点分析技术结合进来。该工具叫BuzzFuzz,它关注的不再是路径,而是输入数据,对于通常的fuzzing技术都是随机的变异输入数据的一些或全部字节。而BuzzFuzz通过动态污点分析,找到敏感点对应的输入数据,只对这些输入数据进步变异,可以提高fuzzing效率。
BuzzFuzz关注的是库函数入口点作为参数的函数和系统调用时所使用的寄存器和栈参数。首先执行一遍程序,分析出与所有函数入口点和系统调用相关的输入数据。最后FUZZ的时候只对这些字节进行变异,直到程序崩溃。
总结:BuzzFuzz也是只能对有源码的程序进行fuzzing测试,现在很多程序都是没有源码的,所以也是使用的范围比较小。还有就是一些大型的程序,会调用很多的库函数,那么就会有很多地方会被标记为敏感点,也会有很多的输入数据与敏感点对应的,这样其实也不能很好提高触发漏洞的效率。

3. TaintScope: A Checksum-Aware Directed Fuzzing Tool for Automatic Software Vulnerability Detection

论文地址TaintScope: A Checksum-Aware Directed Fuzzing Tool for Automatic Software Vulnerability Detection

总体概述:很多程序会计算输入数据的校验和,但是传统的fuzz技术产生的测试样例不能通过校验和检测,也就不能执行后面的逻辑,而且很多漏洞都是存在校验和检测逻辑后的。这篇论文做的工作是检测出校验和的位置,并且自动修改测试样例,通过校验和检测。
寻找校验和的具体做法分为两步:第一步首先输入多个能通过校验和的合法样例,将所有执行“是”分支的输入放入集合PO,所有执行“否”分支的跳转语句放入集合P1;第二步是输入多个能够通过校验和的非法样例,将所有执行“是”分支的输入放入集合PO‘,所有执行“否”分支的跳转语句放入集合P1’。然后利用(P 1 ∩ P 0 ′ ) ∪ (P 0 ∩ P ′ )找到检查校验和的位置。

总结:这种方法可以提高fuzzing测试的通过效率,因为传统的fuzzing技术都是随机FUZZ,很多的测试样例都不能通过校验和,所以导致后面的代码逻辑根据不能fuzz到,更不用说去发现那些隐藏的漏洞了。

4. Probability-Based Parameter Selection for Black-Box Fuzz Testing

论文地址Probability-Based Parameter Selection for Black-Box Fuzz Testing

总体概述:这篇论文介绍了一种将基本统计理论应用于参数选择问题并自动选择种子文件和范围的算法,来提高fuzzing测试的效率。对fuzzing做了抽象概括,主要侧重两个方面:第一测试样例应该选择怎样的初始种子;第二测试样例要怎样设定测试范围来提高质量。其中提出了两个抽象概念来量化测试样例的质量:致崩溃密度、种子集合质量。

总结:这篇论文是在12年出的,里面的测试步骤到现在有很多工具都是基于此的。

5. Fuzzing with Code Fragments

论文地址Fuzzing with Code Fragments

总体概述:这篇论文的主要工作是针对JS引擎等对于输入有较高语法要求的程序,传统Fuzz方法生成的测试样例基本无法通过JS引擎对语法的校验,因此需要能够稳定输出满足语法规范测试样例的Fuzz工具。目前对语法解析类软件的模糊测试面临的问题有:需要足够多common的数据能够通过检验;通过也需要足够多uncommon的数据能触发漏洞。这篇论文提出的工具名为LangFuzz。LangFuzz通过变异的方式生存测试样例,但是首先需要满足“common”的需求。其做法是收集大量的合法代码片段,并对这些代码片段进行分配,比如if,for语句等一定不能作为叶子结点在一棵语法树中,后面必须要有语句。在分类的过程中,不断的填充代码直到所有的叶子结点都合法,通过不断更新叶子结点,来生成新的代码片段。由于在生成新的片段都是合法代码,所以不会出现不能通过语法检测的问题。

总结:这篇论文对输入测试样例的语法的合法性考虑了进去,即保证了在测试的过程能被目标程序正确解析,能更好的出发隐藏在里面的漏洞。

6. Coverage-based Greybox Fuzzing as Markov Chain

论文地址Coverage-based Greybox Fuzzing as Markov Chain

总体概述:基于代码覆盖率的灰盒测试是一种不需要程序分析的随机测试方法,会将能执行新路径的测试样例重新放回语料库继续变异,但是大多数的测试样例都会去执行一些“高频”的路径,这篇论文提出基于马尔可夫链的模型,对代码中的路径进行评估,对“低频”路径也即难以到达的路径分配更高的权重,同时,降低“高频”路径的调度优先级。
计算代码路径权重的做法是:首先对程序程序进行静态分析,生成控制流程图(CFG);以每一个跳转分支为节点,生成马尔可夫链;对执行概率低的路径分配更高的权重,引导测试样例执行这些路径;同时降低一些高频路径的权重,使得“高概率到达同时权重低”、“低概率同时权重大”的这两类路径在调度测试样例变异时能达到平衡。

总结:这篇论文里用到了静态分析来得到程序的控制流图,但是对于一些大型的程序,控制流图并不容易获得。在分析跳转概率的成本也很高。

7. Driller: Augmenting Fuzzing Through Selective Symbolic Execution

论文地址Driller: Augmenting Fuzzing Through Selective Symbolic Execution

总体概述:这篇论文主要针对两个问题提出了解决方法。问题一、仅仅变异测试样例难以执行到深层代码;问题二、通过符号执行进行探索新路径会过于费时。这篇论文中提出的解决方法是,首先使用传统的模糊测试框架对代码深度为n的部分进行模糊测试,在测试样例达到某个阈值并且代码深度没有变化时,执行下一步。首先对当前代码层进行符号执行,寻找能够到达下层代码的路径,找到新路径后根据新路径的约束条件修改测试样例,然后按照第一步进行fuzz。

总结:对程序中所有的路径进行符号执行速度会非常慢。所以只是在当前测试样例无法发现测试样例的情况下,才去采用符号执行去探索新路径,这样效率会比用符号执行去发现所有的路径要高效的多。

8. Learn&Fuzz Machine Learning for Input Fuzzing

论文地址Learn&Fuzz Machine Learning for Input Fuzzing

总体概述:这篇论文针对现在规范的文件格式越发复杂,如pdf文件可能存在多个节,每个节又可能存在多种格式,现有的规定格式样例生成无法满足条件。提出了使用RNN网络训练seq2seq模型,生成合法的PDF文件用于模糊测试。

9. Skyfire: Data-Driven Seed Generation for Fuzzing

论文地址Skyfire: Data-Driven Seed Generation for Fuzzing

总体概述:这篇论文中,提出了一种新的数据驱动种子生成方法,称为Skyfire,该方法利用大量现有样本中的知识为处理高度结构化输入的模糊程序生成分布良好的种子输入。Skyfire将语料库和语法作为输入,包括两个步骤。 Skyfire的第一步是根据语法将收集的样本(即语料库)解析为抽象语法树(AST),并学习PCSG(probabilistic context-sensitive grammar,一种基于概率的上下文相关语法)。然后第二步,利用学习到的PCSG生成种子输入。

总结:在测试高度结构化输入的程序时,提高测试样例的质量,可以很好提高代码覆盖率,当然能更好的发现漏洞。在进行变异的时候只对抽象语法树的叶子节点进行随机变异,这样保证了生成的测试样例的合法性,在一定程度上会提高代码覆盖率。实验表明,Skyfire生成的测试用例比AFL生成的用例覆盖更多的代码,并且发现了更多的bug。 这项工作还证明,测试用例的质量是影响模糊测试效率和有效性的重要因素。

10. A systematic review of fuzzing based on machine learning techniques

论文地址:A systematic review of fuzzing based on machine learning techniques

总体概述: 这篇论文主要回顾了近年来使用机器学习技术进行模糊测试的研究进展,分析了机器学习如何改善模糊过程和结果,并为将来的fuzzing提供了一些启示。与传统模糊测试模型和基于机器学习的模糊测试模型相比,后者确实能提高测试的效率和性能,但仍然存在一些局限性和缺陷。

总结:这篇论文主要是对当前的用于模糊测试的机器算法的各个工作性能进行比较,并且系统的总结了一些模糊测试中使用的机器学习的知识。看完对基于机器学习的模糊测试有了一个全面系统的了解。

论文地址Angora: Efficient Fuzzing by Principled Search

总体概述:这篇论文做的主要工作是通过不基于符号执行来解路径约束以提高分支覆盖率,提出的工具为Angora。其中为了解路径约束,提出了几个关键算法:可扩展的字节级污点追踪、上下文敏感的分支计数、基于梯度下降的搜索和输入长度探测。
可扩展的字节级污点追踪:可以找到与路径约束相关的输入字节,并且在变异的时候只变异这些字节,而不是去变异所有的字节,因此可以大大减少探索的空闲,提高效率和质量。
上下文敏感的分支计数:可以提高更准确的探索程序的状态相比AFL的上下文无关的分支计数。
基于梯度下降的搜索:Angora使用梯度下降算法去接路径约束,梯度下降算法是机器学习中的一个解决局部最小值的算法,没有采用符号执行去解约束是因为符号执行速度是真的慢并且解约束的类型有很大的局限性。

总结:在解路径约束的时候,采用的时候梯度下降算法,但是梯度下降算法是机器学习中用于解决局部最小值的,但是在解约束的时候需要的全局最小值,而且由于输入数据的类型是整数,但是解约束的函数是线性函数,但实际上输入向量是整数,导致函数不可导。所以用梯度下降算法来解约束会存在误差。

12. Matryoshka: Fuzzing Deeply Nested Branches

论文地址Matryoshka: Fuzzing Deeply Nested Branches

总体概述:这篇论文主要针对嵌套条件语句的解路径约束问题,并提出了解决方案。首先找到目标条件语句的所有控制流依赖条件语句,接下来选择目标条件语句的所有污点流依赖条件语句,即数据流依赖。最后,采用三种策略去同时满足的前面的所有条件语句。比如下面的测试程序:

1
2
3
4
5
6
7
8
9
10
1 void foo(unsigned x,unsigned y, unsigned z) {
2 if (x < 2) {
3 if (x + y < 3) {
4 if (z == 1111) {
5 if (y == 2222) { .... }
6 if (y > 1) { .... }
7 }
8 }
9 }
10}

这里假设目标条件语句是Line6,line2、3、4都是6的控制流依赖条件语句;但是只有line2、3才是6的数据流依赖条件语句。这是因为如果变异6,可能会导致line3分支选择的变化导致line6不可达,但是z的取值不会影响分支2,3的跳转。
三种满足约束的策略分别是:
(1) Prioritize reachability:简单的说就是从前往后满足约束,比如上面的例子,首先输入要满足line2,然后一直往后,直到满足line6的约束。变异的时候会避免变异所有与目标条件语句的有效前向语句的输入字节。
(2) Prioritize satisfiability:这条策略与上一条相反,它是从后往前满足。首先要保证Line6的约束,然后往前回溯,直到满足所有的前向有效条件语句的约束。它分为两个阶段,在前期阶段(forward phase)如果能找到一个能达到目标条件语句s的输入,并且没有人为的修改分支选择。否则就要进入回溯阶段(backward phase),从s的前一个有效条件语句,并且避开变异所有能流向s的的bytes。直到fuzz完所有的有效前向条件语句。
(3) Joint optimization for both reachability and satisfiability:这条策略就是同时使用前两种策略。

总结:这个里面用到了污点分析,静态分析中的前向支配树来获取目标条件语句的有效前向语句。偷一下sc的总结,其实就是两个角度做决策,一个是约束条件要满足,一个是要寻找新路径,其实是矛盾的。总的来说就是优先满足约束,模型很简单。