程序切片技術(shù)在軟件測(cè)試中的應(yīng)用

摘要：基于程序切片的軟件測(cè)試是一種以程序或程序和需求相結(jié)合為基礎(chǔ)的測(cè)試，它根據(jù)程序的不同切片來(lái)縮小軟件的測(cè)試范圍、提高軟件測(cè)試的效率、輔助測(cè)試數(shù)據(jù)的自動(dòng)生成等。同時(shí)由于程序切片不僅考慮了數(shù)據(jù)依賴和控制依賴，還考慮了程序存在的其他各種依賴關(guān)系，使得測(cè)試的準(zhǔn)確性得到提高。詳細(xì)闡述了目前存在的各種切片技術(shù)及其應(yīng)用領(lǐng)域，重點(diǎn)探討了目前切片技術(shù)在測(cè)試領(lǐng)域中的具體應(yīng)用。

關(guān)鍵詞：程序切片；軟件測(cè)試；數(shù)據(jù)依賴；控制依賴；測(cè)試數(shù)據(jù)自動(dòng)生成

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)05－0210－04

程序切片是一種程序分析和理解技術(shù)。它通過(guò)把程序減少到只包含與某個(gè)特定計(jì)算相關(guān)的那些語(yǔ)句來(lái)分析程序。其概念最早是1979年由Mark Weiser[1]提出來(lái)的。他觀察到程序員在調(diào)試過(guò)程中腦海中就有關(guān)于程序的某種抽象，人們?cè)谡{(diào)試一個(gè)程序時(shí)總是從錯(cuò)誤語(yǔ)句s開始，并沿著依賴關(guān)系跟蹤到它影響的程序部分。程序切片的發(fā)展基本成熟，在理論和應(yīng)用方面的研究均取得了可喜的進(jìn)展，特別是在程序的調(diào)試、測(cè)試、分解和集成、軟件維護(hù)、代碼理解以及逆向工程等領(lǐng)域具有廣泛的應(yīng)用。本文將側(cè)重介紹程序切片技術(shù)在軟件測(cè)試領(lǐng)域的應(yīng)用。

1程序切片簡(jiǎn)介

Weiser認(rèn)為一個(gè)切片與人們?cè)谡{(diào)試一個(gè)程序時(shí)所做的智力抽象相對(duì)應(yīng)。他定義的程序P的切片S是一個(gè)可執(zhí)行的程序，對(duì)某個(gè)興趣點(diǎn)s處的變量v而言（s，v稱為切片準(zhǔn)則），S由程序P中可能影響s處變量v的值的所有語(yǔ)句構(gòu)成。這個(gè)可執(zhí)行部分相對(duì)于程序P在功能上是等效的[2]。他提出的切片算法是基于數(shù)據(jù)流分析的，通過(guò)遍歷控制流圖分析數(shù)據(jù)依賴和控制依賴關(guān)系，從源程序中移去零條或多條語(yǔ)句從而得到過(guò)程內(nèi)的切片。

定義1設(shè)s是程序流圖CFG 中的任一節(jié)點(diǎn)，定義：

程序切片不僅與興趣點(diǎn)定義和使用的變量有關(guān)，還與影響該變量的值的語(yǔ)句和謂詞以及受該變量的值影響的語(yǔ)句和謂詞有關(guān)。程序切片過(guò)程中，采用合適的結(jié)構(gòu)來(lái)表示語(yǔ)句間的依賴關(guān)系，尋找與興趣點(diǎn)具有直接或間接數(shù)據(jù)依賴和控制依賴的節(jié)點(diǎn)是生成切片的重點(diǎn)。切片算法基本過(guò)程為：首先尋找語(yǔ)句s的變量v所直接數(shù)據(jù)依賴或控制依賴的節(jié)點(diǎn)；然后尋找這些新節(jié)點(diǎn)所直接數(shù)據(jù)依賴或控制依賴的節(jié)點(diǎn)；一直重復(fù)下去，直到?jīng)]有新節(jié)點(diǎn)加進(jìn)來(lái)為止；最后將這些節(jié)點(diǎn)按源程序的語(yǔ)句順序排列，即為程序P的關(guān)于語(yǔ)句s的切片S。

2程序切片分類

