面向死鎖規(guī)避的路徑敏感插裝

齊鵬　禹振　蘇小紅　馬培軍

摘 要：程序插樁技術(shù)是一種基本的測試手段，在軟件測試中被廣泛的應(yīng)用。插裝方式是指在程序源碼中插入一些語句，通過這些語句可以獲得所需要的信息，在死鎖規(guī)避的靜態(tài)分析中需要通過程序插裝的方式記錄下一些信息。程序插裝按照源程序的結(jié)構(gòu)分為順序結(jié)構(gòu)的插裝，分支結(jié)構(gòu)的插裝和循環(huán)結(jié)構(gòu)的插裝。在對源程序進(jìn)行詞法語法分析的基礎(chǔ)上建立抽象語法樹和控制流圖，根據(jù)控制流圖獲取程序可能執(zhí)行的所有路徑信息，接著根據(jù)路徑信息決定插裝的內(nèi)容。

關(guān)鍵詞：詞法分析；語法分析；抽象語法樹；程序插裝

中圖分類號：TP311 文獻(xiàn)標(biāo)識號：A

Deadlock Avoidance Oriented Path Sensitive Instrumentation

QI Peng， YU Zhen， SU Xiaohong， MA Peijun

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract：The instrumentation of the program is a basic test method， which is widely used in software testing. In instrumentation method is to insert some of the statements in the program source code， the required information is available through these statements， in static analysis of the deadlock avoidance through program instrumentation some information needs to be recorded. Procedures for the insertion into the structure of the source code structure is divided into the order of the structure of the insert， the branch structure of the insert and the structure of the loop. In this paper， on the basis of the lexical and syntax analysis of the source program to establish abstract syntax tree and control flow graph， according to the control flow graph to obtain the program may perform all path information， then according to the route information to decide the inserted content.

Keywords：Lexical Analysis； Syntax Analysis； Abstract Syntax Tree； Program Instrumentation

0 引 言

程序插樁（Program Instrumentation）技術(shù)是一種基本的測試手段，由J.G.Huang教授首次提出，并已在軟件測試中獲得了廣泛的應(yīng)用。其目的是在保障源程序的邏輯和功能不被破壞的情況下，向源程序插入一些語句，這些語句可以記錄或者輸出一些需要關(guān)注的信息，進(jìn)一步通過這些信息了解執(zhí)行過程中程序的一些動(dòng)態(tài)特性。

Clang是一個(gè)支持 C，C++，Object-c及Object-c++等語言的編譯器前端。在本文中即使用了Clang對源碼經(jīng)過詞法語法分析，生成語法樹，并在此基礎(chǔ)上建立控制流圖，方便之后的獲取執(zhí)行路徑。使用Clang進(jìn)行詞法語法分析主要是由于Clang本身性能的優(yōu)異，其生成語法樹所消耗的內(nèi)存僅僅是GCC的20%左右，同時(shí)編譯時(shí)間快，錯(cuò)誤輸出明確，并且Clang支持在語法樹的基礎(chǔ)上建立控制流圖，自動(dòng)查找頭文件，解析C語言在Linux下的頭文件的功能。

在基于未來鎖集的死鎖規(guī)避算法[1]中程序插裝的是記錄鎖集信息的關(guān)鍵步驟[2]，這也是基于未來鎖集死鎖規(guī)避算法與其它死鎖規(guī)避算法[3-5]最大的不同，通常情況下程序插裝的目的是獲取程序的執(zhí)行路徑，或者關(guān)鍵的狀態(tài)值等。雖然基于未來鎖集的死鎖規(guī)避算法也需要獲取程序的執(zhí)行路徑，但卻通過靜態(tài)的分析方法獲得程序可能的執(zhí)行路徑，而不是等到程序運(yùn)行時(shí)獲取真實(shí)的執(zhí)行路徑。所以本算法插裝的目的是為了記錄下相關(guān)的加鎖操作的信息。只有獲得了這些信息，才能根據(jù)這些信息添加規(guī)避邏輯[6]。

1 路徑敏感分析

在基于未來鎖集的死鎖規(guī)避算法中程序的插裝內(nèi)容是根據(jù)程序的實(shí)際執(zhí)行路徑來確定的，然而在靜態(tài)分析時(shí)卻仍無法確定程序真實(shí)的執(zhí)行路徑，因此就需要找出程序所有的可能執(zhí)行路徑，并區(qū)分具體情況進(jìn)行插裝，這一過程就是路徑敏感分析。

