基于改進(jìn)PSO算法的路徑軟件測(cè)試用例生成方法

,

( 國(guó)網(wǎng)天津市電力公司 信息通信公司,天津 300010)

0 引言

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

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

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

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

1 軟件測(cè)試用例生成描述

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

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

本文提出的方法屬于基于搜索的測(cè)試方法，使用了PSO智能搜索算法來(lái)生成測(cè)試數(shù)據(jù)。

2 改進(jìn)PSO算法

2.1 傳統(tǒng)PSO算法

粒子群優(yōu)化(PSO)算法最早由Berhart和Kennedy兩位學(xué)者提出[11]。與遺傳算法相比，PSO算法從隨機(jī)解開(kāi)始，通過(guò)種群中個(gè)體之間的相互協(xié)作和信息共享來(lái)實(shí)現(xiàn)最優(yōu)解的搜索。其中，PSO算法中的每一個(gè)粒子代表問(wèn)題的一個(gè)可能解，調(diào)節(jié)粒子位置和速度的適應(yīng)度特征參數(shù)，以達(dá)到所選粒子的最優(yōu)情形。

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

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

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表示迭代次數(shù)，ω表示權(quán)重系數(shù)，其取值大小決定了當(dāng)前粒子速度占下一刻速度的比例。c1,c2表示學(xué)習(xí)因子系數(shù)，用來(lái)調(diào)節(jié)粒子的位置方向的步長(zhǎng)。r1,r2表示約束因子，為[0,1]范圍內(nèi)的隨機(jī)數(shù)。

2.2 改進(jìn)PSO算法

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

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

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

(3)

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

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

(4)

式中，wmax和wmin為w的最大值和最小值，取值為0.9和0.4；Tmax為最大迭代次數(shù)，ite為當(dāng)前迭代次數(shù)。

適應(yīng)度函數(shù)對(duì)PSO算法的搜索尋找測(cè)試數(shù)據(jù)速度有直接的影響[13]。本文通過(guò)分值函數(shù)疊加方法來(lái)構(gòu)造適應(yīng)度函數(shù)。其中，當(dāng)分支謂詞為假時(shí)，F(xiàn)(x)為正或零，當(dāng)分支謂詞為真時(shí)，F(xiàn)(x)為負(fù)或零。

分支函數(shù)表達(dá)式為：

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

(5)

3 基于改進(jìn)PSO算法的測(cè)試數(shù)據(jù)生成

采用PSO算法自動(dòng)生成路徑測(cè)試的測(cè)試用例的原因之一是實(shí)現(xiàn)簡(jiǎn)單。PSO算法的每次迭代都會(huì)生成一代個(gè)體。在實(shí)踐中，計(jì)算時(shí)間不能是無(wú)限的，所以迭代在算法中應(yīng)該是有限的。在有限的世代內(nèi)，由PSO算法得出的求解結(jié)果可能會(huì)是局部最優(yōu)解，結(jié)果就是不能定位需求可能被困在不需要的路徑周?chē)瑹o(wú)法找到所需的全局最優(yōu)值[14]。PSO在第一代的測(cè)試用例正常地分布在被測(cè)試的領(lǐng)域程序中，受困概率非常低。另外，其產(chǎn)生的測(cè)試用例的質(zhì)量高于隨機(jī)產(chǎn)生的測(cè)試用例的質(zhì)量，因?yàn)樵撍惴梢詫y(cè)試用例的產(chǎn)生快速地引導(dǎo)到期望的范圍[15]。

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

1)控制流程圖構(gòu)建。被測(cè)試程序的控制流程圖可以通過(guò)相關(guān)工具手動(dòng)或自動(dòng)構(gòu)建?？刂屏鞒虉D有助于測(cè)試人員選擇具有代表性的目標(biāo)路徑。

2)目標(biāo)路徑選擇。一般來(lái)說(shuō)，被測(cè)試的程序有太多的路徑可以完全測(cè)試。因此，測(cè)試人員必須選擇有意義的路徑作為目標(biāo)路徑。

3)適應(yīng)度函數(shù)構(gòu)建。為了評(píng)估執(zhí)行路徑和目標(biāo)路徑之間的距離，必須構(gòu)建適應(yīng)度函數(shù)。

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

