[發(fā)明專利]基于靜態(tài)共享變量識別的動態(tài)數(shù)據(jù)競爭檢測方法

有效

• 申請?zhí)枺?/td>: 201110103794.0
• 申請日: 2011-04-25
• 公開（公告）號: CN102760095A
• 公開（公告）日: 2012-10-31
• 發(fā)明（設(shè)計）人: 鄭緯民;盛田維;陳文光;蔣運韞
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩

技術(shù)領(lǐng)域

本發(fā)明涉及計算機軟件可靠性技術(shù)領(lǐng)域，特別涉及一種基于靜態(tài)共享變量識別的動態(tài)數(shù)據(jù)競爭檢測方法。

背景技術(shù)

隨著底層多核處理器的發(fā)展，并發(fā)程序越來越受到程序員的歡迎。但是并發(fā)程序不僅不易正確編寫，而且會出現(xiàn)各種難以調(diào)試和重現(xiàn)的軟件缺陷。數(shù)據(jù)競爭是引起并發(fā)程序軟件缺陷的重要原因之一。數(shù)據(jù)競爭是指多個線程沒有同步保護地訪問同一個內(nèi)存地址，且至少一個訪問是寫操作。因為其會導(dǎo)致嚴重的后果，學(xué)術(shù)界和工業(yè)界一直試圖找到一種有效的檢測方法。

現(xiàn)有的數(shù)據(jù)競爭檢測方式都基于軟件插裝的方法，主要分為兩類：程序運行前的靜態(tài)插裝和程序運行中的動態(tài)插裝。程序運行前的靜態(tài)插裝工具在程序真正運行前對源代碼或者二進制文件進行插裝，得到一個插裝后的二進制代碼，最后按照原始程序的運行方式執(zhí)行插裝程序。程序運行中的動態(tài)插裝在程序執(zhí)行的過程中動態(tài)插入插裝指令，現(xiàn)有的動態(tài)插裝工具一般采用類似Java虛擬機的即時執(zhí)行方式，在執(zhí)行過程中動態(tài)翻譯執(zhí)行用戶程序指令并插入插裝指令。相對于靜態(tài)插裝，動態(tài)插裝方式的功能更加豐富且方便使用(比如不需要重新編譯鏈接程序，可以監(jiān)控運行進程等)。現(xiàn)有的廣泛使用的插裝工具Pin和Valgrind都采用動態(tài)插裝方式。

對于數(shù)據(jù)競爭，不管是動態(tài)插裝方式，還是靜態(tài)插裝方式，都面臨著開銷和于擾性的問題。在典型應(yīng)用程序中，不管是串行還是并行程序，內(nèi)存訪問操作數(shù)量占的比例都很大，因此數(shù)據(jù)競爭檢測的開銷和干擾性主要來源于對于內(nèi)存操作的插裝。最新的研究提出了基于采樣的方法，也即不需要插裝程序中所有的內(nèi)存訪問，而只以采樣的方式插裝一部分內(nèi)存訪問操作。對于采樣，首先要解決的問題是采樣的對象或者粒度。現(xiàn)有的一個方法(參考LiteRace：effective?sampling?for?lightweight?data-race?detection，PLDI′09?Proceedings?of?the?2009?ACMSIGPLAN?conference?on?Programming?language?design?and?implementation)采用一個基于函數(shù)粒度的采樣，也就是針對一個函數(shù)，統(tǒng)計其動態(tài)執(zhí)行過程運行的次數(shù)，不同函數(shù)以不同的概率各自進行采樣而不互相干擾。但是其選取函數(shù)作為采樣粒度并不合適，主要存在下面的問題：

1、采樣檢查開銷增大。程序中大多數(shù)的函數(shù)都和數(shù)據(jù)競爭無關(guān)，盲目對每個函數(shù)檢查采樣會使檢查開銷增大。如果某個熱點函數(shù)中不涉及數(shù)據(jù)競爭，而基于函數(shù)粒度采樣的方法每次運行這個函數(shù)之前都需要檢查采樣條件，這會引入額外不必要的開銷。如果檢查采樣的代碼實現(xiàn)的不合理，這個開銷有時候會達到20％。

2、代碼膨脹。一個函數(shù)體如果很大，但是真正與數(shù)據(jù)競爭相關(guān)的只是其中的一小部分代碼區(qū)域，基于函數(shù)粒度的采樣會復(fù)制整個函數(shù)，并在復(fù)制的函數(shù)中加入插裝代碼，這必然會引起程序代碼膨脹，對程序產(chǎn)生干擾。

總之，現(xiàn)有基于函數(shù)粒度的采樣方法沒有考慮并發(fā)程序缺陷或者數(shù)據(jù)競爭的特性。

發(fā)明內(nèi)容

(一)要解決的技術(shù)問題

本發(fā)明要解決的技術(shù)問題是：如何以較小的資源開銷代價實現(xiàn)動態(tài)數(shù)據(jù)競爭檢測。

(二)技術(shù)方案

為解決上述技術(shù)問題，本發(fā)明提供了一種基于靜態(tài)共享變量識別的動態(tài)數(shù)據(jù)競爭檢測方法，包括以下步驟：

S1：識別待檢測程序的共享變量；

S2：對所述待檢測程序中包含共享變量的基本塊進行數(shù)據(jù)競爭檢測插裝和采樣，得到所述待檢測程序經(jīng)插裝和采樣后的二進制代碼，所述基本塊是指一個連續(xù)的程序語句序列，控制流從它的開始進入，并從它的末尾離開，中間沒有中斷或者分支；

S3：運行所述二進制代碼動態(tài)檢測所述待檢測程序中的數(shù)據(jù)競爭。

其中，所述步驟S1具體包括：

S1.1：讀取所述待檢測程序的源代碼，為源代碼中的每一個函數(shù)建立函數(shù)信息，對所有函數(shù)根據(jù)其調(diào)用關(guān)系建立一個不完整的函數(shù)調(diào)用圖，不完整的函數(shù)調(diào)用關(guān)系圖不包括函數(shù)中指針的調(diào)用關(guān)系；

S1.2：對函數(shù)進行上下文敏感的指針分析，并構(gòu)建完整函數(shù)調(diào)用圖，指針分析的結(jié)果為每一個函數(shù)建立一個指針別名圖。指針別名圖的結(jié)點代表該函數(shù)中可以訪問的內(nèi)存空間，邊代表結(jié)點之間的指向關(guān)系，指針分析還需要建立函數(shù)調(diào)用者指針和被調(diào)用者指針的指向圖之間的關(guān)系；

S1.3：采用自底向上的方式遍歷線程間完整的函數(shù)調(diào)用圖，識別出共享變量。

其中，所述函數(shù)信息包括：符號表信息、中間表示結(jié)構(gòu)。

其中，所述步驟S2具體包括：