cgnail's weblog | A quantum of academic

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

| categories notes 
tags 漏洞检测  模糊测试  符号执行  源代码分析  程序分析  UsenixSec 

原文: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较多时则差不多。

然后呢

没了。

If you liked this post, you can share it with your followers !