測試用例最小化研究

摘要：給出了測試用例最小化問題的形式化描述，提出并實現了兩個新的用于用例最小化的算法。與現有其他最小化算法不同，這兩個算法在考慮了每個用例測試覆蓋度的同時，還考慮了用例的測試運行代價，目的是提高最小化效率。最后給出了對這兩個算法進行實例研究的實驗結果。結果表明，用例最小化技術能有效縮減回歸測試用例集的尺寸，大幅度降低回歸測試費用，提高最小化效率。

關鍵詞：回歸測試； 測試用例集； 測試用例最小化； 測試覆蓋率； 測試運行代價

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2007)07－0035－05

0引言

在漸進和快速迭代開發中，軟件新版本的連續發布使回歸測試更加頻繁。在每一次回歸測試中，不僅要確定修改是否達到了預期的目的，還要檢查修改是否損害了原有的正常功能；同時，需要補充新的測試用例以測試新的或被修改了的功能。這樣，一個回歸測試中必須解決測試用例集膨脹帶來的回歸測試成本問題。主要通過兩種途徑解決測試用例集膨脹帶來的測試代價問題，即測試用例最小化和測試選擇。測試用例最小化技術（Test－Suite Minimization Techniques），也叫測試用例縮減技術（Test－Suite Reduction Techniques）[1~7]，就是在原始用例集中，找到一個最小的測試用例子集，并能夠提供與原始測試用例集一樣的測試覆蓋率。測試用例選擇（Test－Suite Selection）就是從原始用例集中選擇出一個用例子集，能夠覆蓋所有的修改，但這種方法一般不能提供與原始測試用例集一樣的測試覆蓋[8~10]。

目前測試用例最小技術都基于兩個基本的假設：①每個測試用例在測試時，都有一定的測試覆蓋度，并且測試覆蓋度在程序的新版本中基本保持不變（本假設已經在文獻[11]中得到實例研究結果的支持）；②假設每個測試用例具有相同的測試運行代價（Test Execution Cost就是使用該用例測試程序時的運行代價），并且運行代價在程序的新版本中基本保持不變。基于以上假設，假定每個用例的運行代價相等，所以測試用例最小化算法就簡化為：找到一個用例數最小的用例集；同時在評價最小化技術的最小化能力時，往往也只考慮最小化后測試用例集(簡稱最小化用例集)的大小，而不考慮最小化對用例集運行代價的縮減。但是，首先，根據用例最小化技術的定義，測試用例最小化，目的是要最小化回歸測試的費用而不是單純地追求用例數的最小化，所以在做測試用例的選擇時，不僅要考慮該用例的測試覆蓋能力，還必須考慮該用例的測試運行代價；其次，在實際測試過程中，各個用例的運行代價肯定會有差別，如果簡單地假設各個用例的測試運行代價相等，勢必會影響最小化的效率。為了研究代價因素對最小化效率的影響，本文提出了兩個新的算法，基于測試覆蓋因素和測試運行因素，進行測試用例最小化，目的是找到一個測試運行代價最小的用例集，而不是用例數最少的用例集，真正提高最小化效率。為了評價算法的效率，筆者設計并實現了算法的原型，獲得了大量的實驗數據。實驗結果表明，提出的最小化技術能有效縮減測試用例集的大小，大幅度降低測試運行代價。為了驗證最小化算法，在考慮了運行代價后，最小化效率相對提高；同時實現了兩個相似的算法，稱之為簡單算法。與新算法唯一不同的地方就是這兩個簡單算法在最小化過程中，假設每個測試用例的運行代價是相等的。比較結果表明了在最小化算法中考慮運行代價的必要性。

1相關工作

1．1測試工具

隨著軟件規模的增長和程序設計語言的迅速發展，軟件測試變得越來越復雜。為了提高軟件測試效率，降低軟件測試費用，筆者研究開發了面向程序設計語言（如C、C++、Visual Basic）的軟件測試自動化工具。該工具實現基于路徑覆蓋的結構測試，能在單元測試和集成測試的級別上工作。主要功能有程序結構圖的自動生成、控制流圖的自動生成和控制流分析自動化、覆蓋分析自動化、質量度量自動化、動態跟蹤自動化。其中，程序結構圖及控制流圖的自動生成和質量度量自動化通過靜態分析實現；覆蓋分析自動化和動態跟蹤自動化通過動態分析實現。

