基于上下文敏感分析的數(shù)據(jù)競爭檢測方法

張楊 劉歡 張冬雯

摘 要：為了提高數(shù)據(jù)競爭檢測過程的準(zhǔn)確性，提出了一種基于上下文敏感分析的數(shù)據(jù)競爭檢測方法。使用控制流分析構(gòu)建上下文敏感的調(diào)用圖，采用逃逸分析查找出可能發(fā)生數(shù)據(jù)競爭的線程逃逸對象，進(jìn)行上下文敏感的別名分析以減少誤報(bào)和漏報(bào)，通過發(fā)生序關(guān)系判斷消除由于忽略線程交互而導(dǎo)致的誤報(bào)。依據(jù)該方法，在WALA軟件分析框架實(shí)現(xiàn)了一個(gè)數(shù)據(jù)競爭檢測工具ConRacer，并將該工具與現(xiàn)有的檢測工具SRD和RVPredict進(jìn)行了比較。結(jié)果表明，與SRD和RVPredict相比，ConRacer的檢測準(zhǔn)確度最高，不僅可以有效地檢測數(shù)據(jù)競爭，而且可以降低檢測過程中的誤報(bào)和漏報(bào)。通過結(jié)合上下文敏感分析技術(shù)與傳統(tǒng)的靜態(tài)檢測技術(shù)，ConRacer提高了檢測過程的準(zhǔn)確性，對發(fā)現(xiàn)并發(fā)錯(cuò)誤和優(yōu)化軟件性能有一定的參考價(jià)值。

關(guān)鍵詞：并行處理;并發(fā)程序;數(shù)據(jù)競爭;上下文敏感;逃逸分析

中圖分類號：TP311 ? 文獻(xiàn)標(biāo)識碼：A ? doi：10.7535/hbkd.2020yx05005

Abstract：To improve the correctness of data race detection， an approach to the data race detection based on the context-sensitive analysis in multithreaded programs was proposed. Firstly， control flow analysis was used to construct context-sensitive call graphs， and then escape analysis was employed to find thread-escaped objects that may cause data race. Secondly， context-sensitive alias analysis was conducted to reduce false positives and false negatives. Finally， the happens-before analysis was performed to remove false positives caused by ignoring thread interactions. A data race detection tool ConRacer was implemented in WALA framework based on this approach and was compared with the existing tools SRD and RVPredict. The experimental results show that ConRacer is the most precise tool compared with SRD and RVPredict and it can not only detect data races， but also reduce false positives and false negatives effectively. ConRacer improves the detection accuracy by combining context-sensitive with static detection methods， which has certain reference value for discovering concurrent errors and optimizing software performance.

Keywords：parallel processing; concurrent programs; data race; context-sensitive; escape analysis

隨著多核處理器的普及和眾核處理器的發(fā)展，基于多線程并發(fā)的程序應(yīng)用越來越廣泛。并行程序可以發(fā)揮多核處理器的優(yōu)勢，有效提高程序運(yùn)行效率，然而這些程序存在龐大的并發(fā)執(zhí)行交錯(cuò)空間狀態(tài)，使得程序員在并發(fā)編程過程中容易忽略某些執(zhí)行交錯(cuò)而導(dǎo)致并發(fā)問題。這些并發(fā)問題主要包括死鎖、數(shù)據(jù)競爭、原子性違背和順序違背等，難以檢測和修復(fù)，嚴(yán)重時(shí)可能會造成系統(tǒng)崩潰。因此，對并發(fā)相關(guān)問題的檢測和修復(fù)越來越受到程序員的關(guān)注。在這些并發(fā)問題中，數(shù)據(jù)競爭是常見的并發(fā)缺陷之一，它是指2個(gè)或多個(gè)線程對某一共享內(nèi)存位置進(jìn)行并發(fā)訪問且至少有一個(gè)是寫訪問[1]。數(shù)據(jù)競爭是一種典型的運(yùn)行時(shí)故障，僅在特定的執(zhí)行交錯(cuò)中暴露出來，因此難以檢測和修復(fù)[2]，嚴(yán)重時(shí)可能會導(dǎo)致程序崩潰，造成不堪設(shè)想的后果。

