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

宋东海，贲可荣，张志祥

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

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

宋东海，贲可荣，张志祥

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

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

多线程程序；数据竞争；程序切片；静态分析；竞争检测

1 引言

随着多核技术的出现和GUI程序的广泛应用，为有效利用计算资源，提高系统效率，而采用并发程序设计。虽然Java编程语言为编写多线程程序提供强大的语言支持，但是编写正确高效的多线程并发程序仍然比较困难。在多线程程序中，当两个线程在无时序约束的情况下访问同一个内存位置并且至少有一个是写访问时，就会导致数据竞争[1]。粗粒度的保守机制可以避免数据竞争，但与此同时可能会导致死锁，并发多线程编程导致许多

特定的优化和检错问题。高效、精确的竞争检测对于提高软件可靠性、增强系统稳定性具有重要意义。

2 Java数据竞争检测

2.1 竞争检测技术研究现状

按照竞争检测的依据，数据竞争可分为基于发生序(Happen-Before Order)[2,3]、锁集 (Lock-Set)[4,5]以及其混合方法[6,7]。按照竞争检测的时机，数据竞争检测可分为竞争动态检测[2,3]和竞争静态检测[7,8]。竞争动态检测采用插桩技术能获得变量和别名的准确信息，准确捕获共享内存访问的发生序和锁集信息，几乎不产生误报(False-Positive)，但依赖于程序输入，只分析与程序执行路径有关的代码，会漏报(False-Negative)一些真正的数据竞争并且开销很大[3]。竞争静态检测是程序编译时或者编译后对源程序或者目标代码进行检测，需要分析整个程序，不像动态竞争检测，无需插桩，不需占用程序的运行时间，不受程序规模限制。但是，因静态分析的不可判定性[9]，对于任何一个有一定规模的软件，希望获得关于它的完备描述通常是不现实的[10]，往往采用不完备的近似算法，静态分析的结果比较保守。

精确的数据竞争检测是一个NP-hard[11]问题，由于并发程序中线程调度的不确定性，数据竞争的出现是随机的，数据竞争很难被发现和重现，并且数据竞争不像死锁，不会导致程序的突然失效，无法继续运行，大量的误报会使得使用者对静态分析工具失去信心和耐心。含有数据竞争错误的程序调试是非常困难的，为了提高分析精度，减少误报，便于调试程序，有必要提高数据竞争静态检测的精度。

2.2 Java内存模型

内存模型描述的是程序中变量(实例域、静态域、数组元素等)之间的关系，以及在实际计算机系统中将变量存储到内存和从内存取出变量的底层细节。

JMM(Java Memory Model)是JVM(Java Virtual Machine)的内存模型，规范了线程之间通过内存的交互原则。JMM定义了一个统一的内存管理模型，屏蔽了底层平台内存管理细节，具体由各个虚拟机来实现对内存的动态管理，包括对内存的分配以及回收。JMM将线程能访问的内存分为主内存(Main Memory)与工作内存(Working Memory)。Java中所有类实例域、静态域、数组都储存在主内存中，对于所有线程都是共享的。每个线程都有自己的工作内存，工作内存中保存的是主内存中某些变量的拷贝和临时变量，线程内对所有变量的操作都是在工作内存中进行，线程之间无法相互直接访问，变量传递均需要通过主内存完成，数据竞争只可能出现在主内存变量上。

2.3 Java语言数据竞争静态检测

Java程序竞争静态检测主要有流非敏感的基于类型约束的系统。流敏感的基于锁集合算法的静态检测和路径敏感的模型检测器。Choi等人[12]将竞争检测分成一系列分析阶段，包括逃逸分析阶段、别名分析阶段和竞争检测阶段。在此基础上斯坦福Naik等人[8]提出了一种K-对象敏感、上下文敏感Java程序竞争静态检测算法，算法分为五个阶段：(1)可达竞争对检测(originalRaces)；(2)别名竞争对检测(aliasingRaces)；(3)逃逸竞争对检测(escapingRaces)；(4)并发竞争对检测(parallelRaces)；(5)未加锁竞争对检测(unlockedRaces)。该算法随着各阶段的进行，逐渐缩小检测范围，采用了自适应K-对象敏感(K-Object-Sensitive)的上下文信息，提高了静态分析的精度。张昱等人[7]基于即时编译器JIT(Just-In Time)采用增量式竞争检测技术，提高了竞争检测的精度。

2.4 并发程序静态切片

