基于輸出域的測試用例自動生成方法研究

尤　楓　趙瑞蓮　呂珊珊

(北京化工大學(xué)計算機(jī)科學(xué)系　北京　100029)

(rlzhao@mail.buct.edu.cn)

?

基于輸出域的測試用例自動生成方法研究

尤楓趙瑞蓮呂珊珊

(北京化工大學(xué)計算機(jī)科學(xué)系北京100029)

(rlzhao@mail.buct.edu.cn)

Output Domain Based Automatic Test Case Generation

You Feng, Zhao Ruilian, and Lü Shanshan

(DepartmentofComputerScienceandTechnology,BeijingUniversityofChemicalTechnology,Beijing100029)

AbstractFor most software systems it is very hard to obtain expected output automatically on the basis of specifications. However, there exist many notable detection points in output domain of some software, so it may be more suitable to develop test cases from output domain than from input. In addition, even if an output is given, it is also difficult to find its input automatically. Therefore in this paper, we present an output domain based automatic test case generation method. At first, a back propagation neural network is used to create a model that can be taken as a function substitute for the software under test, and then according to the created function model, genetic algorithms are employed to search the corresponding inputs for given outputs. In order to improve the effectiveness of test case generation, a new crossover operation and a mutation operation are introduced in our genetic algorithm. Moreover, a number of experiments have been conducted on test generation based on the created function models over the fault tolerant software RSDIMU and three common used software. The experimental results show that the approach is promising and effective, and our genetic algorithm can distinctly enhance the efficiency and successful ratio to test case generation from output domains.

Key wordsBP neural network; software function model; test case generation; output domain; genetic algorithm

摘要對大多數(shù)軟件，很難根據(jù)規(guī)格說明自動產(chǎn)生期望的輸出.而對于某些軟件，輸出域存在許多值得關(guān)注的檢測點(diǎn)，適合于從輸出域出發(fā)開發(fā)測試用例.但對于給定的輸出，自動生成相應(yīng)的輸入也較為困難.提出了一種基于輸出域的測試用例自動生成方法，首先利用BP神經(jīng)網(wǎng)絡(luò)構(gòu)建被測軟件的功能模型，然后在被測軟件的功能模型上，對于給定的輸出，利用遺傳算法搜索相應(yīng)的輸入，實(shí)現(xiàn)基于輸出域的測試用例自動生成.同時，對遺傳算法進(jìn)行了改進(jìn)，提出了一種新的交叉算子和變異算子，以提高遺傳算法生成測試用例效率，并在容錯軟件RSDIMU子模塊和3個常用軟件上進(jìn)行了模型構(gòu)建及測試生成實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，利用遺傳算法實(shí)現(xiàn)基于輸出域的測試用例自動生成方法是行之有效的，改進(jìn)的遺傳算法能夠提高測試生成的效率和成功率.

關(guān)鍵詞BP神經(jīng)網(wǎng)絡(luò)；軟件功能模型；測試用例生成；輸出域；遺傳算法

隨著軟件應(yīng)用領(lǐng)域的不斷擴(kuò)展和軟件規(guī)模的不斷增大，軟件的可靠性顯得越來越重要.軟件測試是保證軟件可靠性和安全性的重要技術(shù)手段，軟件測試的成本通常占整個研發(fā)成本相當(dāng)大的比例.

目前常用的測試方法有黑盒測試和白盒測試.白盒測試通過分析被測軟件的結(jié)構(gòu)信息來生成測試用例；黑盒測試則根據(jù)其輸入輸出關(guān)系，即規(guī)格說明來開發(fā)測試用例.Vanmali等人[1]認(rèn)為白盒測試不適合于現(xiàn)在大規(guī)模的軟件系統(tǒng)，無法檢測出遺漏的代碼問題，因此，使用黑盒測試來保障軟件質(zhì)量和可靠性至關(guān)重要.

黑盒測試的一個關(guān)鍵問題是如何從規(guī)格說明出發(fā)，以盡可能少的代價開發(fā)出有效的測試用例.顯然，如果測試自動化能夠?qū)崿F(xiàn)，測試開銷會降低.

實(shí)現(xiàn)測試自動化，最基本也是最重要的就是測試用例的自動生成[2-3].測試自動化涉及測試輸入的自動生成、期望輸出的自動產(chǎn)生、測試執(zhí)行的自動實(shí)現(xiàn)以及測試結(jié)果的自動評估[4]，其中測試輸入和期望輸出的自動生成是關(guān)鍵.但從規(guī)格說明自動產(chǎn)生期望輸出比較困難，特別是對于無法用形式化描述的規(guī)格說明，自動獲得期望輸出更加困難.