目前，對數(shù)據(jù)競爭檢測已有大量研究，主要分為2種：靜態(tài)檢測和動態(tài)檢測[3]。動態(tài)檢測通過運(yùn)行源程序，監(jiān)視程序在執(zhí)行過程中的行為，收集必要的變量和別名的準(zhǔn)確信息[4]。SimpleLock+是一個(gè)結(jié)合了發(fā)生序（happens-before）關(guān)系和鎖集（lockset）算法的混合動態(tài)數(shù)據(jù)競爭檢測方法，它對線程調(diào)度不敏感并且運(yùn)行時(shí)開銷較低[5]。HistLock+通過推斷來自同一線程的同一內(nèi)存位置上的2次訪問在連續(xù)的加鎖和解鎖操作之間是否具有共同鎖集來執(zhí)行鎖集分析，從而進(jìn)行數(shù)據(jù)競爭檢測[6]。RaceDetector結(jié)合共享變量分析和約束求解方法檢測安卓系統(tǒng)中的數(shù)據(jù)競爭[7]。SlimFast通過減少數(shù)據(jù)冗余、內(nèi)存使用和運(yùn)行時(shí)間來檢測數(shù)據(jù)競爭，提高檢測效率[8]。RVPredict將數(shù)據(jù)競爭檢測作為約束求解問題，利用SMT（satisfiability modulo theories）求解器查找數(shù)據(jù)競爭[9]。佘藝等[10]提出了一種基于測試用例生成的Android應(yīng)用數(shù)據(jù)競爭驗(yàn)證方法。然而，由于線程調(diào)度的不確定性，動態(tài)檢測方法會產(chǎn)生很多的漏報(bào)并且運(yùn)行時(shí)開銷較大。與動態(tài)檢測相比，靜態(tài)檢測可以在不運(yùn)行源代碼的情況下分析多線程程序，開銷較小并且檢測更加全面。SIERRA是用于Android應(yīng)用程序中基于事件的靜態(tài)競爭檢測方法[11]。通過NADROID平臺將事件回調(diào)模擬為線程，檢測回調(diào)之間以及線程之間的數(shù)據(jù)競爭情況[12]。IDRC是以Eclipse插件形式存在的交互式工具，可向Java程序員提供早期警告，允許程序員在數(shù)據(jù)競爭變得過于復(fù)雜之前對其進(jìn)行修復(fù)[13]。TAFT等[14]基于模型檢測理論提出一種檢測方法，對程序中鎖操作路徑進(jìn)行分析并通過發(fā)生序關(guān)系過濾結(jié)果。CRSampler通過特定的硬件采樣方式降低檢測的時(shí)間開銷，有效減少了競爭檢測過程中的漏報(bào)[15]。SRD采用程序切片技術(shù)靜態(tài)判斷訪問事件之間的發(fā)生序關(guān)系并結(jié)合別名分析等靜態(tài)分析技術(shù)檢測數(shù)據(jù)競爭[16]。陳俊等[17]通過詞法分析和語法分析進(jìn)行數(shù)據(jù)競爭靜態(tài)檢測。由于忽略了程序執(zhí)行過程中的發(fā)生序關(guān)系，靜態(tài)分析技術(shù)會存在很多誤報(bào)。從目前的研究來看，由于缺乏對上下文敏感性的考慮，大多數(shù)數(shù)據(jù)競爭檢測工具會存在誤報(bào)和漏報(bào)。上下文敏感分析是指在對程序進(jìn)行過程間分析時(shí)，考慮函數(shù)調(diào)用的上下文信息。一個(gè)子過程或函數(shù)可能被多個(gè)過程調(diào)用，在調(diào)用過程中，傳遞給調(diào)用者的實(shí)際參數(shù)或全局變量可能會有所不同，上下文敏感考慮了這些不同。

針對數(shù)據(jù)競爭檢測過程中存在的誤報(bào)和漏報(bào)問題，本文提出了一種基于上下文敏感分析的靜態(tài)數(shù)據(jù)競爭檢測方法。該方法基于WALA[18]軟件分析框架，使用控制流分析、逃逸分析、上下文敏感的別名分析等分析技術(shù)對多線程程序中的數(shù)據(jù)競爭進(jìn)行檢測。首先，利用控制流分析構(gòu)造上下文敏感的函數(shù)調(diào)用圖，利用逃逸分析查找線程逃逸對象以縮小檢測范圍;其次，采用上下文敏感的別名分析分別對別名變量和別名鎖進(jìn)行判斷，減少誤報(bào)和漏報(bào);最后，通過發(fā)生序關(guān)系分析消除由于忽略線程交互而導(dǎo)致的誤報(bào)。在實(shí)驗(yàn)中，選取了8個(gè)基準(zhǔn)測試程序?qū)Ρ疚姆椒ㄟM(jìn)行評估。結(jié)果表明，ConRacer可以有效檢測數(shù)據(jù)競爭，與SRD和RVPredict相比，ConRacer的檢測結(jié)果準(zhǔn)確率更高，可以有效降低漏報(bào)和誤報(bào)。