程序切片技術(shù)的發(fā)展經(jīng)歷了從靜態(tài)到動(dòng)態(tài)、從前向到后向、從單一過(guò)程到多個(gè)過(guò)程、從過(guò)程型程序到面向?qū)ο蟪绦颉姆欠植际匠绦虻椒植际匠绦虻葞讉€(gè)方面。

2．1靜態(tài)切片與動(dòng)態(tài)切片

Weiser最初提出的程序切片概念就屬于靜態(tài)切片（Static Slicing）范疇。靜態(tài)切片是在編譯時(shí)間， 即程序尚未運(yùn)行時(shí)進(jìn)行切片；該技術(shù)對(duì)程序的輸入不作任何假設(shè)，所作的分析完全以程序的靜態(tài)信息為依據(jù)。因此靜態(tài)切片包含了所有與興趣點(diǎn)處變量相關(guān)的語(yǔ)句， 考慮了程序中所有可能的執(zhí)行路徑。其缺點(diǎn)是：①容易包含不相關(guān)節(jié)點(diǎn)，具有很大的冗余性。主要是由于程序的執(zhí)行路徑無(wú)法靜態(tài)判斷，尤其是數(shù)組和指針變量無(wú)法靜態(tài)確定。②使用該技術(shù)的工作量較大。因?yàn)橐治龀绦蛩锌赡艿膱?zhí)行軌跡，靜態(tài)切片技術(shù)一般用于程序理解與軟件維護(hù)方面。

實(shí)際應(yīng)用中，人們往往更關(guān)注某一具體輸入下，程序?qū)嶋H執(zhí)行時(shí)影響興趣點(diǎn)處某一變量值的那些語(yǔ)句。

Korel等人[3]提出了動(dòng)態(tài)切片（Dynamic Slicing）的概念。切片準(zhǔn)則是一個(gè)三元組（s，v，x），s、v的定義不變，x是一個(gè)輸入序列，在該輸入下與源程序計(jì)算出的該變量的值是相同的。動(dòng)態(tài)程序切片計(jì)算過(guò)程使用用戶的實(shí)際輸入x產(chǎn)生的精確數(shù)據(jù)流信息進(jìn)行分析，通常情況下比靜態(tài)切片要小得多；動(dòng)態(tài)切片的另一個(gè)優(yōu)點(diǎn)是在程序運(yùn)行時(shí)間進(jìn)行切片， 數(shù)組中的每個(gè)元素和指針變量的值得到確定，因此動(dòng)態(tài)切片要比靜態(tài)切片精確得多。動(dòng)態(tài)切片的缺點(diǎn)是需要保留程序的執(zhí)行歷史記錄。采用這一技術(shù)，每一次的計(jì)算工作量較小，但每一次的計(jì)算都不盡相同，因此動(dòng)態(tài)切片技術(shù)多用于程序調(diào)試、測(cè)試方面。動(dòng)態(tài)切片還可以用在理解大型程序方面。圖1給出了靜態(tài)切片與動(dòng)態(tài)切片的例子。

2．2前向切片與后向切片

如果切片S由程序P中可能影響s處變量v的值的所有語(yǔ)句組成，這是一種前向切片（Forward Slicing）。與此相反，后向切片（Backward Slicing）S是程序P中興趣點(diǎn)s處變量v的值影響到的語(yǔ)句和謂詞組成的集合。圖2給出了前向和后向切片的例子。

2．3對(duì)象切片

自Weiser提出程序切片概念后，人們提出了許多用于過(guò)程型程序的切片方法，但這些方法并不適用于OO程序。因?yàn)镺O編程語(yǔ)言提出了一些新的概念與特性，如類、對(duì)象、動(dòng)態(tài)綁定、封裝、繼承、消息傳遞以及多態(tài)。所以面向?qū)ο蟪绦蚯衅粌H要考察語(yǔ)句和數(shù)據(jù)之間的依賴關(guān)系，還要考察各個(gè)類之間的關(guān)系。為了獲得更準(zhǔn)確、更有效的程序切片，D Liang和M.J.Harrod提出了對(duì)象切片（ObjectSlicing）技術(shù)這一概念；他們的工作是通過(guò)擴(kuò)展系統(tǒng)依賴圖實(shí)現(xiàn)的。目前對(duì)它的研究更多是側(cè)重于靜態(tài)切片這一部分，而且基本都是基于依賴圖的。李必信等人提出了一種逐步求精的基于OO程序的分層切片方法。

