一種新的過程間靜態(tài)切片快速算法

蘇小紅，龔丹丹，王甜甜，馬培軍

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱)

程序切片技術(shù)是一種重要的程序分析和理解技術(shù)，廣泛應(yīng)用于程序調(diào)試、測(cè)試及軟件維護(hù)中［1-2］.其原理和方法最早出現(xiàn)在文獻(xiàn)［3］中，文獻(xiàn)［3］根據(jù)數(shù)據(jù)流方程的迭代解對(duì)程序切片進(jìn)行了定義，并提出了基于控制流圖(control flow graph，CFG)的計(jì)算過程內(nèi)程序切片的算法，但此方法所消耗的時(shí)間和空間均比較多，計(jì)算所得的程序切片準(zhǔn)確性也不是很好.文獻(xiàn)［4］引入了基于程序依賴圖(program dependence graph，PDG)的圖形可達(dá)性算法，用于計(jì)算過程內(nèi)切片，但此算法只能計(jì)算一個(gè)過程內(nèi)的切片問題，含有多個(gè)過程的程序切片計(jì)算問題并未得到解決.文獻(xiàn)［5］通過把PDG擴(kuò)展為系統(tǒng)依賴圖(system dependence graph，SDG)，以計(jì)算過程間切片，根據(jù)系統(tǒng)依賴圖，將函數(shù)間的切片問題轉(zhuǎn)化為圖的可達(dá)性問題［6］，從而解決了包含多個(gè)過程程序的切片計(jì)算問題.

目前，計(jì)算程序靜態(tài)切片主要使用的方法是基于依賴圖的遍歷算法［7］.系統(tǒng)依賴圖能夠充分表示程序的數(shù)據(jù)依賴、控制依賴信息以及函數(shù)調(diào)用信息，但是SDG數(shù)據(jù)流分析的復(fù)雜度較高，而且生成系統(tǒng)依賴圖的過程中，需要計(jì)算與切片無關(guān)的數(shù)據(jù)依賴，這些不必要的計(jì)算造成了時(shí)間和空間資源的浪費(fèi)，并嚴(yán)重影響了切片計(jì)算的效率.類似地，傳統(tǒng)的動(dòng)態(tài)切片算法使用動(dòng)態(tài)依賴圖，復(fù)雜性也很高，針對(duì)該方法，文獻(xiàn)［8］提出利用D/U表達(dá)式計(jì)算動(dòng)態(tài)切片的方法，不需要使用動(dòng)態(tài)依賴圖，可以同時(shí)計(jì)算程序的控制依賴和數(shù)據(jù)依賴，空間開銷較小.但傳統(tǒng)的利用D/U表達(dá)式計(jì)算動(dòng)態(tài)切片的方法，只考慮了直接控制依賴關(guān)系沒有考慮多層嵌套的情況，而且由于未考慮函數(shù)調(diào)用的情況，只能用于過程內(nèi)動(dòng)態(tài)切片的計(jì)算中.

本文提出的基于idUCf五元結(jié)構(gòu)的過程間切片算法，既保留了程序的數(shù)據(jù)依賴、控制依賴以及函數(shù)調(diào)用信息，又充分考慮了多層嵌套情況，而且不需要使用SDG，無需計(jì)算與切片無關(guān)的數(shù)據(jù)依賴、控制依賴以及不相關(guān)函數(shù)調(diào)用信息.

1 idUCf五元結(jié)構(gòu)及相關(guān)定義

本文在分析靜態(tài)切片與切片準(zhǔn)則的基礎(chǔ)上，給出了復(fù)合語句控制結(jié)構(gòu)信息表以及idUCf五元結(jié)構(gòu)的定義，作為本文切片算法的研究基礎(chǔ).

