基于Adaboost 模型的并發(fā)程序數(shù)據(jù)競爭語句級檢測

孫家澤，易 剛，舒新峰

（1.西安郵電大學(xué) 計算機(jī)學(xué)院，西安 710121；2.西安郵電大學(xué) 陜西省網(wǎng)絡(luò)數(shù)據(jù)分析與智能處理重點(diǎn)實驗室，西安 710121）

0 概述

隨著計算機(jī)硬件技術(shù)的更新迭代，多核處理器以及眾核處理器［1］被廣泛應(yīng)用，越來越多的開發(fā)人員使用并發(fā)編程來提高程序的性能，提升了程序的運(yùn)行速度、吞吐量和CPU 利用率。然而，并發(fā)程序內(nèi)部存在并發(fā)性和不確定性，這會導(dǎo)致并發(fā)程序出現(xiàn)死鎖［2］、數(shù)據(jù)競爭［3］、原子性違背［4］、順序違背［5］等難以檢測和修復(fù)的問題。數(shù)據(jù)競爭往往是引發(fā)其他并發(fā)問題的根本原因，在所有的并發(fā)缺陷問題中占較大比例，也是目前研究最多的一類問題［2］。如何有效地構(gòu)建多線程數(shù)據(jù)競爭檢測模型、設(shè)計或改進(jìn)數(shù)據(jù)競爭定位算法以及準(zhǔn)確識別多線程程序中的安全故障，是多線程并發(fā)程序安全性質(zhì)量保障亟待解決的問題，其影響到多核處理器在各個領(lǐng)域的普及與應(yīng)用。

針對數(shù)據(jù)競爭檢測問題，國內(nèi)外已有較多研究成果。在動態(tài)檢測方面，Djit+［6］基于發(fā)生序關(guān)系方法，使用向量時鐘對數(shù)據(jù)競爭進(jìn)行分析，同時還包括FastTrack［7］、LOFT［8］和基于鎖集的檢測工具Eraser［9］。在靜態(tài)檢測方面，常用的檢測工具有RacerX［5］、LOCKSMITH［10］和RELAY［11］。此外，蔡彥等提出一種基于采樣的數(shù)據(jù)競爭檢測方法來降低檢測的開銷，并開發(fā)了檢測工具AtexRace［12］，孫家澤等提出一種基于隨機(jī)森林的數(shù)據(jù)競爭指令級檢測方法，并實現(xiàn)了AIRaceTest 檢測工具［13］。然而，這些檢測方法中仍存在誤報、漏報以及開銷大等問題。

本文基于數(shù)據(jù)挖掘分類模型可高效處理大量數(shù)據(jù)的特點(diǎn)，提出一種以語句對特征作為樣本集建立Adaboost［14］分類模型的方法，實現(xiàn)多線程程序數(shù)據(jù)競爭檢測工具ADR。通過對被測程序進(jìn)行動態(tài)插樁取樣并對插樁［15］結(jié)果進(jìn)行語句級轉(zhuǎn)化提取語句對特征，以此構(gòu)建數(shù)據(jù)競爭Adaboost 檢測模型。由于數(shù)據(jù)競爭最終都可以歸結(jié)到2 條線程交織［16］，因此本文分析來自2 條不同線程的語句對，以簡化檢測過程。

1 數(shù)據(jù)競爭語句級檢測算法

1.1 傳統(tǒng)數(shù)據(jù)競爭檢測

在對被測程序進(jìn)行動態(tài)插樁取樣時，需要取出指令的所在線程ID、指令的讀寫操作op 和指令所訪問的內(nèi)存地址memaddr。根據(jù)數(shù)據(jù)競爭的定義，如果同時滿足以下3 個條件，則判定為數(shù)據(jù)競爭：1）2 條指令或多條指令所在線程ID 不一樣；2）2 條指令或多條指令訪問的內(nèi)存地址一致；3）2 條指令或多條指令中至少有1 條指令的讀寫操作為寫操作。但在實際情況下，該判斷方法會帶來大量的漏報和誤報，因為不同線程存在確定先后關(guān)系，或者存在一個公共鎖以保證針對共享內(nèi)存空間的訪問不會發(fā)生數(shù)據(jù)沖突，在這種情況下會帶來大量的誤報。

1.2 基于語句對特征的數(shù)據(jù)競爭檢測方法

