,

( 國網天津市電力公司 信息通信公司,天津 300010)

0 引言

計算機技術的不斷發(fā)展，軟件的使用范圍以及軟件自身質量都顯得越來越重要。軟件測試作為軟件質量保證的主要手段，在實際應用中往往由于要占據大約50%的運行時間和50%以上的軟件開發(fā)總成本，導致軟件測試費時費力[1-2]。自動化測試數據生成是軟件測試中的一個關鍵問題，其實施不僅可以顯著提高效率，而且可以降低軟件測試的高成本[3]。特別值得注意的是，各種結構測試數據生成問題可以轉化為面向路徑的測試數據生成問題。此外，路徑測試策略可以檢測到將近65個測試程序中的錯誤。

雖然路徑測試下的測試數據生成是一個很難解決的問題，有關學者仍然試圖開發(fā)各種方法并進行了大量的研究，并取得了一些進展。這些方法可以分為兩類：靜態(tài)的方法和動態(tài)的方法。靜態(tài)方法包括域縮減[4]和符號執(zhí)行[5]等。當處理無限數組，循環(huán)，指針引用和過程調用等問題時這些方法會受到一定的局限性。

與靜態(tài)方法相比，動態(tài)方法包括隨機測試，局部搜索方法，目標導向方法，鏈接方法以及演化方法[6-8]。由于輸入變量的值是在程序執(zhí)行時確定的，動態(tài)測試數據的生成可以避免那些靜態(tài)方法面臨的問題。作為復雜空間中的一種強大的搜索方法，粒子群優(yōu)化(particle swarm optimization, PSO)算法在1995年被應用于測試數據生成，并且演化方法從那以后一直是受到廣大學者的關注。相關文獻也表明基于PSO算法的測試數據生成優(yōu)于其他動態(tài)方法，例如隨機測試和本地搜索。

基于此，本文采用了基于改進PSO算法的軟件測試用例生成方法。與傳統的遺傳算法相比，改進PSO算法采用分支函數疊加方法來構造適應度函數。同時，為了提高目標路徑選擇上的泛化能力，以三角形分類判別程序為例，選擇具有最多分支結構的路徑為目標路徑。最后，利用程序插裝收集個體的最優(yōu)適應值。實驗結果表明，本文采用基于改進PSO算法的軟件測試用例生成方法可以有效減少生成所需時間以及能夠生成更合適的測試用例。

1 軟件測試用例生成描述

測試用例生成是軟件測試中勞動力最密集的任務之一，對軟件測試的有效性和效率產生了很大的影響。由于這些原因，測試用例的自動生成是幾十年來較為活躍的研究課題之一[9]。一般來說，測試用例作為一個重要的軟件工件，必須從一些信息中產生，也就是其他一些類型的軟件工件。已經用作生成測試用例的參考輸入的工件類型包括：程序結構和/或源代碼；軟件規(guī)格和/或設計模型；關于輸入/輸出數據空間的信息以及從程序執(zhí)行中動態(tài)獲得的信息。因此，可以將自動生成軟件測試用例方法分為以下幾類[10]，即(a)基于符號執(zhí)行的結構測試，(b)基于模型的測試，(c)組合測試，(d)隨機測試，以及(e)基于搜索的測試。

基于符號執(zhí)行的結構測試是一種程序分析技術，它分析程序的代碼，為程序自動生成測試數據。然而，該技術存在一些基本問題，限制了其對現實軟件的有效性?；谀Ｐ偷臏y試是一種使用軟件系統模型推導測試套件的輕量級形式化方法。與傳統的形式化方法相比，其旨在通過不完整的測試方法來收集程序正確性的見解。組合測試已經成為軟件測試工具箱中常見的技術。在組合測試中，重點是選擇輸入參數(或配置設置)的樣本，覆蓋要測試的元素組合子集。隨機測試中，測試用例均勻分布在輸入域中。一組測試用例的選擇旨在通過強制隨機測試的均勻擴展來提高隨機測試的失敗檢測效率。即如果之前執(zhí)行的測試用例沒有發(fā)現失敗，那么新的測試用例應該遠離已執(zhí)行過的非失敗測試用例?；谒阉鞯臏y試是基于一些智能搜索算法來自動化查找測試數據，從而最大限度地實現測試目標，同時最小化測試成本。

