帶權(quán)值參數(shù)的兩兩組合測(cè)試用例集生成算法

李龍澍，王雅婷

(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230601)

1 概述

在整個(gè)軟件開發(fā)生命周期中，軟件測(cè)試是非常重要的一個(gè)環(huán)節(jié)，是保證軟件質(zhì)量、提高軟件可靠性的重要手段。研究表明，有20% ～40%左右的軟件故障是由某個(gè)系統(tǒng)參數(shù)引發(fā)，20% ～40%左右的故障由某2個(gè)參數(shù)的相互作用引發(fā)，而大約70%的軟件故障是由1個(gè)或2個(gè)參數(shù)的作用引起的［1］。所以，對(duì)各種待測(cè)軟件系統(tǒng)而言，兩兩組合測(cè)試是一種科學(xué)、實(shí)用而有效的測(cè)試方法［2］。

目前國內(nèi)外在兩兩組合覆蓋的測(cè)試數(shù)據(jù)生成方面已有廣泛研究，主要有以下算法:正交拉丁方算法［3］，Williams 算法［4］，Kobayashi算法［5］，AETG 算法［6-7］，IPO 算法［8-11］，PSST 算法［12］等。但這些算法都是致力于如何減小測(cè)試集的規(guī)模，并未考慮到參數(shù)帶權(quán)值的實(shí)際要求。參數(shù)被賦予權(quán)值基本有2種情況:(1)因參數(shù)重要程度不同而賦予相應(yīng)權(quán)值;(2)因生成的測(cè)試集過大而無法完全執(zhí)行測(cè)試用例時(shí)，賦予參數(shù)權(quán)值以使生成的測(cè)試用例帶有權(quán)值和，然后根據(jù)權(quán)值和可以優(yōu)先執(zhí)行比較重要的測(cè)試用例。前者是對(duì)待測(cè)系統(tǒng)硬性要求的處理，后者則為測(cè)試人員如何選擇測(cè)試用例提供了重要依據(jù)。因此，本文在研究逐參數(shù)(In-Parameter-Order，IPO)擴(kuò)展策略的基礎(chǔ)上，考慮待測(cè)系統(tǒng)參數(shù)被賦予權(quán)值的情況，提出一種參數(shù)帶權(quán)值的兩兩組合測(cè)試用例集生成方法。

2 基本概念及相關(guān)定義

假設(shè)待測(cè)系統(tǒng)SUT(Software Under Testing)的n個(gè)輸入?yún)?shù)集合 X={x1，x2，…，xn}，其中每個(gè)輸入?yún)?shù)對(duì)應(yīng)的取值域?yàn)镈j(j∈［1，n］)，即每個(gè)輸入?yún)?shù)有|Dj|個(gè)互異的取值。

定義1(測(cè)試集) 設(shè)集合 T={t1，t2，…，ti}，如果對(duì) ti∈T，有 ti={ti1，ti2，…，tin}，且 tij∈Dj(j∈［1，n］)，則稱集合T為待測(cè)系統(tǒng)SUT的一個(gè)測(cè)試集，ti為待測(cè)系統(tǒng)SUT的一條測(cè)試用例。

定義2(兩兩組合測(cè)試集) 設(shè) T為待測(cè)系統(tǒng)SUT的一個(gè)測(cè)試集，如果對(duì)X中不同參數(shù)之間的任一兩兩取值組合(y，z)，都至少存在一個(gè)ti∈T，滿足y∈ti且z∈ti，則稱T為待測(cè)系統(tǒng)SUT的一個(gè)兩兩組合測(cè)試集。

定義3(參數(shù)需求度) 設(shè) ti={ti1，ti2，…，tij}，其中tij∈Dj(j∈［1，n))，為已有測(cè)試集中的一條測(cè)試用例，x1，x2，…，xj為已擴(kuò)展參數(shù)，將其作為待擴(kuò)展參數(shù)xj+1進(jìn)行組合時(shí)的可選參數(shù)，定義每個(gè)已擴(kuò)展參數(shù)相對(duì)于待擴(kuò)展參數(shù)的參數(shù)需求度為:

