G.O.S.S.I.P 阅读推荐 2022-04-20

今天是24节气中的谷雨，谷雨之后意味着春天结束，夏天到来。暮春三月，江南草长，杂花生树，群莺乱飞。虽然禁足不出小区，但这江南春色中孕育的勃勃生机让小编相信，G.O.S.S.I.P 会和大家一起变得越来越好。周三是我们的投稿专栏，感谢这两年来许许多多为我们送上投稿的作者，感谢你们选择我们这个微小的平台宣发，我们也会继续努力为大家推荐更多更好的内容！

今天为大家介绍的是IEEE S&P 2022的录用论文Effective Seed Scheduling for Fuzzing with Graph Centrality Analysis，这篇论文关注的是fuzzing的改进。我们都知道fuzzing是一种自动化的软件测试方法。它简单高效，易于部署，已经被大规模应用到工业界当中，例如Google的OSS-fuzz和微软的OneFuzz。直至2022年4月，Google的OSS-Fuzz平台已经累积找到了39,000个软件漏洞，分布在550个开源程序里面[1]。早年间OpenSSL中著名的Heartbleed漏洞, 可以被常见的Fuzzing工具--AFL在一天半内自动化发现[2]。

 

我们先简单介绍一下Fuzzing的基本工作流程。如下面的图1所示，fuzzing初始时候会有一个种子池(seed corpus), 里面有很多的测试用例，每个测试用例都是一个种子 (seed)，每次fuzzing需要从种子池里面挑选出来一个种子, 在它的基础上生成很多测试用例变种，然后把这些测试用例变种输入程序中，观察是否有异常的程序行为或者程序崩溃出现，并且保留那些能测试新的代码段的测试用例变种。

 

图1. Fuzzing的基本工作流程

 

在整个Fuzzing流程中，一个基本性的问题就是如何选择种子。一个好的种子，可以帮助生成很多有价值的测试用例变种，迅速提升代码测试率，进而更快地找到漏洞。而一个坏的种子，可以导致生成大量的无效变种，反复测试已经的代码范围，拉低了fuzzing的效率。在实验中，我们发现一个好的种子，在程序流程图(CFG)中, 它的的执行路径可以连通到大量的未测试代码段。如下面的图2所示，seed1可以连通到一块未测试代码段，seed2可以连通到两块未测试代码段。显然的，seed2是一个更好的种子选择，因为它连通到更多的未测试代码段。相比较于seed1,通过seed2生成的大量测试用例变种，也更容易去增加新的代码测试范围。

 

图2. 种子连通到的未测试代码段示例

 

通过上面的分析，我们知道了一个高效的种子选择策略，只要去选择可以连通大量的未测试代码段的种子即可。但在现实Fuzzing中，程序流程图(CFG)的规模很大，如果用简单遍历图的方法，去计算每个种子连通的未测试代码段数量，会产生很大的运行时间开销。同时，我们需要计算的是未测试代码段的数量，这个数字在Fuzzing的过程中会一直保持动态增长，没法使用预先处理再缓存结果的方法去优化。

 

进一步分析，这个问题可以抽象成在一个动态的大规模图中，如何去高效地计算可以连通到的节点数量？我们想到了社交网络中的中心性算法。中心性算法可以测量每个节点在社交网络中的连通性和影响力。举个例子，有些社交达人可以连通到大量的人群；而有些不擅长社交的人却只能连通到很少的人。因此，社交达人的中心性数值就会比较高，而社恐的中心性数值会比较低。

 

对应到Fuzzing领域的种子选择问题上，我们要选择的就是有较高中心性数值的种子，因为它可以连通到大量的未测试代码节点。举个例子，如下面的图3所示，我们对CFG进行图的中心性算法分析，seed1的中心性数值是1.2，seed2的中心性数值是3。因为中心性数值可以近似连通的节点数量， 通过计算中心度，我们就可以选择出有价值的种子，提升Fuzzing效率。在这个例子里面，我们选择seed2作为高效率的种子。中心度数值的另外一个优点是便于快速计算，中心性算法利用iterativepower method可以非常高效的在大规模的图上运算。

 

图3. 利用中心性算法去近似每个seed可以连通到的节点数量

 

利用中心性数值, 我们设计了一个通用的种子调度算法--K-Scheduler。我们把K-Scheduler集成到了主流的Fuzzing工具LibFuzzer和AFLhavoc mode上面。在24小时的Fuzzing实验中，K-Scheduler取得了显著的效果调升。在LibFuzzer上面，对比Entropic，K-Scheduler提升了25.89%的featurecoverage。在AFL havoc mode上，对比AFLFast, K-Scheduler提升了4.21%的edge coverage。具体的实验结果如下面的图4和图5所示：

图4. Fuzzbench里面12个程序的feature coverage在LibFuzzer上

 

图5. Fuzzbench里面12个程序的edge coverage在AFLhavoc上

 

更有趣的是，我们发现K-Scheduler不仅可以提升Fuzzing的效率，还可以用在符号执行中去优化路径选择。符号执行一直以来都有路径爆炸的问题，K-Scheduler可以在众多路径中选择最有价值的路径去进行符号执行，提升代码测试率。我们把K-Scheduler集成到QSYM的符号执行引擎当中，对比默认的路径调度算法，提升了35.76%的edgecoverage。实验结果如下面的表1所示：

表1. QSYM符号执行引擎的edge coverage

 

通过上述实验，我们展示了K-Scheduler,一个具有通用性的基于图中心性算法的种子调度设计。利用图中心度的搜索方法，也为很多基于代码覆盖率的动态软件测试方法(e.g., Fuzzing, 符号执行) 提供了新思路。理论上来说，K-Scheduler还可以被应用到其他应用层面的Fuzzing，诸如黑盒Fuzzing，内核Fuzzing，网络协议状态Fuzzing中等等。

 

论文地址：

https://arxiv.org/pdf/2203.12064.pdf

代码和复现包 (包括测试程序和种子池)：

https://github.com/Dongdongshe/K-Scheduler

 

Reference:

[1] https://bugs.chromium.org/p/oss-fuzz/issues/list?q=-status%3AWontFix%2CDuplicate%20-component%3AInfra&can=1

[2] https://blog.hboeck.de/archives/868-How-Heartbleed-couldve-been-found.html

 

---

作者介绍：佘东冬，哥伦比亚大学计算机学院博士生，导师SumanJana和Baishakhi Ray。他本科毕业于华中科技大学，研究生毕业于加州大学河滨分校，师承钱志云老师。他的研究方向专于利用机器学习，数据驱动的方法去解决安全问题，程序分析，Fuzzing。多次将研究成果发表于Oakland，CCS，UsenixSecurity， FSE等国际安全和软件工程顶级会议。

作者主页：https://www.cs.columbia.edu/~dongdong/

 

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2022-04-20