下面使用塊號代表節(jié)點(diǎn)，將控制流圖這個(gè)有向圖轉(zhuǎn)化成矩陣的存儲(chǔ)形式Arcs[N][N]，N是所有節(jié)點(diǎn)的個(gè)數(shù)。在算法開始之前，需要首先引入一些變量定義：

（1）節(jié)點(diǎn)棧mystack。

（2）VertexStatus[]={0，0，0，1，1，…}當(dāng)結(jié)點(diǎn)未進(jìn)棧或者已經(jīng)出棧，則其對應(yīng)的狀態(tài)為0，否則為1。

（3）ArcStatus[][]={0，0，1，0，1…..} 當(dāng)且僅當(dāng)邊的兩個(gè)結(jié)點(diǎn)都在棧外時(shí)，邊的狀態(tài)才為0，否則為1。

對以上變量實(shí)現(xiàn)其定義后，算法1給出了路徑敏感分析算法的具體描述。

算法1：路徑敏感分析算法

輸入：控制流圖的矩陣存儲(chǔ)形式Arcs[N][N]

輸出：控制流圖中基本塊N到基本塊0的所有路徑集合Paths

1 Paths={}//路徑集合

2 VertexStatus[]={0}；//全部置0

3 ArcStatus[][]={0}；//全部置0

4 mystack.push（0）；// 節(jié)點(diǎn)棧

5 VertexStatus[N]=1；//將第N塊入棧

6 while ！mystack.empty（）

7 elem= mystack.top（）；//獲得棧頂元素

8 if elem==0

9 path=Traverse（mystack）；//遍歷棧將棧中信息組成路徑

10 Paths.add（path）；//將棧中的路徑添加到路徑集合Paths中

11 VertexStatus[elem]=0；

12 UpdateArcStatus（）；//更新ArcStatus[][]

13 mystack.pop（）；//移除棧頂元素

14 else

15 i=N

16 T1= VertexStatus[i]==0；//第i塊不在棧中

17 T2= ArcStatus[elem][i]==0；//邊（elem，i）不在棧中

18 T3= Arcs.contain（elem，i）；//控制流圖中存在（elem，i）邊

19 if 如果存在一個(gè)最大的數(shù)i使i在0～N，并且使

20 T1&&T2&&T3成立

21 VertexStatus[i]=1；//標(biāo)記i塊狀態(tài)為入棧

22 VrcStatus[elem][i]=1；//標(biāo)記（elem，i）邊為入棧狀態(tài)

23 mystack.push（i）；//將i點(diǎn)入棧

24 else

25 VertexStatus[elem]=0；//標(biāo)記elem塊狀態(tài)為入棧

26 mystack.pop（）；//將棧頂元素出棧

27 UpdateArcStatus（）；//更新ArcStatus[][]

28 endif

29 endif

30 endwhile

31 return Paths；

算法1中，變量的初始化表示將起始塊號N放入棧中，更新點(diǎn)的狀態(tài)集合，并且開始算法，整個(gè)算法是在一個(gè)大的循環(huán)中；并且只要棧不為空，程序則繼續(xù)循環(huán)。進(jìn)入循環(huán)體之后首先判斷棧頂元素是否為0，也就是最后一塊Exit：如果是的話說明棧中的所有塊是一條符合要求的完整路徑，接下來需記錄下這個(gè)路徑并且更新邊的狀態(tài)集合，最后將棧頂元素出棧；如果不是，說明棧內(nèi)的元素還不是一條符合要求的路徑，即需要繼續(xù)改變棧中元素。改變棧中元素就是判定從棧頂元素開始到Exit塊是否還有新的路徑產(chǎn)生，為此定義了一個(gè)判斷條件T1&&T2&&T3，同時(shí)結(jié)合點(diǎn)的狀態(tài)集合，邊的狀態(tài)集合和原始的有向圖，進(jìn)而判斷：如果在控制流圖中還存在點(diǎn)使T1&&T2&&T3條件滿足的話，這就說明從棧頂元素到最后有新的路徑，隨即將更新點(diǎn)狀態(tài)集合和邊狀態(tài)集合，并且將棧頂元素的后繼入棧；否則也就說明從棧頂元素到最后已經(jīng)沒有新的路徑，如此將更新點(diǎn)的狀態(tài)集合，將棧頂元素出棧，更新邊的狀態(tài)集合。同時(shí)在路徑敏感分析算法完整執(zhí)行后，Paths中保存的就是兩點(diǎn)之間的所有路徑。

