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

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

我们之前的研究工作对 Linux 内核代码中的数据竞争进行了调研 [24] ,通过分析 Linux 内核代码 5 年的修改
日志发现,2011 年~2015 年有将近 500 个数据竞争被确认和修复,Linux 内核各模块中数据竞争的分布情况如图
6 所示.其中,文件系统和驱动程序模块的数据竞争占比最大.Bai 等人 [25] 对 Linux 内核中的 use-after-free(UAF)
错误进行了调研分析,发现从 2016 年~2018 年之间,49%的 UAF 相关补丁来自于 Linux 内核驱动程序.而且,42%
的 UAF 错误都与多线程并发相关.事实上,任何一个 Linux 内核驱动程序的设计和实现都需要依赖于 Linux 内
核驱动程序接口和 Linux 内核中断处理接口两个模块,而各接口函数之间存在并发关系,因此驱动程序模块更
有可能触发并发错误.此外,我们对 2011 年~2019 年 Linux 内核中文件系统相关的并发错误进行了调研分析,各
种并发错误类型的占比如图 7 所示,从图 7 中可以看出,将近一半的并发错误是死锁,数据竞争的数量也达到
[4]
20%.有研究表明,当前发布的操作系统代码中 39%的并发错误补丁都是不正确的,比内存错误补丁高 4~6 倍 .
因此,对并发错误特别是操作系统内核并发错误的研究显得尤为重要.

Fig.6 Distribution of data races in Linux kernel modules (2011~2015)
图 6 Linux 内核各模块中数据竞争的分布情况(2011 年~2015 年)

Fig.7 Distribution of concurrency bugs over categories in Linux kernel (2011~2019)
图 7 Linux 内核各种类型并发错误的分布情况(2011 年~2019 年)
1.2 并发错误检测方法
针对不同的并发错误类型,研究人员从并发错误的触发机制出发,结合形式化验证、静态和动态代码分析
等技术提出了一系列用于并发错误检测的方法.
死锁的发生通常需要满足 4 个基本条件:互斥、非抢占、持有并等待和循环等待.死锁的检测需要构建出
程序的资源依赖关系图,通过检查是否存在资源的循环依赖来进行检测.如 Williams 等人 [26] 基于流敏感和上下
文敏感的静态代码分析技术,构建出 Java 库代码的 lock-order 图,进而检查 lock-order 图中是否存在环,若存在环,
则可能存在死锁.在此基础之上,很多研究人员采取了一系列的措施以降低死锁检测的误报率和漏报率.如
DeadlockFuzzer [27] 和 MagicFuzzer [28] 通过动态调度线程的方法以确认检测到的锁依赖循环是否是真正的死锁