基于并行化粒子群算法的組合測試用例生成

王曙燕, 張海清, 孫家澤

(西安郵電大學 計算機學院， 陜西 西安 710121)

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

兩兩組合測試作為組合測試的一種，近年來已成為很多學者研究的熱點，且已被證明是一種能有效解決組合用例爆炸問題的方法[3]。組合測試生成最小用例集是一個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)用較為廣泛?；贙-均值聚類的組合測試用例生成優(yōu)化算法[9]、基于粒子群優(yōu)化和交叉熵(cross entropy, CE)生成組合測試用例的方法[10]和基于島模型并行化的遺傳算法(island parallel genetic algorithm based on Spark, IPGAS )[11]生成組合測試用例時，雖然可以生成更小規(guī)模的測試用例集，但隨著軟件系統(tǒng)輸入?yún)?shù)的不斷增加，消耗時長也會成倍增長[12]。

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

1 基礎(chǔ)理論介紹

1.1 覆蓋表

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

1.2 基本粒子群算法

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

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

每一次迭代通過更新當前粒子的最優(yōu)解pBest和種群的最優(yōu)解gBest，進行不斷搜索，直到搜索出最優(yōu)解或達到最大迭代次數(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個粒子在第j維的速度；xi,j為第i個j維的位置；w為慣性權(quán)重，影響粒子的速度；c1和c2為加速因子，分別表示對當前粒子的最優(yōu)位置pBest和種群的最優(yōu)位置gBest的影響；r1和r2取[0,1]范圍內(nèi)的兩個隨機數(shù)，目的是保證種群的多樣性。

2 兩兩組合測試用例生成

2.1 并行化策略

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

圖1 并行化框架

2.1.1 組合集生成

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

2.1.2 組合集分組

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

2.1.3 測試用例集生成

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

2.1.4 用例收集并約簡

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

基于大數(shù)據(jù)平臺Spark，通過Scala語言，實現(xiàn)PPSOS算法。PPSOS運行在由4個節(jié)點組成的小集群上，該集群基于Standlone模式，將其中一個節(jié)點作為主節(jié)點Master，其余3個節(jié)點全部用作Slave。每個節(jié)點的硬件環(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兩個實例[10]，分析PPSOS中的子種群規(guī)模m和最大迭代次數(shù)Imax對生成測試用例集規(guī)模的影響。實驗在相同條件下進行30次，取其規(guī)模的平均值作為比較對象。

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

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

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

3.2 同類算法比較

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

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

將PPSOS分別與測試用例自動生成系統(tǒng)(automatic efficient test generator, AETG)[18]、基于參數(shù)順序漸進擴充的兩兩組合覆蓋測試數(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所示，加粗標記的數(shù)據(jù)表示其最優(yōu)值。

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

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

3.2.2 算法消耗時間的比較

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

表3 不同實例各算法運行時間/s

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

4 結(jié)語

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