基于動態集合進化算法的弱變異測試用例集生成

郭后錢，王微微，尚 穎，趙瑞蓮

(北京化工大學 信息科學與技術學院，北京 100029)(*通信作者電子郵箱Shangy@mail.buct.edu.cn)

基于動態集合進化算法的弱變異測試用例集生成

郭后錢，王微微，尚 穎*，趙瑞蓮

(北京化工大學 信息科學與技術學院，北京 100029)(*通信作者電子郵箱Shangy@mail.buct.edu.cn)

為解決基于集合進化算法(SEA)的弱變異測試用例集生成過程中個體規模固定和執行開銷大的問題，提出一種基于動態集合進化算法(DSEA)的弱變異測試用例集生成方法。以測試用例集為個體，生成覆蓋所有變異分支的弱變異測試用例集。在進化過程中，集合精簡算子根據最優個體的最小子集及其未覆蓋變異分支數量計算所需測試用例集的最小規模，并基于該最小規模調整種群中所有個體的規模，以生成最小規模的弱變異測試用例集，同時設計了適用于評估以測試用例集為個體的適應度函數。實驗結果表明，動態集合進化算法指導弱變異測試用例集生成，獲得的測試用例集規模比個體初始規模平均約簡了50.15%，執行時間比集合進化的弱變異測試用例集生成最多降低了74.58%。因此，動態集合進化算法為最小規模的弱變異測試用例集生成和提升算法速度提供了一種解決方案。

測試用例生成；弱變異測試；分支覆蓋；集合進化算法；貪心算法

0 引言

軟件測試日漸重要，基于變異的測試用例生成技術(Mutation-based Test Case Generation, MTCG)[1]得到了學術界的廣泛關注。變異測試是一種基于故障植入的軟件測試技術，使用變異算子對被測程序語句進行合乎語法的微小改動，被改動的語句稱為變異語句，帶有變異語句的程序稱為變異體[2]。在變異體上執行測試用例，若執行結果和原程序執行結果不同，則稱該變異體被該測試用例殺死，反之則稱該變異體未被殺死。MTCG技術旨在生成極少的測試用例殺死盡可能多的變異體，以獲得較高質量的測試用例集。然而，變異測試代價昂貴，無法應用于軟件實際測試中，因此，如何降低變異執行開銷是MTCG技術的重點研究內容[3]。

變異測試分為弱變異測試和強變異測試，弱變異測試只需檢測變異體變異位置的狀態和原程序不同，即可以判定該變異體被殺死；強變異測試則需要檢測變異體執行結果和原程序輸出結果不同，才可判定變異體被殺死。所以，弱變異測試不用運行完整的程序，其測試代價小于強變異測試，是一種降低變異執行開銷的有效途徑[4]。因此，目前大部分研究集中在弱變異測試用例自動生成方面。Papadakis等[5]基于弱變異測試準則，提出用變異前后的語句構建變異分支，將弱變異測試問題轉化為變異分支覆蓋問題，這在一定程度上降低了變異測試的執行開銷，然而其在測試用例生成時，采用的進化算法每次僅以一個變異分支為目標，生成一條測試用例，效率較低。隨后，Fraser等[6-7]以所有變異分支為目標，以測試用例集為個體，利用遺傳算法實現測試用例集的自動生成；在此基礎上，文獻[8]給出了一種基于集合進化算法(Set Evolutionary Algorithm, SEA)的弱變異測試用例集生成方法，將測試用例集作為個體，增設了集合內部的交叉算子，通過種群進化，使其個體能夠覆蓋更多變異分支，最終生成一個能夠覆蓋全部變異分支的個體或者達到其最大迭代次數，即測試用例集生成成功或失敗。該方法的執行效率高于傳統的面向單個變異分支的測試用例生成方法，但也存在下面兩個問題：