眾所周知，基于路徑覆蓋的結構測試是軟件測試的一個難點，它要求獲悉完備的程序結構知識。為了有效分析程序的控制流，本文采用了一種新的、有效的、基于塊的程序劃分機制，并在此基礎上擴展了基于塊的測試覆蓋度量標準，設計了中間數據庫來存儲對程序進行劃分的靜態分析數據和在測試過程中動態跟蹤所獲取的測試信息（合稱為測試歷史）。下面簡單介紹一下基于塊的劃分機制和基于塊的測試覆蓋度量標準[12]，以及中間數據庫[11]的測試歷史信息。

1．1．1基于塊的劃分和基于塊的覆蓋度量

把程序理解為塊(Block)的序列。塊的定義是：可以被看做一個單元的一組連續的程序語句，或者說，總是在一起執行的最大的程序語句序列。

塊有兩類，即節點(Node)和段(Segment)。節點包括判斷（Decision）、連接（Junction）、程序單元的入口點和出口點。判斷是指程序中控制流開始分開的那一點，具體地說就是指分支語句的條件部分。C語言中的判斷有If(condition)、Switch(expression)、For(expression；expression；expression)、While(condition)(While語句或者Do…While 語句)。

連接是指程序中控制流可以合并的那一點。C語言中的連接有如下幾種：Do…While語句中的“Do”，If…Else…語句中的“Else”，Switch語句中的“Case常數表達式：”和“Default:”，標號(Label)。程序單元的入口點和出口點可以理解為一個作用域的開始點和結束點。在C語言中，“{”和“}”可以說是一個作用域的開始和結束的顯示標志。

段，即在兩個相鄰程序分支點之間的程序語句序列。也就是說，段是一段順序執行的單入口且單出口的程序語句序列。這里的程序分支點包括兩種：一種是前面所說的節點；另一種是指無條件轉移語句與下一條語句之間這個位置。所謂無條件轉移語句，以C語言為例，就是Goto、Return、Break和Continue語句等。不可見段的主要作用是記錄程序的執行路徑，以便進行覆蓋分析、路徑分析乃至測試用例生成等工作。

基于塊的劃分機制，擴展了基于塊的測試覆蓋度量準則：

（1）SC0統計執行過的可見段的比例，公式為

SC0＝至少執行過一次的可見段數目/可見段總數×100%

SC0類似于語句覆蓋率，但比語句覆蓋準則更充分。

（2）SC1統計執行過的可見段和基本不可見段的比例。其計算公式為

SC1＝至少執行過一次的可見段和基本不可見段的數目/可見段和基本不可見段的總數×100%

（3）SC1+統計執行過的可見段和所有不可見段（基本不可見段和循環邊界低端不可見段）的比例。計算公式為

SC1+＝至少執行過一次的可見段和不可見段的數目/可見段和不可見段的總數×100%

（4）J－Coverage統計執行過的可見段和不可見段以及演算過的條件輸出值的比例，計算公式為

J－Coverage＝至少執行過一次的可見段和不可見段以及條件輸出值的數目/可見段和不可見段以及條件輸出值的總數×100%

J－Coverage包含SC1+。

1．1．2測試歷史信息

測試歷史信息包括程序的靜態分析信息和動態測試跟蹤信息。

靜態分析信息包括源文件的結構信息、類的定義信息、方法的定義信息、源文件的塊劃分信息。塊劃分信息包括塊的類型、塊所對應的記錄點序號、塊在源程序中的起始行號等信息。每個源文件的所有塊用鏈表依次串成一條鏈，對應于整個程序。

動態測試跟蹤信息只收集與被測軟件運行時相關的信息，如程序中各個塊、條件等在每次測試中的執行次數；程序中的每個條件、判斷在測試執行過程中的取值（True/False）；每個測試用例測試了哪些段、方法、類以及運行時間等。一個簡化的基于塊的歷史執行信息如表1所示。

3實例研究

