馬竹根

摘 要： 提出基于智能水滴算法的測試用例生成方法，描述了如何把測試用例的生成問題轉(zhuǎn)換成智能水滴在控制流圖的各邊之間尋找最優(yōu)路徑的問題，討論了利用智能水滴算法發(fā)現(xiàn)控制流圖中的測試路徑的算法。該方法利用控制流圖的圈復(fù)雜度和自然界水滴的基本屬性，使用動態(tài)參數(shù)來發(fā)現(xiàn)控制流圖中的獨(dú)立路徑，能通過自動生成測試路徑保證完全的代碼覆蓋。

關(guān)鍵詞： 控制流圖； 圈復(fù)雜度； 獨(dú)立路徑； 智能水滴算法； 測試用例生成

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2016）05-73-05

Abstract： This paper proposes a automatic test case generation method based on intelligent water drop algorithm， and describes how to convert the problem of test case generation into the problem that intelligent water drop searches the optimal path in between the each side of the control flow graph. The method uses the cyclomatic complexity of the control flow graph and the basic properties of the water droplet， and uses the dynamic parameters to find the independent paths in the control flow graph， which can ensure the complete code coverage by automatic generation of test paths.

Key words： control flow graph； cyclomatic complexity； independent path； intelligent water drop algorithm； test case generation

0 引言

軟件測試是保證軟件質(zhì)量的重要手段，軟件測試在軟件開發(fā)和維護(hù)過程中是花費(fèi)最多的一個階段。將軟件測試環(huán)節(jié)自動化，將極大地降低開發(fā)成本和提高軟件可靠性。實(shí)現(xiàn)軟件自動測試的核心是生成能發(fā)現(xiàn)軟件錯誤或缺陷的有效的測試數(shù)據(jù)，以滿足既定的測試充分性準(zhǔn)則?；谒阉鞯臏y試用例生成技術(shù)[1]可以利用適應(yīng)度函數(shù)，將測試用例生成問題轉(zhuǎn)化成函數(shù)優(yōu)化問題，進(jìn)而利用一些人工智能搜索算法尋找最優(yōu)解，最終達(dá)到程序所要求的覆蓋標(biāo)準(zhǔn)。人工智能搜索算法種類有很多，近年來，研究人員開始使用遺傳算法[2]、粒子群優(yōu)化算法[3-4]、蜂群算法[5]、神經(jīng)網(wǎng)絡(luò)[6]、蟻群算法[7]、模擬退火算法[8]等智能優(yōu)化算法來解決軟件測試中的測試用例的生成問題。

本文使用一種新的啟發(fā)式算法——智能水滴算法（Intelligent Water Drops algorithms）[9]生成測試用例，使用基本路徑作為測試充分性準(zhǔn)則，從而使用較少的時間和花費(fèi)得到有效的測試用例。

1 基本路徑測試法

基本路徑測試法是在程序控制流圖的基礎(chǔ)上，通過分析控制結(jié)構(gòu)的圈復(fù)雜度，導(dǎo)出基本可執(zhí)行的路徑集合，從而設(shè)計(jì)測試用例的方法。通?；韭窂綔y試法包括程序控制流圖、計(jì)算程序圈復(fù)雜度、確定基本路徑集、導(dǎo)出測試用例。

1.1 程序控制流圖

程序控制流圖是對程序流程圖簡化后得到的，它可以更加突出的表示程序控制流的結(jié)構(gòu)。程序中的語句構(gòu)成控制流圖中的節(jié)點(diǎn)，并由帶箭頭的曲線將節(jié)點(diǎn)按照程序執(zhí)行順序進(jìn)行連接。

1.2 圈復(fù)雜度

圈復(fù)雜度是一種代碼復(fù)雜度衡量標(biāo)準(zhǔn)[10]，常用于評估一個模塊判定結(jié)構(gòu)的復(fù)雜程度，在數(shù)值上等價于獨(dú)立運(yùn)行的路徑條數(shù)。圈復(fù)雜度是根據(jù)控制流圖中的邊和節(jié)點(diǎn)來計(jì)算的，圈復(fù)雜度計(jì)算公式有以下三種。

⑴ V（G）=E-N+2

其中V（G）表示圈復(fù)雜度，E表示控制流圖的邊的數(shù)量，N 表示控制流圖的節(jié)點(diǎn)個數(shù)。

⑵ 圈復(fù)雜度等于控制流圖中判定節(jié)點(diǎn)的數(shù)量加1。

V（G）=P+1，P表示判定節(jié)點(diǎn)數(shù)

⑶ 圈復(fù)雜度等于控制流圖將平面劃分成區(qū)域的數(shù)量。

V（G）=R，R表示區(qū)域數(shù)

1.3 基本路徑集

