梁 凡，宋曉秋

（中國航天科工集團(tuán)第二研究院706所，北京100039）

0 引 言

在軟件的功能測(cè)試過程中，很多軟件故障是由多個(gè)參數(shù)互相作用引起的。但是如果一個(gè)待測(cè)系統(tǒng)有N個(gè)不同的參數(shù)，每個(gè)參數(shù)有N1，N2……NK個(gè)可能的取值，那么根據(jù)全排列的方式可知，完全覆蓋所有的組合就需要個(gè)測(cè)試用例［1］。顯然，對(duì)于一般的大型待測(cè)系統(tǒng)而言，這個(gè)用例數(shù)量是不現(xiàn)實(shí)的。所以如何選取合適的參數(shù)組合構(gòu)成測(cè)試用例集是提高測(cè)試效率中極為關(guān)鍵的一步。

定義1 在一個(gè)待測(cè)系統(tǒng)的所有測(cè)試用例中，對(duì)于任意N個(gè)參數(shù)，這N個(gè)參數(shù)所組成的所有可能的組合都能被某個(gè)測(cè)試用例所覆蓋。則這種測(cè)試方式稱為N組合測(cè)試［2］。

Kuhn和Reilly分析了Mozilla瀏覽器的錯(cuò)誤報(bào)告記錄［3］，發(fā)現(xiàn)超過70%的軟件故障是由某兩個(gè)參數(shù)的取值組合引起的，而超過90%則是由某3個(gè)參數(shù)引起的。所以設(shè)計(jì)適當(dāng)?shù)姆椒ㄕ业揭粋€(gè)最小的測(cè)試用例集，使所有的參數(shù)配對(duì)都能被這個(gè)測(cè)試用例集所覆蓋［4］，能大大提高測(cè)試工作的效率。但是，研究表明要求得這樣的一個(gè)最小的集合是一個(gè) NPC （non－deterministic polynomial complete－NP 完全）問題，即它不存在一個(gè)多項(xiàng)式時(shí)間的算法［5］。所以，研究人員一直在致力于尋找各種多元配對(duì)組合測(cè)試的方法，以優(yōu)化用例集的生成。下面介紹幾種已經(jīng)被廣泛使用的算法。

1 二組合測(cè)試算法綜述

1.1 正交拉丁算法［6］

正交拉丁方是組合數(shù)學(xué)中的一個(gè)概念，這個(gè)方陣有一個(gè)特殊的性質(zhì)，即每個(gè)元素在每一行每一列均出現(xiàn)且只出現(xiàn)一次。而正交拉丁算法即是使用這種性質(zhì)來構(gòu)造兩兩組合覆蓋集，只需要計(jì)算出正交表，就可以直接產(chǎn)生測(cè)試用例集。所以這種方法最大的優(yōu)點(diǎn)是簡單，但是效率很低且測(cè)試用例易產(chǎn)生冗余［7］。而且對(duì)于正交表的構(gòu)造問題還有很多需要解決，例如混合型正交表。

1.2 AETG算法

基于正交拉丁方算法，D.M.Cohen和S.R.Datal等人提出了一種基于兩兩組合覆蓋的啟發(fā)式的測(cè)試用例生成方法 AETG （automatic efficient test－case generator）算法［8］。算法的主要思想是首先產(chǎn)生一組N個(gè)測(cè)試用例，然后利用貪心算法在這N個(gè) （一般為50個(gè)）測(cè)試用例中選擇能最大程度上覆蓋未被覆蓋的配對(duì)的那個(gè)用例加入到已生成的測(cè)試用例集中，重復(fù)上述步驟直到所有的兩兩組合都被覆蓋到［9］。這種方法的優(yōu)點(diǎn)是形成的測(cè)試用例相對(duì)冗余較少，但是算法執(zhí)行過程較為復(fù)雜，時(shí)間復(fù)雜度高［10］。

1.3 IPO算法

