王曙燕，陳朋媛，孫家澤

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

基于變異分析的測試用例約簡方法

王曙燕*，陳朋媛，孫家澤

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

針對回歸測試過程中由于測試需求的變更導(dǎo)致測試用例規(guī)模不斷擴(kuò)大、測試成本不斷增加的問題，提出一種基于變異分析的測試用例約簡方法(RTM)。首先，以測試用例能否檢測到指定變異體為依據(jù)，對測試用例進(jìn)行劃分并創(chuàng)建二進(jìn)制數(shù)值形式的變異體事務(wù)集矩陣；然后，應(yīng)用改進(jìn)的關(guān)聯(lián)挖掘算法獲取測試用例間的關(guān)聯(lián)關(guān)系；最后，根據(jù)這些關(guān)聯(lián)關(guān)系有效約簡測試用例。6個經(jīng)典程序仿真實(shí)驗(yàn)結(jié)果表明，RTM能夠使約簡后的測試用例約簡率達(dá)到37%，與傳統(tǒng)貪心算法和啟發(fā)式算法相比，測試用例約簡率提高了6%，且在提高測試用例約簡率的同時，保證了測試覆蓋率，單個測試用例的測試覆蓋率平均提高了11%。所提方法能夠利用盡可能少的測試用例滿足更多的測試需求，有效提高了測試效率，降低了測試成本。

回歸測試；測試用例約簡；變異分析；變異體；關(guān)聯(lián)挖掘

0 引言

在軟件開發(fā)過程中，需要頻繁地進(jìn)行軟件測試，測試用例需要不斷被設(shè)計、修改和執(zhí)行，構(gòu)成回歸測試的測試用例集合[1]。在回歸測試過程中，會產(chǎn)生大量冗余的測試用例，有效約簡測試用例，利用盡可能少的測試用例最大限度滿足給定的測試目標(biāo)，能夠有效提高測試效率，降低測試成本[2-4]。傳統(tǒng)的測試用例約簡方法主要有貪心(Greedy, G)算法、啟發(fā)式(Heuristic, H)算法和整數(shù)規(guī)劃等[5]。G算法和H算法總是在當(dāng)前測試需求中尋找最優(yōu)的測試用例，所選擇的測試用例是某種意義上的局部最優(yōu)，不能保證全局最優(yōu)。整數(shù)規(guī)劃法將最優(yōu)代表集選擇問題轉(zhuǎn)化為整數(shù)線性規(guī)劃問題，但時間復(fù)雜度較高，運(yùn)算開銷呈指數(shù)級增長。

經(jīng)過多年研究，測試用例約簡方法已有了很大改進(jìn)[5-9]。華麗等[10]利用遺傳算法的全局搜索能力獲取測試用例優(yōu)化解集合，再根據(jù)蟻群算法的正反饋性得到最小集合的最優(yōu)解。但該方法的約簡效果取決于最初產(chǎn)生的測試用例集，不能從根本上對測試用例進(jìn)行優(yōu)化。聶長海等[11]首先提出依據(jù)測試需求約簡測試用例的方法，根據(jù)測試需求間的關(guān)聯(lián)關(guān)系對測試用例進(jìn)行劃分，再利用啟發(fā)式算法、貪心算法等獲取可覆蓋所有測試需求的最小測試用例集。而在回歸測試中測試需求往往包括關(guān)注需求集和無關(guān)需求集，該方法在約簡測試用例過程中，沒有考慮無關(guān)需求集的問題。顧慶等[1]提出一種啟發(fā)式貪婪搜索方法，減少了對無關(guān)測試需求的覆蓋，最大限度地降低了測試成本。陳靜等[12]提出一種基于關(guān)聯(lián)模式的測試用例約簡模型，根據(jù)程序模塊、測試需求以及測試用例間的關(guān)聯(lián)關(guān)系約簡測試用例，但目前該研究仍處于理論研究階段，并沒有實(shí)現(xiàn)針對具體測試需求約簡測試用例的方法。劉鋒等[13]提出一種向量相似度算法，根據(jù)測試用例間的相似度、覆蓋度和冗余度約簡測試用例，但該方法以矩陣形式存儲數(shù)據(jù)，占用存儲空間比較大，且容易陷入局部最優(yōu)解。