另外，某些軟件存在許多值得關(guān)注的輸出點(diǎn)，這類軟件適合從輸出域出發(fā)開發(fā)測試用例.然而，對于給定的輸出，自動獲得相應(yīng)的輸入同樣困難，尤其是大型復(fù)雜軟件.因此，一個可行的方法是構(gòu)建被測軟件的功能模型，并在此基礎(chǔ)上，從程序輸出域出發(fā)，搜索相應(yīng)的輸入，實(shí)現(xiàn)基于輸出域的測試用例自動生成.

BP神經(jīng)網(wǎng)絡(luò)具有較強(qiáng)的非線性映射能力，在軟件建模方面具有很好的實(shí)用效果，近年來逐漸被應(yīng)用到軟件測試領(lǐng)域中[5].

遺傳算法是一個有效的全局優(yōu)化算法，廣泛應(yīng)用于軟件測試用例自動生成中.例如Pinto和Vergilio[6]采用多目標(biāo)遺傳算法生成測試數(shù)據(jù)；Chen和Yang[7]采用遺傳算法進(jìn)行分支覆蓋測試；Deepak和Samuel[8]采用進(jìn)化的多種群遺傳算法生成測試數(shù)據(jù)；本文作者[9]前期進(jìn)行了利用遺傳算法生成非數(shù)值型測試數(shù)據(jù)的相關(guān)研究.然而，目前已有的這些利用遺傳算法生成測試數(shù)據(jù)方法，大多從程序輸入域出發(fā)，很少有文獻(xiàn)提及如何從輸出域出發(fā)自動生成測試用例.

本文將BP神經(jīng)網(wǎng)絡(luò)和遺傳算法相結(jié)合實(shí)現(xiàn)基于輸出域的測試用例生成.首先采用BP神經(jīng)網(wǎng)絡(luò)作為建模工具構(gòu)建被測軟件的功能模型，模擬被測軟件的功能；然后在功能模型上，對給定的輸出，利用遺傳算法搜索相應(yīng)輸入，實(shí)現(xiàn)基于輸出域的測試用例自動生成.同時，對遺傳算法進(jìn)行了改進(jìn)，提出了一種新的交叉算子和變異算子，以提高遺傳算法生成測試用例的效率.實(shí)驗(yàn)結(jié)果表明：本文提出的利用遺傳算法實(shí)現(xiàn)從輸出到輸入的測試用例自動生成方法是行之有效的.

1被測軟件功能模型的構(gòu)建

實(shí)際上，大多數(shù)軟件系統(tǒng)的輸入、輸出之間存在著復(fù)雜的非線性映射關(guān)系，而3層BP神經(jīng)網(wǎng)絡(luò)具有良好的非線性映射能力.因此，本文采用3層BP神經(jīng)網(wǎng)絡(luò)作為建模工具來構(gòu)建被測軟件的功能模型，以反映被測軟件輸入輸出間的對應(yīng)關(guān)系.其主要思想為：1)根據(jù)被測軟件的特征確定BP神經(jīng)網(wǎng)絡(luò)的初始結(jié)構(gòu)；2)依據(jù)其規(guī)格說明開發(fā)多組輸入輸出對作為訓(xùn)練樣本，對網(wǎng)絡(luò)進(jìn)行訓(xùn)練，調(diào)整網(wǎng)絡(luò)參數(shù).當(dāng)網(wǎng)絡(luò)性能達(dá)到目標(biāo)要求時，結(jié)束訓(xùn)練，并以此網(wǎng)絡(luò)作為被測軟件的功能模型；如果網(wǎng)絡(luò)訓(xùn)練次數(shù)超過一個預(yù)先設(shè)定的值仍不能滿足其性能要求，則終止訓(xùn)練，認(rèn)為無法構(gòu)建此被測軟件的功能模型.