本文提出的方法屬于基于搜索的測試方法，使用了PSO智能搜索算法來生成測試數據。

2 改進PSO算法

2.1 傳統PSO算法

粒子群優(yōu)化(PSO)算法最早由Berhart和Kennedy兩位學者提出[11]。與遺傳算法相比，PSO算法從隨機解開始，通過種群中個體之間的相互協作和信息共享來實現最優(yōu)解的搜索。其中，PSO算法中的每一個粒子代表問題的一個可能解，調節(jié)粒子位置和速度的適應度特征參數，以達到所選粒子的最優(yōu)情形。

PSO算法實現步驟如下，首先初始化一群隨機粒子，讓每個粒子都是所對應問題的一個歷史最優(yōu)解，并確定各自的適應值。確定適應度值后的每個粒子在整個算法過程中，其運動的距離和方向通過速度來確定。經過迭代搜索后的最優(yōu)粒子將從局部最優(yōu)解中求出全局最優(yōu)解。PSO算法的基本思想是加速每個粒子朝各自的歷史和種群的最好位置逼近[12]。

設第i個粒子的當前位置為xi=(xi1,xi2,···,xim)，當前速度為vi=(vi1,vi2,···,vim)，其中m表示搜索空間維數。通過比較更新粒子群的歷史最優(yōu)解和找到的全局極值解，根據公式(1)(2)來更新粒子速度和位置。

vij(t+1)=ωvij(t)+c1r1(pij(t)-xij(t))+

c2r2(pgj(t)-xij(t))

(1)

xij(t+1)=xij(t)+rvij(t+1)

(2)

式中，i∈(1,2,···,n)，j∈(1,2,···,m)，t表示迭代次數，ω表示權重系數，其取值大小決定了當前粒子速度占下一刻速度的比例。c1,c2表示學習因子系數，用來調節(jié)粒子的位置方向的步長。r1,r2表示約束因子，為[0,1]范圍內的隨機數。

2.2 改進PSO算法

為了避免PSO算法在執(zhí)行時所帶來的負面影響，尤其是處理高維復雜問題時，易陷入局部最優(yōu)解的困境，在求解全局最優(yōu)解時，加入考慮相鄰粒子的位置信息。即，式(1)進行如下的改進：

vij(t+1)=ωvij(t)+c1r1(pij(t)-xij(t))+

c2r2(pgj(t)-xij(t))+c2r2(pkj(t)-xij(t))

(3)

式中，pkj(t)表示相鄰粒子的位置信息，而且為了減少計算量，實際運算過程中，并不是納入全部粒子的位置信息，只選擇具有最佳適應度值的相鄰粒子的位置信息。同時，式(3)中由于考慮了相鄰粒子位置對第i個粒子的影響，一定程度地提高了算法的收斂性。

另外，w設置為固定值不能適應動態(tài)的收斂過程。為此，引入了動態(tài)慣性權重，使其在一定范圍內，隨著迭代次數的增加而線性遞減，表達式如下：

(4)

式中，wmax和wmin為w的最大值和最小值，取值為0.9和0.4；Tmax為最大迭代次數，ite為當前迭代次數。

適應度函數對PSO算法的搜索尋找測試數據速度有直接的影響[13]。本文通過分值函數疊加方法來構造適應度函數。其中，當分支謂詞為假時，F(x)為正或零，當分支謂詞為真時，F(x)為負或零。

分支函數表達式為：

F=C-(F(f1)+F(f2)+···+F(fm))

(5)

3 基于改進PSO算法的測試數據生成

采用PSO算法自動生成路徑測試的測試用例的原因之一是實現簡單。PSO算法的每次迭代都會生成一代個體。在實踐中，計算時間不能是無限的，所以迭代在算法中應該是有限的。在有限的世代內，由PSO算法得出的求解結果可能會是局部最優(yōu)解，結果就是不能定位需求可能被困在不需要的路徑周圍，無法找到所需的全局最優(yōu)值[14]。PSO在第一代的測試用例正常地分布在被測試的領域程序中，受困概率非常低。另外，其產生的測試用例的質量高于隨機產生的測試用例的質量，因為該算法可以將測試用例的產生快速地引導到期望的范圍[15]。

