計(jì)算機(jī)程序切片技術(shù)探討

劉恩娜

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

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

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

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

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

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

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

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

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

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

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

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

程序切片還要考慮切片準(zhǔn)則。對(duì)于不同的切片準(zhǔn)則，相同的源代碼得到的程序切片是不同的?；旧?，對(duì)每一類(lèi)切片都有不同的切片準(zhǔn)則。常見(jiàn)的切片準(zhǔn)則有：

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

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

2.2 動(dòng)切片準(zhǔn)則切片

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

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

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

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

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

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

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

3程序切片的算法

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

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

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

4.1 程序調(diào)試

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

4.2 程序理解

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

4.3 回歸測(cè)試

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

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

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

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

4.5 逆向工程

逆向工程這個(gè)術(shù)語(yǔ)最初來(lái)自硬件，后來(lái)發(fā)展到軟件工程中。在軟件工程中是指分析程序．力圖在比源代碼更高抽象層次上建立程序表示的過(guò)程。其中的主要工作就是如何對(duì)現(xiàn)存的軟件系統(tǒng)進(jìn)行理解，包括對(duì)程序源代碼的抽象，對(duì)程序基本算法和設(shè)計(jì)方案的理解等。通過(guò)構(gòu)造程序切片可以對(duì)源程序進(jìn)行精簡(jiǎn)，除去暫不關(guān)心的部分，將源程序中分散的關(guān)鍵部分專(zhuān)門(mé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]王雪蓮,趙瑞蓮,李立健,一種用于測(cè)試數(shù)據(jù)生成的動(dòng)態(tài)程序切片算法,計(jì)算機(jī)應(yīng)用,2005,6(6)