1)個體規模(即其包含的測試用例個數)在進化過程中是固定不變的，因此需要設置適當的個體初始規模。然而通常情況下，測試人員無法事先根據擬覆蓋變異分支的個數確定所需的測試用例個數：取值過大，容易引起測試用例生成開銷的增大和存儲空間的浪費；取值過小，又可能導致測試用例集生成失敗。

2)其以目前廣泛使用的分支距離作為適應度函數，不適合于以集合為個體的進化評估，且該適應度函數計算開銷大。

因此，本文提出了一種基于動態集合進化算法(Dynamic Set Evolutionary Algorithm, DSEA)的弱變異測試用例集生成方法，該方法的個體規模是動態可變的，在進化過程中，尋找合適的個體規模，以生成較小規模的測試用例集，同時避免個體初始規模對于測試用例集生成的影響。本文的主要貢獻如下：

1)提出了一個動態集合進化算法，通過增設集合精簡算子，優化種群中的個體規模，使個體規模在進化過程中得以動態調整，以尋找合適的測試用例集規模。

2)設計了一個適用于集合進化的適應度函數，降低了動態集合進化算法在弱變異測試用例集自動生成中的計算開銷。

3)在5個基準程序上，實現了基于動態集合進化的弱變異測試用例集自動生成，并與使用集合進化的弱變異測試用例集生成方法進行比較，結果表明利用動態集合進化算法的弱變異測試用例集生成其時間開銷最多降低了74.58%，生成的測試用例集規模平均減少了50.15%。

1 相關研究

1.1 弱變異測試

對于給定的被測程序P，在其語句s上實施某一變異算子，得到變異語句s′，將被測程序P中s替換成s′，保持其他語句不變，則可以得到P的一個變異體M[9]。其中變異算子的定義是：在符合語法規則的前提下，從原程序生成差別極小程序(即變異體)的轉換規則。

例如，針對圖1所示原程序中的語句c=a+b，實施基本算術運算符替代變異操作，即分別用“-”“*”和“/”代替原始運算符“+”，生成3個變異體m1、m2和m3，如圖1所示。

變異測試通過執行測試用例并檢測變異體與原程序的執行結果來判定變異體是否被殺死。當測試用例集足夠完備時，未被殺死的變異體，稱為等價變異體[10]。殺死的變異體數量占非等價變異體數量的比值，稱為變異得分[11]，常用來評價測試用例集的質量。變異得分越高，測試用例集質量越好。

一般情況下，測試用例殺死變異體需滿足3個條件：1)可達性條件：變異位置可以被測試用例執行到；2)必要性條件：原程序與變異體在變異位置的執行狀態不同；3)充分性條件：原程序與變異體的輸出結果不同。

滿足上述3個條件的變異測試即為強變異測試，由于充分性條件需要執行完整的程序，執行成本高，為降低執行開銷，Howden[12]給出了弱變異測試準則，只需滿足上述前兩個條件——可達性與必要性，即可判定變異體被殺死。

圖1 變異體示意圖

1.2 弱變異測試用例集生成

弱變異測試用例集生成是指生成滿足弱變異測試準則的測試用例集。Papadakis等[5]認為可以將弱變異測試準則轉化為變異分支覆蓋準則，其變異分支與變異分支覆蓋準則定義如下：

定義1 變異分支。設原語句的主體表達式為e，實施某一變異算子后獲得變異語句的主體表達式為e′，構造條件不等式e!=e′，該條件不等式則為一個變異分支。

例如，對于圖1中原程序語句c=a+b，應用基本算術運算符替代變異操作后，對應的三個變異語句分別為c=a-b、c=a*b和c=a/b，其變異分支分別為a+b!= a-b、a+b!= a*b和a+b!= a/b。

定義2 變異分支覆蓋準則。在原程序P的相應語句前插入其生成的所有變異分支，形成插樁程序P′，對程序P′執行測試用例集，使得P′中每個變異分支其值為真的情況至少出現一次，則稱該測試用例集滿足變異分支覆蓋準則。