BP神經(jīng)網(wǎng)絡(luò)模型一般由3層神經(jīng)元構(gòu)成，即輸入層、輸出層和隱層.由于被構(gòu)建網(wǎng)絡(luò)將作為被測軟件的功能模型，因此，輸入層和輸出層神經(jīng)元數(shù)由被測軟件輸入、輸出變量的個數(shù)決定，即網(wǎng)絡(luò)輸入層神經(jīng)元個數(shù)為輸入變量的個數(shù)，輸出層神經(jīng)元個數(shù)為輸出變量的個數(shù)，BP神經(jīng)網(wǎng)絡(luò)的輸入輸出和被測軟件的輸入輸出一一對應(yīng).隱層神經(jīng)元個數(shù)的選擇是一個十分復(fù)雜的問題，目前并沒有一個公認(rèn)或統(tǒng)一的理論指導(dǎo).在實(shí)際設(shè)計過程中，常采用試湊法，根據(jù)經(jīng)驗(yàn)大致估算其個數(shù)，然后在實(shí)踐中通過訓(xùn)練確定.對于網(wǎng)絡(luò)輸入，利用相應(yīng)轉(zhuǎn)移函數(shù)實(shí)現(xiàn)從輸入到隱層輸出再到網(wǎng)絡(luò)輸出的轉(zhuǎn)化.由于對數(shù)S型函數(shù)本身及其導(dǎo)數(shù)的連續(xù)性，適合于處理非線性映射關(guān)系，因此隱層神經(jīng)元輸出的計算采用對數(shù)S型轉(zhuǎn)移函數(shù).輸出層神經(jīng)元的計算則采用線性轉(zhuǎn)移函數(shù).網(wǎng)絡(luò)具體結(jié)構(gòu)如圖1所示.

(1)

其中，i=1,2,…,n,n為樣本個數(shù)，xi表示第i個樣本中某個輸入(或輸出)變量的值，xmin和xmax代表此變量取值范圍的最小值和最大值.

Fig. 1　Structure of neural network.圖1　神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

最后用歸一化處理后的樣本數(shù)據(jù)對BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，即通過對樣本的學(xué)習(xí)，不斷改變網(wǎng)絡(luò)的參數(shù)，使網(wǎng)絡(luò)輸出不斷地接近期望的輸出.由于標(biāo)準(zhǔn)的BP訓(xùn)練算法其網(wǎng)絡(luò)泛化能力不強(qiáng)，即網(wǎng)絡(luò)訓(xùn)練結(jié)束后，對新的非樣本數(shù)據(jù)，網(wǎng)絡(luò)的預(yù)測能力不夠，不能較精確地計算出非樣本輸入對應(yīng)的輸出.網(wǎng)絡(luò)復(fù)雜是造成這一現(xiàn)象的主要原因，而貝葉斯正則化的BP訓(xùn)練算法則能夠較好地控制網(wǎng)絡(luò)的規(guī)模，簡化網(wǎng)絡(luò)，從而提高網(wǎng)絡(luò)泛化能力.因此，本文采用貝葉斯正則化的BP訓(xùn)練算法對BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，以獲得被測軟件的功能模型.

2基于輸出域的測試用例生成

在構(gòu)建的被測軟件功能模型上，利用遺傳算法實(shí)現(xiàn)基于輸出域的測試用例自動生成的思想是：對于給定的輸出(稱為目標(biāo)輸出值)，隨機(jī)生成若干組輸入作為初始種群，其中一組輸入為一個個體；計算所有個體的適應(yīng)度值，對種群中的個體進(jìn)行評估，并根據(jù)適應(yīng)度值進(jìn)行選擇、交叉、變異等遺傳操作，產(chǎn)生新一代的個體；對新種群中的個體再次進(jìn)行評估，以產(chǎn)生更新一代的種群.重復(fù)上述過程，直到種群中最優(yōu)個體的適應(yīng)度值滿足某個預(yù)先設(shè)定的值，測試生成成功，即生成給定輸出對應(yīng)的測試輸入；或遺傳操作超過設(shè)定的迭代上限，測試生成失敗，即無法找到此輸出對應(yīng)的輸入.

2.1編碼方式

應(yīng)用遺傳算法求解具體問題時，應(yīng)將被求解問題的解空間映射成適合遺傳操作的長度有限的編碼.因此，需要將被測軟件的輸入轉(zhuǎn)化成某種編碼表示的個體，以便對個體進(jìn)行選擇、交叉和變異等遺傳操作.目前有多種編碼方式，如二進(jìn)制編碼和實(shí)數(shù)編碼等.由于被測軟件的輸入和輸出多為實(shí)型數(shù)據(jù)，因此采用實(shí)數(shù)編碼方式，直接使用被測軟件的輸入數(shù)據(jù)作為個體.

例如，如果一個被測軟件有3個輸入變量，其一組輸入(2100.04142209,23.41091118,0.18077368)即為一個實(shí)數(shù)編碼的個體.

2.2適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的確定是遺傳算法實(shí)現(xiàn)的關(guān)鍵，它指導(dǎo)遺傳算法的搜索方向，使個體朝著目標(biāo)方向進(jìn)化.一般而言，適應(yīng)度值越大，表明個體越優(yōu)，它被選擇進(jìn)入下一代的概率就越大.如果個體的適應(yīng)度值大于等于某個預(yù)先設(shè)定的上限fmax，則該個體就是問題的解.