定義1(靜態(tài)切片［9］) 一個(gè)程序P的靜態(tài)切片是由P中的一些語句集合，它包含了所有可能影響興趣變量的語句，考慮了程序中所有可能的執(zhí)行路徑.根據(jù)切片方向的不同，可分為前向切片和后向切片.前向切片是指所有受興趣點(diǎn)變量的值影響的語句的集合;后向切片是指程序中所有能夠影響興趣點(diǎn)變量的值的語句的集合.本文所描述的是后向切片.

定義2(靜態(tài)切片準(zhǔn)則［10］) 靜態(tài)切片準(zhǔn)則是一個(gè)二元組C=(n，V)，其中:V為程序P中變量集合的一個(gè)子集;n為程序P中的某個(gè)興趣點(diǎn)(對(duì)應(yīng)于P中的一條語句).

定義3(復(fù)合語句控制結(jié)構(gòu)信息表(CNT))復(fù)合語句控制結(jié)構(gòu)信息表是記錄程序P中的所有復(fù)合語句(選擇、循環(huán))的開始、結(jié)束位置等關(guān)鍵信息的集合，它能夠精簡(jiǎn)的記錄程序的所有控制依賴關(guān)系，以下簡(jiǎn)稱 CNT(compound node table).其結(jié)構(gòu)定義如圖1所示.

圖1中，key為詞法分析時(shí)所對(duì)應(yīng)的TOKEN，name為該TOKEN對(duì)應(yīng)的源程序中的單詞.在本文所使用的編譯器中，經(jīng)詞法分析后將for語句對(duì)應(yīng)的TOKEN記為“CN-FOR”，則key的值為“CNFOR”，name記錄了源程序中的單詞，則name的值為“for”.對(duì)于多分支的選擇結(jié)構(gòu)，不僅應(yīng)該記錄選擇結(jié)構(gòu)的結(jié)束位置(endID)和結(jié)束行(endline)，還應(yīng)該記錄各個(gè)分支內(nèi)部的結(jié)束位置(ifendID)和結(jié)束行(ifendline)，以便進(jìn)行精確的路徑分析.例如圖2，多分支選擇結(jié)構(gòu)if(第13行)，其內(nèi)部分支結(jié)束位置ifendline=16，總分支結(jié)束位置endline=20;對(duì)于33行的else分支，其內(nèi)部分支結(jié)束位置即為總分支的結(jié)束位置，即endline=ifendline=20.循環(huán)結(jié)構(gòu)無需考慮多分支情況，因此for的endline與ifendline的值相同.詞法分析過程中記錄了每個(gè)TOKEN的具體位置，由于圖2為實(shí)例代碼片段，所包含的信息不完整，因此很難表示復(fù)合語句開始TOKEN位置、結(jié)束TOKEN位置以及內(nèi)部結(jié)束TOKEN位置.因此，并未記錄圖2中的beginID、endID以及ifendID，在圖中用“—”表示.

圖1 復(fù)合語句控制結(jié)構(gòu)信息表結(jié)構(gòu)

圖2 復(fù)合語句控制結(jié)構(gòu)信息表實(shí)例

定義4(idUCf五元結(jié)構(gòu))idUCf五元結(jié)構(gòu)＜i，d，U，C，f＞是表示程序中變量定義、使用、控制依賴關(guān)系、函數(shù)調(diào)用關(guān)系的表達(dá)式，其中:i為語句的行號(hào)，d為語句i定義的變量;U為語句i使用變量的集合，C為語句i復(fù)合關(guān)系集合，存儲(chǔ)該語句所在的復(fù)合語句所對(duì)應(yīng)的CNT的id號(hào)，f為語句i調(diào)用函數(shù)信息.這樣的表達(dá)式稱為idUCf五元結(jié)構(gòu).本文主要討論賦值語句結(jié)點(diǎn)(AssignNode)與函數(shù)調(diào)用結(jié)點(diǎn)(FunctionNode)的idUCf五元結(jié)構(gòu)，圖3中列出了圖2(D:aa.c)中第15行AssignNode和第19行FunctionNode的idUCf五元結(jié)構(gòu)，其中?表示空集.

