一種新的過程間靜態切片快速算法

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

(哈爾濱工業大學計算機科學與技術學院，150001哈爾濱)

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

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

本文提出的基于idUCf五元結構的過程間切片算法，既保留了程序的數據依賴、控制依賴以及函數調用信息，又充分考慮了多層嵌套情況，而且不需要使用SDG，無需計算與切片無關的數據依賴、控制依賴以及不相關函數調用信息.

1 idUCf五元結構及相關定義

本文在分析靜態切片與切片準則的基礎上，給出了復合語句控制結構信息表以及idUCf五元結構的定義，作為本文切片算法的研究基礎.

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

定義2(靜態切片準則［10］) 靜態切片準則是一個二元組C=(n，V)，其中:V為程序P中變量集合的一個子集;n為程序P中的某個興趣點(對應于P中的一條語句).

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

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

圖1 復合語句控制結構信息表結構

圖2 復合語句控制結構信息表實例

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

圖3 idUCf五元結構實例

2 idUCf五元結構的靜態切片模型

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

1)通過詞法分析生成 TOKEN序列，在TOKEN序列基礎上進行代碼標準化［11］，最終生成標準化TOKEN序列.

2)在標準化TOKEN序列基礎上，分別生成函數列表、復合語句控制結構信息表 CNT和idUCF五元結構.

3)應用基于idUCf五元結構的過程間靜態切片算法，得到過程間靜態切片.

圖4 程序切片算法模型

3 切片算法

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

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

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

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

當使用變量集合 ＜U＞為?時，代表定義變量被賦予常數，即找到了變量的初始值，此時，上式可變為

當計算復合關系子切片ControlSlice(c)時，根據idUCf五元結構中的c(c∈C;c為該復合語句所對應的CNT的id號)查找CNT，找到所對應的復合語句的具體信息.

①如果該復合語句為選擇結構，則依次計算該選擇結構的判斷變量j的后向切片，以計算判斷變量的初始值，即

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

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

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

當所求切片變量d∈FunctionNode的使用集＜U＞，說明d為調用函數的參數之一.

①當調用參數傳遞類型為傳值調用時，被調函數中對形參的改變不影響實參的值，所以無需計算實參(para)所對應的形參切片Slice(argue)，則有

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

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

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

復合關系子切片ControlSlice(c)算法如圖6所示.算法ControlSlice(c)的功能是計算復合語句結構(選擇、循環結構)的程序切片，同時保持復合語句結構切片的完整性.對于復合語句結構中的變量x，首先調用Slicing(x)算法查找變量x的切片，目的是為了找到x的初始值.然后在beginline-endline中查找idUCf的五元結構，如果x為第k個idUCf的定義變量，說明x在此復合結構中被重新賦值，則應依次處理第k個idUCf的使用變量集合U.

后向查找切片變量Slicing(d)算法如圖7所示.算法Slicing(d)的功能是根據idUCf五元結構計算變量d的后向靜態切片.對于結點d，后向查找idUCf五元結構.

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

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

圖6 復合關系子切片ControlSlice(c)算法

③如果d與第i個idUCf的使用變量集合中元素相等，且idUCf類型為FunctionNode，根據實參-形參對應關系，調用Slicing(para_d)函數，在調用函數中求得形參切片并返回各形參標志，根據para_flag的取值判斷是否計算形參切片.

4 實驗結果和分析

根據本文算法，以切片準則(24，aboveAver)，計算程序圖8中的實例程序的靜態切片.本文切片算法只計算切片點所在函數以及與切片點計算相關的調用函數時才計算idUCf五元結構和CNT，切片計算結果為:切片 slice(24，aboveAver)={24，4，20，40，48，45，43，42，41，19，2，10，9，8}，切片集合中元素的順序為其被加入的順序.為此，本文使用行號來代表程序切片語句.因為行號與語句具有一一對應關系.圖8中的陰影部分為本切片算法所分析的語句，由此可以看出，本文算法只對main函數以及GetAboveAver函數進行分析，只計算main函數以及GetAboveAver函數的idUCf五元結構和CNT，無需計算與切片計算無關的GetDetail函數.

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

表1～4列出了main函數和GetAboveAver函數的CNT以及idUCf五元結構.

表1 main函數的idUCf五元結構表

表2 main函數的CNT

圖8 實例程序

表3 GetAboveAver函數的idUCf五元結構

表4 GetAboveAver函數的CNT

圖9為本文算法所得到的靜態切片程序，本文算法充分考慮了程序的控制依賴、數據依賴以及函數調用信息.文獻［8］只考慮了直接控制依賴關系，而本文將直接控制依賴關系擴展為復合關系集合 ＜C＞，充分考慮了多層嵌套情況，所得切片精度更高;而且，文獻［8］中只計算了過程內動態切片，而本文算法可以計算過程間靜態切片.

圖9 program1的切片程序

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

1)傳統方法分析的對象是PDG或SDG.建立PDG和SDG時需要計算程序的控制流和數據流，復雜度主要集中在數據流分析中.假設程序中包含n個節點，利用迭代算法生成每個節點的定值/引用到達信息，數據流分析的時間復雜度為O(n2).

本文方法分析的對象是函數的CNT和idUCF五元結構.建立CNT和idUCF五元結構只需分析標準化TOKEN序列一次即可，因此時間復雜度為O(n).

2)傳統方法計算切片時的時間復雜度普遍為O(n4).對于本文方法，考慮最壞情況，假設idUCF五元結構中元素個數為n(實際上idUCF中的元素個數遠小于n)，切片準則中包含了程序中的所有變量，本文方法計算切片的時間復雜度為O(n2).

對于空間復雜度，傳統方法通常使用矩陣來存儲PDG、SDG的數據依賴關系和控制依賴關系，矩陣大小為n×n，則空間復雜度為O(n2).本文方法只需要存儲CNT和idUCF五元結構.考慮最壞情況，假設idUCF五元結構和CNT中元素個數之和為n(實際上應遠小于n)，本文方法需要存儲空間為5×n，則空間復雜度為O(n).

5 結語

針對傳統的基于PDG、SDG的程序切片算法需要計算無關數據依賴，計算復雜度較高的問題，本文提出基于idUCf五元結構的過程間切片算法，對于多層嵌套結構程序在保證其靜態切片完整性的前提下，只計算與切片相關的依賴信息，提高了程序切片的計算效率.

［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］姜淑娟，徐寶文，史亮.一種基于異常傳播分析的數據流分析方法［J］.軟件學報，2007，18(4):832-841.

［7］張龍杰，謝曉方，袁勝智.一種改進的靜態程序切片算法［J］.計算機應用，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］龔丹丹，王甜甜，蘇小紅，等.冗余代碼缺陷檢測方法［J］.哈爾濱工業大學學報，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.