遺傳算法在黑盒測試中的應用

摘要：提出了一種利用遺傳算法幫助測試人員在較短時(shí)間內完成軟件模塊的黑盒測試，并給出測試結果和好的測試用例的方法。

關(guān)鍵詞：遺傳算法 測試用例 耦合度

在軟件測試中，黑盒測試主要是針對模塊進(jìn)行的功能測試。最普遍的方法是以軟件的功能說(shuō)明書(shū)為基礎將軟件的輸入劃分為若干個(gè)等價(jià)類(lèi)，多次運行該軟件來(lái)檢驗軟件對于不同的等價(jià)類(lèi)是否能滿(mǎn)足要求。但是在實(shí)際應用中，有的模塊太大或輸入參數太多，等價(jià)類(lèi)劃分后需要進(jìn)行的測試工作可能是一個(gè)極大的任務(wù)。這時(shí)，如何選擇最優(yōu)的測試用例就成為測試人員的一個(gè)重要任務(wù)。

遺傳算法是模仿生物遺傳和進(jìn)化機制的一種最優(yōu)化方法，它把類(lèi)似于遺傳基因的一些行為，如交叉重組、變異、選擇和淘汰等引入到算法求解的改進(jìn)過(guò)程中。遺傳算法的特點(diǎn)之一是，它同時(shí)保留著(zhù)若干局部最優(yōu)解，通過(guò)交叉重組或者解的變異來(lái)尋求更好的解。與貪婪算法相比，遺傳算法更可能找到全局最優(yōu)解，而貪婪算法則容易限于局部最優(yōu)而達不到全局最優(yōu)。

如果能夠將遺傳算法有效地運用于黑盒測試中，幫助測試人員選擇最優(yōu)的測試用例，那么將給測試工作帶來(lái)極大的幫助。

１ 應用方法

在設計具體的算法之前，我們先介紹遺傳算法的基本算法，其算法框架如下[１]：

第一步，初始化：選?。饌€(gè)候選解作為初始解，把其中最好的解作為暫定（最優(yōu)）解。

第二步，解的改進(jìn)：若滿(mǎn)足終止條件，輸出暫定解，算法終止。否則，進(jìn)行以下的運算：

（１）解的交叉重組：從ｐ個(gè)解中選出兩個(gè)或兩個(gè)以上的解進(jìn)行交叉重組，得到新解，重復該運算若干次。

（２）解的變異：在候選解中隨機加進(jìn)一些變異，產(chǎn)生新解。

（３）局部搜索：對新產(chǎn)生的解用局部搜索法進(jìn)行改良。若能得到比候選解更好的解，更新候選解。

（４）從全部解中按一定的準則選出ｐ個(gè)解作為下一代的候選解，更新暫定解。

轉第二步。

了解了遺傳算法的算法框架后，進(jìn)一步要做的就是在軟件的黑盒測試中，如何將不同的等價(jià)類(lèi)轉變?yōu)檫z傳算法的候選解， 如何設定解的優(yōu)劣標準，如何設置合適的終止條件。

我們假定一個(gè)軟件模塊的輸入參數有５個(gè)：Ａ、Ｂ、Ｃ、Ｄ、Ｅ，經(jīng)過(guò)合理的等價(jià)類(lèi)劃分后，每個(gè)參數又有５個(gè)不同的等價(jià)類(lèi)：Ａ１～Ａ５，．．．．．．，Ｅ１～Ｅ５。我們采用一個(gè)廣義的遺傳算法候選解概念，一般的遺傳算法往往將候選解形式定為二進(jìn)制的數據串，比如：１１１０１０、０１０００１等等，而在不同等價(jià)類(lèi)輸入作為候選解時(shí)我們將候選解形式定為（按照上面假定為基礎）：Ａ３Ｂ１Ｃ２Ｄ４Ｅ５、Ａ２Ｂ２Ｃ４Ｄ１Ｅ３等等。這樣我們解決了候選解的問(wèn)題，在解的優(yōu)劣標準以及終止條件的設定問(wèn)題上，我們需要借助工具作為標準。

軟件測試的目的是提高軟件的可靠性，終止條件當然是軟件達到了測試的目的及要求。而解的優(yōu)劣標準正好與軟件質(zhì)量相反，即軟件失效幾率越大，這個(gè)測試用例（一個(gè)輸入的解）越優(yōu)。文獻２中結合北大的青鳥(niǎo)黑盒測試環(huán)境提出了一種基于測試執行的失效數據模型ＪＢＦＤＭ（Ｊａｄｅ Ｂｉｒｄ ｆａｉｌｕｒｅ ｄａｔａ ｍｏｄｅｌ）。利用該模型我們可以做到[２]：

（１）提供一致的失效數據建模、收集及管理的可靠性度量過(guò)程，從而支持可靠性度量；

（２）利用測試及軟件現場(chǎng)收集的數據來(lái)評價(jià)測試計劃、操作概圖及測試方法的有效性。

軟件測試的目的是發(fā)現錯誤，在黑盒測試中，錯誤表現的形式是軟件失效。但是由于軟件錯誤并不是軟件失效的充分條件，換句話(huà)說(shuō)，并不是所有錯誤都會(huì )在測試或運行時(shí)暴露，所以黑盒測試的目的就是盡可能的通過(guò)運行測試用例使軟件失效而發(fā)現錯誤。在我們對測試用例的評價(jià)時(shí)，用以下的數據表示測試用例的優(yōu)劣：

Ａ＝Ｐ＋λ／Ｍ＋μ×Ｆ