圖3 idUCf五元結(jié)構(gòu)實(shí)例

2 idUCf五元結(jié)構(gòu)的靜態(tài)切片模型

本文建立了idUCf五元結(jié)構(gòu)的過程間靜態(tài)切片模型(如圖4所示)，主要包括以下3個(gè)步驟:

1)通過詞法分析生成 TOKEN序列，在TOKEN序列基礎(chǔ)上進(jìn)行代碼標(biāo)準(zhǔn)化［11］，最終生成標(biāo)準(zhǔn)化TOKEN序列.

2)在標(biāo)準(zhǔn)化TOKEN序列基礎(chǔ)上，分別生成函數(shù)列表、復(fù)合語句控制結(jié)構(gòu)信息表 CNT和idUCF五元結(jié)構(gòu).

3)應(yīng)用基于idUCf五元結(jié)構(gòu)的過程間靜態(tài)切片算法，得到過程間靜態(tài)切片.

圖4 程序切片算法模型

3 切片算法

過程間靜態(tài)切片，以切片準(zhǔn)則C=(n，V)，根據(jù)程序的idUCf五元結(jié)構(gòu)＜i，d，U，C，f＞，從源程序P中抽取結(jié)點(diǎn)n前，影響或間接影響變量v(v∈V)的所有語句和函數(shù).賦值語句以及函數(shù)調(diào)用語句直接影響變量的取值，本文將程序語句的操作分為賦值操作與函數(shù)調(diào)用操作，分別對(duì)應(yīng)idUCf五元結(jié)構(gòu)中的 AssignNode與 FunctionNode.當(dāng)計(jì)算任意變量v的后向切片時(shí)，應(yīng)逆序查找idUCf五元結(jié)構(gòu)，直到找到AssignNode或FunctionNode，使其滿足v=AssignNode或FunctionNode的定義變量d.因此，計(jì)算變量v的后向切片轉(zhuǎn)化為計(jì)算相對(duì)應(yīng)的賦值語句切片AssignSlice(d)或函數(shù)調(diào)用語句切片 FunctionSlice(d)，其中d為AssignNode或FunctionNode的定義變量為

式中“‖”表示“或者”.

1)當(dāng)d為AssignNode的定義變量時(shí)，切片中應(yīng)加入該賦值語句，并檢查其復(fù)合關(guān)系集合＜C＞及使用變量集合 ＜U＞，首先，依次計(jì)算復(fù)合關(guān)系子切片(ControlSlice(c))，以保證多層嵌套程序的完整性.當(dāng)使用變量集合 ＜U＞不為?時(shí)，代表定義的變量d無法直接獲得初始值，需要通過其使用的變量進(jìn)行計(jì)算.應(yīng)依次遞歸計(jì)算其使用變量的子切片slice(u)(u∈U).賦值語句結(jié)點(diǎn)切片AssignSlice(d)可確定為

式中“+”為所求切片的和.例如式中計(jì)算節(jié)點(diǎn)AssignSlice(d)由3部分的和組成，分別為該賦值節(jié)點(diǎn)AssignNode(d)，使用變量的子切片Slice(u)(u∈U)以及復(fù)合關(guān)系子切片(ControlSlice(c)).

當(dāng)使用變量集合 ＜U＞為?時(shí)，代表定義變量被賦予常數(shù)，即找到了變量的初始值，此時(shí)，上式可變?yōu)?/p>

當(dāng)計(jì)算復(fù)合關(guān)系子切片ControlSlice(c)時(shí)，根據(jù)idUCf五元結(jié)構(gòu)中的c(c∈C;c為該復(fù)合語句所對(duì)應(yīng)的CNT的id號(hào))查找CNT，找到所對(duì)應(yīng)的復(fù)合語句的具體信息.

①如果該復(fù)合語句為選擇結(jié)構(gòu)，則依次計(jì)算該選擇結(jié)構(gòu)的判斷變量j的后向切片，以計(jì)算判斷變量的初始值，即

