基于Adaboost 模型的并發程序數據競爭語句級檢測

孫家澤，易 剛，舒新峰

（1.西安郵電大學 計算機學院，西安 710121；2.西安郵電大學 陜西省網絡數據分析與智能處理重點實驗室，西安 710121）

0 概述

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

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

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

1 數據競爭語句級檢測算法

1.1 傳統數據競爭檢測

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

1.2 基于語句對特征的數據競爭檢測方法

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

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

1）訓練過程

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

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

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

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

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

（6）提取特征Pv。假設線程總數一定，該值為常量MmaxThreads，每一個線程維護一個向量時鐘，表示為stt[.]，擁有MmaxThreads條記錄。所有線程由［0，MmaxThreads-1］整數來表示。對于每一個索引u，stt［u］記錄當線程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])。最 后，根據得到向量時鐘進行偏序判斷，如果兩者之間滿足偏序關系，則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。根據樣本集已知的結果，如果該語句對發生數據競爭則Pr為1，否則為0。

（9）模型訓練。以Pm、Po、Pv、Pl為特征屬性，以Pr為標簽屬性，訓練Adaboost 模型。

訓練過程的算法描述如下：

2）檢測過程

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

（2）利用訓練好的Adaboost 模型對提取得到的屬性進行分析，得到檢測檢測結果Pr。

（3）如果Pr為0，則發生數據競爭，反之，則沒發生數據競爭。

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

2 Adaboost 模型

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

2.1 數據采集

數據采集過程如下：

1）輸入多線程程序，使用Pin 工具進行動態插樁取樣。

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

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

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

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

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

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

8）輸出多線程程序語句的內存信息。

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

表1 多線程程序語句的內存信息Table 1 Memory information of multithreading statement

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

表2 語句對數據數值化特征表Table 2 Eigenvalue table of statement pair

2.2 Adaboost 模型訓練

Adaboost［14］算法的設計思想主要是針對同一訓練集將其訓練成不同的分類器并構建在一起，最終形成一個更強的分類器。Adaboost 算法流程如圖1所示。首先，每輪迭代中會在新訓練集上產生一個新的學習器。然后，使用該學習器對所有樣本進行預測，以評估每個樣本的重要性。在每一次迭代時，會給每一個樣本賦予一個權重，根據每一次預測的準確性進行動態調整，權重越高的樣本會在下一次訓練過程中占越大的比重，即準確性低的樣本會被著重關注。

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

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

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

圖2 分類誤差率與迭代次數的關系Fig.2 Relationship between classification error rate and iteration times

3 實驗與結果分析

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

3.1 研究問題

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

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

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

3.2 實驗數據集

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

實驗環境為Ubuntu19.04，處理器核心數為4，運行內存4 GB。選擇的驗證測試程序來源如下：

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

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

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

3.3 實驗過程

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

圖3 ADR 體系結構Fig.3 Architecture of ADR

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

3.4 檢測精度分析

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

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

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

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

3.5 檢測開銷分析

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

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

圖6 不同數據競爭檢測工具的檢測內存開銷Fig.6 Comparison of detection memory overhead of different detection tools

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

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

4 結束語

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