王曙燕, 張海清, 孫家澤

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院， 陜西 西安 710121)

組合測試[1]作為一種可以降低軟件成本并提高其可靠性的測試方法，旨在從龐大的組合空間中選取少量而有效的測試用例集，使這些用例集覆蓋所有組合集，從而完成軟件測試任務(wù)[2]。

兩兩組合測試作為組合測試的一種，近年來已成為很多學(xué)者研究的熱點(diǎn)，且已被證明是一種能有效解決組合用例爆炸問題的方法[3]。組合測試生成最小用例集是一個(gè)NP-hard問題[4]，主要研究方法有遺傳算法(genetic algorithm, GA)[5]、蟻群算法(ant colony algorithm, ACA)[6]、粒子群算法(particle swarm optimization, PSO)[7]和模擬退火(simulated annealing-based, SA)[8]等啟發(fā)式算法，以及K-均值聚類算法(K-means clustering algorithm，K-means)和K-medoids聚類算法(K-medoids clustering algorithm，K-medoids)等聚類算法。目前，粒子群算法、遺傳算法和K-均值聚類算法應(yīng)用較為廣泛。基于K-均值聚類的組合測試用例生成優(yōu)化算法[9]、基于粒子群優(yōu)化和交叉熵(cross entropy, CE)生成組合測試用例的方法[10]和基于島模型并行化的遺傳算法(island parallel genetic algorithm based on Spark, IPGAS )[11]生成組合測試用例時(shí)，雖然可以生成更小規(guī)模的測試用例集，但隨著軟件系統(tǒng)輸入?yún)?shù)的不斷增加，消耗時(shí)長也會成倍增長[12]。

為了改善粒子群算法生成測試用例消耗時(shí)間過長的問題，本文提出一種并行化粒子群算法用于生成兩兩組合測試用例的方法。該方法主要基于大數(shù)據(jù)平臺Spark[13]，采用one-test-at-a-time策略和自適應(yīng)粒子群算法相結(jié)合的方式，將需要覆蓋的所有兩兩組合測試用例集進(jìn)行分組，并分發(fā)到集群中不同的節(jié)點(diǎn)上進(jìn)行尋優(yōu)操作；待所有節(jié)點(diǎn)尋優(yōu)結(jié)束后，利用Spark的Collect()函數(shù)進(jìn)行測試用例集的收集，并對收集后的測試用例集進(jìn)行約簡操作。

1 基礎(chǔ)理論介紹

1.1 覆蓋表

在生成兩兩組合測試用例集時(shí)，需要對待測軟件系統(tǒng)(software under test, SUT)的輸入空間進(jìn)行建模，并生成參數(shù)集，而每個(gè)參數(shù)可能有多個(gè)取值，為了確保SUT在這些參數(shù)相互作用下正常運(yùn)行，需要設(shè)計(jì)相應(yīng)的測試用例檢測出交互故障。兩兩組合測試就是從測試用例集中選出有限但有效的用例集，可通過覆蓋表表示，具體定義如下[14]。

1.2 基本粒子群算法

PSO算法[15]是通過模擬鳥群覓食過程中的遷移和群聚行為而提出的一種基于智能全局隨機(jī)搜索算法。在PSO算法中，每個(gè)優(yōu)化問題的解都是粒子在n維搜索空間中的位置，速度值決定當(dāng)前粒子的飛翔方向和距離，粒子i的速度和位置分別表示為

Vi=(vi,1,vi,2,…,vi,n),Xi=(xi,1,xi,2,…,xi,n)。

每一次迭代通過更新當(dāng)前粒子的最優(yōu)解pBest和種群的最優(yōu)解gBest，進(jìn)行不斷搜索，直到搜索出最優(yōu)解或達(dá)到最大迭代次數(shù)。PSO算法通過適應(yīng)度函數(shù)判斷粒子的優(yōu)劣，判斷的方法是粒子所能覆蓋組合的數(shù)目。在第t+1次迭代中，更新粒子的速度和位置公式[14]分別為

vi,j(t+1)=wvi,j(t)+c2r2[pBest(t)-xi,j(t)]+c1r1[gBest(t)-xi,j(t)],

(1)

xi,j(t+1)=xi,j(t)+vi,j(t+1)。

(2)

式中：vi,j為第i個(gè)粒子在第j維的速度；xi,j為第i個(gè)j維的位置；w為慣性權(quán)重，影響粒子的速度；c1和c2為加速因子，分別表示對當(dāng)前粒子的最優(yōu)位置pBest和種群的最優(yōu)位置gBest的影響；r1和r2取[0,1]范圍內(nèi)的兩個(gè)隨機(jī)數(shù)，目的是保證種群的多樣性。

2 兩兩組合測試用例生成

2.1 并行化策略

