基于弱變異準則的測試用例約簡方法

王曙燕 袁佳娟 孫家澤

摘 要：針對為數較多的測試用例增加了回歸測試成本的問題，提出一種基于弱變異準則的測試用例約簡方法。首先，基于弱變異準則獲得測試用例和變異分支關系矩陣;然后，重復約簡4種無效測試需求和子集測試用例;最后，結合人工魚群算法選擇當前最優測試用例，并且交替執行簡化和測試用例選擇操作直至覆蓋所有測試需求。該方法針對6個經典程序與貪心算法和HGS算法相比，基于弱變異準則并且不改變或稍微改變變異評分的條件下，約簡率分別提高了73.4%和8.2%，且耗時分別降低了25.3%和56.1%。實驗結果表明，所提方法在回歸測試中可有效約簡測試用例，降低測試代價。

關鍵詞：回歸測試;弱變異準則;變異分支;測試用例約簡;人工魚群算法

中圖分類號： TP311. 5

文獻標志碼：A

Abstract： In view of the problem that the test cost is increased by a large number of test suites in regression testing， a test suite reduction method based on weak mutation criterion was proposed. Firstly， the relation matrix between test suites and mutation branches was obtained based on weak mutation criterion. Then， four invalid test requirements and subset test suites were reduced repeatedly. Finally， the current optimal test suite was selected by using artificial fish swarm algorithm， and the simplification and test suite selection operations were performed alternately until all the test requirements were covered. Compared with Greedy algorithm and HGS （Harrold-Gupta-Soff） algorithm on six classical programs， when using weak mutation criterion with no changing or slightly changing mutation score， the reduction rate was improved by 73.4% and 8.2% respectively， and the time consumption was decreased by 25.3% and 56.1% respectively. The experimental results show that the proposed method can effectively reduce the test suites and save the test cost in regression testing.

Key words： regression testing; weak mutation criterion; mutation branch; test suite reduction; artificial fish swarm algorithm

0 引言

軟件測試是評估能否達到預期要求、檢驗軟件質量的過程。回歸測試過程中數量較多的測試用例增加了測試成本[1]，因此從原始測試用例集中選擇規模較小的測試用例，從而有效降低測試費用是軟件測試的主要目標之一。約簡測試用例可描述為選擇盡可能小的子集測試用例，使之盡可能滿足與原測試用例集相同的測試需求。選擇覆蓋所有測試需求的子集測試用例是一個NP（Non-deterministic Polynomial）問題[2-3]。

目前主要的測試用例約簡算法有貪心（Greedy， G）算法、啟發式算法、啟發式貪婪算法和整數規劃算法等[4-5]。G算法總是選擇當前滿足測試需求最多的測試用例，然后移除已被滿足的測試需求，再繼續選擇直到測試需求集為空[6]。Harrold等[7]首先劃分測試需求，以滿足某測試需求的測試用例個數作為重要性判斷依據，提出了根據重要性選擇優化代表集的HGS（Harrold-Gupta-Soff）算法。在此基礎上，Chen等[8]提出貪婪進化（Greedy Evolution， GE）算法和GRE（GREedy heuristic G）算法。GE算法首先選出必不可少的測試用例后結合G算法;GRE算法首先基于必不可少策略、1-1冗余策略重復直至不能再應用兩種策略，然后結合貪心策略約簡測試用例。Lee等[9]應用5種約簡規則化簡矩陣規模，并將測試用例求解問題轉化為整數線性規劃問題得到最優解。G算法和HGS算法的求解結果精度不高，GE和GRE算法時間復雜度較高，且均不能保證約簡后的測試用例集是優化代表集。Marchetto等[10]以源代碼覆蓋、應用需求覆蓋和執行測試用例成本為為目標，提出多目標測試用例約簡（Multi-Objective test suites REduction， MORE+）方法，采用LSI（Latent Semantic Indexing）恢復相似性鏈接，計算軟件度量和可維護性索引自動為代碼和需求加權，采用測試用例集約簡公式，依賴NSGA-II（Non-dominated Sorting Genetic Algorithm-II）約簡測試用例。Vahabzadeh等[11]提出了一種細粒度測試用例最小化方法，在每個語句級別捕獲測試狀態，得到有相同PMC（Production Method Calls）的等價測試語句和相容狀態建立模型，根據模型集合測試用例重組和最小化組合算法識別和移除冗余的測試語句。