針對上述研究中未考慮測試用例間關(guān)聯(lián)關(guān)系以及數(shù)據(jù)存儲、計算消耗大的問題，本文提出一種基于變異分析的測試用例約簡方法(Reduction method of Test suites based on the analysis of Mutation, RTM)。一方面，從變異測試能夠衡量測試用例充分性[14-18]這一特性出發(fā)約簡測試用例；另一方面，創(chuàng)建二進(jìn)制形式的變異體事務(wù)集矩陣，通過位運(yùn)算獲取測試用例間關(guān)聯(lián)關(guān)系。RTM首先根據(jù)源程序特征設(shè)計變異因子并產(chǎn)生變異體，避免無關(guān)變異體被覆蓋而降低測試效率；然后將原始測試用例集分別在原程序和變異體上執(zhí)行，以測試用例能否檢測到指定變異體為依據(jù)，對測試用例進(jìn)行劃分，創(chuàng)建二進(jìn)制變異體事務(wù)集矩陣；再根據(jù)改進(jìn)的關(guān)聯(lián)挖掘算法獲取測試用例間的關(guān)聯(lián)關(guān)系，最后根據(jù)所獲取的關(guān)聯(lián)關(guān)系有效約簡測試用例。

1 基于變異分析的測試用例約簡模型

設(shè)原始測試用例集T={t1,t2,…,tm}，根據(jù)源程序特征設(shè)計變異因子并生成大量變異體，識別出等價變異體，將非等價變異體定義為P={p1,p2,…,pn}。描述測試用例約簡模型需要以下定義。

定義1 變異評分。變異測試最終通過變異評分(Mutation Score, MS)來評估測試用例集的測試充分性，變異評分MS(P,T)通過式(1)計算獲得：

(1)

其中：函數(shù)killed(P,T)返回測試用例集T能夠檢測出的變異體數(shù)量；|P|為變異體總數(shù)；eqv(P)函數(shù)返回等價變異體的數(shù)量，等價變異體與原有程序在語法上存在差異，但在語義上保持一致。等價變異體的檢測是一個不可判定問題，已有的檢測方法主要有靜態(tài)檢測方法和動態(tài)檢測方法。根據(jù)式(1)可以看出，MS的取值范圍介于0 到1之間，MS的取值越高，代表測試用例充分性越高，實(shí)際缺陷檢測能力越強(qiáng)[19]。

定義2 測試需求。將測試用例能夠檢測到變異體作為測試需求，n個測試需求定義為P={p1,p2,…,pn}，那么,P與T之間的映射關(guān)系S={(p,t)∈P×T|t能夠檢測到變異體p}，R(t)表示測試用例t能夠滿足的所有測試需求。

定義3 變異體事務(wù)項(xiàng)。將不能夠檢測到變異體pk的測試用例集合作為一個變異體事務(wù)項(xiàng)MListk(MListk={t1,t2,…,tγ})，其中，pk∈P，ti∈T。

定義4 變異體事務(wù)集。所有變異體事務(wù)項(xiàng)構(gòu)成變異體事務(wù)集，n個變異體事務(wù)項(xiàng)構(gòu)成的變異體事務(wù)集表示為MLists={MList1,MList2,…,MListn}。

定義5 變異體事務(wù)集矩陣。變異體集合與測試用例集合存在一一對應(yīng)的關(guān)系，所有關(guān)系集合組成一個n×m的二進(jìn)制矩陣A:

矩陣的行表示一個變異體事務(wù)項(xiàng)，若事務(wù)項(xiàng)MListi中包含測試用例tj，即測試用例tj不可以檢測到變異體ai，那么aij=1；否則aij=0。

測試用例約簡旨在用最小的測試用例集盡可能地滿足更多的測試需求，本文將變異體集合作為測試需求，變異體集合P與原始測試用例集T存在映射關(guān)系S={(p,t)∈P×T|t能夠檢測到變異體p}，測試用例約簡問題等價于求最小集合覆蓋問題。

