1 引言

　Linux操作系统内核在高性能服务器以及IoT设备中普遍存在. 人们生活中所使用的网络服务、智能家居、工业中的工控系统都离不开操作系统内核的强力支撑.

2020年一篇Linux内核报告^[1]指出, Linux内核的发展离不开一些实用工具如Sparse^[2]、Strace^[3]以及一些持续性的内核测试工具如Syzkaller^[4]. 近年来内核CVE^[5]缺乏标识^[6], 依然很多内核代码缺陷亟待修复.

操作系统作为直接运行在计算机硬件之上的系统软件, 具有最高的内核级的运行权限, 为系统服务程序、应用软件提供基础服务, 其漏洞可以危害整个系统的安全性、稳定性, 带来难以估量的损失, 因此对操作系统进行充分测试, 排除具有安全隐患代码, 及时修复存在bug的代码是操作系统内核开发生命周期以及后期维护阶段一项重中之重的任务.

目前, 内核模糊测试是内核空间漏洞挖掘的主要方式. 在内核模糊测试中, 用户通过内核提供的接口发送大量精心构造的数据, 通过观察内核运行状态, 使用例如KASAN等工具捕捉各种异常以此判断内核中的潜在问题. 内核模糊测试从已知最早的Tsys^[7]开始经历了从随机的内核模糊测试^[8]到类型感知的内核模糊测试^[9-14]再到基于覆盖率的内核模糊测试^[8,15–17]的发展过程. 内核模糊测试领域越来越多运用程序分析技术, 硬件特性以及仿真软件QEMU^[18]辅助内核模糊测试^{[15, 16]}的进行.

目前的内核模糊测试方案主要以系统调用为接口, 通过构造系统调用序列作为运行程序输入至内核执行. 程序运行过程中内核通过一些辅助工具如KASAN、Kmemleak等检测内核异常状态从而发现潜在bug. Linux内核提供了接近400个系统调用, 如果随机组合各种系统调用, 不仅搜索空间巨大, 而且将产生大量的无效输入. 系统调用间还存在一定的依赖关系, 这就意味着这些系统调用不能随意的组合, 而且一些特定的调用必须有前置依赖调用才能顺利执行从而达到更深的代码逻辑. 所以学习系统调用间关系, 构造更加容易被操作系统内核接收的系统调用序列、提高系统调用序列的构造质量是决定内核模糊测试取得更高效率的重要因素.

目前内核模糊测试的研究热点工具Syzkaller^[4]通过专家知识编写的系统调用模版, 给予系统调用一定的语义信息. 然后Syzkaller通过分析系统调用的资源类型信息计算系统调用选择的权重得到系统调用选择矩阵(由一个系统调用选择下一个系统调用的矩阵, 下文称选择矩阵), 通过选择矩阵随机构造系统调用序列.

Syzkaller的选择矩阵的大小是根据可生成的系统调用个数决定的, 通常可生成的系统调用个数约为2000个. 也就是在构造系统调用的过程中, 由某个系统调用扩展下一个系统调用的选择就有2000个, 这个扩展空间较大而且按照此方式构造的调用序列往往无法通过内核检验通过执行. Syzkaller通过动态修正选择矩阵, 可以增加实际通过内核运行的系统调用序列中系统调用的选择权重, 其修正方式是将出现在同一系统调用序列中的任意两两系统调用对应的选择矩阵元素的选择权重加一. 但是, 并非出现在已执行过的调用序列中的系统调用对含有依赖关系, 这种方式容易误判调用间的关系.

Syzkaller的系统调用序列构造方式是首先随机挑选第1个系统调用, 然后从左往右顺序构造. 这种构造方式存在两个问题: 1)随机构造第1个系统调用时, 每个系统调用都是被等概率选取的. 这个构造方式无法高效探索执行次数少的系统调用; 2)当根据选择矩阵构造的系统调用序列能通过内核执行时会增加选择矩阵对应的权值, 当多次使用相同的第1个系统调用构造序列时, 容易构造重复的调用序列.

在目前与系统调用序列相关的研究中, Sun等人的Healer^[19]通过覆盖率变化学习有关系的系统调用, 并构建一个关系矩阵, 以矩阵值为1代表两个系统调用有关联. 然后该方法依据该关系矩阵生成调用序列, 但是, 通过覆盖率变化分析得到有关系的调用开销较大. Moonshine^[20]通过运行Linux测试集程序, 从真实程序中提取系统调用序列, 并尽可能精简这些系统调用序列, 该工作主要提供了Syzkaller运行的高质量初始种子. 杨鑫等人提出的Dependkaller^[21]通过静态分析内核代码中共享内核数据信息的系统调用, 并通过程序信息赋予系统调用依赖权重, 该工作的静态分析容易产生误报且根据人为经验赋予权值不能客观反映调用间关系. FastSyzkaller^[22]通过N-gram模型分析触发崩溃的序列模式, 并得出触发崩溃的常见序列模式. 该工作对指导调用序列的生成并无修改.

