Your bug finding tools are out | Savior: 新一代漏洞驱动的AI混合模糊测试框架

软件中的漏洞一直是导致软件工作异常，造成软件崩溃最重要的原因，软件漏洞不仅会造成大量经济损失，有时甚至会引发灾难性的后果，所以如何在软件部署前尽可能检测排除高危漏洞是一项极其重要的工作，漏洞自动化查找也一直是工业界学术界一个研究开发热点。 模糊测试（Fuzzing）因为其易用性以及漏洞查找的高效性被世界上许多研究人员关注，近些年来许多优秀的工作也诞生在这个领域。 就在最近，在百度安全实验室研究员资深安全研究员Peng Li博士的带领下，高级安全研究员Shengjian Guo博士和Northeastern University的Yaohui Chen博士以及Stevens Institute of Technology的Jun Xu教授就祭出大招，发明并落地了世界上第一个漏洞驱动的混合模糊测试框架:Savior[1]，极大提升了漏洞查找效率。

凭借此项研究，Savior成功被第41界S&P (Oakland) 2020录用。在5月下旬的旧金山，我们会详细介绍Savior中创新的漏洞驱动思路以及这样的思路如何同混合测试相结合并极大地提升漏洞挖掘能力。众所周知，S&P是安全领域四大学术会议之首, 每年5月在美国的旧金山举行，会议聚焦于先进安全研究、发展和趋势，并以其强技术性、权威性、客观性引领未来安全思想和技术的走向。S&P对录用文章有严苛的评审机制，每年的文章录用率仅为11%~12%。

百度安全首创全新的漏洞驱动的混合测试

现在的灰盒模糊测试工具，例如AFL，Libfuzzer etc， 一般都是以覆盖率作为导向的，这些开源 工具 可以认为是当前的stateof arts, 不仅在工业界大量采用，也对学术界的研究起到了深远影响。模糊测试的优势非常明显，它可以快速的找到漏洞, 但是它也有明显的缺点，就是难以访问被复杂条件保护的代码区域，例如，如果一个条件语句是和magic number或者checksum相关， 这种情况下，模糊测试难以猜出一个输入来满足这些复杂条件。相反，concolic execution (符号执行的一种变种) 通过解析constraint非常容易访问这些代码区域。这样来看模糊测试以及concolic execution的结合作为混合模糊测试是非常自然的事情，现有的混合方案包括，Driller[2], QSYM[3]。

但是现有的模糊测试以及混合测试方案都是以覆盖率为导向的，也就是测试会被引导到包含更多代码区域的地方。这样会引发一个问题，就是宝贵的计算资源和时间会浪费在没有漏洞的代码区域。在我们准备这项工作的时候，针对现有的混合测试方案，我们发现它们有两个问题：1. 随机seeds调度，顾名思义concolic execution随机的从模糊测试生成的seeds中挑选一些出来执行。但是这个策略有明显的缺点，我们发现模糊测试seeds生成速率要远高于concolic  execution，如果没有任何优先化选择seeds来发给符号执行，这样会白白浪费大量符号执行的资源; 

2. concolic execution中的随机验证，之前混合模糊测试中concolic execution是在执行的路径中随机选择一个点来检测漏洞，这样的后果是会遗漏非常多的漏洞。

为了克服这些明显的问题，我们开创性的实现了世界第一个漏洞驱动的结合了灰盒模糊测试以及concolic execution的混合模糊测试策略：Savior, 不同于之前的覆盖率为导向的混合模糊测试，Savior会优先化去测试包含更多漏洞的代码区域，为实现这个目标，我们采用两项世界首创的技术来解决上述的问题：

1.    漏洞驱动优先化（bug-driven prioritization）

在Savior实现中，我们先在编译时间内插装undefined behavior sanitizer作为vulnerabilitylabel, 然后通 过静态分析来找到被destination node保护的代码区域以及统计这个区域内vulnerability label的数量。 我们会使用这些静态信息来引导哪些seeds优先传给concolic execution。 Destination node以及如何统计vulnerability label数目如下图所示， 可以看出这片代码区域由8个basic block组成, 其中有3个vulnerability label.  

图1. Destination node定义以及label统计方法

