宋東海，賁可榮，張志祥

(海軍工程大學(xué)計算機(jī)工程系,湖北 武漢 430033)

一種基于類的Java多線程程序數(shù)據(jù)競爭靜態(tài)檢測算法*

宋東海，賁可榮，張志祥

(海軍工程大學(xué)計算機(jī)工程系,湖北 武漢 430033)

多線程并發(fā)程序的廣泛使用引發(fā)了更多的數(shù)據(jù)競爭問題，競爭檢測對于提高軟件質(zhì)量具有重要意義。將競爭靜態(tài)檢測和靜態(tài)切片分析結(jié)合起來，提出了一種基于類的Java數(shù)據(jù)競爭靜態(tài)檢測算法，該算法利用函數(shù)調(diào)用層次獲得函數(shù)調(diào)用鏈，對類域進(jìn)行分析，找出可能數(shù)據(jù)競爭，通過靜態(tài)切片縮小程序分析范圍，并結(jié)合數(shù)據(jù)競爭的必要條件，去掉不可能數(shù)據(jù)競爭。實(shí)例表明，該算法可用于指導(dǎo)修復(fù)程序中的競爭缺陷。

多線程程序；數(shù)據(jù)競爭；程序切片；靜態(tài)分析；競爭檢測

1 引言

隨著多核技術(shù)的出現(xiàn)和GUI程序的廣泛應(yīng)用，為有效利用計算資源，提高系統(tǒng)效率，而采用并發(fā)程序設(shè)計。雖然Java編程語言為編寫多線程程序提供強(qiáng)大的語言支持，但是編寫正確高效的多線程并發(fā)程序仍然比較困難。在多線程程序中，當(dāng)兩個線程在無時序約束的情況下訪問同一個內(nèi)存位置并且至少有一個是寫訪問時，就會導(dǎo)致數(shù)據(jù)競爭[1]。粗粒度的保守機(jī)制可以避免數(shù)據(jù)競爭，但與此同時可能會導(dǎo)致死鎖，并發(fā)多線程編程導(dǎo)致許多

特定的優(yōu)化和檢錯問題。高效、精確的競爭檢測對于提高軟件可靠性、增強(qiáng)系統(tǒng)穩(wěn)定性具有重要意義。

2 Java數(shù)據(jù)競爭檢測

2.1 競爭檢測技術(shù)研究現(xiàn)狀

按照競爭檢測的依據(jù)，數(shù)據(jù)競爭可分為基于發(fā)生序(Happen-Before Order)[2,3]、鎖集 (Lock-Set)[4,5]以及其混合方法[6,7]。按照競爭檢測的時機(jī)，數(shù)據(jù)競爭檢測可分為競爭動態(tài)檢測[2,3]和競爭靜態(tài)檢測[7,8]。競爭動態(tài)檢測采用插樁技術(shù)能獲得變量和別名的準(zhǔn)確信息，準(zhǔn)確捕獲共享內(nèi)存訪問的發(fā)生序和鎖集信息，幾乎不產(chǎn)生誤報(False-Positive)，但依賴于程序輸入，只分析與程序執(zhí)行路徑有關(guān)的代碼，會漏報(False-Negative)一些真正的數(shù)據(jù)競爭并且開銷很大[3]。競爭靜態(tài)檢測是程序編譯時或者編譯后對源程序或者目標(biāo)代碼進(jìn)行檢測，需要分析整個程序，不像動態(tài)競爭檢測，無需插樁，不需占用程序的運(yùn)行時間，不受程序規(guī)模限制。但是，因靜態(tài)分析的不可判定性[9]，對于任何一個有一定規(guī)模的軟件，希望獲得關(guān)于它的完備描述通常是不現(xiàn)實(shí)的[10]，往往采用不完備的近似算法，靜態(tài)分析的結(jié)果比較保守。

精確的數(shù)據(jù)競爭檢測是一個NP-hard[11]問題，由于并發(fā)程序中線程調(diào)度的不確定性，數(shù)據(jù)競爭的出現(xiàn)是隨機(jī)的，數(shù)據(jù)競爭很難被發(fā)現(xiàn)和重現(xiàn)，并且數(shù)據(jù)競爭不像死鎖，不會導(dǎo)致程序的突然失效，無法繼續(xù)運(yùn)行，大量的誤報會使得使用者對靜態(tài)分析工具失去信心和耐心。含有數(shù)據(jù)競爭錯誤的程序調(diào)試是非常困難的，為了提高分析精度，減少誤報，便于調(diào)試程序，有必要提高數(shù)據(jù)競爭靜態(tài)檢測的精度。

