一种基于类的Java多线程程序数据竞争静态检测算法

J4 ›› 2014, Vol. 36 ›› Issue (02): 233-237.

一种基于类的Java多线程程序数据竞争静态检测算法

宋东海，贲可荣，张志祥

（海军工程大学计算机工程系,湖北武汉 430033）

收稿日期:2013-10-05 修回日期:2013-12-10 出版日期:2014-02-25 发布日期:2014-02-25
基金资助:
国家自然科学基金资助项目（61272108）

A class-based data race static detection algorithm for Java multithread programs

SONG Donghai,BEN Kerong,ZHANG Zhixiang

(Department of Computer Engineering,Naval University of Engineering,Wuhan 430033,China)

Received:2013-10-05 Revised:2013-12-10 Online:2014-02-25 Published:2014-02-25

摘要/Abstract

摘要：

多线程并发程序的广泛使用引发了更多的数据竞争问题，竞争检测对于提高软件质量具有重要意义。将竞争静态检测和静态切片分析结合起来，提出了一种基于类的Java数据竞争静态检测算法，该算法利用函数调用层次获得函数调用链，对类域进行分析，找出可能数据竞争，通过静态切片缩小程序分析范围，并结合数据竞争的必要条件，去掉不可能数据竞争。实例表明，该算法可用于指导修复程序中的竞争缺陷。

关键词: 多线程程序, 数据竞争, 程序切片, 静态分析, 竞争检测

Abstract:

The widespread use of multithread concurrent programs induces more detrimental data race problems, race detection is very important for improving software quality. Combining data race static detection with static program slicing, a classbased data race static detection algorithm for Java multithread programs is proposed. The algorithm obtains function callchains by using function calls, analyzes every field of a class, finds out possible data race, reduces the range of program analysis through static program slicing, and removes the impossible data race by considering the necessity of data race. An example demonstrates that the proposed algorithm can guide programmers to fix software data race defects.

Key words: multithread program;data race;program slice;static analysis;race detection

宋东海，贲可荣，张志祥. 一种基于类的Java多线程程序数据竞争静态检测算法[J]. J4, 2014, 36(02): 233-237.

SONG Donghai,BEN Kerong,ZHANG Zhixiang. A class-based data race static detection algorithm for Java multithread programs [J]. J4, 2014, 36(02): 233-237.

参考文献