將圖1中原程序語句c=a+b的三個變異分支插入到該語句c=a+b前，形成一個新的程序P′，如下所示。

class ClassA{

int s(int a,int b){

int c;

if((a+b)!=(a-b)){printf("m1 is killed");}

if((a+b)!=(a*b)){printf("m2 is killed");}

if((a+b)!=(a/b)){printf("m3 is killed");}

c=a+b;

return c;

}}

若測試用例集能夠覆蓋P′所有變異分支的真分支，則可檢測出原程序與所有變異體在變異位置的執行狀態不同；即測試用例集滿足變異分支覆蓋準則，等同于滿足弱變異測試準則。

因此，基于弱變異測試準則的測試用例生成問題可轉換為滿足變異分支覆蓋準則的測試用例生成問題，通過不斷生成測試用例，直到所有變異分支都被覆蓋為止。

1.3 基于集合進化的弱變異測試用例集生成

將弱變異測試準則轉化為變異分支覆蓋準則，將每個變異分支看作一個目標，使得弱變異測試用例集的自動生成可以看作是一個多目標問題，即生成若干測試用例，覆蓋所有變異分支。

利用進化算法實現測試用例自動生成是一種常用的方法。傳統進化算法，一個個體代表一個解。當一個個體代表多個解的集合時，相應的進化優化算法稱為集合進化[13]，該算法可以一次生成滿足多個目標的解集，而不是每次生成滿足單個目標的解。將集合進化算法應用于弱變異測試用例集生成，其種群中的個體為測試用例集合，通過交叉、變異操作生成新個體。基于集合進化的弱變異測試用例集生成如算法1所示。

算法1 基于集合進化的弱變異測試用例生成算法SEA。

Initialpop;

//初始化

evaluate(pop);

//計算適應度值

repeat

Inner_crossover(pop);

//個體內部交叉操作

Inter_crossover(pop);

//個體之間交叉操作

Mutate(pop);

//個體變異操作

evaluate(pop);

//計算適應度值

pop=update(pop);

//種群更新

until(滿足終止條件)

1)集合交叉Crossover()。

集合進化種群中的個體是一個集合，其既可以通過兩個集合交叉產生新個體，又可以通過集合內部交叉產生新個體，因此，集合交叉又可分為集合間交叉Inter_crossover()和集合內交叉Inner_crossover()兩種，其中集合內交叉是集合進化算法所特有的。常用的集合交叉方式為單點交叉。

2)集合變異Mutate()。

集合變異是指通過對集合(個體)中的元素進行更改，產生新的個體。常用的集合變異策略是隨機變異，即隨機選擇個體的某個基因進行變異。

3)種群更新update()。

種群更新策略決定哪些個體可以進入下一代種群。集合進化算法中常用的種群更新策略為(μ+λ)更新策略，即種群規模為μ，其通過交叉變異產生λ個子代個體，在μ個父代個體與λ個子代個體中根據適應度值選擇μ個個體進入下一代種群。

將集合進化算法應用于弱變異測試用例集生成，其生成效率高于傳統方法，但其個體規模在進化過程中是固定不變的，需要事先設置合適的個體初始規模，這是很困難的。此外，其使用分支距離作為適應度函數，需要計算謂詞分支距離，增加了計算開銷。因此，本文提出一種動態集合進化算法，用于實現弱變異測試用例集的自動生成。

2 動態集合進化的弱變異測試用例集生成

本文針對弱變異測試用例集自動生成，提出一種動態集合進化算法，通過增設集合精簡算子，動態調整個體規模，以尋找合適的測試用例集規模，同時避免個體初始規模對生成測試用例集規模的影響；設計了適用于集合進化的適應度函數，降低弱變異測試用例集生成的計算開銷。

2.1 動態集合進化的弱變異測試用例集生成算法

