基于關(guān)聯(lián)矩陣的兩兩組合測(cè)試算法

習(xí) 樂(lè) 賁可榮

基于關(guān)聯(lián)矩陣的兩兩組合測(cè)試算法

習(xí) 樂(lè) 賁可榮

（海軍工程大學(xué)計(jì)算機(jī)工程系 武漢 430033）

組合測(cè)試是軟件黑盒測(cè)試中的一種常用方法，能有效檢測(cè)軟件系統(tǒng)中由各個(gè)因素相互作用所引發(fā)的軟件故障。基于參數(shù)順序的約束滿足算法IPO-SAT是一種常用的組合測(cè)試用例生成算法，該算法約束控制能力突出，能生成精簡(jiǎn)的兩兩組合測(cè)試用例集，但其計(jì)算過(guò)程頻繁調(diào)用約束求解器，導(dǎo)致較多的時(shí)間開(kāi)銷。針對(duì)該問(wèn)題，論文提出一種基于關(guān)聯(lián)矩陣的兩兩組合測(cè)試改進(jìn)算法MIPO，采取將約束信息存儲(chǔ)于關(guān)聯(lián)矩陣中的方式來(lái)避免調(diào)用約束求解器，以減少測(cè)試用例生成過(guò)程中的整體時(shí)間。針對(duì)5組不同的參數(shù)組合進(jìn)行實(shí)驗(yàn)，結(jié)果表明，改進(jìn)后的算法與IPO-SAT算法相比，生成兩兩組合測(cè)試用例集的時(shí)間可節(jié)省90%以上。

約束控制；測(cè)試用例生成；關(guān)聯(lián)矩陣；組合測(cè)試

AbstractCombination test is a method usually used in software black box testing，which can effectively detect the software fault caused by the interaction of factors in the software system.The IPO-SAT algorithm used to generate the combined test case has strong control ability and can generate right pairwise test suites，but the calculation process frequently calling the constraint solver is complex and time consuming.To solve this problem，this paper proposes an improved pairwise test algorithm based on the associa?tion matrix，storing the constraint information in the correlation matrix without calling the constraint solver to reduce the computa?tion time.Experiment shows that compared to the IPO-SAT algorithm，the algorithm generates pairwise test suite with 90%time re?duction.

Key Wordsconstraints control，test case generation，correlation matrix，combination test

Class NumberTP311.5

1 引言

軟件運(yùn)行會(huì)受到系統(tǒng)的配置、外部的輸入等因素的影響，除了可能受單因素影響外，因素間的相互作用也可能對(duì)系統(tǒng)的運(yùn)行造成影響。在軟件黑盒測(cè)試中，組合測(cè)試是一種有效的測(cè)試用例生成技術(shù)［1］，它假定系統(tǒng)失效是由少數(shù)參數(shù)間相互作用所觸發(fā)，因此可用較小規(guī)模的測(cè)試用例集完成測(cè)試工作。兩兩組合測(cè)試（Pairwise Test）是組合測(cè)試中最簡(jiǎn)單的一種方法，要求測(cè)試用例集中每個(gè)參數(shù)的單個(gè)取值和所有其他參數(shù)的取值至少存在一次組合，既可以將測(cè)試用例的數(shù)量控制在較低水平，同時(shí)也能有效地暴露軟件中存在的問(wèn)題。相對(duì)于完全組合測(cè)試，兩兩組合測(cè)試通常能用較少的測(cè)試用例發(fā)現(xiàn)系統(tǒng)中的絕大多數(shù)缺陷。對(duì)兩兩組合測(cè)試效率［2～3］的統(tǒng)計(jì)結(jié)果表明，67%的失效是由一個(gè)參數(shù)出錯(cuò)引起的，93%的失效是由不超過(guò)2個(gè)參數(shù)組合出錯(cuò)引起的，98%的失效是由不超過(guò)3個(gè)參數(shù)組合出錯(cuò)引起的。

兩兩組合測(cè)試的目標(biāo)是通過(guò)測(cè)試每一對(duì)參數(shù)的不同取值來(lái)獲得較高的暴露問(wèn)題能力，所以要求每一對(duì)參數(shù)的組合至少在測(cè)試用例集中出現(xiàn)一次［4］。但邊界值分析和等價(jià)類劃分法，通常只能保證單個(gè)參數(shù)的覆蓋，所以在測(cè)試效果上，兩兩組合測(cè)試方法明顯更有優(yōu)勢(shì)［2］。然而，Lei等研究表明［5～6］，根據(jù)給定參數(shù)的候選值，尋找兩兩組合測(cè)試用例集是一個(gè)NP完全問(wèn)題，所以很難找到一種高效的算法求解最小的組合測(cè)試用例集，大多數(shù)研究工作集中在算法改進(jìn)和擴(kuò)展上。

