一種基于調用鏈的Java程序數據競爭靜態檢測算法＊

宋東海 陳二虎

（1.92493部隊88分隊 葫蘆島 125001）（2.92515部隊 葫蘆島 125001）

1 引言

隨著多核技術的出現和GUI程序的廣泛應用，為有效利用計算資源，提高系統效率，而廣泛采用并發程序設計。雖然Java編程語言為編寫多線程程序提供了強大的語言支持，但是編寫正確高效的多線程并發程序仍然比較困難。在多線程程序中，當兩個線程在無時序約束的情況下訪問同一內存位置并且至少有一個是寫訪問時，就會導致數據競爭［1］。粗粒度的保守機制可以避免數據競爭，但與此同時可能會產生死鎖，并發多線程編程導會致許多特定的優化和檢錯問題。高效、精確的競爭檢測對于提高軟件可靠性，增強系統的穩定性具有重要意義。

2 Java數據競爭檢測

2.1 競爭檢測技術研究現狀

按照競爭檢測的時機，數據競爭檢測可分為競爭動態檢測、競爭靜態檢測。競爭動態檢測主要有基于發生序（happen－before order）［2～3］、基于鎖集（lock－set）［4～5］以及其混合方法［6～7］，采用插樁技術能獲得變量和別名的準確信息，準確捕獲共享內存訪問的發生序和鎖集信息，幾乎不產生誤報（false－positive），但依賴于程序輸入，只分析與程序執行路徑有關的代碼，會漏報（false－negative）一些真正的數據競爭并且開銷很大。競爭靜態檢測是程序編譯時或者編譯后對源程序或者目標代碼進行檢測，需要分析整個程序，不像動態競爭檢測，無需插樁，不需占用程序的運行時間，不受程序規模限制。但因靜態分析的不可判定性［8］，對于任何一個有一定規模的軟件，希望獲得關于它的完備描述通常是不現實的［9］，往往采用不完備的近似算法，靜態分析的結果比較保守。

由于并發程序中線程調度的不確定性，精確的數據競爭檢測是一個NP－hard［1］問題，數據競爭很難被發現和重現，并且數據競爭不像死鎖，不會導致程序的突然失效，無法繼續運行，大量的誤報會使得使用者對靜態分析工具失去信心和耐心。含有數據競爭錯誤的程序調試是非常困難的，為了提高分析精度，減少誤報，便于調試程序，有必要提高數據競爭靜態檢測的精度。

2.2 Java內存模型

內存模型描述的是程序中變量（實例域、靜態域、數組元素等）之間的關系，以及在實際計算機系統中將變量存儲到內存和從內存取出變量的底層細節。

JMM（Java memory model）是JVM的內存模型，規范了線程之間通過內存的交互原則。JMM定義了一個統一的內存管理模型，屏蔽了底層平臺內存管理細節，具體由各個虛擬機來實現對內存的動態管理，包括對內存的分配以及回收。JMM將線程能訪問的內存分為主內存（main memory）與工作內存（working memory），Java中所有類實例域、靜態域、數組都儲存在主內存中，對于所有線程都是共享的。每個線程都有自己的工作內存，工作內存中保存的是主內存中某些變量的拷貝和臨時變量，線程內對所有變量的操作都是在工作內存中進行，線程之間無法相互直接訪問，變量傳遞均需要通過主內存完成，數據競爭只可能出現在主內存變量上。

2.3 Java語言數據競爭靜態檢測

Java程序競爭靜態檢測主要有流非敏感的類層次型約束的系統，流敏感的基于鎖集合算法的靜態檢測，路徑敏感的模型檢測器。Choi［10］等人將競爭檢測分成一系列分析階段，包括逃逸分析階段、別名分析階段、競爭檢測階段。在此基礎上斯坦福Naik［11］等人提出了一種K－對象敏感、上下文敏感Java程序競爭靜態檢測算法，算法分為五個階段：1）可達競爭對檢測（originalRaces）；2）別名競爭對檢測（aliasingRaces）；3）逃逸競爭對檢測（escapingRaces）；4）并發競爭對檢測（paralleRaces）；5）未加鎖競爭對檢測（unlockedRaces）。該算法隨著各階段的進行，逐漸縮小檢測范圍，采用了自適應 K－對象敏感（k－object－sensitive）的上下文信息，提高了靜態分析的精度。張昱［7］等人基于即時編譯器（just－in time，JIT）采用增量式競爭檢測技術，提高了競爭檢測的精度。