基于動態集合進化的弱變異測試用例集生成的核心思想是以變異分支覆蓋為準則，以測試用例集合為個體，在種群進化過程中，動態調整個體規模，以尋找合適的測試用例集規模，生成較小規模的測試用例集，實現弱變異測試用例集的自動生成。基于動態集合進化的弱變異測試用例集生成如算法2所示。

算法2 基于動態集合進化的弱變異測試用例集生成DSEA。

Initialpop;

//初始化

evaluate(pop);

//計算個體的適應度值

repeat

refine_set=Greedy_Essential(best_Ind);

//精簡最優個體

if(best_Ind.fitness==0){returnrefine_set;}

//測試用例集生成

else{

Nt=estimate(refine_set);

//估算個體(測試用例集)合適規模

pop=adjust(pop,Nt,refine_set);

//調整個體

Inner_crossover(pop);

//個體內部交叉操作

Inter_crossover(pop);

//個體之間交叉操作

Mutate(pop);

//變異操作

evaluate(pop);

//計算個體的適應度值

pop=update(pop);

//種群更新

}

until(滿足終止條件)

因此，基于動態集合進化的弱變異測試用例集生成首先初始化種群pop，利用evaluate()函數計算種群中個體的適應度值；通過Greedy_Essential()函數對最優個體進行精簡，除去冗余，獲得最優個體的精簡集refine_set；若最優個體精簡集refine_set能夠覆蓋所有的變異分支，則弱變異測試用例集生成，算法結束；否則，estimate()函數根據最優個體精簡集規模和未覆蓋的變異分支數量估算個體(測試用例集)的適當規模Nt，adjust()函數依據Nt調整種群的個體規模；對調整后的種群應用集合進化算法，實施交叉、變異操作生成新個體，update()函數根據種群更新策略對種群進行更新。重復上述過程，直到進化次數到達指定值或者生成弱變異測試用例集。

2.2 適應度函數及動態集合進化的設計

2.2.1 適應度函數

適應度函數用來評估個體的優劣，本文動態集合進化算法的個體是測試用例集，目標是覆蓋全部變異分支，因此本文將個體未覆蓋的變異分支數量作為衡量個體優劣的適應度函數。

假設被測程序的變異分支集為B，當前個體Ind對每個變異分支bi(bi∈B)的覆蓋情況用fi(Ind)表示，即fi(Ind)=0表示變異分支bi被當前個體Ind覆蓋，fi(Ind)=1表示個體Ind未覆蓋變異分支bi，則適應度函數Fitness(Ind)的計算公式可以表示為：

(1)

Fitness(Ind)值越小，說明Ind沒有覆蓋的變異分支越少。當Fitness(Ind)為0時，說明當前個體覆蓋了全部的變異分支，滿足變異分支覆蓋準則。

2.2.2 集合精簡算子

集合精簡算子用以調整種群中個體的規模，以尋找適當的測試用例集規模，生成較小規模的測試用例集，同時可在集合進化過程中節省存儲空間。

集合精簡算子由3部分組成，即去除最優個體的冗余基因獲得其精簡集Greedy_Essential()，估算適當的個體(測試用例集)規模estimate()和動態調整個體規模adjust()。

