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

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

顺序性违例是指程序中的两个或者多个访存操作必须按照某种顺序执行,而开发人员在程序编写过程中
却没有保证它的顺序性从而导致的并发错误 [19] .图 5 展示了一个 Linux kernel v3.11.10 中的顺序性违例实例.
Thread1 调用函数_request_firmware_load,执行完函数 kobject_uevent 时发生线程调度,Thread2 开始执行并调用
函数 firmware_loading_store,同时释放了 buf-pending_list.然后,Thread1 再次被调度执行,调用 list_add 函数执
行 buf-pending_list 添加操作而报错.这是由于,虽然对共享变量 buf-pending_list 的访问都加了锁保护,但没有
保证 buf-pending_list 的释放必须在 buf-pending_list 添加之前.

Fig.4 An example of atomicity violation of Linux kernel v3.12.36
图 4 一个 Linux kernel v3.12.36 中的原子性违例实例

Fig.5 An example of order violation in Linux kernel v3.11.10
图 5 一个 Linux kernel v3.11.10 中的顺序性违例实例

研究发现,在并发错误的这 4 种基本类型中,死锁与其他 3 类并发错误并不相关.非死锁的并发错误之间存
在着关联关系,如很大一部分原子性违例或顺序性违例发生的本质原因是数据竞争 [20] .如图 3 所示的数据竞争
实例也可以被归为顺序性违例.此外,并发错误的类型不限于上述 4 种基本类型,除此之外还有活锁、
concurrency-use-after-free(CUAF)、sleep-in-atomic-context(SAC)等.CUAF 是由于多线程并发而导致的 UAF 错
误,相比于普通的 UAF 错误,线程的并发和交叉执行使其检测难度大大增加.SAC 错误通常出现在内核级,在原
子性上下文中出现了睡眠操作 [21] ,如在自旋锁加锁过程中或者中断处理程序中出现了睡眠操作,导致 CPU 长期
处于阻塞状态而造成系统挂起或者死锁.研究人员对实际应用中的并发错误进行了调研分析.Lu 等人对
MySQL、Firefox、OpenOffice 和 Apache 中的并发错误进行了研究,发现 97%的非死锁并发错误是原子性违例
或者顺序性违例 [19] .Fonseca 等人 [22] 对 MySQL 中从 2003 年~2009 年之间的并发错误进行了统计分析,发现在修
复的错误中并发错误所占比例在 6 年中增长了两倍多,而且非死锁的并发错误(63%)比死锁(40%)要多.
Asadollah 等人 [23] 对 Apache、ZooKeeper、Spark 等开源软件中的并发错误进行了调研分析,发现并发错误平均
修复时间(82 天)要比非并发错误(66 天)要长.