②如果該復(fù)合語句為選擇結(jié)構(gòu)，為了計(jì)算判斷變量以及循環(huán)累加變量的初始值，首先應(yīng)依次計(jì)算判斷變量j和累加變量a的后向切片Slice(j)和Slice(a)，為了保證靜態(tài)切片的完整性，還應(yīng)考慮j和a的值在循環(huán)體內(nèi)是否改變，基于上述觀點(diǎn)，在循環(huán)體內(nèi)(beginline-endline)，順序查找idUCf五元結(jié)構(gòu)，當(dāng)j或a與 AssignNode或FunctionNode的定義變量d相同時(shí)，說明在循環(huán)體內(nèi)，j或a發(fā)生了改變，則應(yīng)計(jì)算AssignNode或FunctionNode的定義變量d的后向切片.則有

2)當(dāng)d為FunctionNode的定義變量時(shí)，說明此語句調(diào)用了函數(shù)，且d被賦予所調(diào)用函數(shù)的return返回值.切片中不僅應(yīng)加入該賦值語句、復(fù)合關(guān)系子切片(ControlSlice)，而且要在其調(diào)用函數(shù)中求得返回值切片(Slice(r))，即

式中:r為所調(diào)用函數(shù)的return返回值;m為被調(diào)函數(shù)的形參個(gè)數(shù).在計(jì)算Slice(r)的過程中，還應(yīng)記錄每個(gè)形參的使用標(biāo)志para-flag.如果調(diào)用函數(shù)的第i個(gè)形參(para-i)為欲求Slice(r)的切片變量，并且AssignNode(para-i)的使用變量始終不為?，則para-flag-i的值為1，否則為0.當(dāng)para-flag-i的值為1時(shí)，說明被調(diào)函數(shù)中使用了主調(diào)函數(shù)的形參值，因此，應(yīng)計(jì)算形參(para-i)所對(duì)應(yīng)的實(shí)參切片Slice(argue-i).

當(dāng)所求切片變量d∈FunctionNode的使用集＜U＞，說明d為調(diào)用函數(shù)的參數(shù)之一.

①當(dāng)調(diào)用參數(shù)傳遞類型為傳值調(diào)用時(shí)，被調(diào)函數(shù)中對(duì)形參的改變不影響實(shí)參的值，所以無需計(jì)算實(shí)參(para)所對(duì)應(yīng)的形參切片Slice(argue)，則有

②當(dāng)所求切片變量d∈FunctionNode的使用集＜U＞，并且調(diào)用參數(shù)傳遞類型為傳地址調(diào)用時(shí)，對(duì)形參的改變實(shí)際上是對(duì)實(shí)參的改變，因此，不僅要在調(diào)用函數(shù)中求得d所對(duì)應(yīng)的形參切片Slice(para-d)，同時(shí)還應(yīng)記錄形參的使用標(biāo)志para-flag，當(dāng)?shù)趇個(gè)形參的使用標(biāo)志para-flag-i的取值為1時(shí)，說明被調(diào)函數(shù)的切片計(jì)算中需要使用第i個(gè)形參所對(duì)應(yīng)的主調(diào)函數(shù)實(shí)參的取值，因此，應(yīng)計(jì)算第i個(gè)實(shí)參的切片Slice(argue-i).

本文在定義了上述公式的基礎(chǔ)上，給出了基于idUCf五元結(jié)構(gòu)的過程間靜態(tài)切片算法，構(gòu)造標(biāo)準(zhǔn)C=(n，V)的程序切片Slice(V)算法如圖5所示.主算法Slice(V)，根據(jù)切片準(zhǔn)則C=(n，V)，對(duì)第n行的每個(gè)變量d(d∈V)，首先根據(jù)復(fù)合語句控制信息，判斷其是否處于復(fù)合語句結(jié)構(gòu)中，并調(diào)用ControlSlice(c)算法依次處理復(fù)合語句結(jié)構(gòu)(解決了多層嵌套結(jié)構(gòu));然后，調(diào)用Slicing(d)算法，后向查找變量d的靜態(tài)切片.