獲得最優個體精簡集Greedy_Essential()：個體中冗余的基因擴大了自身的規模，通過除去個體中的冗余基因，可以獲得較小規模的個體，同時還可以節省存儲空間。E貪心算法[14]是一種常用的精簡測試用例集方法，它在貪心算法的基礎上加入了essential策略，即由essential策略和greedy策略組成，essential策略的主要思想是選取出必要的元素。本文中的個體是測試用例集，除去測試用例集中的冗余測試用例，即可對該測試用例集進行精簡，因此，本文根據E貪心算法，設計Greedy_Essential()函數，對最優個體進行精簡。假設被測程序的變異分支集為B，最優個體由m個測試用例組成，即best_Ind={x1,x2,…,xm}，best_Ind覆蓋的變異分支集為Rp，未覆蓋的變異分支集為Rf，則該最優個體的適應度函數值為|Rf|；若測試用例xi(xi∈best_Ind)覆蓋的變異分支集記為bxi，則best_Ind中測試用例對應覆蓋的變異分支集記為R={bx1,bx2,…,bxm}, 那么Greedy_Essential()首先應用essential策略，選取出必要的測試用例，即某個變異分支只被best_Ind中的某個測試用例所覆蓋，那么這個測試用例就不可能是冗余的測試用例，將該測試用例放入精簡集refine_set并從best_Ind中刪除，同時從R和Rp中刪去其覆蓋的變異分支，繼續從best_Ind中選取必要的測試用例，放入精簡集refine_set，直到Rp中不存在只被best_Ind中一個測試用例覆蓋的變異分支為止。然后使用greedy策略，根據R中變異分支集的規模，從best_Ind中選取測試用例，每次選取R中最大規模元素對應的測試用例，放入精簡集refine_set，并從R和Rp中刪去該測試用例覆蓋的變異分支，繼續選取直到Rp中不存在變異分支。綜上，選取出的所有測試用例組成了最優個體精簡集refine_set。

估算個體合適規模estimate()：種群進化過程中，通過在個體中添加額外的測試用例以覆蓋其未覆蓋的變異分支，可以估算合適的個體規模。由于最優個體未覆蓋變異分支數量最少，所以其在理論上需要添加的額外測試用例個數最少。因此，可以通過最優個體精簡集規模|refine_set|加上其未覆蓋變異分支數|Rf|作為估算的個體合適規模，即個體合適規模為Nt=|refine_set|+|Rf|。

調整個體規模adjust()：在每一輪種群進化過程中，根據估算的個體合適規模Nt=|refine_set|+|Rf|，對種群中的個體規模進行調整。比較當前種群中的個體規模與Nt的大小：若個體規模≥Nt，調整策略為：最優個體通過其精簡集refine_set中加入|Rf|條測試用例，將規模調整為Nt，其他個體移除(|best_Ind|-Nt)條測試用例，將規模調整為Nt；若個體規模

2.2.3 種群更新策略

集合進化的種群更新update()采用(μ+λ)更新策略，即在進化過程中保留父代與子代中的優秀個體，易導致種群失去多樣性。結合進化策略中(μ，λ)更新[15]中只在λ個子代個體中擇優選擇μ個個體組成下一代種群，本文設計一種新的種群更新策略(μ，λ+1)更新策略，μ表示當前種群中有μ個父代個體，λ+1表示從λ個子代個體與1個父代最優個體組成的臨時種群(要求λ+1>μ)中根據適應度值擇優選擇出μ個個體組成下一代種群，不僅保證了種群的多樣性，同時保證了種群進化的質量不會下降。

3 實驗

為驗證本文方法能否在不受個體初始規模影響的前提下，生成較小規模的弱變異測試用例集并降低執行開銷，設計實驗，分析比較文獻[8]中的基于集合進化的弱變異測試用例集生成方法和本文提出的基于動態集合進化的弱變異測試用例集生成方法在生成的測試用例集規模和執行時間上的優劣。

3.1 基準程序

實驗以5個變異測試常用的Java程序作為基準程序[5,8],其程序的ID、總代碼行數、生成的變異分支數以及程序說明如表1所示。

表1 基準程序

3.2 研究問題

為驗證本文的動態集合進化算法在生成弱變異測試用例集時，是否能不受個體初始規模的影響，生成較小規模的測試用例集并降低執行開銷，本文從以下兩個方面進行研究：

1)利用動態集合進化算法實現弱變異測試用例集自動生成時，個體初始規模對其最終生成的測試用例集規模是否有影響？與使用集合進化的弱變異測試用例集生成方法相比，能否生成更小規模的測試用例集？