并行化策略主要分為生成組合集S、對S進(jìn)行分組、將分組下發(fā)到各個(gè)節(jié)點(diǎn)中進(jìn)行優(yōu)化和最后回收用例集并進(jìn)行約簡等4個(gè)階段。具體框架如圖1所示。

圖1 并行化框架

2.1.1 組合集生成

通過分析實(shí)際問題，計(jì)算因素個(gè)數(shù)N以及每個(gè)因素的取值范圍Di={1,2,…,Li}，并根據(jù)因素的覆蓋強(qiáng)度和約束條件，生成需被覆蓋的二元組集合S。在生成組合集S后，為了增加每個(gè)節(jié)點(diǎn)上用于被覆蓋二元組合的隨機(jī)性，對組合集S進(jìn)行重新排序，隨機(jī)選取S中一半數(shù)量的粒子，并將選取的粒子再按隨機(jī)方式插入到S中。

2.1.2 組合集分組

利用parallelize()將組合集S轉(zhuǎn)換為彈性分布式數(shù)據(jù)集(resilient distributed dataset, RDD),并將該RDD劃分為n個(gè)分區(qū)，其中每個(gè)分區(qū)是由若干個(gè)二元組集合組成的組合集Si(i=1,2,3,…,N)。

2.1.3 測試用例集生成

將分區(qū)后的RDD下發(fā)到集群中不同的節(jié)點(diǎn)進(jìn)行尋優(yōu)操作。在每個(gè)節(jié)點(diǎn)上采用one-test-at-a-time策略和自適應(yīng)粒子群算法相結(jié)合的方式生成兩兩組合測試用例集T。

2.1.4 用例收集并約簡

待所有節(jié)點(diǎn)尋優(yōu)過程結(jié)束后，主節(jié)點(diǎn)利用Spark的Collect()函數(shù)對各個(gè)節(jié)點(diǎn)的用例集T進(jìn)行收集，并對收集后的用例集進(jìn)行約簡操作[10]，最后輸出約簡后的用例集。

2.2 生成測試用例集的過程描述

在集群的每個(gè)從節(jié)點(diǎn)上，基于Spark的并行化的粒子群優(yōu)化算法 (parellel particle swarm optimization based on Spark,PPSOS)主要采用one-test-at-a-time策略和自適應(yīng)粒子群算法相結(jié)合的方式生成兩兩組合測試用例集，一個(gè)節(jié)點(diǎn)上生成測試用例集的具體步驟如下。

步驟1生成一個(gè)空的測試用例集T。

步驟2判斷需要被覆蓋的二元組集合Si是否為空，若不為空，在Si中選取覆蓋率最高的組合Q[16]，生成代表迭代次數(shù)的累加器iterNums, 并置iterNums的初始值為0。

步驟3根據(jù)選取的組合Q生成初始種群P，而P中每個(gè)粒子即為當(dāng)前粒子的初始位置，并將粒子的當(dāng)前位置設(shè)置為該粒子的最佳位置pBest， 粒子中每個(gè)因素取(-1,1)區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)[10]為粒子初始速度。

步驟4進(jìn)入最優(yōu)測試用例的生成階段。更新種群中每個(gè)粒子的適應(yīng)度值[10]，適應(yīng)度值越大代表粒子越優(yōu)；通過粒子的優(yōu)劣更新當(dāng)前粒子的最佳位置pBest和當(dāng)前種群的最優(yōu)位置gBest。

步驟5自適應(yīng)調(diào)整[17]式(1)中的慣性權(quán)重w，利用式(1)和式(2)更新種群中每個(gè)粒子的位置和速度值，并采用“回飛機(jī)制”校正更新后粒子位置不在可行域范圍內(nèi)的參數(shù)，并對該粒子中參數(shù)值不變的因素進(jìn)行擾動(dòng)操作[10]。

步驟6根據(jù)pBest更新種群P，并將累加器iterNums的迭代次數(shù)加1，至此，一次迭代尋優(yōu)過程全部結(jié)束。

步驟7重復(fù)步驟4～步驟6，直到累加器iterNums達(dá)到迭代次數(shù)的上限，返回當(dāng)前種群的最優(yōu)位置gBest，即gBest為新生成的一條最優(yōu)或近似最優(yōu)的測試用例；反之則繼續(xù)迭代。

步驟8剔除Si中已經(jīng)被gBest覆蓋的組合集，并將生成的最優(yōu)測試用例gBest添加到T中。

步驟9重復(fù)步驟2～步驟8，直到Si為空，即該節(jié)點(diǎn)上的所有二元組集合已被覆蓋完畢。至此，從一個(gè)節(jié)點(diǎn)上生成兩兩組合測試用例集的過程已全部結(jié)束。