Weiser认为一个切片与人们在调试一个程序时所做的智力抽象相对应。他定义的程序P的切片S是一个可执行的程序，对某个兴趣点s处的变量v而言(〈s,v〉称为切片准则)，S由程序P中可能影响s处变量v的值的所有语句构成。这个可执行部分相对于程序P在功能上是等效的。

程序切片作为一种对程序结构进行分析的技术，可以用在程序信息分析方面，从而增强对程序的理解、调试、测试和确认。1993年，Cheng J[13]最早考虑了并发程序的静态切片，并提出了一种基于程序依赖网PDN(Process Dependence Net)的并发程序切片方法。1998年，Krinke J[14]针对多线程程序提出了一种新的静态切片算法，引入了线程控制流图、线程程序依赖图，同时提出了线程证据的概念，用来描述多线程程序的执行路径。对程序的分析主要考虑程序数据依赖和控制依赖关系。Ranganath[1]于2003年又提出了并发程序干扰依赖(Interference Dependence)和现成依赖(Ready Dependence)的概念。2007年，戚晓芳[15]提出了线程交互可达图，构建了以程序状态和语句二元组为节点的并发程序依赖图。随着Java等语言并发程序的应用越来越多，多线程程序的分析、调试、测试比传统单线程程序更复杂。并发程序切片工具可以使并发程序的理解和维护等工作更容易完成。

3 基于类的Java竞争静态检测算法(CBDCD)描述

虽然竞争静态检测是一种有效的数据竞争检测方法，但是它受到线程交互、动态数据分配、别名信息、流信息、路径信息、数组元素的影响，很难有精确的实现。为了提高竞争检测的有效性且方便程序理解，需要对竞争静态检测的结果进行确认，但对数据竞争结果进行确认费时又费力。

本文将竞争静态检测技术和静态程序切片技术结合起来，提出了一种基于类的Java数据竞争静态检测算法。该算法首先以函数调用链为上下文信息对类域进行分析，找出可能数据竞争；然后通过对调用链静态切片分析，并结合数据竞争的必要条件，去掉不可能数据竞争。

3.1 数据竞争必要条件

用五元组(t,p,v,e,ls)表示线程t在程序点p对变量v进行访问e(e为读r或写w)，ls表示在程序点p变量v访问时拥有的锁集，如果线程t在程序点p对变量v进行访问e时，v没有被锁保护，则ls为Ø。数据对(t1,p1,v1,e1,ls1),(t2,p2,v2,e2,ls2)为数据竞争的必要条件：

(1)t1≠t2；

(2)alias(v1,v2)=true；

(3)程序点p1、p2处对变量v1、v2的访问不具有发生序；

(4)e1、e2至少一个为写操作；

(5)∀l1∈ls1，∀l2∈ls2，alias(l1,l2)=false(v1、v2在程序点p不被同一别名锁保护)。

3.2 竞争检测算法描述

记一个类的域集合为F(包含实例域和静态域)，函数集合为M，线程为T，域操作为E(E={r，w})，函数调用链为L(L为m1-m2-m3-…-mn-1-mn，表示函数mn调用mn-1，…，m3调用m2，m2调用m1)。则函数m中对域f操作为f-e-m∈F×E×M，线程t中调用函数m记为m-l-t∈M×L×T，则f-e-m-l-t∈F×E×M×L×T表示线程t内以l为调用链对方法m内f进行e操作，用OP表示这些操作的集合。

问题：求类C上的数据竞争集R={〈f-e1-m1-l1-t1，f-e2-m2-l2-t2〉|f-e-m-l-t∈F×E×M×L×T}。

算法步骤：

输入：源程序P;

输出：类C上的数据竞争集R。

步骤1初始化R=Ø，从源程序P中提取类C的F、M、F-E-M、M-L-T，计算OP={f-e-m-l-t|f-e-m-l-t∈F×E×M×L×T}，执行步骤2。

步骤2如果F为空，则转步骤10；否则转步骤3。

步骤3从F中取出一个元素f(F=F-{f})，计算f上的可能数据竞争集R0=①∪②，其中①为{〈f-r-mi1-lp1-tj1，f-w-mi2-lp2-tj2〉|f-e-m-l-t∈OP}，②是{〈f-w-mi1-lp1-tj1，f-w-mi2-lp2-tj2〉|f-e-m-l-t∈OP}，执行步骤4。

步骤4从R0中取出一个元素r(R0=R0-{r})，对r中f-e-m-l-t按切片准则〈p,f〉(p表示f-e-m-l-t程序点，即线程t内以l为调用链对方法m内f进行e操作的程序点，下同)向后静态切片，获得切片s1、s2，执行步骤5。