2)利用動態集合進化算法生成弱變異測試用例集，相比于基于集合進化的弱變異測試用例集生成，其執行開銷是否有所降低？

3.3 實驗過程

首先，利用MuClipse工具[16]對表1所示的5個基準程序實施15種方法級運算符變異操作，如算術運算符替換操作、邏輯運算符插入替換等操作，形成變異分支，并將所有變異分支插入原程序相應位置，形成插樁后的被測程序，其相應的變異分支數如表1第4列所示。

然后，利用集合進化算法和本文提出的動態集合進化算法，生成基準程序的弱變異測試用例集。集合進化算法采用分支距離作為其適應度，計算方法如表2所示，T、F列分別表示條件語句為真(T)、假(F)時分支距離。

表2 分支距離計算方法

為保持實驗結果的可比性，兩種算法使用相同的參數，即種群規模為100，集合內部的交叉概率P_inner為0.2，集合間交叉概率P_inter為0.7，集合變異的概率P_mutation為0.1。

實驗環境為Intel Core i7-4790 CPU 3.60 GHz，4.00 GB內存，采用Microsoft Windows 7 64位操作系統和Eclipse SDK 4.2.2集成開發環境。

3.4 結果與分析

對于表1程序，分別以本文提出的動態集合進化算法(DSEA)與集合進化算法(SEA)生成弱變異測試用例集，生成的測試用例集規模如表3所示。

為探討基于動態集合進化算法的弱變異測試用例集生成方法最終產生的測試用例集規模是否受個體初始規模的影響，本文對5個基準程序，在5組個體初始規模下，進行弱變異測試用例集生成。每個程序第一組個體初始規模的設置參照文獻[8]的個體初始規模值，隨后個體規模以5遞增，每組實驗重復十次，生成的弱變異測試用例集平均規模如表3所示。

表3 動態集合進化算法生成的測試用例集規模

由表3可知，利用動態集合進化算法實現弱變異測試用例集生成時，其生成的測試用例集規模不受個體初始規模的影響，并且約簡率最低為31.98%，平均為50.15%，約簡率是指最終生成的測試用例集約簡規模與個體初始規模的比值。

此外，實驗還討論了個體初始規模小于所需測試用例集規模的情況，結果如表4所示。

由表4可以看出，即使個體初始規模較小，利用動態集合進化算法(DSEA)仍能生成所需的測試用例集，滿足弱變異測試準則。而集合進化算法(SEA)在個體初始規模小于所需測試用例集規模時，無法生成覆蓋全部變異分支的測試用例集。

表4 個體初始規模較小的弱變異測試用例集生成

集合進化算法應用于弱變異測試用例集生成時，其生成效率受個體初始規模影響，且最終生成的測試用例集規模即為個體初始規模。而動態集合進化算法其最終生成的測試用例集規模不受個體初始規模影響，且生成的測試用例集規模很大程度上接近所需測試用例集的最小規模。

為分析對比動態集合進化算法和集合進化算法在生成弱變異測試用例集的時間開銷，本文對5個基準程序，參照表3最終生成的測試用例集規模設置個體初始規模，重復進行10次弱變異測試用例集生成，其生成的測試用例集規模和執行時間如表5所示。

表5 兩種算法執行時間開銷對比

由表5可知，利用動態集合進化算法生成的弱變異測試用例集規模更小，其執行時間也更少。執行時間減少最多的是程序J2，比集合進化算法降低了74.58%，程序J4的執行時間也降低了64.13%。從表1可以看出，J2和J4的程序規模較大，生成的變異體數量也較多，因此可以認為，被測程序的變異分支數越多，動態集合進化算法越適用，弱變異測試用例集生成效率越高。

為更直觀地對比兩種算法的弱變異測試用例集生成時間開銷，圖2(a)(b)分別給出了J2和J4 10次重復生成弱變異測試用例集的執行時間，并按執行時間升序排列。由圖2可以看出動態集合進化算法應用于弱變異測試用例集生成時，其執行時間明顯少于集合進化算法。

