宮云戰(zhàn)，徐健豪，邢穎

(1.北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876；2.北京郵電大學(xué) 自動(dòng)化學(xué)院，北京 100876)

軟件測(cè)試在檢驗(yàn)和提升軟件設(shè)計(jì)和實(shí)現(xiàn)質(zhì)量的過(guò)程中是非常重要但耗時(shí)的環(huán)節(jié)。在軟件開(kāi)發(fā)需要檢查版本迭代過(guò)程中是否產(chǎn)生了新錯(cuò)誤。但是在每次更改后沒(méi)有必要執(zhí)行全部測(cè)試用例，一方面，多個(gè)測(cè)試用例可能集中在一段相同的代碼上，從而產(chǎn)生冗余和浪費(fèi)；另一方面，在一個(gè)大型項(xiàng)目中執(zhí)行一次測(cè)試套件需要大約1 h[1]，頻繁的代碼更改需要大量時(shí)間來(lái)進(jìn)行測(cè)試。測(cè)試用例集約簡(jiǎn)旨在保障覆蓋率不變的情況下限度地減少執(zhí)行的測(cè)試用例的數(shù)量，約簡(jiǎn)測(cè)試用例集，在進(jìn)行約簡(jiǎn)時(shí)，約簡(jiǎn)后測(cè)試用例集必須要滿足跟原始測(cè)試用例集具有相同的覆蓋率，例如語(yǔ)句覆蓋率等[2]。

Harrold等[3]提出測(cè)試用例集約簡(jiǎn)的概念并提出一種啟發(fā)式方法。在隨后的發(fā)展中，出現(xiàn)了許多方法，包括貪心算法、啟發(fā)式算法和整數(shù)規(guī)劃等[4]。Chvatal[5]介紹的種貪心算法是一種經(jīng)典的用于尋找測(cè)試用例集問(wèn)題的近似最優(yōu)解的方法。然而，貪心算法并不能盡早處理基本測(cè)試用例(唯一可以覆蓋其中某測(cè)試需求的測(cè)試用例)，Chen等[6]提出了2種算法來(lái)解決這個(gè)問(wèn)題。全君林等[7]提出采用遺傳算法，通過(guò)遺傳算子完成進(jìn)化過(guò)程找到最優(yōu)或近似最優(yōu)解。張衛(wèi)祥等[8]提出了一種改進(jìn)的基于測(cè)試點(diǎn)覆蓋和離散粒子群優(yōu)化算法的方法來(lái)提高回歸測(cè)試效率。但是這類算法會(huì)有陷入局部收斂等問(wèn)題。

本文提出了一種基于螢火蟲(chóng)算法的測(cè)試用例集約簡(jiǎn)算法，利用螢火蟲(chóng)算法發(fā)現(xiàn)能夠滿足測(cè)試需求的最簡(jiǎn)測(cè)試用例集，對(duì)回歸測(cè)試進(jìn)行優(yōu)化，并通過(guò)對(duì)實(shí)際工程項(xiàng)目進(jìn)行測(cè)試實(shí)驗(yàn)，對(duì)螢火蟲(chóng)算法的效果、魯棒性等性能進(jìn)行檢驗(yàn)分析。

1 螢火蟲(chóng)算法及建模

本文從覆蓋率以及測(cè)試開(kāi)銷(xiāo)2個(gè)方面進(jìn)行了綜合考慮，利用螢火蟲(chóng)算法空間搜索能力強(qiáng)、收斂快等特點(diǎn)，構(gòu)建了二值細(xì)胞自動(dòng)機(jī)模型，將其應(yīng)用于測(cè)試用例集約簡(jiǎn)之中，使其可以在快速收斂的情況下，更高效的進(jìn)行測(cè)試用例集約簡(jiǎn)。

1.1 測(cè)試用例集約簡(jiǎn)

測(cè)試用例集約簡(jiǎn)問(wèn)題輸入主要可以概括為：測(cè)試用例集T={t1,t2,…,tn}，測(cè)試需求集R={r1,r2,…,rm}，測(cè)試關(guān)系Z={(t,r)|t∈T，r∈R}，其中，如果測(cè)試用例t可以檢測(cè)到測(cè)試需求r，則為1，否則為0，測(cè)試開(kāi)銷(xiāo)C={c1,c2,…,cm}。

