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

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

错误,从而降低了死锁检测的误报率.
数据竞争的检测需要对并发线程及其访存操作进行建模,分析是否满足数据竞争发生的 3 个基本条件.研
究人员提出了 Happens-before(HB)关系和 Lockset 锁集算法用于数据竞争检测.HB 关系是一个最早由 Lamport
于 1978 年提出来的 [29] 的偏序关系,它表示在程序运行过程中两个事件之间的关系,即这两个事件在现实中的执
行顺序.在同一线程内,事件的执行顺序是由它们发生的先后顺序决定的.而在不同的线程中,事件的执行顺序
是由它们对线程中同步对象的访问权决定的.例如,若存在两个并发线程 T1 和 T2,线程 T1 中的事件 a 先于线程
T2 中的事件 b 执行,那么必有事件 a 先于事件 b 获得同步对象的访问权限.因此,具有 HB 关系的事件是有先后
关系的.反之,如果两个事件不具有 HB 关系,则被称为并发事件.如果存在两个并发事件同时访问了同一个共享
变量,且其中至少一个是写操作,则认为在对共享变量进行访问时可能存在数据竞争.基于 HB 关系的数据竞争
检测工具就是基于上述原理实现的.如 RACEZ [30] 以动态插桩的方式监控程序的运行时行为,并利用 HB 关系进
行数据竞争检测,该方法采用采样机制以降低跟踪同步和访存操作的运行时开销.Lockset 锁集分析是一个轻量
级的用于并发错误检测的算法,它最早于 1997 年被用于一个动态的数据竞争检测工具 Eraser [31] .Lockset 锁集算
法的核心思想是跟踪程序执行过程中保护每一个访存位置的锁.锁集为空表明可能有两个或多个线程并发地
访问了一个内存位置,即可能存在数据竞争.基于 HB 关系和基于 Lockset 算法的一个重要区别在于,前者可以用
于分析除锁之外的其他同步机制之间的关系,而后者相对来说更加轻量级.虽然基本的 HB 关系算法和 Lockset
锁集算法可以帮助开发人员进行并发错误的检测,但考虑到具体的使用场景,研究人员还对这些算法作了进一
步的拓展和优化,使其能够更好地用于并发错误研究中.如 O’Callahan 等人 [32] 提出将 HB 关系算法与 Lockset
锁集算法相结合进行并发错误检测,与单纯采用 Lockset 锁集算法相比有更低的误报率.鉴于传统的 Lockset 锁
集算法受限于动态分析技术代码覆盖率较低、漏报率较高的问题,RELAY [33] 和 Locksmith [34] 方法将 Lockset 锁
集算法用于静态代码分析技术中,进行并发错误检测,提高了并发错误检测效率.Whoop [35] 则利用符号对
Lockset 锁集分析算法,检测设备驱动程序中的并发错误,使得 Lockset 锁集算法具有更好的可扩展性,检测到了
更多的并发错误.
原子性违例的检测需要定位程序中的原子性区域,并对原子性区域的操作进行检查,进而判断这些操作是
否违反原子性.研究人员常常通过模式匹配的方法找到程序中的原子性区域,再利用动态分析、静态分析等方
法检测程序中存在的原子性违例错误.如 CTrigger 通过动态控制线程调度,触发尽可能多的原子性违例错误 [36] .
EPAJ 方法通过静态分析并发线程的所有可能执行序列,检查其是否符合预定义的原子性类型 [37] .

1.3 并发错误检测方法的评价指标
判断一个并发错误检测方法好坏的指标主要有:误报率、漏报率和检测速度.误报率是指检测到的非并发
错误报告数占总的检测报告数的比率.误报率越低,表明检测效果越好.漏报率是指实际存在而没有被检测到的
并发错误数占总的检测报告的比率.漏报率越低,检测效果越好.检测速度是指整个并发错误检测过程所花费的
时间.花费的时间越短,检测方法更容易应用于实际的生产过程之中.
研究人员在设计并发错误检测工具时,常常需要在误报率、漏报率和检测速度之间加以权衡.如采用静态
分析方法往往能对代码进行较为全面的分析,具有较低的漏报率.但是由于代码中存在的函数指针、宏定义等
而无法进行精确分析导致误报率较高.很多研究人员提出通过过程间分析、流敏感分析、上下文分析和指向分
析等方法降低并发错误的误报率,然而,这又增加了静态分析的时间和空间开销,检测速度会变慢.动态分析方
法可以检测出实际运行过程中存在的并发错误,误报率较低.但是由于很难探测到所有的执行路径,漏报率较
高.另一方面,动态插桩、动态调度等方法的运行时开销较大.因此,研究人员一直在寻求一种低误报率、低漏报
率,且运行速度快的并发错误检测方法.
2 现有并发错误检测方法的局限性

作为软件系统领域的一个研究热点,并发错误检测方法的研究已经取得了很大的进展.然而,很多研究工作
针对应用程序级的并发错误,由于操作系统内核本身的特殊性和复杂性,这些方法通常不能直接用于操作系统