2．4其他切片技術(shù)

（1）準(zhǔn)靜態(tài)切片（Quasi Static Slicing）。準(zhǔn)靜態(tài)切片的產(chǎn)生是對(duì)于一些特殊程序P，某些輸入值可以確定，而另外一些輸入不停變化；在此情況下對(duì)程序P進(jìn)行分析時(shí)，需要混合使用靜態(tài)切片和動(dòng)態(tài)切片方法。在計(jì)算切片時(shí)，固定一部分輸入值，使得程序P中的某些特定子路徑得以執(zhí)行，可以刪除一些分支。這樣得到的切片比純粹的靜態(tài)切片要精簡(jiǎn)得多。部分靜態(tài)切片用于程序理解和轉(zhuǎn)換。

(2)同步動(dòng)態(tài)切片（Simultaneous Dynamic Slicing）。Hall[4]擴(kuò)展了動(dòng)態(tài)切片，他將一個(gè)測(cè)試集而不是單個(gè)測(cè)試用例用于程序動(dòng)態(tài)切片中。一個(gè)測(cè)試集可以看成是對(duì)某個(gè)需求的完全測(cè)試用例集。Hall提出的同步動(dòng)態(tài)切片并不是簡(jiǎn)單地對(duì)每個(gè)測(cè)試用例的動(dòng)態(tài)切片進(jìn)行的并集，而是采用了迭代算法，從初始切片開始在迭代過(guò)程中逐步增長(zhǎng)為大型的動(dòng)態(tài)切片。同步動(dòng)態(tài)切片適用于定位程序P的某個(gè)需求有關(guān)的代碼部分。

（3）分解切片技術(shù)（Decomposition Slicing）。它是一種以把程序分解為不同模塊為目的的切片技術(shù)。分解切片是由一組關(guān)注某一變量的程序切片構(gòu)成的集合，可以捕獲程序中對(duì)某一變量的所有計(jì)算。分解切片不依賴于語(yǔ)句在程序中的位置，構(gòu)成分解切片的程序切片按照一定的規(guī)則排列成網(wǎng)格（Lattice），通過(guò)使用這種網(wǎng)格來(lái)實(shí)現(xiàn)對(duì)程序的分解。分解切片技術(shù)適用于回歸測(cè)試方面。

（4）條件切片（Conditioned Slicing）。Confora等人提出的條件切片技術(shù)通過(guò)增加一個(gè)條件擴(kuò)展了傳統(tǒng)的靜態(tài)切片準(zhǔn)則[5]，這個(gè)條件對(duì)應(yīng)著程序的某個(gè)或某些初始狀態(tài)。在進(jìn)行切片算法時(shí)，只有滿足該切片條件的那些輸入才會(huì)被分析。條件切片技術(shù)主要用于程序理解和軟件重用方面。 

（5）無(wú)定型切片技術(shù)（Amorphous Slicing）。該技術(shù)施加更廣泛的切片準(zhǔn)則，在簡(jiǎn)化源程序的過(guò)程中充分利用傳統(tǒng)切片技術(shù)保留源程序語(yǔ)義映射的簡(jiǎn)化功能。無(wú)定型切片的特點(diǎn)使其更適合程序理解領(lǐng)域，而傳統(tǒng)的切片技術(shù)則更多地應(yīng)用在調(diào)試領(lǐng)域。 

3程序切片技術(shù)在軟件測(cè)試中的應(yīng)用

基于程序切片的軟件測(cè)試是一種以程序或程序和需求相結(jié)合為基礎(chǔ)的測(cè)試，它根據(jù)程序的不同切片來(lái)縮小軟件的測(cè)試范圍，并提高軟件測(cè)試的效率。同時(shí)由于程序切片考慮程序存在的各種依賴關(guān)系（不僅僅是數(shù)據(jù)依賴和控制依賴），使得測(cè)試的準(zhǔn)確性得到提高。因?yàn)槿魏我粋€(gè)程序都可以和一組程序切片的并集等價(jià)，所以測(cè)試每個(gè)切片實(shí)際就是測(cè)試了整個(gè)程序，從而保證了測(cè)試的充分性。軟件測(cè)試中，測(cè)試數(shù)據(jù)生成是至關(guān)重要的一步。引入切片技術(shù)的目的是，計(jì)算程序在某一具體輸入下興趣點(diǎn)處變量的當(dāng)前值，以輔助測(cè)試數(shù)據(jù)的生成，提高測(cè)試數(shù)據(jù)的生成效率。

