内核漏洞挖掘技术系列(4)——syzkaller(4)-先知社区

在上一篇文章中我们主要介绍了syzkaller是怎么处理crash的，这篇文章我们主要介绍vmLoop函数中是怎么进行fuzz的。在runInstance函数中把syz-fuzzer和syz-executor复制到VM中，调用FuzzerCmd函数通过ssh执行syz-fuzzer。

执行的命令大概像下面这样：

/syz-fuzzer -executor=/syz-executor -name=vm-0 -arch=amd64 -manager=10.0.2.10:33185 -procs=1 -leak=false -cover=true -sandbox=none -debug=true -v=100

同时MonitorExecution函数进行监控，检测输出中的内核oops信息、丢失连接、挂起等等。

在fuzzer.go的main函数中首先进行了一些设置，比较重要的是通过RPC调用的Check函数。Check函数最终调用loadCorpus函数将db中的语料加载到mgr.candidates中。在fuzzer.go的main函数最后调用pollLoop函数，pollLoop函数中又调用了poll函数，在poll函数中继续通过RPC调用Poll函数，Poll函数主要是调用了candidateBatch函数取得mgr.candidates，将它们加入到fuzzer的workQueue中。
返回fuzzer.go的main函数中，然后调用了CalculatePriorities函数和BuildChoiceTable函数。

对于给定的一对系统调用X和Y，prios[X][Y]是指我们对在包含系统调用X的程序中添加系统调用Y是否可能得到新的覆盖的猜测。当前算法有两个组件：静态和动态。静态组件基于对参数类型的分析。例如，如果系统调用X和系统调用Y都接受fd [sock]，那么它们在一起更可能得到新的覆盖。动态组件基于语料库中单个程序中特定系统调用出现的频率。例如，如果socket和connect经常一起出现在程序中，那么会给这对系统调用提供更高的优先级。在CalculatePriorities函数中分别调用了calcStaticPriorities函数和calcDynamicPrio函数计算静态部分和动态部分，最后返回的二维数组dynamic[i][j]中系统调用i和系统调用j的优先级是二者的乘积。

在calcStaticPriorities函数中调用calcResourceUsage函数创建了一个hash表，key是string类型，表示某一种资源；value也是一个hash表，key是系统调用的id，value是权重。资源是通过遍历函数参数得到的，比如可以是Vma，Ptr，Buffer等等。每种类型的权重是不同的，比如Vma是0.5，Ptr是1.0等等。在noteUsage函数中同一种资源同一个系统调用做记录的时候只会记录最大的值。calcStaticPriorities函数在遍历的过程中对于同一种资源把系统调用A占该资源的权重乘上系统调用B占该资源的权重加到系统调用A和B的优先级里。

而当A等于B时prios被设置为A与其它所有系统调用prios的最大值，最后调用normalizePrio函数规范化。

动态部分的计算如前所述，非常简单，如果语料库一对系统调用一起出现在程序中那么会给这对系统调用的prios加1。最后同样也是要调用normalizePrio函数规范化。

CalculatePriorities函数之后会调用BuildChoiceTable函数，它基于CalculatePriorities函数计算的prios和启用的系统调用计算出一个类似的表run，不过对于系统调用i和系统调用j来说run[i][j]的值是之前run[i][x](x小于j)的和加上prios中i和j对应的值乘上1000。所以对于run[x]来说是由小到大排好序的。Choose函数的功能是对于一个给定的系统调用根据run表返回一个系统调用。选择仍然是随机的，run表仅仅提供了有限的权重。

在上一篇文章中我们说到config文件中的procs参数表示每个VM中的并行测试进程数，所以接下来：

现在让我们进入loop函数。

WorkQueue包含还没有fuzz的对象。WorkQueue对它们进行优先排序，例如我们希望在销毁程序之前对新的输入进行分类并发送给manager，以便不会丢失让VM崩溃的程序。WorkQueue中的对象有WorkTriage，WorkSmash和WorkCandidate三类。在loop函数中遍历WorkQueue，对于这三种对象分别调用triageInput函数，smashInput函数和execute函数。后面分别还有对Generate函数和Mutate函数的调用，它们分别生成新的系统调用和对已知的系统调用进行变异。
WorkTriage是我们在第一次执行时注意到可能存在新覆盖率的程序，但还不确定。在分类过程中我们将知道这些程序是否提供了新的覆盖，如果是，则最小化它们并添加到语料库中。
WorkSmash是刚刚添加到语料库中的程序。在smashInput函数中如果设置了comparisonTracingEnabled则调用executeHintSeed函数。hint基本上是一个由指向程序的一个系统调用中的一个参数的指针和一个值组成，该值应该赋给该参数(syzkaller中称之为replacer)。syzkaller中hint的原理如下：fuzzer启动一个程序(hint seed)，并为程序中的每个系统调用收集所有比较的数据。接下来，它尝试匹配获得的比较操作数的值和输入参数的值。对于每一个这样的匹配，fuzzer都会用保存的值替换指定的参数来改变程序。如果获得了一个有效的程序，fuzzer启动它并检查是否获得了新的覆盖率。收集比较的数据是通过kcov中提供的KCOV_MODE_TRACE_CMP模式实现的。