本文利用遺傳算法搜索輸出對應(yīng)的輸入，適應(yīng)度函數(shù)定義為

(2)

其中，c為當(dāng)前個體在被測軟件功能模型上計算得到的輸出值，g為給定的目標(biāo)輸出值.該適應(yīng)度函數(shù)反映了當(dāng)前輸出與目標(biāo)輸出之間的差異程度，差異越小，表明個體與目標(biāo)輸出對應(yīng)的輸入越接近，適應(yīng)度值越大.因此，該適應(yīng)度函數(shù)能夠指導(dǎo)個體向更優(yōu)的方向逼近，且計算簡單.

2.3算法描述

利用遺傳算法實(shí)現(xiàn)基于輸出域的測試用例自動生成算法如下：

算法1. 基于輸出域的測試用例自動生成算法.

Genetic Algorithm(F,n,upper[n],lower[n],popsize,Imax,g,fmax,Pc,Pm).

輸入:被測軟件的功能模型F、被測軟件輸入變量的個數(shù)n、輸入變量的取值范圍upper[n],lower[n]、種群規(guī)模popsize、最大迭代次數(shù)Imax、目標(biāo)輸出值g、設(shè)定的最大適應(yīng)度值fmax、交叉概率Pc、變異概率Pm；

輸出:最優(yōu)個體result.

population←initialize(n,upper[n],lower[n],popsize)；*隨機(jī)生成初始種群*

fitness←evaluate(F,population,g)；*計算個體適應(yīng)度值，評估個體*

repeat

iteration_number++；

population←select(population,fitness)；

population←crossover(population,fitness,Pc)；*交叉操作*

population←mutate(population,fitness,Pm)；*變異操作*

fitness←evaluate(F,population,g)；*計算個體適應(yīng)度值，評估個體*

result[n]←keep_the_best(population,fitness)；*獲取當(dāng)前種群中的最優(yōu)個體*

until

((thefitnessofresult)≥fmax) or (iteration_number>Imax)；

returnresult.

對于給定的目標(biāo)輸出值g，函數(shù)initialize隨機(jī)生成規(guī)模為popsize的初始種群population，其中每個個體由n個基因組成，對應(yīng)于被測軟件的n個輸入變量；將個體加載到被測軟件的功能模型F上，計算其適應(yīng)度值fitness，對各個個體進(jìn)行評估evaluate(F,population,g)；然后進(jìn)行選擇、交叉、變異等遺傳操作，得到新一代個體，計算新種群的最優(yōu)個體result.重復(fù)上述遺傳操作，直到種群中最優(yōu)個體result的適應(yīng)度值大于等于預(yù)先設(shè)定的上限fmax，生成輸出對應(yīng)的測試輸入；或遺傳操作超過設(shè)定的迭代次數(shù)Imax，測試生成失敗.其中，fmax的設(shè)置依賴于具體的精度要求，當(dāng)精度要求較高時，即最優(yōu)個體與目標(biāo)輸出對應(yīng)的輸入更接近，可設(shè)置fmax為一個較大的值；反之，可設(shè)置fmax為一個較小的值.

2.4選擇操作

選擇操作從父代選取相對優(yōu)良的個體進(jìn)入下一代，本文采用輪盤賭法選取父代個體.

輪盤賭法的基本思想是個體被選中的概率取決于個體的相對適應(yīng)度.顯然個體適應(yīng)度越大，被選中的概率就越大.但是，適應(yīng)度小的個體也有被選中的機(jī)率，以便增加下一代種群的多樣性.

對于種群中的n個個體來說，具體實(shí)現(xiàn)方法為：1)順序計算種群中各個個體的適應(yīng)度fi(1≤i≤n)，并計算第j個(1≤j≤n)個體的適應(yīng)度累計值Cj=f1+f2+…+fj；2)在區(qū)間[0,Cn]內(nèi)隨機(jī)生成n個均勻分布的隨機(jī)數(shù)T1,T2,…,Tn；3)在第k次(1≤k≤n)用Tk順序與C1,C2,…,Cn進(jìn)行比較，當(dāng)?shù)?次出現(xiàn)Ct≥Tk(t∈{1,2,…,n})時，選取第t個個體進(jìn)入中間代.

2.5交叉操作

(3)

原始交叉算子通常采用的交叉形式為

(4)

父代個體Xt和Yt按式(4)進(jìn)行交叉操作，即隨機(jī)產(chǎn)生一個交叉位i-1,2個父代個體從i以后的基因進(jìn)行交叉產(chǎn)生的2個新個體At+1,Bt+1替換父代個體Xt和Yt.這種交叉算子采用簡單的基因重組，父代與子代個體的變化不大.

