基于智能水滴算法的軟件路徑測試用例生成方法

馬竹根

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

關鍵詞： 控制流圖； 圈復雜度； 獨立路徑； 智能水滴算法； 測試用例生成

中圖分類號：TP301.6 文獻標志碼：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 引言

軟件測試是保證軟件質量的重要手段，軟件測試在軟件開發和維護過程中是花費最多的一個階段。將軟件測試環節自動化，將極大地降低開發成本和提高軟件可靠性。實現軟件自動測試的核心是生成能發現軟件錯誤或缺陷的有效的測試數據，以滿足既定的測試充分性準則。基于搜索的測試用例生成技術[1]可以利用適應度函數，將測試用例生成問題轉化成函數優化問題，進而利用一些人工智能搜索算法尋找最優解，最終達到程序所要求的覆蓋標準。人工智能搜索算法種類有很多，近年來，研究人員開始使用遺傳算法[2]、粒子群優化算法[3-4]、蜂群算法[5]、神經網絡[6]、蟻群算法[7]、模擬退火算法[8]等智能優化算法來解決軟件測試中的測試用例的生成問題。

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

1 基本路徑測試法

基本路徑測試法是在程序控制流圖的基礎上，通過分析控制結構的圈復雜度，導出基本可執行的路徑集合，從而設計測試用例的方法。通常基本路徑測試法包括程序控制流圖、計算程序圈復雜度、確定基本路徑集、導出測試用例。

1.1 程序控制流圖

程序控制流圖是對程序流程圖簡化后得到的，它可以更加突出的表示程序控制流的結構。程序中的語句構成控制流圖中的節點，并由帶箭頭的曲線將節點按照程序執行順序進行連接。

1.2 圈復雜度

圈復雜度是一種代碼復雜度衡量標準[10]，常用于評估一個模塊判定結構的復雜程度，在數值上等價于獨立運行的路徑條數。圈復雜度是根據控制流圖中的邊和節點來計算的，圈復雜度計算公式有以下三種。

⑴ V（G）=E-N+2

其中V（G）表示圈復雜度，E表示控制流圖的邊的數量，N 表示控制流圖的節點個數。

⑵ 圈復雜度等于控制流圖中判定節點的數量加1。

V（G）=P+1，P表示判定節點數

⑶ 圈復雜度等于控制流圖將平面劃分成區域的數量。

V（G）=R，R表示區域數

1.3 基本路徑集

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

1.4 生成測試數據

為了確保基本路徑集中每一條路徑的執行，根據判斷結點給出的條件，選擇適當的數據以保證每一條路徑可以被測試到。

2 智能水滴算法

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

⑴

其中符號表示非線性正比關系，計算公式為：

⑵

其中av，bv，cv是用戶選定的參數。

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

⑶

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

⑷

其中as，bs，cs都是大于0的參數。

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

⑸

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

⑹

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

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

⑺

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

⑻

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

⑼

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

⑽

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

⑾

其中

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

⑿

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

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

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

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

⑴ 分析控制流圖中每一個結點的圈復雜度。

⑵ 利用智能水滴算法在控制流圖中從開始結點到終端結點遍歷得到所有可能的獨立路徑。

⑶ 對每一條獨立路徑生成測試數據。

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

初始化：

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

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

5 結束語

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

參考文獻（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] 姜淑娟，王令賽，薛猛等.基于模式組合的粒子群優化測試用例生成方法[J].軟件學報，2016.27（4）：1-17

[4] 毛澄映，喻新欣，薛云志.基于粒子群優化的測試數據生成及其實證分析[J].計算機研究與發展，2014.51（4）：824-837

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

[6] 李鑫.基于神經網絡的路徑覆蓋測試數據生成[D].中國礦業大學，2014.

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

[8] 王博，王曙燕.一種新的基于模擬退火的測試用例生成與約簡算法[J].計算機應用與軟件，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] 陳夢云，高建華.基于圈復雜度的靜態測試用例排序方法[J].計算機應用與軟件，2016.33（1）：1-3

[11] 鞏敦衛，姚香娟，張巖.測試數據進化生成理論及應用[M].科學出版社，2014.