一種基于逆向程序流的程序切片算法

(南京大學(xué) 計算機(jī)系 計算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室， 南京 210093)



摘 要：傳統(tǒng)的程序切片方法一般基于程序依賴圖(PDG)和系統(tǒng)依賴圖(SDG)的可達(dá)性算法，但是在建立PDG和SDG的過程中會計算一些與切片無關(guān)的數(shù)據(jù)依賴，造成時空資源的浪費(fèi)及切片效率的降低。提出了一種基于程序逆向流的切片算法，它事先建立逆向程序流，再從切片點(diǎn)開始沿逆向程序流掃描程序以獲得程序切片，只計算與切片相關(guān)的數(shù)據(jù)依賴，從而提高了切片計算的時空效率。通過實(shí)驗(yàn)發(fā)現(xiàn)該算法具有一定的可行性和實(shí)用性。本算法適用于包括Fortran、C等編程語言在內(nèi)的命令式程序的切片生成。

關(guān)鍵詞：程序切片； 程序逆向流； 謂詞依賴集； 過程內(nèi)切片； 過程間切片

中圖分類號：TP311.5 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2009)03092003



Algorithm of program slicing based on reverse program flow



BAI Wenke， YANG Xianchun， XU Manwu



(State Key Laboratory for Novel Software Technology， Dept. of Computer Science， Nanjing University， Nanjing 210093， China)



Abstract:The traditional method of program slicing was based on reachability algorithm of program dependence graph(PDG) and system dependence graph(SDG). However， to construct PDG and SDG， some data dependenced which were irrelevant to the slicing may be computed. The redundant computing wasted time and memory， and reduced slicing efficiency. To address this problem， this paper presented a slicing algorithm based on reverse program flow. It firstly constructed reverse flow of the program， then scaned the program along reverse flow from the slicing point， and only computed the data dependences which were relevant to slicing. So it improved slicing efficiency. The result of experiment shows this algorithm is feasible and practical. This algorithm can be used for generating slicing of imperative programs， such as Fortran and C program.

Key words：program slicing; reverse program flow; predicate dependence set (PDS); intraprocedural slicing; interprocedural slicing



0 引言

程序切片是一種重要的程序分析理解方法，它廣泛應(yīng)用于程序調(diào)試、測試、軟件維護(hù)、軟件度量、逆向工程和再工程等領(lǐng)域。其概念最早由Mark Weiser[1]提出，定義為：對程序P、程序點(diǎn)l和變量x，其切片是指可能影響變量x在l點(diǎn)狀態(tài)的所有語句和謂詞的集合，記做slice(l， x)。其中〈l，x〉為一個切片標(biāo)準(zhǔn)。程序切片可以縮小考察的程序范圍，有利于程序員對錯誤的查找和定位。K.J.Ottenstein等人[2]提出了通過遍歷程序依賴圖(PDG)來獲得過程內(nèi)切片的方法。后來Horwitz等人[3]通過把PDG擴(kuò)展為系統(tǒng)依賴圖(SDG)以得到過程間切片。由于順序程序中依賴關(guān)系具有傳遞性，基于程序依賴圖的函數(shù)內(nèi)切片算法是一個簡單的圖的可達(dá)性問題。在系統(tǒng)依賴圖上，函數(shù)間的切片問題也是一個圖的可達(dá)性問題[3，4]。