3．1基于切片技術(shù)的測(cè)試數(shù)據(jù)自動(dòng)生成

將程序切片技術(shù)應(yīng)用到軟件測(cè)試數(shù)據(jù)生成中，只要重點(diǎn)關(guān)注程序中與指定路徑上興趣點(diǎn)相關(guān)的那部分語(yǔ)句，即可有效提高基于路徑的測(cè)試數(shù)據(jù)生成效率。

基于程序切片的軟件測(cè)試數(shù)據(jù)生成系統(tǒng)主要由預(yù)處理器、程序切片生成器、測(cè)試數(shù)據(jù)生成器三部分組成，如圖3所示。

（1）預(yù)處理器。它對(duì)源程序進(jìn)行預(yù)處理，包括標(biāo)記語(yǔ)句、分析程序數(shù)據(jù)流信息、記錄變量的定義—引用屬性、確定語(yǔ)句間的支配關(guān)系等。

（2）程序切片生成器。它結(jié)合初始輸入(可手工或隨機(jī)生成)，根據(jù)程序指定執(zhí)行路徑，計(jì)算源程序各興趣點(diǎn)（主要是謂詞節(jié)點(diǎn)）處的程序切片。

（3）測(cè)試數(shù)據(jù)生成器。它比較程序?qū)嶋H執(zhí)行路徑與指定路徑的差異，從程序切片生成器產(chǎn)生的切片集合中選出該路徑上興趣點(diǎn)處的切片s；在測(cè)試數(shù)據(jù)生成器中按照一定規(guī)則調(diào)整程序輸入，并在新的程序輸入上執(zhí)行切片s，直到該興趣點(diǎn)滿足路徑要求。

該過(guò)程的處理算法主要有分支函數(shù)最小化、松弛迭代法、遺傳算法等。

Neelam Gupta等人于1998年提出了迭代松弛法自動(dòng)生成測(cè)試數(shù)據(jù)[6]。該方法采用程序切片思想，從定義域中任意選擇一組輸入x，通過(guò)靜態(tài)/動(dòng)態(tài)數(shù)據(jù)流分析確定指定路徑上的各分支謂詞函數(shù)對(duì)于輸入變量的依賴關(guān)系（即使在輸入x下該路徑不經(jīng)過(guò)），構(gòu)造謂詞片和動(dòng)態(tài)切片，建立這些謂詞函數(shù)關(guān)于當(dāng)前輸入的線性算術(shù)表示；然后建立輸入變量的增量線性約束系統(tǒng)，進(jìn)而建立輸入變量的增量線性方程系統(tǒng)，求解方程后得到關(guān)于指定路徑的測(cè)試數(shù)據(jù)。

Gupta提出的謂詞片是從路徑上的輸入語(yǔ)句和賦值語(yǔ)句靜態(tài)計(jì)算得到的。它既不是傳統(tǒng)意義上的靜態(tài)切片，也不是動(dòng)態(tài)切片，而是面向路徑的靜態(tài)切片。指定路徑P上的謂詞節(jié)點(diǎn)s的謂詞片Slice(s，P)是路徑P上的s謂詞語(yǔ)句之前的s所數(shù)據(jù)依賴的（包括直接和間接數(shù)據(jù)依賴的輸入變量），僅由輸入語(yǔ)句和賦值語(yǔ)句組成的程序片。通過(guò)引入謂詞片，無(wú)須考慮其他分支謂詞的計(jì)算結(jié)果即可計(jì)算路徑P上的每個(gè)分支謂詞的結(jié)果。根據(jù)輸入x，通過(guò)執(zhí)行謂詞片Slice(s，P)的語(yǔ)句，并從動(dòng)態(tài)數(shù)據(jù)依賴圖上提取動(dòng)態(tài)切片，確定謂詞節(jié)點(diǎn)的輸入變量依賴集， Gupta等人采用均差作為謂詞函數(shù)F關(guān)于輸入變量導(dǎo)數(shù)的近似，得到謂詞函數(shù)F關(guān)于輸入x的線性算術(shù)表示。