［1］Ranganath V P, Hatcliff J. Slicing concurrent Java programs using Indus and Kaveri ［J］.International Journal on Software Tools for Technology Transfer,2007, 9(56):489504.
［2］Adve S V, Hill M D, Miller B P, et al.Detecting data races on weak memory systems［C］∥Proc of the 18th Annual International Symposium on Computer Architecture,1991:234243.
［3］Christiaens M, Brosschere K.TRaDe:A topological approach to onthefly race detection in Java programs［C］∥Proc of the 1st Java Virtual Machine Research and Technology Symposium, 2001:105116.
［4］Agarwal R, Sasturkar A, Wang L, et al. Optimized runtime race detection and atomicity checking using partial discovered types［C］∥Proc of the 20th IEEE/ACM International Conference on Automated Software Engineering, 2005:233242.
［5］Cheng G, Feng M, Leiserson C, et al.Detecting data races in Cilk programs that use locks［C］∥Proc of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures,1998:298309.
［6］Yu Y,Rodeheffer T,Chen W.RaceTrack:Efficient detection of data race conditions via adaptive tracking［C］∥Proc of the 20th ACM Symposium on Operating Systems Principles,2005:221234.
［7］Zhang Yu,Hao Yunyun.Incremental detection of data race for java programs［J］.JournaL of Xi’an Jiaotong University,2009,43(8):2227.(in Chinese)
［8］Naik M. Effective static race detection for Java［D］.Stanford, CA:Stanford University,2008.
［9］Landi W. Undecidability of static analysis ［J］.ACM Letters on Programming Languages and Systems,1992,1(4):323337.
［10］Mei Hong,Wang Qianxiang, Zhang Lu, et al. Software analysis:A road map［J］.Chinese Journal of Computers, 2009,32(9):16971710.(in Chinese)
［11］Netzer R H B, Miller B P. What are race conditions? some issues and formalizations ［J］.ACM Letters on Programming Languages and Systems, 1992,1(1):7488.
［12］Choi J D, Loginov A, Sarkar K.Static data race analysis for multithreaded objectoriented programs［R］.IBM Research:Technical Report RC22146,2001.
［13］Cheng J. Slicing concurrent programsA graph theoretical approach［C］∥Proc of the 1st International Workshop on Automated and Algorithmic Debugging,1993:223240.
［14］Krnke J.Static slicing of threaded programs［J］.ACM SIGPLAN Notices ,1998,33(7):3542.
［15］Qi Xiaofang, Xu Baowen, Zhou Xiaoyu. An approach to analyzing dependence of concurrent programs based on program reachability graphs［J］.Acta Electronica Sinica，2007,35(2):287291.(in Chinese)
［16］Zhang Longbing, Zhang FuXin, Wu Shaogang, et al. A locksetbased dynamic data race detection approach［J］.Chinese Journal of Computers, 2003,26(10):12171223.(in Chinese)
［17］Fu Hao, Cai Ming, Dong Jinxiang, et al. Enhanced data race detection approach based on lockset algorithm［J］.Journal of Zhejiang University:Engineering Science,2009,43(2):328333.(in Chinese)
［18］Li Keqing, Chen Xinmeng, Zheng Wuji.A dynamic detective algorithm based on lockset to solve multithreaded data race［J］.Wuhan University Journal of Natural Sciences,2000,46(3):289292.(in Chinese)
附中文参考文献：
［7］张昱，郝允允.Java程序数据竞争的增量式检测［J］.西安交通大学学报,2009,43(8):2227.
［10］梅宏，王千祥，张路，等.软件分析技术进展［J］.计算机学报, 2009,32(9):16971710.
［15］戚晓芳，徐宝文，周晓宇.一种基于程序可达图的并发程序依赖性分析方法［J］.电子学报.2007,35(2):287291.
［16］章隆兵，张福新，吴少刚，等.基于锁集合的动态数据竞争检测方法［J］.计算机学报， 2003,26(10):12171223.
［17］富浩，蔡铭，董金祥，等.基于锁集合算法的增强型数据竞争检测方法［J］.浙江大学学报(工学版),2009,43(2):328333.
［18］李克清，陈莘荫，郑无疾.一种基于锁集合的多线程数据竞争的动态检测算法［J］.武汉大学学报(自然科学版),2000,46(3):289292.

[1]	张静1，黄志球1,2，沈国华1,2，喻垚慎1，艾磊1. C程序中的内存泄漏机制分析与检测方法设计[J]. 计算机工程与科学, 2020, 42(05): 776-787.
[2]	贾周阳，廖湘科，刘晓东，李姗姗，周书林，谢欣伟. 基于机器学习的日志函数自动识别方法[J]. 计算机工程与科学, 2017, 39(01): 111-117.
[3]	蔡军，邹鹏，熊达鹏，何骏. 结合静态分析与动态符号执行的软件漏洞检测方法[J]. 计算机工程与科学, 2016, 38(12): 2536-2541.
[4]	张晓东1，郑庆华1，刘烃1，俞乐晨1，刘沛1，杨子江2. 多线程程序数据竞争检测与证据生成方法[J]. J4, 2014, 36(11): 2047-2053.
[5]	舒绍娴1，徐小平2，荣霓3,郭敏1. 面向对象软件的综合特征定位方法[J]. J4, 2013, 35(6): 101-106.
[6]	秦广赞，郭帆，徐芳，余敏. 一种防SQL注入的静态分析方法[J]. J4, 2013, 35(2): 68-73.
[7]	李锋,文艳军,齐治昌,陆赛因. 基于MYGCC的编程规则检查算法研究[J]. J4, 2012, 34(2): 67-72.
[8]	侯苏宁，陈立前，王昭飞，王戟. 一个面向C和Fortran数值程序的静态分析工具[J]. J4, 2011, 33(3): 94-102.
[9]	郭〓婧，吴军华. 一种新的检测结构克隆的方法[J]. J4, 2011, 33(12): 78-83.
[10]	冯〓锴,林柏钢. 跨站脚本漏洞的白盒测试框架的设计和实现[J]. J4, 2011, 33(10): 45-50.
[11]	刘震[1,2] 缪力[1]. 互斥并发程序的程序切片算法研究[J]. J4, 2007, 29(1): 79-82.
[12]	蒋曹清张大方缪力. 一种回归测试后的错误定位方法[J]. J4, 2005, 27(4): 14-15.
[13]	王鹏飞张大方缪力. 包含异常处理的Java程序切片[J]. J4, 2005, 27(4): 22-24.