聶長海等[6]充分考慮測試需求之間的相互關系，對所有可用測試用例集進行劃分得到子集族，每個子集由滿足某一個或多個測試需求的測試用例組成，利用啟發式算法、貪心算法或整數規劃方法簡化測試用例集，從而生成滿足所有測試需求的最小測試用例集。該方法雖然考慮到測試需求之間的關系，但卻沒有分析測試用例與測試需求的覆蓋關系，簡化無效的測試需求。章曉芳等[12]進一步研究如何充分利用測試需求間的相互關系約簡測試需求，去除包含、相等和部分重合三種關系的測試需求，將精簡的測試需求作為測試用例生成和約簡的基礎;但通過對所有測試需求的兩兩組合，判斷相互關系，精簡測試需求時間復雜度較大，且沒有考慮到通過必不可少的測試用例進而精簡測試需求。顧慶等[13]提出啟發式貪婪搜索算法（Heuristic search Algorithm with Three Strategies， HATS），應用必選策略、替代策略和貪婪策略選擇最合適的測試用例。Usaola等[14]首次將變異體覆蓋作為測試需求，通過測試用例與變異體的關系，選擇覆蓋當前變異體最多的測試用例，移除已滿足變異體，繼續選擇直至所有變異體被覆蓋;但其基于強變異準則，隨著程序規模的增加，大量變異體的產生使得在變異體和測試用例關系獲取的代價增加，且得到約簡后的測試用例集不能保證全局最優。王曙燕等[5]通過執行變異體與程序變異體集矩陣，然后結合關聯規則約簡測試用例;但隨著程序規模的增加，該方法將產生數量較多的變異體，執行變異體與原程序以結果區分變異體是否被殺死，其時間消耗是不可忽略的過程。

針對上述結合變異測試約簡測試用例，未考慮測試用例與測試需求關系獲取的代價以及約簡測試需求的計算方式復雜問題。基于Papadakis等[15]的弱變異轉化方法，一次執行構建變異分支的新程序獲取關系矩陣，此外對測試需求進行二進制編碼，通過編碼值約簡4種測試需求可降低計算消耗。本文基于弱變異準則的測試用例約簡方法，首先通過弱變異轉化方法獲得關系矩陣，然后重復約簡測試需求和子集測試用例并結合人工魚群算法，交替執行簡化和測試用例選擇操作以加快降低求解復雜度，直至滿足所有測試需求。實驗表明在弱變異準則下，該方法在不改變或稍微改變測試用例充分性情況下可有效約簡測試用例。

1 基本概念和術語

變異測試是一種基于缺陷的軟件測試技術[16]。變異測試通過對原程序作合乎語法的微小改動模擬軟件中的實際缺陷，每個被注入缺陷的副本稱為變異體，若相同輸入情況下變異體和原程序輸出不同，則變異體被殺死，否則變異體存活。在傳統強變異測試中，原程序與變異體的輸出結果作為判斷變異體是否被殺死的依據，即滿足可達性、必要性和完全性則判定變異體被殺死[17]。可達性指測試用例可到達變異點;必要性指在變異點之后程序狀態發生改變;完全性指程序狀態改變影響程序出口，改變程序運行結果。

弱變異準則只需要滿足可達性和必要性，即測試用例執行變異語句后，程序的狀態發生改變可判定變異體被殺死。通過學者研究表明，弱變異測試可有效替代強變異測試[18]。若被測程序P，m個原始測試用例組成集合T={t1，t2，…，tm}，n個變異體組成集合M={m1，m2，…，mn}。

4 結語

本文針對回歸測試中測試用例約簡問題，提出一種基于弱變異準則的測試用例約簡方法。基于弱變異準則，在不改變或稍微改變變異評分的條件下，本文算法可有效約簡測試用例。在此基礎上，接下來準備從以下兩方面進行研究：一方面，對類級別變異算子進行更深一步研究; 另一方面，弱變異分支轉化導致極小部分等價變異體未被識別，影響對應變異分支覆蓋，從而改變了某些測試用例約簡，因此接下來將對此類未識別變異體作進一步研究。

參考文獻：

[1] NARDO D D， ALSHAHWAN N， BRIAND L， et al. Coverage-based regression test case selection， minimization and prioritization： a case study on an industrial system [J]. Software Testing， Verification and Reliability， 2015， 25（4）： 371-396.

[2] JONES J A， HARROLD M J. Test-suite reduction and prioritization for modified condition/decision coverage [J]. IEEE Transactions on Software Engineering， 2003， 29（3）： 195-209.