步骤5对s1、s2进行分析，判断f-r/w-mi1-lp1-tj1，f-w-mi2-lp2-tj2是否具有发生序，如果是，则转步骤9；否则转步骤6。

步骤6对s1、s2进行分析，判断s1.f、s2.f在程序点p是否指向同一内存块，如果是，则转步骤7；否则转步骤9。

步骤7对s1、s2进行分析，判断s1.f、s2.f在程序点p是否被别名锁保护，如果是，则转步骤9；否则转步骤8。

步骤8此竞争为数据竞争，R=R+{r}。判断R0是否为空，如为空则转步骤2；否则转步骤4。

步骤9此竞争为不可能数据竞争。判断R0是否为空，如为空则转步骤2；否则转步骤4。

步骤10输出类C上的数据竞争R，结束。

通过步骤3可以得到可能读-写、写-写数据竞争。通过步骤5判断是否具有发生序关系，去掉不可能数据竞争。通过步骤6变量别名分析，判断是否对同一内存块访问，去掉不可能数据竞争。通过步骤7锁变量别名分析，判断是否被同一别名锁保护，去掉不可能数据竞争。通过遍历类中的每个域可以获得类存在哪些竞争，对程序中的每个类执行一次算法，就会获得整个程序的数据竞争。

算法以类为基础对程序进行数据竞争检测，可以让我们更关注程序中经常使用的类，并且对f-r-e-l-t进行切片分析，缩小了程序分析的范围，易于理解竞争出现的原因，便于指导修复程序中的竞争缺陷。

3.3 发生序判断

问题：判断f-e1-mi1-lp1-tj1，f-e2-mi2-lp2-tj2是否具有发生序。

算法步骤：

输入：源程序P，f-e1-mi1-lp1-tj1，f-e2-mi2-lp2-tj2。

输出：如果具有发生序，则输出是；否则输出否。

步骤1对f-e1-mi1-lp1-tj1，f-e2-mi2-lp2-tj2按切片准则〈p,f〉向后静态切片，获得切片s1、s2。

步骤2对s1进行分析，判断程序点p2是否在程序点p1的切片s1上，如果是，则执行步骤4；否则执行步骤3。

步骤3对s2进行分析，判断程序点p1是否在程序点p2的切片s2上，如果是，则执行步骤6；否则执行步骤5。

步骤4对s2进行分析，判断程序点p1是否在程序点p2的切片s2上，如果是，则执行步骤5；否则执行步骤6。

步骤5没有发生序，输出否，退出。

步骤6具有发生序，输出是，退出。

Figure 1 Dependence graph of program EX1图1 程序EX1的依赖图

4 算法实例分析

以文献[8]第13页程序EX1进行实例分析，通过对实例程序进行切片分析，可以获得程序的依赖图(包含数据依赖、控制依赖、调用依赖)，如图1所示。我们对类A进行分析，首先获得F={f4}，M={A.init，A.set，A.get}(其中init为类的构造函数)，F-E-M={f4-r-A.get，f4-w-A.init，f4-w-A.get}，M-L-T={A.get-B.get-T.main，A.get-B.get-T.run，A.set-B.set-T.main，A.init-B.init-T.main，A.set-B.set-T.run}，为了方便后面阐述，F-E-M-L-T记为：

①f4-r-A.get-B.get-T.main;②f4-r-A.get-B.get-T.run;③f4-w-A.set-B.set-T.main;④f4-w-A.init-B.init-T.main;⑤f4-w-A.set-B.set-T.run(其中⑤属于多个线程)

对f4访问的可能数据竞争有：{〈①，⑤〉,〈②，③〉,〈②，④〉,〈②，⑤〉,〈③，⑤〉,〈④，⑤〉,〈⑤，⑤〉}。

如图1所示，对于可能竞争〈①,⑤〉，通过对调用链①、⑤切片分析，调用链①、⑤分别对v1.v8.f4 (即同一内存快)进行读写，并且他们没有被锁保护，会产生数据竞争。对于可能竞争〈②,③〉，通过对调用链②、③切片分析，v2、v7属于别名，并且被别名锁(v2,v7)保护，则不会产生数据竞争。对于可能竞争〈②,④〉，通过对调用链②、④切片分析，调用链②先于④执行，他们不会产生数据竞争。对于可能竞争〈②,⑤〉，通过对调用链②、⑤切片分析，调用链②、⑤分别对v1.v8.f4、v2.v8.f4进行读写，但是v1、v2属于不同对象，则不会产生数据竞争。对于可能竞争〈③,⑤〉，通过对调用链③、⑤切片分析，调用链③、⑤分别对v1.v8.f4、v2.v8.f4进行读写，但是v1、v2属于不同对象，则不会产生数据竞争。对于可能竞争〈④,⑤〉，通过对调用链④、⑤切片分析，调用链④先于调用链⑤执行，则不会产生数据竞争。对于可能竞争〈⑤,⑤〉，调用链⑤、⑤分别对v1.v8.f4 (即同一内存快)进行读写，并且他们没有被锁保护，会产生数据竞争。