針對傳統(tǒng)數(shù)據(jù)競爭檢測方法誤報率高、檢測精度低的問題，本文提出一種基于語句對特征的數(shù)據(jù)競爭檢測方法。首先對樣本程序集進(jìn)行插樁，提取出語句對的數(shù)據(jù)競爭相關(guān)屬性，然后根據(jù)得到的數(shù)據(jù)集進(jìn)行模型訓(xùn)練，最后根據(jù)得到的分類模型對被測并發(fā)程序進(jìn)行數(shù)據(jù)競爭檢測。本文采用的是集成分類模型。集成分類模型由若干單個分類器組成，相較于單一分類器而言，模型精度會更高。集成分類算法里最常用的是Adaboost 算法和隨機(jī)森林算法，Adaboost 相較于隨機(jī)森林而言，其各個弱分類器之間存在迭代關(guān)系，模型分類準(zhǔn)確率更高。因此，本文先采用Adaboost 算法建立模型，再利用建立好的模型進(jìn)行數(shù)據(jù)競爭檢測。

本文方法的具體檢測過程如下：

1）訓(xùn)練過程

（1）設(shè)樣本并發(fā)程序P 的指令數(shù)為inscount，線程數(shù)為n，利用插樁工具Pin 對被測并發(fā)程序P 進(jìn)行動態(tài)插樁，記錄指令的線程為ID tid，指令訪問的內(nèi)存地址為addr，指令的讀寫操作為op，指令的鎖集為lock。

（2）剔除掉無對應(yīng)原碼的指令以及來自同一條語句的指令，每一條語句僅保留一條指令，將指令級的插樁轉(zhuǎn)換成為語句級插樁。

（3）遍歷所有的語句對，提取出語句對中的Pm、Po、Pv、Pl、Pr這5 項數(shù)據(jù)競爭相關(guān)屬性。

（4）提取特征Pm。語句對a-b的訪問地址分別為memaddr_a 和memaddr_b。如 果memaddr_a=memaddr_b，則Pm為1，反之Pm為0。

（5）提取特征Po。取出語句a對內(nèi)存讀寫模式op_a，取出語句b對內(nèi)存的讀寫模式op_b。如果op_a=op_b，則Po為1，反之Po為0。

（6）提取特征Pv。假設(shè)線程總數(shù)一定，該值為常量MmaxThreads，每一個線程維護(hù)一個向量時鐘，表示為stt[.]，擁有MmaxThreads條記錄。所有線程由［0，MmaxThreads-1］整數(shù)來表示。對于每一個索引u，stt［u］記錄當(dāng)線程u與線程t同步時線程u的本地時間。向量時鐘的更新過程如下：先將每一個線程的向量時鐘本地時間初始化為1：?t：stt[t]←1，?u：stu[u]←1。如果線程t釋放了同步對象，則stt[t]←stt[ ]t+1，如果線程u獲得一個由線程t釋放的同步對象，則線程u更新其向量時鐘，且每一個向量的值更新為此時線程t和線程u的向量的各個維度上的較大值：fori=0 toMmaxThreads-1：stu[i]←max(stu[i]，stt[i])。最 后，根據(jù)得到向量時鐘進(jìn)行偏序判斷，如果兩者之間滿足偏序關(guān)系，則Pv為1，反之Pv為0。

（7）提取特征Pl。對于共享變量v和讀寫鎖m，每次寫訪問變量v并持有鎖m時，將鎖m加入到write_locks_held(t)集合中，每次讀訪問變量v并持有鎖m時，將鎖m加入到locks_held(t)集合中。令locks_held(t)為線程t所持有的鎖，包括寫模式和讀模式。令locks_held(u)為線程u所持有的鎖，包括寫模式和讀模式。C(v)=locks_held(t)∩locks_held(u)，如果C(v)為空集，則Pl為1，反之Pl為0。

（8）提取特征Pr。根據(jù)樣本集已知的結(jié)果，如果該語句對發(fā)生數(shù)據(jù)競爭則Pr為1，否則為0。

（9）模型訓(xùn)練。以Pm、Po、Pv、Pl為特征屬性，以Pr為標(biāo)簽屬性，訓(xùn)練Adaboost 模型。

訓(xùn)練過程的算法描述如下：

2）檢測過程

（1）提取被測并發(fā)線程Pm、Po、Pv、Pl特征屬性。

（2）利用訓(xùn)練好的Adaboost 模型對提取得到的屬性進(jìn)行分析，得到檢測檢測結(jié)果Pr。

（3）如果Pr為0，則發(fā)生數(shù)據(jù)競爭，反之，則沒發(fā)生數(shù)據(jù)競爭。