待所有從節(jié)點(diǎn)尋優(yōu)過程結(jié)束后，主節(jié)點(diǎn)利用Spark的collect()函數(shù)對各個(gè)從節(jié)點(diǎn)上生成的測試用例集T進(jìn)行收集，并對收集后的用例集進(jìn)行約簡，最后輸出約簡后的兩兩組合測試用例集。

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

基于大數(shù)據(jù)平臺Spark，通過Scala語言，實(shí)現(xiàn)PPSOS算法。PPSOS運(yùn)行在由4個(gè)節(jié)點(diǎn)組成的小集群上，該集群基于Standlone模式，將其中一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)Master，其余3個(gè)節(jié)點(diǎn)全部用作Slave。每個(gè)節(jié)點(diǎn)的硬件環(huán)境為3.40 GHz i3 3240 處理、2 G內(nèi)存和160 G硬盤；軟件環(huán)境為Centos 7.0、Java 1.8、Hadoop 2.7.1和Spark 2.1.2。PPSOS算法的參數(shù)r1=r2=0.5,c1=c2=1.49。

3.1 參數(shù)調(diào)整

選取46和53443122兩個(gè)實(shí)例[10]，分析PPSOS中的子種群規(guī)模m和最大迭代次數(shù)Imax對生成測試用例集規(guī)模的影響。實(shí)驗(yàn)在相同條件下進(jìn)行30次，取其規(guī)模的平均值作為比較對象。

表1表示子種群規(guī)模m和迭代次數(shù)Imax分別取不同值時(shí)，生成組合測試用例集規(guī)模的具體情況，加粗標(biāo)記的數(shù)據(jù)表示其最優(yōu)值。

表1 不同m或Imax下測試用例集的規(guī)模/個(gè)

由表1可知，當(dāng)m=100，Imax=10時(shí)，實(shí)例46和53443122生成的用例集規(guī)模分別為22.0和30.6，以及21.8和31.0，規(guī)模均為最小值，說明PPSOS可用于生成較小規(guī)模的兩兩組合測試測試用例集。

3.2 同類算法比較

分別將PPSOS與已有兩兩組合測試用例生成方法在測試數(shù)據(jù)集生成規(guī)模和所消耗時(shí)間上進(jìn)行比較。每個(gè)實(shí)例執(zhí)行了30次，取其最優(yōu)值作為對比數(shù)據(jù)。

3.2.1 測試數(shù)據(jù)集規(guī)模的比較

將PPSOS分別與測試用例自動(dòng)生成系統(tǒng)(automatic efficient test generator, AETG)[18]、基于參數(shù)順序漸進(jìn)擴(kuò)充的兩兩組合覆蓋測試數(shù)據(jù)生成方法 (an IPO-based test generation tool, PAIRTEST)[18]、Williams[18]、Kobayashi[18]、NetWork[18]、解空間樹算法 (pair-testing using solution space tree, PSST)[18]、SA、GA、ACA、交叉熵 (cross entropy, CE)[10]方法和PSO[10]比較，結(jié)果如表2所示，加粗標(biāo)記的數(shù)據(jù)表示其最優(yōu)值。

由表2中數(shù)據(jù)可知，PPSOS在測試用例的生成規(guī)模上除實(shí)例41339235與最優(yōu)值差距較大外，其余實(shí)例均與最優(yōu)值相當(dāng)。因此，PPSOS生成兩兩組合測試用例的方法是有效的。

表2 不同實(shí)例各算法測試數(shù)據(jù)集規(guī)模/個(gè)

3.2.2 算法消耗時(shí)間的比較

將PPSOS在測試用例的生成時(shí)間上分別與SA[10]、GA[18]、ACA[10]、CE[10]、基于Spark的并行化遺傳算法 ( parallel genetic algorithm based on Spark, PGAS)[14]、IPGAS[11]和PSO[10]進(jìn)行比較，結(jié)果如表3所示。

表3 不同實(shí)例各算法運(yùn)行時(shí)間/s

由表3中數(shù)據(jù)可知，除實(shí)例716151453823和6151463823的生成時(shí)間少于PPSOS外，其他算法的生成時(shí)間均大于PPSOS。因此，PPSOS可改善粒子群算法生成測試用例時(shí)間過長的問題。

4 結(jié)語

基于大數(shù)據(jù)平臺Spark，PPSOS將需要被覆蓋的全部二元組集合進(jìn)行分組，并下發(fā)到集群中不同的節(jié)點(diǎn)上進(jìn)行尋優(yōu)操作，待所有節(jié)點(diǎn)尋優(yōu)結(jié)束后再對所有用例集進(jìn)行收集，并對收集到的用例集進(jìn)行約簡。實(shí)驗(yàn)結(jié)果表明，PPSOS生成兩兩組合測試用例集的規(guī)模和消耗的時(shí)間要少于SA、GA和ASA等算法，有效地減少了粒子群算法生成兩兩組合測試用例的消耗時(shí)間。