基于關聯矩陣的兩兩組合測試算法

習 樂 賁可榮

基于關聯矩陣的兩兩組合測試算法

習 樂 賁可榮

（海軍工程大學計算機工程系 武漢 430033）

組合測試是軟件黑盒測試中的一種常用方法，能有效檢測軟件系統中由各個因素相互作用所引發的軟件故障。基于參數順序的約束滿足算法IPO-SAT是一種常用的組合測試用例生成算法，該算法約束控制能力突出，能生成精簡的兩兩組合測試用例集，但其計算過程頻繁調用約束求解器，導致較多的時間開銷。針對該問題，論文提出一種基于關聯矩陣的兩兩組合測試改進算法MIPO，采取將約束信息存儲于關聯矩陣中的方式來避免調用約束求解器，以減少測試用例生成過程中的整體時間。針對5組不同的參數組合進行實驗，結果表明，改進后的算法與IPO-SAT算法相比，生成兩兩組合測試用例集的時間可節省90%以上。

約束控制；測試用例生成；關聯矩陣；組合測試

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 引言

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

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

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

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

2 組合測試相關知識

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

2.1 關聯矩陣

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

圖1 無向圖及關聯矩陣

圖2 XYZ對應的初始關聯矩陣

2.2 約束條件

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

表1 設備和瀏覽器的組合

最常見的兩種約束類型是參數組合中的依賴和沖突［15］：

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

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

對于參數間的依賴約束和沖突約束，這些約束條件都可以用禁止出現的組合的來表示。

2.3 IPO算法

IPO（In-Parameter-Order）是一種貪心算法，常被用來求解兩兩組合測試用例集。IPO算法先求得前兩個參數的完全組合，在此基礎上，不斷將后續的參數添加到測試用例集中。在添加參數的過程中，需要保證后續每一個參數的取值與之前所有參數取值的兩兩組合，當最后一個參數完成時，則算法結束。

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

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

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

3）為未覆蓋的組合添加新用例。由于還剩4個組合未覆蓋，所以還需要添加新的測試用例來達到對所有組合的覆蓋。對于a1c3，a2c2，可以添加(a1，_，c3)，(a2，_，c2)。注意到，當 (a1，_，c3)填充成(a1，b2，c3)時，可以覆蓋 b2c3。同理 (a2，b1，c2)可以覆蓋b1c2。此時沒有未被覆蓋的組合，算法結束。

3 兩兩組合測試改進算法M IPO

如何提高算法的約束控制能力，減少計算時間，生成更小的測試用例集是組合測試研究的重點。在兩兩組合測試中，各種算法的約束控制能力已經滿足大部分需要，但是算法的求解時間還存在優化的空間。

3.1 問題分析及解決思路

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

3.2 基于關聯矩陣的M IPO算法

在關聯矩陣的基礎上，擴充矩陣元素的屬性，將約束控制信息加入其中，使得每個元素包含兩個屬性：覆蓋信息F和約束信息Y。用Cell［a，b］表示取值a和取值b在關聯矩陣中對應的元素，Cell［end，b］表示b所在列最后一行的元素。關聯矩陣的具體含義如表2所示。

表2 關聯矩陣擴展后的屬性和含義

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

算法1 基于關聯矩陣的IPO組合測試算法

輸入：參數 P1，P2，P3，…，Pm，及對應的候選輸入個數 n1，n2，

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

1.生成一個關聯矩陣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. 調用子算法ADDPARA（T，M，Pi）；//在T中添加參數Pi

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

23.End For

算法1主要生成前兩個參數的兩兩組合，后續參數尚未加入測試用例集T中，所以針對每個后續參數Pi，都要調用算法1.1來將T中的每個用例中填入Pi的取值。

算法1.1 ADDPARA（T，M，Pi）

輸入：已生成的測試用例集T及對應的關聯矩陣M，參數Pi。

輸出：更新后的測試用例集T和關聯矩陣M。

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

1.For each t∈T do

2. For v：=v1to vmdo

4. End for

5.根據Cell［end，Pi.v］.F對v1，v2，v3，…，vni進行增序排序，

記錄在數組A［］中；

6. For k：=1 to nido

