Driller: Augmenting Fuzzing Through Selective Symbolic Execution(2016)

原文：Driller: Augmenting Fuzzing Through Selective Symbolic Execution

为什么要做

现有漏洞检测的问题是难以规模化，以及需要人工干预。静态分析的问题是误报和无法提供可用的输入；动态分析（fuzzer）的问题是需要输入来驱动程序执行。混合执行（concolic execution）的主要问题是路径爆炸，对于大规模程序不适用。

模糊测试生成的输入可以快速深入代码空间，但经常无法通过程序中的输入处理代码，如输入合法性检查。混合执行可以生成能通过输入处理代码的输入，但是很容易就路径爆炸，导致无法深入代码空间。如果能将两种方法结合，就可能达到既能通过输入检查，又能深入代码空间的效果。

做了什么

• 把selective concolic execution和fuzzing结合起来：用fuzzing探索程序空间，遇到输入检查时交由混合执行生成合法输入，从而能有效地分析大规模程序。
• 利用上述技术实现了工具Driller，可以检测出导致程序崩溃的错误(原则上支持任意的漏洞规范)。
• 用工具参加了DARPA的一个漏洞发现竞赛，得了奖。【竞赛用的二进制程序有调用动态库么？还是压根不管库函数有没有漏洞？】

怎么做到的

关键点：程序的用户输入可分为两部分，而程序空间也可根据输入检查的不同分支分成不同的区间（compartment）。general input的值域很宽泛，用fuzzing可以很好地覆盖；而specific input的值域非常有限，通常是被程序进行输入检查的对象，这类输入决定了执行程序空间的哪个区间，用混合执行可以求解跨越区间的sepcific input。

1. 先用测试用例驱动程序并开始fuzzing（也可以不用测试用例）
2. fuzzing【用现成的American Fuzzy Lop】会在一个区间里探索，直至无法深入。（如何认定“无法深入”？在探索了占输入长度一定比例的路径之后仍没有发现新状态）【什么叫新状态？(输入，目的地)二元组】同时标记两种输入：首个触发状态迁移的输入，和首个使路径进入新的循环桶的输入。
3. 调用混合执行【用现成的引擎angr，该引擎使用了Mayhem只对写内存进行符号化的优化，减少了符号值的数量】，将上一步所有标记出来的输入传给混合执行引擎，并为之建立约束。标记出来的输入数量很少，所以可以防止路径爆炸。然后跟踪fuzzing得到的输入的路径，修改路径约束，求解得到能进入新区间的输入。为了减少混合执行的复杂度，采用了一些优化手段，如每次符号执行都探索周边区域以减少符号执行的启动次数；
4. 将新输入传回fuzzer，继续fuzzing。如此反复直至程序崩溃

效果如何

参加了DARPA的Cyber Grand Challenge竞赛，得了奖。竞赛要求用24小时全自动地查找内存崩溃漏洞，并提供相应输入。CGC提供了专门的二进制格式，测试环境等，和实际环境不通用。测试集有131个应用。Driller发现的崩溃比单独用fuzzer或混合执行加起来还要多。

实验环境是一个AMD集群，每个二进制文件分给4个fuzzer节点，混合执行是一个64个节点的池子，所有二进制文件的混合执行都交给这个池子排队执行。每次符号执行限制为1小时和4G内存。

然后呢

Driller的问题：标识状态迁移的方式有缺陷，对于用不同参数多次调用同一个函数的情况无法算作新的迁移，从而不会调用混合执行；对输入的划分有问题，有的程序会把同一段输入在不同的区间里同时当做generic的和specific的，这会导致频繁调用混合执行并最终状态爆炸。第二点的可能解决办法是把符号执行的约束传给fuzzer，让后者生成输入时满足这些约束。