經(jīng)過(guò)約簡(jiǎn)，得到一個(gè)的測(cè)試用例集T的子集RS，其中RS的測(cè)試用例可以滿足所有的測(cè)試需求，并且使產(chǎn)生的測(cè)試開(kāi)銷(xiāo)盡可能小。

令測(cè)試需求集為R={r1,r2,…,rm}，測(cè)試用例集為T(mén)={t1,t2,…,tn}，?T1?T，其中：T1滿足R，有?Tx?T，使得Tx的測(cè)試開(kāi)銷(xiāo)大于等于T1的測(cè)試開(kāi)銷(xiāo)，因此這是一個(gè)最小集合覆蓋問(wèn)題，屬于典型的NP-Complete問(wèn)題，所以無(wú)法用傳統(tǒng)的方法得到最優(yōu)解。

給出一個(gè)測(cè)試用例集約簡(jiǎn)的實(shí)例。

如表1所示，測(cè)試用例T內(nèi)包含5個(gè)測(cè)試用例{t1,t2,t3,t4,,t5}，測(cè)試需求集包含6個(gè)需求{r1,r2,r3,r4,r5,r6}，其中的■代表的是測(cè)試關(guān)系，每個(gè)測(cè)試用例分別都對(duì)應(yīng)一個(gè)測(cè)試開(kāi)銷(xiāo)，實(shí)際上這組測(cè)試用例是有冗余的，不考慮開(kāi)銷(xiāo)的情況下，只需要{t1,t2}便可以覆蓋全部測(cè)試點(diǎn)，因此另外3個(gè)需要約簡(jiǎn)的冗余測(cè)試用例。

將上述問(wèn)題轉(zhuǎn)化為數(shù)學(xué)問(wèn)題：測(cè)試用例集和測(cè)試需求分別代表矩陣的列和行，測(cè)試用例i滿足測(cè)試需求j的測(cè)試關(guān)系表示為Sij=1，測(cè)試開(kāi)銷(xiāo)表示為一個(gè)向量，則可以將表1轉(zhuǎn)換為：

表1 測(cè)試用例集實(shí)例Table 1 Test suite example

r1r2r3r4r5r6c

即問(wèn)題可以表示為一個(gè)m×n的矩陣，目的是在開(kāi)銷(xiāo)最小的情況下，選擇一部分矩陣的行，使其覆蓋矩陣所有的列，設(shè)向量x表示約簡(jiǎn)結(jié)果，xi=1表示行i被選中，可以覆蓋Sij=1各行對(duì)應(yīng)的測(cè)試功能點(diǎn)，問(wèn)題求解目標(biāo)表示為：

minf(x)=xc

(1)

(2)

式(1)是約簡(jiǎn)目標(biāo)，式(2)為約束條件，表示每個(gè)測(cè)試點(diǎn)都需要被覆蓋。

1.2 螢火蟲(chóng)算法描述

螢火蟲(chóng)算法(firefly algorithm，F(xiàn)A)是一種基于群體的隨機(jī)優(yōu)化算法。文獻(xiàn)[9]研究了螢火蟲(chóng)個(gè)體間相互吸引與發(fā)光亮度之間的關(guān)系和螢火蟲(chóng)的移動(dòng)特性，從而提出了一種新型群智能優(yōu)化算法，即螢火蟲(chóng)算法。

在螢火蟲(chóng)算法中，空間各點(diǎn)視為螢火蟲(chóng)，發(fā)光弱的螢火蟲(chóng)會(huì)被發(fā)光強(qiáng)的所吸引。根據(jù)這一特點(diǎn)，在算法中，將適應(yīng)度設(shè)置為發(fā)光強(qiáng)度，適應(yīng)度越高代表其位置越好，這樣適應(yīng)度低的螢火蟲(chóng)會(huì)朝向適應(yīng)度高的螢火蟲(chóng)移動(dòng)，從而完成位置的迭代，并找出最優(yōu)位置，即完成了尋優(yōu)過(guò)程。

螢火蟲(chóng)算法有以下條件：1) 所有螢火蟲(chóng)都是同一性別且相互吸引；2) 吸引度只與發(fā)光強(qiáng)度和距離有關(guān)，與發(fā)光強(qiáng)度成正比，與距離成反比；3) 發(fā)光強(qiáng)弱，即適應(yīng)度，由目標(biāo)函數(shù)決定，在指定區(qū)域內(nèi)與指定函數(shù)成比例關(guān)系。

