MoonShine: Optimizing OS Fuzzer Seed Selection with Trace Distillation
本文发表于Usenix Security 2018，作者：Shankara Pailoor，Andrew Aday，Suman Jana。三位作者均来自于Columbia University。
1. 主要内容
OS Fuzzer是一种主要在操作系统内核与用户态程序间利用system-call进行安全漏洞挖掘的工具。现有Fuzzer的效率主要依赖种子程序中system-call序列的高质量与多样性，但是产生好的种子程序是一个很难的问题，因为每一个system-call的行为都将严重依赖于前一个system-call所产生的内核状态，因此现在流行的Fuzzer都依赖于人工编写的规则产生可用的种子程序，然而这种方法不仅浪费了大量的人力资源，而且产生的种子程序也比较缺乏多样性。
在这篇文章中，作者设计了一种名为Distillation（蒸馏）的算法，并且开发了用这种算法来产生种子程序的框架工具——MoonShine。它通过利用真实世界中的程序产生的Trace，因为真实世界的程序为了让自身功能的正常运行，需要满足Trace中system-call正常执行所需要的内核状态。MoonShine使用了轻量级的静态分析来对不同的system-call进行依赖关系的检测。
作者将MoonShine嵌入到了Syzkaller（Google开发的OS Fuzzer）中，从3220个真实世界中的程序提取了共计3195个Trace，包含280万个system-call，MoonShine通过蒸馏算法将其优化到14000个。另外，嵌入了MoonShine的Syzkaller发现了17个新的Linux内核漏洞。
2. 解决方法
2.1问题陈述
大多数现在的OS Fuzzer都是利用人工编写的规则来满足前后system-call之间的依赖，生成可用的种子程序，MoonShine从真实的程序运行中产生Trace，因为现实世界运行的程序为了让功能正常运行，需要满足这种依赖。但是这样做有两个challenge，第一个是正常运行的程序，Trace所包含的system-call增长地很快，比如Chromium会在十秒左右的时间产生46万个system-call，因此这样的Trace没法直接当成seed程序使用，而另一方面这样的system-call序列如果因为过长进行缩短的话，很难知道哪些system-call之间有依赖关系。现有的方法通过动态测试的方法进行优化，但是大都时间复杂度较高，不具备可伸缩性。
为了避免这种情况的发生，作者采用了静态分析的方法，首先作者定义了前后system-call之间的两种依赖关系：
Explicit Dependencies：如果系统调用c_i与系统调用c_j满足这种关系，那么表示c_i产生的结果被c_j直接当做输入参数使用。
Implicit Dependencies：如果系统调用c_i与系统调用c_j满足这种关系，那么表示c_i将会通过与c_j在内核中共享的数据来影响c_j的执行，即便c_i的输出与c_j的输入没有重叠。
左边是seed的原始序列，右边是经过蒸馏过的system-call序列。其中可以很明显地看出来第三行的mmap与第二行的open构成了implicit dependency，因为mmap的输入参数直接使用了open的输出，而第一行的mlockall与第六行的msync构成了implicit dependency关系，如下图所示，mlockall会对msync的条件语句的变量进行修改，进而影响到了msync的代码覆盖率。
2.2算法思路
下图是对Trace进行蒸馏算法的伪代码示意图：
首先MoonShine会首先计算每个system-call的coverage，然后将每个system-call的coverage从大到小排序（第5-8行）。对于每一个system-call，首先会判断这个system-call对覆盖率有没有提升（第10行），如果没有的话就剔除（如果这个system-call存在状态依赖的话会在11行与12行通过Dependency添加到seed）MoonShine都会计算它们的Explicit与Implicit Dependency然后合并（第11-13行）。之后这些Dependencies与这个system-call将会和seed合并，另外还会把当前system-call的coverage记录在一个集合中（第14-16行），这样保持了各个system-call在seed中的顺序与在原有Trace中的顺序一致。
接下来给出求Explicit与Implicit Dependency的伪代码：
对于每一个Trace，MoonShine都会为其构造一个包含两类结点的依赖图：1.结果结点；2.参数结点。其中结果结点包含三类信息：1.返回值；2.返回类型；3.在Trace中产生这样结果结点的system-call。参数结果保存的信息类似：值，类型以及这个参数所属于的system-call。一条从参数结点a指向结果结点r的边表示a依赖于产生r的system-call，MoonShine通过解析Trace来构造这样的图。利用这种依赖图，可以通过遍历依赖图来检测Explicit Dependency。
而对于Implicit Dependency，MoonShine通过静态控制流分析得到。这两个方法会互相进行递归调用，在Trace上不断向上搜索Dependency。Implicit Dependency产生的原因是他们分别对同一个内存中的变量进行了读/写。这样便产生了两种定义：如果一个system-call读了一个变量，那么就称为Read Dependency，同理可以定义Read Dependency。那么可以很容易地给出Implicit Dependency的定义，如果一个system-call的Read Dependency集合与另一个system-call的Write Dependency集合的交集不为空，那么可以认为这两个system-call之间存在着Implicit Dependency关系。
3. 工具实现
为了能够执行蒸馏算法，MoonShine需要知道每个system-call执行后内核的代码覆盖率，作者采用了Kcov进行了覆盖率的测量。
作者通过扩展STrace实现了Tracer，之所以要对STrace进行再开发的原因是要捕捉system-call的名称、参数和返回值。本身STrace是通过fork和exec来跟踪system-call的，他们最后共添加了455行代码和3个文件，并且计划向STrace的开发者提供补丁。
作者通过使用Smatch，一个对C进行静态分析的框架，来进行控制流分析。Smatch允许用户使用hook的方式对程序进行跟踪，这种hook类似于C的表达式，如赋值hook、条件hook，Smatch通过遍历程序的AST完成这项功能。MoonShine如果要跟踪Read Dependency的话，那么通过注册一个Condition Hook来检测条件语句，而Write Dependency只要注册一个Assignment Hook，它会来检测赋值语句的左值。
4. 测试
4.1种子程序
MoonShine的Trace主要通过如下程序来获取：1.Linux Testing Project；2.Linux selftests；3.Open Posix Tests；4.Glibc Testsuite。
由于MoonShine本身只是用来进行优化种子选取的模块，不是整个OS Fuzzer，因此需要嵌入到现有的OS Fuzzer中去。作者为此选取了Google开发的Syzkaller，同时他们将嵌入了MoonShine的Syzkaller运行在了Google的两个fuzzing groups上面，每个group包含4个3.75GHz的CPU与3.6GB的memory。
4.2漏洞检测能力
作者检测了三种不同的情况：不使用蒸馏算法（即采用Syzkaller自身编写的人工规则，Default），使用蒸馏算法（Explicit Dependency，E）与使用蒸馏算法（Explicit+Implicit Dependency，I+E）。作者对每一个种子程序的集合分别运行了三次，每次运行了24小时，最后发现使用蒸馏算法可以多发现17个漏洞，其中如果不使用Implicit Dependency的话，能发现7个。
4.3代码覆盖率
与4.2中的测试情况一样，作者依旧分为三类进行测试并在每种情况下运行了24小时，最后发现，（I+E）发现了53270个独立的基本块，（E）发现了51920个独立基本块，而Default发现了47320个独立基本块。
5. 不足之处
5.1缺少线程之间的依赖跟踪
MoonShine的依赖跟踪算法假设了一个system-call的所有依赖都由同一个线程或者父进程产生，但是如果一个system-call依赖的资源由并行线程或进程产生，那么现在的MoonShine的实现将无法跟踪这样的依赖。
5.2静态分析产生误报
作者称使用静态分析去检测implicit depedency可能会产生误报，但是这不会让代码覆盖率下降，只会让Trace的长度变地更长。
作者为此做了实验并发现产生这种误报的主要原因是不够精准的指针分析，如果两个system-call同时读写了一个struct field，MoonShine不能决定是否对应的指针引用了相同的struct实例。
文丨RainyD4y, dotsu, DJR