目前一般采用的交叉算子為

(5)

其中：

(6)

為提高遺傳算法生成測試用例的效率，本文提出的交叉算子為

(7)

其中：

(8)

r∈[0,1],i=1,2,…,n.

Fig. 2　Range of the crossover gene i value.圖2　交叉基因i的取值范圍

2.6變異操作

變異操作通過對單個個體的某一位基因進(jìn)行變異，產(chǎn)生新個體.目前一般采用隨機(jī)變異，其變異算子為

(9)

其中：

(10)

針對該問題，本文提出了一種改進(jìn)的變異算子：

(11)

其中：

(12)

3實(shí)例研究

下面以計算三角形面積為被測軟件，說明本文方法及實(shí)現(xiàn)細(xì)節(jié).

3.1建立計算三角形面積軟件的功能模型

計算三角形面積功能說明要求根據(jù)輸入的3條邊，計算并輸出三角形的面積.因此，對計算三角形面積被測軟件建立3層BP神經(jīng)網(wǎng)絡(luò)，其輸入、輸出層神經(jīng)元個數(shù)分別為3和1.隱層神經(jīng)元個數(shù)則采用試湊法，根據(jù)經(jīng)驗(yàn)公式：

(13)

其中,n為輸入層節(jié)點(diǎn)數(shù)，l為輸出層節(jié)點(diǎn)數(shù)，a為10～100之間的隨機(jī)數(shù)，大致估算其個數(shù)，然后在訓(xùn)練過程中根據(jù)訓(xùn)練情況進(jìn)行調(diào)整.

隱層神經(jīng)元輸出的計算采用對數(shù)S型轉(zhuǎn)移函數(shù)：

(14)

輸出層神經(jīng)元的計算則采用簡單的線性轉(zhuǎn)移函數(shù)：

(15)

至此，3層BP神經(jīng)網(wǎng)絡(luò)設(shè)計完成.

根據(jù)計算三角形面積功能說明，隨機(jī)生成3個1～100之間的數(shù)作為三角形的3條邊輸入.若輸入滿足三角形性質(zhì)，則計算其面積輸出，此時輸入輸出對構(gòu)成一個樣本.有研究表明，網(wǎng)絡(luò)訓(xùn)練所需的樣本數(shù)可以遵照一個經(jīng)驗(yàn)規(guī)則，即訓(xùn)練樣本數(shù)是網(wǎng)絡(luò)連接權(quán)總數(shù)的5～10倍.按照這個經(jīng)驗(yàn)規(guī)則，設(shè)定樣本數(shù)目為500.為避免手工計算和編程出現(xiàn)錯誤，本文采用文獻(xiàn)[10]發(fā)布的C版本Triangle_area程序計算三角形的面積，開發(fā)了500組輸入輸出對，作為樣本數(shù)據(jù).

最后，利用美國Mathworks公司推出的MATLAB自帶神經(jīng)網(wǎng)絡(luò)工具箱，對樣本數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)訓(xùn)練.具體而言，MATLAB訓(xùn)練程序：1)對訓(xùn)練樣本中的所有輸入、輸出數(shù)據(jù)進(jìn)行歸一化處理；2)對3層BP神經(jīng)網(wǎng)絡(luò)進(jìn)行結(jié)構(gòu)設(shè)置，即確定輸入、輸出層神經(jīng)元的個數(shù)，隱層神經(jīng)元設(shè)為30個，隱層和輸出層分別采用式(14)(15)的對數(shù)S型(logsig)和線性(purelin)轉(zhuǎn)移函數(shù)，訓(xùn)練算法則為貝葉斯正則化的BP算法(trainbr)；3)設(shè)置訓(xùn)練參數(shù)，包括最大迭代次數(shù)，訓(xùn)練目標(biāo)等;4)使用歸一化的樣本數(shù)據(jù)對網(wǎng)絡(luò)進(jìn)行訓(xùn)練.當(dāng)訓(xùn)練迭代到3 302次時，網(wǎng)絡(luò)誤差為0.576E-4，小于目標(biāo)要求1E-3，訓(xùn)練成功.MATLAB訓(xùn)練程序如下：

functionTrain()*訓(xùn)練程序*

p=GuiYi(r)；*樣本輸入數(shù)據(jù)歸一化*

t=GuiYi(w)；*樣本輸出數(shù)據(jù)歸一化*

net=newff(minmax(p),[3,30,1],

{‘logsig’,‘purelin’},‘trainbr’)；*設(shè)定網(wǎng)絡(luò)結(jié)構(gòu)*

net.trainParam.epochs=10 000;*設(shè)定最大迭代次數(shù)*

