梁帥帥 李蘭英

摘? 要：針對多線程程序同時讀寫同一塊內存產生的數據競爭，已有的檢測方法漏檢率和誤檢率較高，文章結合靜態(tài)RELAY法和動態(tài)Eraser鎖集法，利用數據流的靜態(tài)法對共同鎖集的判斷和動態(tài)法對共同鎖集的保護，有效地降低誤檢率和漏檢率。為減少因重復交織出現的冗余，提出使用重復檢測器減少重復檢測的數據競爭，提升了檢測性能，降低了檢測開銷。

關鍵詞：數據競爭;動靜態(tài)檢測;重復檢測器

中圖分類號：TP311.5? ? ? 文獻標識碼：A 文章編號：2096-4706（2020）17-0069-03

Abstract：In view of the data competition generated by multi-threading programs reading and writing the same memory at the same time，the existing detection methods have high miss detection rate and false detection rate. This paper combines the static RELAY method and dynamic ERASER lock set method，uses the static method of data flow to judge the common lock set and the dynamic method to protect the common lock set，so as to effectively reduce the false detection rate and missed detection rate. In order to reduce the redundancy caused by repeated interleaving，the use of duplicate detector to reduce the data competition of repeated detection is proposed，which improves the detection performance and reduces the detection overhead.

Keywords：data race;dynamic and static detection;repetitive detector

0? 引? 言

程序中并發(fā)性bug越來越多，常見的bug有四種類型：死鎖、數據競爭、原子性違背和順序違背。數據競爭指在非線程安全的情況下，多線程對同一個地址空間進行寫操作，需花費大量時間進行調試和修復，很多學者提出了很多檢測方法，靜態(tài)檢測方法主要使用RELAY[1]、Locksmith、RacerX等;本文所述動態(tài)檢測主要使用鎖級法、先發(fā)生于算法。

因很難確定程序操作實際影響到哪些內存、被訪問的值是局部范圍還是全局范圍、是否通過參數傳遞到函數中，RELAY、Locksmith等方法能調用上下文敏感分析來確定訪問內存的實際位置，但每個位置上持有哪些鎖，程序操作獲取和釋放了哪些鎖，這些鎖是否有可能通過參數傳入的結構派生而來的都無法確定。RELAY、Locksmith等方法在兩個不同訪問處，鎖持有的鎖集的交集進行判斷是否為可疑數據競爭。Flanagan等人的先發(fā)生于算法提出更新時鐘向量，通過時鐘向量狀態(tài)判斷相關讀寫訪問信息。

為提升并發(fā)缺陷相關方向的效率，降低漏檢和誤檢率，加強程序的正確性和可操作性，校內相關國家自然基金課題也對并發(fā)缺陷數據競爭進一步研究，根據學者提出的算法，本人進行復現、改進。研究時基于數據流分析和鎖集REALY方法，先進行上下文敏感分析，計算函數相對鎖集和保護訪問集，然后判斷相關鎖集是否有交集，再使用Eraser[2]方法對相關鎖集進行保護，如果有可疑的數據競爭將被進行刪除，隨后再根據檢測過程中檢測出的可疑競爭所在位置的程序段進行分步驟重復檢測，本文動靜結合檢測方法減少了動態(tài)檢測的漏檢率和靜態(tài)檢測的誤檢率，并解決了一些數據競爭重復檢測的問題。在檢測并發(fā)缺陷后，使用重復檢測器再一次進行篩選，時間、空間開銷會有所減少。

1? FPX的算法描述

首先靜態(tài)RELAY法對符號執(zhí)行的局部和全局傳入值跟蹤內存位置中包含的值，使用元變量x∈X表示局部和全局，符號值的集合V表示符號分析計算的值，整數init（x）是x的局部值;must（x）表示一個必須指向x的值;may（x）表示一個可能指向x中的任何左值。符號執(zhí)行跟蹤每個程序點上的符號映射，并使用函數更新這個符號映射。簡單賦值x：= e的函數，將當前映射中的e計算為一個符號值，然后更新映射中的x。對于通過指針進行的賦值，也就是?x：=e，函數將x計算為一個符號值v1，將e計算為一個符號值v2，存儲中更新哪些x取決于值v1。

鎖集的結果存儲為XLock（f）∈L，表示函數末尾的相對鎖集。將鎖和解鎖操作為鎖集函數調用，修改鎖集函數調用e（a）。lock（l）函數為（{l}，{ }）的相對鎖集摘要，unlock（l）函數為（{ }，{l}）的相對鎖集摘要，相對鎖集產生的摘要表從開始執(zhí)行到返回的鎖集中的變化。查找調用f后的相對鎖集，將更新后的鎖集信息傳入的相對鎖集[3]。鎖集分析完成對給定函數的所有程序點的相對鎖集的計算，保護訪問使用這些信息來計算函數執(zhí)行的保護訪問集合。保護訪問集合是一個triple a=（x，L，k），x值被訪問，l∈L是當前鎖的訪問，k代表鎖的類型即讀鎖或寫鎖;訪問設置更新（s，L）。