圖5 程序切片主算法Slice(V)

復(fù)合關(guān)系子切片ControlSlice(c)算法如圖6所示.算法ControlSlice(c)的功能是計(jì)算復(fù)合語句結(jié)構(gòu)(選擇、循環(huán)結(jié)構(gòu))的程序切片，同時(shí)保持復(fù)合語句結(jié)構(gòu)切片的完整性.對(duì)于復(fù)合語句結(jié)構(gòu)中的變量x，首先調(diào)用Slicing(x)算法查找變量x的切片，目的是為了找到x的初始值.然后在beginline-endline中查找idUCf的五元結(jié)構(gòu)，如果x為第k個(gè)idUCf的定義變量，說明x在此復(fù)合結(jié)構(gòu)中被重新賦值，則應(yīng)依次處理第k個(gè)idUCf的使用變量集合U.

后向查找切片變量Slicing(d)算法如圖7所示.算法Slicing(d)的功能是根據(jù)idUCf五元結(jié)構(gòu)計(jì)算變量d的后向靜態(tài)切片.對(duì)于結(jié)點(diǎn)d，后向查找idUCf五元結(jié)構(gòu).

①如果d與第i個(gè)idUCf的定義變量相等，且idUCf類型為 AssignNode，則首先調(diào)用ControlSlice(c)函數(shù)，依次處理復(fù)合語句結(jié)構(gòu)的程序切片，然后依次遞歸調(diào)用Slicing(d)函數(shù)處理變量使用集U，直到U為?.

②如果d與第i個(gè)idUCf的定義變量相等，且idUCf類型為FunctionNode，則調(diào)用Slicing(r)，在其調(diào)用函數(shù)中求得返回值切片并返回各形參標(biāo)志para_flag，根據(jù)para_flag的取值判斷是否計(jì)算形參切片.

圖6 復(fù)合關(guān)系子切片ControlSlice(c)算法

③如果d與第i個(gè)idUCf的使用變量集合中元素相等，且idUCf類型為FunctionNode，根據(jù)實(shí)參-形參對(duì)應(yīng)關(guān)系，調(diào)用Slicing(para_d)函數(shù)，在調(diào)用函數(shù)中求得形參切片并返回各形參標(biāo)志，根據(jù)para_flag的取值判斷是否計(jì)算形參切片.

4 實(shí)驗(yàn)結(jié)果和分析

根據(jù)本文算法，以切片準(zhǔn)則(24，aboveAver)，計(jì)算程序圖8中的實(shí)例程序的靜態(tài)切片.本文切片算法只計(jì)算切片點(diǎn)所在函數(shù)以及與切片點(diǎn)計(jì)算相關(guān)的調(diào)用函數(shù)時(shí)才計(jì)算idUCf五元結(jié)構(gòu)和CNT，切片計(jì)算結(jié)果為:切片 slice(24，aboveAver)={24，4，20，40，48，45，43，42，41，19，2，10，9，8}，切片集合中元素的順序?yàn)槠浔患尤氲捻樞?為此，本文使用行號(hào)來代表程序切片語句.因?yàn)樾刑?hào)與語句具有一一對(duì)應(yīng)關(guān)系.圖8中的陰影部分為本切片算法所分析的語句，由此可以看出，本文算法只對(duì)main函數(shù)以及GetAboveAver函數(shù)進(jìn)行分析，只計(jì)算main函數(shù)以及GetAboveAver函數(shù)的idUCf五元結(jié)構(gòu)和CNT，無需計(jì)算與切片計(jì)算無關(guān)的GetDetail函數(shù).

圖7 后向查找切片變量Slicing(d)

表1～4列出了main函數(shù)和GetAboveAver函數(shù)的CNT以及idUCf五元結(jié)構(gòu).