net.trainParam.goal=1E-3；*設(shè)定訓(xùn)練目標(biāo)，即網(wǎng)絡(luò)誤差*

[net,tr]=train(net,p,t)；*使用歸一化后的樣本數(shù)據(jù)對網(wǎng)絡(luò)進(jìn)行訓(xùn)練*

Fig. 4　Test Generation effectiveness based output of triangle area software.圖4　計算三角形面積軟件基于輸出的測試生成效果

用訓(xùn)練成功時的網(wǎng)絡(luò)作為計算三角形面積軟件的功能模型，能否較好地模擬計算三角形面積軟件的功能呢?為此，本文又開發(fā)了100組非樣本的輸入輸出對，將輸入數(shù)據(jù)加載到此功能模型，計算其輸出并與樣本輸出期望進(jìn)行比較，結(jié)果如圖3所示，可以看出該功能模型能夠很好地替代計算三角形面積軟件進(jìn)行工作.

Fig. 3　Comparison between outputs from software functional model and expected outputs.圖3　軟件功能模型輸出與期望輸出的比較

3.2測試用例自動生成

以該功能模型代替計算三角形面積軟件，利用遺傳算法進(jìn)行基于輸出域的測試用例自動生成，即已知三角形面積求其對應(yīng)的3條邊.具體實(shí)現(xiàn)過程如下：隨機(jī)生成一個數(shù)，如440，作為三角形的面積(目標(biāo)輸出)，隨機(jī)生成50組三元組作為初始種群，以每個三元組為該功能模型的輸入并計算其輸出，將輸出與目標(biāo)輸出進(jìn)行比較并按式(2)計算其適應(yīng)度值.若適應(yīng)度值大于1 000，則該功能模型的輸出與給定面積之間的差異很小，對應(yīng)輸入可作為三角形的三條邊；否則使用輪盤賭策略選取父代個體，按式(7)進(jìn)行交叉操作，再對每個個體按式(11)進(jìn)行變異操作并從中選取適應(yīng)度較高者取代父代個體，形成新的種群.重復(fù)上述操作，當(dāng)遺傳進(jìn)化迭代到第49代時，個體(16.8，65.7，57.5)的適應(yīng)度值為1 307.354，大于1 000，算法終止.表明當(dāng)以440為三角形面積時，(16.8，65.7，57.5)即為生成的測試輸入.

對于計算三角形面積軟件，本文設(shè)定最大迭代次數(shù)為500，隨機(jī)生成100組10～4 000之間的數(shù)作為三角形的面積，在此功能模型上利用遺傳算法搜索其對應(yīng)輸入，所需迭代次數(shù)如圖4所示，其最高點(diǎn)表示在500次迭代中沒有找到對應(yīng)的輸入.從圖4可以看出，在100組目標(biāo)輸出中僅有19組沒有發(fā)現(xiàn)對應(yīng)的輸入，其搜索成功率為81%；并且對于大多數(shù)的目標(biāo)輸出，都能以較低的迭代次數(shù)找到對應(yīng)的輸入，其測試生成效率較高.

4實(shí)驗(yàn)結(jié)果與分析

為進(jìn)一步驗(yàn)證本文提出的利用遺傳算法實(shí)現(xiàn)基于輸出域的測試用例自動生成方法，作者以香港中文大學(xué)開發(fā)的容錯軟件RSDIMU子模塊、計算弧長度、求三角形面積、求定積分4個軟件作為被測軟件進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明：該方法具有良好的可行性和有效性.

4.1功能模型模擬實(shí)驗(yàn)

RSDIMU子模塊、計算弧長度、求三角形面積、求定積分這4個被測軟件的主要特征如表1 所示：

Table 1　Parameters of the Software Under Test

對于每個被測軟件，其BP神經(jīng)網(wǎng)絡(luò)的初始網(wǎng)絡(luò)結(jié)構(gòu)、樣本數(shù)、訓(xùn)練迭代次數(shù)和訓(xùn)練成功后得到的網(wǎng)絡(luò)性能參數(shù)如表2所示.其中RSDIMU子模塊399個樣本根據(jù)文獻(xiàn)[11]的測試用例修改得到，其他3個軟件則從文獻(xiàn)[10]上下載相應(yīng)的程序，隨機(jī)生成500組輸入，運(yùn)行程序得到輸出，構(gòu)建樣本庫.

Table 2　Training Parameters of the Neural Network

網(wǎng)絡(luò)性能參數(shù)體現(xiàn)了網(wǎng)絡(luò)實(shí)際輸出與期望輸出之間的差異程度，表2中的網(wǎng)絡(luò)性能參數(shù)都很小，表明網(wǎng)絡(luò)實(shí)際輸出與期望輸出非常接近，網(wǎng)絡(luò)性能較好，可以作為被測軟件的功能模型.

