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

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

统化调度以及模型检验等方法.第 3 列为具体的研究方法名称.第 4 列给出了各项研究工作中针对的并发错误
类型,如数据竞争、死锁、CUAF、SAC 等.没有明确说明或检测结果中包含多种类型的方法即标记为所有并发
错误类型.第 5 列为每项研究工作针对的操作系统内核版本和模块.第 6 列代表该研究方法采用的是 HB 关系算
法还是 Lockset 锁集算法来进行并发错误检测,没有使用这两种算法则不标记.第 7 列为该方法检测到的并发错
误数目.第 8 列为该方法进行并发错误检测的检测速度以时间开销计算,时间开销越大,表明检测速度越慢.从表
1 中可以看出:
1) 从并发错误检测手段上,数据流分析、符号执行等技术仍是静态检测方法的重要手段,而研究人员也尝
试着将不同的技术手段结合起来提高检测的效率.如 RELAY 采用符号执行和数据流分析相结合的检测方法,
DSAC 则采用流敏感分析和流不敏感分析相结合的混合数据流检测方法.其次,由于静态检测方法和动态检测
方法各有优缺点,Razzer 通过静态检测与动态检测相结合的检测方法,以达到更好的检测效果.此外,形式化验证
方法的模型检验 [56] 和操作系统内核验证 [87] 也为内核并发错误检测提供了新的思路.
2) 从并发错误类型上,大量(8/18)内核并发错误研究工作将数据竞争作为重点检测对象,如 RELAY 方法、
DataCollider 方法和 DILP 方法等.这可能是由于,一方面,数据竞争在内核中占的比重较大,是 Linux 内核中除死
锁外,发生最多的并发错误(如图 7 所示);另一方面,研究人员对应用程序级数据竞争的研究已经取得了很大进
展,数据竞争的定义和触发机制清晰,相比于其他并发错误的研究更容易开展.近年来,也有很多研究人员对原
子性违例进行了研究,如 Lu 等人提出的 AVIO [88] 和 Ctrigger [36] 方法用于应用程序级的原子性违例检测.另外,针
对内核的并发错误特点,研究人员还关注了一些特殊类型的并发错误,如 DCUAF 方法用于检测 Linux 内核驱动
程序中的 CUAF 错误,DSAC 方法用于 SAC 错误的检测.
3) 从检测算法上,很多研究工作(6/18)采用 Lockset 锁集相关的算法进行并发错误检测,一方面是由于
Lockset 锁集算法相比于 HB 关系算法更加轻量级,且易于实现;另一方面,由于内核中的线程并发和同步更加多
样和复杂,很难对多线程并发和同步进行建模和分析,例如设备中断可能随时打断线程的执行,DMA 的执行不
在处理器内核上等因素使得 HB 关系算法用于操作系统内核的并发错误检测更加困难.然而,传统的基于 HB 和
Lockset 锁集的算法已不能满足研究的需要,研究人员提出了很多改进的算法,如相对 Lockset 锁集 [33] 和符号对
Lockset 锁集 [35] 等算法,以提高并发错误的检测效率.此外,还有很多研究人员采用 HB 关系和 Lockset 相结合的
方法进行并发错误检测 [32] .近年来,很多动态检测方法,如 DataCollider、DRDDR 和 SKI 等方法则避免使用 HB
关系和 Lockset 锁集进行并发错误检测,也取得了较好的检测效果.
4) 从涉及到的内核模块上看,由于内核代码规模庞大且复杂,无论是静态检测方法还是动态检测方法,对
整个内核的并发错误检测的分析开销都较大,实现起来较为困难.另外,操作系统内核各个模块运行机制和实现
技术各不相同,难以用同样的技术方案对内核的不同模块进行处理,因此,研究人员会选择从并发错误发生较多
的操作系统模块着手进行研究,如 DCUAF 方法利用了驱动程序接口的并发特性而实现了专门针对 Linux 内核
驱动程序并发错误检测的方法,而 SKI 则针对 Linux 内核中文件系统模块进行数据竞争检测.从表 1 中可以看
出,针对内核中的驱动程序和文件系统两个模块进行并发错误研究的工作较多.
5) 从检测效果上看,静态检测方法能够检测出的并发错误数少则 9 个(aComment),多则 640 个(DCUAF),
而动态检测方法则能检测到 1~190 个并发错误.从整体上看,静态检测方法检测到的并发错误数目比动态检测
方法要多.然而,静态检测方法的误报率较高,RacerX 有将近 40%的误报率,因此研究人员采用静态检测方法时
主要考虑如何降低误报率.例如,RacerX 通过裁剪代码路径、移除不必要的锁集分析等方法降低死锁检测的误
报率.动态检测方法虽然误报率较低,但漏报率很高.如 DRDDR 方法只能检测到 2 个良性的数据竞争.研究人员
则通过系统化调度 [81] 、动态与静态相结合 [45] 等方法降低动态检测的漏报率.无论是静态检测方法还是动态检
测方法,将其用于操作系统内核这种大规模代码中,都面临着检测开销大的问题.为了追求更低的误报率和漏报
率,研究人员需要进行更为精确的分析,而检测的开销也随之增加.如 Razzer 方法甚至需要花费 7 天的时间才能
完成对整个 Linux 内核代码的检测.