1 研究動機(jī)

通過一個(gè)示例演示本文的研究動機(jī)，如圖1所示。示例程序中共有2類：MThread和CThread。MThread中包含main（）方法，在方法中創(chuàng)建了2個(gè)子線程T1和T2（行①、行②），并通過start（）方法啟動2個(gè)子線程（行④），然后T1和T2分別執(zhí)行CThread中的run（）方法。對該示例程序進(jìn)行線程內(nèi)和線程間的調(diào)用關(guān)系分析，可以得到各個(gè)線程的調(diào)用關(guān)系描述。

對于線程T1和T2，在同步塊a的保護(hù)下調(diào)用了主線程中的方法m1（）（行⑧），分別對方法m1（）中的域q.f和x.f進(jìn)行了寫操作。然后在無鎖保護(hù)的情況下調(diào)用了方法m2（）。圖2描述了上下文敏感分析的示例，當(dāng)分析T1調(diào)用m1（）時(shí)，上下文不敏感的分析結(jié)果是既訪問了域q.f，也訪問了域x.f，因?yàn)樯舷挛牟幻舾蟹治鰰⒄{(diào)用處信息合并起來傳播給被調(diào)用函數(shù)，并將返回值傳播給所有的調(diào)用函數(shù)。進(jìn)一步的結(jié)果是，3個(gè)線程在調(diào)用m1（）時(shí)均訪問了域q.f和x.f，這會造成很多錯(cuò)誤的變量訪問，從而可能會導(dǎo)致誤報(bào)。

本文采用上下文敏感方式檢測數(shù)據(jù)競爭，將上下文敏感分析技術(shù)應(yīng)用到靜態(tài)分析技術(shù)中，盡可能減少冗余訪問，降低檢測結(jié)果的誤報(bào)和漏報(bào)，提高檢測過程的精度。

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

2.1 檢測框架

數(shù)據(jù)競爭檢測框架如圖3所示。本文基于WALA軟件分析框架對Java源代碼進(jìn)行上下文敏感分析的靜態(tài)數(shù)據(jù)競爭檢測。首先，利用控制流分析構(gòu)造上下文敏感的函數(shù)調(diào)用圖，通過遍歷該調(diào)用圖獲取程序的基本語義信息，然后獲取所有變量的訪問操作。其次，利用逃逸分析查找可能發(fā)生數(shù)據(jù)競爭的線程逃逸對象以縮小檢測范圍。為了提高檢測的準(zhǔn)確性，采用上下文敏感的別名分析分別對別名變量和別名鎖進(jìn)行判斷，從而減少誤報(bào)和漏報(bào)。最后，通過發(fā)生序關(guān)系分析，消除由于忽略線程交互而導(dǎo)致的誤報(bào)。

2.2 控制流分析

控制流分析是指通過分析程序間的控制流及函數(shù)間的調(diào)用關(guān)系構(gòu)造程序的函數(shù)調(diào)用圖。函數(shù)調(diào)用圖是對程序中函數(shù)調(diào)用過程的一種靜態(tài)描述，用圖的形式表示一個(gè)過程內(nèi)函數(shù)之間的調(diào)用關(guān)系。本文在WALA框架下使用方法makeNCFABuilder（）來構(gòu)建調(diào)用圖。調(diào)用圖包含節(jié)點(diǎn)信息和邊信息，其中，節(jié)點(diǎn)表示方法，邊表示方法之間的調(diào)用過程。

首先構(gòu)造上下文敏感的過程間調(diào)用圖，上下文敏感的調(diào)用圖中的節(jié)點(diǎn)除了包括基本函數(shù)信息，還包括函數(shù)調(diào)用的上下文信息。這里記錄節(jié)點(diǎn)的函數(shù)調(diào)用信息作為上下文并進(jìn)行傳播，以保證上下文敏感性的過程間分析。makeNCFABuilder（）方法中存在整型參數(shù)n，對于某一個(gè)方法節(jié)點(diǎn)m，n代表調(diào)用m的方法的深度。例如，n=0時(shí)，即為上下文不敏感的調(diào)用圖節(jié)點(diǎn)，m的上下文信息為EveryWhere，也就是說當(dāng)分析m的調(diào)用時(shí)，需要回退到所有可能的調(diào)用點(diǎn)，此時(shí)分析的精度會有所下降;n=1時(shí)，m的上下文為直接調(diào)用m的所有的函數(shù)集合;n=2時(shí)，m的上下文除了對m的直接調(diào)用還包括間接調(diào)用的所有函數(shù)。由于n的值越大，調(diào)用圖結(jié)構(gòu)越復(fù)雜，分析效率就會隨之降低，故本文選取n=3，即考慮函數(shù)的3層調(diào)用，既保證了一定的上下文敏感性，也考慮了實(shí)驗(yàn)所需時(shí)間。

為了表示一個(gè)訪問事件，這里使用四元組（f，m，o，ls），其中，f為變量訪問操作的內(nèi)存位置;m為變量訪問操作所在的方法或函數(shù);o為變量訪問操作的類型（write/read）;ls為訪問操作擁有的鎖的集合。例如，示例程序中第⑤行表示在主線程MThread中對靜態(tài)變量q的域f進(jìn)行寫（write）操作并且有一個(gè)同步鎖Synchronized（p）保護(hù)，記作（q.f，MThread，write，{p}）。根據(jù)得到的調(diào)用關(guān)系描述以及上下文敏感的調(diào)用圖，可以收集到程序中的所有變量訪問操作。

2.3 逃逸分析

逃逸分析是判斷一個(gè)對象的生命周期是否超過創(chuàng)建它的方法的生命周期。若該對象被多個(gè)線程或方法所訪問，則超過了創(chuàng)建它的方法的生命周期;若只是被單一線程所引用，則相反，此時(shí)，該對象是線程局部對象。線程逃逸對象的定義是：如果一個(gè)對象被2個(gè)或多個(gè)線程所訪問，則稱為線程逃逸對象。

本文采用過程間逃逸分析對所有發(fā)生訪問操作的對象進(jìn)行分析，查找出所有可能發(fā)生數(shù)據(jù)競爭的線程逃逸對象，從而進(jìn)一步縮小檢測范圍。為了判斷一個(gè)對象是否逃逸出線程，本文定義了逃逸判定規(guī)則如下。

逃逸判定規(guī)則1：若對象O存儲于靜態(tài)字段中，或者對象O出現(xiàn)在靜態(tài)字段的可達(dá)路徑上，并且該字段至少被2個(gè)不同線程所訪問，則可判定對象O線程逃逸。

逃逸判定規(guī)則2：若對象O存儲于線程創(chuàng)建字段中，或者對象O出現(xiàn)在線程創(chuàng)建字段的可達(dá)路徑上，并且該字段至少被2個(gè)不同線程所訪問，則可判定對象O線程逃逸。

如圖1所示，訪問變量q和x存儲于靜態(tài)字段中，并且被多個(gè)不同的線程所訪問，根據(jù)逃逸判定規(guī)則1，對象q和x是線程逃逸的，因此有關(guān)訪問變量q和x的所有訪問操作都需要保留，因?yàn)榇嬖诎l(fā)生數(shù)據(jù)競爭的可能性。對于線程T1調(diào)用m2（），在此調(diào)用中存在2個(gè)訪問操作，即（x.f，T1，write，null）和（c.g，T1，write，null）。由圖1可知，將x賦值給了域c.g，即x指向了域c.g，已知x是線程逃逸的，根據(jù)逃逸判定規(guī)則1，對象c出現(xiàn)在了靜態(tài)字段x的可達(dá)路徑上，因此對象c也是線程逃逸的。所以，以上2個(gè)訪問事件同樣存在發(fā)生數(shù)據(jù)競爭的可能性。根據(jù)逃逸判定規(guī)則，可以得到所有可能發(fā)生數(shù)據(jù)競爭的訪問事件，再根據(jù)數(shù)據(jù)競爭定義，對訪問事件進(jìn)行數(shù)據(jù)競爭判定，從而可以得到所有可能的數(shù)據(jù)競爭對。

