張 楊 喬 柳 東春浩 高鴻斌
(河北科技大學(xué)信息科學(xué)與工程學(xué)院 石家莊 050018)
(zhangyang@hebust.edu.cn)
數(shù)據(jù)競爭[1]是指2個或多個線程同時訪問1個內(nèi)存位置并且至少有1個線程執(zhí)行寫操作.數(shù)據(jù)競爭是目前最常見的并發(fā)缺陷之一,它是一種典型的運行時故障,通常在特定的并發(fā)執(zhí)行環(huán)境中發(fā)生,難以被檢測,它的存在會給程序運行帶來潛在的風(fēng)險,嚴重時會導(dǎo)致程序無法正常運行甚至崩潰,造成無法估量的損失,因此迫切需要對數(shù)據(jù)競爭檢測問題進行研究.
數(shù)據(jù)競爭檢測一直是國內(nèi)外并發(fā)缺陷研究領(lǐng)域的熱點問題之一,很多學(xué)者對數(shù)據(jù)競爭檢測問題進行了研究,所采用的方法包括基于動態(tài)程序分析的檢測方法、基于靜態(tài)程序分析的檢測方法、動靜結(jié)合的檢測方法[2-4].基于動態(tài)程序分析的檢測方法在程序運行過程中,通過監(jiān)控程序執(zhí)行路徑和內(nèi)存讀寫訪問等方式檢測數(shù)據(jù)競爭的發(fā)生,這種檢測方式的優(yōu)點在于誤報率較低,缺點是數(shù)據(jù)競爭的漏報率較高,而且檢測過程開銷較大.已有的動態(tài)數(shù)據(jù)競爭檢測工具有Said[5],RVPredict[6],SlimFast[7]等.與動態(tài)數(shù)據(jù)競爭檢測方法不同,靜態(tài)數(shù)據(jù)競爭檢測在源代碼或中間代碼層次展開,通過分析程序中變量的讀寫訪問,輔助以各種靜態(tài)程序分析技術(shù)(如發(fā)生序分析、別名分析、逃逸分析等)進行數(shù)據(jù)競爭檢測.這種檢測方式的優(yōu)點在于可以在程序運行之前排除相關(guān)問題,不僅開銷較小,而且檢測較為全面,漏報率較低;缺點在于僅在代碼層面進行分析而沒有真正運行程序,可能會導(dǎo)致很多誤報,已有的靜態(tài)檢測工具包括RELAY[8],Elmas[9],SRD[10]等.此外,為了彌補以上2種方式各自的不足,有些研究人員也嘗試將動態(tài)分析和靜態(tài)分析2種檢測方法結(jié)合起來,以此提高檢測的整體效率,常用的動靜結(jié)合的檢測工具有RaceTracker[11]和AsampleLock[12]等.
近年來,隨著機器學(xué)習(xí)和深度學(xué)習(xí)技術(shù)的發(fā)展和廣泛應(yīng)用,一些研究人員開始將相關(guān)技術(shù)應(yīng)用于數(shù)據(jù)競爭檢測.在國內(nèi),孫家澤等人[13-14]提出一種基于機器學(xué)習(xí)的數(shù)據(jù)競爭檢測方法,該方法使用隨機森林模型,收集指令級別數(shù)據(jù),進行數(shù)據(jù)競爭檢測,而且他們還基于Adaboost模型進行語句級并發(fā)程序數(shù)據(jù)競爭檢測,該方法的準確率可達92%.在國外,Tehrani等人[15]通過提取文件級別的特征來構(gòu)建數(shù)據(jù)競爭訓(xùn)練數(shù)據(jù)集,他們提出一種基于卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network, CNN)的數(shù)據(jù)競爭檢測方法,實驗表明該方法檢測的準確率在83%~86%.
從目前的研究現(xiàn)狀來看,一些研究人員從程序分析的角度開展數(shù)據(jù)競爭檢測研究,另一些研究人員將程序作為語料庫,使用機器學(xué)習(xí)和深度學(xué)習(xí)方法開展研究,雖然已有的檢測方法取得了一定的成效,但仍存在3個方面的問題亟需進一步研究完善:
1) 目前已有工作所使用的學(xué)習(xí)模型主要依賴于深度學(xué)習(xí)中CNN模型和機器學(xué)習(xí)中隨機森林模型,模型還有待于優(yōu)化,準確率還有提升的空間.
2) 在構(gòu)建數(shù)據(jù)集時,現(xiàn)有的基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測工具[15]僅應(yīng)用了3個不同的基準測試程序,所提取的數(shù)據(jù)集樣本個數(shù)較少,在輸入到深度學(xué)習(xí)模型時會導(dǎo)致檢測精度下降.
3) 在特征抽取時,僅提取指令或文件等級別的某一方面的特征,無法充分反映數(shù)據(jù)競爭的真實情況.
針對目前研究存在的問題,本文提出一種基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測方法DeleRace(deep-learning-based data race detection).該方法首先使用程序靜態(tài)分析工具WALA[16]從多個實際應(yīng)用程序中提取指令、方法和文件級別中多個代碼特征,對其向量化并構(gòu)造訓(xùn)練樣本數(shù)據(jù);然后通過ConRacer[17]工具對真實數(shù)據(jù)競爭進行判定進而標記樣本數(shù)據(jù),并采用SMOTE[18]增強算法使正負數(shù)據(jù)樣本分布均衡化;最后構(gòu)建CNN-LSTM[19]的深度神經(jīng)網(wǎng)絡(luò),加以訓(xùn)練構(gòu)建分類器,進而實現(xiàn)對數(shù)據(jù)競爭的檢測.在實驗中選取DaCapo[20],JGF[21],IBM Contest[22],PJBench[23]這4個基準測試程序套件中的26個基準程序進行數(shù)據(jù)競爭檢測,結(jié)果表明DeleRace的準確率為96.79%,與目前已有的基于深度學(xué)習(xí)的檢測方法DeepRace相比提升了4.65%.與RNN和LSTM相比,DeleRace采用的CNN-LSTM網(wǎng)絡(luò)也具有較高的準確率.此外,我們將DeleRace與已有的動態(tài)數(shù)據(jù)競爭檢測工具(Said和RVPredict)和靜態(tài)數(shù)據(jù)競爭檢測工具(SRD和ConRacer)進行比較,結(jié)果表明DeleRace可以檢測出更多真實有效的數(shù)據(jù)競爭.
本文的主要貢獻有3個方面:
1) 從26個不同領(lǐng)域的實際應(yīng)用程序提取指令、方法和文件等多個級別的特征構(gòu)建深度學(xué)習(xí)模型訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集.
2) 提出一種適合數(shù)據(jù)競爭檢測的深度學(xué)習(xí)模型DeleRace,使用CNN的卷積核提取相關(guān)特征,借助LSTM提取時序特征,通過CNN和LSTM的結(jié)合提升檢測精度.
3) 將DeleRace與現(xiàn)有的基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測工具進行了對比,并與已有的基于程序分析的數(shù)據(jù)競爭檢測工具進行比較,驗證了DeleRace的有效性.
本節(jié)首先給出DeleRace的檢測框架,然后對框架中的每個部分進行詳細介紹.
為了對數(shù)據(jù)競爭進行檢測,提出了一個基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測框架DeleRace.首先,為了構(gòu)建深度學(xué)習(xí)模型的訓(xùn)練數(shù)據(jù)集,DeleRace從DaCapo[20],JGF[21],IBM Contest[22],PJBench[23]四個基準測試程序套件中選取26個含有數(shù)據(jù)競爭的并發(fā)程序,然后使用靜態(tài)程序分析工具提取數(shù)據(jù)競爭發(fā)生位置的上下文特征信息,構(gòu)造訓(xùn)練和測試樣本,并且在樣本數(shù)據(jù)中對真實有效的數(shù)據(jù)競爭進行標記.為了使提取的文本特征樣本更易于被深度學(xué)習(xí)模型所處理,DeleRace使用Keras[24]的嵌入層對訓(xùn)練樣本中文本特征進行向量化.考慮到收集的并發(fā)程序中含有數(shù)據(jù)競爭正樣本數(shù)可能較少,會導(dǎo)致正樣本和負樣本分布不均衡,我們使用數(shù)據(jù)增強算法增加正樣本的數(shù)量,盡可能地保證正負樣本均衡分布.最后,構(gòu)建了一個CNN-LSTM深度神經(jīng)網(wǎng)絡(luò)模型,使用訓(xùn)練集對該模型進行訓(xùn)練,得到訓(xùn)練好的分類器,使用該分類器進行數(shù)據(jù)競爭檢測.基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測框架如圖1所示:
Fig. 1 The framework of DeleRace圖1 DeleRace方法框架
由于目前沒有公開的專門用于數(shù)據(jù)競爭檢測的數(shù)據(jù)集,為了訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)進行數(shù)據(jù)競爭檢測,我們首先構(gòu)建數(shù)據(jù)競爭的訓(xùn)練數(shù)據(jù)集.
已有的方法在提取數(shù)據(jù)競爭特征時相對單一,無法充分體現(xiàn)數(shù)據(jù)競爭的產(chǎn)生條件,例如文獻[13-14]分別提取指令和語句級別的特征,而文獻[15]僅提取了文件級別的特征.為了充分提取特征,我們在構(gòu)建數(shù)據(jù)集樣本時充分考慮了數(shù)據(jù)競爭產(chǎn)生的條件,依據(jù)這些條件提取多個級別的程序相關(guān)特征.
數(shù)據(jù)競爭的產(chǎn)生條件包括:1)2個或多個線程對同一個共享內(nèi)存單元進行并發(fā)訪問;2)至少有1個為寫操作;3)各個操作之間沒有被使用同一監(jiān)視器對象的鎖保護.基于這3個條件,我們從收集的基準程序中選取多個級別的特征來構(gòu)建數(shù)據(jù)集樣本,其中包括訪問操作指令相關(guān)信息(如指令的Hash值、是否為寫操作、是否被同步塊包含、是否被同步方法包含)和數(shù)據(jù)競爭發(fā)生位置的相關(guān)信息(如包名、類名、方法名和變量名),其中前4個特征用于表明數(shù)據(jù)競爭的產(chǎn)生條件,后4個特征用于表明數(shù)據(jù)競爭發(fā)生的位置.
DeleRace借助程序靜態(tài)分析工具WALA[16]進行特征提取,主要操作包括:
1) 通過方法makeNCFABuilder()構(gòu)建程序的控制流圖cg.
2) 遍歷控制流圖cg,收集所有節(jié)點cgNode下的訪問操作,獲取訪問字段中的指令,判斷該指令是否為寫操作,判斷是否被同步塊或同步方法包含,并通過指令對應(yīng)的內(nèi)存地址來生成Hash值,將其作為變量訪問的唯一標識.
3) 通過以上方法獲得所有變量訪問操作,將每個線程的訪問操作存入集合V中,V定義為
V=〈isWrite,hashCode,isSyn,isSynBlock〉,
(1)
其中isWrite表示是否為寫操作,hashCode表示變量訪問操作指令的Hash值,isSyn表示是否被同步方法包含,isSynBlock表示是否被同步塊包含.遍歷每個線程集合中的所有訪問操作,與不同線程的訪問操作進行對比判斷,獲得所有可能存在競爭的訪問操作對.
4) 通過獲取包名、類名、方法名以及所有靜態(tài)變量和實例變量表明每對訪問操作發(fā)生數(shù)據(jù)競爭的位置,判斷其訪問變量是否相同.
這里對特征提取后的表現(xiàn)形式進行演示,如表1和表2所示.表1展示了IBM Contest[22]基準測試程序套件中的Account程序中部分數(shù)據(jù)的數(shù)值特征信息.其中,“讀寫訪問”列中的“1”代表寫操作,“0”代表讀操作;“標簽”列中“1”代表構(gòu)成數(shù)據(jù)競爭,“0”代表不構(gòu)成數(shù)據(jù)競爭;其他列中的“1”代表是,“0”代表否,每一條數(shù)據(jù)樣本包括2個訪問操作,每個訪問操作包含讀寫訪問、Hash值、同步方法、同步塊等4條指令級別的特征.
Table 1 Numerical Feature表1 數(shù)值特征信息
Table 2 Text Feature表2 文本特征信息
表2展示了IBM Contest[22]基準測試程序套件中的Account程序中部分數(shù)據(jù)的文本特征.“標簽”列中“1”表示構(gòu)成數(shù)據(jù)競爭,“0”表示不構(gòu)成數(shù)據(jù)競爭,每一條數(shù)據(jù)樣本包括2個訪問操作,每個訪問操作均包含包名、類名、方法名、變量名等文本特征,其中包名和類名為文件級別的特征,方法名和變量名為方法級別的特征.
Fig. 2 Text feature vectorization圖2 文本特征向量化
我們借助ConRacer[17]工具對真實數(shù)據(jù)競爭進行判定,并對樣本數(shù)據(jù)進行標記.之所以選擇ConRacer工具,是因為ConRacer在對數(shù)據(jù)競爭的分析過程中考慮了方法調(diào)用的上下文信息,誤報和漏報都相對較少.然而在實際應(yīng)用中ConRacer也不是完美的,仍存在一些誤報和漏報,為了確保數(shù)據(jù)集標記的準確性,我們對標記情況進行了手動驗證,保證數(shù)據(jù)集的正確性.
深度學(xué)習(xí)模型在訓(xùn)練時一般采用數(shù)值向量數(shù)據(jù)作為輸入,通常不會直接采用文本數(shù)據(jù).為了使訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)易于被深度學(xué)習(xí)模型所使用,需要把提取的文本特征轉(zhuǎn)化為數(shù)值向量.在文本特征向量化的過程中,由于指令級別的特征信息本身為整數(shù)(如表1所示),因此無需將其向量化;而對于方法和文件級別的特征,由于在特征抽取階段獲得的均為文本數(shù)據(jù)(如表2所示),因此需將其轉(zhuǎn)化為數(shù)值向量.
DeleRace使用Keras[24]的嵌入層進行文本特征向量化,該層采用有監(jiān)督的學(xué)習(xí)方式,基于已經(jīng)標記好的信息進行學(xué)習(xí)并更新權(quán)重,其定義可表示為
f:Mi→Rn,
(2)
其中,Mi表示第i個文本特征的整數(shù)編碼;Rn表示Mi對應(yīng)的n維向量;f是一個參數(shù)化函數(shù)映射,表示將單詞映射到n維向量.
圖2以Account測試程序中某一文件級別的特征信息為例演示了文本特征向量化的過程,這里設(shè)置詞向量維度n=8.首先將單詞表中的單詞進行詞頻統(tǒng)計并進行整數(shù)編碼,將單詞轉(zhuǎn)換為數(shù)值向量時不區(qū)分大小寫,因此單詞Account與單詞account的編碼均為18,其他單詞out,num編碼分別為135,100;然后將每個單詞的編碼M經(jīng)過嵌入層處理后映射為一個8維向量,此時得到文本向量化的表示是隨機的,我們對嵌入層進行訓(xùn)練并更新權(quán)重;最后得到一個真正可以代表每個單詞的數(shù)值向量,單詞間通過各自對應(yīng)的數(shù)值向量反映單詞間相關(guān)性,通過計算均值使每一個單詞僅用一個數(shù)值來表示.
DeleRace在樣本數(shù)據(jù)的提取過程中,由于這些并發(fā)程序中數(shù)據(jù)競爭的數(shù)量很少,導(dǎo)致數(shù)據(jù)集中所提取的含有數(shù)據(jù)競爭的樣本數(shù)遠少于不含有數(shù)據(jù)競爭的樣本數(shù),這導(dǎo)致標簽為正樣本和負樣本的數(shù)量極度不均衡,如果使用該數(shù)據(jù)集進行訓(xùn)練會嚴重影響深度學(xué)習(xí)模型的準確率.為了解決這個問題,通常采用欠采樣(undersampling)和過采樣(oversampling)2種方法.其中,欠采樣方法會從多數(shù)樣本中減少訓(xùn)練實例,該方法只會減少不含數(shù)據(jù)競爭的樣本,雖可以保證數(shù)據(jù)均衡分布,但減少了樣本數(shù)量;過采樣方法通過分析少數(shù)樣本來增加訓(xùn)練實例,有助于增加數(shù)據(jù)競爭的正樣本數(shù).此外,考慮到欠采樣方法一方面可能會因為減掉的數(shù)據(jù)導(dǎo)致某些關(guān)鍵信息丟失,另一方面減少訓(xùn)練樣本也很有可能導(dǎo)致模型精度下降,因此本文采用過采樣方法來達到數(shù)據(jù)均衡分布的目的,既可以保證特征信息的完整,又有助于擴充訓(xùn)練樣本從而提高模型精度.
在過采樣過程中,DeleRace使用SMOTE算法[18]進行數(shù)據(jù)增強,它是一種合成少數(shù)類的過采樣技術(shù),其基本思想是對少數(shù)類樣本進行分析,并根據(jù)少數(shù)類樣本合成新樣本,然后添加到數(shù)據(jù)集中,如圖3所示.這里先選定一個正樣本,找出這個正樣本的K近鄰(假設(shè)K=4),隨機從K個近鄰中選擇一個樣本,在正樣本和被選出的近鄰樣本的連線上隨機找一個點,這個點就是我們生成的新的正樣本,一直重復(fù)這個過程,直到正樣本和負樣本數(shù)量均衡.通過SMOTE算法,將原有的12 836條訓(xùn)練樣本擴充到25 438條,從而使正樣本和負樣本的數(shù)據(jù)樣本數(shù)量達到了均衡.
Fig. 3 SMOTE algorithm[18] 圖3 SMOTE算法[18]
本文采用CNN-LSTM的神經(jīng)網(wǎng)絡(luò)模型,該模型在Keras中實現(xiàn).CNN并非只能處理圖像,在NLP領(lǐng)域也能夠很精準地處理分類任務(wù),比如在情感分析[25]和觀點分類[26]中都發(fā)揮了很好的作用.使用CNN進行文本分類最顯著的優(yōu)勢是其無需人工手動地提取文本特征,可以自動獲取基礎(chǔ)特征并組合為高級特征,訓(xùn)練模型獲得文本特征與目標分類之間的關(guān)系.我們借助CNN模型中卷積層的卷積核提取特征,然后使用最大池化層對上一層卷積層進行降維,既降低提取特征的數(shù)據(jù)維度,又保留了具有代表性的特征.
雖然CNN在處理文本分類問題上存在諸多益處,但由于卷積核的存在,導(dǎo)致CNN在處理時序信號數(shù)據(jù)時存在“長期依賴”問題.針對這一問題,我們選擇了LSTM神經(jīng)網(wǎng)絡(luò)與CNN進行結(jié)合.LSTM是長短期記憶神經(jīng)網(wǎng)絡(luò),可以有效解決“長期依賴”問題,不僅如此,LSTM既能解決RNN在訓(xùn)練時反向傳播帶來的“梯度消失”問題,又能夠獲得源代碼中的語義關(guān)系.源程序中的包名、類名、方法名和變量名多以功能命名,因此不同層次中的語義信息與數(shù)據(jù)競爭息息相關(guān).我們選取不同層次的文本特征,通過LSTM層,可以提取其中的語義關(guān)系[27],例如包含關(guān)系和上下文關(guān)系等,這有助于檢測數(shù)據(jù)競爭,提高檢測精度.
構(gòu)建的CNN-LSTM神經(jīng)網(wǎng)絡(luò)架構(gòu)如圖4所示:
Fig. 4 CNN-LSTM deep neural network model圖4 CNN-LSTM深度神經(jīng)網(wǎng)絡(luò)模型
訓(xùn)練網(wǎng)絡(luò)時,首先將每對訪問操作的特征信息輸入到CNN-LSTM神經(jīng)網(wǎng)絡(luò)中,DeleRace的特征輸入定義為
Input=〈Number_input,Text_input〉,
(3)
Number_input=〈numw,numh,numsm,numsb〉,
Text_input=〈textpa,textc,textm,textv〉,
其中,Input表示分類器的輸入,Number_input表示數(shù)值信息的輸入,numw,numh,numsm,numsb分別表示是否為寫操作、Hash值、是否被同步方法包含和是否被同步塊包含,Text_input表示文本信息的輸入,此時輸入的文本信息已經(jīng)被向量化,textpa,textc,textm,textv分別為包名、類名、方法名和變量名.由于DeleRace的卷積和池化都采用了2維操作,因此用Reshape函數(shù)將數(shù)值向量的1維矩陣轉(zhuǎn)化為2維,然后再將輸入層的輸出傳入2維卷積層中進行自動學(xué)習(xí),每個卷積層后都有一個最大池化層來降低特征維數(shù),避免過擬合.函數(shù)Concatenate把CNN輸出的卷積特征和和LSTM提取的時序特征融合到另一個全連接層進行二分類,并通過Dropout方法來防止過擬合,最終輸出測試程序中含有數(shù)據(jù)競爭的個數(shù).
本節(jié)首先對實驗配置進行介紹;然后對DeleRace進行了實驗評估,并對結(jié)果進行了分析;最后給出了DeleRace與傳統(tǒng)的數(shù)據(jù)競爭檢測工具的對比.
硬件上,所有的實驗都是在Dell Z820工作站上進行的,該工作站配備2個Intel Xeon處理器,主頻為3.2 GHz,內(nèi)存為8 GB.軟件上,操作系統(tǒng)使用Windows 7 Professional,開發(fā)平臺使用Jupyter NoteBook;使用Python3.6和Tensorflow1.9作為深度學(xué)習(xí)的運行支撐環(huán)境;程序分析工具使用WALA1.4.2,使用Eclipse 4.5.1作為WALA的運行平臺,JDK版本為 1.8.0_31.
表3列出了構(gòu)建DeleRace訓(xùn)練集的基準測試程序及其配置信息,這些基準程序主要來源于DaCapo[20],JGF[21],IBM Contest[22]基準測試程序套件.從表3中可以看出,DeleRace從16個訓(xùn)練程序中共提取了12 836個數(shù)據(jù)樣本,由于數(shù)據(jù)集中正負樣本分布不均衡,所以采用SMOTE算法對訓(xùn)練樣本進行擴充,擴充后的訓(xùn)練樣本數(shù)增長了近1倍,總數(shù)為25 438個.Lusearch是較大型的基準測試程序,其提取的訓(xùn)練樣本數(shù)最多,達到了5 683個,經(jīng)過SMOTE算法擴充后樣本數(shù)增加到11 336個.對于Rax基準測試程序,最初只提取了23個訓(xùn)練樣本,經(jīng)過SMOTE擴充后訓(xùn)練樣本增加到36個,是16個基準測試程序中所提訓(xùn)練樣本最少的程序.對于其他基準測試程序,提取的訓(xùn)練樣本數(shù)經(jīng)過擴充后數(shù)量的范圍在98~4 618.
Table 3 Training Dataset表3 訓(xùn)練數(shù)據(jù)集
表4列出了構(gòu)建DeleRace測試集的并發(fā)程序及其配置信息,這些測試程序主要來源于JGF[21],IBM Contest[22],PJBench[23]基準測試程序套件.在Account,AirlineTickets,Boundedbuffer等10個基準程序中提取數(shù)據(jù)樣本作為DeleRace的測試集.表4中列出了這些測試程序及抽取的測試樣本數(shù),其中Boundedbuffer描述生產(chǎn)者-消費者算法,是所有測試程序中提取測試樣本最多的程序,共提取599條測試樣本;Critical是模擬雙線程環(huán)境的測試程序,是所有基準程序中提取測試樣本最少的程序,只有11條測試樣本;其他測試程序的測試樣本數(shù)在25~403.
Table 4 Test Dataset表4 測試數(shù)據(jù)集
在實驗中,我們提出了6個研究問題(research question, RQ),通過回答這些問題對DeleRace方法進行評估.
RQ1:不同特征信息作為DeleRace輸入信息對數(shù)據(jù)競爭檢測結(jié)果有什么影響?如果只考慮幾種特征輸入信息,DeleRace的性能會如何?
RQ2:DeleRace是否能準確有效地檢測出數(shù)據(jù)競爭?
RQ3:DeleRace是否優(yōu)于現(xiàn)有的基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測工具,與其他的深度神經(jīng)網(wǎng)絡(luò)相比,DeleRace的表現(xiàn)會如何?
RQ4:DeleRace是否優(yōu)于傳統(tǒng)的基于動態(tài)分析的數(shù)據(jù)競爭檢測工具?
RQ5:DeleRace是否優(yōu)于傳統(tǒng)的基于靜態(tài)分析的數(shù)據(jù)競爭檢測工具?
RQ6:DeleRace在檢測數(shù)據(jù)競爭時各部分時間性能表現(xiàn)如何?
RQ1關(guān)注的是不同特征信息對數(shù)據(jù)競爭檢測結(jié)果的影響,通過比較部分特征信息和全部指令特征、方法特征和文件特征相結(jié)合的信息檢測結(jié)果,以此來判斷本文所提取的特征是否有效.
RQ2關(guān)注的是DeleRace在各個測試程序中準確率、精確率、召回率和F1值,以此來判斷DeleRace是否可以準確測試出各個程序中是否含有數(shù)據(jù)競爭以及含有數(shù)據(jù)競爭的個數(shù).
RQ3關(guān)注的是DeleRace與其他深度學(xué)習(xí)算法在檢測數(shù)據(jù)競爭上的性能對比.我們選擇現(xiàn)有的基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測算法DeepRace[15]進行對比實驗,并且與RNN和LSTM神經(jīng)網(wǎng)絡(luò)進行對比.
RQ4關(guān)注的是DeleRace與傳統(tǒng)的基于動態(tài)程序分析工具在檢測數(shù)據(jù)競爭上的性能對比.我們選擇現(xiàn)有的基于動態(tài)分析的數(shù)據(jù)競爭檢測算法Said和RVPredict進行對比實驗.
RQ5關(guān)注的是DeleRace與傳統(tǒng)的基于靜態(tài)程序分析工具在檢測數(shù)據(jù)競爭上的性能對比.我們選擇現(xiàn)有的基于靜態(tài)分析的數(shù)據(jù)競爭檢測算法SRD和ConRacer進行對比實驗.
RQ6關(guān)注的是DeleRace在檢測數(shù)據(jù)競爭上的時間性能,針對測試數(shù)據(jù)集上10個開源程序,記錄了DeleRace在整個檢測數(shù)據(jù)競爭時的平均耗時情況.
使用準確率、精確率、召回率、F1作為評價指標評估DeleRace的有效性.分類問題的混淆矩陣如表5所示,其中TP表示將正樣本預(yù)測為正樣本,F(xiàn)P表示將負樣本預(yù)測為正樣本,F(xiàn)N表示將正樣本預(yù)測為負樣本,TN表示將負樣本預(yù)測為負樣本.
Table 5 Confusion Matrix of Binary Classification Problem表5 二分類問題的混淆矩陣
準確率(accuracy,ACC),表示預(yù)測正確的樣本占測試集中所有樣本的比例.
(4)
精確率(Precision),用于描述模型將正樣本預(yù)測為正樣本占測試集中實際預(yù)測為正樣本的比例.
(5)
召回率(Recall),用于描述模型將正樣本預(yù)測為正樣本占測試集中實際預(yù)測正確的比例.
(6)
F1(F-Measure),用于描述精確率和召回率的加權(quán)調(diào)和平均.
(7)
精確率和召回率是相互影響的,通常情況下,精確率升高,召回率會隨之下降,反之亦然.如果測試集中含有數(shù)據(jù)競爭的樣本數(shù)量為0,則會得到值為1的召回率,但精確率卻會很低,因此,F(xiàn)1用來權(quán)衡精確率和召回率之間的關(guān)系,其取值范圍通常在[0,1]之間,F(xiàn)1值越大表示模型性能越好.
為了回答RQ1,我們選擇5個具有代表性的特征與本文所選擇的8個特征進行對比,其對比結(jié)果如表6所示.首先研究特征提取的個數(shù)對于實驗結(jié)果的影響情況,為此我們分別選擇8個特征(見1.3節(jié))和5個特征(包括訪問指令的Hash值、是否含有讀寫操作、發(fā)生數(shù)據(jù)競爭的包名、類名以及方法名)的情況進行實驗對比.實驗結(jié)果如表6所示,其中 “DeleRace-5”代表在5個特征下深度學(xué)習(xí)模型的實驗結(jié)果,“DeleRace-8”代表8個特征下深度學(xué)習(xí)模型的實驗結(jié)果.從實驗結(jié)果可以看出,在DeleRace-8情況下,無論是準確率、精確率、召回率還是F1都比DeleRace-5情況下要高,這表明選取8個特征進行實驗比選取5個特征更能提高數(shù)據(jù)競爭的檢測精度.這里我們沒有對更多的特征個數(shù)進行實驗,主要是因為這8個特征是依據(jù)數(shù)據(jù)競爭的產(chǎn)生條件提取出來的,已經(jīng)可以充分表示數(shù)據(jù)競爭的相關(guān)特征.基于該實驗結(jié)果,在對DeleRace模型進行訓(xùn)練時選擇特征個數(shù)為8.
Table 6 Performance Comparison of Deep Neural Network Models with Different Feature Numbers表6 不同特征數(shù)量下深度神經(jīng)網(wǎng)絡(luò)模型的性能對比 %
Fig. 5 The relationship between accuracy and iteration times for DeleRace圖5 DeleRace準確率與迭代次數(shù)的關(guān)系
在不同特征數(shù)下DeleRace模型的訓(xùn)練過程中,我們還發(fā)現(xiàn)不僅特征提取的個數(shù)對分類精度有一定的影響,而且模型的迭代次數(shù)也會影響最終測試精度和訓(xùn)練時間開銷.我們研究訓(xùn)練的迭代次數(shù)對于實驗結(jié)果的影響情況,這主要基于2方面考慮:1)迭代次數(shù)過少可能會使檢測精度降低;2)迭代次數(shù)過多雖然可以增加檢測精度但會明顯增加訓(xùn)練的時間開銷.為了在檢測精度和時間開銷之間進行折中,我們通過實驗確定相對合適的迭代次數(shù),使其在提高模型檢測精度的同時不會顯著增加訓(xùn)練時間開銷.圖5給出了DeleRace隨迭代次數(shù)的增加時訓(xùn)練和測試準確率的變化情況.從圖5中可以看出,隨著迭代次數(shù)的增加,準確率也會不斷提高,當?shù)螖?shù)增加到50時,準確率接近一個穩(wěn)定值,即使迭代次數(shù)再增加準確率已不再有明顯提升,因此在本實驗中訓(xùn)練DeleRace模型的最佳迭代次數(shù)選擇為50.
為了回答RQ2,我們選用表3中擴充后的25 438個數(shù)據(jù)樣本作為DeleRace的訓(xùn)練集,選用表4中的10個基準測試程序所提取出的1 686個數(shù)據(jù)樣本作為DeleRace的測試集,其檢測結(jié)果如表7所示:
Table 7 Detection Results of DeleRace表7 DeleRace檢測結(jié)果 %
由表7可知,整體上準確率范圍在90.91%~99.30%,F(xiàn)1值在90.27%~99.34%.Account測試程序的準確率和F1值分別為99.30%和99.34%,其準確率、精確率、召回率和F1都是10個測試程序中最高的;而對于Critical基準測試程序,由于只提取了11個數(shù)據(jù)樣本,其各個指標值都是10個基準測試中最低的,造成其性能較差的原因可能是因為含有的數(shù)據(jù)競爭數(shù)較少,進而提取的樣本數(shù)也少,而深度學(xué)習(xí)模型的精度又與數(shù)據(jù)集大小有關(guān),提供的數(shù)據(jù)集樣本越多,效果越好,這可能導(dǎo)致Critical測試程序的檢測精度偏低.
為了回答RQ3,我們將DeleRace與現(xiàn)有的基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測工具DeepRace[15]進行對比,并與單獨使用RNN或LSTM的神經(jīng)網(wǎng)絡(luò)性能進行比較,其實驗對比結(jié)果如表8所示:
Table 8 Performance Comparison of Different Deep Neural Network Models表8 不同深度神經(jīng)網(wǎng)絡(luò)模型性能對比 %
DeepRace[15]是目前已有的基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測工具,由于其數(shù)據(jù)集和模型均未開源,我們無法將其直接與本文方法DeleRace進行比較.為了進行比較,我們根據(jù)文獻[15]中介紹的方法對其工作進行了復(fù)現(xiàn).在比較時,DeleRace,RNN,LSTM,DeepRace都使用相同的訓(xùn)練集和測試集,遵循相同的過程和使用相同的工具來解析源代碼和特征向量化,處理數(shù)據(jù)不平衡問題時也采用了相同的數(shù)據(jù)增強算法,在最大程度上保證了實驗的公平性.與此同時,為了使我們的實驗結(jié)果更為可靠,我們采用10倍交叉驗證的方式來評估DeleRace,即將訓(xùn)練集和數(shù)據(jù)集混合為1份數(shù)據(jù)集,把整個數(shù)據(jù)集隨機分成 10組,用其中9組作為訓(xùn)練集,另外1組作為測試集,重復(fù)這個過程,直到每組數(shù)據(jù)都作過測試集,我們?nèi)?0次結(jié)果的平均值作為我們的最終結(jié)果.實驗結(jié)果如表8所示.
從表8可以看出,DeleRace檢測的準確率為96.79%,F(xiàn)1為96.79%,在4種方法中是最高的,準確率和F1分別比DeepRace高出約4.65%和4.67%,這表明本文方法DeleRace在檢測數(shù)據(jù)競爭方面的性能優(yōu)于DeepRace.此外,我們還將DeleRace與RNN和LSTM網(wǎng)絡(luò)相比,在準確率方面,DeleRace比其他2種網(wǎng)絡(luò)模型高出7%以上,DeleRace的F1值也比其他2種網(wǎng)絡(luò)模型分別高出7.09%,8.23%.實驗結(jié)果表明,無論是準確率還是F1,DeleRace均優(yōu)于采用RNN神經(jīng)網(wǎng)絡(luò)、LSTM神經(jīng)網(wǎng)絡(luò)和DeepRace工具檢測數(shù)據(jù)競爭的方法.
為了回答RQ4,我們將DeleRace與現(xiàn)有的基于動態(tài)程序分析的的數(shù)據(jù)競爭檢測工具Said[5]和RVPredict[6]進行對比,其實驗對比結(jié)果如表9所示,其中R-races表示該程序?qū)嶋H的數(shù)據(jù)競爭數(shù)目.
Table 9 Comparison of DeleRace and Dynamic Data Race Detection Tools表9 DeleRace與動態(tài)數(shù)據(jù)競爭檢測工具的對比
從表9可以看出, Said檢測到數(shù)據(jù)競爭總數(shù)為46個, RVPredict檢測的總數(shù)為52個,而DeleRace檢測到實際競爭的個數(shù)為57個,明顯多于其他2種檢測工具.對于測試程序AirlineTickets,BoundedBuffer,Bufwriter和Weblech,DeleRace檢測到的實際競爭個數(shù)均多于Said檢測到的數(shù)據(jù)競爭個數(shù);對測試程序PingPong,DeleRace檢測到的數(shù)據(jù)競爭個數(shù)比Said和RVPredict檢測到的數(shù)據(jù)競爭個數(shù)多4個,并且使用DeleRace檢測大部分程序的結(jié)果與實際競爭數(shù)#R-races是相同的, DeleRace最貼近真實競爭的個數(shù).
在漏報方面,Said和RVPredict工具的漏報總數(shù)分別為11個和5個,而DeleRace的漏報總數(shù)為1個,相比較而言,DeleRace檢測數(shù)據(jù)競爭時存在較少的漏報.在這些測試程序中,只有在檢測Bubblesort測試程序時存在1個漏報,對于Said和RVPredict也同樣存在1個漏報.漏報可能的原因是將某條標簽為1的文本特征轉(zhuǎn)化成數(shù)值向量時的單詞相關(guān)性較低,從而導(dǎo)致其發(fā)生漏報.
盡管DeleRace檢測的真實數(shù)據(jù)競爭個數(shù)較多且漏報較少,但在誤報方面DeleRace與其他2個檢測工具相比還存在一定的差距.總體來說,Said和RVPredict分別只有8個和13個誤報,但是DeleRace的誤報數(shù)卻有22個.在這些程序中,誤報較多的是BoundedBuffer和Bubblesort測試程序,造成誤報的原因可能是在提取數(shù)據(jù)樣本時標簽為“0”的數(shù)據(jù)樣本過多而標簽為“1”的數(shù)據(jù)樣本過少,造成了數(shù)據(jù)分布不均衡,盡管我們使用了SMOTE數(shù)據(jù)增強算法,使數(shù)據(jù)樣本達到了平衡,但還是不可避免地造成了一些誤報.DeleRace在誤報方面的不足,將驅(qū)使我們進一步完善該方法.
為了回答RQ5,我們將DeleRace與現(xiàn)有的基于靜態(tài)程序分析的的數(shù)據(jù)競爭檢測工具SRD[5]和ConRacer[17]進行對比,其實驗對比結(jié)果如表10所示.
從表10可以看出,DeleRace檢測到的數(shù)據(jù)競爭總數(shù)比SRD檢測到的個數(shù)多17個,漏報個數(shù)比SRD少15個,在誤報方面雖然與SRD相等,但總體而言,DeleRace的性能是優(yōu)于靜態(tài)數(shù)據(jù)競爭工具SRD的.
Table 10 Comparison of DeleRace and Static Data Race Detection Tools表10 DeleRace與靜態(tài)數(shù)據(jù)競爭檢測工具的對比
我們還將DeleRace與ConRacer進行了對比.對于檢測到的實際競爭個數(shù),DeleRace所檢測到的個數(shù)為57個,而ConRacer是53個,本文方法DeleRace比ConRacer所檢測到的個數(shù)多4個.漏報方面,本文方法DeleRace比ConRacer的漏報個數(shù)少4個.盡管DeleRace檢測的真實數(shù)據(jù)競爭個數(shù)較多且漏報較少,但在誤報方面DeleRace與ConRacer相比依舊存在一些差距,ConRacer的誤報個數(shù)僅為6個,但本文方法DeleRace卻為22個,造成誤報較多的原因在2.8節(jié)已經(jīng)進行了說明.我們計劃在下一步的工作中進行改進.
雖然ConRacer工具檢測到的實際競爭個數(shù)比本文方法DeleRace少,且漏報個數(shù)比DeleRace多,但與本文所提到的Said,RVPredict和SRD這3種基于程序分析的數(shù)據(jù)競爭檢測方法相比,ConRacer不僅檢測到的實際競爭個數(shù)最多,而且誤報和漏報均最少,因此ConRacer依舊是較好的檢測工具.針對判定時所出現(xiàn)的誤報和漏報情況,我們對標記情況進行了手動驗證,以保證數(shù)據(jù)集的正確性.
對于回答RQ6,我們評估了DeleRace在檢測數(shù)據(jù)競爭時的時間性能.表11記錄了DeleRace檢測數(shù)據(jù)競爭的整體耗時情況,總時長為3 657.14 s,其中耗時最久的步驟是深度神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練時間,共耗時3 492.42 s,占據(jù)整體檢測時長的95%,主要原因是神經(jīng)網(wǎng)絡(luò)的時間復(fù)雜度和空間復(fù)雜度都會對模型的訓(xùn)練時間產(chǎn)生影響,如果復(fù)雜度過高,很容易導(dǎo)致模型在訓(xùn)練過程中消耗過多的時間,而DeleRace采用了3個卷積層和1個LSTM層處理數(shù)據(jù),獲得了不同的特征并加以合并,層數(shù)深且操作過程較為復(fù)雜,并且迭代次數(shù)過多也會使得訓(xùn)練時間過長,因此在訓(xùn)練模型過程中花費時間較多,耗時比例較高.
Table 11 The Time of Each Step in DeleRace表11 DeleRace完成各個步驟所花費的時間
本節(jié)對實驗過程中威脅有效性的4個因素進行了討論.
1) 本文僅選擇來自DaCapo,JGF,IBM Contest,PJBench這4個基準測試組件中的并發(fā)程序,從這些程序中提取的數(shù)據(jù)競爭數(shù)據(jù)集并不能代表所有程序,因為不同程序可能展現(xiàn)不同的數(shù)據(jù)樣本.為了緩解這個有效性威脅,我們選擇了26個測試程序,這些程序分別來自不同領(lǐng)域,盡可能保證數(shù)據(jù)集來源的多樣性.
2) 我們在對訓(xùn)練數(shù)據(jù)集進行標記時采用了ConRacer工具,盡管該工具采用了上下文敏感的程序分析方法,可以有效地報告數(shù)據(jù)競爭,但該工具仍存在誤報和漏報的情況.為了解決這一問題,我們對報告的數(shù)據(jù)競爭采用手動的方式檢查數(shù)據(jù)競爭位置的代碼,盡可能地排除誤報和漏報,最大程度上保證了數(shù)據(jù)集的準確性.
3) 將文本特征轉(zhuǎn)化為數(shù)值向量時,轉(zhuǎn)化相似度的高低會影響最終結(jié)果的精度.本文采用Keras中的嵌入層進行文本向量化,通過對Keras的嵌入層進行訓(xùn)練并對其參數(shù)進行調(diào)節(jié)使其轉(zhuǎn)化準確率可達98.7%,雖然沒有達到100%的準確率,但通過該技術(shù)轉(zhuǎn)化的數(shù)值向量已經(jīng)在很大程度上接近數(shù)據(jù)競爭的文本特征,有效減少了文本向量化對最終結(jié)果的影響.
4) 在數(shù)據(jù)增強時我們選擇的算法會對訓(xùn)練的最終效果有一定的影響.本文選擇的SMOTE算法是基于隨機過采樣算法的一種改進方案,由于隨機過采樣采取簡單復(fù)制樣本的策略來增加少數(shù)類樣本,容易使模型過擬合,而SMOTE算法采用KNN技術(shù)生成新樣本[28-29],通過計算每個少數(shù)類樣本的K個近鄰,并從中隨機挑選N個樣本進行隨機線性插值,最終構(gòu)造新的少數(shù)類樣本.因此使用SMOTE算法增加正樣本個數(shù),在擴充訓(xùn)練集時有效減小數(shù)據(jù)增強對模型訓(xùn)練的影響.
數(shù)據(jù)競爭檢測的相關(guān)研究仍是目前研究的熱點內(nèi)容之一,所采用的方法有很多,目前可分為基于程序分析的數(shù)據(jù)競爭檢測方法以及基于機器學(xué)習(xí)和深度學(xué)習(xí)的數(shù)據(jù)競爭檢測方法.基于程序分析的數(shù)據(jù)競爭檢測方法通常又分為動態(tài)檢測、靜態(tài)檢測和動靜結(jié)合的檢測方法.
動態(tài)檢測通過運行源程序時插樁等方法獲取并記錄程序運行時狀態(tài).Said等人[5]提出了一種基于SMT解算器的符號分析方法,可以有效地分析線程調(diào)度,準確定位數(shù)據(jù)競爭.RVPredict[6]將數(shù)據(jù)競爭檢測作為約束求解問題,利用可滿足性模理論(satisfiability modulo theories, SMT)求解器查找數(shù)據(jù)競爭.SlimFast[7]通過減少數(shù)據(jù)冗余、內(nèi)存使用和運行時間來檢測數(shù)據(jù)競爭并提高檢測效率.
靜態(tài)方法是基于靜態(tài)源代碼分析,通過程序驗證或符號執(zhí)行的方式分析源碼語義或者程序控制流.RELAY[8]是一種基于流敏感和過程間分析的靜態(tài)數(shù)據(jù)競爭檢測工具.Elmas[9]是基于模型檢測理論提出的一種檢測方法,通過對程序中鎖操作路徑進行分析并通過發(fā)生序關(guān)系過濾結(jié)果.SRD[10]采用程序切片技術(shù)靜態(tài)判斷訪問事件之間的發(fā)生序關(guān)系并結(jié)合別名分析等靜態(tài)分析技術(shù)檢測數(shù)據(jù)競爭.
動靜結(jié)合的檢測方法是先靜態(tài)找出所有可能的數(shù)據(jù)競爭,再利用動態(tài)分析檢測程序.RaceTracker[11]采用動靜結(jié)合的檢測方法,首先使用當前的靜態(tài)檢測器來產(chǎn)生潛在的競爭,然后潛在競爭的代碼位置進行插樁來識別數(shù)據(jù)競爭.AsampleLock[12]是基于優(yōu)化的FastTrack[30]算法和鎖模式的動態(tài)混合數(shù)據(jù)競爭檢測算法,利用采樣技術(shù)監(jiān)控同一時刻同時運行的并發(fā)線程函數(shù)對,再通過預(yù)競爭檢測獲得真正的數(shù)據(jù)競爭的內(nèi)存訪問對.
有些研究人員開始使用機器學(xué)習(xí)和深度學(xué)習(xí)方法來檢測數(shù)據(jù)競爭.Tehrani等人[15]提出基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測工具DeepRace,首先通過變異分析生成特定的數(shù)據(jù)競爭類型,再通過為每個源文件生成AST構(gòu)造數(shù)據(jù)集,最后將向量化的數(shù)值輸入到CNN中進行訓(xùn)練,其檢測準確率在83%~86%.孫家澤等人提出了AIRaceTest[13]和ADR[14]檢測數(shù)據(jù)競爭工具,AIRaceTest是基于隨機森林的數(shù)據(jù)競爭指令級的檢測工具,首先基于HB關(guān)系和Lockset算法指令級檢測數(shù)據(jù)競爭,并利用其分析結(jié)果訓(xùn)練數(shù)據(jù)競爭隨機森林檢測模型,模型精度為92%.ADR是基于Adaboost模型的數(shù)據(jù)競爭語句級檢測工具,將插樁得到的指令內(nèi)存信息進行語句級轉(zhuǎn)化,提取出相關(guān)特征后構(gòu)建Adaboost數(shù)據(jù)競爭檢測模型.與AIRaceTest和DeepRace相比,DeleRace通過提取多個特征,模型性能更好,準確率也更高.
本文提出一種基于深度學(xué)習(xí)的數(shù)據(jù)競爭檢測方法,該方法首先利用WALA工具從多個實際應(yīng)用程序中提取指令、方法和文件等級別的多個特征,對其向量化并構(gòu)造訓(xùn)練樣本數(shù)據(jù),通過ConRacer工具對真實數(shù)據(jù)競爭進行判定進而標記樣本數(shù)據(jù),采用SMOTE增強算法使數(shù)據(jù)樣本均衡化,最后構(gòu)建并訓(xùn)練CNN-LSTM深度神經(jīng)網(wǎng)絡(luò)實現(xiàn)對數(shù)據(jù)競爭的檢測.在實驗中選取10個基準測試程序驗證了該方法的有效性,結(jié)果表明DeleRace的數(shù)據(jù)競爭檢測準確率為96.79%,高于目前已有的基于深度學(xué)習(xí)的檢測方法.此外,我們將DeleRace與已有的動態(tài)數(shù)據(jù)競爭檢測工具(Said和RVPredict)和靜態(tài)數(shù)據(jù)競爭檢測工具(SRD和ConRacer)進行比較,驗證了本文方法的有效性.
進一步的研究工作包括:1)針對本文方法誤報較多的問題,將在未來的工作中通過擴大訓(xùn)練數(shù)據(jù)集、增加含有數(shù)據(jù)競爭的標簽樣本和采用更多軟件分析等方法減少誤報,并且選取更多的基準測試程序?qū)δP瓦M行訓(xùn)練,提高工具的普適性;2)本文使用CNN-LSTM的神經(jīng)網(wǎng)絡(luò)來對數(shù)據(jù)競爭進行檢測,雖然準確率可達96.79%,但仍有可提升的空間,我們將繼續(xù)嘗試對深度學(xué)習(xí)模型進行優(yōu)化,進一步提高檢測精度.
作者貢獻聲明:張楊負責(zé)論文想法的提出、方法設(shè)計、實驗指導(dǎo)、數(shù)據(jù)整理與分析、論文的寫作與修改;喬柳負責(zé)實驗設(shè)計與探究、深度學(xué)習(xí)模型實現(xiàn)、實驗數(shù)據(jù)整理與分析、論文的寫作與修改;東春浩負責(zé)深度學(xué)習(xí)模型實現(xiàn)、部分實驗數(shù)據(jù)整理、論文的修改;高鴻斌指導(dǎo)實驗和論文的修改.