5)測(cè)試數(shù)據(jù)生成和插裝程序執(zhí)行。為實(shí)現(xiàn)目標(biāo)路徑，原始測(cè)試數(shù)據(jù)主要來(lái)自于從測(cè)試數(shù)據(jù)的領(lǐng)域隨機(jī)選擇和PSO算法產(chǎn)生的新測(cè)試數(shù)據(jù)。最后，可能會(huì)產(chǎn)生沿著目標(biāo)路徑執(zhí)行的合適的測(cè)試數(shù)據(jù)，或者由于超過(guò)最大生成而不能找到合適的測(cè)試數(shù)據(jù)。

圖1 基本流程圖

4 實(shí)驗(yàn)與分析

4.1 案例程序

為了驗(yàn)證本文算法在收斂性及運(yùn)行時(shí)間上的性能表現(xiàn)，選擇三角形分類判別程序?yàn)槭纠绦颉Ｈ切畏诸惓绦驈V泛應(yīng)用于軟件測(cè)試研究領(lǐng)域。它旨在確定3個(gè)輸入邊是否可以形成一個(gè)三角形，以及它們可以形成什么類型的三角形。三角形分類程序如下所示。

算法：三角形分類程序

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

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

圖2 示例程序的流程圖

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

4.2 目標(biāo)路徑選擇

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

路徑l： //非三角形

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

路徑3： //等腰三角形

路徑4： //等邊三角形

根據(jù)概率論知識(shí)，路徑是路徑測(cè)試中最難涵蓋的路徑。因此，選擇路徑作為目標(biāo)路徑。

4.3 測(cè)試數(shù)據(jù)生成和執(zhí)行

測(cè)試用例的自動(dòng)生成可以按照如下步驟進(jìn)行：

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

2)根據(jù)測(cè)試路徑要求，繪制合適的測(cè)試路徑，如圖2所示，并制定適應(yīng)度函數(shù)；

3)通過(guò)程序插裝對(duì)源程序進(jìn)行插裝；

4)根據(jù)程序的需求，隨機(jī)產(chǎn)生定義域內(nèi)的初始化測(cè)試用例集合；

5)在獲得對(duì)應(yīng)的適應(yīng)度值后，檢測(cè)是否執(zhí)行了預(yù)定目標(biāo)路徑；

6)根據(jù)每個(gè)粒子的適應(yīng)度值，執(zhí)行改進(jìn)PSO算法，生成測(cè)試用例，轉(zhuǎn)到步驟5)

7)運(yùn)行結(jié)束，輸出合適的測(cè)試用例。

表1為當(dāng)設(shè)定測(cè)試總數(shù)為500時(shí)，10次迭代中各種路徑上的測(cè)試用例數(shù)量。圖3顯示了每一次迭代路徑上測(cè)試用例數(shù)量曲線。

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

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

表2顯示了當(dāng)測(cè)試總數(shù)為1000時(shí)，10次迭代中測(cè)試用例的平均數(shù)量。圖4顯示了每一次迭代路徑上測(cè)試用例數(shù)量曲線。

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

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

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

5 結(jié)束語(yǔ)

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

實(shí)驗(yàn)表明，PSO算法能夠有效生成合適的路徑測(cè)試的測(cè)試用例，并大大減少生成測(cè)試所需的時(shí)間。

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

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

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

[4] 周虹伯, 金大海, 宮云戰(zhàn). 基于域敏感指向分析的區(qū)間運(yùn)算在軟件測(cè)試中的應(yīng)用[J]. 計(jì)算機(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] 耿 技, 聶 鵬, 秦志光. 軟件確保智能測(cè)試用例生成PSO算法進(jìn)展研究[J]. 電子科技大學(xué)學(xué)報(bào), 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的多目標(biāo)測(cè)試用例預(yù)優(yōu)化[J]. 計(jì)算機(jī)科學(xué), 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] 郭書(shū)杰, 黃 明, 梁 旭,等. 基于差分進(jìn)化算法的組合測(cè)試用例集生成[J]. 計(jì)算機(jī)應(yīng)用研究, 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.