2.4 上下文敏感的別名分析

在數(shù)據(jù)競爭檢測過程中，別名分析是為了判斷2個(gè)訪問變量是否互為別名。當(dāng)2個(gè)引用變量互為別名時(shí)，它們指向同一個(gè)內(nèi)存位置，其中一個(gè)引用對象的值改變，另一個(gè)引用變量的對象值也會跟著改變。若訪問變量只是名稱相同而內(nèi)存位置不同，則不存在數(shù)據(jù)競爭。

上下文敏感的別名分析是在進(jìn)行別名分析的過程中，將函數(shù)的調(diào)用信息記錄在函數(shù)的指向集中，傳播給被調(diào)用函數(shù)，然后記錄被調(diào)用函數(shù)處的訪問事件的別名信息并傳播給調(diào)用函數(shù)，結(jié)合調(diào)用上下文再進(jìn)一步進(jìn)行別名分析的判斷，從而使檢測過程更加精確。假設(shè)q和x互為別名，則q.f和x.f指向同一內(nèi)存位置，對于MThread中的訪問事件（q.f，MThread，write，{p}）和T2調(diào)用m2（）中的訪問事件（x.f，T2，write，null），根據(jù)數(shù)據(jù)競爭判定條件，該訪問對報(bào)告為一個(gè)真實(shí)數(shù)據(jù)競爭對。若不考慮別名現(xiàn)象，q.f與x.f被作為2個(gè)不同的訪問對象，則會導(dǎo)致實(shí)際的數(shù)據(jù)競爭對被漏報(bào)。