1998年，北卡羅來納大學(xué)的Y.Lei和K.C.Tai提出了一種基于參數(shù)順序的漸進(jìn)擴(kuò)充的兩兩配對(duì)組合測(cè)試用例生成方法IPO （in－parameter－order）［11］。算法首先以參數(shù)為對(duì)象，生成配對(duì)覆蓋所有可能的組合測(cè)試集T。然后逐個(gè)向測(cè)試集中添加參數(shù)，并通過擴(kuò)展算法覆蓋這個(gè)參數(shù)和當(dāng)前測(cè)試集T內(nèi)每個(gè)參數(shù)所能夠形成的所有組合，并使測(cè)試集保持最小，直到所有的參數(shù)都添加到測(cè)試集里［12］。這個(gè)過程分為水平擴(kuò)展和垂直擴(kuò)展兩個(gè)部分，水平擴(kuò)展是在測(cè)試用例集里添加一個(gè)新的參數(shù)，不產(chǎn)生新的測(cè)試用例的過程，垂直擴(kuò)展在水平擴(kuò)展之后，對(duì)仍然沒有被覆蓋的參數(shù)組合，生成新的用例覆蓋它們。IPO算法在時(shí)間復(fù)雜度上略優(yōu)于AETG算法，但是得到的用例集冗余度大于AETG方法［13］。

1.4 IPO算法與AETG算法的比較

AETG的方法由于在每次生成用例的時(shí)候都選擇那些能覆蓋最多未被覆蓋的兩兩組合，所以能很好的控制生成用例的冗余度［14］，但是不斷地遍歷可能的組合，使得這種方法的時(shí)間開銷大大增加。而IPO方法每次的迭代著眼于參數(shù)，而不是大量可能的組合，就使得從時(shí)間上明顯優(yōu)于AETG方法。但是對(duì)于用例全局上的掌控度顯然遜于AETG方法，也就使得它更容易產(chǎn)生不必要的用例［15］。

所以，本文首先將AETG方法的主要思想與IPO方法的不足之處結(jié)合起來，得到一個(gè)用例冗余度低于IPO方法但是算法復(fù)雜度低于AETG的算法。

2 改進(jìn)的IPO方法

首先，IPO算法在水平擴(kuò)展方面每次添加一個(gè)參數(shù)以覆蓋更多未被覆蓋的組合，但是待擴(kuò)展參數(shù)的順序和測(cè)試用例水平被擴(kuò)展的次序比較難以界定，其次測(cè)試用例集覆蓋的配對(duì)個(gè)數(shù)如何安排。這些都會(huì)在很大程度上影響結(jié)果。而AETG算法的結(jié)果優(yōu)于IPO算法，主要是因?yàn)樗鼘?duì)于參數(shù)配對(duì)的遍歷過程。例如如果某個(gè)待測(cè)系統(tǒng)有5個(gè)參數(shù)，每個(gè)參數(shù)均有3個(gè)取值，一步AETG迭代可能生成 （A1，B2，C1，D3，E2），但是一步IPO水平擴(kuò)展可能生成（A1，B2，C1，＿，＿）。所以，如何進(jìn)一步提高IPO算法每次水平擴(kuò)展在用例形成問題上的影響度就成為改進(jìn)IPO算法一個(gè)重要的方向。

2.1 優(yōu)化水平擴(kuò)展的方法

首先，給出一組結(jié)論：

結(jié)論一：如果一個(gè)待測(cè)系統(tǒng)有K個(gè)參數(shù)，每個(gè)參數(shù)有Vi個(gè)取值 （i＝1，2……K）。則如果要覆蓋所有可能的兩兩組合，則至少需要 （Vi×Vj）個(gè)測(cè)試用例 （其中Vi≥Vj≥ ｛Vn｜n∈ （1，2……i－1，i＋1……j－1，j＋1……k｝）。結(jié)論顯然成立。

結(jié)論二：改進(jìn)的IPO算法首先要選擇Ki和Kj的配對(duì)，如果選取Vi≥Vj≥ ｛Vn｜n∈ （1，2……i－1，i＋1……j－1，j＋1……k｝，則可以進(jìn)一步提高水平擴(kuò)展效率。簡單證明：任取 （Vn×Vm）＞ （Vi×Vj），由結(jié)論一可得至少需要 （Vi×Vj）個(gè)測(cè)試用例，所以若初始選取Kn和Km，則需要將更多的工作依賴于垂直擴(kuò)展階段，極大地降低了水平擴(kuò)展的效率。