通過程序依賴圖和系統(tǒng)依賴圖來獲得切片，需要先計算程序的控制依賴和數(shù)據(jù)依賴。但在生成程序依賴圖和系統(tǒng)依賴圖的過程中，可能會分析執(zhí)行流不經(jīng)過切片點(diǎn)的代碼，或者計算執(zhí)行流經(jīng)過切片點(diǎn)的代碼中與切片無關(guān)的數(shù)據(jù)依賴。這些不必要的計算造成了時間和空間資源的浪費(fèi)，并嚴(yán)重影響了切片計算的效率。事實(shí)上，程序的數(shù)據(jù)依賴受控制依賴制約，因?yàn)槿艚粨Q一段程序語句的執(zhí)行順序，則不同的交換方法將導(dǎo)致不同的數(shù)據(jù)依賴關(guān)系。所以對于計算程序切片來說，可以事先生成整個程序的逆向控制流，再從切片點(diǎn)開始沿逆向控制流掃描程序，僅計算與切片相關(guān)的數(shù)據(jù)依賴，在此過程中用控制依賴和剛生成的數(shù)據(jù)依賴來計算切片，這樣就提高了切片算法的效率。本文提出了一種基于此原理的命令式程序的切片方法，并依次給出了過程內(nèi)和過程間的切片算法，它們消除了傳統(tǒng)PDG、SDG切片算法中無關(guān)的數(shù)據(jù)依賴計算，提高了算法的性能。

1 基于逆向程序流的切片算法原理

本章先給出命令式程序的語法，然后描述了基于逆向程序流的切片算法原理。本章只討論了過程內(nèi)切片，過程間切片在第3章討論。

1.1 命令式程序的語法

下面是所要分析的命令式程序過程內(nèi)語句的語法，用BNF表示如下：

a ::=x｜n｜a1 opa a2

b ::=true｜1｜not b｜b1 op b b2｜a1 opr a2

S ::=[x=a]l｜S1; S2｜if ([b]l){S1}else{S2}｜while ([b]l) {S}

其中：a為算術(shù)表達(dá)式，x為變量，n為數(shù)字常量；b為邏輯表達(dá)式，opa、opb和opr分別表示算術(shù)運(yùn)算符、邏輯運(yùn)算符和算術(shù)比較符；S為程序語句。標(biāo)在語句右上方的l為一個自然數(shù)，它是該語句的編號(label)，用于標(biāo)志對應(yīng)的程序語句。每條語句的編號在程序中是惟一的。

1.2 切片算法原理

命令式程序的一個顯著特點(diǎn)是它有賦值語句。賦值語句是命令式程序中惟一改變內(nèi)存變量值的語句，由于切片是指所有可能影響所考察變量在切片點(diǎn)取值的語句和謂詞，賦值語句是本切片算法關(guān)注的主要對象。本文將程序語句的操作分為賦值操作和非賦值操作：賦值操作改變程序的狀態(tài)；非賦值操作控制程序的執(zhí)行流或者進(jìn)行計算。因?yàn)橛绊懬衅c(diǎn)變量值的直接操作是賦值操作，所以當(dāng)賦值語句的左式為欲求其切片的變量時，切片中應(yīng)加入該賦值語句；若同時存在某謂詞決定該賦值操作是否執(zhí)行，則切片中還要加入該謂詞；如果該賦值語句的右式或剛加入的謂詞中含有變量，則再計算這些變量的切片，最后把這些切片并入目標(biāo)切片中，由此就可得到目標(biāo)切片。

令切片點(diǎn)的語句編號為l，變量x在該點(diǎn)的切片記做S，S初始時為空集。為標(biāo)記要計算哪些切片，增加一個數(shù)據(jù)結(jié)構(gòu)：待處理表U，它用于記錄當(dāng)前應(yīng)該計算哪些變量的切片，其初始值為{(l， x)}。計算S時，沿逆向程序流掃描分析程序，不斷加入可能影響x在l處值的語句或謂詞，直至集合S不再擴(kuò)大為止，如圖1所示。

圖1中的箭頭表示沿逆向程序流掃描程序，S″為l點(diǎn)之后的切片，S′為l點(diǎn)之前的切片。逆向掃描時，若遇到非賦值語句，則直接把掃描點(diǎn)前移一步。若遇到賦值語句，由于它是程序中惟一改變變量值的操作，有可能處于切片中，需分情況處理：a）當(dāng)賦值語句的左式為S中某個欲求其切片的變量時，就在S中加入該語句的編號，并刪除其在待處理表U中的待處理標(biāo)記(l″， x)，同時在U中加入賦值語句的右式中變量的切片待求標(biāo)記{(l′，v)｜v是a中的變量}；b）否則，S、U不變，掃描點(diǎn)沿逆向程序流移動一步。