在模糊测试运行一段时间之后，Savior将它生成的seeds排序，排序靠前的seeds代表有更大的可能能够访问到包含更多vulnerability label的代码区域。如何计算一个特定seed的score如图2所示，例如，这条path中b5, b7为没有访问过的代码区域，L1，L2分别代表在b5, b7区域中的label数目，在这个公式中，我们还考虑到了过去concolic execution曾经尝试解析这个branch的次数Si，这个数字越大，代表这个seed能够访问这些没有被测试过的区域可能性在降低。

图2. 计算seed的漏洞导向优先化的公式

2.    漏洞引导全验证（bug-guided verification）

区别于以前的混合模糊测试方案，Savior的concolic execution可以对所执行路径上所有可能出现的漏洞都进行了验证 (bug-guided verification), 这样可以确保在这条执行路径上面不会遗漏掉漏洞。如图3所示，Savior在执行的路径上通过对每个可能出现漏洞的位置都进行constraint solving, 从而可以成功的捕获 overflow，可以避免像其他混合模糊测试遗漏掉bug。

图3. Bug-guided verification实例

漏洞驱动混合模糊测试展现的高效性

我们已将Savior应用于百度的无人驾驶系统Apollo, 以及Deep learning平台PaddlePaddle等重要产品中，帮助这些产品持续提升质量和稳定性。除此之外，Savior也为广泛采用的第三方库如libjpeg, tcpdump以及binutils汇报了483个undefined behavior, 其中243个会导致逻辑错误以及内存越界访问，17个高危漏洞得到了开发人员的确认以及修复, 图4显示了Savior从第三方库中找到的具体的漏洞分布。

图4.  Savior从第三方库中找到漏洞分布

基于在第三方开源软件的实验表明，如图5所示，我们发现Savior可以比现有的混合模糊测试框架Driller以及QSYM查找漏洞速率分别高出43.4%以及44.3%。

图5. 24小时内不同fuzzer汇报的UBSan错误数目

这些数据都表明，Savior在漏洞查找的高效性（effectiveness）以及完整性（thoroughness）上都优于现有的模糊测试方案。

漏洞驱动混合模糊测试的未来

不同于之前覆盖率为导向的模糊测试以及混合模糊测试，我们介绍了世界第一个漏洞驱动的混合模糊测试框架：Savior，这项工作是将漏洞作为导向的一种全新探索，但是这个探索不是终点，仅仅是开始。后续的模糊测试或者混合模糊测试，无论应用在structure aware fuzzing, kernel fuzzing或者其他应用场景 , 漏洞驱动都会提供强大的助力，NDSS 20中的TortoiseFuzz[4]使用漏洞导向来优先化seeds来测试包含更多漏洞的代码区域，Usenix Security 20的ParmeSan[5]应用了sanitizer-guided fuzzing来测试包含更多sanitizer的代码区域，这些都是漏洞驱动应用的最新实例。我们相信Savior核心的漏洞驱动优先以及漏洞引导验证技术也证明了可以在其他混合模糊测试框架得到应用，从而提升漏洞捕获能力。

References:

[1]. Yaohui Chen, Peng Li, Jun Xu, Shengjian Guo, Rundong Zhou,Yulong Zhang, Tao Wei, Long Lu. SAVIOR: TowardsBug-Driven Hybrid Testing, S&P20

[2]. NickStephens, John Grosen, Christopher Salls, Audrey Dutcher, Ruoyu Wang, JacopoCorbetta, Yan Shoshitaishvili, Christopher Kruegel, Giovanni Vigna. Driller:Augmenting Fuzzing Through Selective Symbolic Execution, NDSS16

[3].Insu Yun,Sangho Lee, Meng Xu, Yeongjin Jang, Taesoo Kim, QSYM: APractical Concolic Execution Engine Tailored for Hybrid Fuzzing, USenixSecurity18

[4].YanhaoWang, Xiangkun Jia, Yuwei Liu, Kyle Zeng, Tiffany Bao, Dinghao Wu, Purui Su, NotAll Coverage Measurements Are Equal: Fuzzing by Coverage Accounting for InputPrioritization. NDSS20

[5]. Sebastian Österlund, Kaveh Razavi, Herbert Bos, andCristiano Giuffrida, ParmeSan:Sanitizer-guided Greybox Fuzzing, USenix Security 20