现有工作中, 使用静态分析修正选择矩阵开销过大且存在误报漏报, 使用动态执行序列分析调用间关系更加精确但也存在执行开销过大的问题. 目前能查阅到的内核模糊测试的文献资料中, 尚未有针对系统调用序列构造存在的问题做出相应修改的工作.

本文将使用N-gram模型计算Syzkaller运行中实际执行的语料库(系统调用序列数据)中的调用间关系信息, 通过概率模型获得更加准确的调用关系信息. 然后通过N-gram模型强化初始的选择矩阵, 最后通过随机游走建图的方式构造系统调用序列, 我们希望系统调用序列在满足局部的关系依赖的同时构造更加多样的系统调用序列, 从而提高覆盖率以及漏洞发现能力. 总体来说, 我们的设计有以下特点.

(1) 采用N-gram模型收集系统调用信息. 我们将系统调用的选择抽象为自然语言模型中的词语选择, 以实际运行的系统调用动态信息通过N-gram模型进行建模, 得到系统调用间的概率分布, 通过N-gram模型选择系统调用, 使得生成的系统调用序列更长从而达到更深的代码逻辑. 并且通过N-gram模型训练结果反馈到选择矩阵生成增强系统调用选择矩阵, 通过N-gram模型和增强的系统调用选择矩阵作为生成系统调用的依据.

(2) 采用随机游走方式生成调用序列. 我们根据N-gram模型以及增强的系统调用选择矩阵以随机游走的方式进行构建无向图, 然后使用拓扑排序从无向图中选择系统调用序列, 随机游走扩展系统调用根据系统调用的IF-IDF值按概率扩展. 保证构造序列在尽可能满足依赖关系的基础上尽可能“畸形”, 并且扩展更加“重要”的系统调用. 缓解Syzkaller缺少系统调用选择的能量分配导致构造相同覆盖率的调用序列带来的效率问题.

基于以上两点, 我们在Syzkaller的基础上实现了原型工具Psyzkaller (Percentage Syzkaller), 在和Syzkaller工具的对比实验中, Psyzkaller在Linux 4.19和5.19版本的24 h实验中分别提升了15.8%、14.7%的覆盖率. 此外, 我们挖掘到了一个已知CVE (CVE-2022-3524)、8个新崩溃, 其中一个获得了CNNVD编号(CNNVD-2023-84723975).

本文第1节是引言. 第2节是背景, 主要讲述我们工作的基础工具Syzkaller的工作流程、系统调用序列构造的重要性以及N-gram模型. 第3节是方案设计, 主要讲述我们实现中3个模块的方法设计. 第4节是实现, 主要讲述我们工作的基础工具版本以及涉及的重要库文件. 第5节是实验评估, 主要从覆盖率、系统调用序列构造情况、漏洞发现能力以及额外时间开销4个方面进行工具有效性说明. 第6节是结束语.

2 背景

由于本文工作基于Syzkaller实现, 本节主要讲述Syzkaller的工作流程、系统调用序列构造重要性以及N-gram模型.

2.1 Syzkaller的工作流程

Syzkaller作为目前内核模糊测试研究的基准工具, 在Linux、Android、OpenBSD、Windows等操作系统中挖掘出的漏洞数以千计, 取得了一定的成果. 目前该工具依然在主流的内核版本持续模糊测试并将挖掘的漏洞公布在syzbot^[23]中.

如图1展示了Syzkaller系统的程序结构, 红色字体代表了对应功能的配置选项. 整体来看, Syzkaller分为两部分, 主机部分和虚拟机部分. 主机部分通过运行syz-manager来控制整个系统. syz-manager可以创建虚拟机并通过ssh进行连接. 虚拟机部分通过syz-fuzzer生成和变异的系统调用序列作为内核的输入, syz-executor将syz-fuzzer生成的系统调用序列交给内核执行. syz-fuzzer收集系统调用执行的覆盖率信息并通过RPC的方式回传给syz-manager含有新覆盖的系统调用序列或者程序崩溃信息. syz-manager将程序崩溃信息以及语料库信息存于本地数据库, 并开启了Web服务, 用户可以实时查阅Web界面查看模糊测试过程中的语料库信息、触发的崩溃等信息.

2.2 系统调用序列构造的重要性

如下代码所示的是服务端程序建立网络通讯的系统调用序列, 该序列涉及4个系统调用. 其中socket系统调用用于建立一个套接字, 该套接字用于接下来的网络通讯; bind系统调用将该套接字绑定到一个地址, 并制定一个端口号; listen系统调用, 使用该套接字监听连接请求; accept系统调用用于请求到来时的处理流程.

sock_fd = socket(AF_INET, SOCK_STREAM, o)