2 面向不同結(jié)構(gòu)源程序的插裝方法

2.1 順序結(jié)構(gòu)插裝

程序插裝是靜態(tài)分析的最后一步，未來鎖集就是根據(jù)靜態(tài)分析時(shí)插裝的信息計(jì)算而得來的。插裝的方式對于程序的不同結(jié)構(gòu)有不同的方法。在這里插裝的內(nèi)容為加鎖解鎖信息。具體插入的語句為入棧語句，入棧元素包含鎖的名稱和該鎖是否執(zhí)行加鎖。例如“Push（ps，Mutex1，1，mutex）”，表示向棧ps中加入一個(gè)鎖的信息，這個(gè)信息指明為鎖Mutex1實(shí)施加鎖，其中最后一個(gè)mutex參數(shù)表示Mutex1是一個(gè)互斥鎖，主要是為了區(qū)別讀寫鎖而設(shè)立的。算法2給出順序結(jié)構(gòu)插裝的算法描述。

算法2：對源碼為順序結(jié)構(gòu)的程序插裝的算法

輸入：順序結(jié)構(gòu)的源碼對應(yīng)的控制流圖

輸出：插裝之后的源碼對應(yīng)的控制流圖

1 對輸入的源碼建立控制流圖G

2 for G中的每條語句s

3 if s為加鎖操作

4 while 以s為起點(diǎn)遍歷控制流圖中的每條語句t

5 if t不是對應(yīng)s的解鎖操作并且為加鎖解鎖語句

6 記錄加鎖語句t中的信息

7 endif

8 endwhile

9 endif

10 將所記錄的所有鎖信息插裝到s之前，更新G

11 if s為自定義函數(shù)調(diào)用

12 while 以語句s為起點(diǎn)遍歷G的每條語句t直到控制流圖結(jié)束

13 記錄下所有加鎖解鎖操作

14 endwhile

15 endif

16 將記錄的鎖信息插裝到s之前， 更新G

17 在s之后插裝相應(yīng)的出棧語句，更新G

18 endif

19 endfor

20 return G；

2.2 分支結(jié)構(gòu)的插裝

基于未來鎖集的死鎖規(guī)避算法中主要包含著一個(gè)“提前“的思想，當(dāng)算法執(zhí)行到加鎖操作時(shí)，如果能知道加鎖操作之后執(zhí)行的其他加鎖解鎖操作的話，就可以根據(jù)這些信息判斷所遇到的加鎖操作是不是可以執(zhí)行。本文研究的插裝就是將加鎖之后執(zhí)行的鎖信息提前。但是這里存在一個(gè)問題，在路徑分析時(shí)可能獲得的是兩點(diǎn)之間的所有路徑，而在實(shí)際執(zhí)行的過程中執(zhí)行路徑卻只有一條。也就是說，在程序運(yùn)行之前終將無法確定程序運(yùn)行時(shí)的真實(shí)執(zhí)行路徑。圖1所示為采用將分支條件提前的方法插裝帶有分支結(jié)構(gòu)的源碼。

圖1 采用將分支條件提前的方法插裝帶有分支結(jié)構(gòu)的源碼

Fig.1 Instrumentate source code with branch structure using the method that put the branch condition in front

圖1展示了兩個(gè)簡化后的控制流圖，其中省略了Entry和Exit塊。圖中箭頭右邊的控制流圖采用了將分支條件提前的方法，插裝帶有分支結(jié)構(gòu)的程序。源程序?yàn)橐粋€(gè)分支結(jié)構(gòu)，分支條件為T，需要插裝的語句為S1，S2，S3，且都是加鎖語句。具體地，S2，S3只有一條路徑可以執(zhí)行，其插裝代碼分別為In3、In4和In5，In6及In7。而對于S1來說，則有兩條路徑可以執(zhí)行；此時(shí)為了確定執(zhí)行路徑，即將分支條件提前，所以插裝的語句為條件語句In1和In2。

針對將分支條件提前這一方法，雖然可以精準(zhǔn)確定程序執(zhí)行的路徑，但是符合這種方法的條件卻過于苛刻。如果遇到分支條件不能提前的情況，這種方法將不能使用，比如用戶輸入，或者分支條件中的變量定義在加鎖操作之后等情況。如圖2所示，為使圖2中的B3塊發(fā)生變化，分支條件中的變量定義改動(dòng)在加鎖條件之后，只是如此插裝之后就會(huì)出現(xiàn)語法錯(cuò)誤。圖3則為分支條件中的變量需要用戶輸入導(dǎo)致不能將分支條件提前。

