程序切片技術在軟件測試中的應用

摘要：基于程序切片的軟件測試是一種以程序或程序和需求相結合為基礎的測試，它根據程序的不同切片來縮小軟件的測試范圍、提高軟件測試的效率、輔助測試數據的自動生成等。同時由于程序切片不僅考慮了數據依賴和控制依賴，還考慮了程序存在的其他各種依賴關系，使得測試的準確性得到提高。詳細闡述了目前存在的各種切片技術及其應用領域，重點探討了目前切片技術在測試領域中的具體應用。

關鍵詞：程序切片；軟件測試；數據依賴；控制依賴；測試數據自動生成

中圖分類號：TP311文獻標志碼：A

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

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

1程序切片簡介

Weiser認為一個切片與人們在調試一個程序時所做的智力抽象相對應。他定義的程序P的切片S是一個可執行的程序，對某個興趣點s處的變量v而言（s，v稱為切片準則），S由程序P中可能影響s處變量v的值的所有語句構成。這個可執行部分相對于程序P在功能上是等效的[2]。他提出的切片算法是基于數據流分析的，通過遍歷控制流圖分析數據依賴和控制依賴關系，從源程序中移去零條或多條語句從而得到過程內的切片。

定義1設s是程序流圖CFG 中的任一節點，定義：

程序切片不僅與興趣點定義和使用的變量有關，還與影響該變量的值的語句和謂詞以及受該變量的值影響的語句和謂詞有關。程序切片過程中，采用合適的結構來表示語句間的依賴關系，尋找與興趣點具有直接或間接數據依賴和控制依賴的節點是生成切片的重點。切片算法基本過程為：首先尋找語句s的變量v所直接數據依賴或控制依賴的節點；然后尋找這些新節點所直接數據依賴或控制依賴的節點；一直重復下去，直到沒有新節點加進來為止；最后將這些節點按源程序的語句順序排列，即為程序P的關于語句s的切片S。

2程序切片分類

程序切片技術的發展經歷了從靜態到動態、從前向到后向、從單一過程到多個過程、從過程型程序到面向對象程序、從非分布式程序到分布式程序等幾個方面。

2．1靜態切片與動態切片

Weiser最初提出的程序切片概念就屬于靜態切片（Static Slicing）范疇。靜態切片是在編譯時間， 即程序尚未運行時進行切片；該技術對程序的輸入不作任何假設，所作的分析完全以程序的靜態信息為依據。因此靜態切片包含了所有與興趣點處變量相關的語句， 考慮了程序中所有可能的執行路徑。其缺點是：①容易包含不相關節點，具有很大的冗余性。主要是由于程序的執行路徑無法靜態判斷，尤其是數組和指針變量無法靜態確定。②使用該技術的工作量較大。因為要分析程序所有可能的執行軌跡，靜態切片技術一般用于程序理解與軟件維護方面。

實際應用中，人們往往更關注某一具體輸入下，程序實際執行時影響興趣點處某一變量值的那些語句。

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

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

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

2．3對象切片

自Weiser提出程序切片概念后，人們提出了許多用于過程型程序的切片方法，但這些方法并不適用于OO程序。因為OO編程語言提出了一些新的概念與特性，如類、對象、動態綁定、封裝、繼承、消息傳遞以及多態。所以面向對象程序切片不僅要考察語句和數據之間的依賴關系，還要考察各個類之間的關系。為了獲得更準確、更有效的程序切片，D Liang和M.J.Harrod提出了對象切片（ObjectSlicing）技術這一概念；他們的工作是通過擴展系統依賴圖實現的。目前對它的研究更多是側重于靜態切片這一部分，而且基本都是基于依賴圖的。李必信等人提出了一種逐步求精的基于OO程序的分層切片方法。

2．4其他切片技術

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

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

（3）分解切片技術（Decomposition Slicing）。它是一種以把程序分解為不同模塊為目的的切片技術。分解切片是由一組關注某一變量的程序切片構成的集合，可以捕獲程序中對某一變量的所有計算。分解切片不依賴于語句在程序中的位置，構成分解切片的程序切片按照一定的規則排列成網格（Lattice），通過使用這種網格來實現對程序的分解。分解切片技術適用于回歸測試方面。

（4）條件切片（Conditioned Slicing）。Confora等人提出的條件切片技術通過增加一個條件擴展了傳統的靜態切片準則[5]，這個條件對應著程序的某個或某些初始狀態。在進行切片算法時，只有滿足該切片條件的那些輸入才會被分析。條件切片技術主要用于程序理解和軟件重用方面。 

（5）無定型切片技術（Amorphous Slicing）。該技術施加更廣泛的切片準則，在簡化源程序的過程中充分利用傳統切片技術保留源程序語義映射的簡化功能。無定型切片的特點使其更適合程序理解領域，而傳統的切片技術則更多地應用在調試領域。 

3程序切片技術在軟件測試中的應用

基于程序切片的軟件測試是一種以程序或程序和需求相結合為基礎的測試，它根據程序的不同切片來縮小軟件的測試范圍，并提高軟件測試的效率。同時由于程序切片考慮程序存在的各種依賴關系（不僅僅是數據依賴和控制依賴），使得測試的準確性得到提高。因為任何一個程序都可以和一組程序切片的并集等價，所以測試每個切片實際就是測試了整個程序，從而保證了測試的充分性。軟件測試中，測試數據生成是至關重要的一步。引入切片技術的目的是，計算程序在某一具體輸入下興趣點處變量的當前值，以輔助測試數據的生成，提高測試數據的生成效率。

3．1基于切片技術的測試數據自動生成

將程序切片技術應用到軟件測試數據生成中，只要重點關注程序中與指定路徑上興趣點相關的那部分語句，即可有效提高基于路徑的測試數據生成效率。

