帶權值參數的兩兩組合測試用例集生成算法

李龍澍，王雅婷

(安徽大學計算機科學與技術學院，合肥230601)

1 概述

在整個軟件開發生命周期中，軟件測試是非常重要的一個環節，是保證軟件質量、提高軟件可靠性的重要手段。研究表明，有20% ～40%左右的軟件故障是由某個系統參數引發，20% ～40%左右的故障由某2個參數的相互作用引發，而大約70%的軟件故障是由1個或2個參數的作用引起的［1］。所以，對各種待測軟件系統而言，兩兩組合測試是一種科學、實用而有效的測試方法［2］。

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

2 基本概念及相關定義

假設待測系統SUT(Software Under Testing)的n個輸入參數集合 X={x1，x2，…，xn}，其中每個輸入參數對應的取值域為Dj(j∈［1，n］)，即每個輸入參數有|Dj|個互異的取值。

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

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

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

當待擴展參數的值 Dj+1，k’(參數值集 Dj+1中的第k’個取值)與已擴展參數的值Dm，k(參數值集Dm中的第 k個取值)的組合未覆蓋時，Coverm，k取1，已覆蓋則取 0;Weightm，k為該組合的權重值;Sm，k等于已有測試集中Dm，k的總個數。

3 IPO算法影響因子分析及改進

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

3．1 待擴展參數的擴展次序

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

定義4(參數值的權值) 為每個參數取值Di，k(參數值集Di中的第k個取值)賦予一個數值Wi，k(－1．0≤Wi，k≤1．0)，其中，－1．0 表示優先級最低;1．0表示優先級最高，這個Wi，k就稱為該參數值的權值。

為每個參數取值賦予一個權值 Wi，k后，對可選參數進行排序的步驟如下:

(1)計算參數值兩兩組合的組合權重值

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

(2)計算兩參數間權值和

兩參數間權值和為該兩參數所有取值兩兩組合的組合權重值之和，計算公式為:

如參數(x1，x3)兩參數間權值和為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)兩參數間權值和分別為0．9，0．63。參數和參數取值及參數值權值的輸入如表1所示。其中，括號中的數值為該參數值的權值。

表1 參數和參數取值及參數值權值的輸入

(3)計算各參數的權值總和

每個參數的權值總和等于該參數與其他參數的兩參數間權值和的和。例如，上述例子各參數的權值總和如表2所示。

表2 各參數的權值總和

最后，根據各參數的權值總和的大小按降序進行排序，得到待擴展參數的擴展次序。例如，上述例子的擴展次序為:x1，x2，x3。這種排序過程適用于參數值帶權值的情況，若參數值未被賦予權值，則可直接根據參數取值個數|Dj|按降序對待擴展參數進行排序。

3．2 已有測試集的擴展次序

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

當參數值未被賦予權值時，則Weightm，k=1，可以進一步簡化公式。然后，根據已有測試用例的需求度R按從大到小降序的順序進行排序，得到已有測試集的擴展次序。

3．3 待擴展參數的取值選擇

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

(1)計算參數值的權值貢獻

依次選取待擴展參數的參數值，然后計算所選取參數值對應的權值貢獻。計算公式為:

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

在這個計算過程中，有一種特殊情況，就是擴展的兩兩組合包含了前面測試用例所覆蓋過的兩兩組合，那么此兩兩組合所對應的Coverm，k=0，即此兩兩組合所對應的參數值兩兩組合的組合權重值不計入該參數值的權值貢獻。

(2)為待擴展參數選取參數值

比較每個參數值所對應的權值貢獻，選取使權值貢獻達到最大的那個參數值作為此測試用例待擴

當參數值未被賦予權值時，上述兩步驟中的Weightm，k=1。

4 算法描述

IPO_PW(In-Parameter-Order based Parameter Weight)算法主要是根據參數的權值對IPO中的擴展次序和參數取值進行有關改進。并且，在擴展完所有參數后，對得到的測試集用約簡算法進一步處理，以獲得更加簡化的測試集。這種方法不僅生成的測試用例少，而且更適應現實場景對組合測試的要求。IPO_PW算法的基本步驟如下:

(1)確定待擴展參數的擴展次序:按照3．1節中待擴展參數的擴展次序的改進方法對參數進行排序。

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

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

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

(5)使用水平擴展算法1進行水平擴展。

(6)使用IPO垂直擴展算法進行垂直擴展。

(7)使用算法2對擴展完后的已有測試集進行約簡處理。

(8)輸出測試集。

算法1水平擴展算法

輸入 T={已有測試集};xj+1=待擴展參數;Dj+1={待擴展參數的取值域};Wj+1={待擴展參數的權值域}

輸出 T={經過擴展后的測試集}展參數的參數取值。選取公式為:

算法2約簡算法

輸入 T={約簡前的測試集}

輸出 T’={約簡后的測試集}

5 實驗結果與分析

由于IPO_PW算法是在基于IPO算法的基礎上實現的，因此IPO_PW算法也是一種啟發式算法，它不能保證在任何情況下都能生成最小的兩兩組合測試集。為了檢驗IPO_PW算法在生成組合測試集過程中的實際效果，將IPO_PW算法的實驗結果與組合測試其他幾種經典算法進行比較，如表3所示。

表3 6種算法的測試集大小對比

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

6 結束語

本文基于IPO算法提出一種處理參數帶權值的組合測試集生成算法。這種算法主要是對影響測試集的3個因素進行改進，并且在生成測試集后進行約簡，進一步減小測試集的規模。實驗結果表明，該算法在一定范圍內不僅提高了IPO算法的測試性能，而且具有很強的實際應用性。但目前的兩兩組合測試算法生成的測試集都只是最優解的近似，今后將對現有算法作研究，以取得更好的測試效果。

［1］ 聶長海，徐寶文，史 亮．一種新的二水平多因素系統兩兩組合覆蓋測試數據生成算法［J］．計算機學報，2006，29(6):841-848．

［2］ 高建華，劉 慧．配對組合測試中參數約束問題研究［J］．計算機工程與科學，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，Fredman 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］ 惠戰偉，黃 松，蘇士瀚，等．成對覆蓋組合測試用例生成方法研究［C］//2010亞太地區信息論學術會議論文集．［出版地不詳］:中國電子學會信息論分會，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］ 嚴 俊，張 健．組合測試:原理與方法［J］．軟件學報，2009，20(6):1393-1405．

［12］ 史 亮，聶長海，徐寶文．基于解空間樹的組合測試數據生成［J］．計算機學報，2006，29(6):849-857．

［13］ 戴 麗．組合測試用例生成技術的研究與應用［D］．廣州:華南理工大學，2011．