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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(7):20392055 [doi: 10.13328/j.cnki.jos.006260] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563


高精度的大规模程序数据竞争检测方法

1
2
4
1
3
1
1
高凤娟 , 王 豫 , 周金果 , 徐安孜 , 王林章 , 吴荣鑫 , 张 川 , 苏振东 5
1
(计算机软件新技术国家重点实验室(南京大学),江苏 南京 210023)
2
(蚂蚁集团,广东 深圳 518000)
3 (厦门大学 信息学院,福建 厦门 361005)
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)
通讯作者: 王林章, E-mail: lzwang@nju.edu.cn

摘 要: 随着技术的不断发展,软件系统的非确定性(uncertainty)不断增强,数据竞争是并发系统这一类典型的非
确定性软件系统中常见的缺陷.尽管数据竞争静态检测近年来取得了巨大进展,但其面临的重要问题仍然存在.先前
的静态技术要么以分析精度为代价达到高扩展性,要么由于高精度分析而导致可扩展性问题.提出一种解决上述矛
盾的分段分析方法——GUARD.它首先基于程序值流进行轻量级上下文敏感的数据访问分析,以识别出候选的数
据竞争子路径而非完整的程序路径.接下来,进行可能并行执行(may-happen-in-parallel,即 MHP)分析来确定程序中
的两个数据访问操作是否可能会同时执行.MHP 分析基于线程流图(TFG)将线程信息进行编码以便于高效地查询
各个子路径之间的并发关系.最后,对于每条存在 MHP 数据访问的子路径,进行重量级路径敏感分析以确定数据竞
争路径的可行性.针对 12 个开源项目的实验评估显示,GUARD 能够在 1 870s 内完成对 130 万行代码的工业规模项
目的检测,且平均误报率为 16.0%.此外,GUARD 的分析速度更快,比现有的前沿技术平均快了 6.08 倍,并且显著降低
了误报率.除此之外,GUARD 在其中还发现了 12 个数据竞争漏洞.将它们全部报告给了开发者,其中 8 个已得到了
确认.
关键词: 数据竞争;MHP 分析;静态分析
中图法分类号: TP311

中文引用格式: 高凤娟,王豫,周金果,徐安孜,王林章,吴荣鑫,张川,苏振东.高精度的大规模程序数据竞争检测方法.软件学报,
2021,32(7):2039–2055. http://www.jos.org.cn/1000-9825/6260.htm
英文引用格式: Gao FJ, Wang Y, Zhou JG, Xu AZ, Wang LZ, Wu RX, Zhang C, Su ZD. High-precision data race detection method
for large scale programs. Ruan Jian Xue Bao/Journal of Software, 2021,32(7):20392055 (in Chinese). http://www.jos.org.cn/1000-
9825/6260.htm

High-precision Data Race Detection Method for Large Scale Programs
2
1
1
3
1
1
GAO Feng-Juan , WANG Yu , ZHOU Jin-Guo , XU An-Zi , WANG Lin-Zhang , WU Rong-Xin ,
5
4
ZHANG Charles , SU Zhen-Dong
1 (State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023, China)
2 (ANT Group, Shenzheng 518000, China)

 高凤娟和王豫为共同第一作者,作者顺序依据姓氏首字母排序.
 基金项目: 国家自然科学基金(62032010)
Foundation item: National Natural Science Foundation of China (62032010)
本文由“面向非确定性的软件质量保障方法与技术”专题特约编辑陈俊洁副教授、汤恩义副教授、何啸副教授以及马晓星教授
推荐.
收稿时间: 2020-09-05; 修改时间: 2020-10-26; 采用时间: 2020-12-14; jos 在线出版时间: 2021-01-22