算法的數(shù)學(xué)描述和主要參數(shù)如下：1) 螢火蟲(chóng)相對(duì)熒光亮度：

I=I0e-γrij

(3)

式中：I0表示螢火蟲(chóng)的最大亮度，與目標(biāo)函數(shù)有關(guān)，位置越優(yōu)，亮度越大；γ表示光吸收系數(shù)，其代表的是熒光會(huì)隨著距離的增加和傳播介質(zhì)的吸收而逐漸減弱；rij表示的是i和j2個(gè)螢火中之間的歐氏距離。

2) 相互吸引度β：

(4)

式中β0為最大吸引度，即距離為0的吸引度。

3) 最優(yōu)目標(biāo)迭代：

(5)

式中：t表示的是時(shí)刻，xi與xj表示螢火蟲(chóng)i、j的空間位置，α為步長(zhǎng)因子，rand為隨機(jī)項(xiàng)，防止產(chǎn)生震蕩，為[0,1]上的均勻分布。

1.3 二元優(yōu)化問(wèn)題應(yīng)用

測(cè)試用例約簡(jiǎn)問(wèn)題屬于二元優(yōu)化問(wèn)題，因此引入二進(jìn)制編碼，并采用一維二值細(xì) 胞自動(dòng)機(jī)模型對(duì)問(wèn)題的復(fù)雜求解過(guò)程進(jìn)行描述[10]，假設(shè)問(wèn)題維度L，則螢火蟲(chóng)細(xì)胞列的長(zhǎng)度為L(zhǎng)，每個(gè)細(xì)胞的取值Q∈{0,1}，第i只螢火蟲(chóng)的第j維位置表示為xij。采用sign函數(shù)對(duì)細(xì)胞值進(jìn)行分類，sign函數(shù)為：

(6)

則細(xì)胞自動(dòng)機(jī)模型分類的表達(dá)示為：

(7)

式中：t代表的是時(shí)刻，螢火蟲(chóng)在0時(shí)刻需要遍歷一遍分類模型，將位置信息轉(zhuǎn)化為一個(gè)0/1序列，從而得到二元離散問(wèn)題的解。

1.4 基于FA的測(cè)試用例集約簡(jiǎn)

本文將FA算法應(yīng)用于測(cè)試用例集約簡(jiǎn)，算法思想是將螢火蟲(chóng)位置轉(zhuǎn)化為0/1序列，其中0代表舍棄這個(gè)測(cè)試用例，1代表保留這個(gè)測(cè)試用例，然后采用傳統(tǒng)的貪婪算法得到解。螢火蟲(chóng)算法隨機(jī)在空間中生成初始點(diǎn)，每個(gè)點(diǎn)通過(guò)二值細(xì)胞自動(dòng)機(jī)模型轉(zhuǎn)化為0或1，并利用螢火蟲(chóng)算法搜索能力強(qiáng)的特點(diǎn)遍歷空間，向適應(yīng)度最好的點(diǎn)收斂，更新位置和適應(yīng)度，最后得到最好的約簡(jiǎn)效果。

本文FA的主要步驟為：1)初始化螢火蟲(chóng)算法的基本參數(shù)，包括螢火蟲(chóng)數(shù)目、位置維度、最大吸引度、步長(zhǎng)因子、最大迭代次數(shù)；2)隨機(jī)初始化位置，經(jīng)過(guò)細(xì)胞模型分類機(jī)，生成細(xì)胞陣列，即0/1序列，并根據(jù)該序列計(jì)算該螢火蟲(chóng)的最大熒光度；3)計(jì)算群體中螢火蟲(chóng)之間的相對(duì)亮度和吸引度，并進(jìn)行比較判斷移動(dòng)方向；4)更新螢火蟲(chóng)的位置，對(duì)最佳位置螢火蟲(chóng)進(jìn)行隨機(jī)移動(dòng)。5)根據(jù)更新后的位置，重新生成細(xì)胞陣列，并根據(jù)新的0/1序列計(jì)算亮度；6)當(dāng)?shù)竭_(dá)最大搜索次數(shù)時(shí)，轉(zhuǎn)到下一步；否則進(jìn)行下一次迭代，迭代次數(shù)加1，轉(zhuǎn)到步驟3；7)輸出全局極值點(diǎn)，最優(yōu)螢火蟲(chóng)，以及對(duì)應(yīng)的0/1序列。