2.4 并發程序靜態切片

程序切片作為一種對程序結構進行分析的技術，可以用在程序信息分析方面，從而增強對程序的理解、調試、測試和確認。1993年，J.Cheng［12］最早考慮了并發程序的靜態切片，并提出了一種基于程序依賴網（PDN）的并發程序切片方法。1998年，J.Krinke［13］針對多線程程序提出了一種新的靜態切片算法，引入了線程控制流圖、線程程序依賴圖，同時提出了線程證據的概念，用來描述多線程程序的執行路徑。對程序的分析主要考慮程序數據依賴和控制依賴關系。Ranganath［14］于2003年又提出了并發程序干擾依賴（Interference Dependence）和現成依賴（Ready Dependence）的概念。2007年，戚曉芳［15］提出了線程交互可達圖，構建了以程序狀態和語句二元組為節點的并發程序依賴圖。隨著Java等語言并發程序的應用越來越多，多線程程序的分析、調試、測試比傳統單線程程序更復雜。并發程序切片工具可以使并發程序的理解和維護等工作更容易完成。

3 類層次的Java競爭靜態檢測算法（Class－lever DC）

雖然競爭靜態檢測作為一種有效的數據競爭檢測方法，但是競爭靜態檢測受到線程交互、動態數據分配、別名信息、流信息、路徑信息、數組元素的影響，很難有精確的實現。為了提高檢測競爭檢測的有效性并且方便程序理解，需要對競爭靜態檢測的結果進行確認，但是對數據競爭結果進行確認費時費力。

本文將競爭靜態檢測技術和靜態程序切片技術結合起來，提出了一種類層次的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 競爭檢測算法描述

Narayanasamy［16］發現程序中的絕大部分數據競爭是無害的。通過對Java并發程序進行分析，可以發現產生數據競爭的類是非常少的，需要更加重視頻繁使用以及更值得關注的類，因此本文提出了類層次的Java程序數據競爭靜態檢測算法。

3.2.1 類層次的Java數據競爭靜態檢測算法

類層次的Java程序數據競爭靜態檢測算法包含兩個部分：類層次數據競爭預測部分和以函數調用鏈的數據競爭確認部分。

類層次的Java程序數據競爭靜態檢測算法：

類層次的Java程序數據競爭靜態檢測算法的數據競爭預測部分對一個類的每個字段進行分析，找出一對可能產生數據競爭的程序語句。記一個待分析類的字段集合F（包含實例字段和靜態字段）、函數集合M，啟動線程集T（T表示啟動線程集合，包含main函數和start函數啟動的線程。滿足關系；T＝｛（［］，main）｝∪｛（o，start）｝），字段操作E（E＝｛r，w｝），函數調用鏈L（L為 m1－m2－m3…mn－1mn，表示函數 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表示這些操作的集合。

如圖1所示，我們從類Class的代碼中可以獲得類的F×E×M集合，從程序函數調用圖中可以獲得M×L×T集合。根據數據競爭必要條件4），利用笛卡爾積運算可以計算待分析類上的數據競爭〈f－w／r－m1－l1－t1，f－wm2－l2－t2〉。

圖1 數據競爭預測

圖2 數據競爭確認

如圖2所示，〈f－e－m1－l1－t1，f－e－m2－l2－t2〉表示一個可能的數據競爭對，以函數調用鏈的數據競爭確認部分對類層次的數據競爭預測部分產生的數據競爭進行確認。通過MHP（可能并行執行）分析［17］，根據數據競爭必要條件3）去掉不能并發執行的語句對；通過TLO（線程局部對象）分析［18］，根據數據競爭必要條件1）去掉不能被多個線程訪問變量的語句對；最后進行別名鎖分析，根據數據競爭必要條件2）和5），更進一步對競爭結果進行確認，判斷兩個引用變量是否可能別名，如果不可能的話，則說明不可能產生數據競爭。如果兩個引用變量可能別名，則在此基礎上判斷它們是否被相同鎖保護，如果被同一鎖保護，則說明對共享變量的訪問被同步保護，不會產生數據競爭，否則說明可能產生數據競爭。

3.2.2 算法分析