Cohen 等［7～8］提出了基于 one-test-at-a-time策略的組合測(cè)試用例生成方法AETG，每次增加一個(gè)新的測(cè)試用例，計(jì)算過(guò)程較為復(fù)雜，得到的測(cè)試用例集也不夠精簡(jiǎn)。文獻(xiàn)［9～10］用貪心算法來(lái)改進(jìn)AETG的缺點(diǎn)，由于都基于AETG框架，只是啟發(fā)策略不同，并沒(méi)有本質(zhì)的改進(jìn)。Lei等［11］提出了基于in-parameter-order策略的IPO算法，該算法先構(gòu)造前兩個(gè)參數(shù)的兩兩組合，然后逐步擴(kuò)展到全部參數(shù)。它減小了算法的復(fù)雜性，同時(shí)也得到更為精簡(jiǎn)的測(cè)試用例集，但是不能處理參數(shù)間的約束問(wèn)題。Hnich等［12］嘗試將組合測(cè)試的約束問(wèn)題轉(zhuǎn)化為SAT的子句集來(lái)解決約束問(wèn)題，但是得到的不是最優(yōu)解，嚴(yán)峻等［13］使用 SAT工具 zChaff解決了這個(gè)問(wèn)題。Lei等［14］給出了增強(qiáng)約束控制能力的IPO（In-Parameter-Order）算法，文獻(xiàn)［15］針對(duì)它的約束控制問(wèn)題，進(jìn)一步給出了優(yōu)化算法IPO-SAT，但是仍需要頻繁調(diào)用約束求解器。文獻(xiàn)［16］中采用關(guān)聯(lián)矩陣的形式，存儲(chǔ)組合參數(shù)的覆蓋信息，雖然計(jì)算快速簡(jiǎn)單，但是約束控制能力差。目前還找不到一種通用的方法來(lái)高效解決所有組合測(cè)試的求解問(wèn)題，IPO算法可以很好地控制測(cè)試用例集的規(guī)模，但是在參數(shù)復(fù)雜時(shí)往往使得求解時(shí)間急劇增加。

針對(duì)上述問(wèn)題，本文將關(guān)聯(lián)矩陣和IPO算法相結(jié)合，提出一種改進(jìn)的基于關(guān)聯(lián)矩陣的兩兩組合測(cè)試算法（Matrix-based In Parameter Order，MIPO），通過(guò)對(duì)關(guān)聯(lián)矩陣的屬性進(jìn)行擴(kuò)展來(lái)增強(qiáng)約束控制能力，將約束信息保存在關(guān)聯(lián)矩陣中，以擺脫對(duì)約束求解器的依賴，從而減少求解時(shí)間，快速生成滿足約束條件的兩兩組合測(cè)試用例集。實(shí)驗(yàn)結(jié)果表明，MIPO算法相比IPO-SAT，生成測(cè)試用例集的時(shí)間大幅減少。

2 組合測(cè)試相關(guān)知識(shí)

令待測(cè)試的軟件系統(tǒng)有m個(gè)輸入?yún)?shù)，第i個(gè)參數(shù)有ni個(gè)可能的取值，Vi表示第i個(gè)參數(shù)取值的集合，那么 t=(v1，v2，…，vm)（其中 v1∈ V1，v2∈ V2，…，vm∈Vm）就表示一個(gè)測(cè)試用例，這樣的t的全體組成測(cè)試用例集T。理想情況下，測(cè)試工作需要執(zhí)行完T中所有的測(cè)試用例。當(dāng)參數(shù)取值數(shù)ni較大時(shí)，執(zhí)行T中全部的測(cè)試用例是不現(xiàn)實(shí)的，只能選擇其中部分測(cè)試用例進(jìn)行測(cè)試，所以要權(quán)衡發(fā)現(xiàn)問(wèn)題的能力和測(cè)試用例的數(shù)量。組合測(cè)試就是要研究測(cè)試代價(jià)和測(cè)試效果間的平衡。

2.1 關(guān)聯(lián)矩陣

