一種新的程序變體測試方法
2008-01-01 00:00:00蔡國永錢俊彥
計算機應用研究 2008年5期
摘要：在對程序分片技術研究的基礎上，提出一種新的片變體測試方法。通過實例說明，該方法能更有效地提高變體測試的準確性及測試效率。
關鍵詞：變體測試；程序分片；片變體測試；測試指標
中圖分類號：TP311 文獻標志碼：A
文章編號：1001-3695(2008)05-1393-03
高質量的軟件（程序）離不開高質量的測試。為了保證測試的質量及提供一種度量測試用例好壞的指標，人們提出了一種基于缺陷的測試方法（fault－based testing）——變體測試。區別于別的測試方法，變體測試根據一定的準則（變體算子）在程序中引入bug來判斷測試用例集的好壞（是否充分）。對于現實中的一般程序，由于其整個輸入集一般都趨于無窮大或大到無法控制的范圍，只能根據一定的原則選取其中的一個子集作為測試用例集。準則的意義就在于提供一種量化測試等級的指標。通過等級越高的測試，程序的可信度就越高。
本文利用一種有效的程序分析技術，即程序分片對傳統的變體測試技術進行分析，提出基于程序片的變體測試指標，該指標涵蓋了傳統變體測試指標。所謂涵蓋就是一定存在這樣的情況，永遠有缺陷會在測試的一個層次上被發現，并能夠在測試的下層上逃避檢測[1]。另外給出了基于該指標的一般性測試方法——結合分片的片變體測試方法。
1程序變體與分片
1．1變體測試
變體測試思想始于20世紀70年代末[2]，基本思想是：對于一個待測程序P，假設給定的測試用例集T足夠好（充分）的話，應該能測試出P中所有的缺陷。基于以上假設，人為地在通過測試后的程序P中引入缺陷（稱引入缺陷的程序為源程序的變體），再用原測試用例集T對所有的變體進行測試。當變體中引入的缺陷被檢測出來時，則稱變體P被消滅。如果所有的變體都能被消滅，那么就認為測試用例集T是足夠好（充分）的，通過T測試的程序P也是可信賴的。如果還存在變體沒有被消滅，則認為測試用例集T是不夠充分的，通過T測試的程序P也是不可信賴的。變體測試的基本流程如圖1所示。
程序缺陷是通過修改源程序部分代碼的形式引入的。這種修改遵循一定的標準算子，稱為變體算子，如修改算術運算符、修改邏輯運算符、修改變量等操作算子。這種引入缺陷的方法可能會造成等價變體問題，即修改后的程序和源程序是功能等價的（也就是對于任意相同的輸入，它們的輸出是一樣的），所以在進行變體測試時只要求非等價變體被消滅。就如何識別等價變體這一問題，人們已進行了很多研究[3]，具體的方法本文不進行討論。
為進一步討論的需要，先給出本文的一些表示符號。對于任一個程序P，用P′表示程序P的一個變體；P表示P的所有變體集合；P.t表示P對于輸入t的輸出； fp(t)表示P實際要完成的函數功能；D為程序的整個輸入域。
定義1測試用例集T滿足變體測試指標iff P′.P′∈P→(t∈T. P′.t≠fp(t))∨(t∈D.P′.t＝P.t)。當程序P通過了滿足以上指標的T測試，則稱P通過了變體測試。
1．2程序分片
程序分片是一種有效的程序分析技術，它根據給定的分片準則從源程序中提取出所需部分進行分析。最早的程序分片概念由Weiser提出[4]。 Weiser定義的程序分片是一個可執行的程序，它是通過從源程序中移去零條或多條語句來構造的。 原始的程序分片定義如下：
定義2對于某一語句s和某一變量v，程序p關于分片準則〈s， v〉的程序分片是可能影響語句s處變量v值的所有語句的集合。
目前比較流行的分片技術大多是借助于系統依賴圖（SDG）來實現[5]。其主要思路是先對目標程序構造SDG來表示其內部的依賴關系，然后通過回溯算法（也稱為節點反向可達性算法）來計算分片。由于本文第3章討論的需要，簡要介紹一下基于SDG的分片技術。
SDG是由過程間的控制和數據依賴邊相連接的過程依賴圖(PDG)[5]的集合。一個PDG表示程序中的單個過程，它是一個有向圖，其節點分為表示賦值語句或謂詞的節點、表示過程輸入和輸出的節點及表示方法調用的節點；邊表示過程各部分間的依賴關系，依賴關系有控制依賴和數據依賴兩種。節點間可以有多種邊。如果圖中有一條控制依賴邊〈v1，v2〉，當且僅當滿足下列條件之一：a)v1是初始節點，且v2沒有嵌套在條件或循環中；b)v1是謂詞，v2直接嵌套在謂詞v1的條件或循環中。如果圖中有一條數據依賴邊〈v1，v2〉，當且僅當同時滿足以下三個條件：a)v1定義了某個變量x；b)v2使用了變量x；c)v1和v2間有一條可執行的路徑且沒有對x重新定義。
為描述過程間參數傳遞，SDG中對于每個過程起始節點都有相應的形參節點，由起始節點指向形參節點的控制依賴邊與起始節點相連接。對于每一個過程調用節點都有相應的實參節點，通過過程調用節點指向實參節點的控制依賴邊與相應過程調用節點相連接。通過用過程調用邊來連接過程調用節點和相應的過程起始節點，用參數傳遞邊來連接相應的實參和形參的方法連接各個PDG來構造SDG。對例程P構造SDG，如圖2所示。
為了描述的一般性，本文中的程序用偽代碼來表示。其中規定輸入為input(〈變量列表〉)；輸出為output(〈變量列表〉)；數據聲明為dim〈變量〉As〈類型〉。程序P中不存在方法調用，所以P的PDG就是P的SDG。其中邊〈1，3〉、〈2，3〉、〈3，4〉、〈3，5〉、〈4，6〉、〈5，6〉、〈6，7〉為數據依賴邊。假設分片準則為〈5，e〉，通過回溯算法可以找出所有影響語句5處變量值e的節點，即可得到相應的分片，如圖2中陰影節點。
2基于程序片的變體測試指標
一個程序P上的所有不重復的分片是一個有限集，用S來表示，S={S0，S1，…，Sn}。其中規定S0＝P。前面提到，變體測試是通過修改程序中的代碼來產生變體的。顯然，在通過修改程序P中的部分代碼來產生程序變體的同時，也產生了包含該部分代碼的程序片的變體，稱之為片變體。對于程序P的變體集合P，存在一個片變體的集合，用S表示。S由P中所有變體所對應的程序片變體組成。本文的想法是：如果測試用例集T足夠充分的話，那么片變體集合中的所有非等價片變體都應該被T消滅，而并不只是程序變體集合中的非等價變體被T消滅。
基于上述思想提出一種比傳統變體測試指標更加嚴格的指標——基于程序片的變體測試指標。
定義3測試用例集T滿足基于程序片的變體測試指標iffS′.S′∈S→(t∈T.S′.t≠Fs(t))∨(t∈D.S′.t＝S.t)。
因為P∈S，所以PS。再根據定義1和3可以得出，測試用例集T滿足基于程序片的變體測試指標→T滿足變體測試指標。實際測試中確實存在這樣一種情況，程序中的bug在傳統的變體測試中逃避了測試而在結合分片的變體測試中被發現（第4章的例子）。所以基于程序片的變體測試指標涵蓋了傳統變體測試指標，比傳統變體測試方法具有更強的發現錯誤的能力。
3基于片變體的測試技術
測試指標只提供了一種度量測試的標準，并沒有給出滿足該指標的具體測試技術方法。本章將給出滿足以上基于程序片的變體測試指標的一般性測試技術方法——結合分片的變體測試技術及一些相關性質的證明。
由定義3可以得出，要知道T是否滿足基于程序片的變體測試指標，就要確定T是否能消滅所有的非等價程序片變體。但是通過研究發現，如果用T對每一個非等價變體進行測試再判斷結果的話往往開銷太大，而且存在重復性的測試。現在的想法是，是否存在一個S的子集S*′滿足以下條件：(S′.S′∈S*′→(t∈T.S′.t≠Fs(t))∨(t∈D.S′.t＝S.t))→(S′.S′∈S→(t∈T.S′.t≠Fs(t))∨(t∈D.S′.t＝S.t))。如果存在的話，則只需要對子集S*′中的片變體進行測試再對結果進行比較就可以了。
下面介紹一種借助于SDG來確定滿足這一條件的子集的方法，稱之為片變體生成算法。在SDG中，從一個語句節點出發通過回溯算法即可確定一分片。所以要確定一個分片本質上就是要確定一個語句節點。
片變體生成算法具體步驟如下：
a)對于程序P，構造其對應的SDG。
b)對于P的每一個變體，執行以下操作：
(a)在SDG中標志出被修改的節點。
(b)從已標志的節點出發，通過正向搜索標志出所有正向可達節點。
(c)去掉已標志節點n的標志當且僅當存在一個節點m滿足：節點m被標志；節點m是節點n的后續節點并且對于節點m來說，除了節點n之外不存在其他已標志的前趨節點。
(d)從所有剩下的已標志節點出發通過回溯算法計算得到分片。
c)把以上所有計算得到的分片組成一個集合，該集合即為要求的片變體子集。
以例程P為例具體解釋一下該算法。算法第a)步中生成的SDG如圖2所示；設第b)步取的一個變體為修改P的第三行的語句c=a+b;即修改的節點為圖2中的節點3，則第(a)步標志節點3；第(b)步標志從節點3正向可達的節點，即節點4~7；第(c)步去掉那些滿足條件的被標志的節點（即節點3和6）的標志，因此剩下的標志節點還有：4、5、7；第(d)步通過從剩下的標志節點出發，分別進行反向回溯，從而可以得到三個片變體，即節點4對應的片變體{1， 2， 3， 4}，節點5對應的片變體{1，2，3，5}和節點7對應的片變體{1，2，3，4，5，6，7}。這相當于去掉了節點3和6對應的片變體，也即這兩個片變體是不必要再測試的。下面將證明這一結論。
證明分兩步。首先證明步驟(a)和(b)能標志出所有片變體對應的語句節點；其次要證明步驟(c)去除的語句節點對應的片變體是沒有必要測試的。
a)由于借助于SDG的分片方法是從分片所對應的一個節點n出發，提取出所有反向可達的節點來得到分片的，要知道該分片有沒有包括被修改的代碼節點，只要從被修改的節點出發，判斷該分片所對應的節點n有沒有在正向可達路徑上即可。所以算法中步驟(a)(b)所標志出的節點是對應于該程序變體的所有片變體對應的節點，也就是說從這些節點出發，通過回溯算法得到的分片集合為該程序變體對應的片變體集合。
b)要證明步驟(c)去除的語句節點對應的片變體沒有必要測試，只要證明所有剩下的節點對應的非等價片變體被T消滅(所有去除的語句節點對應的非等價片變體也能被T消滅。現在假設被去除的語句節點n節點不能被T消滅，由步驟(c)知道存在一個節點m，只有n這一個被標志的前趨。也就是說節點m對應的片Sm包含了節點n對應的片Sn， 且所有的代碼改動部分都在片Sn中。由假設知道，對于T中的所有測試用例，節點n對應的片變體的輸出與原來的片一樣，所以節點m對應的片變體的輸出也應該與原來的片一樣。這樣可以得出：存在去除的語句節點對應的非等價片變體不能被T消滅→存在剩下的節點對應的非等價片變體不能被T消滅。由逆否定律，證明結論成立。
在得到一個片變體子集后就可以開始結合分片的變體測試了。測試過程類似圖2，具體步驟說明如下：
a)用測試用例集T對程序P進行測試。如果P沒有通過T的測試，那么P沒有通過變體測試；如果P通過T測試，執行第b)步。
b)根據一定的準則（變體算子）修改P中的代碼，產生程序變體集合P，再用片變體生成算法得到一個片變體子集S*′，接著執行第c)步。
c)用測試用例集T對片變體集合S*′中的每一個非等價片變體進行測試。如果S*′中的非等價變體全部被消滅，那么P通過變體測試；如果存在非等價變體沒有被消滅，那么在T中添加測試用例，再重復第a)步。
4案例測試及比較研究
下面利用一個簡單的例子對上面提到的例程P分別用傳統變體測試方法和結合分片的變體測試方法進行測試，并比較所得結果。
設例程P要實現以下函數的功能：f(a，b)= (a-b+12)×(4(a-b)×(a-b)-16(a-b)+20)。其中a，b∈Z。
程序的錯誤出現在第5行，正確的寫法應該是：e=4×c×c-16×c+20 。為了分析簡單，程序中并沒有謂詞語句，不過這并不影響結論的一般性。
1）用傳統的變體測試方法對P進行測試
首先要從整個輸入集中選取一個子集作為測試用例集。假定所選的測試用例集為T：{(3，1)， (3，3)}；其次選定一組變體算子，這里采用的變體算子是修改源程序中的算術運算符。按照圖1所示的變體測試的一般流程開始對P進行測試。
a)用測試用例集T對P進行測試，結果說明P通過了T的測試。
b)根據變體算子改變源程序生成變體，P中共有8個運算符，一共生成24個變體。本文用T對所有的變體進行測試，結果表明變體全部被消滅（因篇幅所限，這兩步的測試結果圖省略）。根據定義1，T達到了傳統的變體測試指標。P通過T的測試，所以說P通過了變體測試，即測試集是足夠充分的，但P中是存在有錯誤的。
2）用本文提出的結合分片的變體測試方法對P進行測試
為了比較，采用相同的測試用例集T和變體算子，按照結合分片的變體測試的一般步驟對P進行測試。
a)用測試用例集T對P進行測試，結果與前面一致，P通過了T測試。
b)與前面一樣根據變體算子改變源程序生成變體，再用片變體生成算法得到片變體集合S*′。由于篇幅關系，此文不詳細列出S*′中的元素。
c)用測試用例集T對片變體進行測試，結果如表1所示。可以發現存在片變體4沒有被消滅，也就是說T沒有達到基于程序片的變體測試指標。
例子的結果說明，P中的bug在傳統的變體測試中沒有被測試出來，而在結合分片的變體測試中被測試出來。就是說P中的bug在T只滿足傳統的變體測試指標的情況下逃避了檢測，而在基于片變體的測試中被捕獲。
5結束語
傳統的變體測試方法還存在不足。利用程序分片技術對傳統的變體測試進行分析改進，提出一種新的基于程序片的變體測試指標，該指標涵蓋了傳統變體測試指標；同時還給出了相應的結合分片的變體測試技術流程。與其他
所有的測試指標一樣，換取指標的代價往往就是增加測試過程中的開銷。所以如何以最小的代價換取最大的測試效果仍是測試研究工作的一個重點。對片變體測試方法也還有待進一步的分析，如片變體測試方法及其他測試方法的關系等。
參考文獻：
[1]JORGENSEN P C. Software Testing: a craftsman’s approach[M]. 2nd ed. Beijing: Publishing House of Electronic Industry， 2003.
[2]BUDD T， SAYWARD F. Users guide to the pilot mutation system[R]. New Haven: Yale University， 1977.
[3]OFFUTT A J， PAN Jie. Automatically detecting equivalent mutants and infeasible paths[J]. Journal of Software Testing， Verification Reliability， 1997，17(3):165－192.
[4]WEISER M. Program Slicing [J]. IEEE Trans on Software Engineering， 1984，16(5)：498-509.
[5]LIANG D， HARROLD M J. Slicing objects using system dependence graphs[C]//Proc of International Conference on Software Maintenance. Washington DC: IEEE Computer Society， 1998:358-367.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