當(dāng)待擴(kuò)展參數(shù)的值 Dj+1，k’(參數(shù)值集 Dj+1中的第k’個(gè)取值)與已擴(kuò)展參數(shù)的值Dm，k(參數(shù)值集Dm中的第 k個(gè)取值)的組合未覆蓋時(shí)，Coverm，k取1，已覆蓋則取 0;Weightm，k為該組合的權(quán)重值;Sm，k等于已有測(cè)試集中Dm，k的總個(gè)數(shù)。

3 IPO算法影響因子分析及改進(jìn)

IPO算法是一種逐參數(shù)擴(kuò)展進(jìn)而生成兩兩組合覆蓋測(cè)試數(shù)據(jù)的方法。其核心步驟為水平擴(kuò)展和垂直擴(kuò)展兩部分，但在擴(kuò)展次序和參數(shù)取值上，該算法并未考慮到有關(guān)影響因子對(duì)算法性能的影響。所以，本文從擴(kuò)展次序和參數(shù)取值上出發(fā)，分析對(duì)算法性能可能產(chǎn)生影響的有關(guān)因子，并分別對(duì)影響因子做出合理的改進(jìn)。

3．1 待擴(kuò)展參數(shù)的擴(kuò)展次序

IPO算法中第一個(gè)擴(kuò)展次序問題，即待擴(kuò)展參數(shù)的擴(kuò)展次序。該算法在選擇一個(gè)未擴(kuò)展參數(shù)作為擴(kuò)展對(duì)象時(shí)，采用了隨機(jī)次序進(jìn)行擴(kuò)展，并未考慮參數(shù)次序不同而可能產(chǎn)生的不同影響。本文考慮在根據(jù)某些因素對(duì)待擴(kuò)展參數(shù)進(jìn)行排序后，再按照此順序逐一擴(kuò)展參數(shù)。

定義4(參數(shù)值的權(quán)值) 為每個(gè)參數(shù)取值Di，k(參數(shù)值集Di中的第k個(gè)取值)賦予一個(gè)數(shù)值Wi，k(－1．0≤Wi，k≤1．0)，其中，－1．0 表示優(yōu)先級(jí)最低;1．0表示優(yōu)先級(jí)最高，這個(gè)Wi，k就稱為該參數(shù)值的權(quán)值。

為每個(gè)參數(shù)取值賦予一個(gè)權(quán)值 Wi，k后，對(duì)可選參數(shù)進(jìn)行排序的步驟如下:

(1)計(jì)算參數(shù)值兩兩組合的組合權(quán)重值

當(dāng)參數(shù) xi取值為 Di，k，參數(shù) xj取值為 Dj，k’，則兩兩組合(Di，k，Dj，k’)的組合權(quán)重值為 Wi，k× Wj，k’。參數(shù)x1取1，參數(shù)x2取5，則兩兩組合(1，5)的組合權(quán)重值為 W1，2× W2，2=0．2 ×0．2=0．04。

(2)計(jì)算兩參數(shù)間權(quán)值和

兩參數(shù)間權(quán)值和為該兩參數(shù)所有取值兩兩組合的組合權(quán)重值之和，計(jì)算公式為:

如參數(shù)(x1，x3)兩參數(shù)間權(quán)值和為Wj，k'=0．4 × 0．2+0．4 × 0．5+0．2 × 0．2+0．2 ×0．5+0．3 × 0．2+0．3 × 0．5+0．1 × 0．2+0．1 ×0．5=0．7。同理，得(x1，x2)，(x2，x3)兩參數(shù)間權(quán)值和分別為0．9，0．63。參數(shù)和參數(shù)取值及參數(shù)值權(quán)值的輸入如表1所示。其中，括號(hào)中的數(shù)值為該參數(shù)值的權(quán)值。