上述切片計算過程是逆向程序流進(jìn)行的，為此必須事先生成整個程序的執(zhí)行流flow，再獲得程序逆向流flowR。flow為(l， l′)的集合，(l， l′)表示執(zhí)行完l處的語句后將可能執(zhí)行l(wèi)′處的語句。flowR={(l′，l)｜(l，l′)∈flow}。flow和flowR的詳細(xì)說明見文獻(xiàn)[4]的第2章，這里不再贅述。

現(xiàn)在還有一個問題要解決：如何處理分支語句和循環(huán)語句。這些語句中的謂詞決定了某些賦值語句是否被執(zhí)行，所以它們也可能是影響變量取值的語句，需納入對它們的處理，但同時又要不影響沿逆向程序流求切片的基本思想。為此本文建立了謂詞依賴集（PDS），其定義為PDS={〈l， lb〉｜存在決定l處語句是否執(zhí)行的謂詞，謂詞編號為lb}。有了PDS后就可以處理分支語句和循環(huán)語句了：當(dāng)某條語句被加入到切片集合中，且PDS中存在該語句編號l對應(yīng)的〈l，lb〉，則應(yīng)在切片集合中加入lb，并分析lb對應(yīng)的謂詞：若謂詞中含有變量，則應(yīng)該以lb為切片點(diǎn)計算這些變量的切片，最后再并入目標(biāo)切片集合中。

1.3 最小解原則

最小解原則是用來處理循環(huán)語句和遞歸程序的切片求解。它是指在切片計算過程中，不斷擴(kuò)大的語句和謂詞的集合應(yīng)該是最小的，即不能出現(xiàn)這種情況：沿flowR循環(huán)無休止地計算某個變量的切片。舉例如下：

程序：[i=-3]1; while([i＜0]2 ) {[i=i+1]3;}

求slice(2，i)

解: flow={(1，2)， (2，3)， (3，2)}， flowR={(2，1)， (3，2)， (2，3)}， PDS={〈3， 2〉}

依照前面給出的切片計算方法，slice(2，i)的計算過程為

slice(2，i)=slice(1，i)∪slice(3，i)={1}∪({3}∪slice(2，i))={1，3}∪slice(2，i)

筆者發(fā)現(xiàn)計算結(jié)果中又包含了slice(2，i)的計算，產(chǎn)生了遞歸。遇到這種情況時，正確的做法應(yīng)該是中止slice(2，i)的計算，這樣slice(2，i)的最終計算結(jié)果為{1，3}。

2 過程內(nèi)程序切片的生成算法

根據(jù)1.2節(jié)的算法原理，計算切片前只需生成flow和PDS這兩個集合就可以了。無論是flow還是PDS，它們實(shí)際上都是一種控制流。下面給出了過程內(nèi)程序切片的生成算法：

輸入: 程序P， 切片點(diǎn)l， 變量x

輸出: 切片S， S為語句和謂詞的編號集合

變量說明: U為待處理表， 用于記錄算法當(dāng)前應(yīng)該計算哪些變量的切片; V為已處理表， 用于保存哪些切片已經(jīng)被處理過，以便在下次又遇到該切片計算時中止它，從而遵循前述的最小解原則。

begin slice

1 語法分析程序P， 給語句和謂詞標(biāo)定編號， 生成程序執(zhí)行流flow和謂詞依賴集PDS;

2 由flow生成flowR;

3 進(jìn)行初始化工作: S=，U={(l，x)}，V=;

4 while U≠

5for U中每個(l， x) do

6 U=U \\{(l， x)}; V=V ∪{(l， x)};

7 if l處是給x賦值的語句

8S=S∪{l};

