bsauce读论文：MoonShine：Optimizing O
摘要
问题：现有OS Fuzzer的效率受到种子程序中syscall序列的质量和多样性的影响，种子程序中各个syscall之间可能存在相互依赖的关系（每个syscall的行为依赖于之前的syscall所创建的内核状态），仅仅依靠人工定义的规则来生成有效syscall序列非常耗时耗力，且代码覆盖率有限。
目标：从真实程序中提取有效的syscall序列作为OS fuzzer的种子，同时保持较高的覆盖率。
方法：轻型静态分析—distillation算法，有效检测不同syscall之间的依赖关系。作为Syzkaller的扩展
结果：从3220个包含280万syscall的真实程序中，提取出3195个trace，syscall数目减少到14000个，但仍然保持了86%的原始路径覆盖率。将syzkaller的代码覆盖率提高了13%；发现17个漏洞。
缺点：只能从已有路径中探索，不能变异生成畸形调用序列。是否能找到调用之间的参数依赖图，这样变异效率更高。
1.Introduction
总体步骤：
执行真实程序—>收集syscall序列+每个syscall覆盖信息—>选取覆盖大的syscall，静态分析识别依赖关系—>分组形成种子程序。
Fig3-MoonShine总体流程
贡献：
a.提出seed distillation（保持依赖关系，实现代码覆盖）。
b.用轻型静态分析实现高效的seed distillation算法。
c.实现MoonShine，帮助Syzkaller提高代码覆盖，发现17个漏洞。
2.Overview
2.1 问题描述
人工定义调用规则：扩展性不强。
最小化策略—afl-tmin[12]：动态移除输入的部分字节，而不影响覆盖率。但无法处理调用序列，syscall之间依赖关系很复杂。
解决方法：从真实程序中提取trace，因为真实程序的syscall序列一般满足call之间调用依赖。新问题是真实程序的syscall序列过长，不能直接作为种子程序，要想缩短trace，动态分析的开销很大。
依赖类型：
（1）显式依赖：参数来自其他syscall的输出。见Fig1，mmap()的第3参数来自open()的返回值。
（2）隐式依赖：控制流影响，某些syscall内部修改了内存共享变量（共享数据结构），从而影响其他syscall的执行流。见Fig1-2，mlockall()设置的变量vma->vmflags影响了msync()的执行流。
2.2案例分析
见Fig1。
（1）识别显式依赖
首先识别出覆盖率贡献最大的syscall，如mmap,msync,write。识别其中的显式依赖，如对mmap，遍历每个参数，搜索该参数是之前哪个syscall的返回值。
（2）识别隐式依赖
如对msync，检查执行时是否在条件语句中用了之前syscall设置的结构变量。msync在条件语句中读取vma_struct->vma_flags，mlockall在赋值语句中写vma_struct->vma_flags。
Fig1—Distillation案例
Fig2—隐式依赖案例
3.方法
（1）Seed distillation算法
见Algorithm1。
Algorithm1—seed distillation算法 - 笔记
（2）显式依赖算法
见Algorithm2。
定义
依赖图：结果节点+参数节点。
结果节点r：返回值+返回值类型+生成返回值的syscall。
参数节点a：参数+参数类型+使用该参数的syscall。
a->r边：参数a依赖产生r的syscall。
方法：Mooshine解析Trace来构造依赖图，通过依赖图来检测显/隐式依赖关系。
显式依赖：
对每个syscall的返回值，构造结果节点加入到结果map，用组合key(type,value)索引；对每个syscall的参数，检查结果map，若有匹配的结果节点，则添加一条边。构建好参数依赖图后，对给定call c，遍历c的参数，访问依赖图中对应的参数节点，标记c与该参数节点指向的结果节点为显式依赖。
（3）隐式依赖算法
Read dependency：调用c在条件语句中读取全局变量v。
Write dependency：调用c写全局变量v。
定义隐式依赖：调用c_a的写依赖与c_b的读依赖交集不为空，则c_a是c_b的隐式依赖。
方法：利用静态控制流分析，得到读/写依赖，对指定syscall c，记录每个条件语句的全局变量读和一元赋值语句的全局变量写。
问题：过依赖—全局变量设置为特定值才会影响其他syscall执行流；欠依赖：别名-全局变量。
Algorithm2-显式隐式依赖算法 - 笔记
4.实现
总体：Trace Generation + Seed Selection。
（1）内核插桩
Kcov[38]内核插桩—设置CONFIG_KOV标记。
检测bug—gcc sanitizer：KASAN[18]，UBSAN[14]。
其他detector：死锁检测；内存泄露KMEMLEAK[5]。
（2）Tracer
扩展Strace[13]—通用syscall tracer：检测syscall名称，参数，返回值，能跟踪到fork/exec内部。给Strace添加455行代码+3个文件，用-k选项执行。
（3）多进程Trace
进程树：node—存call trace；edge—父子关系。
跨进程找显式依赖，确保父进程在clone之前把值存入cache。
（4）显式依赖
存在3种例外：syscall参数自己返回结果，如pipe；内存分配syscall如mmap，依赖返回值确定的调用空间，只要落在这个地址空间内都算显式依赖；不同种子程序之间有依赖，则整合为1个。
（5）隐式依赖
基于Smatch[16]—针对c的静态分析框架，进行控制流分析；能够在smatch遍历程序的AST时根据相应事件触发相应的注册函数。
方法：在判断条件处Hook，检测read依赖；在一元赋值处Hook，检测Write依赖。
5.测试
5.1 环境准备
种子程序（获取Trace）：
a.Linux Testing Project (LTP) [7]
b.Linux Kernel selftests (kselftests) [6]
c.Open Posix Tests [8]
d.Glibc Testsuite [3]
OS Fuzzer—syzkaller。
提取算法：MoonShine(I+E)—显式/隐式；MoonShine(E)—显式；RANDOM—不考虑依赖。
5.2 漏洞检测能力
MoonShine(I+E)发现17个漏洞；MoonShine(E)发现7个。10/17个是竞争漏洞，都在文件/网络子系统中。见Table1。
5.3代码覆盖率
MoonShine(I+E)发现53270个基本块；MoonShine(E)发现51920个基本块；RANDOM发现47320个基本块。帮助syzkaller把代码覆盖率提高了13%。
5.4 提取trace有效性
3220条trace包含290万个syscall，提取过后的种子只包含16442个syscall，保留了86%覆盖率。
5.5 高效性
80min内收集和提取了110千兆（十亿）字节的trace。
6.讨论
6.1 不足
（1）不能识别线程/进程之间的依赖：只能识别同一个线程或父进程产生的依赖关系。
（2）静态分析的误报率较高：一是错误识别为隐式依赖，使trace过长；二是指针分析不准确，若两个syscall同时读写了一个struct，MoonShine不能判断是否对应的指针引用了相同的struct，例如mlock和munmap都引用了vma struct，但vma由传入的第一个参数指针决定，若传入指针不同，则没有依赖，而MoonShine每次都判定有隐式依赖。
6.2 未来方向
（1）支持其他内核fuzzer
例如Digtool[29]，kAFL[33]。基于虚拟化的动态方法能更准确的识别隐式依赖，当然性能开销更大。
（2）fuzz设备驱动
本文目标是linux内核，如文件系统、内存管理、网络，但设备驱动占linux源码超过40%。