結(jié)論三：在水平擴(kuò)展階段一次擴(kuò)展一個(gè)配對(duì)在大部分情況下要優(yōu)于一次擴(kuò)展一個(gè)參數(shù)或是一次擴(kuò)展3個(gè)或更多參數(shù)。且配對(duì)元素的選擇順序按Vi的降序排列。

證明：一個(gè)待測(cè)系統(tǒng)有K個(gè)參數(shù)，每個(gè)參數(shù)有Vi個(gè)取值 （i＝1，2……K）。初始選擇Vi和Vj的配對(duì) （Vi≥Vj≥Vm≥Vn≥Vp≥Vt，｛Vt｜t∈ （1，2……k）＆t≠i，j，m，n，p｝）。如果按一次擴(kuò)展一個(gè)參數(shù)的水平擴(kuò)展，下次要選擇配對(duì)的元素為Kn然后是Km依次類推，一次擴(kuò)展一對(duì)參數(shù)的水平擴(kuò)展下次擴(kuò)展Kn和Km的配對(duì)然后擴(kuò)展下一個(gè)取值在剩余參數(shù)中最大的兩個(gè)參數(shù)配對(duì)，若一次擴(kuò)展3個(gè)參數(shù)則擴(kuò)展Kn、Km和Kp然后擴(kuò)展下一個(gè)取值在剩余參數(shù)中最大的3個(gè)參數(shù)配對(duì)組合，一次擴(kuò)展更多的參數(shù)則不再贅述。

方法一：如果一次只擴(kuò)展一個(gè)參數(shù)，在將參數(shù)Kn添加到用例的時(shí)候，將Kn（1）～Kn（vn）全部填入之前，對(duì)于任意（Ki（x），Kj（y），Kn（z）） （x∈Vi，y∈Vj，z∈Vn）無需進(jìn)行配對(duì)冗余驗(yàn)證，因?yàn)镵n（z）存在且僅存在于 （Ki（x），Kj（y），Kn（z））。也就使無需進(jìn)行驗(yàn)證的用例為Vn個(gè)，第一次水平擴(kuò)展結(jié)束后需要進(jìn)行次比較。所以水平測(cè)試進(jìn)行結(jié)束后至少需要 （Vi×Vj－Vn）×2Vn次比較，所以水平測(cè)試進(jìn)行結(jié)束后至少需要次比較。但是在實(shí)際進(jìn)行參數(shù)擴(kuò)展的過程中，某幾個(gè)參數(shù)覆蓋相同大小的未被覆蓋的配對(duì)的可能性是非常大的。在發(fā)生這種情況的時(shí)候，應(yīng)該選擇哪一個(gè)參數(shù)是一個(gè)無法給出定論的問題。所以頻繁發(fā)生的盲目的參數(shù)選擇就容易帶來極大的配對(duì)冗余。

方法二：如果一次擴(kuò)展一個(gè)參數(shù)配對(duì)。第一次水平擴(kuò)展待選擇的參數(shù)對(duì)為Vn×Vm個(gè)，每次優(yōu)先選擇未被使用的參數(shù)對(duì)，如果對(duì)于 （Ki（x），Kj（y），Kn（z），Km（h）） （Ki（x），Kn（z）），（Ki（x），Km（h）），（Kj（y），Kn（z）），（Kn（z），Km（h））都是新生產(chǎn)的參數(shù)對(duì)，則選擇 （Kn（z），Km（h））加入，如果覆蓋了某些已經(jīng)形成的參數(shù)對(duì)，則繼續(xù)向下選擇，最后選擇覆蓋未被覆蓋配對(duì)最大的參數(shù)對(duì)加入。在比較理想的情況下，完成水平測(cè)試需要的操作數(shù)

對(duì)比兩種方法在較為理想的情況下需要進(jìn)行的操作數(shù)，對(duì)比結(jié)果見表1。

表1 方法一與方法二時(shí)間開銷對(duì)比