bind((sock_fd, &addr, sizeof(addr))

listen(sock_fd, …)

accept(sock_fd, &peer_addr, &size)

由于操作系统内核中存在“依赖”挑战^[12], 系统调用间存在关联. 在这个例子中, 由于socket调用的输出是bind、listen、accept的输入, 我们称他们具有显式关系.

Syzkaller会提供一个系统调用选择矩阵, 选择矩阵中元素的大小代表系统调用间的依赖强度, 也就是一个系统调用有多大的概率选择它的下一个系统调用. 例如, 当选取socket作为第一个系统调用时, Syzkaller将根据代表socket调用的那行矩阵元素大小, 选取下一个系统调用. 在这个例子中, 需要构造完整的网络通讯的程序逻辑, 必须根据上述所示的调用序列进行构造. 选择有效的序列并建立有效的探索路径具有重要价值.

1) 合理构造序列将排除无效输入, 增加模糊测试效率. Linux中的系统调用约有400个, 其中Syzkaller中专家知识编写的调用模版约有5000个, 排列组合的方式构造序列搜索空间巨大.

2) 一个有效且精简过后的序列, 能构成更深的代码逻辑, 挖掘更深层次的代码缺陷.

2.3 N-gram模型

N-gram模型来源于自然语言处理领域, 主要用于评估一个句子的合理性. 内核模糊测试中, 通过构造系统序列进行测试. 而系统调调用间存在依赖关系, 系统调用序列的合理性影响模糊测试效率. 我们可以通过N-gram模型使用到序列构造上以满足调用间的依赖关系构造更长的序列.

这里我们将每个系统调用看作是一个词, 假设一个系统调用序列S由T个系统调用组成:

$ {{S}} = {w_1}, {w_2}, {w_3}, \cdots , {w_{T - 1}}, {w_T} $

(1)

一个系统调用序列出现的概率为:

$ \begin{split} p(S) & = P({w_1}, {w_2}, {w_3}, \cdots , {w_{{{T - 1}}}}, {w_T}) \\ & = \prod\limits_{t = 1}^T {P({w_t}|{w_1}, {w_2}, {w_3}, \cdots , {w_{{{T - 1}}}})} \end{split} $

(2)

根据马尔可夫假设, 第n个系统调用只和前n–1个系统调用有关, 则式(2)改进为:

$ \begin{split} p(S)& = P({w_1}, {w_2}, {w_3}, \cdots , {w_{{{T - 1}}}}, {w_T}) \\ & = \prod\limits_{t = 1}^T {P({w_t}|{w_{t - n + 1}}, {w_{t - n + 2}}, \cdots , {w_{{{t - 1}}}})} \end{split} $

(3)

以bigram为例, 也就是n为2的情况, 每个系统调用仅与前一个系统调用有关联, 此时:

$ \begin{gathered} p(S) = P({w_1}, {w_2}, {w_3}, \cdots , {w_{{{T - 1}}}}, {w_T}) = \prod\limits_{t = 1}^T {P({w_t}|{w_{{{t - 1}}}})} \end{gathered} $

(4)

根据最大似然估计:

$ p(w{ _t}|{w_{t - 1}}) = \frac{{C({w_t}, {w_{t - 1}})}}{{C({w_{t - 1}})}} $

(5)

结合式(4)和式(5)可得:

$ \begin{gathered} p(S) = \prod\limits_{t = 1}^T {p({w_t}|{w_{t - 1}})} = \prod\limits_{t = 1}^T {\frac{{C({w_t},{w_{t - 1}})}}{{C({w_{t - 1}})}}} \end{gathered} $

(6)

其中, $ C({w_i}) $ 代表系统调用 $ {w_i} $ 在语料库中出现的次数. 式(6)是我们运用N-gram模型的基础.

3 方案设计

如图2所示, 我们在Syzkaller的基础上实现了我们的原型工具Psyzkaller, 其中黄色部分为原有工作, 蓝色部分为我们的增加或者改进的模块. 我们的改进主要包括3个模块: 1)语料库分析模块负责根据语料库的动态执行信息在初始选择矩阵的基础上生成调用子序列作为训练集训练N-gram模型; 2)选择矩阵增强模块负责将系统调用序列执行的动态信息反馈至初始选择矩阵得到增强的选择矩阵; 3)调用序列生成模块负责根据N-gram模型以及增强的选择矩阵采用随机游走构造调用序列.

3.1 语料分析模块

语料库分析模块通过分析语料库中的调用序列训练N-gram模型. 语料分析模块由初始语料建图、深度遍历提取子序列以及N-gram模型训练3部分组成.

(1) 初始语料库建图

初始语料来自于Syzkaller种子程序的运行得到的系统调用序列. 我们首先提取调用序列初始选择矩阵中对应的子图. 以F代表系统调用序列, 长度为T, ${w_{{n_{{i}}}}}$ 代表一个系统调用, 其中下标 $ {n_i} $ 是该调用在选择矩阵中的行(列), M为选择矩阵. 假设一个序列F为:

$ F = {w_{{n_1}}}, {w_{{n_2}}}, {w_{{n_3}}}, \cdots , {w_{{n_{T - 1}}}}, {w_{{n_T}}} $

(7)

则我们选取M的 $ {n_i} $ 行列组成的矩阵为M_sub.

也就是在初始选择矩阵中提取调用序列每个系统调用表示的行和列. 得到的子图是初始选择矩阵的若干行列组成的邻接矩阵表示, 矩阵中元素信息为系统调用的选择权重. 初始选择矩阵包含着系统调用间的静态信息, 而系统调用序列是运行的动态信息, 我们提取调用序列对应的子图是为了将动静态信息结合并为下一步遍历工作做好数据基础.

