基于系统调用序列学习的内核模糊测试.pdf

基于系统调用序列学习的内核模糊测试张阳1,2,范俊杰1,2,孙晓山1,2,张颖君1,2,程亮1,21(中国科学院大学,北京100049)2(中国科学院软件研究所可信计算与信息保障实验室,北京100190)通信作者:程亮,E-mail:摘要:操作系统内核是计算机系统中最基本的软件组件,它控制和管理计算机硬件资源,并提供访问和管理其他应用程序所需的接口和服务.操作系统内核的安全性直接影响整个计算机系统的稳定性和可靠性.内核模糊测试是一种高效、准确的安全漏洞检测方法.然而目前内核模糊测试工作中,存在系统调用间关系的计算开销过大且容易误判,以及系统调用序列构造方式缺乏合理能量分配以至于很难探索低频系统调用的问题.本文提出以 N-gram模型学习系统调用间关系,根据系统调用的出现频次信息和 TF-IDF 信息优先探索出现频次低或者 TF-IDF 值高的系统调用.我们以极低的开销,在 Linux4.19 和 5.19 版本的 24h 实验中分别提升了 15.8%、14.7%的覆盖率.此外,我们挖掘到了一个已知 CVE(CVE-2022-3524)、8 个新崩溃,其中一个获得了 CNNVD 编号(CNNVD-2023-84723975).关键词:内核模糊测试;N-gram;TF-IDF;系统安全;系统调用引用格式:张阳,范俊杰,孙晓山,张颖君,程亮.基于系统调用序列学习的内核模糊测试.计算机系统应用,2023,32(9):1931.http:/www.c-s- Fuzzing Based on System Call Sequence LearningZHANGYang1,2,FANJun-Jie1,2,SUNXiao-Shan1,2,ZHANGYing-Jun1,2,CHENGLiang1,21(UniversityofChineseAcademyofSciences,Beijing100049,China)2(TrustedComputingandInformationAssuranceLaboratory,InstituteofSoftware,ChineseAcademyofSciences,Beijing100190,China)Abstract:Theoperatingsystemkernelisthemostfundamentalsoftwarecomponentinacomputersystem.Itcontrolsandmanagescomputerhardwareresourcesandprovidesinterfacesandservicesnecessaryforaccessingandmanagingotherapplications.Thesecurityoftheoperatingsystemkerneldirectlyaffectsthestabilityandreliabilityoftheentirecomputersystem.Kernelfuzzingisanefficientandaccuratesecurityvulnerabilitydetectionmethod.However,incurrentkernelfuzzingwork,theoverheadofcalculatingtherelationshipbetweensystemcallsistoohigh,oritiseasytomisjudgetherelationshipbetweensystemcalls.Inaddition,theexistingmethodforconstructingsystemcallsequenceslacksreasonableenergyallocation,makingitdifficulttoexploreproblemsoflow-frequencysystemcalls.ThisstudyproposestolearntherelationshipbetweensystemcallsbyusinganN-grammodelandprioritizetheexpansionofsystemcallswithlowfrequencyorhighTF-IDFvaluesbasedonthefrequencyandTF-IDFinformationofsystemcalloccurrences.Withminimaloverhead,thisstudyachievesacoverageincreaseof15.8%and14.7%in24-hourexperimentsonLinuxversions4.19and5.19,respectively.Besides,oneknownCVE(CVE-2022-3524)andeightnewcrashesarediscovered,oneofwhichisnumberedCNNVD(CNNVD-2023-84723975).Key words:kernelfuzzing;N-gram;TF-IDF;systemsecurity;systemcall计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(9):1931doi:10.15888/ki.csa.009218http:/www.c-s-中国科学院软件研究所版权所有.Tel:[phone]基金项目:国家自然科学基金(62072448)收稿时间:2023-02-17;修改时间:2023-03-14;采用时间:2023-03-30;csa 在线出版时间:2023-07-14CNKI 网络首发时间:2023-07-17SpecialIssue专论综述191引言Linux 操作系统内核在高性能服务器以及 IoT设备中普遍存在.人们生活中所使用的网络服务、智能家居、工业中的工控系统都离不开操作系统内核的强力支撑.2020 年一篇 Linux 内核报告1指出,Linux 内核的发展离不开一些实用工具如 Sparse2、Strace3以及一些持续性的内核测试工具如 Syzkaller4.近年来内核CVE5缺乏标识6,依然很多内核代码缺陷亟待修复.操作系统作为直接运行在计算机硬件之上的系统软件,具有最高的内核级的运行权限,为系统服务程序、应用软件提供基础服务,其漏洞可以危害整个系统的安全性、稳定性,带来难以估量的损失,因此对操作系统进行充分测试,排除具有安全隐患代码,及时修复存在 bug 的代码是操作系统内核开发生命周期以及后期维护阶段一项重中之重的任务.目前,内核模糊测试是内核空间漏洞挖掘的主要方式.在内核模糊测试中,用户通过内核提供的接口发送大量精心构造的数据,通过观察内核运行状态,使用例如 KASAN 等工具捕捉各种异常以此判断内核中的潜在问题.内核模糊测试从已知最早的 Tsys7开始经历了从随机的内核模糊测试8到类型感知的内核模糊测试914再到基于覆盖率的内核模糊测试8,1517的发展过程.内核模糊测试领域越来越多运用程序分析技术,硬件特性以及仿真软件 QEMU18辅助内核模糊测试15,16的进行.目前的内核模糊测试方案主要以系统调用为接口,通过构造系统调用序列作为运行程序输入至内核执行.程序运行过程中内核通过一些辅助工具如 KASAN、Kmemleak 等检测内核异常状态从而发现潜在 bug.Linux 内核提供了接近 400 个系统调用,如果随机组合各种系统调用,不仅搜索空间巨大,而且将产生大量的无效输入.系统调用间还存在一定的依赖关系,这就意味着这些系统调用不能随意的组合,而且一些特定的调用必须有前置依赖调用才能顺利执行从而达到更深的代码逻辑.所以学习系统调用间关系,构造更加容易被操作系统内核接收的系统调用序列、提高系统调用序列的构造质量是决定内核模糊测试取得更高效率的重要因素.目前内核模糊测试的研究热点工具 Syzkaller4通过专家知识编写的系统调用模版,给予系统调用一定的语义信息.然后 Syzkaller 通过分析系统调用的资源类型信息计算系统调用选择的权重得到系统调用选择矩阵(由一个系统调用选择下一个系统调用的矩阵,下文称选择矩阵),通过选择矩阵随机构造系统调用序列.Syzkaller 的选择矩阵的大小是根据可生成的系统调用个数决定的,通常可生成的系统调用个数约为2000 个.也就是在构造系统调用的过程中,由某个系统调用扩展下一个系统调用的选择就有 2000 个,这个扩展空间较大而且按照此方式构造的调用序列往往无法通过内核检验通过执行.Syzkaller 通过动态修正选择矩阵,可以增加实际通过内核运行的系统调用序列中系统调用的选择权重,其修正方式是将出现在同一系统调用序列中的任意两两系统调用对应的选择矩阵元素的选择权重加一.但是,并非出现在已执行过的调用序列中的系统调用对含有依赖关系,这种方式容易误判调用间的关系.Syzkaller 的系统调用序列构造方式是首先随机挑选第 1 个系统调用,然后从左往右顺序构造.这种构造方式存在两个问题:1)随机构造第 1 个系统调用时,每个系统调用都是被等概率选取的.这个构造方式无法高效探索执行次数少的系统调用;2)当根据选择矩阵构造的系统调用序列能通过内核执行时会增加选择矩阵对应的权值,当多次使用相同的第 1 个系统调用构造序列时,容易构造重复的调用序列.在目前与系统调用序列相关的研究中,Sun 等人的 Healer19通过覆盖率变化学习有关系的系统调用,并构建一个关系矩阵,以矩阵值为 1 代表两个系统调用有关联.然后该方法依据该关系矩阵生成调用序列,但是,通过覆盖率变化分析得到有关系的调用开销较大.Moonshine20通过运行 Linux 测试集程序,从真实程序中提取系统调用序列,并尽可能精简这些系统调用序列,该工作主要提供了 Syzkaller 运行的高质量初始种子.杨鑫等人提出的 Dependkaller21通过静态分析内核代码中共享内核数据信息的系统调用,并通过程序信息赋予系统调用依赖权重,该工作的静态分析容易产生误报且根据人为经验赋予权值不能客观反映调用间关系.FastSyzkaller22通过 N-gram 模型分析触发崩溃的序列模式,并得出触发崩溃的常见序列模式.该工作对指导调用序列的生成并无修改.现有工作中,使用静态分析修正选择矩阵开销过计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第9期20专论综述SpecialIssue大且存在误报漏报,使用动态执行序列分析调用间关系更加精确但也存在执行开销过大的问题.目前能查阅到的内核模糊测试的文献资料中,尚未有针对系统调用序列构造存在的问题做出相应修改的工作.本文将使用 N-gram 模型计算 Syzkaller 运行中实际执行的语料库(系统调用序列数据)中的调用间关系信息,通过概率模型获得更加准确的调用关系信息.然后通过 N-gram 模型强化初始的选择矩阵,最后通过随机游走建图的方式构造系统调用序列,我们希望系统调用序列在满足局部的关系依赖的同时构造更加多样的系统调用序列,从而提高覆盖率以及漏洞发现能力.总体来说,我们的设计有以下特点.(1)采用 N-gram 模型收集系统调用信息.我们将系统调用的选择抽象为自然语言模型中的词语选择,以实际运行的系统调用动态信息通过 N-gram 模型进行建模,得到系统调用间的概率分布,通过 N-gram 模型选择系统调用,使得生成的系统调用序列更长从而达到更深的代码逻辑.并且通过 N-gram 模型训练结果反馈到选择矩阵生成增强系统调用选择矩阵,通过 N-gram 模型和增强的系统调用选择矩阵作为生成系统调用的依据.(2)采用随机游走方式生成调用序列.我们根据 N-gram 模型以及增强的系统调用选择矩阵以随机游走的方式进行构建无向图,然后使用拓扑排序从无向图中选择系统调用序列,随机游走扩展系统调用根据系统调用的 IF-IDF 值按概率扩展.保证构造序列在尽可能满足依赖关系的基础上尽可能“畸形”,并且扩展更加“重要”的系统调用.缓解 Syzkaller 缺少系统调用选择的能量分配导致构造相同覆盖率的调用序列带来的效率问题.基于以上两点,我们在 Syzkaller 的基础上实现了原型工具 Psyzkaller(PercentageSyzkaller),在和 Syz-kaller 工具的对比实验中,Psyzkaller 在 Linux4.19 和5.19 版本的 24h 实验中分别提升了 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 等操作系统中挖掘出的漏洞数以千计,取得了一定的成果.目前该工具依然在主流的内核版本持续模糊测试并将挖掘的漏洞公布在 syzbot23中.如图 1 展示了 Syzkaller 系统的程序结构,红色字体代表了对应功能的配置选项.整体来看,Syzkaller 分为两部分,主机部分和虚拟机部分.主机部分通过运行syz-manager 来控制整个系统.syz-manager 可以创建虚拟机并通过 ssh 进行连接.虚拟机部分通过 syz-fuzzer生成和变异的系统调用序列作为内核的输入,syz-executor 将 syz-fuzzer 生成的系统调用序列交给内核执行.syz-fuzzer 收集系统调用执行的覆盖率信息并通过 RPC 的方式回传给 syz-manager 含有新覆盖的系统调用序列或者程序崩溃信息.syz-manager 将程序崩溃信息以及语料库信息存于本地数据库,并开启了 Web服务,用户可以实时查阅 Web 界面查看模糊测试过程中的语料库信息、触发的崩溃等信息.syz-managerdir/crashes/chrash N-Tdir/corpus/*workdir:dirhttp:urlsshkey:filesshdsyz-executorsyz-fuzzerVM managementsyscallscoverage infoinputs/syz/kernel/debug/kcovRPCVMinodescp,sshvmlinux:filekernel:file图 1Syzkaller 流程图 2.2 系统调用序列构造的重要性如下代码所示的是服务端程序建立网络通讯的系统调用序列,该序列涉及 4 个系统调用.其中 socket系统调用用于建立一个套接字,该套接字用于接下来2023年第32卷第9期http:/www.c-s-计 算 机 系 统 应 用SpecialIssue专论综述21的网络通讯;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=w1,w2,w3,wT1,wT(1)一个系统调用序列出现的概率为:p(S)=P(w1,w2,w3,wT1,wT)=Tt=1P(wt|w1,w2,w3,wT1)(2)根据马尔可夫假设,第 n 个系统调用只和前 n1个系统调用有关,则式(2)改进为:p(S)=P(w1,w2,w3,wT1,wT)=Tt=1P(wt|wtn+1,wtn+2,wt1)(3)以 bigram 为例,也就是 n 为 2 的情况,每个系统调用仅与前一个系统调用有关联,此时:p(S)=P(w1,w2,w3,wT1,wT)=Tt=1P(wt|wt1)(4)根据最大似然估计:p(wt|wt1)=C(wt,wt1)C(wt1)(5)结合式(4)和式(5)可得:p(S)=Tt=1p(wt|wt1)=Tt=1C(wt,wt1)C(wt1)(6)C(wi)wi其中,代表系统调用在语料库中出现的次数.式(6)是我们运用 N-gram 模型的基础.3方案设计如图 2 所示,我们在 Syzkaller 的基础上实现了我们的原型工具 Psyzkaller,其中黄色部分为原有工作,蓝色部分为我们的增加或者改进的模块.我们的改进主要包括 3 个模块:1)语料库分析模块负责根据语料库的动态执行信息在初始选择矩阵的基础上生成调用子序列作为训练集训练 N-gram 模型;2)选择矩阵增强模块负责将系统调用序列执行的动态信息反馈至初始选择矩阵得到增强的选择矩阵;3)调用序列生成模块负责根据 N-gram 模型以及增强的选择矩阵采用随机游走构造调用序列.corpus 语料库模型学习数据输入系统调用选择矩阵执行信息动态修正系统调用序列调用信息生成语料库分析模块选择矩阵增强模块调用序列生成模块123syz-managerRPCscp,sshinvokesshdVMsyz-fuzzercoverage infokernelinputsyz-executor图 2Psyzkaller 流程图计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第9期22专论综述SpecialIssue 3.1 语料分析模块语料库分析模块通过分析语料库中的调用序列训练 N-gram 模型.语料分析模块由初始语料建图、深度遍历提取子序列以及 N-gram 模型训练 3 部分组成.(1)初始语料库建图wnini初始语料来自于 Syzkaller 种子程序的运行得到的系统调用序列.我们首先提取调用序列初始选择矩阵中对应的子图.以 F 代表系统调用序列,长度为T,代表一个系统调用,其中下标 是该调用在选择矩阵中的行(列),M 为选择矩阵.假设一个序列F 为:F=wn1,wn2,wn3,wnT1,wnT(7)ni则我们选取 M 的 行列组成的矩阵为 Msub.也就是在初始选择矩阵中提取调用序列每个系统调用表示的行和列.得到的子图是初始选择矩阵的若干行列组成的邻接矩阵表示,矩阵中元素信息为系统调用的选择权重.初始选择矩阵包含着系统调用间的静态信息,而系统调用序列是运行的动态信息,我们提取调用序列对应的子图是为了将动静态信息结合并为下一步遍历工作做好数据基础.(2)深度搜索提取子序列从选择矩阵中构建完成子图之后,我们从系统调用序列的起始节点深度遍历该调用序列获得潜在子序列.资源分析通过静态分析得到的系统调用间互相选择的权重.这个分析结果代表系统调用间可能存在联系,语料库中的系统调用序列代表真实通过运行的序列.我们通过实际运行的系统调用序列遍历这个静态子图,得到潜在的子序列.通过语料库中系统调用序列数据遍历静态子图得到的子序列含有程序的动静态信息并且可以扩展数据集.深度遍历搜索提取算法具体步骤如下.1)输入 F 为调用序列,Msub为由初始语料库建图得到的邻接矩阵,用于判断系统调用节点间是否有可达的边.2)调用序列从未探索节点 notvisit 选取第一个系统调用节点 syscalli(算法 1line17).3)将选取的节点作为当前系统调用节点 cur(算法 1line4).4)探索路径 path 扩展当前系统调用节点 cur,未探索节点集合 notvisit 去除扩展节点(算法 1line6).5)如果当前系统调用节点无法扩展节点,说明已经探索完成一条子序列,将子序列存于 S(算法 1line8),回到上一层递归函数(算法 1line9).6)如果当前节点能继续扩展节点,遍历 notvisit 节点(剩余节点),如果 syscalli能够从当前节点到达,syscalli作为选取节点(算法 1line11).进入递归(算法 1line12).7)如果本层递归结束,则进行回溯,撤销处理结果(算法 1line13、14).8)计算输出为潜在子序列集合 S.伪代码如算法 1 所示.算法 1.深度遍历搜索提取序列Input:调用序列 F、子选择矩阵 Msub.Output:潜在子序列 S.1.Functionrecursion(syscall)/递归函数2.cur=syscall3.path.apppend(cur)4.notvisit=notvisitcur5.ifsyscalldonthavesuccessornode6.S.append(path)7.return8.end if9.for syscalliinnovisitcanbereachedfromcur10.recursion(syscalli)11.path.erase(syscalli)12.notvisit=notvisit+syscalli13.end for14.end Function15.notvisit=F16.path=;S=17.forsyscalliinnotvisit18.recursion(syscalli)19.end for深度搜索提取子序列旨在实际运行的调用序列中,挖掘子序列.以图 3 为例,假设我们有调用序列 1-2-3-4(F),提取的子图(Msub)如图 3 所示.则我们从系统调用结点 1 作为第一个节点开始在 Msub上深度遍历(算法 1line17、18),此时 path 为“1”(算法 1line2、3).通过for 循环遍历,从节点 1 能到达的节点是节点 2 和节点3,我们首先选择节点 2,进入递归函数,此时 path 为“1-2”(算法 1line2、3).以 2 为当前节点只能探索到节点 4(算法 1line9),所以以系统调用节点 4 进入递归函数后,终止条件(算法 1line5)满足,得到一条子序列“1-2-4”(算法 1line6).然后回溯至节点 2,path 为“1-2”(算法 1line11)由于其可达节点(4)已经探索完,for 循2023年第32卷第9期http:/www.c-s-计 算 机 系 统 应 用SpecialIssue专论综述23环结束,所以继续回溯至节点 1,此时 path 为“1”(算法1line11).接着从未探索的可达节点 3 开始探索,同理可以探索“1-3-2”“1-3-4”两条子序列.接着我们分别以2、3、4 为第 1 个节点开始探索(算法 1line17、18),按照这样的规则,我们提取的潜在子序列有“1-2-4”“1-3-4”“1-3-2-4”“2-4”“2-1-3-4”“3-2-4”“3-4”.1342图 3深度搜索示意图(3)N-gram 模型训练N-gram 模型来源于自然语言处理领域,相关的背景知识在第 2 节中已经阐述.由于在我们的使用场景中,系统调用序列语料库中的数量为数万之内,无法支撑复杂的深度学习模型以及 N 值较大的 N-gram 模型训练;而且,在我们的实验中,语料库调用序列长度为2 的调用序列占比最大,我们采取 n=2 的 bigram 模型进行训练.N-gram 模型训练的具体算法如下.1)输入 S 为潜在子序列.2)遍历每个子序列.3)在每个子序列中,提取相邻的两个系统调用,并使用二维 hash 存储(算法 2line5、7),哈希表的两个维度分别是两个关联系统调用标号(callnum)(Psyzkaller对可生成的系统调用的标记),数值大小为出现次数.4)语料库数据增加 100 条开始训练.5)计算输出为 bigram 模型 N.伪代码如算法 2.算法 2.N-gram 模型训练Input:潜在子序列 S.Output:N/N-gram 模型.1.N=/N 为二维哈希表2.foreachsinS3.fori inrange(1,s.length1)4.ifNsi.callnumsi1.callnum=05.Nsi.callnumsi1.callnum=16.else7.Nsi.callnumsi1.callnum+8.end if9.end for10.end for通过 N-gram 模型的训练,我们得到强相关的调用序列对以及某个系统调用选择下一个的概率,根据大数定律,出现次数足够多的调用对的依赖关系可能更强.在构造系统调用序列的过程中,我们根据模型训练得到的数据依概率选取系统调用,更容易构造出长序列.3.2 选择矩阵增强模块选择矩阵增强模块的目的在于将系统调用序列动态信息和初始的选择矩阵相结合,使得选择矩阵包含系统调用的静态信息以及其运行的动态信息,更加客观合理地反映系统调用间的关系.选择矩阵增强的算法具体步骤如下.1)输入 N 为 N-gram 模型,输入 M 为选择矩阵.2)遍历 N-gram 模型的第 1 个维度 Ni,i 代表系统调用标号,Ni 代表与 i 系统调用相关的所有系统调用集合.3)如果 N-gram 模型中,i、j 系统调用有关联,也就是 Nij 不为零,则 sum 对应增加初始矩阵的权值Mij(算法 3line5、6).4)增加出现 i、j 系统调用的选择权值,对于 Mi中的值,如果 Nij 有值,则 Mij 计算为 Mij+sum*(Nij/Ni*),其中 Ni*为 Ni 行的数值之和(算法 3line10、11).5)计算输出为 M.伪代码如算法 3 所示.算法 3.选择矩阵增强Input:N-gram 模型 N、选择矩阵 M.Output:增强矩阵 M.1.forni inN/ni为系统调用标号 i 所在哈希表 ni=Ni2.MiM/M 中系统标号为 i 的行3.sum=04.forjinrangelen(ni)5.if Nij!=06.sum+=Mij7.end if8.end for9.forvalinrangeMi10.if Nij!=011.Mij=val+sum*(Nij/Ni*)12.end if13.end for14.end for由于我们采用了 N-gram 模型关注于相邻调用的关系,原系统的增加调用序列任意两个调用间的动态更新选择矩阵的方案不再适用.我们采用 N-gram 模型计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第9期24专论综述SpecialIssue信息更新选择矩阵.我们的增强算法保障无 N-gram 模型数据的调用的相对权重不变(算法 3line10),此外我们根据 N-gram 模型数据再分配调用的选择权重(算法 3line11).该算法经模拟迭代验证能将选择矩阵中的系统调用的选择权重收敛至该调用对应的 N-gram权重大小.3.3 调用序列生成模块TF-IDF(termfrequency-inversedocumentfre-quency)值的大小代表一个系统调用的“关键性”,其在语料库中越少出现其值就越高,而一个在语料越少出现的系统调用,从该调用扩展将更可能增加覆盖率.而采取随机游走的方式,能产生更多样且“畸形”的调用序列.使用增强选择矩阵一定程度上保障系统调用满足依赖条件,模糊测试往往需要较为“畸形”的输入.Syzkaller 中采取随机生成第 1 个系统调用,往后逐个构造的方式构造调用序列,这种方式容易选择相同的第 1 个调用,从前往后生成调用序列容易产生重复的调用序列.因此我们在调用序列生成部分做了一些修改.首先我们按照语料库出现系统调用的情况,首先选择语料库更少出现的系统调用,然后随机游走建图,扩展 TF-IDF 值更高的系统调用.最后拓扑排序生成具有依赖关系的一个调用序列.原始 Syzkaller 随机选取第 1 个系统调用,然后向后生成随机的系统调用.随机选取第一个系统调用缺乏能量分配策略.当其使用某个系统调用作为第 1 个系统调用构造序列并长时间的 fuzz 后,该系统调用相关的覆盖率将趋于饱和.因此我们统计每个系统调用在语料库出现的次数,将更多的能量赋予更少出现的系统调用中.从前往后生成的构造方式中,容易生成相同的调用序列,所以我们采取随机游走的方式构建系统调用序列.wi|S|我们的工作不是完全的随机游走,构造序列过程中,我们计算构造序列中的 TF-IDF 权值,以下公式代表一个系统调用,代表语料库中所有的序列个数,其计算公式如下:TFi=wiTt=1wt(8)TF 为某个系统调用在本次构造中出现的频率:IDFi=log|S|wi Si+1|(9)IDF 为该系统调用在整个语料库中出现的逆频率值.TF-IDF 权值更大代表该系统调用在整个语料库中出现更少,更可能是比较“关键”的系统调用将有更大的概率被扩展.调用序列生成的具体步骤如下.1)输入 N 为 N-gram 模型,M为增强选择矩阵,L 为构建序列长度.2)根据每个系统调用在语料库中的出现次数,按概率选择第 1 个更少出现系统调用,G 扩展该调用(算法 4line3),其中 G 中节点表示系统调用,其有向边表示两个系统调用存在选择关系.3)计算 G 中调用序列的 TF-IDF 值,TF-IDF 值更高,代表该系统调用 C在所有语料库中更重要,将有更大概率被扩展(算法 4line6).=0.34)选择该调用前向或者后向进行插入(算法 4line7),根据的概率使用增强选择矩阵 M(算法 4line8),0.7 的概率使用 N-gram 模型扩展(算法 4line9).扩展得到扩展的调用 C,调用 C导入 G 中.重复步骤 3).5)将 G 拓扑排序,生成长度为 L 的系统调用序列P(算法 4line11).6)计算输出为 L 长度的系统调用序列 P.伪代码描述如算法 4 所示.算法 4.调用序列生成算法Input:N-gram 模型 N、增强选择矩阵 M、构建序列长度 L.Output:系统调用序列 P.=0.31.2.list=3.choosefirstsystemCcallwithenergyandGappend C4.list.append(C),G.append(C)5.while(list.sizeL)6.selectonecallC inGbyTF-IDFvalue7.chooseadirectionforwardorbackwardtoappendC andGappend C8.ithasthe probabilitytousetheMtoappendtheG19.ithastheprobabilitytousetheNtoappendG10.end while11.P=TopoSort(G)/拓扑排序我们通过 N-gram 模型训练得到出现更频繁的系统调用对信息.这个信息在生成长系统调用序列时更有优势,如在生成第 2.2 节所示的网络通讯系统调用时,使用 N-gram 模型扩展将更大概率生成该系统调用序列,探索更深层次的内核代码逻辑.2023年第32卷第9期http:/www.c-s-计 算 机 系 统 应 用SpecialIssue专论综述254实现基于 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)Gold52182.30GHz 的 CPU、128GB 内存、Ubuntu20.04 的环境中,Psyzkaller 以及 Syzkaller 在相同内核配置下运行 24h 三次取平均整值作为实验数据.由于与我们工作强相关的工作中,Dependkaller 并未提供源码,Moon-shine 在种子精简上做工作,Healer 基于旧版本的 Syz-kaller 且缺乏更新,经我们测试其实验效果并不我们选取的的基准 Syzkaller 效果好,所以我们的工作只和Syzkaller 做比较.由于 5.19 是 5.x 向 6.x 过渡的测试版本,5.x 的旧版本特性和 6.x 的新特性都可以在该内核代码中有所体现,所以我们选取 5.19 版本的内核作为测试内核.为了说明我们的工具的相同时间内能触发更多的内核崩溃,我们选取 4.19 版本内核作为测试内核.5.2 覆盖率对比Syzkaller 通过将程序运行的 trace 中的相邻的 PC(programercounter)值也就是程序运行经过的相邻地址做个哈希作为边覆盖信息.我们沿用了这个边覆盖统计信息.在 24h 实验中,如图 4、图 5 所示,Psyzkaller的边覆盖率对比 Syzkaller 在内核 4.19、5.19 版本中分别提升了 15.8%、14.7%的覆盖率.其中在 5.19 版本增加的覆盖率主要分布在 net 文件中当中,表 1 展示这些覆盖率差额.我们进一步探索了 Linux 内核 net 模块已覆盖部分的调用序列情况,其调用序列长度多为 2 个及以上.构造 2 个调用长度以及长序列是使用 N-gram 模型扩展系统调用的优势.edge coverage350 000300 000250 000200 000150 000100 00050 00002 h4 h6 h8 h 10 h 12 h 14 h 16 h 18