當處理完函數中的所有語句后，最后的保護訪問集將成為函數的訪問摘要。最終能計算出該線程的入口函數的保護訪問集，對于共享變量v的來自不同線程T1和T2的2個保護訪問（o，，k）和（o′，，k′），其中，o是左值被訪問，L+是進程所獲取的鎖的集合，L-是進程所釋放的鎖的集合。獲取保護它們的鎖集的交集，如果交集為空，則這2個訪問就構成一個可疑的數據競爭。使用靜態(tài)檢測的數據競爭誤檢率高，所以使用動態(tài)檢測降低誤檢率，如下述使用Eraser鎖集算法動態(tài)檢測在靜態(tài)檢測鎖集和保護訪問集結果的基礎上對共享變量的保護訪問應受到共同鎖集的保護，并不斷更新鎖集向量時鐘[4]的信息，通過線程調度發(fā)現真實數據競爭，然后剔除數據競爭，從而降低誤檢率。

Eraser lockset algorithm

Input：thread t's lock set and sharevarable v's candidate lock set

Output：null or a race warning

Let Lt be the set of locks held by thread t;

For each shared variable v，CL（v） stands v's candidate locks

namely the set of locks consistently protecting v.Initially， CL（v） is set to be all locks;

Let prev be the previous access to v before the current access to v.Initially，prev is nil;

Let mode（x）be a map from access x to its type，namely READ or WRITE;

foreach access a to v by thread t do

CL（v）←CL（v）∩Lt;

if CL（v）=0&&?。╩ode（a）=READ&&mode

（prev）=READ） then

return a race warning（v，prev，a）;

return;

算法檢測后有大量的數據競爭重復檢測，在上述動靜態(tài)檢測后加一個檢測器，來過濾重復檢測，描述如下：檢測器由多個步驟組成，最重要的步驟是預測步驟和驗證步驟。預測步驟檢查動態(tài)的執(zhí)行，基于動態(tài)檢測模式預測潛在的重復數據競爭;驗證步驟主動控制線程調度[5]，驗證許多重新執(zhí)行中的數據競爭。第一步可能會產生許多重復的數據競爭，給第二步帶來許多重復的新執(zhí)行，這將影響并發(fā)性數據競爭檢測的效率。在第一步中預測潛在的競爭（兩個數據競爭），如果S1->S3->S2之間的潛在競爭已經被檢測，則無需再次檢測S1->S3和S3->S2之間的其他兩個潛在競爭。比如S1-> S3->S2的實例iS1->iS3->iS2表示兩個線程之間的三個內存訪問事件，S1->S3的實例iS1->iS3表示兩個線程之間的兩個內存訪問事件，而實例iS1->iS3無需檢測，因為另一iS1->iS3->iS2已經包含了這個實例。如果S1->S3和S3-> S2在檢測時沒有進行重復檢測，那么效率會得到明顯提高。檢測器算法描述如下：

Dynamic detector after Eraser detect Event 1、Event 2、Event 3.

Let detect the set of lock by FPX

For search Datarace in the set lock and detect repeat

If search （Event 1—>Event 3）∩（Event 1—>Event 2—> Event 3） = Event 1—> Event 3

Return Event 1—>Event 2—>Event 3

Break repeat lock

Elseif Event 2—>Event 3∩（Event 1—> Event 2—>Event 3） = Event 2—> Event 3

Return Event 1—>Event 2—>Event 3

Break repeat lock

Return Event 1—>Event 2—>Event 3

2? 實驗結果分析

RELAY算法能檢測數據競爭，誤檢率高，但相對于一般檢測方法漏檢率低，檢測出程序中的數據競爭即報錯。針對誤檢問題動態(tài)使用Eraser鎖集算法，因對鎖集的時鐘向量信息不斷更新，最終獲取時鐘信息判斷數據競爭，因此誤檢率較低。

對相關論文重新實現了這些檢測工具和算法。對比實驗在同一環(huán)境下進行，保證了實驗結果具有可比性。對FPX、RaceChecker和RaceFuzzer進行驗證，結果如表1所示，其中前三列表示檢測工具RaceChecker、FPX、RaceFuzzer檢測出的數據競爭對數目，RC、FPX、RF表示RC和FPX、RaceFuzzer檢測過程中的潛在可疑的數據競爭對數。為評測和對比分析FPX對目標程序的性能影響，在fft、lu、radix等程序上分別運行來檢測驗證RaceFuzzer[6]、RaceChecker和FPX。

表2是在動靜態(tài)檢測方法檢測前的重復數據競爭數量和使用重復數據競爭檢測器檢測后的數據競爭數量對比表，其中檢測工具檢測程序5 000行左右，在檢測器下，檢測重復數據競爭前和檢測重復數據競爭后的數據對比。

為了更能清晰地看出重復檢測器檢測效率的提升，如圖1所示，沒有檢測前的數據競爭數量和使用重復檢測器后的數據競爭的數量效率對比，在多種檢測方法下，針對三種不同的檢測器重復檢測出的數據競爭數目有所減少，開銷效率提升4%，但還存在一些問題有待繼續(xù)研究，例如檢測器檢測的數據競爭，在必要條件非常高的時候，有檢測器的開銷是否比沒有檢測器的開銷還要大。