鎖集分析是指判斷可能數(shù)據(jù)競爭對中的2個(gè)變量訪問操作是否具有共同的鎖，若交集不為空，根據(jù)鎖的排他性，2個(gè)變量訪問操作不可能同時(shí)訪問同一內(nèi)存地址，即不存在數(shù)據(jù)競爭故障。例如，對于訪問事件對（q.f，T1，write，{a}）和（x.f，T2，write，{a}），因?yàn)閾碛泄餐逆ia，鎖集交集不為空，因此該訪問對不存在數(shù)據(jù)競爭。別名現(xiàn)象也存在于鎖集分析中，對于（q.f，MThread，write，{p}）和（x.f，T2，write，{a}），若鎖集中的p和a互為別名，則交集不為空，不存在數(shù)據(jù)競爭;若不考慮別名現(xiàn)象，該訪問事件對就會報(bào)告為1個(gè)競爭，導(dǎo)致誤報(bào)。

2.5 發(fā)生序關(guān)系分析

發(fā)生序關(guān)系分析用來判斷訪問事件之間發(fā)生的先后關(guān)系，通過確定發(fā)生順序的先后，可以查找出由于忽略線程交互而造成的誤報(bào)。對于訪問事件A1和A2，發(fā)生序關(guān)系滿足以下條件的最小關(guān)系：

1） 若A1和A2在同一個(gè)線程中，且A1在A2之前，則A1先發(fā)生于A2;

2） 若A1所在線程對A2所在線程執(zhí)行start（）操作，則A1中的start（）操作先發(fā)生于A2所在線程中的所有操作;

3） 若A1所在線程對A2所在線程執(zhí)行join（）操作并成功返回， 則A2先發(fā)生于join（）語句后的所有操作;

4） 若A1先發(fā)生于A2，A2先發(fā)生于A3，則A1先發(fā)生于A3。

在示例程序中，主線程MThread通過start（）方法啟動了線程T1和T2，根據(jù)條件2，MThread中的start（）操作先發(fā)生于T1和T2線程中的所有操作。因此，MThread中的訪問事件（x.f，MThread，write，null）將會先發(fā)生于T1和T2中的所有操作。對于訪問事件對（x.f，MThread，write，null）和（x.f，T2，write，{a}），由于存在發(fā)生序關(guān)系，因此不會發(fā)生數(shù)據(jù)競爭。若忽略了start/join原語，則會將該訪問對判斷為一個(gè)數(shù)據(jù)競爭，因此會造成誤報(bào)。

2.6 分析描述

1） 通過調(diào)用圖構(gòu)造方法makeNCFABuilder（）構(gòu)建程序的上下文敏感的函數(shù)調(diào)用圖cg，通過保守的Thread.start判斷程序是否是單線程，若是，則不存在數(shù)據(jù)競爭;若不是，則繼續(xù)。

2） 從線程調(diào)用節(jié)點(diǎn)開始對cg做深度優(yōu)先遍歷，收集每個(gè)cgNode下的字段訪問指令I(lǐng)nstruction，通過cgNode和Instruction獲取讀寫操作相關(guān)信息并記錄在定義的variableAccess中，收集所有變量訪問存入集合VASet中，variableAccess表示為variableAccess。