為分析比較兩種算法在不同個體初始規模下，對弱變異測試用例集生成所需時間的影響，本文設置了5組不同的個體初始規模，圖3(a)(b)分別給出了程序J2和J4在不同個體初始規模下的測試用例集生成時間開銷。

由圖3可以看出，不同的個體初始規模下，動態集合進化算法實現弱變異測試用例集生成的執行時間明顯低于集合進化算法。所以，利用動態集合進化算法生成弱變異測試用例集，相比于基于集合進化的弱變異測試用例集生成，其執行開銷明顯降低。

圖2 兩種算法時間開銷對比

圖3 兩種算法不同個體初始規模的時間開銷對比

4 結語

測試用例集的自動生成一直是軟件工業界關注的重點。本文在弱變異測試準則轉化為變異分支覆蓋準則的基礎上，研究如何高效快速地生成較小規模的弱變異測試用例集。基于此，本文提出一種基于動態集合進化算法的弱變異測試用例集生成方法，以測試用例集為個體，在進化過程中根據執行信息動態調整個體規模，尋找適當的測試用例集規模，生成較小規模的測試用例集，降低執行開銷和節省存儲空間；同時設計了一個適用于集合進化的適應度函數，以降低計算開銷。研究表明基于動態集合進化的弱變異測試用例集生成方法在執行開銷和生成的測試用例集規模得到了極大的改善，提高了弱變異測試效率。

References)

[1] HANH L T M, BINH N T, TUNG K T. Survey on mutation-based test data generation [EB/OL]. [2017- 01- 04]. http://iaesjournal.com/online/index.php/IJECE/article/view/7917.

[2] PAPADAKIS M, MALEVRIS N. Searching and generating test inputs for mutation testing [J]. SpringerPlus, 2013, 2(1): 121.

[3] DAVE M, AGRAWAL R. Mutation testing and test data generation approaches: a review [C]// Smart Trends for Information Technology and Computer Communications. Berlin: Springer, 2016: 373-382.

[4] SOUZA F C, SOUZA M, PAPADAKIS M, et al. Test data generation techniques for mutation testing: a systematic mapping [EB/OL]. [2014- 04- 25]. http://pages.cs.aueb.gr/～mpapad/papers/eselaw2014.pdf.

[5] PAPADAKIS M, MALEVRIS N. Automatically performing weak mutation with the aid of symbolic execution, concolic testing and search-based testing [J]. Software Quality Control, 2011, 19(4): 691-723.

[6] FRASER G, ARCURI A. Whole test suite generation [J]. IEEE Transactions on Software Engineering, 2013, 39(2): 276-291.

[7] FRASER G, ARCURI A. Achieving scalable mutation-based generation of whole test suites [J]. Empirical Software Engineering, 2015, 20(3): 783-812.

[8] 張功杰,鞏敦衛,姚香娟.基于變異分析和集合進化的測試用例生成方法[J].計算機學報,2015,38(11):2318-2331.(ZHANG G J,GONG D W, YAO X J. Test case generation based on mutation analysis and set evolution [J]. Chinese Journal of Computers, 2015, 38(11): 2318-2331.)

[9] 鞏敦衛,陳永偉,田甜.消息傳遞并行程序的弱變異測試及其轉化[J].軟件學報,2016,27(8):2008-2024.(GONG D W, CHEN Y W, TIAN T. Weak mutation testing and its transformation for message passing parallel programs [J]. Journal of Software, 2016, 27(8): 2008-2024.)

[10] KINTIS M, PAPADAKIS M, MALEVRIS N. Isolating first order equivalent mutants via second order mutation [C]// Proceedings of the 2012 IEEE 5th International Conference on Software Testing, Verification and Validation. Washington, DC: IEEE Computer Society, 2012: 701-710.

