計算機程序切片技術探討

劉恩娜

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

關鍵詞：動態程序切片；算法：回歸測試

1計算機程序切片的分類

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

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

1.2 過程內切片和過程間切片

根據切片的范圍，可以分為過程內切片和過程間切片。過程內切片是指單個過程內影響興趣點變量的值(或受興趣點變量的值影響)的語句的集合，不考慮過程調用的情況；過程間切片指在過程內切片的基礎上，考慮過程調用的情況。執行過程間切片時，要分析實參和形參相對應的依賴關系，要完成實參和形參之間依賴性的轉換。

1.3 靜態切片，動態切片和條件切片

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

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

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

2 程序切片的準則

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

2.1 靜態切片準則

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

2.2 動切片準則切片

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

2.3 條件切片準則

如果要對一個程序進行條件切片，需要構造一個條件切片準則。條件切片準則是一個三元組，其中p是感興趣點，就是程序中的某條語句。V是p處定義或引用的變量，可以是某一個變量，也可以是幾個變量的集合。π是一個謂詞，是V中變量的關系的集合。構造一個程序P的條件切片，當在一個滿足π的初始狀態執行時，條件切片必須保持程序P（與V有關）的投影含義。

2.4 迭代切片準則

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

2.5 多點切片準則

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

3程序切片的算法

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

4 程序切片的應用

程序切片技術在軟件工程的活動中應用非常廣泛。如程序分析、理解、測試、調試、度量以及維護過程中都可以應用程序切片技術。了解程序切片的作用，是我們研究切片技術的基礎。

4.1 程序調試

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

4.2 程序理解

對原有軟件系統的維護和修改是一項非常繁瑣的工作，在開發過程中，對原有系統的理解要占整個軟件開發生命周期和軟件費用的50％到70％。所謂程序理解就是通過系統的靜態描述來理解程序的動態行為。不借助專門的程序理解工具，無論是對經驗豐富的維護人員還是一個新手來說，程序理解的過程都是很困難的。程序切片作為一種程序理解的方法能夠將用戶所關心的變量從復雜的程序中挖掘出來。計算該變量的程序切片，讓用戶更清晰地理解其它變量與該變量之間的聯系，在切片過程中，還能收集程序的調用信息，類，結構等信息，這樣用戶就能很方便地理解程序了。

4.3 回歸測試

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

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

4.4 測試數據生成

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

4.5 逆向工程

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

參考文獻

[1]楊洪,徐寶文,PSS/Ada程序切片系統的設計與實現,計算機研究與發展,1997,34(3)

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

[3]王偉,陳平,程序切片技術綜述,微電子學與計算機,2002,8

[4]王雪蓮,趙瑞蓮,李立健,一種用于測試數據生成的動態程序切片算法,計算機應用,2005,6(6)