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

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

成及规则违背分析阶段.Trace 的收集采用动态二进制插桩方法,通过 Linux Test Project 中的测试用例获取
访存信息.因此,LockDoc 的代码覆盖率取决于测试用例的有效性.锁规则生成是根据 Linux 内核源代码提取
的同步信息,以便生成更多的锁规则.LockDoc 的一个不足之处在于,其只关注单个变量相关的同步操作,而
无法处理包含多个变量同步的并发错误.另外,LockDoc 只分析内核中的锁机制而不能检测其他同步机制导
致的并发错误.
2) 基于动态调试的检测
基于动态调试的检测方法依赖于内核代码调试中的代码断点和数据断点技术.该方法需要借助于硬件调
试技术,而且目前仅仅基于 x86 架构有相关的实现.DataCollider [77] 就是利用动态调试技术实现的动态数据竞争
检测方法.相比于传统的数据竞争检测方法针对特定的同步协议(如锁机制等)保护的共享访存,该方法对于像
底层内核代码这样采用多种复杂同步机制的程序代码更为重要.为了提高运行时效率,该方法采用随机采样内
存的方法构建目标访存集合.利用硬件代码中断和数据中断检测 Windows 内核代码中存在的数据竞争错误.为
了去除掉良性数据竞争,该方法通过检查是否共享变量的值一直增加、是否涉及到修改不同标志,或者其他一
些特殊变量等手段,来降低 DataCollider 的误报率.最终,该方法检测出了 38 个数据竞争错误,其中 25 个被确认
为真正的数据竞争错误,12 个已经被修复.DRDDR [78] 采用与 DataCollider 类似的方法实现了 Linux 内核上的数
据竞争检测,该方法首次将调试寄存器用于 Linux 内核的数据竞争检测之中,并成功复现了两个 Linux 内核中已
有的数据竞争错误,发现了一些新的数据竞争错误.为了降低动态分析的运行时开销,这两种检测方法都采用了
动态采样机制,因此,该方法的准确率都依赖于最初访存采样算法的有效性.
3) 基于系统化调度的检测
基于动态二进制插桩和基于动态调试的检测方法,很难检测到没有执行而潜在的并发错误.因此,研究人员
提出了基于系统化调度的检测方法.该方法通过探究内核线程可能的交叉执行路径,检测到尽可能多的并发错
误.Blum 等人 [79] 提出了系统化调度的方法来检测内核中存在的并发错误.通过确定性地执行每一种可能的线程
交叉,识别出触发并发错误线程模式.Landslide 的实现基于仿真器 Simics [80] ,该仿真器是一个 x86 的全系统仿真
器,从而实现对内核的动态监控.Landslide 的基本组件包含内核插桩模块、调度模块、内存跟踪模块以及调度
探索等.通过时钟中断的方式控制调度器的线程调度,并跟踪线程的生命周期(线程创建、睡眠和消亡等)和内存
的读写操作,检查内核中是否发生 Panic、内存访问是否合法以及线程之间是否存在阻塞的环路等,找出内核中
存在的并发错误.Landslide 的实现主要用于课程教学中的操作系统内核原型,并没有真正用于实际的操作系统
内核,如 Linux 内核等,但它提供了一种重要的用于动态检测内核并发错误的思路.SKI [81] 的设计思路类似于
Landslide 提出的系统化探索方法,通过系统化地测试内核线程的交叉执行,动态地检测内核中的并发错误.相比
于 Landslide,SKI 可以用于真实的操作系统内核中.SKI 的实现基于全系统仿真器 QEMU [82] ,可以实现在避免修
改内核代码的情况下对内核进行调度控制.SKI 将内核线程与仿真器的虚拟 CPU 进行映射,并通过加入内核中
断机制、扩展已有的 PCT 算法 [27] ,从而实现对内核线程的调度.并且,利用内核的特殊指令,如 halt 指令、pause
指令、loop 指令等推断内核线程的生命周期.通过跟踪内核的运行时信息,并将访存信息、指令执行顺序以及
执行上下文信息记录到日志文件,再利用相应的 Bug 检测器检测出并发错误.SKI 用于 Linux 内核的文件系统
中,并检测到 11 个并发错误,其中有 6 个已经被修复.SKI 还可用于内核并发错误的复现,通过与传统的压力测试
方法相比较,SKI 可以大大降低复现并发错误的运行时开销.由于 SKI 的实现基于 VMM,操作系统内核运行于
一个被虚拟化了的硬件环境中,因此,很多需要硬件支持的并发错误是无法检测和复现的.另外,由于 SKI 利用用
户线程事件驱动线程调度以发现系统调用中存在的并发错误问题,忽略了很多其他内核线程并发导致的错误.
对操作系统内核而言,还有大量的空间没有被探测到,从而造成漏报率较高.
4) 基于模糊测试的检测
模糊测试是一种常用的软件测试方法,主要通过在程序中生成随机的输入数据,以触发程序中可能存在的
错误 [83] .研究人员将模糊测试和系统化调度方法相结合,提出了一些可用于并发错误检测的方法.MUZZ [84] 采用
基于覆盖率的插桩、线程上下文插桩和调度干预插桩这 3 种新的多线程插桩方法以提高模糊测试过程中动态