在executeHintSeed函数中首先执行原始程序，在MutateWithHints函数中用系统调用参数和保存在compMaps中的比较操作数之间的每一次匹配对初始程序进行Mutate。CompMap是一个uint到uint64Set的映射，uint64Set又是一个uint64到bool的映射。执行每一个这样的Mutate之后检查它是否提供新的覆盖率。

在generateHints函数中主要是调用了checkConstArg函数和checkDataArg函数，在这两个函数中调用shrinkExpand函数得到replacer替换掉原来的值。

还是以test中的例子说明。比如说有这样的代码：

// Models the following code:
// void f(u64 qw) {
//      u8 b = (u8) qw
//      u16 w = (u16) qw
//      u32 dw = (u32) qw
//      if (b == 0xab) {...}
//      if (w == 0xcdcd) {...}
//      if (dw == 0xefefefef) {...}
//      if (qw == 0x0101010101010101) {...}
//  }; f(0x1234567890abcdef);

那么CompMap中的内容应该是：

CompMap{
    0xef:               uint64Set{0xab: true},
    0xcdef:             uint64Set{0xcdcd: true},
    0x90abcdef:         uint64Set{0xefefefef: true},
    0x1234567890abcdef: uint64Set{0x0101010101010101: true},
},

得到的结果是：

uint64Set{
    0x1234567890abcdab: true,
    0x1234567890abcdcd: true,
    0x12345678efefefef: true,
    0x0101010101010101: true,
},

再比如说有这样的代码：

// void f(i32 dw) {
//      i64 qw = (i32) dw;
//      if (qw == -2) {...};
// }; f(-1);

那么CompMap中的内容应该是：

CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}},

得到的结果是：

uint64Set{0xfffffffe: true},

这里涉及到位数的扩展和截断，也是函数名的由来。当然对于下面这样的情况：

// void f(i8 b) {
//      i16 w = (i16) b;
//      if (w == (i16) 0xfeff) {...};
// }; f(-1);

w == (i16) 0xfeff永远不可能成立，所以结果为空。这样满足程序中的比较条件，能够得到更多的路径。
WorkCandidate是来自hub的程序，我们还不知道它们对fuzzer是否有用，proc处理它们的方式与本地Generate和Mutate的程序相同。在经过proc.execute->proc.executeRaw->proc.env.Exec->env.cmd.exec一系列的调用后将数据传给executor执行。在proc.env.Exec函数调用env.cmd.exec函数之前先调用makeCommand函数。makeCommand函数设置pipe通信并通过osutil.Command运行executor，executor从fuzzer读取输入并运行系统调用。

我们来看看executor目录下的executor.cc中的main函数。首先做的是重新映射输入/输出，之后根据上一篇文章我们已经提过config中的sandbox不同的设置分别调用do_sandbox_(none/setuid/namespace)等函数。以位于executor目录下的common_linux.h中的do_sandbox_none函数为例，它主要是调用了loop函数，接下来经过execute_one->schedule_call->thread_create->thread_start->worker_thread->execute_call->execute_syscall一系列的调用后系统调用最终被执行，最后得到代码覆盖率等信息。
在这一篇文章中我们介绍了vmLoop函数中是怎么进行fuzz的，关于该选择哪些系统调用进行fuzz虽然syzkaller通过静态和动态组件计算了权重，但是仍然有一些改进的余地。在USENIX Security 2017上的一篇论文MoonShine: Optimizing OS Fuzzer Seed Selection with Trace Distillation中作者设计了一种名为Distillation(蒸馏)的算法，并且开发了用这种算法来产生种子程序的框架工具MoonShine。真实世界的程序为了让自身功能正常运行，需要满足Trace中system-call正常执行所需要的内核状态。MoonShine使用了轻量级的静态分析来对真实世界中的程序产生的Trace中的system-call进行依赖关系的检测并“蒸馏”出种子程序给syzkaller fuzz。嵌入了MoonShine的syzkaller发现了17个新的Linux内核漏洞。
源代码：https://github.com/shankarapailoor/moonshine
论文地址：https://www.usenix.org/conference/usenixsecurity18/presentation/pailoor
论文解读：https://zhuanlan.zhihu.com/p/60798641
有兴趣的读者可以自行查阅。
在下一篇文章中我们将介绍Generate和Mutate的具体方式。