王曙燕 袁佳娟 孫家澤

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

關(guān)鍵詞：回歸測試;弱變異準(zhǔn)則;變異分支;測試用例約簡;人工魚群算法

中圖分類號： TP311. 5

文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

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

1 基本概念和術(shù)語

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

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

4 結(jié)語

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

參考文獻(xiàn)：

[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] 鄭煒，楊喜兵，胡圣佑，等.基于變異分析和覆蓋準(zhǔn)則的回歸測試用例集縮減[J].西北工業(yè)大學(xué)學(xué)報(bào)，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] 華麗，李曉月，王成勇，等.能提高錯(cuò)誤檢測能力的回歸測試用例集約簡[J].湖南科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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].計(jì)算機(jī)應(yīng)用，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].計(jì)算機(jī)學(xué)報(bào)，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.只查到優(yōu)先發(fā)表的

[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] 章曉芳，徐寶文，聶長海，等.一種基于測試需求約簡的測試用例集優(yōu)化方法[J].軟件學(xué)報(bào)，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] 顧慶，唐寶，陳道蓄.一種面向測試需求部分覆蓋的測試用例集約簡技術(shù)[J].計(jì)算機(jī)學(xué)報(bào)，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] 張功杰，鞏敦衛(wèi)，姚香娟.基于統(tǒng)計(jì)占優(yōu)分析的變異測試[J].軟件學(xué)報(bào)，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] 李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實(shí)踐，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] 張功杰，鞏敦衛(wèi)，姚香娟.基于變異分析和集合進(jìn)化的測試用例生成方法[J].計(jì)算機(jī)學(xué)報(bào)，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.）.