表1 main函數(shù)的idUCf五元結(jié)構(gòu)表

表2 main函數(shù)的CNT

圖8 實(shí)例程序

表3 GetAboveAver函數(shù)的idUCf五元結(jié)構(gòu)

表4 GetAboveAver函數(shù)的CNT

圖9為本文算法所得到的靜態(tài)切片程序，本文算法充分考慮了程序的控制依賴、數(shù)據(jù)依賴以及函數(shù)調(diào)用信息.文獻(xiàn)［8］只考慮了直接控制依賴關(guān)系，而本文將直接控制依賴關(guān)系擴(kuò)展為復(fù)合關(guān)系集合 ＜C＞，充分考慮了多層嵌套情況，所得切片精度更高;而且，文獻(xiàn)［8］中只計(jì)算了過程內(nèi)動(dòng)態(tài)切片，而本文算法可以計(jì)算過程間靜態(tài)切片.

圖9 program1的切片程序

傳統(tǒng)的基于PDG、SDG的靜態(tài)程序切片算法復(fù)雜度很高［12-13］.例如對(duì)于程序 program1(見圖9)，傳統(tǒng)方法生成的 SDG共有66個(gè)結(jié)點(diǎn)(本程序?yàn)?7行:除去“{”和“}”)，66條控制依賴邊，79條數(shù)據(jù)依賴邊，2條函數(shù)調(diào)用邊.采用本文方法建立的idUCF五元結(jié)構(gòu)的元素總個(gè)數(shù)為10個(gè)，CNT中的元素總個(gè)數(shù)僅為4個(gè)，大大低于SDG中的節(jié)點(diǎn)個(gè)數(shù).在計(jì)算程序切片過程中，傳統(tǒng)的基于SDG的方法需要根據(jù)控制依賴邊和數(shù)據(jù)依賴邊遍歷所有節(jié)點(diǎn)，而本文算法只需計(jì)算與切片點(diǎn)相關(guān)的控制依賴、數(shù)據(jù)依賴以及相關(guān)的函數(shù).在main函數(shù)中，控制依賴信息只分析了與切片點(diǎn)相關(guān)的第10行的for循環(huán)，無需分析第13行的if語句.數(shù)據(jù)依賴信息只分析了與aboveAver相關(guān)的 aver、score、sum的數(shù)據(jù)依賴，不需對(duì)failnum的數(shù)據(jù)依賴進(jìn)行分析.函數(shù)調(diào)用方面，函數(shù)GetDetail與切片點(diǎn)無關(guān)，也不用分析.另外，只計(jì)算與切片點(diǎn)相關(guān)函數(shù)的 idUCf五元結(jié)構(gòu)和CNT，在本實(shí)例中，只計(jì)算了 main函數(shù)和GetAboveAver的 idUCf和 CNT，而 GetDetail未計(jì)算.綜上所述，本文算法在保證多層嵌套結(jié)構(gòu)程序的靜態(tài)切片完整性的前提下，充分考慮了函數(shù)調(diào)用信息，有效節(jié)省了時(shí)間與空間.

1)傳統(tǒng)方法分析的對(duì)象是PDG或SDG.建立PDG和SDG時(shí)需要計(jì)算程序的控制流和數(shù)據(jù)流，復(fù)雜度主要集中在數(shù)據(jù)流分析中.假設(shè)程序中包含n個(gè)節(jié)點(diǎn)，利用迭代算法生成每個(gè)節(jié)點(diǎn)的定值/引用到達(dá)信息，數(shù)據(jù)流分析的時(shí)間復(fù)雜度為O(n2).

本文方法分析的對(duì)象是函數(shù)的CNT和idUCF五元結(jié)構(gòu).建立CNT和idUCF五元結(jié)構(gòu)只需分析標(biāo)準(zhǔn)化TOKEN序列一次即可，因此時(shí)間復(fù)雜度為O(n).