建立被測軟件的功能模型后，對每個被測軟件開發(fā)了100組非樣本輸入輸出對，將輸入加載到構(gòu)建的功能模型上，運(yùn)行計算實(shí)際輸出，與期望輸出進(jìn)行擬合比較.實(shí)驗(yàn)結(jié)果如圖5～8所示，表明被構(gòu)建的功能模型實(shí)際輸出與期望輸出的偏差極小，能夠替代被測軟件，模擬被測軟件的功能.

Fig. 5　Output fitting(Subroutine of RSDIMU).圖5　輸出擬合(RSDIMU子模塊)

Fig. 6　Output fitting (Arc_length).圖6　輸出擬合(Arc_length)

Fig. 7　Output fitting (Triangle_area).圖7　輸出擬合(Triangle_area)

Fig. 8　Output fitting (Integral).圖8　輸出擬合(Integral)

4.2測試用例生成實(shí)驗(yàn)及分析

在構(gòu)建的被測軟件功能模型上，對于給定的輸出，利用遺傳算法搜索對應(yīng)的輸入值，實(shí)現(xiàn)基于輸出域的測試用例自動生成.實(shí)驗(yàn)假設(shè)初始種群規(guī)模popsize=50，最大適應(yīng)度值fmax=1 000，最大迭代次數(shù)Imax=500，交叉概率Pc=0.8，變異概率Pm=0.15.對表1所示的每個被測軟件，隨機(jī)生成了100組輸出作為目標(biāo)輸出，分別使用原始遺傳算法、一般遺傳算法和本文改進(jìn)的遺傳算法生成測試輸入.3種遺傳算法的不同之處在于：原始遺傳算法采用原始交叉算子(式(4))和隨機(jī)變異(式(9))；一般遺傳算法采用交叉算子(式(5))和隨機(jī)變異；改進(jìn)的遺傳算法采用本文提出的交叉算子(式(7))和變異算子(式(11)).3種算法的測試生成效率(迭代次數(shù))和成功率如表3和表4所示.

Table 3Comparison of the Test Generation Efficiency for Three Genetic Algorithms

表3　3種遺傳算法測試生成效率比較

Table 4Comparison of the Successful Test Generation Ratio for Three Genetic Algorithms

表4　3種遺傳算法測試生成的成功率比較　%

顯然，采用本文改進(jìn)的遺傳算法，測試生成效率較高，能夠很快搜索到目標(biāo)輸出對應(yīng)的輸入，并且成功率較高，平均為85%.而原始遺傳算法和一般遺傳算法的測試生成效率和成功率都較低，尤其是原始遺傳算法，對于被測軟件Triangle_area和Integral，無法在500次迭代中搜索到對應(yīng)的測試輸入.分析其原因，主要是因?yàn)檫@2個被測軟件輸入變量的取值范圍較大，利用原始遺傳算法和一般遺傳算法交叉算子產(chǎn)生的子代個體與父代個體差異不大，容易收斂于某個局部極小點(diǎn)，從而導(dǎo)致算法搜索失敗.對被測軟件Triangle_area的測試生成失效數(shù)據(jù)進(jìn)行仔細(xì)分析，也說明了這一點(diǎn).例如，對于Triangle_area的一個目標(biāo)輸出值440，使用原始遺傳算法、一般遺傳算法和改進(jìn)的遺傳算法搜索其對應(yīng)的測試輸入，進(jìn)化過程如圖9所示，其中橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為種群最優(yōu)個體的適應(yīng)度值，圖10是圖9的局部放大圖.采用改進(jìn)的遺傳算法，其進(jìn)化速度即最優(yōu)個體的適應(yīng)度值增長速度較快，當(dāng)進(jìn)化到第49代種群時，最優(yōu)個體的適應(yīng)度已超過1 000、為1 307.354，

Fig. 9　Comparison of the evolutionary process for three genetic algorithms.圖9　3種遺傳算法的進(jìn)化過程比較

Fig. 10　Enlarged local part of Fig.9.圖10　圖9的局部放大圖

測試生成成功，此時目標(biāo)輸出值對應(yīng)的輸入為(16.8,65.7,57.5).而原始遺傳算法和一般遺傳算法則進(jìn)化速度較慢，當(dāng)分別進(jìn)化到第112和24代種群之后，其最優(yōu)個體的適應(yīng)度值一直保持在12.284和33.455，陷入局部極小點(diǎn)，無法生成目標(biāo)輸出值對應(yīng)的測試輸入.

