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

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

内核级的并发错误检测.另一方面,目前很多内核开发人员仍在广泛使用的内核级并发错误检测工具,如 Linux
内核死锁检测工具 Lockdep [38] 、内存检查工具 KASAN [39] 、模糊测试工具 Syzkaller [40] 和数据竞争检测工具
KTSAN [41] 等都存在很大的不足.因此,操作系统内核并发错误检测的研究仍面临巨大的挑战.

2.1 应用程序级并发错误检测方法局限性
操作系统内核作为软件栈最底层的部分,区别于上层的普通应用程序,其并发错误检测的难度也更大.很多
可用于应用程序级并发错误的检测方法不能直接用于操作系统内核之中.主要原因有以下几个方面.
1) 操作系统内核代码规模大,复杂度高:以 Linux 内核代码为例,其代码量从最初发布时的几千行增加到现
在的两千多万行.庞大的代码量会造成静态检测方法分析时间长,而动态检测方法 Trace 收集和分析的时间空
间开销大大增加.另一方面,Linux 内核代码的结构相比于普通应用程序更为复杂,包含大量的宏定义和预处理
指令,goto 语句及配置项繁多.如 Linux kernel v4.15 的代码函数达到 2 500 多万行,而其中的 goto 语句就有超过
15 万行,宏定义数目更是多达 210 多万条.
2) 操作系统内核位置特殊性:操作系统内核作为应用程序与硬件设备交互的平台,处于软件栈最底层,很
多可用于应用程序级动态二进制插桩的工具,如 Pin [42] 和 Valgrind [43] 等无法对操作系统内核进行插桩和分析.而
且,由于操作系统内核通常支持多种硬件架构,如 Linux 内核中支持的硬件架构包含 ARM、X86、Alpha 等超过
30 多种.因此,为了实现对不同架构下操作系统内核的插桩和动态监控,还需要虚拟化技术的支持.
3) 操作系统内核的同步原语复杂多样:以 Linux 内核为例,其中的同步原语除了各种锁机制(自旋锁、互斥
锁、读写锁和顺序锁等),还包括内存屏障、原子操作和信号量等同步机制.此外,还有 Linux 内核特有的大内核
锁(big kernel lock,简称 BKL)和读-复制-更新(read-copy-update,简称 RCU)等机制.BKL 可以锁定整个内核,确保
没有 CPU 运行于内核态中.RCU 机制的设计主要针对指针类型的数据,它允许多个读者和写者访问临界区,提
高了并发访问的效率.操作系统内核的很多同步原语,尤其是 RCU 和 BKL 机制,在应用程序中使用较少.因此,
很多与这些同步原语相关的并发错误则无法被应用程序级的并发错误检测工具所识别.
4) 操作系统内核中断机制:中断是操作系统内核的特有构成部分,然而,中断机制的加入,也使得操作系统
内核中多线程并发执行过程变得更为复杂.一方面,由于中断处理程序的线程可能会与正常的内核线程交叉执
行,从而造成并发错误;另一方面,中断相关的线程之间可能存在并发.因此,内核开发人员很难推断内核并发错
误的产生是否与中断相关.
5) 线程调度带来的不确定性:在抢占式内核中,操作系统内核线程的调度可以分为抢占式调度和主动式调
度.在主动式调度中,线程的时间片结束或者线程需要等待资源就会自动挂起线程;而在抢占式调度中,高优先
级的线程会抢占正处于内核态执行的低优先级线程.因此,相比于应用程序,操作系统内核线程调度的不确定性
更增加了并发错误的复杂性.
2.2 操作系统内核中并发错误检测工具的局限性
目前,在操作系统内核中集成了很多用于对内核进行动态调试以及并发错误检测的工具.例如,Linux 内核
中的死锁检测工具 Lockdep、Linux 内核内存错误检测工具 KASAN、Linux 内核模糊测试工具 Syzkaller 以及
Linux 内核数据竞争检查工具 KTSAN 和 KCSAN [44] .这些工具被内核开发人员广泛使用,但仍存在很多的不足
和缺点.
Lockdep 可以构建 Linux 内核锁类的统一抽象,并通过跟踪内核中锁的状态和不同锁之间的相互依赖关系,
进行死锁检测.Lockdep 被证明可以达到几乎 100%的准确率.然而,Lockdep 只能检测到 Linux 内核运行过程中
发现的死锁问题,无法找出潜在的死锁问题,漏报率较高.我们之前针对 Linux 内核文件系统的死锁问题进行调
研发现,Linux 内核中同步原语种类多样,除了 mutex_lock、spin_lock、down_write 等常见的同步函数,还包含各
文件系统中为了同步而专门设计的同步函数,如 btrfs 文件系统中的 btrfs_tree_lock 函数用于实现对全局结构
extent_buffer 变量的同步访问.
KASAN 是 Linux 内核的一个内存错误检测工具.KASAN 利用影子内存机制实现编译时的内存检查,可以