當(dāng)用例的參數(shù)數(shù)量和取值增加的時(shí)候，方法二對(duì)于方法一增加的時(shí)間開銷的維持在較小的整數(shù)倍，在現(xiàn)有的計(jì)算機(jī)硬件水平下，這個(gè)時(shí)間開銷完全可以接受。方法二雖然帶來了更大的時(shí)間開銷，但是從整體上來看一次擴(kuò)展兩個(gè)參數(shù)，則在選擇某個(gè)參數(shù)對(duì)是否應(yīng)該被擴(kuò)展的時(shí)候就比一次擴(kuò)展一個(gè)參數(shù)提供了更多的參考。例如有已生成的用例 （A1，B3，C2，D2）如果待擴(kuò)展E1，E2，F(xiàn)1，F(xiàn)2，如果 （A1，E1）（B3，E1） （C2，E1）； （A1，E2） （B3，E2）（C2，E2）；（A1，F(xiàn)1） （B3，F(xiàn)1） （C2，F(xiàn)1） （E1，F(xiàn)1）都已經(jīng)被覆蓋，若一次擴(kuò)展一個(gè)參數(shù)，此時(shí)選擇E1還是E2就是一個(gè)很大的問題，貪心算法在此并不能起到作用。但是如果一次擴(kuò)展兩個(gè)參數(shù)，毫無疑問現(xiàn)在應(yīng)該擴(kuò)展（E1，F(xiàn)2）。

方法三：若一次擴(kuò)展3個(gè)參數(shù)，首先，同時(shí)擴(kuò)展Kn、Km和Kp，待選擇的用例數(shù)為Vn×Vm×Vp，很可能大于Vi×Vj。如果出現(xiàn)這種情況，就只能將更多的工作寄托于垂直擴(kuò)展階段。極大地降低了水平擴(kuò)展的效率，所以方法三并不可取。

2.2 改進(jìn)的IPO算法描述

根據(jù)以上幾個(gè)結(jié)論，給出改進(jìn)的IPO算法的水平擴(kuò)展方法 （以下簡稱IPO＿I（improved IPO））：

（1）首先將待擴(kuò)展參數(shù)集按照取值數(shù)量進(jìn)行排序，即得到V1≥V2≥……≥Vk。然后生成V1和V2的全部配對(duì)。取代原有的隨機(jī)選取參數(shù)的形式。

（2）每次擴(kuò)展一個(gè)參數(shù)對(duì)，取代原有的一次擴(kuò)展一個(gè)參數(shù)的形式。

（3）每次優(yōu)先選擇未被使用的待擴(kuò)展配對(duì)，若不能產(chǎn)生新的覆蓋未被覆蓋的參數(shù)對(duì)時(shí)，再考慮擴(kuò)展已使用的配對(duì)。

（4）當(dāng)多組配對(duì)能覆蓋被覆蓋的參數(shù)對(duì)數(shù)量相同時(shí)，優(yōu)先選擇能覆蓋的配對(duì)中包含參數(shù)可選值多的那個(gè)參數(shù)的配對(duì)。

2.3 IPO＿I的算法概要設(shè)計(jì)與實(shí)驗(yàn)對(duì)比

改進(jìn)的IPO算法描述如圖1所示。

圖1 改進(jìn)的IPO算法描述

改進(jìn)的IPO＿I算法與傳統(tǒng)IPO算法實(shí)驗(yàn)對(duì)比見表2。

表2 IPO算法與IPO＿I算法實(shí)驗(yàn)結(jié)果對(duì)比

實(shí)驗(yàn)1：5個(gè)參數(shù)，其中2個(gè)參數(shù)有3個(gè)取值，3個(gè)參數(shù)有2個(gè)取值。

實(shí)驗(yàn)2：10個(gè)參數(shù)，其中1個(gè)參數(shù)有5個(gè)可選值，2個(gè)參數(shù)有4個(gè)可選值，3個(gè)參數(shù)有3個(gè)可選值，4個(gè)參數(shù)有2個(gè)可選值。

實(shí)驗(yàn)3：20個(gè)參數(shù)，其中所有參數(shù)都有2個(gè)取值。

