基于遺傳算法的軟件測試用例自動生成研究

1、    基于遺傳算法的軟件測試用例自動生成研究    劉東旭 吳昊摘要：測試用例由測試輸入數(shù)據(jù)以及與之對應的輸出結(jié)果組成，測試用例設(shè)計的好壞直接決定了測試的效果和結(jié)果，所以說在軟件測試活動中最關(guān)鍵的步驟就是設(shè)計有效的測試用例。文章闡述了一種尋優(yōu)搜索算法來自動生成軟件測試用例數(shù)據(jù)，即遺傳算法，利用遺傳算法原理的模型圖結(jié)合測試用例設(shè)計需求，介紹了遺傳算法自動生成測試用例數(shù)據(jù)的思想和步驟，并在此基礎(chǔ)上研究了基于遺傳算法在測試用例自動生成上的技術(shù)。利用此方法產(chǎn)生的測試用例數(shù)據(jù)可以產(chǎn)生較好的測試結(jié)果。關(guān)鍵詞：軟件測試；測試用例；遺傳算法1 遺傳算法概述遺傳算法（g

2、enetic algorithm，ga）是在20世紀70年代由美國科學家提出的，是模擬自然界的生物物種的進化和遺傳機制原理用來尋找最優(yōu)解的自組織、自適應搜索算法。軟件測試與軟件質(zhì)量是成正比的關(guān)系。測試工作的質(zhì)量決定了軟件的質(zhì)量，而測試用例的優(yōu)劣又決定了測試工作的質(zhì)量，人工的用例設(shè)計耗時耗力且存在主官片面性，因此，要設(shè)計出最優(yōu)最少的用例找出軟件中盡可能多的缺陷是測試人員需要解決的問題。本文在闡述了軟件測試的特點及測試用例設(shè)計之后，結(jié)合軟件測試與遺傳算法各自的特點，分析利用遺傳算法自動生成軟件測試用例數(shù)據(jù)的應用，研究用于軟件測試用例數(shù)據(jù)自動生成的遺傳算法。2 軟件測試及測試用例設(shè)計軟件測試是由測試

3、人員獲取需求規(guī)格說明書，設(shè)計文檔及源程序清單等資料，結(jié)合測試用例設(shè)計方法有針對性地設(shè)計出大量的測試用例，測試用例執(zhí)行人員執(zhí)行設(shè)計出的用例找出軟件中存在的問題2。因此軟件測試的目的找出程序在設(shè)計過程中的問題（或者叫缺陷）。所以軟件測試是在軟件開發(fā)整個周期中找出軟件中存在的缺陷，而并不是為了驗證軟件的正確。軟件測試團隊在進行測試時主要包括以下幾個步驟。（1）編寫軟件測試計劃方案；（2）利用常用的測試用例設(shè)計方法編寫測試用例；（3）測試人員逐條執(zhí)行用例，如找出缺陷，標記并提交；（4）測試人員追蹤缺陷狀態(tài)，進行回歸測試；（5）編寫本次測試總結(jié)報告。測試用例是測試人員在測試過程中執(zhí)行的最小的一個單位，是

4、由輸入的數(shù)據(jù)值、測試執(zhí)行的條件和步驟以及對應的預期輸出的數(shù)據(jù)值3部分構(gòu)成3。一個測試用例的好壞，不能體現(xiàn)整個測試用例集的優(yōu)劣。所以測試用例集的設(shè)計對測試人員有著很高的要求，不僅能找出潛在的缺陷，還能節(jié)省軟件開發(fā)的成本。測試用例在設(shè)計過程中的輸入數(shù)據(jù)值的范圍很廣，如有一個程序f，有兩個輸入量x，y，一個輸出量z，在字長為64位的計算機上運行。若x，y取整數(shù)，按用例設(shè)計方法可設(shè)計出：264×264=2 128條測試用例。這是一個非常龐大的數(shù)據(jù)，在實際的測試中這種數(shù)據(jù)量的測試是不可行的，因此窮舉法在測試中是不能實現(xiàn)的，我們需要在大量的數(shù)據(jù)中選擇一些具有代表性的值作為測試用例。這要求在測試人

