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

王曙燕，陳朋媛，孫家澤

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

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

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

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

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

回歸測試；測試用例約簡；變異分析；變異體；關聯挖掘

0 引言

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

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

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

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

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

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

(1)

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

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

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

定義4 變異體事務集。所有變異體事務項構成變異體事務集，n個變異體事務項構成的變異體事務集表示為MLists={MList1,MList2,…,MListn}。

定義5 變異體事務集矩陣。變異體集合與測試用例集合存在一一對應的關系，所有關系集合組成一個n×m的二進制矩陣A:

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

測試用例約簡旨在用最小的測試用例集盡可能地滿足更多的測試需求，本文將變異體集合作為測試需求，變異體集合P與原始測試用例集T存在映射關系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í)行測試用例，以測試用例能否檢測到指定變異體為依據，對測試用例進行劃分并獲取測試用例頻繁1項集，根據頻繁1項集創(chuàng)建變異體事務集矩陣A，矩陣元素取值0或1，1表示對應測試用例不能夠檢測到指定變異體，否則能夠檢測到。設計實現基于二進制矩陣的關聯挖掘算法，獲取測試用例間的關聯關系，根據所獲取的測試用例間的關聯關系有效約簡測試用例。

2.1 初始化變異體事務集矩陣

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

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

(2)

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

2.2 約簡變異體事務集矩陣

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

約簡變異體事務集矩陣，首先需要按照事務項中所包含的測試用例數，對事務項進行排序，即對矩陣A按行降序排序，再對排序后的矩陣進行約簡。

算法1 約簡變異體事務集矩陣。

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

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

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

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

步驟5 當前預處理事務項MListi下移，即矩陣預處理行向量下移，重復步驟2。

步驟6 刪除矩陣當前行及其后所有元素。

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

2.3 獲取變異體事務集頻繁模式

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

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

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

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

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

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

2.4 約簡測試用例

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

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

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

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

3 實驗結果與分析

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

3.1 實驗設計及評估準則

本文實驗結果以測試用例約簡率、變異評分、測試覆蓋率和錯誤檢測率四個指標進行對比和分析。其中，錯誤檢測率表示約簡后測試用例集和原始測試用例集能夠檢測到錯誤數的比值。錯誤檢錯率越大，表示約簡后測試用例集相比原始測試用例集，對測試用例檢測率的影響越低，錯誤檢測能力越強[19]。

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

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

表1 實驗程序描述Tab. 1 Description of experimental program

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

3.2 實驗結果分析

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

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

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

3.2.2 測試充分性評估

實驗通過變異評分和測試覆蓋率綜合評估約簡后測試用例集的測試充分性，圖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 %

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

4 結語

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

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

References)

[1] 顧慶,唐寶,陳道蓄.一種面向測試需求部分覆蓋的測試用例集約簡技術[J].計算機學報,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].軟件學報,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].通信學報,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] 邢行,尚穎,趙瑞蓮,等.面向多目標測試用例優(yōu)先排序的蟻群算法信息素更新策略[J].計算機應用,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].計算機應用研究,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].工程數學學報,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].計算機學報,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] 陳靜,楊美紅,王魯,等.基于關聯模式的回歸測試用例約簡模型[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].微電子學與計算機,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)化和應用[J].計算機科學與探索,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].計算機科學,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)化目標的軟件測試用例約簡方法研究[J].計算機應用研究,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è)科技攻關項目(2017GY- 092); 陜西省教育廳自然科學基金項目(15JK1678)。

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

1001- 9081(2017)12- 3592- 05

10.11772/j.issn.1001- 9081.2017.12.3592

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

TP311.5

A