NDSS 2020 - HFL: Hybrid Fuzzing on the Linux Kernel

原文链接:https://www.ndss-symposium.org/wp-content/uploads/2020/02/24018-paper.pdf

会议PPT:https://www.ndss-symposium.org/wp-content/uploads/24018-slides.pdf

一作 Kyungtae Kim 来自普渡大学,其也是另一篇 fuzz kernel 相关工作 Razzer 的作者,感兴趣的可以浏览他的个人主页

主要内容

将符号执行(symbolic execution)与模糊测试(fuzzing)相结合的混合模糊测试(hybrid fuzzing)由于结合了二者的优点,在漏洞自动化挖掘领域受到了越来越多的关注。但由于以下三点 challenge 的存在,混合模糊测试很难直接用于发现内核漏洞:

  1. 内核为了实现多态而导致的存在大量由系统调用的参数决定的非直接调用
  2. 系统调用间隐含的依赖关系
  3. 调用系统调用时未知嵌套参数类型的结构推断

为了解决上述问题,本文提出了 HFL,一款基于内核模糊测试工具 Syzkaller 和符号执行工具 s2e 开发的内核混合模糊测试工具,并利用以下三项技术解决了之前提到的内核模糊测试的难点:

  1. 将间接控制流转换为直接控制流
  2. 推断系统调用的顺序
  3. 识别系统调用的嵌套参数类型

最后的实验结果表明,HFL 在 Linux 内核中发现了 24 个新的漏洞;相比 Moonshine 和 Syzkaller 代码覆盖率分别提升了 15% 和 26%,相比 kAFL、S2E、TriforceAFL,在相同的资源消耗(CPU、时间)的情况下,代码覆盖率甚至高达四倍;此外,针对 13 个已知漏洞,HFL 的漏洞挖掘效率是 Syzkaller 的三倍。

设计实现

Overview

Overview

HFL 的通用混合模糊测试由以下三部分组成:

  1. Kernel Syscall Fuzzing
  2. Coverage Guided Fuzzing
  3. Symbolic Analyzer

其中需要关注的是混合模糊测试从 fuzzing 切换到 symbolic execution 的时机,HFL 会维持一个频度表来统计模糊测试过程中遇到的各个分支取值为真或假的次数,这样它就能识别出一些在执行过程中一直为真或一直为假的困难分支,继而忽略那些之前已经见过的分支,触发更多的代码覆盖。

Indirect Control Transfer Determined by Input

为了支持大量的设备和功能,Linux 内核中的大部分设计都被划分为了接口和实现两层,用接口来访问特定的实现,即所谓的“多态”。而这种多态一般使用函数指针表实现的,内核会维护一张函数指针表作为接口,里面包含指向不同实现的函数指针,示例代码如下所示:

ssize_t (*ucma_table[])(struct ucma_file *file,
                        char __user *inbuf, int in_len, int out_len) = {
    [RDMA_CREATE_ID] = ucma_create_id,
    [RDMA_DESTROY_ID] = ucma_destroy_id,
    [RDMA_BIND_IP] = ucma_bind_ip,
    ...
    [RDMA_JOIN_MCAST] = ucma_join_multicast
};
ssize_t ucma_write(struct file *filp, char __user *buf,
                   size_t len, loff_t *pos) {
    struct rdma_ucm_cmd_hdr hdr;
    ...
    if (copy_from_user(&hdr, buf, sizeof(hdr)))
    ...
    // indirect function invocation
    ret = ucma_table[hdr.cmd](file, buf + sizeof(hdr), hdr.in, hdr.out);
}

为了解决这个问题,HFL 设计了一款基于内核源代码的离线转换工具,将间接跳转转换为直接跳转,其工作流程如下:

  1. 工具验证函数指针表的索引来自系统调用的参数
  2. 根据函数指针表和可行的索引值,HFL 会进行分支转换,针对每个索引值,HFL 会插入跳转到相应函数指针的条件分支(该过程类似循环展开)

转换前后的代码如下所示:

// before translation
ret = ucma_table[hdr.cmd](...);
...
// after translation
if (hdr.cmd == RDMA_CREATE_ID)
    ret = ucma_create_id (...);
else if (hdr.cmd == RDMA_DESTROY_ID)
    ret = ucma_destroy_id (...);
...

Internal System States

内核通过维护系统内部状态来管理计算资源,而绝大多数的内部状态是通过 syscall 来控制的。因为 syscall 和系统状态是高度相关的,所以如果在没有构造出正确的系统内部状态下来调用 syscall,这个调用会被内核拒绝。比如最简单的系统调用 read / write 需要对一个打开的文件描述符进行操作,因此这两个 syscall 必须在调用了 open 后才能进行,否则该调用会直接被系统拒绝。