1.5 螢火蟲(chóng)算法描述

Input:T//測(cè)試用例集

Input:C//測(cè)試開(kāi)銷(xiāo)

Output:xb//最優(yōu)解

Begin：

Initialize variables pop,α,β,γ,max GAN

Itializef=1,firefly populationbp

Initialize fireflies′ positionsxp

while f

Find fitness forbpusingTandC

Find best solutionx′ inxp

ifx′>xb:

Updatexb

End if

for eachi=1，2，…，pop:

for eachj=1，2，…，pop:

ifi!=jand fitnessi<=fitnessj:

Updateximove toxj

else ifi!=jand fitnessi==fitnessj:

Updatexirandom

End if

End for

End for

f=f+1

End while

returnxb

End

2 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

本文算法算法是在CPU為i5-4200 2.3 GHz，內(nèi)存為12G DDR3內(nèi)存下運(yùn)行，算法的實(shí)現(xiàn)語(yǔ)言為Python 3.6。

2.1 測(cè)試數(shù)據(jù)集

本文采用為了研究程序的數(shù)據(jù)流和控制流的覆蓋準(zhǔn)則的錯(cuò)誤檢測(cè)能力而提供的標(biāo)準(zhǔn)程序測(cè)試套件Siemens Suite[11]。在Siemens程序有7個(gè)標(biāo)準(zhǔn)C程序 (printtokens、printtokens2、replace、schedule、schedule2、tca、totinfo) 和對(duì)應(yīng)的測(cè)試用例集合，以及執(zhí)行這些用例的shell腳本。

2.2 實(shí)驗(yàn)探究

首先進(jìn)行測(cè)試需求的提取，本文中測(cè)試需求的為Siemens Suite中7個(gè)程序的分支覆蓋，采用gcov[12]進(jìn)行提取。本文的測(cè)試開(kāi)銷(xiāo)用的是每個(gè)測(cè)試用例執(zhí)行的時(shí)間，總共執(zhí)行50次后取得平均時(shí)間。

每個(gè)測(cè)試程序分別進(jìn)行如下操作：在保證覆蓋率為100%的情況下，分別在總測(cè)試集中隨機(jī)選擇50、200、1 000個(gè)測(cè)試用例和全集組成新的測(cè)試用例集，每組進(jìn)行隨機(jī)抽取20次。

本文復(fù)原了文獻(xiàn)[13]中改進(jìn)的GRE算法和貪心算法進(jìn)行對(duì)比試驗(yàn)。在實(shí)驗(yàn)過(guò)程中，分2方面進(jìn)行比較：1)統(tǒng)計(jì)在進(jìn)行了相同次數(shù)的約簡(jiǎn)實(shí)驗(yàn)后，F(xiàn)A、GRE和貪心算法3個(gè)算法表現(xiàn)最優(yōu)的次數(shù)，其中20次約簡(jiǎn)中效果最好的次數(shù)，包括約簡(jiǎn)效果相同實(shí)驗(yàn)；2)統(tǒng)計(jì)每組實(shí)驗(yàn)后約簡(jiǎn)后的ECRS值。經(jīng)過(guò)實(shí)驗(yàn)，得到實(shí)驗(yàn)結(jié)果，如表2所示：

表2 實(shí)驗(yàn)結(jié)果Table 2 Experimental results

2.3 實(shí)驗(yàn)結(jié)果分析

首先，對(duì)測(cè)試用例集約簡(jiǎn)來(lái)說(shuō)，開(kāi)銷(xiāo)的降低是最重要的也是最直接的表現(xiàn)，本文用約簡(jiǎn)集開(kāi)銷(xiāo)成本(the execution cost of the representative set,ECRS)[14]，即RS中的開(kāi)銷(xiāo)總表示約簡(jiǎn)效果，EECRS表示為：

(8)

式中：Ccost(i)代表第i個(gè)測(cè)試用例的開(kāi)銷(xiāo)，即ci，EECRS值越小代表約簡(jiǎn)效果越好。