[3] 鄭煒，楊喜兵，胡圣佑，等.基于變異分析和覆蓋準則的回歸測試用例集縮減[J].西北工業大學學報，2017，35（3）：494-499. （ZHENG W， YANG X B， HU S Y， et al. Regression test case reduction based on mutation analysis and coverage criterion[J]. Journal of Northwestern Polytechnical University，2017，35（3）： 494-499.）

[4] 華麗，李曉月，王成勇，等.能提高錯誤檢測能力的回歸測試用例集約簡[J].湖南科技大學學報（自然科學版），2015，30（2）：99-103. （HUA L， LI X Y， WANG C Y， et al. Regression test suite reduction on improving fault detection capability[J]. Journal of Hunan University of Science & Technology （Natural Science Edition）， 2015， 30（2）： 99-103.）

[5] 王曙燕，陳朋媛，孫家澤.基于變異分析的測試用例約簡方法[J].計算機應用，2017，37（12）：3592-3596. （WANG S Y， CHEN P Y， SUN J Z. Reduction method of test suites based on mutation analysis[J]. Journal of Computer Applications， 2017， 37（12）： 3592-3596.）

[6] 聶長海，徐寶文.一種最小測試用例集生成方法[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.）

[7] HARROLD M J， GUPTA R， SOFFA M L. A methodology for controlling the size of a test suite [J]. ACM Transactions on Software Engineering & Methodology， 1993， 2（3）： 270-285.

[8] CHEN T Y， LAU M F. A new heuristic for test suite reduction [J]. Information and Software Technology， 1998， 40（5/6）： 347-354.

[9] LEE J G， CHUNG C G. An optimal representative set selection method [J]. Information and Software Technology， 2000， 42（1）： 17-25.

[10] MARCHETTO A， SCANNIELLO G， SUSI A. Combining code and requirements coverage with execution cost for test suite reduction [J/OL]. IEEE Transactions on Software Engineering， 2017 [2018-03-06]. https：//www.onacademic.com/detail/journal_1000040248934010_36b2.html.只查到優先發表的

[11] VAHABZADEH A， STOCCO A， MESBAH A. Fine-grained test minimization [C]// ICSE 2018： Proceedings of the 40th International Conference on Software Engineering. New York： ACM， 2018： 210-221.

[12] 章曉芳，徐寶文，聶長海，等.一種基于測試需求約簡的測試用例集優化方法[J].軟件學報，2007，18（4）：821-831. （ZHNAG 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.）

[13] 顧慶，唐寶，陳道蓄.一種面向測試需求部分覆蓋的測試用例集約簡技術[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.）

[14] USAOLA M P， MATEO P R， LAMANCHA B P. Reduction of test suites using mutation [C]// FASE 2012： Proceedings of the 2012 International Conference on Fundamental Approaches to Software Engineering， LNCS 7212. Berlin： Springer， 2012： 425-438.

[15] PAPADAKIS M， MALEVRIS N. Automatically performing weak mutation with the aid of symbolic execution， concolic testing and search-based testing[J]. Software Quality Journal， 2011， 19（4）： 691-723.

[16] MRESA E S， BOTTACI L. Efficiency of mutation operators and selective mutation strategies： an empirical study [J]. Software Testing Verification & Reliability， 2015， 9（4）： 205-232.

[17] DEMILLI R A， OFFUTT A J. Constraint-based automatic test data generation [J]. IEEE Transactions on Software Engineering， 1991， 17（9）： 900-910.

[18] 張功杰，鞏敦衛，姚香娟.基于統計占優分析的變異測試[J].軟件學報，2015，26（10）：2504-2520. （ZHANG G J， GONG D W， YAO X J. Mutation testing based on statistical dominance analysis[J]. Journal of Software， 2015， 26（10）： 2504-2520.）

[19] IIDA C， TAKADA S. Reducing mutants with mutant killable precondition [C]// ICSTW 2017： Proceedings of the 2017 IEEE International Conference on Software Testing， Verification and Validation Workshops. Piscataway， NJ： IEEE， 2017： 128-133.

[20] 李曉磊，邵之江，錢積新.一種基于動物自治體的尋優模式：魚群算法[J].系統工程理論與實踐，2002，22（11）：32-38. （LI X L， SHAO Z J， QIAN J X. An optimizing method based on autonomous animats： fish-swarm algorithm [J]. Systems Engineering — Theory & Practice， 2002， 22（11）： 32-38.）

[21] 張功杰，鞏敦衛，姚香娟.基于變異分析和集合進化的測試用例生成方法[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.）.