設(shè) G=V，E 是 無(wú) 向 圖 ，V={v1，v2，…，vn} ，E={e1，e2，…，em} ，關(guān)聯(lián) 矩陣 M=(mij)n×n，其中：mij=1表示vi和vj存在連接，mij=0表示vi和vj不存在連接。例如一個(gè)包含4個(gè)頂點(diǎn)，3條邊的無(wú)向圖，其關(guān)聯(lián)矩陣如圖1所示。類比無(wú)向圖的關(guān)聯(lián)矩陣，將待組合參數(shù)的所有取值依次編排起來(lái)，分別對(duì)應(yīng)矩陣的行和列，構(gòu)成參數(shù)取值的關(guān)聯(lián)矩陣，矩陣中每個(gè)值都表示參數(shù)取值間的組合關(guān)系。由于關(guān)聯(lián)矩陣的對(duì)稱性和冗余性，約定參數(shù)的關(guān)聯(lián)矩陣?yán)锏囊韵略責(zé)o效：表示同一參數(shù)的不同取值間的組合關(guān)系的元素、表示各個(gè)參數(shù)的取值和自身組合關(guān)系的元素、矩陣左對(duì)角線以下的元素，如圖2中陰影部分所示。初始關(guān)聯(lián)矩陣中的元素都為0，若測(cè)試用例集中出現(xiàn)了某兩個(gè)參數(shù)取值之間的組合，就將關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素標(biāo)記為1。當(dāng)兩兩組合的測(cè)試用例集滿足覆蓋要求時(shí)，則矩陣中對(duì)應(yīng)的有效元素都為1，即為目標(biāo)矩陣。設(shè)X、Y、Z三個(gè)參數(shù)的取值分別為{x1，x2，x3}，{y1，y2}，{z1，z2}，當(dāng)存在(x3，y1，z2)組合時(shí)所對(duì)應(yīng)的關(guān)聯(lián)矩陣如圖2所示。

圖1 無(wú)向圖及關(guān)聯(lián)矩陣

圖2 XYZ對(duì)應(yīng)的初始關(guān)聯(lián)矩陣

2.2 約束條件

約束條件是指各個(gè)參數(shù)的取值組合必須滿足一定的條件，而不是完全組合自由的。約束條件增加了組合測(cè)試的難度。例如，在表1所示的平板電腦和瀏覽器之間的組合中，平板電腦可以選擇ipad和 Surface，瀏 覽 器 可 以 選 擇 safari、IE、chrome、Edge、firefox。組合（iPad，IE）是不會(huì)出現(xiàn)的，因此平板電腦和瀏覽器之間的組合并非完全自由，即為組合的一個(gè)約束條件。

表1 設(shè)備和瀏覽器的組合

最常見(jiàn)的兩種約束類型是參數(shù)組合中的依賴和沖突［15］：

1）瀏覽器選擇IE，平板電腦就必須選擇Sur?face，這種約束條件就是依賴型約束。瀏覽器為IE時(shí)，平板電腦必須為Surface，平板電腦取其它的值都是無(wú)效的組合，因此組合（iPad，IE）是禁止的，同樣禁止的組合還有（iPad，Edge）。

2）平板電腦選擇iPad，瀏覽器就不能選擇IE或Edge，這種約束條件就是沖突型約束。平板電腦為iPad時(shí)，瀏覽器只能選擇IE和Edge之外的選項(xiàng)，否則都是無(wú)效的組合，所以這些組合的是禁止的：（iPad，IE）、（iPad，Edge）。

對(duì)于參數(shù)間的依賴約束和沖突約束，這些約束條件都可以用禁止出現(xiàn)的組合的來(lái)表示。

2.3 IPO算法

IPO（In-Parameter-Order）是一種貪心算法，常被用來(lái)求解兩兩組合測(cè)試用例集。IPO算法先求得前兩個(gè)參數(shù)的完全組合，在此基礎(chǔ)上，不斷將后續(xù)的參數(shù)添加到測(cè)試用例集中。在添加參數(shù)的過(guò)程中，需要保證后續(xù)每一個(gè)參數(shù)的取值與之前所有參數(shù)取值的兩兩組合，當(dāng)最后一個(gè)參數(shù)完成時(shí)，則算法結(jié)束。

針對(duì)3個(gè)參數(shù)A、B、C，其取值分別為{a1，a2}、{b1，b2}、{c1，c2，c3}的情況，IPO算法步驟如下：

1）先構(gòu)建前兩個(gè)參數(shù)A、B的取值的完全組合即：(a1，b1，_)，(a1，b2，_)，(a2，b1，_)，(a2，b2，_)，此時(shí) 未 覆 蓋 的 組 合 為 a1c1，a1c2，a1c3，a2c1，a2c2，a2c3，b1c1， b1c2， b1c3， b2c1， b2c2， b2c3。

2）在已生成的測(cè)試用例中將后續(xù)參數(shù)補(bǔ)充完整。首先添加 c1到 (a1，b1，_)中得到 (a1，b1，c1)，則無(wú)覆蓋的組合為 a1c2，a1c3，a2c1，a2c2，a2c3，b1c2，b1c3，b2c1，b2c2，b2c3。同樣添加 (a1，b2，c2)，(a2，b1，c3)，(a2，b2，c1)，此時(shí)未覆蓋組合為 a1c3，a2c2，a1c2，a2c3。