表1 參數(shù)和參數(shù)取值及參數(shù)值權(quán)值的輸入

(3)計(jì)算各參數(shù)的權(quán)值總和

每個(gè)參數(shù)的權(quán)值總和等于該參數(shù)與其他參數(shù)的兩參數(shù)間權(quán)值和的和。例如，上述例子各參數(shù)的權(quán)值總和如表2所示。

表2 各參數(shù)的權(quán)值總和

最后，根據(jù)各參數(shù)的權(quán)值總和的大小按降序進(jìn)行排序，得到待擴(kuò)展參數(shù)的擴(kuò)展次序。例如，上述例子的擴(kuò)展次序?yàn)?x1，x2，x3。這種排序過程適用于參數(shù)值帶權(quán)值的情況，若參數(shù)值未被賦予權(quán)值，則可直接根據(jù)參數(shù)取值個(gè)數(shù)|Dj|按降序?qū)Υ龜U(kuò)展參數(shù)進(jìn)行排序。

3．2 已有測(cè)試集的擴(kuò)展次序

IPO算法中的第2個(gè)擴(kuò)展次序問題是在選定待擴(kuò)展參數(shù)后，需要對(duì)已有測(cè)試集中的測(cè)試用例進(jìn)行水平擴(kuò)展，即已有測(cè)試集的擴(kuò)展次序。IPO算法對(duì)該擴(kuò)展次序并未做任何處理，只是按照原本的已有測(cè)試集次序進(jìn)行擴(kuò)展［13］。所以，本文在考慮不同的擴(kuò)展次序可能生成不同的測(cè)試集結(jié)果的基礎(chǔ)上，根據(jù)有關(guān)影響因子對(duì)已有測(cè)試集中的測(cè)試用例進(jìn)行排序，過程如下:首先根據(jù)定義3中參數(shù)需求度的概念，計(jì)算已有測(cè)試用例的需求度R:

當(dāng)參數(shù)值未被賦予權(quán)值時(shí)，則Weightm，k=1，可以進(jìn)一步簡(jiǎn)化公式。然后，根據(jù)已有測(cè)試用例的需求度R按從大到小降序的順序進(jìn)行排序，得到已有測(cè)試集的擴(kuò)展次序。

3．3 待擴(kuò)展參數(shù)的取值選擇

IPO算法中參數(shù)取值問題，是指在進(jìn)行水平擴(kuò)展時(shí)，為待擴(kuò)展參數(shù)選取一個(gè)參數(shù)值，即待擴(kuò)展參數(shù)的取值選擇。該算法只是將待擴(kuò)展參數(shù) xj+1的|Dj+1|個(gè)可選值依次擴(kuò)展到已有測(cè)試集中，若此時(shí)仍有可選值未被擴(kuò)展，則未擴(kuò)展完的可選值直接進(jìn)入垂直擴(kuò)展步驟;反之，則繼續(xù)選擇覆蓋率較大的可選值進(jìn)行賦值，直到完成水平擴(kuò)展［13］。在此參數(shù)取值問題上，本文同樣根據(jù)某些因素進(jìn)行選擇，具體過程如下:

(1)計(jì)算參數(shù)值的權(quán)值貢獻(xiàn)

依次選取待擴(kuò)展參數(shù)的參數(shù)值，然后計(jì)算所選取參數(shù)值對(duì)應(yīng)的權(quán)值貢獻(xiàn)。計(jì)算公式為:

其中，Coverm，k和 Weightm，k的約束如同定義 3 中一樣。

在這個(gè)計(jì)算過程中，有一種特殊情況，就是擴(kuò)展的兩兩組合包含了前面測(cè)試用例所覆蓋過的兩兩組合，那么此兩兩組合所對(duì)應(yīng)的Coverm，k=0，即此兩兩組合所對(duì)應(yīng)的參數(shù)值兩兩組合的組合權(quán)重值不計(jì)入該參數(shù)值的權(quán)值貢獻(xiàn)。