同時(shí)引入謂詞殘量，表示根據(jù)輸入x，謂詞片執(zhí)行之后計(jì)算相應(yīng)謂詞函數(shù)F所得之值。該謂詞殘量用來(lái)指示為使分支謂詞得到滿足，謂詞函數(shù)允許改變的范圍。對(duì)路徑P上的每個(gè)謂詞函數(shù)，迭代松弛法利用上面求得的線性算術(shù)表示和相應(yīng)的謂詞殘量共同生成一個(gè)關(guān)于程序輸入的增量線性約束。

指定路徑P上的各分支謂詞函數(shù)關(guān)于當(dāng)前輸入x的增量線性約束表示一切構(gòu)成了線性約束方程組，利用迭代松弛法求解。求解后得到各輸入變量的增量，從而獲得一組新輸入。如果路徑P上的謂詞函數(shù)都是輸入變量的線性函數(shù)，并且所有輸入變量均無(wú)整數(shù)限制時(shí)，該方法迭代一次后，或者找到P的解，或者保證P不可行。當(dāng)謂詞函數(shù)中含有輸入變量的非線性函數(shù)時(shí)，該方法可能需要迭代多次。該方法允許變量的數(shù)據(jù)類型為整數(shù)類型、實(shí)數(shù)類型。

文獻(xiàn)[7]提出了一種基于謂詞切片的字符串測(cè)試數(shù)據(jù)自動(dòng)生成方法。對(duì)指定路徑P上給定的字符串謂詞以相應(yīng)的動(dòng)態(tài)切片標(biāo)準(zhǔn)為準(zhǔn)則，將該路徑上與給定謂詞有關(guān)的語(yǔ)句以及謂詞抽取出來(lái)，形成關(guān)于輸入變量的謂詞切片；對(duì)任意輸入，通過(guò)執(zhí)行該謂詞切片，獲取謂詞中變量的當(dāng)前值，進(jìn)而對(duì)謂詞變量中的每一字符，構(gòu)造其線性分支函數(shù)，進(jìn)行分支函數(shù)最小化，動(dòng)態(tài)生成給定字符串謂詞邊界的ON－OFF測(cè)試點(diǎn)。

文獻(xiàn)[8]提出了一種基于前向分析的動(dòng)態(tài)切片測(cè)試數(shù)據(jù)生成方法。首先對(duì)程序細(xì)化分塊，以塊之間的支配關(guān)系來(lái)表示塊與塊之間的嵌套包含關(guān)系。該方法以Korel提出的程序前向動(dòng)態(tài)切片算法為基礎(chǔ)，并結(jié)合塊與塊之間的支配關(guān)系計(jì)算各節(jié)點(diǎn)的動(dòng)態(tài)切片；然后調(diào)整輸入，使各分支節(jié)點(diǎn)的執(zhí)行條件得到滿足。

V. M. Vedula等人將程序切片思想擴(kuò)展到硬件設(shè)計(jì)語(yǔ)言Verilog，并對(duì)硬件進(jìn)行分層自動(dòng)測(cè)試[9]。一般而言，用Verilog描述的數(shù)字系統(tǒng)都是由多個(gè)模塊分層組成；每個(gè)模塊是一個(gè)不中斷的程序，由若干過(guò)程組成，這些過(guò)程之間通過(guò)一些共享信號(hào)進(jìn)行通信。Vedula等人首先將每個(gè)待測(cè)模塊M1視為獨(dú)立的部分，而將硬件設(shè)計(jì)的其他部分均抽象為一個(gè)環(huán)境模塊M1，構(gòu)造每個(gè)待測(cè)模塊興趣點(diǎn)處的約束切片：M1的約束切片是一個(gè)可執(zhí)行的M1的子程序，采取后向切片算法構(gòu)造M1的輸入信號(hào)的約束切片，前向切片算法構(gòu)造輸出信號(hào)的約束切片。然后根據(jù)約束切片產(chǎn)生每個(gè)待測(cè)模塊的檢錯(cuò)測(cè)試集。

3．2程序切片技術(shù)在錯(cuò)誤定位中的應(yīng)用