3）為未覆蓋的組合添加新用例。由于還剩4個(gè)組合未覆蓋，所以還需要添加新的測(cè)試用例來(lái)達(dá)到對(duì)所有組合的覆蓋。對(duì)于a1c3，a2c2，可以添加(a1，_，c3)，(a2，_，c2)。注意到，當(dāng) (a1，_，c3)填充成(a1，b2，c3)時(shí)，可以覆蓋 b2c3。同理 (a2，b1，c2)可以覆蓋b1c2。此時(shí)沒(méi)有未被覆蓋的組合，算法結(jié)束。

3 兩兩組合測(cè)試改進(jìn)算法M IPO

如何提高算法的約束控制能力，減少計(jì)算時(shí)間，生成更小的測(cè)試用例集是組合測(cè)試研究的重點(diǎn)。在兩兩組合測(cè)試中，各種算法的約束控制能力已經(jīng)滿足大部分需要，但是算法的求解時(shí)間還存在優(yōu)化的空間。

3.1 問(wèn)題分析及解決思路

文獻(xiàn)［15］中的IPO-SAT算法，雖然能夠生成規(guī)模適當(dāng)?shù)臏y(cè)試用例集，但是對(duì)約束求解器頻繁調(diào)用增加了時(shí)間開(kāi)銷，尤其當(dāng)參數(shù)個(gè)數(shù)和約束條件增多時(shí)，耗時(shí)急劇增加。受文獻(xiàn)［16］中關(guān)聯(lián)矩陣的啟發(fā)，本文提出一種改進(jìn)的基于關(guān)聯(lián)矩陣的兩兩組合測(cè)試用例生成算法MIPO，以減少生成測(cè)試用例集所用時(shí)間。該算法過(guò)程為：首先引入關(guān)聯(lián)矩陣，同時(shí)為解決復(fù)雜的依賴問(wèn)題，對(duì)關(guān)聯(lián)矩陣進(jìn)行約束信息屬性擴(kuò)展，以達(dá)到約束求解要求。其次，與IPO-SAT算法不同，將禁止出現(xiàn)的組合信息添加到關(guān)聯(lián)矩陣的擴(kuò)展屬性中，從而直接在關(guān)聯(lián)矩陣中檢查約束條件的滿足情況，不再調(diào)用約束求解器，以降低IPO算法為驗(yàn)證所生成組合是否滿足約束條件所帶來(lái)的時(shí)間開(kāi)銷，縮短整個(gè)測(cè)試用例集的生成時(shí)間。

3.2 基于關(guān)聯(lián)矩陣的M IPO算法

在關(guān)聯(lián)矩陣的基礎(chǔ)上，擴(kuò)充矩陣元素的屬性，將約束控制信息加入其中，使得每個(gè)元素包含兩個(gè)屬性：覆蓋信息F和約束信息Y。用Cell［a，b］表示取值a和取值b在關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素，Cell［end，b］表示b所在列最后一行的元素。關(guān)聯(lián)矩陣的具體含義如表2所示。

表2 關(guān)聯(lián)矩陣擴(kuò)展后的屬性和含義

由于關(guān)聯(lián)矩陣的最后一行未被利用，可以用于統(tǒng)計(jì)各取值的覆蓋情況和約束信息，每一列的覆蓋信息F之和保存在最后一行對(duì)應(yīng)的覆蓋信息F中，每一列的約束信息Y之和保存在最后一行對(duì)應(yīng)的約束信息Y中。改進(jìn)的算法利用IPO的用例生成策略，在滿足約束條件的狀態(tài)下不斷將新的參數(shù)取值添加到生成的測(cè)試用例集中。對(duì)于m個(gè)輸入?yún)?shù) P1，P2，P3，…，Pm，每個(gè)參數(shù)分別對(duì)應(yīng)著 n1，n2，n3，…，nm個(gè)取值 (n1≥n2≥n3≥…≥nm)，在這些輸入?yún)?shù)之中，存在著約束條件集C，C中的組合禁止出現(xiàn)在測(cè)試用例集中，最終算法退出時(shí)得到滿足約束條件的測(cè)試用例集T。在下面給出基于關(guān)聯(lián)矩陣的MIPO組合測(cè)試算法，其中算法1調(diào)用算法1.1和算法1.2。算法1初始化關(guān)聯(lián)矩陣并生成覆蓋前兩個(gè)參數(shù)組合的測(cè)試用例。

算法1 基于關(guān)聯(lián)矩陣的IPO組合測(cè)試算法

輸入：參數(shù) P1，P2，P3，…，Pm，及對(duì)應(yīng)的候選輸入個(gè)數(shù) n1，n2，

n3，…，nm，約束集C 。輸出：測(cè)試用例表T。

1.生成一個(gè)關(guān)聯(lián)矩陣M；

