Dowsing for Overflows: A Guided Fuzzer to Find Buffer Boundary Violations

本文是发表在USENIX Security上的一篇关于Overflows漏洞探索的文章，第一作者是来自VU University Amsterdam的Istvan Haller，他Ph.D期间所在的团队主要从事程序分析，漏洞分析，编译器及编程语言优化等工作。

1 主要内容

这篇文章主要针对Buffer Overflow这一类在软件错误中非常严重的问题，提出一个有效的解决思路，并据此实现了一个能快速准确定位代码中此类bug的工具。作者的主要思路是首先对程序进行分析，定位到可能发生Overflow的地方，只对这些可能涉及到Overflow的部分进行关注。然后作者对输入进行污点分析，确定输入的哪些部分对这些容易产生Overflow的地方有影响。最后作者通过对可能影响Overflows 的输入部分进行符号化执行，并通过一定策略引导符号化执行往可能发生Overflows的代码推进，从而快速的分析出可能的Overflow问题。本篇工作的一大特点是作者提出一种引导式，针对性的符号化执行策略去探索代码中的Overflow，而不是覆盖所有代码，这个策略带来了很高的效率提升。

2 案例分析

这段代码是流行的web 服务器 Nginx中的一段存在Overflow漏洞的代码。对于32行和33行，代码未加检查的对指针进行循环操作，攻击者可以构造一个巧妙的payload来利用这段逻辑bug完成任意代码的执行，造成严重的后果。但这段代码的逻辑非常复杂，需要触发bug的条件非常难满足，一般的静态分析或fuzz工具都不能有效的定位这个问题。黑盒fuzzer很难走到较深的路径，去发现这种复杂的bug；白盒fuzzer，符号化执行现有的策略要求代码覆盖率，虽然能发现更深的bug，但对于Overflow这样需要在循环中多次执行才能发生bug还是难以发现。另外不定长的输入对于符号化执行的效率也有很大的影响，符号化长度的增加会导致计算时间指数级的增加。因此，对于Overflow这类问题，现有的工具，方法都不能很好的解决。

3 设计实现

于是作者提出了一种针对Overflow的解决思路，引导符号化执行仅去探索我们关注的地方,并且最小化的符号化输入，以提高执行效率。

解决方法主要分为3步：

1. 静态分析

本文提出的一个观点是，Buffer Overflow更易容易发生在对数组的循环操作过程中，并且这些操作越复杂，程序员对与它的掌控能力越小，漏洞越可能发生。

因此作者对程序进行静态分析，基于LLVM的SSA模块找到代码中所有的数组循环操作指令集，并根据复杂度对这些指令group排序，优先选择复杂度高的代码进行后续的分析，希望能找到Overflow。通过静态分析，作者确定了更容易寻找到Overflow的代码段。

2. 污点分析

污点分析部分主要确定输入的哪些部分对我们关注的代码段有影响，这样当我们进行符号化执行的时候就可以只对我们关注的部分进行符号化，避免符号化输入部分太长导致的效率低的问题。作者沿用了Bao et al. 提出的污点分析策略来解决污点分析中隐式流的问题，并提出输入块位置调整的方法来解决过度依赖的问题，最终确定了输入对可能发生Overflow的代码段的影响。

3. 符号化执行

根据前两步的结果，作者已经知道需要将符号化执行引导到哪些地方，并知道需要对输入的哪些部分进行符号化执行，在第三步需要解决的是如何引导的问题。

作者提出的一个想法是，先执行一个简单的符号化执行，沿用以前的策略，将代码所有的路径扫描一遍，在扫描的过程中将我们关注的代码路径权值调高，当权值确定后再次执行符号化执行，让符号化有限选择权值高的路径，这样就做到了对符号化执行的引导，去探索Overflow的代码段来发现bug。这里对代码进行静态分析也可以起到简单符号化执行的效果，但是由于关注的代码段比较多，对每一个代码段都进行一次分析太麻烦。

4 实验结果

作者节选了09年以来到关于Overflows的比较重要的CVE对工具进行验证，结果如上图所示。

作者的工具是基于S2E工具实现的，可以看到作者的工具在寻找Overflow的漏洞上效果非常显著，能够在15分钟内就快速的找到bug，并且还可能发现未知的Overflow漏洞。

5 总结与评价

本工作在技术上都采用已有的技术，只是进行了一些优化，但提出的策略能够很好的解决Overflow这一类问题，并能够高效的完成符号化的执行，找到代码深处存在的Overflow，在思路上值得学习与借鉴，是一篇不错的文章。

文丨Harry, Robin, DR.XX