Page 111 - 《软件学报》2021年第7期

石剑君 等:操作系统内核并发错误检测研究进展 2029

种子生成和执行的效率,检测多线程程序中存在的并发错误.ConFuzz [85] 将静态代码分析技术与模糊测试技术
相结合检测应用程序中存在的并发错误.除此之外,很多研究人员将模糊测试技术用于操作系统内核的并发错
误检测.KRACE 用模糊测试技术检测内核文件系统中存在的数据竞争问题 [86] .KRACE 通过覆盖率导向的模糊
测试方法对并发线程的空间进行探测,提出了生成、变换和合并多线程系统调用序列的演化算法进行模糊测
试,大大提高了文件系统代码的空间探测范围和效率.最后,采用 Lockset 锁集和 HB 关系相结合的数据竞争检测
算法对内核数据竞争进行精确检测.KRACE 最终在 ext4、btrfs 和 VFS 中发现了 23 个数据竞争,其中 9 个数据
竞争已被确认为有害的数据竞争错误.然而,由于 KRACE 只能探测到运行时的内核线程空间,其他潜在的内核
执行空间则无法探测.因此,存在着误报率较高的问题.
综上,动态检测方法的优势在于可以明确程序的执行过程,包括具体的共享变量访问情况以及具体的函数
调用路径等,可以帮助开发人员准确定位并发错误发生的位置及过程.然而,采用动态检测方法对操作系统内核
的并发错误检测还面临着如下挑战.
 操作系统内核线程交叉空间难以探测,漏报率高.动态分析很难遍历到程序执行的所有路径,因此,动态检
测方法无法检测到系统中存在但没有触发的并发错误.研究人员往往需要不断调整配置和输入参数,才能探测
到尽可能多的路径,触发潜在的并发错误.相比于应用程序而言,操作系统内核执行过程中的线程数量多达几十
甚至几百.尽管研究人员采取的压力测试和系统化调度的方法可以探测到更多的线程执行路径,可以从一定程
度上降低误报率.如 SKI 方法和 Landslide 都从一定程度上降低了漏报率.如何探测所有线程的交叉执行过程仍
是一个巨大的挑战.
 操作系统内核运行时分析开销大.无论是动态插桩、动态调试方法、系统化调度方法还是模糊测试方法,
由于操作系统内核代码复杂而造成运行时时间和空间开销很大.研究人员采用采样、离线分析等手段降低运行
时开销.如 DataCollider 和 DRDDR 通过随机采样方法降低动态插桩的开销.
3.4 静态与动态相结合的检测方法
为了提高并发错误的检测效率,研究人员通过静态分析和动态分析相结合的方法进行并发错误检测.通过
静态分析覆盖到尽可能多的并发错误,动态分析降低误报率,从而有效地检测出更多的并发错误.
Razzer [45] 就是这样一个动态和静态相结合的数据竞争检测工具.Razzer 首先利用静态分析的方法获得潜
在的数据竞争访存对,然后利用动态的模糊测试方法对这些访存对进行测试,从而检测出数据竞争.为了获得潜
在的数据竞争并发访存对,Razzer 利用基于 LLVM 的静态分析方法,包括控制流分析、数据流分析以及指向分
析等方法找出内核代码中可能的并发访存对.然后,基于 QEMU 和 KVM 实现了一个用于监控内核运行时行为,
确定性地控制内核线程的调度管理程序.通过确定性的内核线程交叉执行,判断给定的并发访存对是否造成数
据竞争.Razzer 用于 Linux kernel v4.16.-rc3 和 v4.18-rc3,并检测出了 30 个有害的数据竞争问题.文献[45]还将
Razzer 与 SKI、Syzkaller 进行了比较,发现 Razzer 的检测准确性和运行时效率都比其他工具要高.相比于 SKI
的随机线程调度,Razzer 需要更少的运行次数就可以触发数据竞争错误.由于 Razzer 依赖于静态分析的结果,静
态分析过程可能会漏掉部分并发访存对而造成漏报.目前,静态与动态分析相结合的方法是一种效率比较高的
并发错误检测方法.静态分析作为前提,可以帮助动态分析降低运行时开销,更高效地触发并发错误.动态分析
可以作为静态分析的补充,进一步确认静态分析的检测结果,降低静态分析的误报率.因此,静态和动态分析相
结合的并发错误检测方法是一种比较有前景的并发错误检测方法.
3.5 总结与对比分析

对操作系统并发错误检测方法的评估主要包括两个方面:一是针对检测效果的评价,包括误报率、漏报率
和准确率等;二是针对检测效率的评价,包括检测速度、运行时开销等.表 1 中选取了针对操作系统内核并发错
误检测的 17 个代表性研究工作,并对其采用的技术手段、检测类型、检测效果和性能进行了对比分析.第 1 列
代表该项研究工作所采用的检测方法类别,包含静态检测、动态检测、静态与动态相结合的检测和形式化验证
4 类.第 2 列是每一项研究工作中具体采用的检测技术手段,包含数据流分析、符号执行、动态二进制插桩、系