2.For each Cell［x，y］∈M do

3.Cell［x，y］.F←0；

4.Cell［x，y］.Y←0；5.End for

6.For each（x，y）∈C do

7.Cell［x，y］.Y←1；

8.Cell［end，y］.Y←Cell［end，y］.Y+1；

9.End for

10.將P1，P2兩兩組合加入T，T=｛（P1.u，P2.v，_，…，_）|P1.u，P2.v分別為P1，P2的取值｝；

11.Cell［P1.u，P2.v］.F←1；

12.Cell［end，P2.v］.F←Cell［end，P2.v］.F+1；

13.For Cell［P1.u，P2.v］∈M do

14.If Cell［P1.u，P2.v］.Y=1&Cell［P1.u，P2.v］.F=1 then

15. 從T中刪除（P1.u，P2.v，_，…，_）；

16.Cell［P1.u，P2.v］.F←0；

17.Cell［end，P2.v］.F←Cell［end，P2.v］.F-1；

18. End if

19.End for

20.For i：=3 to m do

21. 調(diào)用子算法ADDPARA（T，M，Pi）；//在T中添加參數(shù)Pi

22. 調(diào)用子算法ADDCASE（T，M，Pi）；//在T中添加Pi的新用例

23.End For

算法1主要生成前兩個(gè)參數(shù)的兩兩組合，后續(xù)參數(shù)尚未加入測(cè)試用例集T中，所以針對(duì)每個(gè)后續(xù)參數(shù)Pi，都要調(diào)用算法1.1來(lái)將T中的每個(gè)用例中填入Pi的取值。

算法1.1 ADDPARA（T，M，Pi）

輸入：已生成的測(cè)試用例集T及對(duì)應(yīng)的關(guān)聯(lián)矩陣M，參數(shù)Pi。

輸出：更新后的測(cè)試用例集T和關(guān)聯(lián)矩陣M。

假定Pi的取值分別為v1，v2，v3，…，vni；

1.For each t∈T do

2. For v：=v1to vmdo

4. End for

5.根據(jù)Cell［end，Pi.v］.F對(duì)v1，v2，v3，…，vni進(jìn)行增序排序，

記錄在數(shù)組A［］中；

6. For k：=1 to nido

7. 將A［k］對(duì)應(yīng)的取值Pi.v加入到t中對(duì)應(yīng)參數(shù)位置，并在關(guān)聯(lián)矩陣中設(shè)置對(duì)應(yīng)的覆蓋信息；

8.If Cell［end，Pi.v］.Y=0 then

9. Break；

10. Else

11.For each Cell［a，Pi.v］∈M do

12. If Cell［a，Pi.v］.Y=1&Cell［a，Pi.v］.F=1&a≠end then

13. 將Pi.v從t中刪除，并在關(guān)聯(lián)矩陣中更新對(duì)應(yīng)的覆蓋信息；

14. Break；

15. End if

16. End for

17. End if

18.End for

19.End for

算法1.1在T中的每個(gè)測(cè)試用例中都加入了Pi的一個(gè)取值，但是不能排除Pi是否仍有未覆蓋到的組合，因此調(diào)用算法1.2來(lái)將所有的Pi組合加入T中。

算法1.2 ADDCASE（T，M，Pi）

輸入：已生成的測(cè)試用例集T及對(duì)應(yīng)的關(guān)聯(lián)矩陣M，參數(shù)Pi。

輸出：更新后的測(cè)試用例集T和關(guān)聯(lián)矩陣M。

假定Pi.v是Pi的取值，Ph.w是Ph的取值（h＜i）

1.For each Cell［Ph.w，Pi.v］∈M do

2.If Cell［Ph.w，Pi.v］.Y=0&Cell［Ph.w，Pi.v］.F=0 then

3. For each t∈T do

4. If t中 Ph為空 &Pi為 v then

5. 將Ph.w添加到t中Ph對(duì)應(yīng)的位置；

6. 設(shè)置關(guān)聯(lián)矩陣中對(duì)應(yīng)的覆蓋信息；

7. End if

8.For each Cell（a，b）∈M do

9.If Cell（a，b）.Y=1&Cell（a，b）.F=1&a≠end then

10. 從t中刪除Ph.w，更新關(guān)聯(lián)矩陣的覆蓋信息；

11. End if

12. End for

13. End for

14.End if

15.End for

16.For each Cell［Ph.w，pi.v］∈M do

17.if Cell［Ph.w，Pi.v］.Y=0&Cell［Ph.w，Pi.v］.F=0 then

18. 在T中新增t’，分別設(shè)置Ph，Pi為w，v；

19. 更新關(guān)聯(lián)矩陣的覆蓋信息；

20.End if

21.End for