2.2 Java內(nèi)存模型

內(nèi)存模型描述的是程序中變量(實(shí)例域、靜態(tài)域、數(shù)組元素等)之間的關(guān)系，以及在實(shí)際計算機(jī)系統(tǒng)中將變量存儲到內(nèi)存和從內(nèi)存取出變量的底層細(xì)節(jié)。

JMM(Java Memory Model)是JVM(Java Virtual Machine)的內(nèi)存模型，規(guī)范了線程之間通過內(nèi)存的交互原則。JMM定義了一個統(tǒng)一的內(nèi)存管理模型，屏蔽了底層平臺內(nèi)存管理細(xì)節(jié)，具體由各個虛擬機(jī)來實(shí)現(xiàn)對內(nèi)存的動態(tài)管理，包括對內(nèi)存的分配以及回收。JMM將線程能訪問的內(nèi)存分為主內(nèi)存(Main Memory)與工作內(nèi)存(Working Memory)。Java中所有類實(shí)例域、靜態(tài)域、數(shù)組都儲存在主內(nèi)存中，對于所有線程都是共享的。每個線程都有自己的工作內(nèi)存，工作內(nèi)存中保存的是主內(nèi)存中某些變量的拷貝和臨時變量，線程內(nèi)對所有變量的操作都是在工作內(nèi)存中進(jìn)行，線程之間無法相互直接訪問，變量傳遞均需要通過主內(nèi)存完成，數(shù)據(jù)競爭只可能出現(xiàn)在主內(nèi)存變量上。

2.3 Java語言數(shù)據(jù)競爭靜態(tài)檢測

Java程序競爭靜態(tài)檢測主要有流非敏感的基于類型約束的系統(tǒng)。流敏感的基于鎖集合算法的靜態(tài)檢測和路徑敏感的模型檢測器。Choi等人[12]將競爭檢測分成一系列分析階段，包括逃逸分析階段、別名分析階段和競爭檢測階段。在此基礎(chǔ)上斯坦福Naik等人[8]提出了一種K-對象敏感、上下文敏感Java程序競爭靜態(tài)檢測算法，算法分為五個階段：(1)可達(dá)競爭對檢測(originalRaces)；(2)別名競爭對檢測(aliasingRaces)；(3)逃逸競爭對檢測(escapingRaces)；(4)并發(fā)競爭對檢測(parallelRaces)；(5)未加鎖競爭對檢測(unlockedRaces)。該算法隨著各階段的進(jìn)行，逐漸縮小檢測范圍，采用了自適應(yīng)K-對象敏感(K-Object-Sensitive)的上下文信息，提高了靜態(tài)分析的精度。張昱等人[7]基于即時編譯器JIT(Just-In Time)采用增量式競爭檢測技術(shù)，提高了競爭檢測的精度。

2.4 并發(fā)程序靜態(tài)切片

Weiser認(rèn)為一個切片與人們在調(diào)試一個程序時所做的智力抽象相對應(yīng)。他定義的程序P的切片S是一個可執(zhí)行的程序，對某個興趣點(diǎn)s處的變量v而言(〈s,v〉稱為切片準(zhǔn)則)，S由程序P中可能影響s處變量v的值的所有語句構(gòu)成。這個可執(zhí)行部分相對于程序P在功能上是等效的。

程序切片作為一種對程序結(jié)構(gòu)進(jìn)行分析的技術(shù)，可以用在程序信息分析方面，從而增強(qiáng)對程序的理解、調(diào)試、測試和確認(rèn)。1993年，Cheng J[13]最早考慮了并發(fā)程序的靜態(tài)切片，并提出了一種基于程序依賴網(wǎng)PDN(Process Dependence Net)的并發(fā)程序切片方法。1998年，Krinke J[14]針對多線程程序提出了一種新的靜態(tài)切片算法，引入了線程控制流圖、線程程序依賴圖，同時提出了線程證據(jù)的概念，用來描述多線程程序的執(zhí)行路徑。對程序的分析主要考慮程序數(shù)據(jù)依賴和控制依賴關(guān)系。Ranganath[1]于2003年又提出了并發(fā)程序干擾依賴(Interference Dependence)和現(xiàn)成依賴(Ready Dependence)的概念。2007年，戚曉芳[15]提出了線程交互可達(dá)圖，構(gòu)建了以程序狀態(tài)和語句二元組為節(jié)點(diǎn)的并發(fā)程序依賴圖。隨著Java等語言并發(fā)程序的應(yīng)用越來越多，多線程程序的分析、調(diào)試、測試比傳統(tǒng)單線程程序更復(fù)雜。并發(fā)程序切片工具可以使并發(fā)程序的理解和維護(hù)等工作更容易完成。