(2) 深度搜索提取子序列

从选择矩阵中构建完成子图之后, 我们从系统调用序列的起始节点深度遍历该调用序列获得潜在子序列. 资源分析通过静态分析得到的系统调用间互相选择的权重. 这个分析结果代表系统调用间可能存在联系, 语料库中的系统调用序列代表真实通过运行的序列. 我们通过实际运行的系统调用序列遍历这个静态子图, 得到潜在的子序列. 通过语料库中系统调用序列数据遍历静态子图得到的子序列含有程序的动静态信息并且可以扩展数据集. 深度遍历搜索提取算法具体步骤如下.

1) 输入F为调用序列, M_sub为由初始语料库建图得到的邻接矩阵, 用于判断系统调用节点间是否有可达的边.

2) 调用序列从未探索节点notvisit选取第一个系统调用节点syscall_i(算法1 line 17).

3) 将选取的节点作为当前系统调用节点cur (算法1 line 4).

4) 探索路径path扩展当前系统调用节点cur, 未探索节点集合notvisit去除扩展节点(算法1 line 6).

5) 如果当前系统调用节点无法扩展节点, 说明已经探索完成一条子序列, 将子序列存于S(算法1 line 8), 回到上一层递归函数(算法1 line 9).

6) 如果当前节点能继续扩展节点, 遍历notvisit节点(剩余节点), 如果syscall_i能够从当前节点到达, syscall_i作为选取节点(算法1 line 11). 进入递归(算法1 line 12).

7) 如果本层递归结束, 则进行回溯, 撤销处理结果(算法1 line 13、14).

8) 计算输出为潜在子序列集合S.

伪代码如算法1所示.

算法1. 深度遍历搜索提取序列

Input: 调用序列F、子选择矩阵M_sub.

Output: 潜在子序列S.

1. Function recursion(syscall) //递归函数

2. 　　 cur=syscall

3.　　 path.apppend(cur)

4.　　 notvisit=notvisit–cur

5.　　 if syscall don’t have successor node

6. 　　　　 S.append(path)

7.　　　　 return

8.　　 end if

9.　　 forsyscall_i in novisit can be reached from cur

10.　　　　 recursion(syscall_i)

11. 　　　　 path.erase(syscall_i)

12. 　　　　 notvisit=notvisit+syscall_i

13.　　 end for

14. end Function

15. notvisit = F

16. path= $ \scriptstyle \varnothing $ ; S= $\scriptstyle \varnothing $

17. for syscall_i in notvisit

18. 　　 recursion(syscall_i)

19. end for

深度搜索提取子序列旨在实际运行的调用序列中, 挖掘子序列. 以图3为例, 假设我们有调用序列1-2-3-4 (F), 提取的子图(M_sub)如图3所示. 则我们从系统调用结点1作为第一个节点开始在M_sub上深度遍历(算法1 line 17、18), 此时path为“1” (算法1 line 2、3). 通过for循环遍历, 从节点1能到达的节点是节点2和节点3, 我们首先选择节点2, 进入递归函数, 此时path为“1-2” (算法1 line 2、3). 以2为当前节点只能探索到节点4 (算法1 line 9), 所以以系统调用节点4进入递归函数后, 终止条件(算法1 line 5)满足, 得到一条子序列“1-2-4” (算法1 line 6). 然后回溯至节点2, path为“1-2” (算法1 line 11) 由于其可达节点(4)已经探索完, for循环结束, 所以继续回溯至节点1, 此时path为“1” (算法1 line 11). 接着从未探索的可达节点3开始探索, 同理可以探索“1-3-2”“1-3-4”两条子序列. 接着我们分别以2、3、4为第1个节点开始探索(算法1 line 17、18), 按照这样的规则, 我们提取的潜在子序列有“1-2-4”“1-3-4”“1-3-2-4”“2-4”“2-1-3-4”“3-2-4”“3-4”.

(3) N-gram模型训练

N-gram模型来源于自然语言处理领域, 相关的背景知识在第2节中已经阐述. 由于在我们的使用场景中, 系统调用序列语料库中的数量为数万之内, 无法支撑复杂的深度学习模型以及N值较大的N-gram模型训练; 而且, 在我们的实验中, 语料库调用序列长度为2的调用序列占比最大, 我们采取n=2的bigram模型进行训练. N-gram模型训练的具体算法如下.

1) 输入S为潜在子序列.

2) 遍历每个子序列.

3) 在每个子序列中, 提取相邻的两个系统调用, 并使用二维hash存储(算法2 line 5、7), 哈希表的两个维度分别是两个关联系统调用标号(callnum)(Psyzkaller对可生成的系统调用的标记), 数值大小为出现次数.

4) 语料库数据增加100条开始训练.

5) 计算输出为bigram模型N.

伪代码如算法2.

算法2. N-gram模型训练

Input: 潜在子序列S.

Output: N//N-gram模型.