通过上述分析知道类A的域f4会产生两个数据竞争R={〈①,⑤〉，〈⑤,⑤〉}。同理，可以对类B、T进行分析，可以获得整个程序的数据竞争。通过对每个类进行分析，我们发现类之间的数据竞争是有关联的，类B上的数据竞争实际上是由于对类B的A类型实例域f3的访问导致的。可以通过对类A的访问进行保护，消除类A、类B上的数据竞争。同样可以消除类T的数据竞争。

5 结束语

数据竞争不会导致程序突然失效，因此未受到开发人员的重视。虽然现在的数据竞争检测主要是以动态竞争检测为主，但由于静态竞争检测不需要对运行程序进行插桩，不会影响系统运行，随着静态竞争检测技术分析结果精度的不断提高，静态竞争检测越来越受到重视。本文通过引入切片技术，提出了一种基于类的Java数据竞争静态检测算法。通过实例分析，发现类之间的数据竞争是有关联的，对一个类进行修改，不仅可以消除这个类上的数据竞争，还能消除与之有关联的类上的部分数据竞争。实例表明，该算法是可行的，并且对于修复程序中的竞争缺陷具有指导意义。

[1]RanganathVP,HatcliffJ.SlicingconcurrentJavaprogramsusingIndusandKaveri[J].InternationalJournalonSoftwareToolsforTechnologyTransfer,2007, 9(5-6):489-504.

[2]AdveSV,HillMD,MillerBP,etal.Detectingdataracesonweakmemorysystems[C]∥Procofthe18thAnnualInternationalSymposiumonComputerArchitecture,1991:234-243.

[3]ChristiaensM,BrosschereK.TRaDe:Atopologicalapproachtoon-the-flyracedetectioninJavaprograms[C]∥Procofthe1stJavaVirtualMachineResearchandTechnologySymposium, 2001:105-116.

[4]AgarwalR,SasturkarA,WangL,etal.Optimizedrun-timeracedetectionandatomicitycheckingusingpartialdiscoveredtypes[C]∥Procofthe20thIEEE/ACMInternationalConferenceonAutomatedSoftwareEngineering, 2005:233-242.

[5]ChengG,FengM,LeisersonC,etal.DetectingdataracesinCilkprogramsthatuselocks[C]∥Procofthe10thAnnualACMSymposiumonParallelAlgorithmsandArchitectures,1998:298-309.

[6]YuY,RodehefferT,ChenW.RaceTrack:Efficientdetectionofdataraceconditionsviaadaptivetracking[C]∥Procofthe20thACMSymposiumonOperatingSystemsPrinciples,2005:221-234.

[7]ZhangYu,HaoYun-yun.Incrementaldetectionofdataraceforjavaprograms[J].JournaLofXi’anJiaotongUniversity,2009,43(8):22-27.(inChinese)

[8]NaikM.EffectivestaticracedetectionforJava[D].Stanford,CA:StanfordUniversity,2008.

[9]LandiW.Undecidabilityofstaticanalysis[J].ACMLettersonProgrammingLanguagesandSystems,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.

SONGDong-hai,born in 1987,MS candidate,his research interest includes program analysis.

Aclass-baseddataracestaticdetectionalgorithmforJavamultithreadprograms

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

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

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.

multithread program;data race;program slice;static analysis;race detection

2013-10-05;

：2013-12-10

国家自然科学基金资助项目(61272108)

：贲可荣(benkerong08@21cn.com)

1007-130X(2014)02-0233-05

TP311.55

：A

10.3969/j.issn.1007-130X.2014.02.008

宋东海(1987-),男,湖北咸宁人，硕士生，研究方向为程序分析。E-mail:443655536@qq.com

通信地址：430033 湖北省武汉市海军工程大学计算机系Address:Department of Computer Engineering,Naval University of Engineering,Wuhan 430033,Hubei,P.R.China