A和B為待分析的兩個類，其中類A有字段f1，類B有字段f2，類B上的可能數據競爭對記為〈B.f2－e－B.mi－l1－t1，B.f2－e－B.mj－l2－t2〉，類B 的函數mi訪問（直接或間接）類A的字段f1，類B的函數mj訪問（直接或間接）類A的字段f1，因此，類A上的可能數據競爭對可以記為〈A.f1－e－A.mp－mp＋1－…－B.mi－l1－t1，A.f1－e－A.mq－mq＋1－B.mj－l2－t2〉。消除類A 上數據競爭〈A.f1－e－A.mp－mp＋1－…－B.mi－l1－t1，A.f1－e－A.mq－mq＋1－B.mj－l2－t2〉的同時可以消除與之關聯的類B上的數據競爭〈B.f2－e－B.mi－l1－t1，B.f2－e－B.mj－l2－t2〉，即消除一個類上的數據競爭同時可以消除與之有關聯類上的相應數據競爭。類A上的函數相對于類B上的函數處于函數調用鏈的底層，類層次的數據競爭算法預測部分以類為基礎對程序進行數據競爭預測，使得我們可以根據類之間的關系來安排類上數據競爭檢測的順序，可以首先分析類層次較低的類（一般它的函數處于函數調用鏈的底層）或者更需要關注的類（程序中頻繁使用的類或對任務關鍵的類）。

在以函數調用鏈為上下文的數據競爭確認部分，利用數據競爭的必要條件，對以類為層次的數據競爭預測部分產生的可能數據競爭進行確認，逐步求精，最后可以獲得較精確的數據競爭檢測結果，但由于靜態程序分析的不可判定性，由于是根據數據競爭的必要條件進行判斷，檢測結果有一定的誤報率。

可以通過對程序中的每個類執行一次算法，就會獲得整個程序的數據競爭。并且以函數調用鏈為上下文，縮小了程序分析的范圍，易于理解競爭出現的原因，讓程序員關注函數調用鏈上的代碼，便于指導修復程序中的競爭缺陷。

4 競爭檢測實例分析

本節將通過一個Java多線程程序實例詳細介紹了競爭靜態檢測原型工具的分析執行過程。以附錄1程序進行實例分析。我們對類A進行分析，首先獲得F＝｛f4｝，M＝｛A.init，A.set，A.get｝（其中init為類的構造函數），F－EM＝｛f4－r－A.get，f4－w－A.init，f4－w－A.get｝。

從附錄1程序的函數調用圖中可以獲得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（其中⑤屬于多個線程）

如表1所示，對于可能競爭〈①，⑤〉，通過對調用鏈①，⑤分析，調用鏈①，⑤分別對v1.v8.f4（即同一內存快）進行讀寫，并且他們沒有被鎖保護，會產生數據競爭。

表1 競爭詳細信息

如表2所示，可以對類層次生成的其他可能數據競爭進行分析。

表2 競爭檢測

通過對調用鏈②，③分析，v2，v7屬于別名，并且被別名鎖（v2，v7）保護，則不會產生數據競爭。對于可能競爭〈②，④〉，通過對調用鏈②，④分析，調用鏈②先于④執行，他們不會產生數據競爭。對于可能競爭〈②，⑤〉，通過對調用鏈②，⑤分析，調用鏈②，⑤分別對v1.v8.f4，v2.v8.f4進行讀寫，但是v1，v2屬于不同對象，則不會產生數據競爭。對于可能競爭〈③，⑤〉，通過對調用鏈③，⑤分析，調用鏈③，⑤分別對v1.v8.f4，v2.v8.f4進行讀寫，但是v1，v2屬于不同對象，則不會產生數據競爭。對于可能競爭〈④，⑤〉，通過對調用鏈④，⑤分析，調用鏈④先于調用鏈⑤執行，則不會產生數據競爭。對于可能競爭〈⑤，⑤〉，調用鏈⑤，⑤分別對v1.v8.f4（即同一內存快）進行讀寫，并且他們沒有被鎖保護，會產生數據競爭。

表3 競爭檢測結果

同理，對類B，T進行分析，可以獲得整個程序的數據競爭。通過對每個類進行分析，我們發現類A〈①f4－r－A.get－B.get－T.main，⑤f4－w－A.set－B.set－T.run〉上的數據競爭與類B〈①f3－r－B.get－T.main，⑤f3－w－B.set－T.run〉上的數據競爭是有關聯的，實際上是由于對類B的A類型實例字段f3的訪問導致的?？梢酝ㄟ^對類A的訪問進行保護，消除類A，類B上的數據競爭。同理可以消除類T的數據競爭。

