基于分類樹和蟻群算法的測試用例設計

何 斌 王敏帥

（中國人民解放軍91404部隊，河北 秦皇島 066000）

0 引言

軟件測試是保證軟件質量最為重要的一種手段，有效的軟件測試可以發現軟件中存在的絕大部分問題。所以，軟件測試項目的終級目標是100%測試覆蓋，發現軟件中盡可能多的問題，為靠近這一目標測試項目組會盡可能多設計測試用例以達到最佳測試效果。因為不可能進行窮盡的測試，測試一般會在保證測試覆蓋率同時盡可能精簡測試集，相應的方法一直是測試工程師研究的重點課題。

基于不同測試方法設計的測試用例集會有很大的差異。在軟件的系統測試階段，分類樹方法是一種非常有效的測試用例集設計方法，分類樹方法是由Grochtmann和Grimm在1993年提出的，是在軟件功能測試方面一種有效的測試方法，通過分類樹把測試對象的整個輸入域分割成獨立的類。通過組合各種不同分類的結果來形成測試用例。使用分類樹方法的一個重要的好處是：它把測試用例設計轉變成一個組合若干結構化和系統化的測試對象組成部分的過程使其容易把握，易于理解，當然也易于文檔化。但分類樹設計方法并未根據測試覆蓋標準對測試用例集進行約束，測試用例集往往很龐大。本文針對功能測試用例集生成，提出使用變異因子的蟻群算法對采用分類樹生成的測試用例集進行優化，使測試用例集達到測試覆蓋率與規模的最優化。

1 分類樹方法用于測試用例設計

分類樹方法的基本原理是：首先把測試對象的可能輸入按照不同的分類方式進行分類，每一種分類要考慮的是測試對象的不同的方面。然后把各種分開的輸入組合在一起產生測試用例，同時又能覆蓋測試對象的整個輸入域。

分類樹方法設計測試用例的過程分為三大步驟：

1）識別出測試對象并分析輸入空間。

2）對測試對象的輸入空間進行分類。

3）畫出分類樹、組合成測試用例。

以Windows操作系統自帶標準計算器為例演示分類樹的測試用例設計過程：

如圖1所示對計算器的輸入進行劃分，以一個二元運算式為例輸入操作為：

把計算器輸入劃分成運算數、運算符、內存操作（屬于擴展功能）。按等價類方法把各種分類細化各種輸入可能。例如，運算數可能的輸入是負數最小值、負數正常值、負數最大值、零、正數最小值、正數正常值、正數最大值、無操作等；運算符可能的輸入是/、*、-、+、1/x、sqrt、%、=；內存操作的可能的操作是 MC、MR、MS、M+、無操作。 最后，測試用例由不同分類的類組合形成，在組合類時交集不能為空。測試人員組合類形成需要的測試用例，以便覆蓋測試一個二元等式的所有方面并充分考慮各種可能。

從例子中可以看出測試人員如果要考慮所有組合進行用例設計，最后用例集將十分大。在實際的測試工作中，被測軟件的規模及復雜程度也比例子軟件大的多，采用分類樹設計的測試用例數將十分巨大。事實上若無特殊要求的情況下，在滿足充分性同時會考慮最精簡的測試用例集，以達到測試效益的最優。

2 蟻群算法優化測試用例設計

20 世紀 90 年代意大利學者 M．Dorigo，V．Maniezzo，A．Colorni等從生物進化的機制中受到啟發，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進化算法——蟻群算法(Ant Colony Optimization,ACO)，是群智能理論研究領域的一種主要算法。

在分類樹測試用例集的優化中蟻群算法可這樣描述。設節點r為分類樹的根節點，節點1－m分別代表分類樹的葉子（測試輸入值），任何一個測試用例可看成根節點到葉子j(j≠0)的路徑。

將r作為螞蟻尋優的起點，輸入值j看作螞蟻選擇的食物源,dj可以理解為從尋優起點到食物源的距離。對任任意一只螞蟻k從節點r觀到節點j的概率為：

τrj（t）表示路徑上殘留的信息素強度，該參數表明了系統從節點r轉移到j的后天演化過程中得到受益度；ηrj（t）表示先天性的啟發性，該起始信息是由要解決的問題給出的即表示轉移對于螞蟻k的吸引度。α表示殘留信息的相對重要程度；β表示期望值的相對重要程度。在計算器的例子中一個用例是由一組螞蟻轉移尋找食物源完成的，如完成一個二元計算式是至少由4只螞蟻同時尋找路徑完成的。在使用蟻群算法過程中每設計一個用例完成一次求解，每求解一次對路徑中的信息素強度進行更新，更新的方程式為：

ρ為揮發系數，為了防止信息的無限累積，ρ必須小于1。

在實際中主要有兩種應用：首輪測試用例與回歸用例設計。首輪測試用例設計需要在滿足覆蓋率的基本上有好的發散性；回歸用例設計一般的做法是首輪用例加新增用例，新增用例要求對有錯誤的模塊有重點增加測試用例。所以，首輪測試用例設計參數選擇原則：ρ揮發系數設置應適當偏大，dm可以忽略為近似。算法結束條件為分類樹分支覆蓋。

回歸測試新增設計主要由上一輪測試問題啟發，所以在其它參數不變的情況下適當增大β值并重新調整：更改為：,其中w為上一輪這一路徑涉及模塊發現問題數。

3 驗證

為驗證本文的方法進行編程實驗，以上文計算器測試為例，演算達到塊覆蓋率的用例數。 在實驗中，取 Q=1，ρ=0.8，α=0.5，β=0.7，共 39個葉子（輸入值），啟動5只螞蟻，得到實驗結果如表所示：

表1 得到測試用例數

以上結果表明，本方法在實踐中可行。由于計算器軟件沒有首輪測試未發現問題，回歸測試用例實驗未進行。

4 結束語

本文提出以分類樹為基礎并以蟻群算法優化進行用例設計，可以使用例的設計更加科學化、規范化，以此基礎可以進一步研究測試用例設計的自動化生成與實現，必將為軟件測試帶來新的技術革新?；诂F有工作，下一步研究：（1）算法的通用性及自適應能力；(2)方法的工程實現可能。

［1］Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.

［2］傅博.基于蟻群算法的軟件測試數據自動生成[J].計算機工程與應用,2007(12).

［3］尹文潔，崔冬華.測試用例集的方法研究[J].電腦開發與應用，2011：5.

［4］吳啟迪,汪鐳著.智能蟻群算法及應用[M].上?？萍冀逃霭嫔?2004：4-6.

［5］朱少民.全程軟件測試[M].電子工業出版社,2007,9.