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

高凤娟 等:高精度的大规模程序数据竞争检测方法 2053

相关性分析工具.它使用基于约束的技术来计算描述保护左值的锁的关联.LOCKSMITH 仅仅被应用于检测
[6]
[5]
100K 行代码的程序 .Goblint 将指针和值分析相结合,从而使其能够处理复杂的加锁情况.RELAY [35] 是一种
使用自底向上分析方法的静态可扩展算法.它采用符号执行、指针分析、锁集分析、受保护访问分析的方法产
生竞争警报.IteRace [36] 是一种针对 Java 并行循环的静态数据竞争检测工具,它通过专门处理 lambda 式并行循
环、跟踪、汇总,实现了较低的误报率.但其只能分析并行循环.ECHO [15] 能够在编写代码期间在 IDE 中实时检
测数据竞争.为了能够在 IDE 中得以使用,它采用的指针分析在程序有修改时会增量分析.然而,由于对分析速度
存在一定的要求,它不是上下文敏感和路径敏感的.RacerX [33] 使用流敏感的过程间分析检测数据竞争以及死锁.
然而,为了实现可扩展,它丢弃了一些程序信息,例如使用类型表示所有左值,这就导致了它是不完善的.据我们
所知,这些静态分析技术都没有同时实现上下文、流、路径敏感,大部分技术仅实现了其中的一部分.例如,
[5]
Goblint 在分析锁集时只实现了路径敏感分析.与先前的工作相比,GUARD 编码 MHP 关系、上下文信息、路
径信息,从而构建起了一个完备、有效的数据竞争检测器.
7 结 论

本文提出了一种阶段化的数据竞争检测技术 GUARD.它首先基于值流分析检测出数据可能的数据竞争候
选,之后采用 MHP 分析,基于新的程序表现形式(即线程流图)高效地筛除不可行的数据竞争路径.最后,GUARD
使用路径敏感分析保护数据竞争检测过程,进一步降低了误报率.我们通过多个程序评估了 GUARD,结果表明,
它能够精确、高效地检测已知和未知的数据竞争.未来,我们计划进一步提高分析精度,同时也扩展 GUARD,使
其能够处理其他种类的并发错误.

References:
[1] Savage S, Burrows M, Nelson G, Sobalvarro P, Anderson T. Eraser: A dynamic data race detector for multithreaded programs.
ACM Trans. on Computer Systems (TOCS), 1997,15(4):391–411.
[2] CVE security vulnerabilities related to CWE (Common Weakness Enumeration) 362. 2020. https://www.cvedetails.com/vulnerability-
list/cweid-362/vulnerabilities.html
[3] Chen D, Jiang Y, Xu C, Ma X, Lu J. Testing multithreaded programs via thread speed control. In: Proc. of the 26th ACM Joint
Meeting on European Software Engineering Conf. and Symp. on the Foundations of Software Engineering (ESEC/FSE). ACM,
2018. 15–25.
[4] Pratikakis P, Foster JS, Hicks M. LOCKSMITH: Context-sensitive correlation analysis for race detection. ACM SIGPLAN Notices,
2006,41(6):320–331.
[5] Vojdani V, Apinis K, Rõtov V, Seidl H, Vene V, Vogler R. Static race detection for device drivers: The Goblint approach. In: Proc.
of the 31st IEEE/ACM Int’l Conf. on Automated Software Engineering (ASE). IEEE, 2016. 391–402.
[6] Voung JW, Jhala R, Lerner S. RELAY: Static race detection on millions of lines of code. In: Proc. of the 6th Joint Meeting of the
European Software Engineering Conf. and the ACM SIGSOFT Symp. on the Foundations of Software Engineering (ESEC/FSE).
ACM, 2007. 205–214.
[7] Wang Y, Wang L, Yu T, Zhao J, Li X. Automatic detection and validation of race conditions in interrupt-driven embedded software.
In: Proc. of the 26th ACM SIGSOFT Int’l Symp. on Software Testing and Analysis (ISSTA). ACM, 2017. 113–124.
[8] Zhou Q, Li L, Wang L, Xue J, Feng X. May-happen-in-parallel analysis with static vector clocks. In: Proc. of the Int’l Symp. on
Code Generation and Optimization. ACM, 2018. 228–240.
[9] Huang J, Rajagopalan AK. Precise and maximal race detection from incomplete traces. ACM SIGPLAN Notices, 2016,51(10):
462–476.
[10] Huang J, Zhang C, Dolby J. CLAP: Recording local executions to reproduce concurrency failures. ACM SIGPLAN Notices, 2013,
48(6):141–152.
[11] Machado N, Lucia B, Rodrigues L. Concurrency debugging with differential schedule projections. ACM SIGPLAN Notices,
2015,50(6):586–595.