5 結語

數據競爭不會導致程序的突然失效，而未受到開發人員的重視，雖然現在的數據競爭檢測主要是以動態競爭檢測為主，但是由于靜態競爭檢測不需要對運行程序進行插裝，不會影響系統運行。隨著靜態競爭檢測技術分析結果精度的不斷提高，靜態競爭檢測越來越受到重視。本文通過引入切片技術，提出了一種類層次基于調用鏈的Java數據競爭靜態檢測算法。通過實例分析，發現類之間的數據競爭是有關聯的，對一個類進行修改，不僅可以消除這個類上的數據競爭，還能消除與之有關聯的類上的部分數據競爭。實例表明，該算法是可行的，我們對整個程序進行數據競爭檢測分析，可以首先對待分析的各個類按照使用頻率和重要程度進行排序，然后對各個類進行數據競爭檢測，由于各個類上的數據競爭是有關聯的，并且對于修復程序中的競爭缺陷具有指導意義。下一步可以進一步研究類之間的關系與其上數據競爭分布的規律，安排類之間競爭檢測的順序，在保證軟件質量的同時，盡可能的節約測試成本。

［1］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.

［2］Adve S V，Hill M D，Miller B P，et al.Detecting data races on weak memory systems［C］／／Proceedings of the 18th Annual International Symposium on Computer Architecture（ISCA'91）.Toronto，Canada，1991：234－243.

［3］Christiaens M，Brosschere K.TRaDe：A topological approach to on－the－fly race detection in Java programs［C］／／Proceedings of the 1st Java Virtual Machine Research and Technology Symposium（JVM'01）.Monterey，California，USA，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］／／Proceedings of the 20th IEEE／ACM International Conference on Automated Software Engineering（ASE 2005），Long Beach，USA，November，2005：233－242.

［5］Cheng G，Feng M，Leiserson C，et al.Detecting data races in Cilk programs that use locks［C］／／Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures（SPAA'98），Puerto Vallarta，Mexico，1998：298－309.

［6］Yu Y，Rodeheffer T，Chen W.RaceTrack：Efficient detection of data race conditions via adaptive tracking［C］／／Proceedings of the 20th ACM Symposium on Operating Systems Principles（SOSP'05），Brighton，United Kingdom，2005：221－234.

［7］張昱，郝允允.Java程序數據競爭的增量式檢測［J］.西安交通大學學報，2009，43（8）：22－27.

［8］Landi W.Undecidability of static analysis［J］.ACM Letters on Programming Languages and Systems，1992，1（4）：323－337.

［9］梅宏，王千祥，張路，等.軟件分析技術進展［J］.計算機學報，2009，32（9）：1697－1710.

［10］Choi J D，Loginov A，Sarkar K.Static datarace analysis for multithreaded object－oriented programs［R］.IBM Research：Technical Report RC22146，2001.

［11］Naik M.Effective static race detection for java［D］.Stanford University，2008.

［12］Cheng J.Slicing concurrent program s－A graph theoretical approach［C］／／The First International Workshop on Automated and Algorithmic Debugging.Link ping，Sweden，1993：223－240.

［13］Krnke J.Static slicing of threaded programs［J］.ACM SIGPLAN Notices，1998，33（7）：35－42.

［14］Ranganath V P，Hatcliff J.Slicing concurrent Java programs using Indus and Kaveri［J］.International Journal on Software Tools for Technology Transfer（STTT），2007，9（5－6）：489－504.

［15］戚曉芳，徐寶文，周曉宇.一種基于程序可達圖的并發程序依賴性分析方法［J］.電子學報，2007，35（2）：287－291.

［16］Narayanasamy S，Wang Z，Tigani J，et al.Automatically classifying benign and harmful data races using replay analysis［C］／／Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation（PLDI）.San Diego，California，USA，2007：22－31.

［17］Li L.A practical MHP information computation for concurrent Java programs［D］.Montreal，Canada：McGill University，2004.

［18］Halpert R.Static lock allocation［D］.Montreal，Canada：McGill University，2008.

附錄1：Java多線程樣例程序EX1（該程序出自文獻［1］Naik M的學位論文第13頁）