軟件測(cè)試中，錯(cuò)誤定位是一個(gè)非常復(fù)雜而費(fèi)時(shí)的過(guò)程，W. Eric Wong等人利用測(cè)試用例驅(qū)動(dòng)的可執(zhí)行動(dòng)態(tài)切片和塊之間的數(shù)據(jù)依賴關(guān)系，高效準(zhǔn)確地在小范圍的代碼內(nèi)對(duì)程序進(jìn)行錯(cuò)誤定位[10]。對(duì)于某個(gè)需求，有一組測(cè)試集，某些測(cè)試用例執(zhí)行的結(jié)果正確，某些錯(cuò)誤。基于每個(gè)測(cè)試用例，進(jìn)行動(dòng)態(tài)切片。Wong認(rèn)為，如果該代碼出現(xiàn)在成功切片中的次數(shù)越頻繁，越不可能是錯(cuò)誤代碼。在此先驗(yàn)下，采取兩階段逐步擴(kuò)大可疑代碼段的方法，即精練法和擴(kuò)展法。

3．3程序切片技術(shù)在回歸測(cè)試中的應(yīng)用

軟件測(cè)試從本質(zhì)上來(lái)說(shuō)是發(fā)現(xiàn)程序錯(cuò)誤的過(guò)程，即一旦找到錯(cuò)誤就進(jìn)行修改。另外，軟件維護(hù)過(guò)程中，由于功能的增加或改變，也需要對(duì)源程序進(jìn)行修改。對(duì)程序的任何修改都可能引入新的錯(cuò)誤，因此就需要進(jìn)行回歸測(cè)試。按照傳統(tǒng)的測(cè)試方法，必須對(duì)整個(gè)程序進(jìn)行重新測(cè)試。如果對(duì)軟件僅作小的改動(dòng)，而要對(duì)它重新測(cè)試則既費(fèi)時(shí)費(fèi)錢，效率又極低。如果將切片技術(shù)應(yīng)用回歸測(cè)試中，解決的方法就會(huì)經(jīng)濟(jì)方便得多。

方法一：程序有若干輸出，如果某個(gè)輸出變量出現(xiàn)錯(cuò)誤，使用分解切片技術(shù)，那么關(guān)于該變量的所有計(jì)算組成一個(gè)模塊，維護(hù)人員可以直觀地判斷一個(gè)模塊中哪些語(yǔ)句和變量可以被安全地修改，即這種修改不會(huì)擴(kuò)散到其他模塊中；哪些語(yǔ)句不能被隨意修改。K.B.Gallagher等人還給出了一些用于禁止那些會(huì)影響到其他模塊的修改原則。這樣，維護(hù)者可以在一個(gè)模塊中測(cè)試對(duì)語(yǔ)句或變量所作的修改，而不必?fù)?dān)心這種修改會(huì)影響到其他部分。

方法二：在回歸測(cè)試中，為了找到這種修改可能影響到的語(yǔ)句，首先找到新舊版本的不同之處，以及兩者的切片與依賴圖不同之處（無(wú)須考慮那些具有相同切片的節(jié)點(diǎn)，這些節(jié)點(diǎn)在新舊版本中的作用不變），標(biāo)記為影響節(jié)點(diǎn)；然后計(jì)算其后向切片和前向切片，并取兩者的并集進(jìn)行測(cè)試。

這樣極大地縮小了測(cè)試的范圍，不必對(duì)源程序進(jìn)行分析。

3．4面向?qū)ο笄衅夹g(shù)在測(cè)試中的應(yīng)用

李必信等人從程序切片著手，根據(jù)測(cè)試人員的需要對(duì)源程序進(jìn)行分層切片，把對(duì)整個(gè)程序的測(cè)試按照一定的規(guī)則轉(zhuǎn)換為只對(duì)程序切片進(jìn)行測(cè)試[11]。

