基于分類樹和蟻群算法的測(cè)試用例設(shè)計(jì)

何 斌 王敏帥

（中國(guó)人民解放軍91404部隊(duì)，河北 秦皇島 066000）

0 引言

軟件測(cè)試是保證軟件質(zhì)量最為重要的一種手段，有效的軟件測(cè)試可以發(fā)現(xiàn)軟件中存在的絕大部分問(wèn)題。所以，軟件測(cè)試項(xiàng)目的終級(jí)目標(biāo)是100%測(cè)試覆蓋，發(fā)現(xiàn)軟件中盡可能多的問(wèn)題，為靠近這一目標(biāo)測(cè)試項(xiàng)目組會(huì)盡可能多設(shè)計(jì)測(cè)試用例以達(dá)到最佳測(cè)試效果。因?yàn)椴豢赡苓M(jìn)行窮盡的測(cè)試，測(cè)試一般會(huì)在保證測(cè)試覆蓋率同時(shí)盡可能精簡(jiǎn)測(cè)試集，相應(yīng)的方法一直是測(cè)試工程師研究的重點(diǎn)課題。

基于不同測(cè)試方法設(shè)計(jì)的測(cè)試用例集會(huì)有很大的差異。在軟件的系統(tǒng)測(cè)試階段，分類樹方法是一種非常有效的測(cè)試用例集設(shè)計(jì)方法，分類樹方法是由Grochtmann和Grimm在1993年提出的，是在軟件功能測(cè)試方面一種有效的測(cè)試方法，通過(guò)分類樹把測(cè)試對(duì)象的整個(gè)輸入域分割成獨(dú)立的類。通過(guò)組合各種不同分類的結(jié)果來(lái)形成測(cè)試用例。使用分類樹方法的一個(gè)重要的好處是：它把測(cè)試用例設(shè)計(jì)轉(zhuǎn)變成一個(gè)組合若干結(jié)構(gòu)化和系統(tǒng)化的測(cè)試對(duì)象組成部分的過(guò)程使其容易把握，易于理解，當(dāng)然也易于文檔化。但分類樹設(shè)計(jì)方法并未根據(jù)測(cè)試覆蓋標(biāo)準(zhǔn)對(duì)測(cè)試用例集進(jìn)行約束，測(cè)試用例集往往很龐大。本文針對(duì)功能測(cè)試用例集生成，提出使用變異因子的蟻群算法對(duì)采用分類樹生成的測(cè)試用例集進(jìn)行優(yōu)化，使測(cè)試用例集達(dá)到測(cè)試覆蓋率與規(guī)模的最優(yōu)化。

1 分類樹方法用于測(cè)試用例設(shè)計(jì)

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

分類樹方法設(shè)計(jì)測(cè)試用例的過(guò)程分為三大步驟：

1）識(shí)別出測(cè)試對(duì)象并分析輸入空間。

2）對(duì)測(cè)試對(duì)象的輸入空間進(jìn)行分類。

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

以Windows操作系統(tǒng)自帶標(biāo)準(zhǔn)計(jì)算器為例演示分類樹的測(cè)試用例設(shè)計(jì)過(guò)程：

如圖1所示對(duì)計(jì)算器的輸入進(jìn)行劃分，以一個(gè)二元運(yùn)算式為例輸入操作為：

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

從例子中可以看出測(cè)試人員如果要考慮所有組合進(jìn)行用例設(shè)計(jì)，最后用例集將十分大。在實(shí)際的測(cè)試工作中，被測(cè)軟件的規(guī)模及復(fù)雜程度也比例子軟件大的多，采用分類樹設(shè)計(jì)的測(cè)試用例數(shù)將十分巨大。事實(shí)上若無(wú)特殊要求的情況下，在滿足充分性同時(shí)會(huì)考慮最精簡(jiǎn)的測(cè)試用例集，以達(dá)到測(cè)試效益的最優(yōu)。

2 蟻群算法優(yōu)化測(cè)試用例設(shè)計(jì)

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

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

將r作為螞蟻尋優(yōu)的起點(diǎn)，輸入值j看作螞蟻選擇的食物源,dj可以理解為從尋優(yōu)起點(diǎn)到食物源的距離。對(duì)任任意一只螞蟻k從節(jié)點(diǎn)r觀到節(jié)點(diǎn)j的概率為：

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

ρ為揮發(fā)系數(shù)，為了防止信息的無(wú)限累積，ρ必須小于1。

在實(shí)際中主要有兩種應(yīng)用：首輪測(cè)試用例與回歸用例設(shè)計(jì)。首輪測(cè)試用例設(shè)計(jì)需要在滿足覆蓋率的基本上有好的發(fā)散性；回歸用例設(shè)計(jì)一般的做法是首輪用例加新增用例，新增用例要求對(duì)有錯(cuò)誤的模塊有重點(diǎn)增加測(cè)試用例。所以，首輪測(cè)試用例設(shè)計(jì)參數(shù)選擇原則：ρ揮發(fā)系數(shù)設(shè)置應(yīng)適當(dāng)偏大，dm可以忽略為近似。算法結(jié)束條件為分類樹分支覆蓋。

回歸測(cè)試新增設(shè)計(jì)主要由上一輪測(cè)試問(wèn)題啟發(fā)，所以在其它參數(shù)不變的情況下適當(dāng)增大β值并重新調(diào)整：更改為：,其中w為上一輪這一路徑涉及模塊發(fā)現(xiàn)問(wèn)題數(shù)。

3 驗(yàn)證

為驗(yàn)證本文的方法進(jìn)行編程實(shí)驗(yàn)，以上文計(jì)算器測(cè)試為例，演算達(dá)到塊覆蓋率的用例數(shù)。 在實(shí)驗(yàn)中，取 Q=1，ρ=0.8，α=0.5，β=0.7，共 39個(gè)葉子（輸入值），啟動(dòng)5只螞蟻，得到實(shí)驗(yàn)結(jié)果如表所示：

表1 得到測(cè)試用例數(shù)

以上結(jié)果表明，本方法在實(shí)踐中可行。由于計(jì)算器軟件沒(méi)有首輪測(cè)試未發(fā)現(xiàn)問(wèn)題，回歸測(cè)試用例實(shí)驗(yàn)未進(jìn)行。

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

本文提出以分類樹為基礎(chǔ)并以蟻群算法優(yōu)化進(jìn)行用例設(shè)計(jì)，可以使用例的設(shè)計(jì)更加科學(xué)化、規(guī)范化，以此基礎(chǔ)可以進(jìn)一步研究測(cè)試用例設(shè)計(jì)的自動(dòng)化生成與實(shí)現(xiàn)，必將為軟件測(cè)試帶來(lái)新的技術(shù)革新?；诂F(xiàn)有工作，下一步研究：（1）算法的通用性及自適應(yīng)能力；(2)方法的工程實(shí)現(xiàn)可能。

［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］傅博.基于蟻群算法的軟件測(cè)試數(shù)據(jù)自動(dòng)生成[J].計(jì)算機(jī)工程與應(yīng)用,2007(12).

［3］尹文潔，崔冬華.測(cè)試用例集的方法研究[J].電腦開發(fā)與應(yīng)用，2011：5.

［4］吳啟迪,汪鐳著.智能蟻群算法及應(yīng)用[M].上海科技教育出版社,2004：4-6.

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