基本路徑集由獨(dú)立路徑組成。獨(dú)立路徑是指，程序中至少引進(jìn)一個新的處理語句集合或一個新條件的任一路徑，即獨(dú)立路徑必須至少包含一條在定義路徑之前不曾用過的邊的路徑。對于一個復(fù)雜的程序，在使用基本路徑測試時，其獨(dú)立路徑數(shù)量的上界是由程序的圈復(fù)雜度來確定的，而且這一獨(dú)立路徑數(shù)能夠保證程序中所有語句至少被執(zhí)行一次。

1.4 生成測試數(shù)據(jù)

為了確?；韭窂郊忻恳粭l路徑的執(zhí)行，根據(jù)判斷結(jié)點(diǎn)給出的條件，選擇適當(dāng)?shù)臄?shù)據(jù)以保證每一條路徑可以被測試到。

2 智能水滴算法

智能水滴算法由Hamed Shah-Hosseini于2007年提出[9]。智能水滴（Intelligent Water Drop，IWD），它具有以下兩個重要的屬性：水滴攜帶的泥土量soil（IWD）和水滴的速度velocity（IWD），這兩個屬性會隨著水滴流動而發(fā)生變化。水滴從當(dāng)前位置i移動到下一個位置j，其速度值的增量定義為Δvelocity（IWD），水滴的速度增量非線性反比于從位置i到j(luò)路徑上的泥土量soil（i，j）。

⑴

其中符號表示非線性正比關(guān)系，計(jì)算公式為：

⑵

其中av，bv，cv是用戶選定的參數(shù)。

由于從位置i到位置j的路徑中帶走了部分泥土，智能水滴中攜帶的泥土量soil（IWD）也會相應(yīng)增加。路徑當(dāng)中減少的泥土量和智能水滴中增加的泥土量是相等的，即：

⑶

泥土的增量非線性反比于水滴從當(dāng)前位置i移動到下一位置j的時間time（i，j），其計(jì)算公式為：

⑷

其中as，bs，cs都是大于0的參數(shù)。

智能水滴移動時間正比于位置i到位置j之間的距離，反比于水滴的移動速度。

⑸

下面給出一種計(jì)算智能水滴由位置i到位置j的時間公式：

⑹

這里沒有直接使用位置i到位置j的距離d（i，j），而是使用了更廣義的反向啟發(fā)函數(shù) HUD（Heuristie undesirability）。HUD（i，j）表示了智能水滴拒絕從位置i移動到位置j的程度，在實(shí)際的優(yōu)化問題中代表了優(yōu)化依據(jù)的條件。

在位置i到位置j的路徑上，由于智能水滴的移動而帶走了一定量的泥土，路徑當(dāng)中的剩余的泥土量用soil（i，j）表示，它與路徑中失去的泥土量Δsoil（i，j）成正比。

⑺

從位置i到位置j路徑當(dāng)中的泥土量通過由智能水滴帶走的泥土量來更新，計(jì)算公式為：

⑻

而智能水滴中攜帶的泥土量soil（IWD）按照以下公式更新：

⑼

智能水滴在遇到多條可選路徑時，會更傾向于選擇泥土量較少的路徑。對于智能水滴可能選擇的多個下一位置，每個位置以一定的概率被選擇。以p（i，j）代表智能水滴在位置i時選擇j作為下一位置的概率，它與路徑當(dāng)中的泥土量成反比。

⑽

在位置i與位置j之間的路徑上泥土量越少，則位置j越有可能被在位置i的智能水滴選擇作為下一步移動的位置。一種可能的計(jì)算下一步位置概率的表達(dá)式如下：

⑾

其中

ε是很小的正數(shù)，用來防止函數(shù)f的分母為0。函數(shù)g用來確保將位置i與位置j之間的路徑泥土量轉(zhuǎn)換為正數(shù)，其表達(dá)式為：

⑿

函數(shù)min表示當(dāng)前位置與所有可能選擇的下一個位置之間泥土量的最小值。

3 智能水滴算法測試用例生成方法

許多軟件測試問題可歸結(jié)為基本路徑測試數(shù)據(jù)生成問題，可描述為[13]：給定程序的一條目標(biāo)路徑，在程序的輸入空間中尋找測試數(shù)據(jù)，使得以該數(shù)據(jù)為輸入，所經(jīng)過的路徑為目標(biāo)路徑。測試數(shù)據(jù)的生成過程就是根據(jù)一定的規(guī)則，對被測試程序的輸入空間進(jìn)行抽樣的過程。因此可以把測試數(shù)據(jù)生成問題轉(zhuǎn)化為一個優(yōu)化問題，利用智能優(yōu)化算法來求解。智能水滴算法在很多優(yōu)化問題中得到了應(yīng)用，本文應(yīng)用智能水滴算法來生成測試數(shù)據(jù)。

智能水滴算法生成測試用例的過程可分為二個主要階段。第一階段利用分析工具（如LEX和YACC）生成包含控制流圖的輸出文件。第二個階段對控制流圖進(jìn)行處理，可分為以下三個步驟。

