張楊 劉歡 張冬雯

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

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

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

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

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

1 研究動(dòng)機(jī)

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

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

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

2 數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)

2.1 檢測(cè)框架

數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)框架如圖3所示。本文基于WALA軟件分析框架對(duì)Java源代碼進(jìn)行上下文敏感分析的靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)。首先，利用控制流分析構(gòu)造上下文敏感的函數(shù)調(diào)用圖，通過遍歷該調(diào)用圖獲取程序的基本語(yǔ)義信息，然后獲取所有變量的訪問操作。其次，利用逃逸分析查找可能發(fā)生數(shù)據(jù)競(jìng)爭(zhēng)的線程逃逸對(duì)象以縮小檢測(cè)范圍。為了提高檢測(cè)的準(zhǔn)確性，采用上下文敏感的別名分析分別對(duì)別名變量和別名鎖進(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)用圖是對(duì)程序中函數(shù)調(diào)用過程的一種靜態(tài)描述，用圖的形式表示一個(gè)過程內(nèi)函數(shù)之間的調(diào)用關(guān)系。本文在WALA框架下使用方法makeNCFABuilder（）來(lái)構(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，對(duì)于某一個(gè)方法節(jié)點(diǎn)m，n代表調(diào)用m的方法的深度。例如，n=0時(shí)，即為上下文不敏感的調(diào)用圖節(jié)點(diǎn)，m的上下文信息為EveryWhere，也就是說(shuō)當(dāng)分析m的調(diào)用時(shí)，需要回退到所有可能的調(diào)用點(diǎn)，此時(shí)分析的精度會(huì)有所下降;n=1時(shí)，m的上下文為直接調(diào)用m的所有的函數(shù)集合;n=2時(shí)，m的上下文除了對(duì)m的直接調(diào)用還包括間接調(diào)用的所有函數(shù)。由于n的值越大，調(diào)用圖結(jié)構(gòu)越復(fù)雜，分析效率就會(huì)隨之降低，故本文選取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中對(duì)靜態(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è)對(duì)象的生命周期是否超過創(chuàng)建它的方法的生命周期。若該對(duì)象被多個(gè)線程或方法所訪問，則超過了創(chuàng)建它的方法的生命周期;若只是被單一線程所引用，則相反，此時(shí)，該對(duì)象是線程局部對(duì)象。線程逃逸對(duì)象的定義是：如果一個(gè)對(duì)象被2個(gè)或多個(gè)線程所訪問，則稱為線程逃逸對(duì)象。

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

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

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

如圖1所示，訪問變量q和x存儲(chǔ)于靜態(tài)字段中，并且被多個(gè)不同的線程所訪問，根據(jù)逃逸判定規(guī)則1，對(duì)象q和x是線程逃逸的，因此有關(guān)訪問變量q和x的所有訪問操作都需要保留，因?yàn)榇嬖诎l(fā)生數(shù)據(jù)競(jìng)爭(zhēng)的可能性。對(duì)于線程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，對(duì)象c出現(xiàn)在了靜態(tài)字段x的可達(dá)路徑上，因此對(duì)象c也是線程逃逸的。所以，以上2個(gè)訪問事件同樣存在發(fā)生數(shù)據(jù)競(jìng)爭(zhēng)的可能性。根據(jù)逃逸判定規(guī)則，可以得到所有可能發(fā)生數(shù)據(jù)競(jìng)爭(zhēng)的訪問事件，再根據(jù)數(shù)據(jù)競(jìng)爭(zhēng)定義，對(duì)訪問事件進(jìn)行數(shù)據(jù)競(jìng)爭(zhēng)判定，從而可以得到所有可能的數(shù)據(jù)競(jìng)爭(zhēng)對(duì)。

2.4 上下文敏感的別名分析

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

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

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

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

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

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

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

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

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

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

2.6 分析描述

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

2） 從線程調(diào)用節(jié)點(diǎn)開始對(duì)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ù)競(jìng)爭(zhēng)對(duì)存入preRacePairs，對(duì)于2個(gè)訪問操作variableAccess_1，variableAccess_2，可能的數(shù)據(jù)競(jìng)爭(zhēng)對(duì)檢測(cè)過程如圖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作為檢測(cè)工具的開發(fā)平臺(tái)，使用JDK 1.8.0_31和程序分析工具WALA 1.4.2。

3.2 測(cè)試程序

本文選取8個(gè)基準(zhǔn)測(cè)試程序來(lái)驗(yàn)證ConRacer的有效性，HelloThread是一個(gè)與圖1類似的小型測(cè)試程序。Pingpong和Bbuffer選取自基準(zhǔn)測(cè)試組件IBM Contest[19]。Raytracer，Montecarlo和Moldyn均來(lái)自JGF[20]基準(zhǔn)測(cè)試組件。其中，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ù)競(jìng)爭(zhēng)檢測(cè)工具SRD和RVPredict的檢測(cè)結(jié)果進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果如表1所示，其中，“R-races”代表已知的實(shí)際數(shù)據(jù)競(jìng)爭(zhēng)數(shù)目，“Races”代表檢測(cè)出的數(shù)據(jù)競(jìng)爭(zhēng)數(shù)，“FP”代表誤報(bào)數(shù)，“FN”代表漏報(bào)數(shù)。

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

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

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

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

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

4 結(jié) 語(yǔ)

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

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

參考文獻(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ù)競(jìng)爭(zhēng)檢測(cè)方法研究[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] 孫全， 許蕾， 夏昕濛， 等. 使用共享變量分析和約束求解檢測(cè)安卓應(yīng)用數(shù)據(jù)競(jìng)爭(zhēng)[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] 佘藝， 唐弘胤， 吳國(guó)全， 等. 基于測(cè)試?yán)傻腁ndroid應(yīng)用數(shù)據(jù)競(jìng)爭(zhēng)驗(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ìng)爭(zhēng)檢測(cè)方法[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ù)競(jìng)爭(zhēng)靜態(tài)檢測(cè)方法[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.