1. N= $\scriptstyle \varnothing$ //N为二维哈希表

2. for each s in S

3. 　　 for iin range (1, s.length–1)

4.　　　　 if N[s[i].callnum][s[i–1].callnum]==0

5. 　　　　　　 N[s[i].callnum][s[i–1].callnum]=1

6. 　　　　 else

7. 　　　　　　 N[s[i].callnum][s[i–1].callnum]++

8.　　　　 end if

9. 　　 end for

10. end for

通过N-gram模型的训练, 我们得到强相关的调用序列对以及某个系统调用选择下一个的概率, 根据大数定律, 出现次数足够多的调用对的依赖关系可能更强. 在构造系统调用序列的过程中, 我们根据模型训练得到的数据依概率选取系统调用, 更容易构造出长序列.

3.2 选择矩阵增强模块

选择矩阵增强模块的目的在于将系统调用序列动态信息和初始的选择矩阵相结合, 使得选择矩阵包含系统调用的静态信息以及其运行的动态信息, 更加客观合理地反映系统调用间的关系. 选择矩阵增强的算法具体步骤如下.

1) 输入N为N-gram模型, 输入M为选择矩阵.

2) 遍历N-gram模型的第1个维度N[i], i代表系统调用标号, N[i]代表与i系统调用相关的所有系统调用集合.

3) 如果N-gram模型中, i、j系统调用有关联, 也就是N[i][j]不为零, 则sum对应增加初始矩阵的权值M[i][j] (算法3 line 5、6).

4) 增加出现i、j系统调用的选择权值, 对于M[i]中的值, 如果N[i][j]有值, 则M'[i][j]计算为M[i][j]+sum*(N[i][j]/N[i][*]), 其中N[i][*]为N[i]行的数值之和(算法3 line 10、11).

5) 计算输出为M'.

伪代码如算法3所示.

算法3. 选择矩阵增强

Input: N-gram模型N、选择矩阵M.

Output: 增强矩阵M'.

1. for n_i in N //n_i为系统调用标号i所在哈希表n_i=N[i]

2. 　　 M[i]←M//M中系统标号为i的行

3. 　　 sum=0

4.　　 for j in range len(n_i)

5.　　　　 ifN[i][j]!=0

6.　　　　　　 sum+=M[i][j]

7. 　　　　 end if

8.　　 end for

9. 　　 for val in range M[i]

10. 　　　 ifN[i][j]!=0

11.　　　　　 M'[i][j]=val+sum*(N[i][j]/N[i][*])

12. 　　　 end if

13. 　 end for

14. end for

由于我们采用了N-gram模型关注于相邻调用的关系, 原系统的增加调用序列任意两个调用间的动态更新选择矩阵的方案不再适用. 我们采用N-gram模型信息更新选择矩阵. 我们的增强算法保障无N-gram模型数据的调用的相对权重不变(算法3 line 10), 此外我们根据N-gram模型数据再分配调用的选择权重(算法3 line 11). 该算法经模拟迭代验证能将选择矩阵中的系统调用的选择权重收敛至该调用对应的N-gram权重大小.

3.3 调用序列生成模块

TF-IDF (term frequency-inverse document frequency)值的大小代表一个系统调用的“关键性”, 其在语料库中越少出现其值就越高, 而一个在语料越少出现的系统调用, 从该调用扩展将更可能增加覆盖率. 而采取随机游走的方式, 能产生更多样且“畸形”的调用序列.

使用增强选择矩阵一定程度上保障系统调用满足依赖条件, 模糊测试往往需要较为“畸形”的输入. Syzkaller中采取随机生成第1个系统调用, 往后逐个构造的方式构造调用序列, 这种方式容易选择相同的第1个调用, 从前往后生成调用序列容易产生重复的调用序列. 因此我们在调用序列生成部分做了一些修改. 首先我们按照语料库出现系统调用的情况, 首先选择语料库更少出现的系统调用, 然后随机游走建图, 扩展TF-IDF值更高的系统调用. 最后拓扑排序生成具有依赖关系的一个调用序列.

原始Syzkaller随机选取第1个系统调用, 然后向后生成随机的系统调用. 随机选取第一个系统调用缺乏能量分配策略. 当其使用某个系统调用作为第1个系统调用构造序列并长时间的fuzz后, 该系统调用相关的覆盖率将趋于饱和. 因此我们统计每个系统调用在语料库出现的次数, 将更多的能量赋予更少出现的系统调用中. 从前往后生成的构造方式中, 容易生成相同的调用序列, 所以我们采取随机游走的方式构建系统调用序列.

我们的工作不是完全的随机游走, 构造序列过程中, 我们计算构造序列中的TF-IDF权值, 以下公式 $ {w_i} $ 代表一个系统调用, $ \left| S \right| $ 代表语料库中所有的序列个数, 其计算公式如下:

$ T{F_i} = \frac{{{w_i}}}{{\displaystyle\sum\limits_{t = 1}^T {{w_t}} }} $

(8)

TF为某个系统调用在本次构造中出现的频率:

