基于弱變異準(zhǔn)則的測(cè)試用例約簡(jiǎn)方法

王曙燕 袁佳娟 孫家澤

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

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

中圖分類號(hào)： 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 引言

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

本文針對(duì)回歸測(cè)試中測(cè)試用例約簡(jiǎn)問(wèn)題，提出一種基于弱變異準(zhǔn)則的測(cè)試用例約簡(jiǎn)方法。基于弱變異準(zhǔn)則，在不改變或稍微改變變異評(píng)分的條件下，本文算法可有效約簡(jiǎn)測(cè)試用例。在此基礎(chǔ)上，接下來(lái)準(zhǔn)備從以下兩方面進(jìn)行研究：一方面，對(duì)類級(jí)別變異算子進(jìn)行更深一步研究; 另一方面，弱變異分支轉(zhuǎn)化導(dǎo)致極小部分等價(jià)變異體未被識(shí)別，影響對(duì)應(yīng)變異分支覆蓋，從而改變了某些測(cè)試用例約簡(jiǎn)，因此接下來(lái)將對(duì)此類未識(shí)別變異體作進(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)則的回歸測(cè)試用例集縮減[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ò)誤檢測(cè)能力的回歸測(cè)試用例集約簡(jiǎn)[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] 王曙燕，陳朋媛，孫家澤.基于變異分析的測(cè)試用例約簡(jiǎn)方法[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] 聶長(zhǎng)海，徐寶文.一種最小測(cè)試用例集生成方法[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] 章曉芳，徐寶文，聶長(zhǎng)海，等.一種基于測(cè)試需求約簡(jiǎn)的測(cè)試用例集優(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] 顧慶，唐寶，陳道蓄.一種面向測(cè)試需求部分覆蓋的測(cè)試用例集約簡(jiǎn)技術(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)分析的變異測(cè)試[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)化的測(cè)試用例生成方法[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.）.