檢測過程的算法描述如下：

2 Adaboost 模型

本文通過Intel Pin 工具提取出語句對的特征樣本數(shù)據(jù)，并根據(jù)該樣本數(shù)據(jù)建立數(shù)據(jù)競爭Adaboost 檢測模型。本節(jié)具體描述Adaboost 模型的建立過程。

2.1 數(shù)據(jù)采集

數(shù)據(jù)采集過程如下：

1）輸入多線程程序，使用Pin 工具進(jìn)行動態(tài)插樁取樣。

2）記錄程序中該語句所在的線程ID tid。

3）記錄程序中該語句所訪問的內(nèi)存地址memaddr。

4）記錄程序中該語句所對應(yīng)的讀寫操作op。

5）記錄程序中該語句的鎖集lock。

6）程序中該語句所在線程的向量時鐘vectorclock。

7）記錄程序中該語句所在的行號。

8）輸出多線程程序語句的內(nèi)存信息。

表1 列出了從多線程程序中隨機(jī)抽取的5 條案例語句信息，其中：num 表示當(dāng)前語句的編號；op 表示當(dāng)前語句對內(nèi)存進(jìn)行的操作，‘R’表示讀操作，‘W’表示寫操作；memaddr 表示當(dāng)前語句訪問的內(nèi)存地址；line 表示當(dāng)前語句在被測程序中的所在行號；tid表示當(dāng)前語句所在的線程ID，其中主線程的tid 為0，子線程thrd1 的tid 為1，thrd2 的tid 為2，thrd3 的tid為3；locks 表示當(dāng)前指令收到的鎖保護(hù)情況，其中0表示無任何鎖保護(hù)；vectorclock 表示當(dāng)前語句的向量時鐘。

表1 多線程程序語句的內(nèi)存信息Table 1 Memory information of multithreading statement

對表1 中的數(shù)據(jù)進(jìn)行處理，提取出語句對的Pm、Po、Pv、Pl、Pr這5 項特征，如表2 所示。

表2 語句對數(shù)據(jù)數(shù)值化特征表Table 2 Eigenvalue table of statement pair

2.2 Adaboost 模型訓(xùn)練

Adaboost［14］算法的設(shè)計思想主要是針對同一訓(xùn)練集將其訓(xùn)練成不同的分類器并構(gòu)建在一起，最終形成一個更強(qiáng)的分類器。Adaboost 算法流程如圖1所示。首先，每輪迭代中會在新訓(xùn)練集上產(chǎn)生一個新的學(xué)習(xí)器。然后，使用該學(xué)習(xí)器對所有樣本進(jìn)行預(yù)測，以評估每個樣本的重要性。在每一次迭代時，會給每一個樣本賦予一個權(quán)重，根據(jù)每一次預(yù)測的準(zhǔn)確性進(jìn)行動態(tài)調(diào)整，權(quán)重越高的樣本會在下一次訓(xùn)練過程中占越大的比重，即準(zhǔn)確性低的樣本會被著重關(guān)注。

圖1 Adaboost 算法流程Fig.1 Procedure of Adaboost algorithm

本文從Github［17］上選取5組多線程程序來訓(xùn)練Adaboost模型，取出的語句對經(jīng)整合后總數(shù)為60 8631。對整理得到的數(shù)據(jù)進(jìn)行預(yù)處理得到特征數(shù)據(jù)集TestUnity。在特征數(shù)據(jù)集TestUnity 上進(jìn)行Adaboost模型訓(xùn)練時，如果迭代次數(shù)n_estimators 設(shè)定得較低，必然導(dǎo)致模型精確度降低，但如果n_estimators 設(shè)定得較高，也會導(dǎo)致訓(xùn)練模型的開銷增大。因此，需要對其設(shè)定一個合適的值，使模型的精確度達(dá)到要求并且開銷最低。同時，如果決策樹最大深度max_depth 過大也會出現(xiàn)過擬合現(xiàn)象，影響模型精確度。