其中Ａ表示遺傳算法中的適應度Ａｄａｐｔａｔｉｏｎ，Ｐ表示該測試用例在實(shí)際中發(fā)生的幾率Ｐｒｏｂａｂｉｌｉｔｙ，Ｍ表示平均失效時(shí)間（ＭＴＴＦ），Ｆ表示失效等級。因為測試是針對使用的，所以發(fā)生幾率高的測試用例適應度高就不難理解了；而Ｍ——平均失效時(shí)間越長(cháng)，該測試用例應該不容易發(fā)現軟件的錯誤，所以Ａ越低；Ｆ則表示某些特殊情況發(fā)生使軟件嚴重失效（比如造成死機、損壞儀器等等），此時(shí)該測試用例以及其后代必須被重點(diǎn)關(guān)注，所以此時(shí)Ａ越大。λ、μ是相應于各個(gè)具體的被測試軟件模塊而定的系數。在實(shí)際應用中，由于軟件失效的可能性不是特別大，所以遺傳結果往往是發(fā)生幾率高的測試用例后代較多。所以我們應該針對具體被測試軟件設計準確的發(fā)生概率產(chǎn)生算法。具體算法框架如圖１所示。

對于該算法的說(shuō)明如下：
*１．每一個(gè)輸入參數往往有一個(gè)幾率（可以事先定義），可以簡(jiǎn)單相加來(lái)求得該測試用例的概率。但是在輸入參數有較強相關(guān)性時(shí)，此方法并不能準確求得某個(gè)測試用例的發(fā)生概率，一個(gè)解決辦法是設置輸入參數的相關(guān)耦合度。在遺傳算法的交叉、變異時(shí)其同時(shí)進(jìn)行的幾率與相關(guān)耦合度成正比，即對于相關(guān)耦合度高的輸入參數，它們同時(shí)進(jìn)行交叉、變異的幾率高，反之則低。

*２．檢驗是否滿(mǎn)足測試要求時(shí)，需要先設置一個(gè)計數器。每運行一個(gè)新的測試用例，測試計數器加一。當發(fā)現第一次失效或故障時(shí)，計數器加二。若產(chǎn)生的遺傳后代又使軟件發(fā)生失效，則計數器加２２。同理遞推，當遺傳算法產(chǎn)生的測試用例連續ｎ次使軟件失效，則計數器加２ｎ。同時(shí)，記錄所有的測試情況（此工作由外圍的測試環(huán)境完成，比如北大的青鳥(niǎo)黑盒測試環(huán)境）。如果出現嚴重錯誤則終止測試，進(jìn)行對程序的檢查。如果連續ｋ代測試用例的遺傳后代都運行良好，計數器的值加２ｋ。ｋ的值由具體被測試軟件的等價(jià)類(lèi)數量、輸入參數個(gè)數等決定。當測試計數器的值達到所有黑盒測試用例等價(jià)類(lèi)的數值時(shí)（對于我們上面所舉的例子，該值為５５＝３１２５），結束測試。當生成的孫子代、子代與父母代三代完全相同時(shí)，算法也必須結束，因為此時(shí)測試不會(huì )有新的結果。所以我們還要設置一個(gè)結束條件。而且該條件強于計數器條件。

*３．每一組測試用例可以生成多個(gè)測試用例，根據適應度函數大小決定留下哪些測試用例組成新的測試用例組。

從上面的算法框圖和說(shuō)明可以看出，如果某測試用例使軟件的運行發(fā)生了問(wèn)題（即某個(gè)軟件錯誤發(fā)作），它的后代也同樣受困于該軟件錯誤，算法很快能發(fā)現這些最佳測試用例并給出結果。測試人員就可以將它們交給開(kāi)發(fā)人員解決這些問(wèn)題。若軟件本身確實(shí)質(zhì)量?jì)?yōu)良，這些測試用例及其不同的后代無(wú)法發(fā)現失效，算法也能盡快結束，而不是完成所有測試用例（雖然從理論上，我們希望測試盡可能運行所有測試用例）。

２ 效果

上節的算法，相對于運行所有測試用例，并沒(méi)有比較明顯的優(yōu)點(diǎn)。尤其對于測試來(lái)說(shuō)，算法并沒(méi)有加速運行測試用例，好象還降低了運行速度。其實(shí)算法本身的確不是用來(lái)加速運行測試用例的，其目的是找到一組最佳測試用例。因為實(shí)際上對于很多模塊運行所有測試用例或哪怕是所有等價(jià)類(lèi)都是幾乎不可能的。

以上一節舉的例子做說(shuō)明，其輸入等價(jià)類(lèi)大致有５５＝３１２５。如果一個(gè)模塊有１０個(gè)輸入、每個(gè)輸入有１０種等價(jià)類(lèi)，那么輸入等價(jià)類(lèi)為１０１０。按運行一個(gè)等價(jià)類(lèi)需要１分鐘計算（很多循環(huán)運行模塊可能不止１分鐘），需要幾個(gè)月才能運行一遍所有等價(jià)類(lèi)。這時(shí)，運用遺傳算法的優(yōu)勢就體現出來(lái)了。

綜上所述，本文提出了一種利用遺傳算法尋求最佳測試用例的測試方法原理。它能在較短時(shí)間內完成軟件模塊的黑盒測試并給出測試結果和好的測試用例。利用該算法原理，可以在測試集成環(huán)境中做一些設置或修改測試集成環(huán)境，這樣可以大大提高測試工作的效率。