劉恩娜

摘要：程序切片技術(shù)是一種分析和理解程序的技術(shù)，在程序切片技術(shù)提出的30年來，得到了很快的發(fā)展。本文主要介紹了程序切片的基本概念，程序切片的種類、算法以及用途。

關(guān)鍵詞：動態(tài)程序切片；算法：回歸測試

1計(jì)算機(jī)程序切片的分類

１.１ 前向切片和后向切片

根據(jù)計(jì)算切片方向的不同，可把程序切片分為前向程序切片和后向程序切片。前向程序切片是指所有受興趣點(diǎn)變量的值影響的語句的集合；后向切片是指程序中所有能夠影響興趣點(diǎn)變量的值的語句的集合。這兩類切片最后是不構(gòu)成一個可執(zhí)行程序的。

1.2 過程內(nèi)切片和過程間切片

根據(jù)切片的范圍，可以分為過程內(nèi)切片和過程間切片。過程內(nèi)切片是指單個過程內(nèi)影響興趣點(diǎn)變量的值(或受興趣點(diǎn)變量的值影響)的語句的集合，不考慮過程調(diào)用的情況；過程間切片指在過程內(nèi)切片的基礎(chǔ)上，考慮過程調(diào)用的情況。執(zhí)行過程間切片時，要分析實(shí)參和形參相對應(yīng)的依賴關(guān)系，要完成實(shí)參和形參之間依賴性的轉(zhuǎn)換。

1.3 靜態(tài)切片，動態(tài)切片和條件切片

根據(jù)切片過程對程序某一次具體的輸入的依賴程度，可將程序切片分為靜態(tài)切片和動態(tài)切片。靜態(tài)切片是指不考慮程序運(yùn)行時的輸入，完全利用靜態(tài)分析方法得到切片，也就是分析程序的源代碼，計(jì)算所有可能輸入情況下的切片。靜態(tài)切片考慮了程序中所有的執(zhí)行路徑，包含了所有與興趣點(diǎn)處變量相關(guān)的語句，不管某些語句在程序?qū)嶋H的執(zhí)行中是否被執(zhí)行，因而，靜態(tài)切片具有很大的冗余性，工作量較大。

動態(tài)切片是指在特定輸入下實(shí)際影響興趣點(diǎn)變量值（或受興趣點(diǎn)變量值影響）的所有語句的集合。動態(tài)切片只考慮程序在某個具體輸入下，實(shí)際執(zhí)行的路徑中，和興趣點(diǎn)變量相關(guān)的語句。因此，動態(tài)切片的計(jì)算過程依賴于程序的具體輸入，因而，每一次的計(jì)算工作量較小，但得到的切片相對比較精確。

條件切片技術(shù)是一種介于靜態(tài)切片技術(shù)與動態(tài)切片技術(shù)之間的切片技術(shù)。在進(jìn)行條件切片時，只有滿足該切片條件的那些輸入才會被分析。這個條件對應(yīng)著程序的某個或某些初始狀態(tài)。如果存在從滿足切片條件的任一個初始狀態(tài)出發(fā)都不可能被執(zhí)行的語句，那么把這些語句去除掉后，就得到了在這個切片條件下的程序切片。

2 程序切片的準(zhǔn)則

程序切片還要考慮切片準(zhǔn)則。對于不同的切片準(zhǔn)則，相同的源代碼得到的程序切片是不同的。基本上，對每一類切片都有不同的切片準(zhǔn)則。常見的切片準(zhǔn)則有：

2.1 靜態(tài)切片準(zhǔn)則

如果要對一個程序P進(jìn)行靜態(tài)切片，需要構(gòu)造一個靜態(tài)切片準(zhǔn)則。p是感興趣點(diǎn)，就是程序中的某條語句。V是p處定義或引用的變量，可以是某一個變量，也可以是幾個變量的集合。程序P的靜態(tài)后向切片就是程序中所有能夠影響p處的V中的變量的語句的集合；靜態(tài)前向切片就是程序中所有受p處的V中的變量影響的語句的集合。