令R(T)與R(T′)分別表示原始測試用例集T與用例集T′所滿足測試需求集，其中T′?T，若R(T′)=R(T)，并且不存在任何t(t∈T)，使R(T′-{t})=R(T)，即若測試用例集T與T′滿足相同的測試需求，并且不存在比T′更小的集合，使其與原始測試用例集滿足相同的測試需求，那么T′為最小測試用例集合，即約簡后的測試用例集合。

2 測試用例約簡方法

本文提出一種基于變異分析的測試用例約簡方法(RTM)，RTM的測試用例約簡流程如圖1所示。

圖1 RTM的測試用例約簡流程Fig. 1 Test suite reduction process of RTM

首先在源程序與變異體上分別執(zhí)行測試用例，以測試用例能否檢測到指定變異體為依據(jù)，對測試用例進(jìn)行劃分并獲取測試用例頻繁1項(xiàng)集，根據(jù)頻繁1項(xiàng)集創(chuàng)建變異體事務(wù)集矩陣A，矩陣元素取值0或1，1表示對應(yīng)測試用例不能夠檢測到指定變異體，否則能夠檢測到。設(shè)計實(shí)現(xiàn)基于二進(jìn)制矩陣的關(guān)聯(lián)挖掘算法，獲取測試用例間的關(guān)聯(lián)關(guān)系，根據(jù)所獲取的測試用例間的關(guān)聯(lián)關(guān)系有效約簡測試用例。

2.1 初始化變異體事務(wù)集矩陣

分別在原程序O與變異體集合P={p1,p2,…,pn}上執(zhí)行測試用例集T={t1,t2,…,tm}，以測試用例能否檢測到指定變異體為依據(jù)，獲取測試用例頻繁1項(xiàng)集，將不能夠檢測到指定變異pi(pi∈P)的所有測試用例作為一個變異體事務(wù)項(xiàng)MListi，所有變異體事務(wù)項(xiàng)組成變異體事務(wù)集MLists。

令關(guān)聯(lián)挖掘過程中最小支持度為minSup，將頻數(shù)大于等于minSup的測試用例降序排列，存儲在測試用例列表ErrList中，由變異體事務(wù)集MLists與測試用例列表ErrList的映射關(guān)系創(chuàng)建變異體事務(wù)集矩陣A。矩陣的每一行表示一個變異體事務(wù)項(xiàng)，矩陣元素按式(2)設(shè)置。

(2)

其中，ai為矩陣第i行，對應(yīng)變異體事務(wù)集中第i個事務(wù)項(xiàng)MListi。式(2)表明，若MListi中包含測試用例tx，即tx不能檢測到變異體pi，變異體pi相對測試用例tx是可存活變異體，那么tx對應(yīng)矩陣第i行第x列的元素賦值為1；否則賦值為0。

2.2 約簡變異體事務(wù)集矩陣

初始化創(chuàng)建的變異體事務(wù)集矩陣規(guī)模比較龐大，其中包含許多冗余的事務(wù)項(xiàng)，刪除其中無意義的事務(wù)項(xiàng)，合并重復(fù)的事務(wù)項(xiàng)，能夠有效縮減矩陣的規(guī)模，大幅度提高獲取測試用例間關(guān)聯(lián)關(guān)系的效率。

約簡變異體事務(wù)集矩陣，首先需要按照事務(wù)項(xiàng)中所包含的測試用例數(shù)，對事務(wù)項(xiàng)進(jìn)行排序，即對矩陣A按行降序排序，再對排序后的矩陣進(jìn)行約簡。

算法1 約簡變異體事務(wù)集矩陣。

輸入 初始化創(chuàng)建的變異體事務(wù)集矩陣An×m；

輸出 約簡后的變異體事務(wù)集矩陣An×m。

步驟1 對矩陣A按行降序排列。

步驟4 增加MListj頻數(shù)，刪除矩陣第i行元素，矩陣預(yù)處理行向量下移，重復(fù)步驟2。

步驟5 當(dāng)前預(yù)處理事務(wù)項(xiàng)MListi下移，即矩陣預(yù)處理行向量下移，重復(fù)步驟2。