⑴ 分析控制流圖中每一個結(jié)點(diǎn)的圈復(fù)雜度。

⑵ 利用智能水滴算法在控制流圖中從開始結(jié)點(diǎn)到終端結(jié)點(diǎn)遍歷得到所有可能的獨(dú)立路徑。

⑶ 對每一條獨(dú)立路徑生成測試數(shù)據(jù)。

算法：智能水滴算法獲取控制流圖中獨(dú)立路徑

初始化：

程序控制流圖如圖1所示。

表1中簡要描述了路徑的發(fā)現(xiàn)過程。從控制流圖頂端結(jié)點(diǎn)1（Node-1）開始，它有二條可能的路徑，即：結(jié)點(diǎn)2（Node-2）或結(jié)點(diǎn)7（Node-7），根據(jù)算法計(jì)算出概率適應(yīng)度p（1，2）=0.9，p（1，7）=0.1。概率值越大選擇這條路徑的概率越大，因此選擇路徑p（1，2）。從Node-1到Node-2速度更新按算法中的第5步計(jì)算，Vel（IWD）=200.1，算法中第6步更新時間參數(shù)，計(jì)算公式為time（1，2）=HUD（2）/Vel（IWD）=90/200.1=0.45，這里HUD（2）=10（控制流圖的圈復(fù)雜度）*9（Node-2的圈復(fù)雜度）=90。算法中第7步按公式計(jì)算泥土的變化Δsoil（1，2）=1.469，算法中第8步更新智能水滴從Node-1到Node-2帶走的泥土Soil（IWD）=1.469。算法第9步更新Node-1和Node-2之間路徑上的泥土：

5 結(jié)束語

測試用例的生成是軟件測試的重要內(nèi)容，高效的軟件測試用例自動生成方法可以簡化軟件測試過程，減少軟件測試時間和資源消耗，提高測試效率和測試質(zhì)量。本文將面向路徑的測試數(shù)據(jù)生成問題轉(zhuǎn)化成最優(yōu)化問題，提出了使用智能水滴算法自動發(fā)現(xiàn)測試路徑的策略，算法的輸出包含所有的獨(dú)立路徑。本文著重介紹了應(yīng)用智能水滴算法解決軟件測試數(shù)據(jù)生成問題的方法和技術(shù)，并給出了具體的應(yīng)用實(shí)例。實(shí)驗(yàn)結(jié)果表明，基于智能水滴算法的測試實(shí)例能夠在更小的迭代次數(shù)之內(nèi)收斂，并得到最優(yōu)結(jié)果。下一步的研究工作需對測試用例的生成進(jìn)行優(yōu)化，算法中可加入一些啟發(fā)式算法來提高效率。

參考文獻(xiàn)（References）：

[1] Harman M， Jones BF. Search based software engineering[J].Information and Software Technology，2001.43（14）：833-839

[2] Miller J， Reformat M， Zhang H. Automatic test datageneration using genetic algorithm and program dependence graphs[J]. Information and Software Technology，2006.48：586-605

[3] 姜淑娟，王令賽，薛猛等.基于模式組合的粒子群優(yōu)化測試用例生成方法[J].軟件學(xué)報，2016.27（4）：1-17

[4] 毛澄映，喻新欣，薛云志.基于粒子群優(yōu)化的測試數(shù)據(jù)生成及其實(shí)證分析[J].計(jì)算機(jī)研究與發(fā)展，2014.51（4）：824-837

[5] 李云瑋，孫忱，范玉順.基于智能非信息素蜂群優(yōu)化的軟件測試研究[J].計(jì)算機(jī)應(yīng)用研究，2014.31（8）：2399-2403

[6] 李鑫.基于神經(jīng)網(wǎng)絡(luò)的路徑覆蓋測試數(shù)據(jù)生成[D].中國礦業(yè)大學(xué)，2014.

[7] 傅博.基于蟻群算法的軟件測試數(shù)據(jù)自動生成[J].計(jì)算機(jī)工程與應(yīng)用，2007.43（12）：97-99

[8] 王博，王曙燕.一種新的基于模擬退火的測試用例生成與約簡算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013.30（2）：78-81

[9] H. S. Hosseini. Problem solving by intelligent water drops[A].IEEE Congress on Evolutionary Computation[C]， Washington， DC， USA： IEEE Computer Society，2007.3226-3231

[10] 陳夢云，高建華.基于圈復(fù)雜度的靜態(tài)測試用例排序方法[J].計(jì)算機(jī)應(yīng)用與軟件，2016.33（1）：1-3

[11] 鞏敦衛(wèi)，姚香娟，張巖.測試數(shù)據(jù)進(jìn)化生成理論及應(yīng)用[M].科學(xué)出版社，2014.