馬竹根

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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

1 基本路徑測(cè)試法

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

1.1 程序控制流圖

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

1.2 圈復(fù)雜度

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

⑴ V（G）=E-N+2

其中V（G）表示圈復(fù)雜度，E表示控制流圖的邊的數(shù)量，N 表示控制流圖的節(jié)點(diǎn)個(gè)數(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)一個(gè)新的處理語(yǔ)句集合或一個(gè)新條件的任一路徑，即獨(dú)立路徑必須至少包含一條在定義路徑之前不曾用過(guò)的邊的路徑。對(duì)于一個(gè)復(fù)雜的程序，在使用基本路徑測(cè)試時(shí)，其獨(dú)立路徑數(shù)量的上界是由程序的圈復(fù)雜度來(lái)確定的，而且這一獨(dú)立路徑數(shù)能夠保證程序中所有語(yǔ)句至少被執(zhí)行一次。

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

為了確保基本路徑集中每一條路徑的執(zhí)行，根據(jù)判斷結(jié)點(diǎn)給出的條件，選擇適當(dāng)?shù)臄?shù)據(jù)以保證每一條路徑可以被測(cè)試到。

2 智能水滴算法

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

⑴

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

⑵

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

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

⑶

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

⑷

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

智能水滴移動(dòng)時(shí)間正比于位置i到位置j之間的距離，反比于水滴的移動(dòng)速度。

⑸

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

⑹

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

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

⑺

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

⑻

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

⑼

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

⑽

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

⑾

其中

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

⑿

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

3 智能水滴算法測(cè)試用例生成方法

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

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

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

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

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

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

初始化：

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

表1中簡(jiǎn)要描述了路徑的發(fā)現(xiàn)過(guò)程。從控制流圖頂端結(jié)點(diǎn)1（Node-1）開(kāi)始，它有二條可能的路徑，即：結(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í)間參數(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é)束語(yǔ)

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

參考文獻(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)化測(cè)試用例生成方法[J].軟件學(xué)報(bào)，2016.27（4）：1-17

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

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

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

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

[8] 王博，王曙燕.一種新的基于模擬退火的測(cè)試用例生成與約簡(jiǎn)算法[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] 陳夢(mèng)云，高建華.基于圈復(fù)雜度的靜態(tài)測(cè)試用例排序方法[J].計(jì)算機(jī)應(yīng)用與軟件，2016.33（1）：1-3

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