[11] JIA Y, HARMAN M. An analysis and survey of the development of mutation testing [J]. IEEE Transactions on Software Engineering, 2011, 37(5): 649-678.

[12] HOWDEN W E. Weak mutation testing and completeness of test sets [J]. IEEE Transactions on Software Engineering, 1982, 8(4): 371-379.

[13] GONG D, WANG G, SUN X, et al. A set-based genetic algorithm for solving the many-objective optimization problem [J]. Soft Computing, 2015, 19(6): 1477-1495.

[14] 章曉芳,徐寶文,聶長海,等.一種基于測試需求約簡的測試用例集優化方法[J].軟件學報,2007,18(4):821-831.(ZHANG X F, XU B W, NIE C H, et al. An approach for optimizing test suite based on testing requirement reduction [J]. Journal of Software, 2007, 18(4): 821-831.)[15] 周永權,張明,趙斌.基于進化策略方法求任意函數的數值積分[J].計算機學報,2008,31(2):196-206.(ZHOU Y Q, ZHANG M, ZHAO B. Solving numerical integration based on evolution strategy method [J]. Chinese Journal of Computers, 2008, 31(2): 196-206.)

[16] SEGURA S, HIERONS R M, BENAVIDES D, et al. Automated metamorphic testing on the analyses of feature models [J]. Information and Software Technology, 2011, 53(3): 245-258.

Weakmutationtestcasesetgenerationbasedondynamicsetevolutionaryalgorithm

GUO Houqian, WANG Weiwei, SHANG Ying*, ZHAO Ruilian

(CollegeofInformationScienceandTechnology,BeijinguniversityofChemicalTechnology,Beijing100029,China)

To solve the problem of fixed individual scale and high execution cost of weak mutation test case set generation based on Set Evolutionary Algorithm (SEA), a generation method of weak mutation test case set based on Dynamic Set Evolutionary Algorithm (DSEA) was proposed. The test case sets were used as individuals to generate some weak mutations to cover all mutant branches. In the evolutionary process, according to the minimum subset of the optimal individuals and the number of uncovered mutation branches, the minimum scale of the required test case set was calculated by the set compact operator. And the size of all individuals in the population was adjusted based on the minimum scale to generate the smallest scale of the weak mutation test case set. At the same time, a fitness function for assessing a use case set as an individual was designed. The experimental results show that when the dynamic ensemble evolution algorithm is used to guide the generation of weak mutation test cases, and the scale of the test cases was 50.15% lower than the initial size of the individuals, and the execution time is lower than that of SEA by 74.58% at most. Thus, the dynamic ensemble evolution algorithm provides a solution for generating of the weak mutation test case set with minimum scale and enhancing the algorithm speed.

test case generation; weak mutation testing; branch coverage; Set Evolutionary Algorithm (SEA); greedy algorithm

2017- 03- 30;

2017- 04- 23。

國家自然科學基金資助項目(61472025, 61672085)。

郭后錢(1990—)，女，安徽六安人，碩士研究生，主要研究方向：軟件測試； 王微微(1990—)，女，河北滄州人，博士研究生，CCF會員，主要研究方向：軟件測試； 尚穎(1976—)，女，吉林四平人，講師，博士，CCF會員，主要研究方向：軟件測試； 趙瑞蓮(1964—)，女，山西忻州人，教授，博士，CCF會員，主要研究方向：軟件測試、軟件可靠性分析。

1001- 9081(2017)09- 2659- 06

10.11772/j.issn.1001- 9081.2017.09.2659

TP311.5

A

This work is partially supported by the National Natural Science Foundation of China (61472025, 61672085).

GUOHouqian, born in 1990, M. S. candidate. Her research interest include software testing.

WANGWeiwei, born in 1990, Ph. D. candidate. Her research interest include software testing.

SHANGYing, born in 1976, Ph. D., lecturer. Her research interest include software testing.

ZHAORuilian, born in 1964, Ph. D., professor. Her research interests include software testing, software reliability analysis.