3） 逃逸分析主要通過3個(gè)方法收集信息：用getDeclaredStaticFields（）獲取類中的所有靜態(tài)字段;用getAllInstanceFields（）獲取線程構(gòu)造函數(shù)中的實(shí)例字段;用getPointsToSet（）獲取靜態(tài)字段和實(shí)例字段可達(dá)的字段。定義escapeFields并存入所有收集到的字段，定義逃逸訪問操作集合escapeSet，判斷訪問操作的訪問字段是否在escapeFields中，如圖4所示。

4） 遍歷escapeSet找出所有可能的數(shù)據(jù)競爭對存入preRacePairs，對于2個(gè)訪問操作variableAccess_1，variableAccess_2，可能的數(shù)據(jù)競爭對檢測過程如圖5所示。

5） 別名分析主要包含2個(gè)信息contextInfo和insKeySet，getContext（）方法獲取每一個(gè)變量訪問中的contextInfo，其中包含函數(shù)調(diào)用的上下文信息，getInstanceKeySet（）方法獲取變量訪問字段的指向集合，即獲取被調(diào)用的訪問變量的實(shí)例鍵值集合insKeySet。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)配置

所有實(shí)驗(yàn)都是在HP工作站上進(jìn)行的。該工作站中有2.5 GHz Intel Xeon處理器，內(nèi)存為8 GB，操作系統(tǒng)使用Windows 7，使用Eclipse 4.5.1作為檢測工具的開發(fā)平臺，使用JDK 1.8.0_31和程序分析工具WALA 1.4.2。

3.2 測試程序

本文選取8個(gè)基準(zhǔn)測試程序來驗(yàn)證ConRacer的有效性，HelloThread是一個(gè)與圖1類似的小型測試程序。Pingpong和Bbuffer選取自基準(zhǔn)測試組件IBM Contest[19]。Raytracer，Montecarlo和Moldyn均來自JGF[20]基準(zhǔn)測試組件。其中，Raytracer是一個(gè)光線跟蹤程序，Montecarlo是一個(gè)財(cái)務(wù)模擬程序，Moldyn是一個(gè)模擬相互作用的粒子的N體代碼。Sunflow和Lusearch選自Dacapo[21]，Sunflow是使用光線跟蹤渲染圖像的程序，Lusearch是使用lucene進(jìn)行文本搜索的程序。

3.3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文方法的有效性，將ConRacer與現(xiàn)有的數(shù)據(jù)競爭檢測工具SRD和RVPredict的檢測結(jié)果進(jìn)行了對比。實(shí)驗(yàn)結(jié)果如表1所示，其中，“R-races”代表已知的實(shí)際數(shù)據(jù)競爭數(shù)目，“Races”代表檢測出的數(shù)據(jù)競爭數(shù)，“FP”代表誤報(bào)數(shù)，“FN”代表漏報(bào)數(shù)。

使用ConRacer 檢測大部分程序的結(jié)果與實(shí)際競爭數(shù)R-races是相同的，如表1所示。在這些測試程序中，ConRacer的誤報(bào)和漏報(bào)數(shù)目均為0，對于程序Sunflow，ConRacer的檢測結(jié)果與實(shí)際競爭數(shù)目相比，存在1個(gè)誤報(bào)。原因可能在于上下文敏感的別名分析中，高于三級的多層函數(shù)調(diào)用可能會產(chǎn)生上下文不敏感時(shí)的冗余訪問，因此不能避免誤報(bào)的發(fā)生。從數(shù)據(jù)競爭數(shù)目的總數(shù)來看，ConRacer與實(shí)際競爭總數(shù)相比存在1個(gè)偏差，但由于誤報(bào)和漏報(bào)數(shù)較低，因而ConRacer檢測的準(zhǔn)確性相對較高，有效降低了誤報(bào)和漏報(bào)。

與其他檢測工具相比，ConRacer的誤報(bào)總數(shù)目為1個(gè)，而對比工具的誤報(bào)總數(shù)分別為14個(gè)和6個(gè)。由此可知，ConRacer中存在最少的誤報(bào)數(shù)目。例如，對于程序Bbuffer，ConRacer的檢測結(jié)果為12個(gè)，誤報(bào)為0，而SRD中存在4個(gè)誤報(bào)，RVPredict中存在1個(gè)誤報(bào)。這表明ConRacer不僅能夠準(zhǔn)確檢測數(shù)據(jù)競爭，而且還能夠降低誤報(bào)。結(jié)果SRD和RVPredict相比，ConRacer的檢測準(zhǔn)確率分別提高了約34%和14%。SRD中存在最多的誤報(bào)數(shù)目，由于缺乏對逃逸分析和上下文敏感分析的考慮，檢測精度較差，所以該工具中存在較多的誤報(bào)。由于本文采用了上下文敏感的檢測方法，并且結(jié)合了逃逸分析、發(fā)生序關(guān)系分析，減少了冗余訪問的出現(xiàn)，排除了具有發(fā)生序列關(guān)系的訪問事件，因此，本文方法可以有效減少數(shù)據(jù)競爭檢測過程中的誤報(bào)，提高檢測的準(zhǔn)確率。