2.2 動切片準(zhǔn)則切片

如果要對一個程序進(jìn)行動態(tài)切片，需要構(gòu)造一個動態(tài)切片準(zhǔn)則。動態(tài)切片準(zhǔn)則是一個三元組，其中p是感興趣點(diǎn)，就是程序中的某條語句。V是p處定義或引用的變量，可以是某一個變量，也可以是幾個變量的集合。i是程序本次執(zhí)行的具體輸入。程序的動態(tài)后向切片是指在本次執(zhí)行的語句中，所有能夠影響p處的V中的變量的語句的集合；程序的動態(tài)前向切片是指在本次執(zhí)行的語句中，所有受p處的V中的變量影響的語句的集合。

2.3 條件切片準(zhǔn)則

如果要對一個程序進(jìn)行條件切片，需要構(gòu)造一個條件切片準(zhǔn)則。條件切片準(zhǔn)則是一個三元組，其中p是感興趣點(diǎn)，就是程序中的某條語句。V是p處定義或引用的變量，可以是某一個變量，也可以是幾個變量的集合。π是一個謂詞，是V中變量的關(guān)系的集合。構(gòu)造一個程序P的條件切片，當(dāng)在一個滿足π的初始狀態(tài)執(zhí)行時，條件切片必須保持程序P（與V有關(guān)）的投影含義。

2.4 迭代切片準(zhǔn)則

迭代切片準(zhǔn)則是一個三元組C=，其中p是感興趣點(diǎn)，就是程序中的某條語句。V是p處定義或引用的變量，可以是某一個變量，也可以是幾個變量的集合。n是自然數(shù)。程序P的第n次(靜態(tài))迭代切片是由第n次執(zhí)行到達(dá)p那些保持程序P的投影含義不變的語句組成。當(dāng)n擴(kuò)充到N（自然數(shù)集）時就變成廣義迭代切片準(zhǔn)則。

2.5 多點(diǎn)切片準(zhǔn)則

多點(diǎn)切片準(zhǔn)則是一個二元組C=(V,N)，其中N是程序P中節(jié)點(diǎn)的集合，V是變量的集合。當(dāng)在N中任何一點(diǎn)執(zhí)行一條語句時，對于V中的所有變量而言，切片和程序P具有同樣的效果。

3程序切片的算法

程序切片的算法很多，有weiser提出的數(shù)據(jù)流方程的算法，Karl Ottenstein和Linda Ottenstein提出的基于程序依賴圖的算法。Horwitz, Reps和Binkley擴(kuò)展了程序依賴圖的算法，提出了系統(tǒng)依賴圖的方法。Ernst提出了基于另一種圖表示的Value dependence graph(VDG)算法。另外還有無定切片算法，Ergeretti的基于信息流關(guān)系的算法，楊洪的基于波動圖的算法等。其中以基于依賴圖的圖形可達(dá)性算法應(yīng)用最為廣泛。該方法首先根據(jù)程序中的數(shù)據(jù)依賴和控制依賴關(guān)系將源程序轉(zhuǎn)化為程序依賴圖的表示形式，然后利用兩次圖遍歷算法，得到該源程序的關(guān)于某一切片準(zhǔn)則的程序切片。

4 程序切片的應(yīng)用

程序切片技術(shù)在軟件工程的活動中應(yīng)用非常廣泛。如程序分析、理解、測試、調(diào)試、度量以及維護(hù)過程中都可以應(yīng)用程序切片技術(shù)。了解程序切片的作用，是我們研究切片技術(shù)的基礎(chǔ)。

4.1 程序調(diào)試

在程序調(diào)試過程中，經(jīng)常需要跟蹤程序的執(zhí)行過程，以定位錯誤，然后改正。然而對于大型程序來說，程序每次執(zhí)行的語句都很多。如果采用逐條語句跟蹤的調(diào)試方法，將會耗費(fèi)大量的時間，效果也不好。程序切片可以幫助程序員很容易的進(jìn)行錯誤定位。通過程序切片技術(shù)，可以收集到只和出錯變量相關(guān)的語句，忽略其他的語句，調(diào)試時，那些和出錯變量不相關(guān)的語句就可以不考慮，這樣就加快了調(diào)試過程。