基于程序切片的軟件測試數據生成系統主要由預處理器、程序切片生成器、測試數據生成器三部分組成，如圖3所示。

（1）預處理器。它對源程序進行預處理，包括標記語句、分析程序數據流信息、記錄變量的定義—引用屬性、確定語句間的支配關系等。

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

（3）測試數據生成器。它比較程序實際執行路徑與指定路徑的差異，從程序切片生成器產生的切片集合中選出該路徑上興趣點處的切片s；在測試數據生成器中按照一定規則調整程序輸入，并在新的程序輸入上執行切片s，直到該興趣點滿足路徑要求。

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

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

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

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

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

文獻[7]提出了一種基于謂詞切片的字符串測試數據自動生成方法。對指定路徑P上給定的字符串謂詞以相應的動態切片標準為準則，將該路徑上與給定謂詞有關的語句以及謂詞抽取出來，形成關于輸入變量的謂詞切片；對任意輸入，通過執行該謂詞切片，獲取謂詞中變量的當前值，進而對謂詞變量中的每一字符，構造其線性分支函數，進行分支函數最小化，動態生成給定字符串謂詞邊界的ON－OFF測試點。

文獻[8]提出了一種基于前向分析的動態切片測試數據生成方法。首先對程序細化分塊，以塊之間的支配關系來表示塊與塊之間的嵌套包含關系。該方法以Korel提出的程序前向動態切片算法為基礎，并結合塊與塊之間的支配關系計算各節點的動態切片；然后調整輸入，使各分支節點的執行條件得到滿足。

V. M. Vedula等人將程序切片思想擴展到硬件設計語言Verilog，并對硬件進行分層自動測試[9]。一般而言，用Verilog描述的數字系統都是由多個模塊分層組成；每個模塊是一個不中斷的程序，由若干過程組成，這些過程之間通過一些共享信號進行通信。Vedula等人首先將每個待測模塊M1視為獨立的部分，而將硬件設計的其他部分均抽象為一個環境模塊M1，構造每個待測模塊興趣點處的約束切片：M1的約束切片是一個可執行的M1的子程序，采取后向切片算法構造M1的輸入信號的約束切片，前向切片算法構造輸出信號的約束切片。然后根據約束切片產生每個待測模塊的檢錯測試集。

3．2程序切片技術在錯誤定位中的應用

軟件測試中，錯誤定位是一個非常復雜而費時的過程，W. Eric Wong等人利用測試用例驅動的可執行動態切片和塊之間的數據依賴關系，高效準確地在小范圍的代碼內對程序進行錯誤定位[10]。對于某個需求，有一組測試集，某些測試用例執行的結果正確，某些錯誤。基于每個測試用例，進行動態切片。Wong認為，如果該代碼出現在成功切片中的次數越頻繁，越不可能是錯誤代碼。在此先驗下，采取兩階段逐步擴大可疑代碼段的方法，即精練法和擴展法。

3．3程序切片技術在回歸測試中的應用

軟件測試從本質上來說是發現程序錯誤的過程，即一旦找到錯誤就進行修改。另外，軟件維護過程中，由于功能的增加或改變，也需要對源程序進行修改。對程序的任何修改都可能引入新的錯誤，因此就需要進行回歸測試。按照傳統的測試方法，必須對整個程序進行重新測試。如果對軟件僅作小的改動，而要對它重新測試則既費時費錢，效率又極低。如果將切片技術應用回歸測試中，解決的方法就會經濟方便得多。

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

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

這樣極大地縮小了測試的范圍，不必對源程序進行分析。

3．4面向對象切片技術在測試中的應用

李必信等人從程序切片著手，根據測試人員的需要對源程序進行分層切片，把對整個程序的測試按照一定的規則轉換為只對程序切片進行測試[11]。

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

3．5利用切片進行測試覆蓋分析

白盒測試中一個重要的問題是測試進行到什么程度時結束。這就需要有一定的覆蓋準則。常用的覆蓋測試的方法有語句覆蓋、分支覆蓋、條件覆蓋、判定—條件覆蓋以及路徑覆蓋。一種可能的覆蓋標準是語句覆蓋百分之百，分支覆蓋百分之八十五。

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

3．6利用切片進行測試用例集約簡

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

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

通過切片分析，如果一個測試用例當且僅當能夠改善覆蓋程度，則可以加進測試集中，否則可以認為是多余的。如果同時引入切片技術刪除多余的無用代碼，還可以查找出更多的冗余測試數據。

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

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

4結束語

目前對程序切片技術的研究主要集中在靜態切片方面，而在程序調試、測試領域大多采用動態切片技術。如何快速、有效、準確地計算動態切片，如何將切片技術更好地應用在軟件測試方面是本文關注的重點。測試用例的選擇和自動生成技術是軟件測試的一個重要研究領域，無論對白盒測試還是黑盒測試都起著非常關鍵的作用。將程序切片技術引入今后的研究，采用切片技術將程序和需求相結合，用以輔助生成最優的測試用例集；改進Gupta算法，使得對輸入的非線性表示的謂詞函數也能自動生成測試數據；減少錯誤定位和回歸測試的工作量。

參考文獻：

［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]趙瑞蓮.軟件測試方法研究[D].北京：中國科學院，2001：83－88.

[8]王雪蓮，趙瑞蓮，李立健.一種用于測試數據生成的動態程序切片算法[J].計算機應用，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]李必信.程序切片技術及其在面向對象軟件定量和軟件測試中的應用[D]．南京：南京大學，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]黃光燕，李曉維．軟件的變量完整性測試方法[J] ．計算機輔助設計與圖形學學報，2004，16(11):1584－1589.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”