步驟6 刪除矩陣當(dāng)前行及其后所有元素。

步驟7 改變矩陣當(dāng)前規(guī)模。

2.3 獲取變異體事務(wù)集頻繁模式

獲取變異體事務(wù)集的頻繁模式L(L={L1,L2,…,Li,…,La-1})，需逐個獲取事務(wù)項(xiàng)MListi(1≤i

算法2 獲取變異體事務(wù)集頻繁模式。

輸入 約簡后的變異體事務(wù)集矩陣An×m；

輸出 測試用例間的頻繁模式集。

步驟1 若?k(k∈(1,m))滿足aik∩ajk=1，那么MListi與MListj交集集合Lij=Lij+{k}，添加所有符合該條件的k值到Lij中。

步驟3 若l?Li，且集合l在Li中的頻數(shù)為count，那么count=count+aj0；否則count=ai0+aj0，同時令Li=Li+l。

2.4 約簡測試用例

由頻繁項(xiàng)集及其對應(yīng)的置信度產(chǎn)生關(guān)聯(lián)規(guī)則相對較為容易和直觀，根據(jù)已有的方法即可獲取所有的關(guān)聯(lián)規(guī)則Rules={rule1,rule2,…,ruleρ}，令測試用例約簡置信度為minConf，根據(jù)所獲取的關(guān)聯(lián)規(guī)則及其對應(yīng)的置信度conf可有效約簡測試用例。

若測試用例集T′(T′≠?)與測試用例tb存在關(guān)聯(lián)規(guī)則T′?tb，且置信度conf≥minConf，即測試用例集T′不能夠檢測到的變異體，tb也同樣檢測不到的可靠程度為conf，該可靠程度達(dá)到了測試用例約簡的最小置信度值，那么測試用例tb相對于測試用例集T′是冗余的測試用例，即tb為可約簡的測試用例。

由于每一個被約簡的測試用例tb都存在與其具有極大關(guān)聯(lián)度的測試用例集合T′，即tb相對于T′是冗余的測試用例，那么約簡后測試用例集合T′與原始測試用例集合T，執(zhí)行變異測試后具有相同的變異評分，即約簡后測試用例集與原始測試用例集擁有相同的變異評分。

RTM以測試用例能否檢測到指定變異體為依據(jù)，創(chuàng)建變異體二進(jìn)制事務(wù)集矩陣，采用改進(jìn)的關(guān)聯(lián)挖掘算法獲取測試用例間的關(guān)聯(lián)關(guān)系，進(jìn)而約簡測試用例，RTM僅掃描一次數(shù)據(jù)集，因此最壞情況下，RTM的時間復(fù)雜度為n·(n-1)，即測試用例約簡率不受初始測試用例集的影響。

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

為驗(yàn)證本文方法(RTM)的有效性，選擇經(jīng)典測試用例約簡方法，即貪心算法(G算法)和啟發(fā)式算法(HGS算法)進(jìn)行實(shí)驗(yàn)驗(yàn)證。G算法在循環(huán)迭代過程中每次選擇能夠覆蓋最多測試需求的測試用例，直到所有測試需求均被滿足，HGS算法首先根據(jù)被覆蓋到的測試用例數(shù)對測試需求進(jìn)行劃分，再使用貪心算法循環(huán)迭代選擇能夠滿足所有測試需求的測試用例集[18]。

3.1 實(shí)驗(yàn)設(shè)計及評估準(zhǔn)則

本文實(shí)驗(yàn)結(jié)果以測試用例約簡率、變異評分、測試覆蓋率和錯誤檢測率四個指標(biāo)進(jìn)行對比和分析。其中，錯誤檢測率表示約簡后測試用例集和原始測試用例集能夠檢測到錯誤數(shù)的比值。錯誤檢錯率越大，表示約簡后測試用例集相比原始測試用例集，對測試用例檢測率的影響越低，錯誤檢測能力越強(qiáng)[19]。

實(shí)驗(yàn)程序選擇Siemens程序集上(http://sir.unl.edu)上的6個基準(zhǔn)實(shí)驗(yàn)程序：Mid、Triangle、Cal、NextDate、Tcas與WordUtils程序，表1為6個程序的相關(guān)描述信息。

表1描述的待測程序信息包括有效代碼行數(shù)、根據(jù)程序特征選擇的變異因子、由變異因子產(chǎn)生的變異體數(shù)目，以及原始測試用例集的規(guī)模。本實(shí)驗(yàn)中選擇的變異因子的描述信息如表2所示。

表1 實(shí)驗(yàn)程序描述Tab. 1 Description of experimental program

表2 變異因子描述Tab. 2 Description of mutation factor

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

3.2.1 測試用例約簡率和錯誤檢錯率

分別在6個程序上使用RTM、G算法和HGS算法約簡測試用例，表3為分別使用3種算法約簡測試用例的約簡結(jié)果。由表3分析可知，當(dāng)測試用例規(guī)模比較小時，RTM的測試用例約簡率并不明顯，但當(dāng)測試用例規(guī)模增大時，RTM能夠使約簡后測試用例約簡率平均可達(dá)到37%，如程序NextDate，原始測試用例規(guī)模為100，RTM的測試用例約簡率可達(dá)到45%。另一方面，RTM能夠獲得更高的錯誤檢測率，從實(shí)驗(yàn)結(jié)果可看出，RTM相對于G算法和HGS算法，能夠?qū)υ紲y試用例集的錯誤檢測率產(chǎn)生更極小的影響，保證測試用例集的錯誤檢測能力。

表3 測試用例約簡率和錯誤檢測率Tab. 3 Test suite reduction rate and fault detection rate

3.2.2 測試充分性評估

實(shí)驗(yàn)通過變異評分和測試覆蓋率綜合評估約簡后測試用例集的測試充分性，圖2為使用三種算法約簡測試用例后的變異評分。由圖2分析可知，RTM能夠保證在約簡測試用例后變異評分不改變，而H算法和HGS算法在源程序與測試用例規(guī)模增大的時候，會極大程度地降低變異評分，影響原始測試用例集的測試充分性。

在相同測試充分性的前提下，單個測試用例的測試覆蓋率如表4所示。由表4可知，RTM相比G算法和HGS算法，能夠使約簡后的單個測試用例擁有更高的測試覆蓋率。如程序WordUtils，使用RTM約簡測試用例后，單個測試用例的測試覆蓋率相較于G算法提高了18%，相較于HGS算法提高了16%，約簡后單個測試用例的測試覆蓋率相比原測試用例提高了一倍。

圖2 約簡后變異評分Fig. 2 Mutation score after reduction表4 單個測試用例的測試覆蓋率 %

Tab. 4 Test coverage rate of a single test suite %

實(shí)驗(yàn)結(jié)果表明，RTM相較于傳統(tǒng)的G算法和HGS算法，能夠獲得更小的測試用例集，并使得約簡后測試用例集對錯誤檢測率的影響降到最低。RTM能夠在保持測試充分性的同時，有效提高單個測試用例的測試覆蓋率，提高測試效率，降低測試成本。

4 結(jié)語

本文針對回歸測試中測試用例約簡問題，考慮到測試用例間存在的關(guān)聯(lián)關(guān)系，結(jié)合變異分析和改進(jìn)的關(guān)聯(lián)挖掘算法，提出一種基于變異分析的測試用例約簡方法。通過測試用例間的關(guān)聯(lián)關(guān)系有效約簡測試用例，使約簡后的測試用例在不改變原始測試用例集測試充分性的前提下，大幅度提高單個測試用例的測試覆蓋率。

在本文研究基礎(chǔ)上，下一步的研究工作主要有兩個方面：一方面，將針對降低變異測試效率展開更深入的研究；另一方面，針對未被原始測試用例集檢測到的變異體，設(shè)計能夠殺死該變異體的測試用例，使得測試用例集具有更高的測試充分性。

References)