4.2 程序理解

對原有軟件系統(tǒng)的維護(hù)和修改是一項(xiàng)非常繁瑣的工作，在開發(fā)過程中，對原有系統(tǒng)的理解要占整個軟件開發(fā)生命周期和軟件費(fèi)用的50％到70％。所謂程序理解就是通過系統(tǒng)的靜態(tài)描述來理解程序的動態(tài)行為。不借助專門的程序理解工具，無論是對經(jīng)驗(yàn)豐富的維護(hù)人員還是一個新手來說，程序理解的過程都是很困難的。程序切片作為一種程序理解的方法能夠?qū)⒂脩羲P(guān)心的變量從復(fù)雜的程序中挖掘出來。計(jì)算該變量的程序切片，讓用戶更清晰地理解其它變量與該變量之間的聯(lián)系，在切片過程中，還能收集程序的調(diào)用信息，類，結(jié)構(gòu)等信息，這樣用戶就能很方便地理解程序了。

4.3 回歸測試

回歸測試是指在對程序的某一模塊進(jìn)行了修改后，為了確保對模塊的修改達(dá)到目的并且沒有引入新的錯誤，需要對已經(jīng)完成的測試重新進(jìn)行，即重新測試先前測試過的測試用列。但測試用列通常很多，全部進(jìn)行回歸測試需要花費(fèi)很多的人力和時間，在很多情況下是不切實(shí)際的。

運(yùn)用程序切片技術(shù)可以比較新舊版本程序的系統(tǒng)依賴圖，找出新舊版本程序的差別所在。這樣，就能找到針對那些不同點(diǎn)的測試用列，進(jìn)行測試，減少了工作量。

4.4 測試數(shù)據(jù)生成

動態(tài)切片應(yīng)用于軟件測試數(shù)據(jù)自動生成，可以有效地提高基于路徑測試數(shù)據(jù)的生成效率，主要的思想是通過比較動態(tài)切片結(jié)果與指定路徑，不斷地調(diào)整輸入，直到與指定路徑相符，輸入則為測試數(shù)據(jù)。應(yīng)用動態(tài)切片來生成測試數(shù)據(jù)，可以減少反復(fù)執(zhí)行程序花費(fèi)的時間，并且根據(jù)動態(tài)切片可以消除調(diào)整的盲目性，減少調(diào)整次數(shù)，提高測試數(shù)據(jù)的生成效率。

4.5 逆向工程

逆向工程這個術(shù)語最初來自硬件，后來發(fā)展到軟件工程中。在軟件工程中是指分析程序．力圖在比源代碼更高抽象層次上建立程序表示的過程。其中的主要工作就是如何對現(xiàn)存的軟件系統(tǒng)進(jìn)行理解，包括對程序源代碼的抽象，對程序基本算法和設(shè)計(jì)方案的理解等。通過構(gòu)造程序切片可以對源程序進(jìn)行精簡，除去暫不關(guān)心的部分，將源程序中分散的關(guān)鍵部分專門進(jìn)行分析。

參考文獻(xiàn)

[1]楊洪,徐寶文,PSS/Ada程序切片系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn),計(jì)算機(jī)研究與發(fā)展,1997,34(3)

[2]朱平,譚毅,李必信等,一種基于分層切片模型思想的源程序信息分析方案,計(jì)算機(jī)工程,2001,27(12)

[3]王偉,陳平,程序切片技術(shù)綜述,微電子學(xué)與計(jì)算機(jī),2002,8

[4]王雪蓮,趙瑞蓮,李立健,一種用于測試數(shù)據(jù)生成的動態(tài)程序切片算法,計(jì)算機(jī)應(yīng)用,2005,6(6)