22.For each t∈T do

23.If t中參數(shù)Pj為空then

24. For v：=v1to vnjdo

26. End for

27. 根據(jù) Cell［end，Pj.v］.F對(duì)v1，v2，v3，…，vnj進(jìn)行增序排序，記錄在數(shù)組A［］中；

28. For k：=1 to njdo

29. 將A［k］對(duì)應(yīng)的Pj.v加入到t中Pj對(duì)應(yīng)的位置，并在關(guān)聯(lián)矩陣中設(shè)置對(duì)應(yīng)的覆蓋信息；

30.If Cell［end，Pj.v］.Y=0 then

31. break；

32. Else

33.For each Cell［a，Pj.v］∈M do

34.If Cell［a，Pj.v］.Y=1&Cell［a，Pj.v］.F=1&a≠end then

35 將Pj.v從t中刪除，并更新關(guān)聯(lián)矩陣中對(duì)應(yīng)的覆蓋信息；

36. Break；

37. End if

38. End for

39. End if

40. End for

41. End if

42.End for

算法1中，首先構(gòu)建關(guān)聯(lián)矩陣M并初始化，然后將所有的約束條件添加到M中。根據(jù)取值個(gè)數(shù)最多的兩個(gè)參數(shù)，進(jìn)行完全組合，添加到測(cè)試用例表T中，并更新M中的覆蓋信息。根據(jù)覆蓋信息和約束信息，檢查T中組合的合法性，對(duì)于不合法的組合，從T中刪除并清除M中對(duì)應(yīng)的覆蓋信息。

然后添加后續(xù)的參數(shù)Pi，調(diào)用算法1.1。對(duì)T中每一個(gè)用例t，先根據(jù)Pi當(dāng)前所有取值各自已經(jīng)參與組合的次數(shù)進(jìn)行增序排序，選擇次數(shù)最少的取值添加到t中，如果約束條件不被滿足，則替換成下一個(gè)取值，直到滿足為止，然后更新M中覆蓋信息。

完善所生成的用例，再調(diào)用算法1.2。當(dāng)T中所有的用例都添加了Pi的一個(gè)合法取值后，如果在M中，仍存在Pi未覆蓋的組合(Pk.u，Pi.v)，則根據(jù)未覆蓋組合對(duì)應(yīng)的兩個(gè)參數(shù)Pk，Pi，在T中尋找這兩個(gè)參數(shù)未覆蓋的測(cè)試用例t，將u和v添加到t中Pk，Pi對(duì)應(yīng)的位置，然后檢查合法性，如非法就從t中刪除u和v，并清除對(duì)應(yīng)的覆蓋信息。然后用同樣方法處理下一個(gè)未覆蓋的組合，直到處理完所有未覆蓋的組合。

如果在M中，仍然存在Pi未覆蓋的組合(Pk.u，Pi.v)，則根據(jù)未覆蓋組合對(duì)應(yīng)的兩個(gè)參數(shù)Pk和Pi，在T中增加測(cè)試用例t，將u和v分別添加到t中Pk和Pi對(duì)應(yīng)的位置，并更新對(duì)應(yīng)的覆蓋信息。然后用同樣方法處理下一個(gè)未覆蓋的組合，直到處理完所有未覆蓋的組合。

對(duì)T中每一個(gè)用例t，若t中存在未填充的參數(shù)Pj，先根據(jù)Pj當(dāng)前所有取值各自已經(jīng)參與組合的次數(shù)進(jìn)行增序排序，選擇次數(shù)最少的取值添加到t中相應(yīng)位置，如果約束條件不滿足，則換成下一個(gè)取值，直到滿足為止，然后更新M中覆蓋信息，添加Pi工作完成，接著繼續(xù)添加下一個(gè)參數(shù)Pi+1，直到Pm添加完成。

4 實(shí)驗(yàn)

某艦艇指控軟件從數(shù)據(jù)鏈接口獲取當(dāng)前艦艇航海信息，對(duì)其接口參數(shù)取值范圍進(jìn)行等價(jià)類劃分和邊界值分析后，得到接口參數(shù)的離散取值情況如表3所示。

表3 航海參數(shù)及離散取值情況

表3中一共有6個(gè)參數(shù)，每個(gè)參數(shù)有10個(gè)離散取值，覆蓋參數(shù)間的所有組合需要106個(gè)用例，故考慮兩兩組合的測(cè)試方法減少測(cè)試用例。為了驗(yàn)證MIPO算法在縮減計(jì)算時(shí)間上的有效性，本文用C語(yǔ)言實(shí)現(xiàn)了MIPO算法和IPO-SAT算法，對(duì)6個(gè)參數(shù)、每個(gè)參數(shù)10個(gè)取值進(jìn)行兩兩組合測(cè)試用例集生成時(shí)間對(duì)比實(shí)驗(yàn)，所有的參數(shù)間允許自由組合。實(shí)驗(yàn)平臺(tái)配置為：處理器Core i5-2430M 2.4GHz、內(nèi)存8GB DDR3-1333、操作系統(tǒng)Windows7 64位、集成開(kāi)發(fā)環(huán)境VS2010專業(yè)版。兩種算法的試驗(yàn)結(jié)果對(duì)比如表4所示。