在漏報(bào)方面，ConRacer的漏報(bào)總數(shù)目為0個(gè)，SRD和RVPredict的漏報(bào)總數(shù)分別為3個(gè)和5個(gè)，RVPredict工具檢測結(jié)果中存在較多的漏報(bào)數(shù)目。例如，對于測試程序Pingpong，ConRacer的檢測結(jié)果為8個(gè)，漏報(bào)數(shù)目為0，而SRD和RVPredict中存在的漏報(bào)數(shù)目分別為3個(gè)和4個(gè)。由于RVPredict將執(zhí)行路徑抽象為訪問事件序列，可能會遺漏對某些路徑的分析，從而導(dǎo)致漏報(bào)。通過分析可以得知，本文使用上下文敏感的別名分析檢測別名情況，從而減少漏報(bào)。因此，ConRacer可以有效地減少檢測過程中的漏報(bào)，具有較高的覆蓋率。

對于Sunflow和Lusearch 2個(gè)較大型測試程序，SRD中共有10個(gè)誤報(bào)，表明SRD對于大型應(yīng)用程序的適用性較差。從檢測到的數(shù)據(jù)競爭總數(shù)目來看，ConRacer與RVPredict相同，但是RVPredict中存在較多的誤報(bào)和漏報(bào)，因此ConRacer的準(zhǔn)確性較高。實(shí)驗(yàn)結(jié)果表明，ConRacer能夠成功地檢測到數(shù)據(jù)競爭并且有效地減少了檢測過程中的誤報(bào)和漏報(bào)。

在檢測時(shí)間方面，ConRacer對于大部分程序的檢測時(shí)間較長，與SRD和RVPredict相比，時(shí)間消耗相對較高，這是因?yàn)楸疚牟捎昧松舷挛拿舾行缘姆椒z測數(shù)據(jù)競爭，由于函數(shù)調(diào)用信息的復(fù)雜性，上下文敏感分析的時(shí)間消耗相對較高，因此降低了實(shí)驗(yàn)過程的檢測效率，但是在消耗時(shí)間的同時(shí)，增加了檢測的準(zhǔn)確率，最大程度保證了程序的正確性。

4 結(jié) 語

針對數(shù)據(jù)競爭檢測過程中的誤報(bào)和漏報(bào)問題，提出了一種基于上下文敏感分析的靜態(tài)數(shù)據(jù)競爭檢測方法。該方法利用控制流分析、逃逸分析等靜態(tài)程序分析技術(shù)檢測數(shù)據(jù)競爭，結(jié)合上下文敏感分析提高檢測精度，降低了檢測過程中的誤報(bào)和漏報(bào)。通過8個(gè)基準(zhǔn)測試程序驗(yàn)證了該方法的有效性，并與2個(gè)現(xiàn)存的檢測工具作對比，結(jié)果表明該方法可以有效檢測數(shù)據(jù)競爭并減少誤報(bào)和漏報(bào)。

本文方法的檢測結(jié)果依然存在誤報(bào)，檢測效率還有待提高。未來的工作包括提升檢測準(zhǔn)確率，降低時(shí)間消耗以及選取更多基準(zhǔn)進(jìn)行測試，以提高工具的適用性。

參考文獻(xiàn)/References：

[1] NETZER R H B， MILLER B P. What are race conditions？ some issues and formalizations[J]. ACMLett Program Lang， 1992， 1（1）： 74-88.

[2] 梁亞楠.并發(fā)環(huán)境下數(shù)據(jù)競爭檢測方法研究[D]. 石家莊：河北科技大學(xué)， 2018.

LIANG Yanan. Research of Data Race Detection in Concurrent Programs[D]. Shijiazhuang： Hebei University of Science and Technology， 2018.

[3] KANG P. Software analysis techniques for detecting data race[J]. IEICE Transactions on Information and Systems，2017：2674-2682.

[4] PAVLOGIANNIS A.Fast，sound，and effectively complete dynamic race prediction[J].Proceedings of the ACM on Programming Languages，2020，4：1-29.