更复杂的系统调用依赖关系,不止系统调用存在依赖关系,系统调用的参数也存在着依赖关系,如下图所示,两次调用参数 arg 中的 ID 字段就应该保持一致:

DRM

为了解决该问题,HFL 会对系统调用间的顺序进行推断,该过程分为以下三个步骤:

  1. 先用静态分析工具对内核进行过程间的指向分析,得到一系列的读/写操作对,每一对读/写操作会对同一片内存区域进行操作。这样的一对读写操作被称为候选依赖对。
  2. 随后 HFL 会通过符号执行来检查每一对候选依赖对是否访问的是同一个地址,过滤可能的误报。
  3. 除了确定系统调用的顺序外,HFL 还会通过追踪追踪符号化的系统调用参数的传播来保证系统调用参数之间的依赖。

syscall sequence inference

Nested Syscall Arguments

内核中大部分系统调用的参数都是嵌套结构的,结构中的某个字段可能会指向其他的结构。以下图的代码为例,为了拷贝数据,内核需要先拷贝结构 ctrl,该结构由两个字段构成,第一个是指向真实数据段的指针,第二个则是该数据的长度;第二次拷贝,则会再拷贝对应的真实数据。

nested syscall arguments

在嵌套参数结构中,1. 对应嵌套结构的内存位置;2. 对应缓冲区的长度,这两点至关重要,为了解决对嵌套结构的参数推断,HFL 会在动态符号执行的过程中不断监控传递函数(如 copy_from_user)的调用,如果该函数被调用,则看其对应的缓冲区是否被符号化的污染。通过结合符号执行和符号状态,HFL 可以理解并恢复系统调用的嵌套参数类型对应的内存位置和相应的缓冲区长度,进而恢复出相应嵌套参数的结构。

nested syscall argument retrieval

实验评估

实验将回答以下四个问题:

  • Q1: How effective is HFL in finding kernel bugs?

  • Q2: What is the overall coverage enhancement that HFL brings over existing approaches?

  • Q3: How efficiently can HFL find bugs compared to other fuzzers?

  • Q4: What is the contribution of each feature in HFL to the overall performance?

根据不同系统的功能、与系统调用的相关性和出现漏洞的可能性,作者将内核分为了三个子系统:

Category Internal-type Syscalls used
Device drivers 32 open, ioctl, write, read
Network 20 socket, accept, bind, listen, ioctl, getsockopt, setsockopt, sendto, recvfrom, sendmsg, recvmsg
File system 6 open, read, ioctl, write, lseek

漏洞挖掘

在对几个最新的 Linux 内核进行测试后,HFL 找到了 51 个漏洞,其中 24 个是之前未发现的新漏洞,在将这些漏洞提交后,已经有 17 个漏洞被 Linux 社区确认。

Vulnerabilities

代码覆盖率

作者将 HFL 同其他内核模糊测试工具如 Moonshine 和 Syzkaller 相比较,可以看到 HFL 相比 Moonshine 和 Syzkaller,代码覆盖率分别提升了 15% 和 26%;而对比 kAFL、S2E 和 TriforceAFL,HFL 的覆盖率甚至提高了四倍:

Coverage

挖洞效率

选取 13 个 HFL 和 Syzkaller 都能发现的已知漏洞,可以看到相较于 Syzkaller 花费了超过 50 个小时,HFL 只花费了约15个小时就找到了这些漏洞,这说明 HFL 的挖洞效率更高:

Efficiency

HFL 采用的不同技术对于总体覆盖率的贡献

为了测试 HFL 采用的不同技术对模糊测试的覆盖率起到的作用,作者选取了三个测试样例: ext4、rds11 和 ppp 进行测试。

其中 F-H 表示使用混合模糊测试后的结果,F-I 表示会对间接跳转处理,F-C 表示会对系统调用顺序以及参数进行推断,F-N 表示作为基线的模糊测试结果,HL 则表示开启 HFL 全部功能后的结果。

Per Feature Effectiveness

可以看到不同功能均为模糊测试的结果有优化的作用,其中混合模糊测试对代码覆盖率贡献最大,但其他功能也有不可或缺的作用。

总结

作为第一个在 Linux 内核上进行混合模糊测试的自动化漏洞挖掘工具,HFL 无疑具有非常重要的意义。同时文章中创新地将符号执行中的符号状态等信息用于污点分析,从而获得辅助信息来反馈给 fuzzer 以继续后续输入的 mutation,也给了大家不小的启发。

参考链接