圖2分支條件中的變量定義在加鎖操作之后導(dǎo)致插裝錯(cuò)誤

Fig.2 The variable in the branch condition that define after the lock operation lead to the error of instrumentation

圖3 分支條件中的變量需要用戶輸入導(dǎo)致插裝錯(cuò)誤

Fig.3 The variable in the branch condition that require user input lead to the error of instrumentation

在圖3中，由于分支條件中的變量a，b是在加鎖操作S1之后定義的，當(dāng)插裝完成后，插裝語句中的變量a，b就成為未定義的變量，因而這段代碼將無法順利通過編譯。在圖4中真正確定分支條件的變量是需要用戶輸入，而用戶輸入的語句卻是在加鎖操作S1之后，這就使得雖然插裝后的代碼可以運(yùn)行，但卻不能有效確定執(zhí)行路徑。

在插裝時(shí)，為了有效確定程序的執(zhí)行路徑而采用將分支條件提前的方法雖然可以準(zhǔn)確找到執(zhí)行路徑，但其適用范圍并不大，而且也無法判斷程序的分支條件是否可以提前，綜上所述即使插裝代碼中產(chǎn)生了諸多錯(cuò)誤。在此，提出另一種方法將會(huì)遍歷所有可能的執(zhí)行路徑，按照算法3的插裝方法就可將所有應(yīng)該插裝的鎖信息入棧，并將重復(fù)的去掉。如下的算法3就是這種分支結(jié)構(gòu)插裝方法的算法描述。

算法3：對源碼為分支結(jié)構(gòu)的程序插裝的算法

輸入：分支結(jié)構(gòu)的源碼對應(yīng)的控制流圖

輸出：插裝之后的源碼對應(yīng)的控制流圖

1 對輸入的源碼建立控制流圖G

2 for G中的每條語句s

3 if s為加鎖操作or自定義函數(shù)調(diào)用操作

4 以s所在的基本塊為起點(diǎn)Exit塊為終點(diǎn)進(jìn)行路徑敏感分析

5 獲得路徑集合Paths

6 for 遍歷Paths中的每條路徑path

7 將path中的塊連接起來當(dāng)作順序結(jié)構(gòu)的源碼

8 使用算法2是對s進(jìn)行插裝，更新G

9 endfor

10 將s前插裝的語句做去重處理

11 endif

12 endfor

13 return G；

這種方法雖然損失掉一些程序執(zhí)行效率，但卻適用于所有情況，并且不會(huì)向源碼中引入錯(cuò)誤。圖4就列舉了一個(gè)分支結(jié)構(gòu)的源碼對應(yīng)的控制流圖，并且給出使用算法3插裝之后的控制流圖。

圖4 遍歷所有可能路徑的插裝方法

Fig.4 Instrumentation method of traversing all the possible paths

如圖4所示，對于S1的插裝是分別遍歷了左分支和右分支之后將所有插裝信息插入，再去掉重復(fù)的，所以在棧中會(huì)同時(shí)出現(xiàn)加鎖mutex2和加鎖mutex3。

2.3 循環(huán)結(jié)構(gòu)的插樁

前文已經(jīng)介紹了對于順序結(jié)構(gòu)和分支結(jié)構(gòu)的插裝方式，并且在路徑分析時(shí)將所有的循環(huán)結(jié)構(gòu)都轉(zhuǎn)化成了分支結(jié)構(gòu)，那么如果在循環(huán)體中出現(xiàn)了自定義函數(shù)調(diào)用或者加鎖操作的話，相應(yīng)地也可將循環(huán)結(jié)構(gòu)轉(zhuǎn)化成循環(huán)體只可能執(zhí)行一遍的分支結(jié)構(gòu)。

在實(shí)際的編程過程中，如果循環(huán)體中存在單獨(dú)的加鎖操作而沒有對應(yīng)的解鎖操作的話，一旦循環(huán)體重復(fù)執(zhí)行，就極有可能發(fā)生自鎖的情況。這樣的編程方式是不符合規(guī)范的。但是在循環(huán)體中只要加鎖操作和解鎖操作能夠呈現(xiàn)對應(yīng)設(shè)計(jì)，那么插裝之后，即使循環(huán)體重復(fù)執(zhí)行，插裝的內(nèi)容也會(huì)是一樣的，算法4給出循環(huán)結(jié)構(gòu)的插裝算法描述。