[1] 顧慶,唐寶,陳道蓄.一種面向測試需求部分覆蓋的測試用例集約簡技術(shù)[J].計算機(jī)學(xué)報,2011,34(5):879-888.(GU Q, TANG B, CHEN D X. A test suite reduction technique for partial coverage of test requirements [J]. Chinese Journal of Computers, 2011, 34(5): 879-888.)

[2] 章曉芳,徐寶文,聶長海,等.一種基于測試需求約簡的測試用例集優(yōu)化方法[J].軟件學(xué)報,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.)

[3] 郭曦,張煥國.基于謂詞抽象的測試用例約簡生成方法[J].通信學(xué)報,2012,33(3):35-43.(GUO X, ZHANG H G. Approach for reduced test suite generation based on predicate abstraction [J]. Journal on Communications, 2012, 33(3): 35-43.)

[4] 邢行,尚穎,趙瑞蓮,等.面向多目標(biāo)測試用例優(yōu)先排序的蟻群算法信息素更新策略[J].計算機(jī)應(yīng)用,2016,36(9):2497-2502.(XING X, SHANG Y, ZHAO R L, et al. Pheromone updating strategy of ant colony algorithm for multi-objective test case prioritization [J]. Journal of Computer Applications, 2016, 36(9):2497-2502.)