實(shí)驗(yàn)4：18個(gè)參數(shù)，其中1個(gè)參數(shù)有9個(gè)取值，1個(gè)有10個(gè)取值，2個(gè)有8個(gè)取值，6個(gè)有4個(gè)取值，8個(gè)有2個(gè)取值。

2.4 IPO＿I算法分析

觀察實(shí)驗(yàn)得到的結(jié)果，改進(jìn)的IPO算法生成的測(cè)試用例在一定程度上優(yōu)于傳統(tǒng)的IPO算法。觀察IPO＿I算法水平擴(kuò)展階段的描述可以發(fā)現(xiàn)，當(dāng)測(cè)試用例某些參數(shù)的取值明顯多于剩余參數(shù)取值的時(shí)候，該算法可以最大程度上發(fā)揮它的作用，即首先，極大地減少了垂直擴(kuò)展階段的工作，其次在待擴(kuò)展配對(duì)的最終選擇上提供了更多的參考標(biāo)準(zhǔn)。但是，當(dāng)待測(cè)系統(tǒng)的參數(shù)取值相似時(shí)，改進(jìn)的IPO＿I算法并不能改善最終生成的用例集的冗余情況，相反，IPO＿I算法的時(shí)間開銷略大于傳統(tǒng)的IPO算法。

但是，觀察我們經(jīng)常使用的軟件，可以發(fā)現(xiàn)，很大一部分的軟件符合這種某幾個(gè)待測(cè)參數(shù)的取值明顯多于其它參數(shù)的情況。例如，如果我們注冊(cè)一個(gè)社交網(wǎng)站，網(wǎng)站也許期望將所有人按年齡，地域，性別進(jìn)行劃分，那么年齡和地域兩個(gè)參數(shù)有很多種取值組合，但是性別顯然只有兩種可能取值。所以，改進(jìn)的IPO＿I算法具有很大的實(shí)用性。

但是，我們觀察現(xiàn)有的測(cè)試用例生成算法，沒有一種方法可以保證幾乎避免測(cè)試用例的冗余。我們改善測(cè)試用例生成方法，只能從一定程度上去改善冗余。所以，下面本文討論一種精簡已生成測(cè)試用例集的方法，以進(jìn)一步減小測(cè)試用例集規(guī)模。

3 二組合測(cè)試用例集精簡算法

首先觀察我們使用不同的方法生成的測(cè)試用例集，它們有一個(gè)共同的特征，即測(cè)試用例集可以保證參數(shù)配對(duì)的全覆蓋。不論是AETG還是IPO算法，最終執(zhí)行結(jié)束的標(biāo)志都是參數(shù)配對(duì)集P已經(jīng)被測(cè)試用例集T全覆蓋。所以，基于這種思想，提出一種完全基于最終生成的測(cè)試用例集T的測(cè)試用例精簡方法。

算法描述：首先，觀察一組測(cè)試用例集 ｛（A1，B1，C1）， （A1，B2，C2）， （A2，B1，C2）， （A2，B2，C1），（A2，B2，C2）｝如果這個(gè)集合是一個(gè)具有3個(gè)參數(shù)且每個(gè)參數(shù)有2個(gè)取值的待測(cè)系統(tǒng)生成的二組合測(cè)試用例集。很容易發(fā)現(xiàn)其中（A2，B2，C2）這個(gè)用例是冗余的。因?yàn)榕鋵?duì) （A2，B2），（A2，C2），（B2，C2）都已經(jīng)被前4個(gè)用例覆蓋。觀察發(fā)現(xiàn)冗余用例的過程可以發(fā)現(xiàn)，A2，B2，C2每個(gè)參數(shù)作為配對(duì)的形式在其它的用例集中各出現(xiàn)了2次?；诖私o出一個(gè)判斷冗余用例的方法。