PSO算法實現首要是選擇合理的目標路徑，將輸入向量(測試數據)作為一個個體。為了使用PSO為被測程序生成面向路徑的測試數據，本文設計了5個步驟，圖1描述了整體的軟件測試框架。

1)控制流程圖構建。被測試程序的控制流程圖可以通過相關工具手動或自動構建?？刂屏鞒虉D有助于測試人員選擇具有代表性的目標路徑。

2)目標路徑選擇。一般來說，被測試的程序有太多的路徑可以完全測試。因此，測試人員必須選擇有意義的路徑作為目標路徑。

3)適應度函數構建。為了評估執(zhí)行路徑和目標路徑之間的距離，必須構建適應度函數。

4)程序插裝。這意味著在每個源代碼塊的開始插入探測器來監(jiān)視程序執(zhí)行并收集相關信息(例如個體的適應度值)。

5)測試數據生成和插裝程序執(zhí)行。為實現目標路徑，原始測試數據主要來自于從測試數據的領域隨機選擇和PSO算法產生的新測試數據。最后，可能會產生沿著目標路徑執(zhí)行的合適的測試數據，或者由于超過最大生成而不能找到合適的測試數據。

圖1 基本流程圖

4 實驗與分析

4.1 案例程序

為了驗證本文算法在收斂性及運行時間上的性能表現，選擇三角形分類判別程序為示例程序。三角形分類程序廣泛應用于軟件測試研究領域。它旨在確定3個輸入邊是否可以形成一個三角形，以及它們可以形成什么類型的三角形。三角形分類程序如下所示。

算法：三角形分類程序

TraversedPath= [];

TriangleType='Not a Triangle';

If((SideA+SideB>SideC)&&(SideB+SideC>SideA)&&(SideC+SideA>SideB))

TraversedPath =[TraversedPath'a'];

if

((SideA～=SideB)&&(SideB～=SideC)&&(SideC～=SideA))

TraversedPath=[TraversedPath'e'];

TriangleType='Scalene';

else

TraversedPath =[TraversedPath 'b'];

if(((SideA==SideB)&&(SideB～=SideC))||((SideB==SideC)&&(SideC～=SideA))||((SideC==SideA)&&(SideA～=SideB)))

TraversedPath = [TraversedPath 'f'];

TriangleType ='Isosceles';

else

TraversedPath=[TraversedPath 'c'];

TriangleType='Equilateral';

end

end

else

TraversedPath =[TraversedPath'd'];

end

三角形分類測試程序確定任何3個輸入長度的邊可以形成哪種三角形。程序控制流程圖如圖2所示，其中包含4個路徑。

圖2 示例程序的流程圖

這里設置輸入的三角形邊的取值為1到2N的整數。另外，對于本文改進PSO算法，設置粒子編碼長度為3N， 種群大小為1到1000，學習因子c1,c2都為2，w從0.9線性降低到0.4，最大迭代次數為20。

4.2 目標路徑選擇

上圖三角形分類程序的控制流程圖，由四條路徑組成：

路徑l： //非三角形

路徑2： //不等邊三角形

路徑3： //等腰三角形

路徑4： //等邊三角形

根據概率論知識，路徑是路徑測試中最難涵蓋的路徑。因此，選擇路徑作為目標路徑。

4.3 測試數據生成和執(zhí)行

測試用例的自動生成可以按照如下步驟進行：

1)分析測試程序的整體框架，繪制出控制流程圖，如圖1所示；

2)根據測試路徑要求，繪制合適的測試路徑，如圖2所示，并制定適應度函數；

3)通過程序插裝對源程序進行插裝；

4)根據程序的需求，隨機產生定義域內的初始化測試用例集合；

5)在獲得對應的適應度值后，檢測是否執(zhí)行了預定目標路徑；

6)根據每個粒子的適應度值，執(zhí)行改進PSO算法，生成測試用例，轉到步驟5)

7)運行結束，輸出合適的測試用例。

表1為當設定測試總數為500時，10次迭代中各種路徑上的測試用例數量。圖3顯示了每一次迭代路徑上測試用例數量曲線。

表1 各次迭代中的測試用例數量(測試總數為500)