3 基于類的Java競爭靜態(tài)檢測算法(CBDCD)描述

雖然競爭靜態(tài)檢測是一種有效的數(shù)據(jù)競爭檢測方法，但是它受到線程交互、動態(tài)數(shù)據(jù)分配、別名信息、流信息、路徑信息、數(shù)組元素的影響，很難有精確的實(shí)現(xiàn)。為了提高競爭檢測的有效性且方便程序理解，需要對競爭靜態(tài)檢測的結(jié)果進(jìn)行確認(rèn)，但對數(shù)據(jù)競爭結(jié)果進(jìn)行確認(rèn)費(fèi)時又費(fèi)力。

本文將競爭靜態(tài)檢測技術(shù)和靜態(tài)程序切片技術(shù)結(jié)合起來，提出了一種基于類的Java數(shù)據(jù)競爭靜態(tài)檢測算法。該算法首先以函數(shù)調(diào)用鏈為上下文信息對類域進(jìn)行分析，找出可能數(shù)據(jù)競爭；然后通過對調(diào)用鏈靜態(tài)切片分析，并結(jié)合數(shù)據(jù)競爭的必要條件，去掉不可能數(shù)據(jù)競爭。

3.1 數(shù)據(jù)競爭必要條件

用五元組(t,p,v,e,ls)表示線程t在程序點(diǎn)p對變量v進(jìn)行訪問e(e為讀r或?qū)憌)，ls表示在程序點(diǎn)p變量v訪問時擁有的鎖集，如果線程t在程序點(diǎn)p對變量v進(jìn)行訪問e時，v沒有被鎖保護(hù)，則ls為?。數(shù)據(jù)對(t1,p1,v1,e1,ls1),(t2,p2,v2,e2,ls2)為數(shù)據(jù)競爭的必要條件：

(1)t1≠t2；

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

(3)程序點(diǎn)p1、p2處對變量v1、v2的訪問不具有發(fā)生序；

(4)e1、e2至少一個為寫操作；

(5)?l1∈ls1，?l2∈ls2，alias(l1,l2)=false(v1、v2在程序點(diǎn)p不被同一別名鎖保護(hù))。

3.2 競爭檢測算法描述

記一個類的域集合為F(包含實(shí)例域和靜態(tài)域)，函數(shù)集合為M，線程為T，域操作為E(E={r，w})，函數(shù)調(diào)用鏈為L(L為m1-m2-m3-…-mn-1-mn，表示函數(shù)mn調(diào)用mn-1，…，m3調(diào)用m2，m2調(diào)用m1)。則函數(shù)m中對域f操作為f-e-m∈F×E×M，線程t中調(diào)用函數(shù)m記為m-l-t∈M×L×T，則f-e-m-l-t∈F×E×M×L×T表示線程t內(nèi)以l為調(diào)用鏈對方法m內(nèi)f進(jìn)行e操作，用OP表示這些操作的集合。

問題：求類C上的數(shù)據(jù)競爭集R={〈f-e1-m1-l1-t1，f-e2-m2-l2-t2〉|f-e-m-l-t∈F×E×M×L×T}。

算法步驟：

輸入：源程序P;

輸出：類C上的數(shù)據(jù)競爭集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}，執(zhí)行步驟2。

步驟2如果F為空，則轉(zhuǎn)步驟10；否則轉(zhuǎn)步驟3。

步驟3從F中取出一個元素f(F=F-{f})，計算f上的可能數(shù)據(jù)競爭集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}，執(zhí)行步驟4。

步驟4從R0中取出一個元素r(R0=R0-{r})，對r中f-e-m-l-t按切片準(zhǔn)則〈p,f〉(p表示f-e-m-l-t程序點(diǎn)，即線程t內(nèi)以l為調(diào)用鏈對方法m內(nèi)f進(jìn)行e操作的程序點(diǎn)，下同)向后靜態(tài)切片，獲得切片s1、s2，執(zhí)行步驟5。

步驟5對s1、s2進(jìn)行分析，判斷f-r/w-mi1-lp1-tj1，f-w-mi2-lp2-tj2是否具有發(fā)生序，如果是，則轉(zhuǎn)步驟9；否則轉(zhuǎn)步驟6。

步驟6對s1、s2進(jìn)行分析，判斷s1.f、s2.f在程序點(diǎn)p是否指向同一內(nèi)存塊，如果是，則轉(zhuǎn)步驟7；否則轉(zhuǎn)步驟9。

