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

2032 Journal of Software 软件学报 Vol.32, No.7, July 2021

从这些代表性的操作系统内核并发错误检测方法的对比和分析中,我们可以发现:继应用程序级并发错误
的研究之后,操作系统内核并发错误的研究已成为近年来的研究热点.研究人员从操作系统内核各种并发错误
的类型、产生原因以及内核本身的特性出发,并利用静态分析、动态分析和形式化验证等多种方法进行研究,
取得了一系列的研究成果,主要表现在:
1) 并发错误检测效果更好:从 2003 年的 RacerX 到 2019 年的 DSAC,并发错误检测的漏报率和误报率都在
降低.从动态二进制插桩技术到系统化调度分析,并发错误检测的准确率变得更高.
2) 并发错误检测效率更高:从传统的 Lockset 锁集方法到基于摘要的 Lockset 锁集,分析的速度在加快;基
于采样的动态分析相比于普通动态插桩方法大大降低了运行时开销.基于系统化调度和模糊测试的技术相比
于随机调度方法也更加速了并发错误的触发.
3) 更加注重对操作系统内核本身特性的研究:研究人员更加注重解决针对操作系统内核特性导致的并发
错误,如 aComment 提出针对中断的并发错误处理方法,SKI 中也着重考虑了内核中断的处理.
4) 引入其他缺陷检测方法用于并发错误检测:研究人员从软件工程的其他软件缺陷检测方法中受到启发,
将其用于并发错误检测,取得了较好的效果.如 Razzer 和 KRACE 都是基于模糊测试的技术,均可将其用于操作
系统内核的数据竞争检测之中.

4 研究挑战与展望

4.1 研究挑战
基于现有的操作系统内核并发错误检测方法,我们认为,针对操作系统内核的并发错误研究,目前还面临着
如下挑战.
1) 操作系统内核并发错误检测的特殊性
由于操作系统内核处于硬件之上、软件栈的最底层,内核线程的交叉执行分析往往需要借助于虚拟化技术
VMM 的支持.如 SKI [81] 、RAZZER [45] 和 KRACE [86] 等研究中利用 QEMU 实现内核线程的系统化调度.然而,基
于 QEMU 等虚拟化的方法只能复现那些可以被 QEMU 支持的硬件相关的并发错误,对于 QEMU 不支持的硬件
相关的并发错误则无法被检测.其次,VMM 每次模拟一条指令的执行,随后将其结果立即传递给其他 CPU,而现
有的 CPU 大多采用的是弱内存模型,那些误认为是强内存模型的并发错误则无法被暴露出来.此外,没有硬件支
持的虚拟化会导致 Guest 系统运行效率大幅降低,从而导致内核中与时间(延迟)相关的默认配置不再适用,例如
与 RCU 相关的 CONFIG_RCU_CPU_STALL_TIMEOUT 等参数需要重新配置.
操作系统运行过程中既有内核线程也有用户线程,区分不同内核线程的上下文也是一个重要挑战.这是因
为,内核运行时存在大量其他的线程,且部分线程是内核固有的,没有对应的用户进程.基于模糊测试的检测方
法利用外部系统调用触发内核内部代码执行,因此需要识别与用户进程对应的内核线程,以便于调度控制和并
发分析.此外,由于时间片的原因,每隔一个固定时间,内核会发生时钟中断,触发调度算法运行并引发大量的同
步操作,由此引入了大量的加锁与解锁操作,区分内核线程上下文能有效排除这部分干扰.
除了以上问题外,还存在基于模糊测试的检测方法无法控制和分析内核内部固有的线程、基于 Lockset 锁
集算法的检测方法无法分析操作系统内核特有的 lock-free 同步机制(如 RCU 等)问题.
2) 操作系统内核新的并发错误类型检测
近年来,除了针对基本的并发错误,如死锁、数据竞争、原子性违例等之外,还有很多研究人员针对 CUAF、
SAC 等其他类型的操作系统内核的并发错误进行检测.因此,如何从操作系统内核中发现新的并发错误类型,并
提出针对此种类型的并发错误检测方法会是一项重要的挑战.
3) 检测方法的可扩展性
很多现有的操作系统内核并发错误检测方法都是针对特定的操作系统内核类型和特定的硬件架构实现
的.如 DataCollider 和 DRDDR 都是基于 X86 架构的实现,而不能直接用于 ARM、Alpha 等其他架构下的并发
错误检测.另外,很多并发错误检测方法都针对特定的操作系统,如 DataCollider 是基于 Windows 内核的数据竞