Dowsing for overflows: A guided fuzzer to find buffer boundary violations(2013)

原文：Dowsing for overflows: A guided fuzzer to find buffer boundary violations

为什么要做

单纯的fuzzer只能发现简单的bug而且不能保证覆盖率，whitebox fuzzing借助符号执行（SE）扩展了覆盖率，但是由于固有的路径爆炸问题很难扩展到大规模的程序。

做了什么

利用其它分析手段（动态污点分析（DTA）辅助的fuzzing和一些静态分析）引导SE只执行最有可能出bug的路径。这篇文章专注于查找循环中的缓冲区溢出（BO）bug，在ffmpeg和poppler中发现了共计两个未知漏洞。

怎么做到的

1. 基于LLVM对程序做过程内的数据流分析，对所有在循环中访问缓冲区的指令进行优先级排序，这些指令成为分析组（AG）。排序算法可以自定义，文章用了一种基于代码计算复杂度的排序法，原理是越复杂的计算越容易出现溢出。对LLVM做了些优化使得语法上相似的代码可以获得相似的得分。复杂度的阈值为26，因为根据作者的观察，小于26的循环中通常最多只有两条语句修改数组偏移量。
2. 使用DTA的fuzzing，找出影响指令的输入域。DTA忽略了控制依赖，这里基于前人的工作做了些优化，使得可以追踪控制依赖。
3. 利用S2E做符号执行，修改输入2中找到的输入域，在指令处触发漏洞。用第三方工具AddressSanitizer报告溢出。符号执行分为两个阶段：学习阶段用一小段符号值穷举执行循环，对其中的分支进行优先级赋值，更有可能出现新的指针皆引用的分支优先级更高；查找阶段只执行优先级高的分支，对于优先级为0的分支则不执行。根据实验分析，只有不到1/3的分支优先级不为0。学习阶段的算法不能有漏报。

效果如何

先用nginx测试各种优化的效果，然后对7个真实应用作测试。每次SE最多执行15分钟，S2E对于循环做的优化在试验中被证明没有什么效果。

使用Spearman秩相关计算排序算法的赋值和内存崩溃之间的相关性，以证明排序算法的可靠性。结果显示Dowser的排序算法在AG较少时可以比随机赋值和平均赋值多检测出40%的bug，AG较多时则差不多。

然后呢

没了。