5、員在設(shè)計測試用例時利用一些方法并考慮到額外的一些因素。測試方法主要包括兩大類：黑盒測試法主要著重與功能和特性，白盒測試法主要著重與程序的邏輯結(jié)構(gòu)。黑盒測試和白盒測試主要方法如表1所示。3 遺傳算法生成測試用例的系統(tǒng)模型遺傳算法作為一種在大量數(shù)據(jù)中尋優(yōu)的搜索算法，它是在大量搜索數(shù)據(jù)中隨機選取數(shù)據(jù)，按照一定的評價函數(shù)對搜索出的每個數(shù)據(jù)進行評估，并對遺傳算子進行優(yōu)化，直到找出最合理最優(yōu)的數(shù)據(jù)值，利用遺傳算法原理自動生成測試用例數(shù)據(jù)的系統(tǒng)模型如圖1所示。從圖1中我們可看出其由兩大塊組成：（1）遺傳算法設(shè)計與執(zhí)行模塊；（2）數(shù)據(jù)個體評優(yōu)模塊。其中遺傳算法設(shè)計與執(zhí)行模塊是用例生成的核心算法，第一步給定初始

6、數(shù)據(jù)值，隨機初始化第一代種群，第二步按照設(shè)計好的編碼規(guī)則將初始化的數(shù)據(jù)值轉(zhuǎn)換成驅(qū)動程序的實參值，通過參數(shù)傳遞給被測程序的形參，運行被測程序。而個體評價部分主要是在被測程序中插入評價函數(shù)，產(chǎn)生相應的函數(shù)值傳遞給遺傳算法。利用個體評優(yōu)模塊的評價函數(shù)對遺傳算法設(shè)計與執(zhí)行模塊產(chǎn)生的大量數(shù)據(jù)值優(yōu)勝劣汰，再結(jié)合遺傳算子的選擇、交叉、突變操作改變個體數(shù)據(jù)值的結(jié)構(gòu)，形成更優(yōu)一代的種群，反復循環(huán)，直至找出測試用例需求數(shù)據(jù)的最優(yōu)解4。4 遺傳算法在軟件測試用例生成中的應用研究軟件測試過程中測試用例的設(shè)計起著至關(guān)重要的作用，人工設(shè)計軟件測試用例是不可或缺的，但是龐大的數(shù)據(jù)量讓人工設(shè)計測試用例舉步維艱，因此自動化生成

7、測試用例是測試人員設(shè)計用例的未來發(fā)展方向。測試用例數(shù)據(jù)自動生成大大縮短軟件開發(fā)的生命周期、提高了軟件測試的效率。測試用例數(shù)據(jù)的自動生成就是在大量數(shù)據(jù)值的范圍中，利用設(shè)計好的算法規(guī)則選出一些具有代表性的數(shù)據(jù)成為用例的輸入值。而遺傳算法又作為一種尋找最優(yōu)解的搜索算法，因此將遺傳算法融入測試用例設(shè)計中去，很大程度上優(yōu)化了測試用例的數(shù)據(jù)值，提高了測試用例的質(zhì)量。4.1 遺傳算法生成測試數(shù)據(jù)的思想遺傳算法是一種高效的自動尋優(yōu)搜索算法，對繁冗的軟件測試用例自動生成具有指導性作用。利用遺傳算法的原理得出一組最優(yōu)的測試用例數(shù)據(jù)集，在每一次種群迭代過程中，不斷生成新的群體，并繼續(xù)自動生成測試用例傳遞給被測試程序