圖2 顯示了不同的決策樹深度隨著迭代次數(shù)的增加，其分類誤差率的變化趨勢，從中可以看出：當(dāng)max_depth=10 時，隨著迭代次數(shù)的增加，模型的分類誤差率無明顯變換，即泛化能力沒有增強(qiáng)，模型處于過擬合狀態(tài)；當(dāng)max_depth=1 時，迭代次數(shù)逐漸增加時，分類的誤差率也逐漸減少，同時其泛化能力也逐漸增強(qiáng)；但是當(dāng)n_estimators ≥90 時，模型的分類誤差率趨于平穩(wěn)，而當(dāng)max_depth=2時，其誤差率走勢與max_depth=1時相似，但其分類誤差率相對更低。由于在Adaboost模型中選定的弱學(xué)習(xí)器的復(fù)雜度很低，其決策深度一般設(shè)定在1 到2 之間，因此設(shè)定最優(yōu)的max_depth=2，而當(dāng)n_estimators ≥90 時，由于模型的分類誤差率趨于平穩(wěn)，隨著迭代次數(shù)繼續(xù)增加必然導(dǎo)致模型訓(xùn)練的開銷也會不斷增加，因此，本文設(shè)定最優(yōu)的n_estimators為90。

圖2 分類誤差率與迭代次數(shù)的關(guān)系Fig.2 Relationship between classification error rate and iteration times

3 實驗與結(jié)果分析

本節(jié)通過一系列實驗，驗證所提方法的有效性。首先提出研究問題，然后介紹實驗數(shù)據(jù)集，最后總結(jié)并分析實驗結(jié)果。

3.1 研究問題

針對本文所提出的多線程程序數(shù)據(jù)競爭檢測工具ADR，從以下2 個角度出發(fā)進(jìn)行有效性驗證。

1）與Eraser、Djit+等數(shù)據(jù)競爭檢測工具相比，ADR 檢測準(zhǔn)確率是否提升以及提升幅度。

2）與Eraser、Djit+等數(shù)據(jù)競爭檢測工具相比，ADR 的檢測開銷是否有所降低。

3.2 實驗數(shù)據(jù)集

由于目前沒有任何機(jī)構(gòu)或者研究人員發(fā)布數(shù)據(jù)競爭檢測的精確數(shù)據(jù)集，因此本文選擇Github［17］上的1 組已知數(shù)據(jù)競爭結(jié)果的多線程并發(fā)程序進(jìn)行插樁取樣，將插樁結(jié)果作為建立Adaboost 模型的訓(xùn)練集。

實驗環(huán)境為Ubuntu19.04，處理器核心數(shù)為4，運(yùn)行內(nèi)存4 GB。選擇的驗證測試程序來源如下：

1）為驗證Adaboost 數(shù)據(jù)競爭檢測模型的準(zhǔn)確性，在Google Code的data-race-test［18］測試集中篩選出50組多線程并發(fā)程序組成一個測試程序TestCodes進(jìn)行驗證。

2）為驗證Adaboost 數(shù)據(jù)競爭檢測模型的時間開銷和內(nèi)存開銷，選擇SPLASH-2 基本套件［19］中的2 組程序和Parsec 基準(zhǔn)程序3.1［20］中的3 組程序來進(jìn)行驗證。具體如表3 所示。

表3 測試程序信息Table 3 Information of test programs

3.3 實驗過程

ADR 體系結(jié)構(gòu)如圖3 所示，主要由模型構(gòu)建模塊和模型預(yù)測模塊這2 部分組成。本文首先利用樣本程序的插樁結(jié)果訓(xùn)練得到Adaboost 分類模型，然后利用建立好的分類器對待測程序進(jìn)行數(shù)據(jù)競爭檢測。

圖3 ADR 體系結(jié)構(gòu)Fig.3 Architecture of ADR

將ADR 與Eraser、Djit+和Thread Sanitizer 這3 種種動態(tài)數(shù)據(jù)競爭檢測工具進(jìn)行對比實驗。Eraser、Djit+和Thread Sanitizer分別使用的檢測算法是Happen-Before、Lockset 和Happen-Before+Lockset 混 合 算 法。

3.4 檢測精度分析

由于TestCodes 程序由多個小程序示例組成，因此每個小程序示例可能存在零個或者多個數(shù)據(jù)競爭。本文定義以下3 個指標(biāo)來衡量檢測精度：數(shù)據(jù)競爭檢測的誤報數(shù)FP，數(shù)據(jù)競爭檢測的正確數(shù)TP，數(shù)據(jù)競爭檢測的漏報數(shù)FN。4 種檢測工具對TestCodes 程序的數(shù)據(jù)競爭檢測結(jié)果如圖4 所示，已知TestCodes 中真實存在的數(shù)據(jù)競爭次數(shù)為80。

圖4 不同數(shù)據(jù)競爭檢測工具的檢測精度Fig.4 Detection accuracy of different detection tools