步驟7對s1、s2進(jìn)行分析，判斷s1.f、s2.f在程序點(diǎn)p是否被別名鎖保護(hù)，如果是，則轉(zhuǎn)步驟9；否則轉(zhuǎn)步驟8。

步驟8此競爭為數(shù)據(jù)競爭，R=R+{r}。判斷R0是否為空，如為空則轉(zhuǎn)步驟2；否則轉(zhuǎn)步驟4。

步驟9此競爭為不可能數(shù)據(jù)競爭。判斷R0是否為空，如為空則轉(zhuǎn)步驟2；否則轉(zhuǎn)步驟4。

步驟10輸出類C上的數(shù)據(jù)競爭R，結(jié)束。

通過步驟3可以得到可能讀-寫、寫-寫數(shù)據(jù)競爭。通過步驟5判斷是否具有發(fā)生序關(guān)系，去掉不可能數(shù)據(jù)競爭。通過步驟6變量別名分析，判斷是否對同一內(nèi)存塊訪問，去掉不可能數(shù)據(jù)競爭。通過步驟7鎖變量別名分析，判斷是否被同一別名鎖保護(hù)，去掉不可能數(shù)據(jù)競爭。通過遍歷類中的每個域可以獲得類存在哪些競爭，對程序中的每個類執(zhí)行一次算法，就會獲得整個程序的數(shù)據(jù)競爭。

算法以類為基礎(chǔ)對程序進(jìn)行數(shù)據(jù)競爭檢測，可以讓我們更關(guān)注程序中經(jīng)常使用的類，并且對f-r-e-l-t進(jìn)行切片分析，縮小了程序分析的范圍，易于理解競爭出現(xiàn)的原因，便于指導(dǎo)修復(fù)程序中的競爭缺陷。

3.3 發(fā)生序判斷

問題：判斷f-e1-mi1-lp1-tj1，f-e2-mi2-lp2-tj2是否具有發(fā)生序。

算法步驟：

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

輸出：如果具有發(fā)生序，則輸出是；否則輸出否。

步驟1對f-e1-mi1-lp1-tj1，f-e2-mi2-lp2-tj2按切片準(zhǔn)則〈p,f〉向后靜態(tài)切片，獲得切片s1、s2。

步驟2對s1進(jìn)行分析，判斷程序點(diǎn)p2是否在程序點(diǎn)p1的切片s1上，如果是，則執(zhí)行步驟4；否則執(zhí)行步驟3。

步驟3對s2進(jìn)行分析，判斷程序點(diǎn)p1是否在程序點(diǎn)p2的切片s2上，如果是，則執(zhí)行步驟6；否則執(zhí)行步驟5。

步驟4對s2進(jìn)行分析，判斷程序點(diǎn)p1是否在程序點(diǎn)p2的切片s2上，如果是，則執(zhí)行步驟5；否則執(zhí)行步驟6。

步驟5沒有發(fā)生序，輸出否，退出。

步驟6具有發(fā)生序，輸出是，退出。

Figure 1 Dependence graph of program EX1圖1 程序EX1的依賴圖

4 算法實(shí)例分析

以文獻(xiàn)[8]第13頁程序EX1進(jìn)行實(shí)例分析，通過對實(shí)例程序進(jìn)行切片分析，可以獲得程序的依賴圖(包含數(shù)據(jù)依賴、控制依賴、調(diào)用依賴)，如圖1所示。我們對類A進(jìn)行分析，首先獲得F={f4}，M={A.init，A.set，A.get}(其中init為類的構(gòu)造函數(shù))，F(xiàn)-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(xiàn)-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訪問的可能數(shù)據(jù)競爭有：{〈①，⑤〉,〈②，③〉,〈②，④〉,〈②，⑤〉,〈③，⑤〉,〈④，⑤〉,〈⑤，⑤〉}。