5結(jié)論和進(jìn)一步的工作

對于某些軟件來說，輸出域存在許多值得關(guān)注的檢測點(diǎn)，這些軟件適合從輸出域出發(fā)開發(fā)測試用例，而對于給定的輸出，獲得相應(yīng)的輸入較為困難.本文提出了一種基于輸出域的測試用例自動生成方法，該方法首先使用神經(jīng)網(wǎng)絡(luò)構(gòu)建被測軟件的功能模型，然后在此功能模型上，對于給定的輸出，利用遺傳算法搜索相應(yīng)的輸入，實(shí)現(xiàn)基于輸出域的測試用例自動生成.同時對遺傳算法進(jìn)行了改進(jìn)，提出了一種新的交叉算子和變異算子，以提高遺傳算法的搜索效率.實(shí)驗(yàn)結(jié)果表明，本文提出的利用遺傳算法實(shí)現(xiàn)從輸出到輸入的測試用例自動生成方法是行之有效的，改進(jìn)的交叉算子和變異算子能夠在很大程度上提高基于輸出域的測試用例生成效率和成功率.

本文進(jìn)一步的工作是探索如何將多目標(biāo)的遺傳算法應(yīng)用于基于輸出域的測試用例自動生成，以實(shí)現(xiàn)多個輸出變量的測試輸入自動生成，并進(jìn)一步提高測試生成的效率.

參考文獻(xiàn)

[1]Vanmali M, Last M, Kandel A. Using a neural network in the software testing process [J]. International Journal of Intelligent Systems, 2002, 17(1): 45-62

[2]Bhasin H, Singla N. Cellular-genetic test data generation [J]. ACM SIGSOFT Software Engineering Notes, 2013, 38(5): 1-9

[3]He Yanxiang, Chen Yong, Wu Wei, et al. Automatically generating error-traceable test cases based on compiler[J]. Journal of Computer Research and Development, 2012, 49(9): 1843-1851 (in Chinese)(何炎祥, 陳勇, 吳偉, 等. 基于編譯支持錯誤跟蹤的測試用例自動化生成方法[J]. 計算機(jī)研究與發(fā)展, 2012, 49(9): 1843-1851)

[4]Aggarwal K K, Singh Y, Kaur A, et al. A neural net based approach to test oracle[J]. ACM SIGSOFT Software Engineering Notes, 2004, 29(4): 1-6

[5]Grznar J, Prasad S, Tata J. Neural networks and organizational systems: Modeling non-linear relationships [J]. European Journal of Operational Research, 2006, 181(2): 939-955

[6]Pinto G H L, Vergilio S R. A multi-objective genetic algorithm to test data generation[C]Proc of the 22nd IEEE Int Conf on Tools with Artificial Intelligence. Piscataway, NJ: IEEE, 2010: 129-134

[7]Chen J F, Yang L M. Towards automatic generation of test data using branch coverage[C]Proc of the 4th IEEE Int Conf on Computer Science & Education. Piscataway, NJ: IEEE, 2009: 921-925

[8]Deepak A, Samuel P. An evolutionary multi population approach for test data generation[C]Proc of World Congress on Nature & Biologically Inspired Computing. Piscataway, NJ: IEEE, 2009: 1451-1456

[9]Zhao R L, Li C C. Automatic test case generation of non-numerical data based on genetic algorithms[C]Proc of the 9th IASTED Int Conf on Software Engineering and Applications. Anaheim, CA: ACTA, 2005: 212-217

[10]PlanetSourceCode. CC++ free code: PlanetSourceCode[EBOL]. [2013-11-12]. http:www.Planet-Source-Code.com

[11]Zhao Ruilian, Dong Hongxia. An effective strategy for selecting boundary test points[J]. Journal of Computer-Aided Design and Computer Graphics, 2007, 19(2): 251-255 (in Chinese)(趙瑞蓮, 董紅霞. 一種有效的邊界測試點(diǎn)選取策略[J].計算機(jī)輔助設(shè)計與圖形學(xué)報, 2007, 19(2): 251-255)

You Feng, born in 1963. Associate professor. His main research interests include software test and large data analysis.

Zhao Ruilian, born in 1964.Professor and PhD supervisor. Member of China Computer Federation. Her main research interests include software test and software reliability.

Lü Shanshan, born in 1983. Master in Beijing University of Chemical Technology. Her main research interests include software test and software reliability.

中圖法分類號TP311.5

通信作者：趙瑞蓮(rlzhao@mail.buct.edu.cn)

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61472025，61170082)

收稿日期：2014-09-19；修回日期：2015-05-14

This work was supported by the National Natural Science Foundation of China (61472025，61170082).