[5] YU M S， BAE D H. SimpleLock+： Fast and accurate hybrid data race detection[J]. The Computer Journal， 2016， 59（6）： 793-809.

[6] YANG Jialin， JIANG Bo， CHAN W K. HistLock+： Precise memory access maintenance without lockset comparison for complete hybrid data race detection[J]. IEEE Transactions on Reliability， 2018， 67（3）： 786-801.

[7] 孫全， 許蕾， 夏昕濛， 等. 使用共享變量分析和約束求解檢測安卓應(yīng)用數(shù)據(jù)競爭[J]. 軟件學(xué)報(bào)， 2019， 30（11）： 3281-3296.

SUN Quan， XU Lei， XIA Xinmeng， et al. Detecting data races in android applications based on shared variable analysis and constraint solver[J]. Journal of Software， 2019， 30（11）： 3281-3296.

[8] PENG Yuanfeng， DELOZIER C， EIZENBERG A. SLIMFAST： Reducing metadata redundancy in sound and complete dynamic data race detection[C]//2018 IEEE International Parallel & Distributed Processing Symposium. [S.l.]： IEEE， 2018： 835-844.

[9] HUANG J， MEREDITH P O， ROSU G. Maximal sound predictive race detection with control flow abstraction[J]. ACM SIGPLAN Notices， 2014， 49（6）： 337-348.

[10] 佘藝， 唐弘胤， 吳國全， 等. 基于測試?yán)傻腁ndroid應(yīng)用數(shù)據(jù)競爭驗(yàn)證方法[J]. 計(jì)算機(jī)科學(xué)， 2017， 44（11）： 27-32.

SHE Yi， TANG Hongyin， WU Guoquan， et al. Concurrency bugs verification in android applications based on test case generation[J]. Computer Science， 2017， 44（11）： 27-32.

[11] HU Y， NEAMTIU I. Static detection of event-based races in android apps[C]// ASPLOS18. Williamsburg： [s.n.]， 2018： 257-270.

[12] FU Xinwei， LEE D， JUNG C. nAdroid： Statically detecting ordering violations in android applications[C]//Proceedings of the 2018 International Symposium on Code Generation and Optimization. New York：ACM Press，2018： 62-74.

[13] OBAIDA M A， JAHAN I， SAJAL S Z. Analysis on interactive data race checker： IDRC[C]//IEEE International Conference on Electro Information Technology. [S.l.]：[s.n.]， 2017： 265-269.

[14] TAFT S T， SCHANDA F， MOY Y. High-Integrity multitasking in SPARK： Static detection of data races and locking cycles[C]//International Symposium on High Assurance Systems Engineering. [S.l.]： IEEE， 2016： 238-239.

[15] CAI Yan， ZHANG Jian， CAO Lingwei， et al. A deployable sampling strategy for data race detection[C]// Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering-FSE 2016. New York：ACM Press， 2016： 810-821.

[16] 張楊，梁亞楠，張冬雯，等.并發(fā)程序中數(shù)據(jù)競爭檢測方法[J].計(jì)算機(jī)應(yīng)用，2019，39（1）：61-65.

ZHANG Yang，LIANG Yanan，ZHANG Dongwen，et al.Data race detection approach in concurrent programs[J].Journal of Computer Applications，2019，39（1）：61-65.

[17] 陳俊， 周寬久， 賈敏. 多線程并行程序數(shù)據(jù)競爭靜態(tài)檢測方法[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2017， 38（5）： 1264-1272.

CHEN Jun， ZHOU Kuanjiu， JIA Min. Multi-thread parallel program data race static detection model[J]. Computer Engineering and Design， 2017， 38（5）： 1264-1272.

[18] IBM. T J Watson Libraries for Analysis（WALA） [EB/OL]. [2020-07-09]. http：//wala.sourceforge.net.

[19] FARCHI E， NIR Y， UR S. Concurrent bug patterns and how to test them[C]//International Symposium on Parallel & Distributed Processing. [S.l.]： IEEE Computer Society， 2003： 286-296.

[20] SMITH L A， BULL J M， OBDRIZALEK J. A parallel Java grande benchmark suite[C]//Proceedings of 2001 ACM. Piscataway： IEEE， 2001. doi：10.1109/SC.2001.10025.

[21] BLACKBURN S M，GUYER S Z，HIRZEL M， et al. The DaCapo benchmarks： Java benchmarking development and analysis[C]//Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-oriented Programming Systems， Languages， and Applications. New York：ACM Press， 2006： 169-190.