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

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

3 (School of Informatics, National Demonstrative Software School (Xiamen University), Xiamen 361005, China)
4 (Department of Computer Science and Engineering, The Hongkong University of Science and Technology, Hongkong, China)
5 (Department of Computer Science (ETH Zurich), Zürich, Switzerland)
Abstract: With the development of techniques, the uncertainty in software systems is continuously increasing. Data race is a typical bug
in current programs, which is a classic type of uncertainty programs. Despite significant progress in recent years, the important problem of
practical static race detection remains open. Previous static techniques either suffer from a high false positive rate due to the compromise
of precision, or scalability issues caused by a highly precise analysis. This paper presents GUARD, a staged approach to resolve this
paradox. First, it performs a lightweight context-sensitive data access analysis, based on the value flow of a program, to identify the
candidate data race subpaths instead of the whole program paths. Second, may-happen-in-parallel (MHP) analysis is employedto identify
whether two data accesses in a program may execute concurrently. This stage is scalable, due to the design of the thread flow graph (TFG),
which encodes thread information to query MHP relationship of the subpaths. Finally, for each subpath whose two data accesses are MHP,
the heavyweight path-sensitive analysis is appliedto verify the feasibility of the data races. The evaluation demonstrates that GUARD can
finish checking industrial-sized projects, up to 1.3MLoC, in 1 870s with an average false positive rate of 16.0%. Moreover, GUARD is faster
than the state-of-the-art techniques with the average speedup 6.08X and significantly fewer false positives. Besides, GUARD has found 12
new race bugs in real-world programs. All of them are reportedtothe developers and 8 of them have been confirmed.
Key words: data race; MHP analysis; static analysis
1 引 言

随着互联网、物联网、云计算等新计算平台、新应用模式以及智能化等新软件模式的广泛运用,软件系统
内外各种来源的非确定性(uncertainty)不断增强.如何面向非确定性,保障相关软件系统的质量,逐渐成为了国内
外学术界关注的焦点.从软件系统内部的不确定性来看,并发程序是一类典型的非确定性软件程序.并发程序由
于其随机性高,容易导致难以调试的并发缺陷.其中,数据竞争就是一种典型的并发缺陷.数据竞争发生在两个
或以上的线程并发地访问相同的内存位置,并且其中至少一个是写访问.此外,这些线程未采取任何机制来防止
[1]
访问操作同时进行 .数据竞争带来的影响从轻微的内存数据损坏到许多并发相关的缺陷,包括原子性及顺序
[2]
违反.例如,在 2018 年共公开了 52 个数据竞争相关的 CVE .数据竞争需要经过复杂的线程切换才能显露,因此
它是软件系统中最难检测的漏洞之一.随着近年来软件并行化程度不断提高,竞争检测技术正变得前所未有地
重要.尽管已经取得了巨大的研究进展 [38] ,但工业级的静态数据竞争检测技术仍远远不能令人满意.
数据竞争可以通过静态和动态方式来检测.动态分析 [3,912] 能够检测出程序中实际存在的漏洞,但难以推断
线程间存在的所有可能的交织情况.静态工具 [4,5,8,13] 通常能够达到很高的代码覆盖,但现有的前沿静态数据竞
争检测技术在精度和可扩展性之间陷入了两难.一类方法 [5,6,8,1315] 通过放弃上下文或路径敏感达到了很高的可
扩展性,但这不可避免地带来了高误报率的问题.例如,本文对一种近期提出的路径敏感的数据竞争检测技术
[8]
LDruid 进行了评估,它的误报率在 70%以上.另一类方法 [4,5] 追求高精度,但不可避免地存在可扩展性方面的问
[4]
题.如 LOCKSMITH 为程序生成部分约束并求解,这限制了它的可扩展性.本文的实验结果表明,它无法在 1 小
时内完成对 1 万行以上规模项目的分析.
本文解决这种矛盾的思路是基于这样一种观察:在实际程序中,使用部分程序路径来识别数据竞争就已足
够了.尽管这可能会引入误报(例如程序入口到该路径的约束不可达),但因为对于每个数据竞争都至少存在一
条局部路径,所以不会产生漏报.相比之下,传统的竞争检测方法 [46,8] 会分析整个程序路径(即从程序入口点开
始的路径)来检测竞争,而对整个程序路径进行路径敏感分析是代价高昂的.所以,本文只对以两次变量访问为
起止的子路径进行分析,因为这样的子路径是重要的数据竞争候选路径.
由于子路径总体上比整个程序路径更简单、明了,实行重量级分析,例如流敏感、上下文敏感、路径敏感
分析是可行的.但是这些分析技术代价很高,路径敏感分析尤为如此,因为路径条件可能会错综庞杂且计算成本高
昂 [16] .因此,现有的静态数据竞争检测技术都不能同时实现流、上下文和路径敏感分析.为了解决重量级分析(即
路径敏感分析)所带来的分析开销问题,我们设计了一种分段分析的方法.首先进行值流分析 [17,18] 识别出候选的
数据竞争子路径,接着进行可能并行执行(may-happen-in-parallel,简称 MHP)分析筛除不可行的竞争子路径.最