9if存在(l′， l)∈flowRthen

10for a中的每個變量v

11 if ( l′， v)V then U=U∪{( l′， v)};

12 end if

13end for

14 end if

15else if 存在(l′， l)∈flowR且(l′， x)V then

16U=U∪{( l′， x)};

17end if

18if l被加入S， 且在PDS中有〈l， lb〉， 且lbS then

19S=S∪{lb};

20if 存在(l′， l)∈flowRthen

21 for [b]lb中的每個變量v do

22 if (l′， v)V then U=U∪{( l′， v)};

23 end if

24end for

25 end if

26end if

27end for

28 end while

end slice

算法說明：步驟1、2完成了程序的語法分析并生成了程序控制流flow、flowR和謂詞依賴集PDS；步驟3完成了各分析表的初始化；步驟4~28進(jìn)行過程內(nèi)切片的生成，直至待處理表U為空，其中步驟7~14處理賦值語句，步驟15~17對于非賦值語句或者不給變量x賦值的賦值語句，掃描點(diǎn)上移；步驟18~26，若l被加入S， 且存在謂詞lb決定l的執(zhí)行與否， 則將lb加入到S中， 此時若[b]lb中還有變量， 則要標(biāo)記還需要計算這些變量的切片，即在U中加入這些變量的待處理標(biāo)記{(l′，v)}。

算法的優(yōu)點(diǎn): 只用生成兩個控制流，即程序逆向流flowR和謂詞依賴集PDS，就可以進(jìn)行切片分析：從切片點(diǎn)開始沿flowR掃描程序，不斷在切片集合中加入影響變量x在切片點(diǎn)取值的語句，直到切片集合不能再擴(kuò)大為止。該算法消除了傳統(tǒng)PDG、SDG切片算法中不相關(guān)數(shù)據(jù)依賴的計算， 提高了切片的效率。

3 過程間切片方法

對于含有函數(shù)定義和函數(shù)調(diào)用的單線程程序，其執(zhí)行流仍然是順序的，所以切片的計算仍可以沿逆向程序流來進(jìn)行。切片算法的框架與過程內(nèi)切片算法框架一樣，只是增加了對函數(shù)調(diào)用、函數(shù)返回等控制流的處理。下面先給出包含函數(shù)定義和函數(shù)調(diào)用的程序語法，用BNF表示如下：

function declare ::= p(形參列表){ln S }lx

a::= … ｜ [call p(實(shí)參列表)]lclr

S::= … ｜[call p(實(shí)參列表)]lclr｜[return語句]lx

其中：“…”表示省略第2章已經(jīng)給出的過程內(nèi)的語法部分；ln、lx分別表示函數(shù)的進(jìn)入點(diǎn)和退出點(diǎn)；lc、lr分別表示函數(shù)調(diào)用點(diǎn)和返回點(diǎn)。若函數(shù)定義中 “}”的前面有“return語句”，則不在“}”的右上角標(biāo)記lx，否則要標(biāo)記。所有“return語句”的右上角都要標(biāo)記lx。一個函數(shù)內(nèi)的所有l(wèi)x的值均不相同。

flow需要在原來的基礎(chǔ)上再加入(lc;ln)和(lx;lr)，它們分別表示函數(shù)調(diào)用和函數(shù)返回，中間的“;”用來區(qū)別于過程內(nèi)的(l′， l)。

計算切片時，所要新加的處理是函數(shù)調(diào)用語句：若函數(shù)調(diào)用處為賦值語句，且賦值語句左式為待求其切片的變量，則應(yīng)該在過程內(nèi)程序切片生成算法處理后，再在S中并入所調(diào)用函數(shù)的集合{lx}，并根據(jù)lx處返回值的形式作不同處理：a)若返回值為常數(shù)，則不作處理；b)若返回值為變量v，則U=U∪{(l′，v)｜存在(l′，l)∈flowR且(l′，v)V}，其中(l′，v)V的作用是禁止重復(fù)計算切片。