8、執(zhí)行，測試人員在每一次對被測程序執(zhí)行測試之后都將記錄執(zhí)行路徑追蹤測試數(shù)據(jù)，并形成一個日志文件，以路徑覆蓋度的最大化作為評價函數(shù)的評價標準，得出新一代的群體；經(jīng)過多次迭代，使用遺傳和變異的方式更新種群中的個體，當算法達到之前設(shè)定的循環(huán)結(jié)束條件或者產(chǎn)生出最優(yōu)最適合的測試用例集。軟件測試過程中，利用遺傳算法搜索最優(yōu)解的特點，自動生成數(shù)值型測試用例數(shù)據(jù)，產(chǎn)生測試用例集。使用遺傳算法自動生成軟件測試用例數(shù)據(jù)的思想是：（1）數(shù)據(jù)值輸入問題轉(zhuǎn)化為數(shù)據(jù)值優(yōu)化問題；（2）設(shè)計出合理有效的評價函數(shù)，評價生成數(shù)據(jù)值的優(yōu)劣。4.2 利用遺傳算法生成軟件測試用例數(shù)據(jù)（1）將程序的輸入數(shù)據(jù)問題轉(zhuǎn)換為遺傳算法可處理的問題，

9、對程序的輸入值f1（x1，x2，x3，x4，.xn_），進行編碼，一般可利用二進制編碼形式，編碼后數(shù)據(jù)值為f1（y1，y2，y3，y4，.yn_）每個數(shù)據(jù)均視為一個個體，利用隨機函數(shù)生成初始化種群。（2）配置好被測程序的驅(qū)動程序一個driver（）和粧程序若干program1（），program2（），program3（）以及之間的接口問題。（3）結(jié)合具體的程序要求和測試要求，設(shè)計出一個軟件失效模型，給出相應的評價體系函數(shù)f（x）執(zhí)行測試用例數(shù)據(jù)輸入操作，根據(jù)被測程序的返回數(shù)據(jù)值，對比軟件失效模型的數(shù)據(jù)值f=ff1（y1，y2，y3，y4，.yn_）， f2（y1，y2，y3，y4，.yn_）

10、，fn（y1，y2，y3，y4，.yn_），評價測試用例數(shù)據(jù)的優(yōu)劣。所謂的軟件實現(xiàn)模型亦即評價函數(shù)或適應度函數(shù)。（4）根據(jù)軟件失效模型的數(shù)據(jù)值對每個輸入值的個體利用遺傳算子進行選擇、交叉和變異操作，形成新一代的種群。（5）重復（2）（4），利用遺傳算法直至找出測試用例數(shù)據(jù)的最優(yōu)解或依據(jù)程序規(guī)則設(shè)置合適的終止條件。如可定義一個整型變量count。測試用例輸入值每輸入一次count+。當count值達到設(shè)定的范圍時，終止此次算法。依據(jù)評價函數(shù)的數(shù)據(jù)值和實際數(shù)據(jù)值比較形成測試用例數(shù)據(jù)值。5 結(jié)語利用算法為軟件測試生成高效率的測試用例是測試人員必須面臨和急需解決的問題。而遺傳算法由于其本身強大的全局搜

11、索能力和魯棒性，因而能夠很好地應用于測試用例數(shù)據(jù)的自動化生成中1。本文主要闡述了目前測試用例數(shù)據(jù)自動生成技術(shù)的普遍性和重要性，軟件測試的目的和測試用例設(shè)計的主要方法，并利用遺傳算法建立了測試用例自動生成的系統(tǒng)模型，介紹了遺傳算法生成測試用例數(shù)據(jù)的思想以及利用遺傳算法自動生成測試用例數(shù)據(jù)的算法步驟5。綜上所述，遺傳算法在生成數(shù)據(jù)時受到適應性函數(shù)的制約，由此產(chǎn)生的數(shù)據(jù)值既高效又具有代表性。因此，結(jié)合遺傳算法自動生成測試用例，它不僅能保證高質(zhì)量的測試用例數(shù)據(jù)，而且還在很大程度上縮短了開發(fā)周期，提高了軟件質(zhì)量降低軟件使用過程中受到的風險。參考文獻1姚堯.一種基于遺傳算法的軟件測試用例生成新方法j.計算機與數(shù)字工程，2009（1）：1