[5] 周沖波,樓俊鋼,程龍.基于矩陣行列變換的測試用例約簡算法[J].計算機(jī)應(yīng)用研究,2013,30(3):779-782.(ZHOU C B, LOU J G, CHENG L. Test suites reduction based on matrix transformation [J]. Application Research of Computers, 2013, 30(3): 779-782.)

[6] ZHANG C Q, GROCE A, ALIPOUR M A. Using test case reduction and prioritization to improve symbolic execution[C]// ISSTA 2014: Proceedings of the 2014 International Symposium on Software Testing and Analysis. New York：ACM, 2014: 160-170

[7] LIEMANDT J A, SUBRAMANIAM R, ABOEL-NIL S. Test case reduction for code regression testing: US, WO/2014/145604 [P]. 2014- 09- 18.

[8] GRAVES T L, HARROLD M J, KIM J M, et al. An empirical study of regression test selection techniques [J]. ACM Transactions on Software Engineering and Methodology, 2001, 10(2): 184-208.

[9] ASOUDEH N, LABICHE Y. A multi-objective genetic algorithm for gene-rating test suites from extended finite state machines [C]/ / Proceedings of the 2013 International Symposium on Search Based Software Engineering, LNCS 8084. Berlin: Springer, 2013: 288-293.

[10] 華麗,王成勇,谷瓊,等.基于遺傳蟻群算法的測試用例集約簡[J].工程數(shù)學(xué)學(xué)報,2012,29(4):486-492.(HUA L, WANG C Y, GU Q, et al. Test-suite reduction based on genetic algorithm and ant colony algorithm [J]. Chinese Journal of Engineering Mathematics, 2012, 29(4): 486-492.)

[11] 聶長海,徐寶文.一種最小測試用例集生成方法[J].計算機(jī)學(xué)報,2003,26(12):1690-1695.(NIE C H, XU B W. A minimal test suite generation method [J]. Chinese Journal of Computers, 2003, 26(12): 1690-1695.)

[12] 陳靜,楊美紅,王魯,等.基于關(guān)聯(lián)模式的回歸測試用例約簡模型[J].計算機(jī)工程,2011,37(2):63-65.(CHEN J, YANG M H, WANG L, et al. Regression test case reduction model based on association mode [J]. Computer Engineering, 2011, 37(2) : 63-65)

[13] 劉鋒,李朋,朱二周.基于向量相似度的測試用例集約簡方法[J].微電子學(xué)與計算機(jī),2017,34(3):35-39.(LIU F, LI P, ZHU E Z. Test case reduction method based on vector similarity algorithm [J]. Microelectronics & Computer, 2017, 34(3): 35-39.)

[14] 陳翔,顧慶.變異測試:原理、優(yōu)化和應(yīng)用[J].計算機(jī)科學(xué)與探索,2012,6(12):1057-1075.(CHEN X, GU Q. Mutation testing: principal, optimization and application [J]. Journal of Frontiers of Computer Science and Technology, 2012, 6(12): 1057-1075.)