若函數(shù)調(diào)用處未使用函數(shù)返回值，則仍按照過程內(nèi)程序切片生成算法處理，即掃描點(diǎn)上移。所要注意的是：

a）待處理表U只有一個，所以要分清局部變量和全局變量。當(dāng)逆向分析到了某變量的定義處，若待處理表U中仍有該變量的切片值未計算，則應(yīng)刪除它，以防止該變量的切片分析越出它的作用范圍。這種情況也說明該變量未被初始化。

b）增加一個數(shù)據(jù)結(jié)構(gòu)C來記錄函數(shù)調(diào)用情況。C初始時為空。當(dāng)分析到某函數(shù)調(diào)用時，應(yīng)該把(lc，ln)放入C中。而當(dāng)逆向掃描到函數(shù)入口ln時，若C中存在對應(yīng)的(lc，ln)，則應(yīng)該將待處理表U中的(ln，v)轉(zhuǎn)換為(lc， v)，并刪除C中的(lc，ln)；若C中不存在對應(yīng)的(lc，ln)，則應(yīng)根據(jù)flowR中所有的(ln;l′c)，把(ln， v)轉(zhuǎn)換為(l′c， v)。其中v為全局變量或者形式參數(shù)，若v為形式參數(shù)時，則要把v轉(zhuǎn)換為實(shí)參變量。

4 實(shí)例

為說明該切片算法的計算過程，下面給出一個過程間切片的例子：

int count;

void m(){1

[count=0]2;

int [x=2]3， [v=100/x]4

int [y=[f(v)]56]7;

}8

int f(int n){9

int [s=0]10;

while([n>0]11){

[s=s+n]12;

[n=n-1]13;

}

[count=count+1]14;

[return s]15;

}

計算slice(7， y)

解：依照文獻(xiàn)[4]第2章中給出的flow的定義，首先生成程序流flow，如下：

flow={(1，2)，(2，3)，(3，4)，(4，5)，(5;9)，(6，7)，(7，8)，(9，10)，(10，11)，(11，12)，(11，14)，(12，13)，(13，11)，(14，15)，(15;6)}

得程序逆向流：

flowR={(2，1)，(3，2)，(4，3)，(5，4)，(9;5)，(7，6)，(8，7)，(10，9)，(11，10)，(12，11)，(14，11)，(13，12)，(11，13)，(15，14)，(6;15)}

謂詞依賴集PDS={(12，11)，(13，11)}。

切片的計算過程如表1所示。

表1 程序切片計算的實(shí)例

step待處理表U函數(shù)調(diào)用表C切片S

初始{(7， y)} 

1{(14， s)}{(5， 9)} {7，15}

2{(11， s)}{(5， 9)} {7，15}

3{(10， s)，(13， s)}{(5， 9)} {7，15}

4{(12， s)}{(5， 9)} {7，15，10}

5{(11， n)}{(5， 9)} {7，15，10，12，11}

6{(10， n)，(13， n)}{(5， 9)} {7，15，10，12，11}

7{(9， n)，(12， n)}{(5， 9)} {7，15，10，12，11，13}

8{(5， v)}{7，15，10，12，11，13}

9{(4， v)}{7，15，10，12，11，13}

10{(3， x)}{7，15，10，12，11，13，4}

11{7，15，10，12，11，13，4，3}

表的第1列表示計算時的執(zhí)行順序。整個計算過程不斷循環(huán)處理待處理表U，直至U為空。表的第1~11行每一行表示對前一行中U處理后得到的分析結(jié)果。已處理表V在表1中未列出，它初始時為，以后每一行的V為前一行V和U的并集，當(dāng)求解過程中遇到待求的切片已經(jīng)在V中時，就中止該切片的計算。第11行為計算結(jié)果：切片slice(7， y)=S={7，15，10，12，11，13，4，3}，S中元素的順序?yàn)槠浔患尤氲捻樞颉?/p>