為了研究第二章所描述的兩個新算法的效率以及用例運行代價因素在測試最小化中的必要性，本文用C++開發了上述四個算法（SGrA、GrA、SGeA和GeA）的原型；并且對兩個實際的VB程序進行了實例研究，即計算器（CALCULATOR）模擬程序和電視放映模擬程序（LITTLE－TV）。相應的測試用例集是由軟件測試研究小組的研究人員在研究軟件測試工具時精心設計的。CALCULATOR程序由85個塊組成，LITTLE－TV由241個塊組成。它們的測試歷史信息都是由測試工具Panorama Tester在對它們進行測試時生成的。CALCULATOR程序的測試用例庫由174個用例組成，而LITTLE－TV程序的測試用例庫包含238個測試用例。從這兩個用例庫中，本文為每個程序抽取了包含不同數目的用例的原始用例集進行最小化。為CALCULATOR程序準備的原始用例集的大小是5~80個用例，每種大小的用例集各五組，覆蓋率在65%~95%，平均覆蓋率為90%。同樣，為LITTLE－TV程序準備的原始用例集大小是5~85個用例，每種大小的用例集也是各五組，覆蓋率在60%~98%，平均覆蓋率為89%。

從三個方面對最小化算法進行評價：最小化用例集的大小、最小化用例集在測試運行代價上的降低幅度以及最小化算法的運行時間。

為研究最小化算法的最小化能力，將最小化用例集包含的用例數設為原始用例集用例數的函數，實驗結果如圖3、4所示。由于同樣大小的用例集不只一個，得到的最小化用例集也是多個（平均5個以上），在圖中給出最小化用例集的用例數是一個平均值。從結果中可以看出， GeA算法得到的最小化用例集的用例數明顯小于用SGeA算法得到的，但是GrA算法得到的最小化用例集的用例數卻略大于用SGeA算法得到的。對于CALCULATOR程序，GeA和SGeA算法得到最小化用例集的平均用例數分別為6．49和22．64，GrA和SGrA算法得到最小化用例集的平均用例數分別為7．84和6．14；對于LITTLE－TV程序，GeA和SGeA算法得到最小化用例集的平均用例數分別為6．46和22．96，GrA和SGrA算法得到最小化用例集的平均用例數分別為7．33和6．45。

為研究最小化算法的效率，將測試用例最小化后減少的測試運行代價占原測試運行代價的百分比，設為原始用例集大小的一個函數，實驗結果由圖5、6給出。用GeA算法進行測試用例最小化對測試運行代價的降低百分比明顯高于SGeA算法（對于CALCULATOR， GeA比SGeA高38．57%；對于LITTLE－TV，GeA比SGeA高36．68%）；而對于貪心算法，雖然用GrA進行最小化在用例數目的縮減能力上略低于SGrA，但是對測試運行代價的降低百分比卻略高于SGrA算法（對于CALCULATOR，GrA比SGrA高3．6%；對于LITTLE－TV，GrA比SGrA高4．24%）。

為研究最小化算法的性能，對每種算法得到最小化用例集的運行時間進行考察。由于兩種貪心算法的運行時間都在幾毫秒或幾百微秒之間，差異不大，限于篇幅，沒有用圖給出實驗結果。圖7和8只給出了兩個遺傳算法的運行時間。從圖中可以看出，SGeA最小化測試用例所需要的運行時間遠多于GeA算法（對于CALCULATOR，SGeA比GeA平均多180 ms；對于LITTLE－TV， SGeA比GeA則平均多199 ms）且隨著原始用例集用例數目的增加，兩者時間的差距有增加的趨勢。

4結束語

給出了測試用例最小化的形式化描述：從給定的用例集合TS，找到一個子集TTS，滿足Cov(T)=Cov(TS)且Cost(T)最小。基于該描述，本文認為最小化測試用例，必須考慮測試用例的測試運行代價因素，測試用例最小化的目的不是單純減少用于回歸測試的用例數目。為此，提出了兩個用于測試用例最小化的新算法。算法綜合考慮了測試用例在以往測試中的測試覆蓋度和運行代價。為了研究在測試用例最小化算法中考慮運行代價對最小化效率的影響，同時開發了兩個不考慮代價因素簡單算法（其他過程都一樣）。

實驗結果表明，測試用例最小化技術能顯著減少測試用例集中的用例數和降低測試運行代價。同時，圖3~6的實驗結果也表明，在最小化過程中考慮測試運行代價，可以提高測試代價降低的百分率。雖然實驗結果在貪心算法中不是很明顯，但有一個重要現象，卻說明了用例數目與測試代價之間的關系：用例數最少的用例集的測試代價卻不一定最低。因此，測試用例最小化，非常有必要考慮每個測試用例的運行代價因素。