表4 MIPO與IPO-SAT生成測(cè)試用例數(shù)量和時(shí)間

由表4中的實(shí)驗(yàn)結(jié)果看出，兩種測(cè)試用例生成算法生成用例規(guī)模相當(dāng)，但是MIPO算法生成時(shí)間遠(yuǎn)小于IPO-SAT算法。為了充分比較兩種算法在生成用例規(guī)模和時(shí)間開(kāi)銷上的差異，本文補(bǔ)充了不同的對(duì)比實(shí)驗(yàn)，包括參數(shù)個(gè)數(shù)都為6個(gè)時(shí)，參數(shù)取值分別為20個(gè)、15個(gè)的情況以及參數(shù)的取值個(gè)數(shù)都為20個(gè)，參數(shù)數(shù)量分別為5個(gè)、7個(gè)的情況，分別記為ST1、ST2、ST3、ST4。具體的參數(shù)配置情況如表5所示。

表5 4組對(duì)比試驗(yàn)參數(shù)配置情況

分別使用IPO-SAT程序和MIPO程序來(lái)生成ST1、ST2、ST3、ST4的測(cè)試用例集，得到生成的測(cè)試用例數(shù)量以及所花費(fèi)的時(shí)間，如表6所示。

表6 生成用例時(shí)間對(duì)比

從表6可以看出，在同樣的輸入?yún)?shù)情況下，MIPO算法在生成兩兩組合測(cè)試用例時(shí)，比IPO-SAT算法花費(fèi)的時(shí)間減少90%以上。當(dāng)參數(shù)個(gè)數(shù)不變時(shí)，取值個(gè)數(shù)增加，IPO-SAT算法的執(zhí)行時(shí)間急劇增加，而MIPO算法的執(zhí)行時(shí)間增加緩慢。當(dāng)參數(shù)取值個(gè)數(shù)不變時(shí)，參數(shù)個(gè)數(shù)增加時(shí)，IPO-SAT算法的執(zhí)行時(shí)間急劇增加，而MIPO算法的執(zhí)行時(shí)間增加緩慢。實(shí)驗(yàn)結(jié)果表明，MIPO算法相比IPO-SAT，生成測(cè)試用例集的時(shí)間大幅減少，在參數(shù)增多的情況下，時(shí)間上的優(yōu)勢(shì)更為突出。

通過(guò)實(shí)驗(yàn)可以看出，MIPO與IPO-SAT相比，能夠生成大小相當(dāng)?shù)臏y(cè)試用例集，能夠在更快的時(shí)間內(nèi)計(jì)算完成，計(jì)算效率更高。改進(jìn)算法在求解時(shí)間上的優(yōu)勢(shì)主要在于MIPO不調(diào)用約束求解器，節(jié)省了大量的求解時(shí)間。但是需要付出的代價(jià)是犧牲了約束求解器的通用性，關(guān)聯(lián)矩陣只能處理兩個(gè)參數(shù)之間的約束問(wèn)題。

5 結(jié)語(yǔ)

本文通過(guò)對(duì)已有兩兩組合測(cè)試用例生成算法的改進(jìn)，提出了一種新的兩兩組合測(cè)試用例生成算法MIPO。基于關(guān)聯(lián)矩陣的兩兩組合測(cè)試算法，執(zhí)行步驟簡(jiǎn)單快速。另一方面，IPO-SAT方法能夠很好地處理約束問(wèn)題，同時(shí)也能夠得到較為精簡(jiǎn)的測(cè)試用例集，但是當(dāng)參數(shù)數(shù)量和約束增多時(shí)，計(jì)算耗時(shí)急劇增加。針對(duì)該問(wèn)題，本文提出了一種兩兩組合測(cè)試用例集生成算法MIPO，利用關(guān)聯(lián)矩陣存儲(chǔ)約束信息，使用IPO策略生成測(cè)試用例集。實(shí)驗(yàn)表明，在給定同樣的參數(shù)設(shè)置時(shí)，MIPO算法相比IPO-SAT算法，由于擺脫了約束求解器的依賴，能夠大幅減少計(jì)算時(shí)間。受限于關(guān)聯(lián)矩陣的二維結(jié)構(gòu)，還不能處理三個(gè)及以上參數(shù)間的組合問(wèn)題，如何將該算法推廣到更高強(qiáng)度的組合測(cè)試中是需要進(jìn)一步研究的內(nèi)容。