如果一個(gè)待測(cè)系統(tǒng)有K個(gè)參數(shù)，待測(cè)試用例集為T，其中T為一個(gè)由N×K個(gè)參數(shù)組成的矩陣。每一個(gè)用例由（（K1）x，（K2）y，…… （Ki）n…… （Kk）m）組成，那么一個(gè)用例中，配對(duì)數(shù)應(yīng)該為K× （K－1）／2。如果用另外一個(gè)矩陣存儲(chǔ)重復(fù)的配對(duì)，即如果一個(gè)用例為 （（K1）x，（K2）y，…… （Ki）n…… （Kk）m），其中（（K1）x，（Ki）n），（（K2）y，（Ki）n），（（K1）x，（Kk）m）這3個(gè)配對(duì)在其它用例里面出現(xiàn)過，則記這個(gè)用例的重復(fù)矩陣Q為 （即將重復(fù)出現(xiàn)的配對(duì)對(duì)應(yīng)的值置為1，其它為0）。

重復(fù)矩陣Q如圖2所示。

但是如果某兩個(gè)用例包含相同的參數(shù)個(gè)數(shù)大于2，則將對(duì)應(yīng)參數(shù)的所有兩兩組合配對(duì)在Q中的值全部置為1。即如果某個(gè)用例中3個(gè)參數(shù)與另一個(gè)用例中重復(fù)，則需要改變Q中3×2／2＝3行數(shù)值。每次改變矩陣的一行，應(yīng)該檢測(cè)矩陣中不能包含相同的兩行。如果某個(gè)用例對(duì)應(yīng)的重復(fù)矩陣Q的行數(shù)為K×（K－1）／2則說明這個(gè)用例中的每個(gè)配對(duì)都被其它用例覆蓋。

圖3給出算法描述。

圖2 重復(fù)矩陣Q

圖3 測(cè)試用例集精簡算法描述

精簡算法部分實(shí)驗(yàn)結(jié)果見表3。

表3 精簡算法部分實(shí)驗(yàn)結(jié)果

算法部分實(shí)驗(yàn)驗(yàn)證：

實(shí)驗(yàn)1：共100個(gè)參數(shù)，其中每個(gè)參數(shù)都有2種取值

實(shí)驗(yàn)2：共10個(gè)參數(shù)，每個(gè)參數(shù)有10個(gè)取值。

算法的時(shí)間復(fù)雜度為O（K2×N2），這個(gè)時(shí)間小于任何一個(gè)測(cè)試用例生成算法所需要的時(shí)間開銷。而且觀察結(jié)果可以發(fā)現(xiàn)，在用例生成之后進(jìn)行精簡，彌補(bǔ)了IPO＿I算法的薄弱部分。在測(cè)試用例生成之后進(jìn)行用例集精簡，是提高測(cè)試用例生成算法十分有意義的一個(gè)步驟。但是，也需要綜合考慮到精簡帶來的時(shí)間開銷，如果用例數(shù)量過多，而進(jìn)行一條用例的計(jì)算所需要的時(shí)間相對(duì)較短，那選擇精簡也許會(huì)得不償失。

4 結(jié)束語

本文首先討論了一種改進(jìn)的IPO算法，部分實(shí)驗(yàn)結(jié)果表明，該算法可以優(yōu)化一部分滿足特定條件的待測(cè)系統(tǒng)的測(cè)試用例生成結(jié)果。在我們?nèi)粘Ｉ钪?，有相?dāng)大的一部分軟件滿足這種某些參數(shù)取值個(gè)數(shù)遠(yuǎn)大于其它參數(shù)的情況。所以這種IPO＿I算法有一定的實(shí)用性，但是它也存在著一個(gè)很大的問題，就是時(shí)間復(fù)雜度高，雖然現(xiàn)在隨著計(jì)算機(jī)硬件日新月異的發(fā)展，這部分時(shí)間開銷可以被接受。但是難以保證它是否能承擔(dān)那些個(gè)別但是十分龐大的系統(tǒng)的測(cè)試用例生成工作。而且，任何一種測(cè)試用例集生成算法都不能保證100%不存在冗余用例。所以提出一種測(cè)試用例集精簡方法，單純著眼于已生成的結(jié)果 （因?yàn)闇y(cè)試用例集生成算法已經(jīng)保證了所有配對(duì)的全覆蓋），事實(shí)表明，方法時(shí)間空間開銷都在可以接受的范圍里。完成二組合測(cè)試用例集的生成在測(cè)試工作中只能是完成了第一步，對(duì)于如何定位產(chǎn)生失效的配對(duì)，以及N－組合測(cè)試用例集的生成仍然是需要去探索的過程。