$ ID{F_i} = \log \frac{{\left| S \right|}}{{\left| {\{ {w_i} \in {S_i}\} + 1} \right|}} $

(9)

IDF为该系统调用在整个语料库中出现的逆频率值. TF-IDF权值更大代表该系统调用在整个语料库中出现更少, 更可能是比较“关键”的系统调用将有更大的概率被扩展.

调用序列生成的具体步骤如下.

1) 输入N为N-gram模型, M'为增强选择矩阵, L为构建序列长度.

2) 根据每个系统调用在语料库中的出现次数, 按概率选择第1个更少出现系统调用, G扩展该调用(算法4 line 3), 其中G中节点表示系统调用, 其有向边表示两个系统调用存在选择关系.

3) 计算G中调用序列的TF-IDF值, TF-IDF值更高, 代表该系统调用C'在所有语料库中更重要, 将有更大概率被扩展(算法4 line 6).

4) 选择该调用前向或者后向进行插入(算法4 line 7), 根据 $ \varepsilon = 0.3 $ 的概率使用增强选择矩阵M'(算法4 line 8), 0.7的概率使用N-gram模型扩展(算法4 line 9). 扩展得到扩展的调用C'', 调用C''导入G中. 重复步骤3).

5) 将G拓扑排序, 生成长度为L的系统调用序列P(算法4 line 11).

6) 计算输出为L长度的系统调用序列P.

伪代码描述如算法4所示.

算法4. 调用序列生成算法

Input: N-gram模型N、增强选择矩阵M'、构建序列长度L.

Output: 系统调用序列P.

1. $\scriptstyle \varepsilon = 0.3 $

2. list= $\scriptstyle \varnothing$

3. choose first system C call with energy and G appendC

4. list.append(C), G.append(C)

5. while(list.size<L)

6.　　 select one call C'in G by TF-IDF value

7. 　　choose a direction forward or backward to append C'and G appendC'

8. 　　it has the $\scriptstyle \varepsilon $ probability to use the M' to append the G

9. 　　it has the $\scriptstyle 1 - \varepsilon $ probability to use the N to append G

10. end while

11. P= TopoSort(G) //拓扑排序

我们通过N-gram模型训练得到出现更频繁的系统调用对信息. 这个信息在生成长系统调用序列时更有优势, 如在生成第2.2节所示的网络通讯系统调用时, 使用N-gram模型扩展将更大概率生成该系统调用序列, 探索更深层次的内核代码逻辑.

4 实现

基于Syzkaller的5bc3be51提交版本实现了Psyzkaller, 总共编写约2200行的go代码实现上述算法, 引用了go语言实现的TF-IDF库^[24].

5 实验评估

为了验证改进工作的有效性, 我们通过Psyzkaller和Syzkaller在Linux内核4.19、5.19版本的覆盖率、语料库中的系统调用序列分布情况、触发崩溃个数、以及Psyzkaler的额外时间开销来说明我们工具的有效性. 我们的实验评估主要回答以下4个问题.

1) Psyzkaller的覆盖率如何?

2) Psyzkaller系统调用序列的构造情况如何?

3) Psyzkaller的漏洞发现能力如何, 有无发现真实的漏洞?

4) Psyzkaller的额外时间开销如何?

5.1 实验设置

我们实验运行在Intel(R) Xeon(R) Gold 5218 @ 2.30 GHz的CPU、128 GB内存、Ubuntu 20.04的环境中, Psyzkaller以及Syzkaller在相同内核配置下运行24 h三次取平均整值作为实验数据. 由于与我们工作强相关的工作中, Dependkaller并未提供源码, Moonshine在种子精简上做工作, Healer基于旧版本的Syzkaller且缺乏更新, 经我们测试其实验效果并不我们选取的的基准Syzkaller效果好, 所以我们的工作只和Syzkaller做比较. 由于5.19是5.x向6.x过渡的测试版本, 5.x的旧版本特性和6.x的新特性都可以在该内核代码中有所体现, 所以我们选取5.19版本的内核作为测试内核. 为了说明我们的工具的相同时间内能触发更多的内核崩溃, 我们选取4.19版本内核作为测试内核.

5.2 覆盖率对比

Syzkaller通过将程序运行的trace中的相邻的PC (programer counter)值也就是程序运行经过的相邻地址做个哈希作为边覆盖信息. 我们沿用了这个边覆盖统计信息. 在24 h实验中, 如图4、图5所示, Psyzkaller的边覆盖率对比Syzkaller在内核4.19、5.19版本中分别提升了15.8%、14.7%的覆盖率. 其中在5.19版本增加的覆盖率主要分布在net文件中当中, 表1展示这些覆盖率差额.

我们进一步探索了Linux内核net模块已覆盖部分的调用序列情况, 其调用序列长度多为2个及以上. 构造2个调用长度以及长序列是使用N-gram模型扩展系统调用的优势.

5.3 系统调用序列分布情况