他們對(duì)Java源程序按數(shù)據(jù)級(jí)、方法級(jí)（過(guò)程級(jí)）、對(duì)象類級(jí)、類層次結(jié)構(gòu)等進(jìn)行分層：首先對(duì)源程序進(jìn)行分層，抽象出分層切片模型，并確定層次之間的各種依賴關(guān)系和流關(guān)系；然后在不同層次上進(jìn)行數(shù)據(jù)流和控制流以及依賴關(guān)系分析建立各種流圖和依賴關(guān)系圖，從頂層出發(fā)利用切片算法（兩階段圖形可達(dá)性算法）分別計(jì)算各個(gè)層次不同粒度的切片，切片算法在層次之間移動(dòng)時(shí)采用逐步求精的算法。利用分層切片算法結(jié)合各種切片準(zhǔn)則計(jì)算各個(gè)層次的切片，以便確定引起錯(cuò)誤的根源、錯(cuò)誤的影響范圍并進(jìn)行回歸測(cè)試。

3．5利用切片進(jìn)行測(cè)試覆蓋分析

白盒測(cè)試中一個(gè)重要的問(wèn)題是測(cè)試進(jìn)行到什么程度時(shí)結(jié)束。這就需要有一定的覆蓋準(zhǔn)則。常用的覆蓋測(cè)試的方法有語(yǔ)句覆蓋、分支覆蓋、條件覆蓋、判定—條件覆蓋以及路徑覆蓋。一種可能的覆蓋標(biāo)準(zhǔn)是語(yǔ)句覆蓋百分之百，分支覆蓋百分之八十五。

陳振強(qiáng)等人運(yùn)用切片技術(shù)在保持語(yǔ)義的情況下對(duì)源程序進(jìn)行精簡(jiǎn)，即在任何輸入下，兩者的輸出始終保持一致。將一個(gè)大系統(tǒng)分解為若干子系統(tǒng)，再進(jìn)一步通過(guò)部分切片技術(shù)過(guò)濾掉不感興趣的程序部分，對(duì)源程序的測(cè)試覆蓋則由各子系統(tǒng)的覆蓋情況合成[12]。該算法的基本思想是，在對(duì)子系統(tǒng)進(jìn)行測(cè)試覆蓋分析時(shí)，陳振強(qiáng)等人提出一種增長(zhǎng)模式，層次從低到高為語(yǔ)句覆蓋、分支覆蓋和路徑覆蓋；分別賦予不同的級(jí)別，高層的覆蓋情況由低層的覆蓋情況和級(jí)差合成。同時(shí)考慮一定的數(shù)據(jù)流覆蓋程度，對(duì)重要的變量賦予高的權(quán)值，進(jìn)行重點(diǎn)測(cè)試。該方法得到的覆蓋程度一般比源程序的要高。

3．6利用切片進(jìn)行測(cè)試用例集約簡(jiǎn)

測(cè)試用例集約簡(jiǎn)技術(shù)就是從大量的輸入數(shù)據(jù)中精心挑選出少數(shù)有代表性的測(cè)試數(shù)據(jù)，使得采用這些測(cè)試數(shù)據(jù)即能達(dá)到最佳的測(cè)試效果，高效地把隱藏的故障揭露出來(lái)。目前，關(guān)于測(cè)試用例表生成的理論研究的論文還不是很多。

如果通過(guò)切片就可以確定數(shù)據(jù)間的依賴關(guān)系，得到各輸出變量所依賴的輸入變量集，那么在進(jìn)行組合測(cè)試時(shí)也就能夠縮小組合范圍，從而極大地縮減測(cè)試用例的數(shù)量。同時(shí)將一個(gè)大的程序劃分成若干個(gè)小的子系統(tǒng)，可以更方便、更精確地設(shè)計(jì)測(cè)試用例。

通過(guò)切片分析，如果一個(gè)測(cè)試用例當(dāng)且僅當(dāng)能夠改善覆蓋程度，則可以加進(jìn)測(cè)試集中，否則可以認(rèn)為是多余的。如果同時(shí)引入切片技術(shù)刪除多余的無(wú)用代碼，還可以查找出更多的冗余測(cè)試數(shù)據(jù)。

3．7基于切片的變量完整性測(cè)試