圖3 各次迭代中的測試用例數量(測試總數為500)

表2顯示了當測試總數為1000時，10次迭代中測試用例的平均數量。圖4顯示了每一次迭代路徑上測試用例數量曲線。

表2 各次迭代中的測試用例數量(測試總數為1 000)

圖4 各次迭代中的測試用例數量(測試總數為1 000)

通過以上兩組實驗可以看出，所選擇的種群規(guī)模越小，則找到全部用例的迭代次數越多，反之亦然。但是，需注意的是，運行時間會隨著種群規(guī)模的增大而增加。在實際操作中，需要折衷權衡迭代次數和運行時間兩者之間的比重。

5 結束語

針對路徑測試中的軟件測試用例生成的問題，本文提出了一種基于改進PSO算法的軟件測試用例生成方法。首先，考慮相鄰粒子的位置信息和動態(tài)權重來改進傳統PSO，并利用分值函數疊加方法來構造適應值函數。接著構建算法的控制流程圖并進行目標路徑選擇。然后，利用程序插裝收集個體的適應度值。最后，測試數據生成程序執(zhí)行，得到合適的測試數據。

實驗表明，PSO算法能夠有效生成合適的路徑測試的測試用例，并大大減少生成測試所需的時間。

[1] 鄧璐娟, 林 楠, 盧華琦,等. 基于改進粒子群算法的測試數據自動生成研究[J]. 計算機測量與控制, 2011, 19(2)：250-252.

[2] 賀 瀅, 徐蔚鴻, 李楊林. 基于RACPSO的測試用例自動生成方法[J]. 計算機工程, 2016, 42(5)：66-70.

[3] 楊 波, 吳 際, 徐 珞,等. 一種軟件測試需求建模及測試用例生成方法[J]. 計算機學報, 2014, 37(3):522-538.

[4] 周虹伯, 金大海, 宮云戰(zhàn). 基于域敏感指向分析的區(qū)間運算在軟件測試中的應用[J]. 計算機研究與發(fā)展, 2012, 49(9)：1852-1862.

[5] Bertolino A. Software Testing Research： Achievements, Challenges, Dreams[C]. international conference on software engineering, 2007： 85-103.

[6] Haga H, Suehiro A. Automatic test case generation based on genetic algorithm and mutation analysis[C]. IEEE International Conference on Control System, Computing and Engineering. IEEE, 2013:119-123.

[7] Zhang N, Wu B, Bao X. Automatic Generation of Test Cases Based On Multi-population Genetic Algorithm[J]. International Journal of Multimedia & Ubiquitous Engineering, 2015, 10(6)：113-122.

[8] Huang M, Zhang C, Liang X. Software test cases generation based on improved particle swarm optimization[C]. International Conference on Information Technology and Electronic Commerce. IEEE, 2015:52-55.

[9] 耿 技, 聶 鵬, 秦志光. 軟件確保智能測試用例生成PSO算法進展研究[J]. 電子科技大學學報, 2012, 41(6):905-910.

[10] Anand S, Burke E K, Chen T Y, et al. An orchestrated survey of methodologies for automated software test case generation[J]. Journal of Systems & Software, 2013, 86(8):1978-2001.

[11] 陳云飛, 李 征, 趙瑞蓮. 基于PSO的多目標測試用例預優(yōu)化[J]. 計算機科學, 2014, 41(5):72-77.

[12] Tiwari S, Mishra K K, Misra A K. Test Case Generation for Modified Code Using a Variant of Particle Swarm Optimization (PSO) Algorithm[C]. International Conference on Information Technology: New Generations. IEEE Computer Society, 2013:363-368.

[13] Liu D, Feng Q Y. PSO fitness function used in antenna arrays pattern synthesis[J]. Chinese Journal of Radio Science, 2011, 26(3)：581-586.

[14] 郭書杰, 黃 明, 梁 旭,等. 基于差分進化算法的組合測試用例集生成[J]. 計算機應用研究, 2014, 31(5):1449-1451.

[15] Devasena M S G, Gopu G, Valarmathi M L. Automated and Optimized Software Test Suite Generation Technique for Structural Testing[J]. International Journal of Software Engineering & Knowledge Engineering, 2016, 26(1):1-13.