内核模糊测试会将触发新覆盖或者触发崩溃的系统调用序列加入语料库, 精简后的语料库的调用序列信息能说明Psyzkaller通过序列学习的方式构造序列的有效性. 我们以在Linux 5.19模糊测试得到的语料库为例, 图6为系统调用序列长度分布情况, 其长度分布在1–20之中, 其中长度为2的系统调用序列最多.

Psyzkaller生成了系统调用序列8254个, Syzkaller生成有效序列6860个, Psyzkaller生成的系统调用序列高于Syzkaller约20.3%. 由于Psyzkaller将调用序列及其参数信息作哈希统计序列个数, 相同的调用序列不同的参数会被视为不同的序列, 我们的方法没有对参数构造部分进行修改, 因此, 我们统计构造参数无关的序列个数, 如表2所示. 在我们的实验中, Psyzkaller生成的参数无关的序列个数为4707个, 比Syzkaller多约26.5%. 可以看出我们的工具通过系统调用学习的方式构造系统调用序列取得了一定的效果.

FastSyzkaller^[22]指出, 5个系统调用长度的调用序列是最容易触发崩溃的模式, 因此我们以5个系统调用为界, 视5个及以上系统调用序列为长序列. 我们的实验数据中(表3), Psyzkaller生成了381个长序列, 比Syzkaller生成的长序列多约101.6%, 可以看出Psyzkaller使用序列学习的方式在生成长序列方面占有优势, 能够探索更深的程序逻辑.

5.4 漏洞发现能力

我们以相同时间内在相同版本内核中触发的崩溃数量以及是否发现新崩溃作为漏洞发现能力的度量标准. syzbot是Syzkaller进行持续测试且汇报崩溃的平台, 使用Syzkaller相关工具的安全研究者在挖掘内核漏洞后将漏洞报送给内核相关维护者的同时会将bug崩溃信息抄送至Syzkaller讨论社区, 通过检索syzbot、Syzkaller社区邮件以及在CVE查询相关内核漏洞描述信息可以判断Psyzkaller触发的崩溃是否是最新的. Psyzkaller发现了一个已知CVE、8个新崩溃, 我们将这8个崩溃信息提交给内核维护者的同时也与syzbot发布的已有内核CVE的崩溃信息进行比对, 确认它们都是新的. 我们对8个新崩溃中一个完成分析且稳定触发的漏洞提交至国家信息安全漏洞库并获得了CNNVD编号, 该漏洞已经完成研判并被评级为中危. 由于操作系统内核的复杂性, 相同的系统调用序列以及调用参数在不同的内核状态下运行会有不一样的运行结果, 这让复现崩溃构造PoC变得更加困难, 所以我们挖掘的8个新崩溃中, 7个新崩溃目前在构造PoC阶段, 如表4所示.

这里我们以我们提交的CNNVD-2023-84723975为例子, 展示该漏洞的调用栈. 其中$KERNEL代表Linux主目录.

ipv6_flowlabel_opt ( $KERNEL/net/ipv6/ip6_flowlabel.c)

do_ipv6_setsockopt.constprop.0 ($KERNEL/net/ipv6/ipv6_sockglue.c)

ipv6_setsockopt ($KERNEL/net/ipv6/ipv6_sockglue.c)

sock_common_setsockopt ($KERNEL/net/core/sock.c)

__sys_setsockopt ($KEENEL/net/socket.c)

__x64_sys_setsockopt ($KERNEL/net/socket.c)

do_syscall_64 ($KERNEL/arch/x86/entry/common.c)

entry_SYSCALL_64_after_hwframe ($KERNEL/arch/x86/entry/entry_64.S)

该崩溃的调用序列如下所示.

r0 = socket$inet6()

bind$inet6(r0, …)

setsockopt$inet6_IPV6_FLOWLABEL_MGR(r0, …)

setsockopt$inet6_group_source_req(r0, …)

该例子和第2.2节中所示例子类似, 这些系统调用间具有较强关联关系, 构造序列时如果使用增强选择矩阵拓展能强化出现的两两系统调用的选择权重, 如果根据N-gram模型拓展调用将有更大概率生成出该调用序列并更快到达变异环节得到崩溃.

在Linux 4.19版本24 h的模糊测试过程中, Psyz-kaller触发了42个崩溃, Syzkaller触发了35个崩溃. 表5显示了部分崩溃的具体信息.

Psyzkaller在5.19版本挖掘了1个已知CVE, 8个新崩溃, 其中一个新崩溃成功获得CNNVD编号并被评级为中危; 在4.19版本24 h的模糊测试过程中能触发更多的崩溃.

5.5 额外时间开销

我们引入了3个模块, 需要计算系统调用序列的TF-IDF值, 训练N-gram模型, 以及以不同的构造方式构造系统调用. 本节将说明这些工作的时间开销. 我们从Linux 4.19进行模糊测试得到的语料库中随机抽取100、500、10000、20000个语料库作为实验数据.

Syzkaller的动态修正方案首先遍历语料库数据, 然后使用两层for循环增加任意两两系统调用序列的权重. 其时间开销如表6所示. 随着料库数量的增加, 其算法时间复杂度开销差别为毫秒级别.