由于軟件測(cè)試用例的輸出部分很難確定，通過(guò)測(cè)試變量自身的定義域和變量間的一致性約束關(guān)系，只需要確定輸出值的范圍而不用知道其確切的值，就可以提高錯(cuò)誤檢測(cè)的效率。 同時(shí)，檢測(cè)的范圍不局限于程序最后的輸出結(jié)果，而是散布在程序中的各個(gè)有意義的變量，如關(guān)鍵變量、全局變量、局部變量和數(shù)據(jù)結(jié)構(gòu)變量以及函數(shù)的返回值或傳出參數(shù)等的定值點(diǎn)等。文獻(xiàn)[13] 引入變量依賴關(guān)系圖來(lái)進(jìn)行程序切片，并通過(guò)插樁來(lái)檢測(cè)這些重要的變量定值點(diǎn)的定義域和變量間的一致性約束關(guān)系，正如調(diào)試過(guò)程中設(shè)置斷點(diǎn)觀察的那些變量，使得檢測(cè)錯(cuò)誤更加精準(zhǔn)。

4結(jié)束語(yǔ)

目前對(duì)程序切片技術(shù)的研究主要集中在靜態(tài)切片方面，而在程序調(diào)試、測(cè)試領(lǐng)域大多采用動(dòng)態(tài)切片技術(shù)。如何快速、有效、準(zhǔn)確地計(jì)算動(dòng)態(tài)切片，如何將切片技術(shù)更好地應(yīng)用在軟件測(cè)試方面是本文關(guān)注的重點(diǎn)。測(cè)試用例的選擇和自動(dòng)生成技術(shù)是軟件測(cè)試的一個(gè)重要研究領(lǐng)域，無(wú)論對(duì)白盒測(cè)試還是黑盒測(cè)試都起著非常關(guān)鍵的作用。將程序切片技術(shù)引入今后的研究，采用切片技術(shù)將程序和需求相結(jié)合，用以輔助生成最優(yōu)的測(cè)試用例集；改進(jìn)Gupta算法，使得對(duì)輸入的非線性表示的謂詞函數(shù)也能自動(dòng)生成測(cè)試數(shù)據(jù)；減少錯(cuò)誤定位和回歸測(cè)試的工作量。

參考文獻(xiàn)：

［1］WEISER M.Program slicing: formal，psychological and practical investigations of an automatic program abstraction method[D]．Michigan: University of Michigan， 1979.

[2]WEISER M．Program slicing[J]．IEEE Transactions on Software Engineering， 1984， 210(4):352－357.[3]KOREL B， LASKI J．Dynamic program slicing [J].Information Processing Letters，1988，29(3):155－163.

[4]HALL R J.Automatic extraction of executable program subsets by simultaneous program slicing [J].Journal of Automated Software Engineering，1995，2(1):33－53.

[5]CANFORA G， CIMITILE A， LUCIA A De．Conditioned program slicing[J].Information and Software Technology，1998，40(11/12):595－607.

[6]GUPTA N， MATHUR A P， SOFFA M L．Automated test data generation using an iterative relaxation method:proc.of the 6th ACM SIG－SOFT International Symposium on the Foundations of Software Engineering(FSE－6 SIGSOFT’98)[C]. Orlando:[s.n.]，1998:231－244.

[7]趙瑞蓮.軟件測(cè)試方法研究[D].北京：中國(guó)科學(xué)院，2001：83－88.

[8]王雪蓮，趙瑞蓮，李立健.一種用于測(cè)試數(shù)據(jù)生成的動(dòng)態(tài)程序切片算法[J].計(jì)算機(jī)應(yīng)用，2005，25(6) :1445－1450.

[9]VIVEKANANDA M， VEDULA，JACOB A，et al.Program slicing for hierarchical test generation:proceedings of the 20th IEEE VLSI Test Symposium (VTS’02) [C].[S.l.]:[s.n.]，2002.

[10]WONG W E， QI Yu．An execution slice and inter－block data depen－dency－based approach for fault localization:proceedings of the 11th Asia－Pacific Software Engineering Conference (APSEC’04)[C].[S.l.]:[s.n.]， 2004.

[11]李必信.程序切片技術(shù)及其在面向?qū)ο筌浖亢蛙浖y(cè)試中的應(yīng)用[D]．南京：南京大學(xué)，2000：6－18.

[12]CHEN Zhenqiang，XU Baowen， YANG Hongji，et al.Test coverage analysis based on program slicing:IRI’03[C].Las Vegas:[s.n.]，2003:559－565.

[13]黃光燕，李曉維．軟件的變量完整性測(cè)試方法[J] ．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16(11):1584－1589.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”