(2)為待擴(kuò)展參數(shù)選取參數(shù)值

比較每個(gè)參數(shù)值所對(duì)應(yīng)的權(quán)值貢獻(xiàn)，選取使權(quán)值貢獻(xiàn)達(dá)到最大的那個(gè)參數(shù)值作為此測(cè)試用例待擴(kuò)

當(dāng)參數(shù)值未被賦予權(quán)值時(shí)，上述兩步驟中的Weightm，k=1。

4 算法描述

IPO_PW(In-Parameter-Order based Parameter Weight)算法主要是根據(jù)參數(shù)的權(quán)值對(duì)IPO中的擴(kuò)展次序和參數(shù)取值進(jìn)行有關(guān)改進(jìn)。并且，在擴(kuò)展完所有參數(shù)后，對(duì)得到的測(cè)試集用約簡(jiǎn)算法進(jìn)一步處理，以獲得更加簡(jiǎn)化的測(cè)試集。這種方法不僅生成的測(cè)試用例少，而且更適應(yīng)現(xiàn)實(shí)場(chǎng)景對(duì)組合測(cè)試的要求。IPO_PW算法的基本步驟如下:

(1)確定待擴(kuò)展參數(shù)的擴(kuò)展次序:按照3．1節(jié)中待擴(kuò)展參數(shù)的擴(kuò)展次序的改進(jìn)方法對(duì)參數(shù)進(jìn)行排序。

(2)初始化，從已排序參數(shù)列中選取前2個(gè)參數(shù)，將這2個(gè)參數(shù)的所有兩兩組合加入測(cè)試集。

(3)重復(fù)步驟(3)～步驟(6)，直到擴(kuò)展完所有參數(shù)。

(4)選取下一待擴(kuò)展參數(shù)，為每個(gè)測(cè)試用例計(jì)算式(1)的值，并根據(jù)式(1)的值更新水平擴(kuò)展順序。

(5)使用水平擴(kuò)展算法1進(jìn)行水平擴(kuò)展。

(6)使用IPO垂直擴(kuò)展算法進(jìn)行垂直擴(kuò)展。

(7)使用算法2對(duì)擴(kuò)展完后的已有測(cè)試集進(jìn)行約簡(jiǎn)處理。

(8)輸出測(cè)試集。

算法1水平擴(kuò)展算法

輸入 T={已有測(cè)試集};xj+1=待擴(kuò)展參數(shù);Dj+1={待擴(kuò)展參數(shù)的取值域};Wj+1={待擴(kuò)展參數(shù)的權(quán)值域}

輸出 T={經(jīng)過擴(kuò)展后的測(cè)試集}展參數(shù)的參數(shù)取值。選取公式為:

算法2約簡(jiǎn)算法

輸入 T={約簡(jiǎn)前的測(cè)試集}

輸出 T’={約簡(jiǎn)后的測(cè)試集}

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

由于IPO_PW算法是在基于IPO算法的基礎(chǔ)上實(shí)現(xiàn)的，因此IPO_PW算法也是一種啟發(fā)式算法，它不能保證在任何情況下都能生成最小的兩兩組合測(cè)試集。為了檢驗(yàn)IPO_PW算法在生成組合測(cè)試集過程中的實(shí)際效果，將IPO_PW算法的實(shí)驗(yàn)結(jié)果與組合測(cè)試其他幾種經(jīng)典算法進(jìn)行比較，如表3所示。

表3 6種算法的測(cè)試集大小對(duì)比

目前，有關(guān)兩兩組合覆蓋表生成的研究主要是關(guān)注如何減小測(cè)試集規(guī)模，因此表3主要集中于各種方法生成的測(cè)試集大小的比較。從表3可以看出，IPO_PW算法總體上是可以獲得較優(yōu)的測(cè)試集，特別是隨著測(cè)試集規(guī)模的增大，這種優(yōu)越性更加明顯。此外，IPO_PW算法還有一個(gè)重要特性，即它得到的測(cè)試用例是按其權(quán)值和降序排列的，在無法測(cè)試所有的測(cè)試用例時(shí)，可以優(yōu)先選擇那些比較重要的測(cè)試用例進(jìn)行測(cè)試，這尤其適用于現(xiàn)實(shí)場(chǎng)景中。