算法4：對源碼為循環(huán)結(jié)構(gòu)的程序插裝的算法

輸入：循環(huán)結(jié)構(gòu)的源碼對應(yīng)的控制流圖

輸出：插裝之后的源碼對應(yīng)的控制流圖

1 對輸入的源碼建立控制流圖G

2 for G中的每個(gè)基本塊b

3 if 基本塊b的后繼塊號大于本塊號，說明存在回邊

4 b塊的前驅(qū)塊為preb

5 b塊的后繼為succb

6 將preb的后繼塊設(shè)置為succb的除了preb的后繼塊

7 刪除基本塊b

8 endif

9 endfor

10 將G作為算法3的輸入進(jìn)行插裝

11 return G；

如圖5所示，控制流圖中帶有環(huán)的結(jié)構(gòu)G1，在去環(huán)之后轉(zhuǎn)化成為圖G2，使用插裝算法插裝之后則為圖G3。G1中的塊B3，B2和B0，構(gòu)成了一個(gè)環(huán)狀結(jié)構(gòu)，其中B2是一個(gè)空塊。在去環(huán)的過程中將B2刪除，形成G2所示的控制流圖，在G2插裝的過程中只要按照分支結(jié)構(gòu)插裝的算法進(jìn)行就可以了。最終的插裝結(jié)果即為G3所示的控制流圖。

圖5 對于循環(huán)結(jié)構(gòu)的插裝方法

Fig.5 Method of instrumentation of a circular structure

3 實(shí)驗(yàn)

Flider對于靜態(tài)插裝的測試分為順序結(jié)構(gòu)的源碼，分支結(jié)構(gòu)的源碼和循環(huán)結(jié)構(gòu)的源碼。下面以循環(huán)結(jié)構(gòu)為例，如圖6為循環(huán)結(jié)構(gòu)的一段源碼，圖7為該段代碼插裝之后的部分結(jié)果。

圖6 循環(huán)結(jié)構(gòu)的源代碼

Fig.6 Source code of a circular structure

圖7 由于對rwlock1鎖的加鎖操作而插裝的語句

Fig.7 The statement that is instrumentated because of the rwlock1 lock operation

在圖6中的源碼中存在兩個(gè)加鎖語句rwlock1與rwlock2，圖7所示的是對于rwlock1插裝的結(jié)果。插裝的語句為入棧語句，是根據(jù)加鎖操作后面執(zhí)行的代碼所確定的，按照算法4，圖7對于循環(huán)結(jié)構(gòu)的插裝是正確的。

4 結(jié)束語

本文使用Clang作為詞法語法分析工具，建立抽象語法樹，控制流圖并且在控制流圖的基礎(chǔ)上進(jìn)行路徑分析獲取源程序可能執(zhí)行的所有路徑。同時(shí)，根據(jù)獲得的路徑信息將語句插裝進(jìn)源碼。這項(xiàng)工作為基于未來鎖集的死鎖規(guī)避方法提供了鎖集信息，可以用于基于未來鎖集的死鎖規(guī)避方法的靜態(tài)分析部分。

參考文獻(xiàn)：

[1] GERAKIOS P， PAPASPYROU N， SAGONAS K， et al. Dynamic deadlock avoidance in systems code using statically inferred effects[C]//Proceedings of the 6th Workshop on Programming Languages and Operating Systems， New York， NY， USA：ACM， 2011： 5

[2] 白哥樂. 基于靜態(tài)源碼分析的多線程死鎖檢測方法研究 [D]. 北京：北京郵電大學(xué)，2010.

[3] BERGER E D， YANG T， LIUiu T， et al. Grace： safe multithreaded programming for C/C++[J]. ACM Sigplan Notices， 2009， 44（10）： 81-96.

[4] RABIN M O， SCOTT D. Finite automata and their decision problems[J]. IBM journal of research and development， 1959， 3（2）： 114-125.

BERGER E， YANG T， LUYiu T， et al. Grace： Safe and efficient concurrent programming[C]//Object-Oriented Programming， Systems， Languages & Applications， Orlando， Florida：ACM，2009：123-137.

[5] JULA H， CANDEA G. A scalable， sound， eventually-complete algorithm for deadlock immunity[C]//Runtime Verification. Berlin Heidelberg：Springer， 2008： 119-136.

[6] 蘇小紅，禹 振，王甜甜，等. 并發(fā)缺陷暴露、檢測與規(guī)避研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào)，2014，37（103）：1-19