如圖1所示，對于可能競爭〈①,⑤〉，通過對調(diào)用鏈①、⑤切片分析，調(diào)用鏈①、⑤分別對v1.v8.f4 (即同一內(nèi)存快)進(jìn)行讀寫，并且他們沒有被鎖保護(hù)，會產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈②,③〉，通過對調(diào)用鏈②、③切片分析，v2、v7屬于別名，并且被別名鎖(v2,v7)保護(hù)，則不會產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈②,④〉，通過對調(diào)用鏈②、④切片分析，調(diào)用鏈②先于④執(zhí)行，他們不會產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈②,⑤〉，通過對調(diào)用鏈②、⑤切片分析，調(diào)用鏈②、⑤分別對v1.v8.f4、v2.v8.f4進(jìn)行讀寫，但是v1、v2屬于不同對象，則不會產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈③,⑤〉，通過對調(diào)用鏈③、⑤切片分析，調(diào)用鏈③、⑤分別對v1.v8.f4、v2.v8.f4進(jìn)行讀寫，但是v1、v2屬于不同對象，則不會產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈④,⑤〉，通過對調(diào)用鏈④、⑤切片分析，調(diào)用鏈④先于調(diào)用鏈⑤執(zhí)行，則不會產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈⑤,⑤〉，調(diào)用鏈⑤、⑤分別對v1.v8.f4 (即同一內(nèi)存快)進(jìn)行讀寫，并且他們沒有被鎖保護(hù)，會產(chǎn)生數(shù)據(jù)競爭。

通過上述分析知道類A的域f4會產(chǎn)生兩個數(shù)據(jù)競爭R={〈①,⑤〉，〈⑤,⑤〉}。同理，可以對類B、T進(jìn)行分析，可以獲得整個程序的數(shù)據(jù)競爭。通過對每個類進(jìn)行分析，我們發(fā)現(xiàn)類之間的數(shù)據(jù)競爭是有關(guān)聯(lián)的，類B上的數(shù)據(jù)競爭實(shí)際上是由于對類B的A類型實(shí)例域f3的訪問導(dǎo)致的?？梢酝ㄟ^對類A的訪問進(jìn)行保護(hù)，消除類A、類B上的數(shù)據(jù)競爭。同樣可以消除類T的數(shù)據(jù)競爭。

5 結(jié)束語

數(shù)據(jù)競爭不會導(dǎo)致程序突然失效，因此未受到開發(fā)人員的重視。雖然現(xiàn)在的數(shù)據(jù)競爭檢測主要是以動態(tài)競爭檢測為主，但由于靜態(tài)競爭檢測不需要對運(yùn)行程序進(jìn)行插樁，不會影響系統(tǒng)運(yùn)行，隨著靜態(tài)競爭檢測技術(shù)分析結(jié)果精度的不斷提高，靜態(tài)競爭檢測越來越受到重視。本文通過引入切片技術(shù)，提出了一種基于類的Java數(shù)據(jù)競爭靜態(tài)檢測算法。通過實(shí)例分析，發(fā)現(xiàn)類之間的數(shù)據(jù)競爭是有關(guān)聯(lián)的，對一個類進(jìn)行修改，不僅可以消除這個類上的數(shù)據(jù)競爭，還能消除與之有關(guān)聯(lián)的類上的部分?jǐn)?shù)據(jù)競爭。實(shí)例表明，該算法是可行的，并且對于修復(fù)程序中的競爭缺陷具有指導(dǎo)意義。

[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)

附中文參考文獻(xiàn)：

[7] 張昱，郝允允.Java程序數(shù)據(jù)競爭的增量式檢測[J].西安交通大學(xué)學(xué)報,2009,43(8):22-27.

[10] 梅宏，王千祥，張路，等.軟件分析技術(shù)進(jìn)展[J].計算機(jī)學(xué)報, 2009,32(9):1697-1710.

[15] 戚曉芳，徐寶文，周曉宇.一種基于程序可達(dá)圖的并發(fā)程序依賴性分析方法[J].電子學(xué)報.2007,35(2):287-291.

[16] 章隆兵，張福新，吳少剛，等.基于鎖集合的動態(tài)數(shù)據(jù)競爭檢測方法[J].計算機(jī)學(xué)報， 2003,26(10):1217-1223.

[17] 富浩，蔡銘，董金祥，等.基于鎖集合算法的增強(qiáng)型數(shù)據(jù)競爭檢測方法[J].浙江大學(xué)學(xué)報(工學(xué)版),2009,43(2):328-333.

[18] 李克清，陳莘蔭，鄭無疾.一種基于鎖集合的多線程數(shù)據(jù)競爭的動態(tài)檢測算法[J].武漢大學(xué)學(xué)報(自然科學(xué)版),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

國家自然科學(xué)基金資助項目(61272108)

：賁可榮(benkerong08@21cn.com)

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

TP311.55

：A

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

宋東海(1987-),男,湖北咸寧人，碩士生，研究方向?yàn)槌绦蚍治觥-mail:443655536@qq.com

通信地址：430033 湖北省武漢市海軍工程大學(xué)計算機(jī)系A(chǔ)ddress:Department of Computer Engineering,Naval University of Engineering,Wuhan 430033,Hubei,P.R.China