［1］YAN Jun，ZHANG Jian.Combinatorial testing：Principles and methods ［J］.Journal of Software，2009，20 （6）：1393－1405（in Chinese）.［嚴(yán)俊，張健.組合測(cè)試：原理與方法［J］.軟件學(xué)報(bào)，2009，20 （6）：1393－1405.］

［2］WANG Ziyuan，XU Baowen，NIE Changhai.Survey of combinatorial test generation ［J］.Journal of Frontiers of Computer Science and Technology，2008，2 （6）：571－588 （in Chinese）.［王子元，徐寶文，聶長海.組合測(cè)試用例生成技術(shù)［J］.計(jì)算機(jī)科學(xué)與探索，2008，2 （6）：571－588.］

［3］Kulm DR，Reilly MJ.An investigation of the applicability of design of experiments to software testing ［C］／／Caulfield M.Proc ofthe Annual NASA／IEEE Software Engineering Workshop （SEW）.Los Alamitos：IEEE Press，2002：91－95.

［4］Myra B Cohen，Matthew B Dwyer，Jiang Fanshi.Constructing interaction test suites for highly－configurable systems in the presence of constraints：A greedy approach ［J］.IEEE Transactions on Software Engineering，2008，34 （5）：633－650.

［5］Lei Y，Tai K C.In－parameter－order：A test generation strategy for pairwise testing ［C］／／The 3rd IEEE High－Assurance Systems Engineering Symposium，1998：254－261.

［6］Williams A W，Probert R L.A practical strategy for testing pair－wise coverage of network interfaces ［C］／／White Plains NY USA：Proc 7th Internat Symp Software Reliability Engineer，1997：246－254.

［7］White LJ.Regression testing of GUI event interactions ［C］／／Washington：The International Conference on Software Maintenance，2007：350－358.

［8］Colboum CJ，Cohen MB，Bryce RC.A deterministic density algorithm for pairwise interaction ［C］／／Proceeding of the International Conference on Software Engineering，2004：345－352.

［9］CHEN Xiang，GU Qing，WANG Xinping，et al.Research advances in interaction testing ［J］.Computer Science，2010，37 （3）：1－5 （in Chinese）.［陳翔，顧慶，王新平，等.組合測(cè)試研究進(jìn)展 ［J］.計(jì)算機(jī)科學(xué)，2010，37 （3）：1－5.］

［10］WU Yanjie.Analyses and implementing of algorithms for pairwise testing ［D］.Wuhan：Huazhong University of Science Technology，2008（in Chinese）.［吳彥杰.多元配對(duì)組合測(cè)試的算法研究與實(shí)現(xiàn) ［D］.武漢：華中科技大學(xué)，2008.］

［11］Lei Y，Tai K C.In parameter order：A test generation strategy for sairwise testing ［R］.Technical Report TR－2001－03.Raleigh，North Carolina：Dept of Computer Science，North Carolina State University，2001.

［12］Lei Y，Kacher R，Kuhn D R，et al.IPOG：A general strategy for T－way software testing ［C］／／Proceedings of 14th Annual IEEE International Conference and Workshops on the Engineering of Computer－Based Systems，2007：549－556.

［13］HUANG Long，YANG Yuhang，LI Hu.Research on algorithm of parameter pairwise and n－way combinatorial coverage ［J］.Chinese Journal of Computers，2012，35 （2）：257－269 （in Chinese）.［黃隴，楊宇航，李虎.參數(shù)配對(duì)及n－way組合覆蓋算法研究 ［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35 （2）：257－269.］

［14］Ren Zhengping，Huang Song，Wan Hui，et al.Research on testing technology of command and control information system［C］／／16th Information－based theory Science Workshop，2009.

［15］Hui Zhanwei，Huang Song，Su Shihan，et al.Research on generation methods of pair－wise covering combinatorial test cases ［C］／／Asia－Pacific Conference on Information Theory，2010：264－267.