Page 109 - 《软件学报》2021年第7期
P. 109

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


                 面临以下挑战.
                      操作系统内核代码结构复杂,误报率较高.在操作系统内核代码中,各种宏定义、inline 函数、函数指针以
                 及汇编代码等层出不穷,使得传统的静态代码分析方法效果不佳.研究人员需通过结合流敏感分析、路径分析、
                 符号执行以及指向分析等多种静态分析技术才能降低并发检测的误报率.如 DSAC 方法采用的混合流分析方
                 法、RELAY 中采用符号执行和数据流分析相结合的检测方法,都比单纯使用数据流分析方法的 RacerX 具有更好
                 的检测效果.如何将传统的静态代码分析技术更好地用于操作系统内核将是一个重要挑战.
                      操作系统内核代码规模大,分析开销大.由于操作系统内核的代码量庞大,如 Linux 内核代码多达 2 000
                 多万行,采用静态分析时花费的时间和空间开销都较大.如何降低静态分析的开销也将是研究人员关注的重点
                 问题.RELAY 方法采用并行化的思想,使得静态分析的时间从 72 小时缩短至 5 小时.
                      操作系统内核特有的并发错误研究有待加强.相比于应用程序,操作系统内核有其特殊性,如内核的中断
                 特性可能导致中断处理线程与其他内核线程并发执行,进而引发更多的并发错误.aComment 方法基于代码注
                 释的方法检测中断相关的并发错误,但人工分析的工作量较大.如何设计更有效的检测方法也是一个重要挑战.
                 此外,操作系统内核特有的同步机制,如 RCU、信号量、原子性操作等相关的并发错误也占有相当大的比例,但
                 相关的静态检测方法研究需要引起更多的关注.
                 3.3   动态检测方法
                    动态检测方法包括基于动态二进制插桩的检测、基于动态调试的检测、基于系统化调度的检测和基于模
                 糊测试的检测     [70,71] .通过跟踪操作系统内核的动态运行时行为或借助于动态调试技术、系统化调度和模糊测试
                 等策略,检测内核运行过程中存在的并发错误.
                    1)  基于动态二进制插桩的检测
                    基于动态二进制插桩的检测方法常通过跟踪内核代码的执行过程,获取内核运行时 Trace,进而通过 HB 关
                 系算法或者 Lockset 锁集算法进行在线或离线分析.
                    Redflag [72] 就是一个基于动态二进制插桩进行内核级并发错误检测的工具,主要针对内核级的数据竞争和
                 原子性违背错误.Redflag 通过动态二进制插桩的方法,记录内核代码执行的运行时信息,包括获取共享变量的
                 访存操作、同步函数的使用、内存分配以及系统调用边界等,并将这些信息写入日志文件,再利用 Lockset 锁集
                 分析算法和基于块的原子性违例分析算法进行数据竞争和原子性违例的分析.该方法还将内核中特有的同步
                 机制,如 RCU 机制   [73] 以及 LOA 分析等手段,引入到这些分析算法中以提升检测的有效性.Seyster 等人将 Redflag
                 用于 3 个内核组件:Btrfs、Wrapfs 和 Noveau,并分别检测出了数据竞争和原子性违例错误.为了降低二进制插桩
                 的开销,Redflag 采用离线分析的方法进行并发错误检测.而且,Redflag 支持内核的特殊同步机制,如 RCU、BKL
                 等,降低了误报率.但是 Redflag 只能检测到在内核运行过程中出现的并发错误,而无法检测到未执行代码中的
                 并发错误,漏报率较高.DILP      [74] 是一个将动态二进制插桩用于 Linux 内核数据竞争检测更高效的研究方法.DILP
                 主要用于检测 Linux 内核驱动程序中由于不一致的锁保护而导致的数据竞争问题.文献[74]指出在 Linux 内核
                 驱动程序的修复补丁中,有 38%的数据竞争补丁涉及到不一致的锁保护问题.DILP 通过 LLVM                          [75] 插桩的方法获
                 得内核驱动程序的运行时踪迹,通过记录共享变量的访存信息、加锁解锁信息以及并发的驱动函数信息,再利
                 用锁集算法分析程序中存在的数据竞争问题.DILP 被用于 Linux kernel v3.3.1 和 v4.16.9 中进行并发错误检测,
                 分别发现了 13 个和 25 个数据竞争.最终,11 个被开发人员确认为真正的数据竞争.与类似工具 KernelStrider                      [76]
                 相比,DILP 具有更好的检测效果.DILP 对并发的分析是函数级,检测准确率不如更细粒度的指令级,但运行时开
                 销却比指令级分析有大幅度降低.但是由于 DILP 是基于 Lockset 锁集的数据竞争检测,DILP 只能检测到锁相关
                 的数据竞争而无法检测到内核中其他同步机制相关的数据竞争.此外,DILP 也具有动态检测方法的缺点,只能
                 检测到执行路径相关的数据竞争,代码覆盖率低.
                    不同于 Redflag 和 DILP,为了帮助开发人员更好地理解内核同步机制,进而避免并发错误的发生,
                 LockDoc 提出用动态二进制分析的方法,通过分析内核同步机制生成内核同步机制使用规则,并根据是否违
                 反规则进行并发错误检测.LockDoc 的实现包含 3 个阶段:Trace 收集和分析阶段、锁规则生成阶段和文档生
   104   105   106   107   108   109   110   111   112   113   114