本文通過(guò)與GRE算法和貪心算法進(jìn)行對(duì)比，將3種方法的EECRS值分別進(jìn)行統(tǒng)計(jì)，得到EECRS值分別為78.015、79.846和89.307 ms，螢火蟲(chóng)算法相對(duì)GRE算法的EECRS值減少2.3%，相對(duì)貪婪算法的EECRS值減少12.6%；從最優(yōu)次數(shù)進(jìn)行統(tǒng)計(jì)，3種算法的最優(yōu)次數(shù)分別為390、293、20次(包括約簡(jiǎn)效果相同的情況)。從2方面均可以看出螢火蟲(chóng)算法的約簡(jiǎn)效果是較為可取。

接下來(lái)探討本文測(cè)試方法在不同規(guī)模測(cè)試用例集中表現(xiàn)的差異。通過(guò)對(duì)7個(gè)被測(cè)程序的原始測(cè)試用例集隨機(jī)生成不同大小的測(cè)試用例集進(jìn)行約簡(jiǎn)，實(shí)驗(yàn)結(jié)果表明:規(guī)模為50、100、100和全集的情況下，F(xiàn)A約簡(jiǎn)得到最優(yōu)效果的次數(shù)占比分別為52.86%、75.00%、65.00%和85.71%，由此可以看出，在較小的測(cè)試用例集約簡(jiǎn)中，螢火蟲(chóng)算法的效果比GRE算法差一些，而隨著測(cè)試用例集的規(guī)模增大，螢火蟲(chóng)算法的效果在3個(gè)算法中是最好，具體數(shù)據(jù)如表3所示。

表3 不同規(guī)模下最優(yōu)次數(shù)Table 3 The optimal number of times on different scales

之后討論本文測(cè)試方法在不同工程的測(cè)試用例集表現(xiàn)效果。本文一共測(cè)試了7個(gè)不同的工程，對(duì)7個(gè)工程的測(cè)試結(jié)果進(jìn)行統(tǒng)計(jì)，可以得到以下結(jié)果，如表4所示。

表4 不同被測(cè)程序下最優(yōu)次數(shù)Table 4 The optimal number of times under different testing programs

在7個(gè)項(xiàng)目中最優(yōu)次數(shù)占比分別為70%、82.5%、57.5%、76.25%、57.5%、58.75%、85%，均超過(guò)了50%，且只有replace和tcas 2個(gè)項(xiàng)目的最優(yōu)次數(shù)小于GRE算法。因此總體來(lái)說(shuō)，F(xiàn)A在不同的工程中都有著優(yōu)異的表現(xiàn)，證明該算法有著良好的魯棒性。

為了驗(yàn)證本文中螢火蟲(chóng)算法在不同參數(shù)配置下的求解效率，分別重復(fù)實(shí)驗(yàn)20次，獲得各種配置組合下的平均迭代次數(shù)，其主要參數(shù)為螢火蟲(chóng)數(shù)目和步長(zhǎng)系數(shù)，其結(jié)果如圖1所示。

圖1 不同參數(shù)下迭代次數(shù)Fig.1 The number of iterations with different parameters

從圖中可以看出隨著步長(zhǎng)的減小，迭代次數(shù)從總的趨勢(shì)上來(lái)看是上升的，而螢火蟲(chóng)數(shù)目則對(duì)迭代次數(shù)的影響不大，但是隨著數(shù)目的提升會(huì)增強(qiáng)空間搜索的能力。

3 結(jié)論

1) 本文的螢火蟲(chóng)算法能夠在保證對(duì)測(cè)試需求的覆蓋率的情況下，能夠高效率、高質(zhì)量的完成對(duì)測(cè)試用例集的約簡(jiǎn)，其效果優(yōu)于傳統(tǒng)的貪婪算法和改進(jìn)后的GRE算法，同時(shí)在對(duì)不同規(guī)模和不同被測(cè)程序的實(shí)驗(yàn)中，證明該算法具有良好的魯棒性。

2) 由于智能算法具有一定的隨機(jī)性，在對(duì)相同實(shí)驗(yàn)數(shù)據(jù)進(jìn)行約減時(shí)，有少量實(shí)驗(yàn)可能會(huì)陷入局部收斂，無(wú)法達(dá)到最優(yōu)值。

后續(xù)的研究中，可以對(duì)螢火蟲(chóng)算法本身進(jìn)行更多優(yōu)化，提升算法的效率及魯棒性。