[15] DAOUDAGH S, LONETTI F, MARCHETTI E. Assessment of access control systems using mutation testing [C]// TELERISE 2015: Proceedings of the 2015 IEEE/ACM 1st International Workshop on TEchnical and LEgal aspects of data pRIvacy and SEcurity. Piscataway, NJ: IEEE, 2015: 8-13..

[16] PAPADAKIS M, JIA Y, HARMAN M, et al. Trivial compiler equivalence: a large scale empirical study of a simple, fast and effective equivalent mutant detection technique[C]// Proceedings of the 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering. Piscataway, NJ: IEEE, 2015: 936-946.

[17] KHAN R, AMJAD M. Optimize the software testing efficiency using genetic algorithm and mutation analysis [C]// Proceedings of the 2016 3rd International Conference on Computing for Sustainable Global Development. Piscataway, NJ: IEEE, 2016: 1174-1176.

[18] 游亮,盧炎生.測試用例集啟發(fā)式約簡算法分析與評價[J].計算機(jī)科學(xué),2011,38(12):147-150.(YOU L, LU Y S. Analysis and evaluation of heuristic algorithms for test suite reduction [J]. Computer Science, 2011, 38(12): 147-150.)

[19] 張妍,傅秀芬.基于多優(yōu)化目標(biāo)的軟件測試用例約簡方法研究[J].計算機(jī)應(yīng)用研究,2016,33(4):1111-1113.(ZHANG Y, FU X F. Software test case reduction method based on multi-objective optimization [J]. Application Research of Computers, 2016, 33(4): 1111-1113.)

This work is partially supported by the Industrial Science and Technology Research Project of Shaanxi Province (2017GY- 092), the Natural Science Foundation of Shaanxi Education Department (15JK1678).

WANGShuyan, born in 1964, Ph. D., professor. Her research interests include software testing, data mining, intelligent information processing.

CHENPengyuan, born in 1991, M. S. candidate. Her research interests include software testing, data mining.

SUNJiaze, born in 1980, Ph. D. , associate professor. His research interests include software testing, data mining, intelligent information processing.

Reductionmethodoftestsuitesbasedonmutationanalysis

WANG Shuyan*, CHEN Pengyuan, SUN Jiaze

(SchoolofComputerScienceandTechnology,Xi’anUniversityofPostsandTelecommunications,Xi’anShaanxi710061,China)

The scale of test suites is constantly expanding and the cost of testing is increasing due to the change of test requirements in the process of regression testing. In order to solve the problems, a Reduction method of Test suites based on the analysis of Mutation (RTM) was proposed. Firstly, the test suites were classified and the transaction set matrix of mutants was created in binary numerical form according to whether the designated mutants could be detected or not by test suites. Then, the correlation relation between test suites was obtained by using the improved association mining algorithm. Finally, the test suites were effectively reduced according to these relations. The simulation experimental results of the six classical programs show that, the test suite reduction rate of the proposed RTM can reach 37%. Compared with the traditional greedy algorithm and heuristic algorithm, the proposed RTM improves the test suite reduction rate by 6%, and can guarantee the test coverage rate at the same time, even the test coverage rate of a single test suite increases by 11% on average. The proposed method can meet more test requirements by using fewer test suites, effectively improving test efficiency and reducing test cost.

regression testing; test suite reduction; analysis of mutation; mutant; association mining

2017- 06- 12;

2017- 08- 04。

陜西省工業(yè)科技攻關(guān)項(xiàng)目(2017GY- 092); 陜西省教育廳自然科學(xué)基金項(xiàng)目(15JK1678)。

王曙燕(1964—)，女，陜西西安人，教授，博士，主要研究方向：軟件測試、數(shù)據(jù)挖掘、智能信息處理； 陳朋媛(1991—)，女，陜西西安人，碩士研究生，主要研究方向：軟件測試、數(shù)據(jù)挖掘； 孫家澤(1980—)，男，陜西西安人，副教授，博士，主要研究方向：軟件測試、數(shù)據(jù)挖掘、智能信息處理。

1001- 9081(2017)12- 3592- 05

10.11772/j.issn.1001- 9081.2017.12.3592

(*通信作者電子郵箱wsylxj@126.com)

TP311.5

A