7. 將A［k］對應的取值Pi.v加入到t中對應參數位置，并在關聯矩陣中設置對應的覆蓋信息；

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中刪除，并在關聯矩陣中更新對應的覆蓋信息；

14. Break；

15. End if

16. End for

17. End if

18.End for

19.End for

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

算法1.2 ADDCASE（T，M，Pi）

輸入：已生成的測試用例集T及對應的關聯矩陣M，參數Pi。

輸出：更新后的測試用例集T和關聯矩陣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對應的位置；

6. 設置關聯矩陣中對應的覆蓋信息；

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，更新關聯矩陣的覆蓋信息；

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’，分別設置Ph，Pi為w，v；

19. 更新關聯矩陣的覆蓋信息；

20.End if

21.End for

22.For each t∈T do

23.If t中參數Pj為空then

24. For v：=v1to vnjdo

26. End for

27. 根據 Cell［end，Pj.v］.F對v1，v2，v3，…，vnj進行增序排序，記錄在數組A［］中；

28. For k：=1 to njdo

29. 將A［k］對應的Pj.v加入到t中Pj對應的位置，并在關聯矩陣中設置對應的覆蓋信息；

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中刪除，并更新關聯矩陣中對應的覆蓋信息；

36. Break；

37. End if

38. End for

39. End if

40. End for

41. End if

42.End for

算法1中，首先構建關聯矩陣M并初始化，然后將所有的約束條件添加到M中。根據取值個數最多的兩個參數，進行完全組合，添加到測試用例表T中，并更新M中的覆蓋信息。根據覆蓋信息和約束信息，檢查T中組合的合法性，對于不合法的組合，從T中刪除并清除M中對應的覆蓋信息。

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

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

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

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

4 實驗

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

表3 航海參數及離散取值情況

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

表4 MIPO與IPO-SAT生成測試用例數量和時間

由表4中的實驗結果看出，兩種測試用例生成算法生成用例規模相當，但是MIPO算法生成時間遠小于IPO-SAT算法。為了充分比較兩種算法在生成用例規模和時間開銷上的差異，本文補充了不同的對比實驗，包括參數個數都為6個時，參數取值分別為20個、15個的情況以及參數的取值個數都為20個，參數數量分別為5個、7個的情況，分別記為ST1、ST2、ST3、ST4。具體的參數配置情況如表5所示。

表5 4組對比試驗參數配置情況

分別使用IPO-SAT程序和MIPO程序來生成ST1、ST2、ST3、ST4的測試用例集，得到生成的測試用例數量以及所花費的時間，如表6所示。

表6 生成用例時間對比

從表6可以看出，在同樣的輸入參數情況下，MIPO算法在生成兩兩組合測試用例時，比IPO-SAT算法花費的時間減少90%以上。當參數個數不變時，取值個數增加，IPO-SAT算法的執行時間急劇增加，而MIPO算法的執行時間增加緩慢。當參數取值個數不變時，參數個數增加時，IPO-SAT算法的執行時間急劇增加，而MIPO算法的執行時間增加緩慢。實驗結果表明，MIPO算法相比IPO-SAT，生成測試用例集的時間大幅減少，在參數增多的情況下，時間上的優勢更為突出。

通過實驗可以看出，MIPO與IPO-SAT相比，能夠生成大小相當的測試用例集，能夠在更快的時間內計算完成，計算效率更高。改進算法在求解時間上的優勢主要在于MIPO不調用約束求解器，節省了大量的求解時間。但是需要付出的代價是犧牲了約束求解器的通用性，關聯矩陣只能處理兩個參數之間的約束問題。

5 結語

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

［1］陳翔，顧慶，王新平，等.組合測試研究進展［J］.計算機科學，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策略的可變力度組合測試用例生成方法［J］.計算機學報，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］宋道遠.裝備軟件網絡接口測試自動化研究［D］.武漢：海軍工程大學，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日

國防基金《基于容錯機制的面向服務可信支持技術研究》項目（編號：513150402）資助。

習樂，男，碩士研究生，研究方向：軟件質量保證技術。賁可榮，教授，博士生導師，研究方向：軟件工程、人工智能。