從TP 值上來對比分析。ADR 檢測出到79 次數(shù)據(jù)競爭，其檢測準(zhǔn)確度最高。Djit+容易受到線程調(diào)度的影響，所以漏報較多，Eraser 與Thread Sanitizer 由于是在原碼級別進(jìn)行的判斷，會遺漏部分?jǐn)?shù)據(jù)競爭。ADR采用的Adaboost分類模型是由若干個弱分類器組合而成，而且各個弱分類器之間存在迭代關(guān)系，使模型分類準(zhǔn)確率更高。

從FP 值上來對比分析。因為Eraser 對很多確定性同步語句未進(jìn)行處理，所以其誤報數(shù)最多。Dijt+由于其使用的算法是Happen-Before，而ADR 是在語句級上進(jìn)行的實驗，剔除了重復(fù)以及無對應(yīng)原碼的指令信息，因此降低了檢測的誤報數(shù)。

3.5 檢測開銷分析

本文選取SPLASH-2 基本套件中的radix、fft 程序和Parsec 基準(zhǔn)程序3.1 中的streamcluster、deup、x264 組成一個測試程序集，它們的線程數(shù)量呈遞增模式，分別為5、11、17、25、64，對Eraser、Djit+、Thread Sanitizer 與ADR 檢測工具進(jìn)行時間開銷與內(nèi)存開銷方面的對比，如圖5 和圖6 所示。

圖5 不同數(shù)據(jù)競爭檢測工具的檢測時間開銷Fig.5 Comparison of detection runtime overhead of different detection tools

圖6 不同數(shù)據(jù)競爭檢測工具的檢測內(nèi)存開銷Fig.6 Comparison of detection memory overhead of different detection tools

由圖5 可以看出，Thread Sanitizer的檢測時間開銷最大，Djit+的時間開銷僅次于Thread Sanitizer。這是因為Thread Sanitizer和Djit+使用的都是Happen-Before算法，當(dāng)線程數(shù)量很多時，在各個線程之間狀態(tài)切換非常麻煩，增加了時間的開銷，且Thread Sanitizer 還需要判斷鎖集的狀態(tài)，所以時間開銷最大。ADR 通過高效處理大量數(shù)據(jù)建立檢測模型加快了檢測的速度，使檢測的時間開銷更小。綜合檢測數(shù)據(jù)可知，ADR 檢測的時間開銷相比于其他檢測方法降低約29.3%。

由圖6 可以看出，Thread Sanitizer 相比于其他的檢測方法，其檢測的內(nèi)存開銷最大。這是因為Thread Sanitizer 保存了所有并發(fā)歷史訪問的鎖集和向量時鐘，而Djit+保留了所有的歷史訪問的向量時鐘，因此，Thread Sanitizer產(chǎn)生的內(nèi)存開銷最大。ADR 為語句級檢測，在對待測程序進(jìn)行插樁取樣時，每一條語句僅保留一條指令，只需要記錄各個線程在內(nèi)存中的狀態(tài)信息，剔除掉了無對應(yīng)原碼的指令，降低了內(nèi)存開銷。綜合檢測數(shù)據(jù)可知，ADR 檢測所產(chǎn)生的內(nèi)存開銷相比于其他檢測方法降低約21.1%。

4 結(jié)束語

本文提出一種基于語句對特征的數(shù)據(jù)競爭方法。利用插樁工具Pin 對被測并發(fā)程序進(jìn)行動態(tài)插樁，記錄指令的相關(guān)內(nèi)存信息。在此基礎(chǔ)上，通過對指令信息進(jìn)行過濾操作，將指令級插樁轉(zhuǎn)換成語句級插樁，然后根據(jù)樣本數(shù)據(jù)集建立數(shù)據(jù)競爭Adaboost 模型，對被測程序進(jìn)行數(shù)據(jù)競爭檢測，并基于此模型實現(xiàn)數(shù)據(jù)競爭檢測工具ADR。實驗結(jié)果表明，該方法能夠有效降低漏報率與誤報率，同時檢測過程不受線程調(diào)度的影響，可減少檢測的時間開銷和內(nèi)存開銷，提高檢測效率。后續(xù)將在數(shù)據(jù)采集過程中引入采樣策略，減少樣本的數(shù)據(jù)量，從而進(jìn)一步減少數(shù)據(jù)競爭檢測的內(nèi)存消耗，優(yōu)化數(shù)據(jù)競爭的檢測效率。此外，在基于語句對特征的數(shù)據(jù)競爭方法中融入更優(yōu)的采樣策略，也將是下一步的研究方向。