［1］陳翔，顧慶，王新平，等.組合測(cè)試研究進(jìn)展［J］.計(jì)算機(jī)科學(xué)，2010，37（3）：1-5.

CHEN Xiang，GU Qing，WANG Xinping，et al.Research Advances in Interaction Testing［J］.Computer Science，2010，37（3）：1-5.

［2］K.Go，S.Kang，J.Baik.Pairwise testing for systems with date derived from real-valued variable inputs［J］.Soft?ware：Practice and Experience，2016，46（3）：381-403.

［3］D.M.Cohen，S.R.Dalal，J.Parelius.The combinatorial design approach to automatic test generation［J］.Soft?ware：Practice and Experience，1996，13（5）：83-88.

［4］D.Richard，R.kacker，Yu Lei.Introduction to Combina?torial Testing［M］.Berlin：Springer，2013：34-35.

［5］王子元，錢巨，陳林，等.基于One-test-at-a-time策略的可變力度組合測(cè)試用例生成方法［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35（12）：2541-2552.

WANG Ziyuan，QIAN Ju，CHEN Lin，et al.Generating Variable Strength Combinatorial Test Suite with One-test-at-a-time Strategy［J］.Chinese Journal of Com?puters，2012，35（12）：2541-2552.

［6］Lei Y，Tai KC.In-Parameter-Order：A test generation strategy for pairwise testing［J］.IEEE Transactions on Soft?ware Engineering，2002，28（1）：109-111.

［7］D.M.Cohen，S.R.Dalal，J.Parelius.The Combinatorial Design Approach to Automatic Test Generation［J］.IEEE Software，1996，13（5）：83-87.

［8］D.M.Cohen，S.R.Dalal，M.L.Fredman.The AETGSys?tem：An Approach to Testing Based on Combinatorial De?sign［J］.IEEE Transactions on Software Engineering，1997，23（7）：56-63.

［9］R.Bryce.A Deterministic Density Algorithm for Pairwise Interaction Coverage［C］//Proceedings of the International Conference on Software Engineering.Innsbruck：IEEE Press，2004.245-252.

［10］Y.W.Tung，W.S.Aldiwan.Automating test case genera?tion for the new generation mission software system［C］//Proceedings of IEEE Aerospace Conference.New?ark，2000.431-437.

［11］Y.Lei，K.C.Tai.In-parameter-order：a test generation strategy for pairwise testing［C］//Proceedings of High-As?surance Systems Engineering Symposium.Los Alamitos：IEEEPress，1998.254-261.

［12］Hnich B，Prestwich S，Selensky E.Constraint-Based ap?proaches to the covering test problem［C］//Joint Annual Workshop of ERCIM/CoLogNet on Constraint Solving and Constraint Logic Programming（CSCLP）.Berlin：Springer，2004.172-186.

［13］Yan J，Zhang J.Backtracking algorithms and search heu?ristics to generate test suites for combinatorial testing［C］//30th Annual International Computer Software and Applications Conference.Los Alamitos：IEEE Press，2006.385-394.

［14］Linbin Yu，Yu Lei.An Efficient algorithm for constraint handling in combinatorial test generation［C］//IEEE Sixth International Conference on Software Testing，Veri?fication and Validation（ICST）.Luxembourg：IEEE Press，2013.242-251.

［15］Shiwei Gao，Binglei Du，Yaruo Jiang.An efficient algo?rithm for pairwise test case generation in presence of con?traints［C］//International Conference on Systems and In?formatics（ICSAI）.Shanghai：IEEEPress，2015.406-410.

［16］宋道遠(yuǎn).裝備軟件網(wǎng)絡(luò)接口測(cè)試自動(dòng)化研究［D］.武漢：海軍工程大學(xué)，2013：31-35.

SONG Daoyuan.Research of Equipment Software Net?work Interface Test Automation［D］.Wuhan：Navy Uni?versity of Engineering，2013：31-35.

A Pairw ise Test Suite A lgorithm Based on Correlation M atrix

XI Le BEN Kerong
（Department of Computer Engineering，Navy University of Engineering，Wuhan 430033）

TP311.5

10.3969/j.issn.1672-9722.2017.09.006

2017年4月14日，

2017年5月21日

國(guó)防基金《基于容錯(cuò)機(jī)制的面向服務(wù)可信支持技術(shù)研究》項(xiàng)目（編號(hào)：513150402）資助。

習(xí)樂(lè)，男，碩士研究生，研究方向：軟件質(zhì)量保證技術(shù)。賁可榮，教授，博士生導(dǎo)師，研究方向：軟件工程、人工智能。