2)傳統(tǒng)方法計(jì)算切片時(shí)的時(shí)間復(fù)雜度普遍為O(n4).對(duì)于本文方法，考慮最壞情況，假設(shè)idUCF五元結(jié)構(gòu)中元素個(gè)數(shù)為n(實(shí)際上idUCF中的元素個(gè)數(shù)遠(yuǎn)小于n)，切片準(zhǔn)則中包含了程序中的所有變量，本文方法計(jì)算切片的時(shí)間復(fù)雜度為O(n2).

對(duì)于空間復(fù)雜度，傳統(tǒng)方法通常使用矩陣來存儲(chǔ)PDG、SDG的數(shù)據(jù)依賴關(guān)系和控制依賴關(guān)系，矩陣大小為n×n，則空間復(fù)雜度為O(n2).本文方法只需要存儲(chǔ)CNT和idUCF五元結(jié)構(gòu).考慮最壞情況，假設(shè)idUCF五元結(jié)構(gòu)和CNT中元素個(gè)數(shù)之和為n(實(shí)際上應(yīng)遠(yuǎn)小于n)，本文方法需要存儲(chǔ)空間為5×n，則空間復(fù)雜度為O(n).

5 結(jié)語

針對(duì)傳統(tǒng)的基于PDG、SDG的程序切片算法需要計(jì)算無關(guān)數(shù)據(jù)依賴，計(jì)算復(fù)雜度較高的問題，本文提出基于idUCf五元結(jié)構(gòu)的過程間切片算法，對(duì)于多層嵌套結(jié)構(gòu)程序在保證其靜態(tài)切片完整性的前提下，只計(jì)算與切片相關(guān)的依賴信息，提高了程序切片的計(jì)算效率.

［1］WARD M，ZEDAN H.Combining dynamic and static slicing foranalysing assembler［J］. Science of Computer Programming，2010，75(3):134-175.

［2］HALDER R，CORTESI A.Abstract program slicing on dependence condition graphs［J］.Science of Computer Programming，2013，78(9):1240-1263.

［3］WEISER M D.Rrogram slices formal，psychological and practical investigations of an automatic program abstraction method［D］.Michigan:University of Michigan，1979.

［4］ OTTENSTAN K J，OTTENSTAN L M.The program dependence graph in a software development environment［J］.ACM SIGPLAN Notices，1984，19(5):177-184.

［5］ HORWITZ S，REPS T，BNKLEY D.Interprocedural slicing using dependence graths［J］.ACM Trans on Programming Language and System，1990，2(1):26-60.

［6］姜淑娟，徐寶文，史亮.一種基于異常傳播分析的數(shù)據(jù)流分析方法［J］.軟件學(xué)報(bào)，2007，18(4):832-841.

［7］張龍杰，謝曉方，袁勝智.一種改進(jìn)的靜態(tài)程序切片算法［J］.計(jì)算機(jī)應(yīng)用，2009，29(3):705-711.

［8］ BESZEDES A，GERGELY T，SZABO Z M，et al.Dynamic slicing method for maintenance of large C programs［C］//Proceedings of the Fifth European Conference on Software Maintenance and Reengineering. Washington， DC:IEEE Computer Society，2001:105-113.

［9］SIKKA P，KAUR K.Program slicing techniques and their need in aspectoriented programming ［J］.International Journal of Computer Applications，2013，70(3):11-14.

［10］DANICIC S，HARMAN M，HOWROYD J，et al.A non-standard semantics for program slicing and dependence analysis［J］.The Journal of Logic and Algebraic Programming，2007，(72):191-206.

［11］龔丹丹，王甜甜，蘇小紅，等.冗余代碼缺陷檢測(cè)方法［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2012，44(7):58-63.

［12］BINKLEY D，GOLD N，HARMAN H.An empirical study ofstatic program slice size ［J］. ACM Transactions on Software Engineering and Methodology，2007，16(2):1-32.

［13］KRINKE J.Effects of context on program slicing［J］.Journal of Systems and Software，2006，79(9):1249-1260.