表7展示了语料库大小分别为500、10000、20000统计计算TF-IDF值的时间开销情况. 可以看出尽管语料大小为20000, TF-IDF计算的开销也只有2 s左右.

由于我们训练N-gram模型每新增100个语料进行计算, 所以这里我们统计100个语料库的训练时间开销. 表8实验数据显示我们N-gram模型增量训练开销非常小.

从Syzkaller的动态修正方案的时间开销, 以及我们更改该方案引入的TF-IDF计算以及N-gram模型增量开销, 可以看出, 我们Psyzkaller改进方案所使用的额外时间开销很小. 由于我们改变了系统调用构造方式, 表9展示了在语料库大小为20000的信息基础上, 使用Syzkaller构造方案以及Psyzkaller构造方案在生成长度为2、12的时间对比情况. 根据系统调用长度分布图, 长度为2的调用序列占比最高, 我们将长度2以及图6所示长序列分布的中位数12分别作为最常见的序列以及长序列的代表进行实验.

实验数据表明, 我们的构造方式在短序列的构造方式上相差不大, 长序列的构造时间开销虽然接近原方案开销的2倍, 但其开销成本也只多了约0.4 ms. 综合以上Psyzkaller的开销实验说明, Psyzkaller的额外开销很小, 完全不影响模糊测试进程.

6 相关工作

目前, 国内外很多工作基于Syzkaller展开. Sun等人的Healer^[19]通过覆盖率变化学习有关系的系统调用, 并通过构建一个关系矩阵, 以矩阵值为1代表两个系统调用有关联, 并通过该关系矩阵生成调用序列, 达到了一定的效果. Moonshine^[20]通过运行Linux测试集程序, 从真实程序中提取系统调用序列, 并尽可能精简这些系统调用序列, 为Syzkaller提供了初始的种子序列达到了覆盖率提升的效果. 杨鑫等人提出的Denpendkaller^[21]通过静态分析内核代码中共享内核数据信息的系统调用, 并通过程序信息赋予系统调用依赖权重相较于Syzkaller提升了覆盖率以及漏洞挖掘能力. FastSyzkaller^[22]通过N-gram模型分析触发崩溃的序列模式, 并得出触发崩溃的常见序列模式.

除此以外, DIFUZE^[25]通过提取内核驱动信息, 在7个安卓系统上发现了32个之前的未知漏洞; Razzer^[26]通过修改Hypervisor以及加入断点旨在发掘竞争漏洞SLAKE^[27]通过动静态结合分析内核重要数据结构, 并利用slab内存分配器挖掘内核漏洞; HFL^[28]通过模糊测试结合符号执行进行内核模糊测试; Kafl^[17]借助因特尔的CPU硬件特性进行模糊测试; IntellliGen^[29]通过自动化的方法构建驱动测试; Diskaller^[30]通过覆盖率引导以并行方式进行漏洞挖掘从而提升效率; TriforceAFL^[15]在AFL的基础上使用QEMU工具对系统进行全模拟, 通过在QEMU模拟的CPU中一个特殊的指令aflCall(0f24)实现对操作系统进行模糊测试; TriforceLinuxSyscallFuzzer^[31]在TriforceAFL的基础上对系统调用进行模糊测试. 施鹤远等人^[32]详细介绍了使用覆盖率引导的Fuzzing技术来测试企业级Linux内核的实践经验, 包括测试框架的设计与实现、测试用例的生成和筛选、测试效果的评估和反馈等方面. Krace是一项针对内核文件系统的数据竞争模糊测试技术的研究工作. Krace^[33]利用一种名为“Syscall Fuzzing”的技术来生成用于测试文件系统的系统调用序列, 并使用一种名为“K-Mutation”的技术来对这些系统调用进行变异, 以生成不同的测试用例. 此外, Krace还使用了一种名为“事件排序”的技术来控制测试用例的执行顺序, 以便尽可能多地发现数据竞争问题. GREBE^[34]通过 LLVM 静态分析内核数据结构, 以及污点分析 syzbot中的60个含有PoC的漏洞, 探索了这些 PoC 附近的程序漏洞, 提高了原有漏洞的可利用性. Dependency^[12]通过改写内核模糊测试工具Syzkaller和静态分析工具Dr.Check对内核的4个模块进行模糊测试, 然后通过人工分析出了造成内核模糊测试依赖挑战的5个根本原因.

7 结束语

操作系统内核空间的稳定安全是维护网络空间安全稳定的一项重中之重的内容. 内核模糊测试是一种高效的漏洞挖掘工具, 能够精准发现内核空间的潜在安全隐患. 本文设计了一种基于系统调用序列学习的模糊测试方案. 通过真实运行的系统调用序列数据训练N-gram模型, 挖掘系统调用关系, 并通过该信息指导生成系统调用序列. 整体来看, 我们的工作在4.19 和 5.19 的内核版本中分别提升了 15.8%、14.7% 的覆盖率, 发现了8个新崩溃. 内核模糊测试仍然存在许多工作值得研究, 将来的工作中, 我们将进行系统调用序列构造与参数选取相关的研究, 进一步提升内核模糊测试的效率以及效果.