6 結(jié)束語

本文基于IPO算法提出一種處理參數(shù)帶權(quán)值的組合測(cè)試集生成算法。這種算法主要是對(duì)影響測(cè)試集的3個(gè)因素進(jìn)行改進(jìn)，并且在生成測(cè)試集后進(jìn)行約簡(jiǎn)，進(jìn)一步減小測(cè)試集的規(guī)模。實(shí)驗(yàn)結(jié)果表明，該算法在一定范圍內(nèi)不僅提高了IPO算法的測(cè)試性能，而且具有很強(qiáng)的實(shí)際應(yīng)用性。但目前的兩兩組合測(cè)試算法生成的測(cè)試集都只是最優(yōu)解的近似，今后將對(duì)現(xiàn)有算法作研究，以取得更好的測(cè)試效果。

［1］ 聶長海，徐寶文，史 亮．一種新的二水平多因素系統(tǒng)兩兩組合覆蓋測(cè)試數(shù)據(jù)生成算法［J］．計(jì)算機(jī)學(xué)報(bào)，2006，29(6):841-848．

［2］ 高建華，劉 慧．配對(duì)組合測(cè)試中參數(shù)約束問題研究［J］．計(jì)算機(jī)工程與科學(xué)，2011，33(3):103-107．

［3］ Yan Jun，Zhang Jian．A Backtracking Search Tool for Constructing Combinatorial Test Suites［J］．The Journal of Systems and Software，2008，81(10):1681-1693．

［4］ Williams A W，Probert R L．A Practical Strategy for Testing Pair-wise Coverage of Network Interfaces［C］//Proceedings of the 7th International Symposium on Software Reliability Engineering．Washington D．C．，USA:IEEE Press，1997:246-254．

［5］ Noritaka K，Tatssuhio T，Tohru K．A New Method for Constructing Pair-wise Covering Designs for Software Testing［J］．Information Processing Letters，2002，81(2):85-91．

［6］ Cohen D M，DalalS R，Parelius J，etal．The Combinatorial Design Approach to Automatic Test Generation［J］．IEEE Software，1996，13(5):83-87．

［7］ Cohen D M，Dalal S R，F(xiàn)redman M L，et al．The AETG System:An Approach to Test Based on Combinatorial Design［J］．IEEE Transactions on Software Engineering，1997，23(7):437-444．

［8］ 惠戰(zhàn)偉，黃 松，蘇士瀚，等．成對(duì)覆蓋組合測(cè)試用例生成方法研究［C］//2010亞太地區(qū)信息論學(xué)術(shù)會(huì)議論文集．［出版地不詳］:中國電子學(xué)會(huì)信息論分會(huì)，2010:264-267．

［9］ Yu Lei，Tai K C．In-parameter-order:A Test Generation Strategy for Pairwise Testing［D］．Raleigh，USA:North Carolina State University，2001．

［10］ Tai K C，Yu Lei．A TestGeneration Strategy for Pairwise Testing［J］．IEEE Transactions on Software Engineering，2002，28(1):109-111．

［11］ 嚴(yán) 俊，張 ?。M合測(cè)試:原理與方法［J］．軟件學(xué)報(bào)，2009，20(6):1393-1405．

［12］ 史 亮，聶長海，徐寶文．基于解空間樹的組合測(cè)試數(shù)據(jù)生成［J］．計(jì)算機(jī)學(xué)報(bào)，2006，29(6):849-857．

［13］ 戴 麗．組合測(cè)試用例生成技術(shù)的研究與應(yīng)用［D］．廣州:華南理工大學(xué)，2011．