雖然，初步研究結果肯定了研究工作的意義，但必須從更多的實際測試最小化應用中，得到更多更充分的實驗數據，從而證明該最小化技術的通用性。另外，實驗結果中，遺傳算法雖然從優化效率上有比貪心算法更好的表現，但時間性能卻不如貪心算法。經過分析，本文認為一個重要的原因是由于初次使用進化算法解決測試用例最小化問題，許多方面還有待于提高和完善，如從交叉方式、交叉率以及變異率等方面繼續研究。在未來的工作中，筆者將繼續研究最小化算法的通用性和實用性，致力于測試最小化算法的實踐研究，以進一步提高最小化效率。

參考文獻：

[1]CHEN T Y， LAU M F. Dividing strategies for the optimization of a test suite[J]. Information Processing Letters， 1996，60(3):135－141.

[2]JONES J A， HARROLD M J. Test－suite reduction and prioritization for modified condition/decesion coverage[J]. IEEE Trans. on Software Engineering， 2003，29(3):195－209.

[3]HARROLD M J， GUPTA R， SOFFA M L. A methodlogy for controlling the size of a test suite[J]. ACM Trans. Software Eng. and Methods， 1993，2(3):270－285.

[4]OFFUTT J， PAN J， VOAS J M. Procedures for reducing the size of coverage－based test sets: proc.of the 12th Int’l Conf. Testing Computer Software[C].[S.l.]:[s.n.]， 1995:111－123.

[5]ROTHERMEL G， HARROLD M J， OSTRIA J， et al. An empirical study of the effects of minimization on the fault detection capabilities of test suites: proc.of the Int’l Conf. Software Maintenance[C].[S.l.]:[s.n.]， 1998:34－43.

[6]WONG W E， HORGAN J R， LONDON S， et al. Effect of test set minimization on fault detection effectiveness[J]. Software Practice and Experience， 1998，28(4):347－369.

[7]WONG W E， HORGAN J R， MATHUR A P， et al. Test set size minimization and fault detection effectiveness: a case study in a space application: proc.of the 21st Ann. Int’l Comp. Software and Application Conf.[C].[S.l.]:[s.n.]， 1997:522－528.

[8]CHEN Y E， ROSENBLUM D， VO K. TestTube: a system for selective regression testing: proc.of the 16th Int’l Conf. Software Eng.[C].[S.l.]:[s.n.]， 1994:211－222.

[9]ROTHERMEL G， HARROLD M J. A safe， efficient regression test selection technique[J].ACM Trans.Software Eng.and Methods， 1997，6(2):173－210.

[10]ROTHERMEL G， HAROOL M J. Selecting tests and identifying test coverage requirement for modified software: proc. of the 1994 International Symposium on Software Testing and Analysis[C]. Washington， United States:[s.n.]， 1994:169－184.

[11]馬雪英，姚礪，葉澄清.面向對象軟件測試引擎的設計和實現[J].計算機科學，2004，31(7):137－140.

[12]楊建軍，陳衛東，葉澄清， 等.面向上下文無關語言的測試工具的設計和實現[J].計算機研究和發展，2000，37(11):1375－1382.

[13]ONOMA K， TSAI W T， POONAWALA M， et al. Regression testing in an industrial environment[J]. Communications of the ACM， 1988，41(5):81－86.

[14]BCK T. Optimal mutation rates in genetic search: proc.of the 5th International Conference on Genetic Algorithms(ICGA’93)[C].[S.l.]: Morgan Kaufmann， 1993:2－9.

[15]BAUDRY B， FLEUREY F， JZQUEL J M， et al. Genes and bacteria for automatic test cases optimization in the .NET environment: proc.of ISSRE’02(International Symposium on Software Reliability Engineering)[C]. Annapolis， USA:[s.n.]， 2002:195－206.

[16]GOLDBERG D E. Genetic algorithms in search， optimization and machine learning[M].[S.l.]: Addison－Wesley， 1989.

[17]HOLLAND J H. Adaptation in natural and artificial systems[M].[S.l.]:University of Michigan Press， 1974.

[18]ROSENBLUM D S， WEYUKER E J. Using coverage information to predict the cost－effectiveness of regression testing strategies[J]. IEEE Transaction on Software Engineering， 1997，23(3):146－156.

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