梁 凡，宋曉秋

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

0 引 言

在軟件的測試工作中，常常會遇到某些軟件失效是由多個參數(shù)互相作用引發(fā)的情況。事實上，大約70%的軟件失效是由一個或2個參數(shù)作用引起的［1］。因此兩兩組合測試就成為了軟件測試中一種實施性較強同時又比較有效的方法［2］。但是對于一個由K 個參數(shù)構(gòu)成的系統(tǒng)，每個參數(shù)的取值為V ［i］（i＝1，2……k），要覆蓋所有可能的參數(shù)取值組合，就需要個測試用例［3］，顯然這個測試用例的規(guī)模不符合實際。所以，如何取得一個能覆蓋所有配對的最小的測試用例集就成為兩兩組合測試研究中最重要的問題［4］。但是，研究結(jié)果表明生成這樣一個最小的測試用例集是一個NPC 問題，即不存在多項式時間的解法［5］，所以研究的目標就成為尋找一個盡可能小的測試用例集去覆蓋所有可能的配對。

1 兩兩組合測試算法簡介

1.1 正交拉丁算法簡介

早在1985年，就已經(jīng)有學者提出了正交拉丁算法［6］，將正交拉丁方的特性用于生成多元輸入情況下的測試用例。但是在實際工作中，大部分的待測系統(tǒng)都不能滿足拉丁方的數(shù)學特性，導致正交表構(gòu)造困難，從而很難生成理想的測試用例集。近些年來，許多學者以正交拉丁算法為基礎，提出了一些改進的算法。比較有代表性的有加拿大渥太華大學的A.W.Williams提出的Williams算法，日本的Noritaka Kobayashi提出的Kobayashi算法等［7］。這些算法存在相同的問題，即構(gòu)思巧妙，但是實用性不強。

1.2 AETG 算法簡介

1997年，貝爾實驗室的Cohen和Dalal提出了AETG方法，算法的主要思想是首先按貪心算法生成一定數(shù)量N個測試用例，然后從這N 個測試用例中選擇一個能最多覆蓋未覆蓋配對集合中參數(shù)對的用例，將這個用例添加進已經(jīng)形成的測試用例集T 中［8］。從算法的執(zhí)行過程不難發(fā)現(xiàn)，每次產(chǎn)生的N 個待選擇測試用例的差別造成了算法結(jié)果的差別。所以這也是AETG 算法能進行改進的主要部分。

1.3 IPO 算法簡介

1998年，北卡羅來納大學的Y.Lei和K.C.Tai提出了一種基于參數(shù)順序的漸進擴充的兩兩配對組合測試用例生成方法IPO （in－parameter－order）［9］。算 法 首 先 以 參 數(shù) 為 對象，生成配對覆蓋所有可能的組合測試集T，這個過程稱為水平擴展。然后逐個向測試集中添加參數(shù)，并通過擴展算法覆蓋這個參數(shù)和當前測試集T 內(nèi)每個參數(shù)所能夠形成的所有組合，并使測試集保持最小，直到所有的參數(shù)都添加到測試集里，這個過程稱為垂直擴展。

1.4 各種算法比較

正交拉丁算法以及所有以正交拉丁算法為基礎的算法存在共同的缺陷，即對于能夠構(gòu)造正交表的待測系統(tǒng)而言，算法簡單有效，但是大部分的待測系統(tǒng)不能滿足這樣的要求，這就使得這類算法存在適應面窄的問題［10］。AETG 算法每次生成一個測試用例的時候都能在當前可選擇的范圍里選擇那個能覆蓋最多未覆蓋配對的用例，但是一次生成很多條測試用例待選擇，不斷地遍歷未被覆蓋的配對集合，使得AETG 算法的時間開銷大大增加［11］。而IPO 算法每次生成一個測試用例，這個測試用例保證能添加進測試用例集，使得每次遍歷的效率很高。但是從覆蓋盡可能多的配對的角度看，一次生成一個測試用例明顯不如一次生成一些測試用例然后選取最優(yōu)的那個用例［12］。所以，AETG 算法最大的優(yōu)點是能得到更小的測試用例集而IPO 算法最大的優(yōu)點是能花費更少的時間。

當今的硬件水平下，執(zhí)行用例生成算法的時間是微不足道的。實驗結(jié)果表明，對于一個由100 個參數(shù)，每個參數(shù)有4個取值組成的待測系統(tǒng)而言，在普通家用電腦上利用AETG 算法生成測試用例集需要花費大約260s的時間。這個時間與測試人員進行一個用例的輸入，測試與分析所需要花費的時間對比起來，是微不足道的。所以，如何在合理的時間內(nèi)得到盡可能小的測試用例集就成了組合測試問題上最需要解決的問題。

綜上所述，從實際工程應用的角度來考慮，AETG 算法比IPO 算法更加實用。下面給出一種改進的AETG 算法，稱為AETG＿I算法 （AETG improved）。

2 基于AETG 算法的改進方法

2.1 AETG 算法描述：

如果測試用例集T 中已經(jīng)包含了用例t1，t2……ti，下面給出生成ti＋1的方法：

（1）首先選取一個參數(shù)Fi，且Fi的值Vfi在未覆蓋配對集合UC （uncovered）中出現(xiàn)的次數(shù)最多。

（2）令F1＝Fi，然后對剩余的參數(shù)任意排序，得到任意的F2，F(xiàn)3……Fn。

（3）對于任意排序得到的參數(shù)，按順序選擇其參數(shù)值，如果本次應選取的參數(shù)是Fi，則計算Fi的所有參數(shù)值，選擇與已形成的F1，F(xiàn)2……Fi－1的各個值構(gòu)成的配對在UC中出現(xiàn)最多的那個參數(shù)值，將其添加進已形成的參數(shù)組中，接著再用相同的方法擴展Fi＋1。

重復以上3個步驟N 次，其中N 為某個人為設定的數(shù)量，產(chǎn)生N 個待選擇的測試用例。

當已經(jīng)得到N 個測試用例之后，從這N 個測試用例中選擇能覆蓋UC 中最多未被覆蓋的配對的那條用例，并將其添加進T。

看起來，當N 越大的時候每次選取的那個測試用例就越能接近最優(yōu)解，但是N 值過大會極大地增加算法所需要的時間和空間開銷。針對這個問題，Cohen和Dalal做了很多次實驗發(fā)現(xiàn)N＝50的時候，N 值的繼續(xù)增大并沒有明顯的減少測試用例集的大小，所以可以取N＝50。

觀察AETG 執(zhí)行的過程不難發(fā)現(xiàn)，算法的第2步，即任意排序得到待擴展的參數(shù)序列隨機性很大，而這種隨機性很容易冗余。舉一個例子：某個待測系統(tǒng)有4 個參數(shù)，AETG 方法進行到某步時，UC＝ ｛（A1，D1），（A1，B1），（A1，D2）， （B1，D1）， （A1，B2）， （D1，C2）， （A2，C2）｝，按照AETG 方法，首先擴展A1，如果隨機形成的參數(shù)擴展順序為ACDB，則生成的測試用例為 （A1，C1，D1，B1），覆蓋了UC中3個配對 （A1，D1），（B1，D1），（A1，B1）。但是如果測試用例為 （A1，D1，B1，C2）則可以覆蓋UC中4 個配對 （A1，D1）， （A1，B1）， （B1，D1），（C2，D1）。這種差異主要是由AETG 方法隨機排列參數(shù)的自由性所帶來的。雖然AETG 方法要將這個生成測試用例的步驟執(zhí)行50次，可以在很大程度上減少因為這種參數(shù)順序的不確定性帶來的影響。但是如果一個系統(tǒng)有6個或以上的參數(shù)，除去已經(jīng)選擇的F1，剩余參數(shù)的全排列有遠遠大于50種可能性。所以如何有效的改善第2個步驟就成為優(yōu)化AETG 算法的關鍵。

2.2 AETG 算法的改進

改進的AETG 算法 （AETG improved，AETG＿I算法）主要思想是讓每個參數(shù)的選擇均采用與第1個參數(shù)相似的方法，即按照參數(shù)在UC 中出現(xiàn)的次數(shù)差異決定參數(shù)的選擇順序。同時對于出現(xiàn)次數(shù)相同的那些參數(shù)，根據(jù)其某些特點賦予不同的優(yōu)先級，決定其排列順序。具體改進分為兩部分。

2.2.1 AETG＿I算法改進的第1部分

（1）首先選取一個參數(shù)Fi，且Fi的值Vfi在未覆蓋配對集合UC中出現(xiàn)的次數(shù)最多。

（2）令F1＝Fi，然后對剩余的參數(shù)按照其V 在UC 中出現(xiàn)的次數(shù)的不同，得到按Vi出現(xiàn)次數(shù)排序后的F2，F(xiàn)3……Fn。

但是在實際的測試用例生成過程中，可能存在某2個或某些參數(shù)其值在UC 中出現(xiàn)的次數(shù)相同。例如如果一個待測系統(tǒng)共有10個參數(shù)，每個參數(shù)有2個取值，如果第1個生成的測試用例是 （A1，B1，C1，D1，E1，F(xiàn)1，G1，H1，I1，J1）。當生成第2個測試用例時每個參數(shù)在UC 中出現(xiàn)的次數(shù)都是一樣的。發(fā)生這種情況時，需要讓每個取值個數(shù)相同的參數(shù)都能在相同重要的位置出現(xiàn)一次。所以，在選擇排序的時候，需要再增加約束條件。例如：UC＝｛（A3，B2），（A2，B2），（A1，B3），（A1，B4），（B3，C2），（A1，C2），（A1，D2）， （B2，C2）｝，如果按照目前的選擇方法，首選A 或B，如果首選B，第1次生成的測試用例為（B2，A2，C2，D2）覆蓋了UC 中的配對為 ｛（A2，B2），（B2，C2）｝，如果首選A，則生成的測試用例為 （A1，B3，C2，D2）覆蓋了UC 中的配對為 ｛（A1，B3），（B3，C2），（A1，C1），（A1，D2）｝。顯然選擇第1次擴展A 更加合適，這主要是因為參數(shù)A 中的A1在UC中出現(xiàn)的次數(shù)占據(jù)絕對優(yōu)勢。所以當有2個或更多的參數(shù)其值在UC 中出現(xiàn)的次數(shù)相同時，應該優(yōu)先選擇包含某個出現(xiàn)次數(shù)絕對多的取值的那個參數(shù)。

下面舉例說明這種選擇的方法：

如果某個待測系統(tǒng)有5個參數(shù)A，B，C，D，E，每個參數(shù)各有2種取值。當前的UC是 ｛（A1，B2），（A2，B2）（A1，C2），（A1，D1），（A1，D2），（A1，E2），（B1，C2），（B2，D1），（B2，D2），（B1，E2），（C1，D2），（C2，D1），（C2，E1）｝。觀察UC，其中A1出現(xiàn)5 次，A2出現(xiàn)1 次。B1出 現(xiàn)2次，B2出 現(xiàn)4 次。C1出 現(xiàn)1 次，C2出 現(xiàn)4 次。D1出 現(xiàn)3次，D2出 現(xiàn)3 次。E1出 現(xiàn)1 次，E2出 現(xiàn)2 次。其中A，B，D 這3個參數(shù)在UC 中出現(xiàn)的次數(shù)相同都是6次，但是A1出現(xiàn)了5次，B2出現(xiàn)了4次，D1和D2都是出現(xiàn)了3次。所以第1次生成的參數(shù)排序為：A，B，D，C，E。然而需要將A，B，D 在相同重要的位置都出現(xiàn)一次，但是這3個參數(shù)本身按照其出現(xiàn)次數(shù)最多的取值個數(shù)不同而本身存在選擇上的重要性差距。所以還需要生成參數(shù)順序為：B，A，D，C，E和D，A，B，C，E。

綜上，改進的第 （2）步描述為：

如果參數(shù)X，Y，Z 在UC 中出現(xiàn)的次數(shù)相同，且｜Xi｜＞｜Yj｜＞｜Zk｜ （｜Xi｜表示Xi在UC 中出現(xiàn)的次數(shù)）。則應該優(yōu)先選擇Xi進行擴展。為了保證每個在UC中出現(xiàn)次數(shù)相同的參數(shù)都能在同樣重要的位置出現(xiàn)一次，同時需要兼顧每個參數(shù)由于出現(xiàn)次數(shù)最多的取值所帶來的優(yōu)先級問題。即每次優(yōu)先選擇一個參數(shù)進行擴展，但是剩余參數(shù)必須保證按出現(xiàn)次數(shù)最多的那個取值的數(shù)量排序，需要生成 （＿， ＿，...，X，Y，Z， ＿...）， （＿， ＿，...，Y，X，Z， ＿...），（＿， ＿，...，Z，X，Y， ＿...）。同樣的，在之后的每一步操作中如果存在2個或多于2個的參數(shù)在UC中出現(xiàn)的次數(shù)相同時，都選擇同樣的方法。

（3）第3步與原方法大致相同，但是原AETG 方法在進行參數(shù)值選擇時采用的是向前對比的方法，這種方法存在一個問題，例如某個待測系統(tǒng)有4 個參數(shù)，每個參數(shù)有3個取值，生成某個測試用例時參數(shù)擴展順序定為ABCD，且 首 先 選 取 了A1，那 么 如 果 （A1，B1），（A1，B2），（A1，B3）在UC 中都存在，這時如何選取B的取值就存在很大的問題。所以將第3步修改為向前，向上對比。即此時對比B1，B2，B3在UC 中出現(xiàn)的次數(shù)，如果B1出現(xiàn)5次，B2出現(xiàn)4 次，B3出現(xiàn)6 次，選擇B3加入。

AETG＿I算法的第3步可以描述為，優(yōu)先選擇與前面參數(shù)能覆蓋最多UC 中的配對的那個參數(shù)值加入，如果存在某幾個參數(shù)值與前面的取值組成的配對在UC 中出現(xiàn)的次數(shù)相同，則優(yōu)先選取在UC 中出現(xiàn)次數(shù)最多的那個參數(shù)值加入。

2.2.2 AETG＿I算法改進的第2部分

在最初的AETG 方法中，需要生成50個待選擇的參數(shù)序列。在改進的方法中，將參數(shù)排序后避免了原來方法的盲目性，也就可以適當?shù)臏p少操作進行的次數(shù)。如果｜A｜＝｜B｜＝｜C｜，｜G｜＝｜H｜＝｜J｜＝｜K｜，那么在進行參數(shù)選擇的時候，A，B，C 需要出現(xiàn)在相同的位置，那就至少需要3 次，G，H，J，K 至少需要4 次，則在這種情況下就至少需要12個測試用例。在用例形成的開始階段，各個參數(shù)的不同取值使用程度相差不大，這時就會導致測試用例的數(shù)量可能會隨著參數(shù)數(shù)量的增加或者取值的增加遠遠大于50，而進行的幾組實驗證明，將生成的測試用例數(shù)量上限定義為50已經(jīng)可以得到非常理想的結(jié)果。所以當計算出來的重復步驟大于50 時使用傳統(tǒng)的AETG 方法，即將第1部分第2步生成的參數(shù)序列上限設為50，當用例集形成后期，各個參數(shù)之間差別較大，測試用例數(shù)量很難超過50。

所以AETG＿I算法的第2部分即迭代次數(shù)定義為：

如果在UC中存在與｜X｜出現(xiàn)次數(shù)相同的參數(shù)n1個，與｜Y｜相同的n2個……與｜Z｜相同的ni個。則需要的迭代次數(shù)為N＝n1×n2×……×ni次。如果N≥50，則迭代50次，如果N≤50，則迭代N 次。

2.3 改進的AETG 算法描述

下面給出改進的AETG 算法的算法描述，如圖1所示。

2.4 AETG＿I算法分析

2.4.1 間復雜度分析

因為改進后的方法迭代次數(shù)在用例生成工作的后期會越來越小，所以新方法在時間復雜度上根據(jù)待測系統(tǒng)的不同會不同程度的小于原AETG 方法。尤其是當參數(shù)的取值每個之間都存在差異，也就是參數(shù)取值情況參差不齊的時候，算法能很容易的找到每次待擴展的參數(shù)順序，而不是像傳統(tǒng)的AETG 方法那樣必須取50種排序，這種情況下就更能縮短算法需要的時間。

圖1 AETG＿I算法描述

對于任意一個有K 個參數(shù)的待測系統(tǒng)而言，符合兩兩組合測試條件的測試用例集規(guī)模上界為－log（k（k－1）d2／2）／log（1－1／d2）＋1 ，其中 （d＝max （V ［i］，i＝1，2…k），V ［i］為每個參數(shù)的取值個數(shù)）［13］。每條用例包含的配對數(shù)為k× （k－1）／2，每確定一個參數(shù)取值平均需要遍歷UC的次數(shù)為k／2次，UC的大小為d2×k× （k－1）／2。對于傳統(tǒng)的AETG 算法來講，當參數(shù)數(shù)量超過6（5！＝120）時，AETG 算法每一次都必須取到50 個測試用例。所以AETG 算法的時間復雜度上限為

其中當k≥6時，C＝50。但是對于AETG＿I算法，C 上限為50，下面給出一組實驗說明，實驗輸入?yún)?shù)為13個，每個參數(shù)取值為3個。

AETG＿I算法與AETG 算法復雜度比較見表1。

從上述實驗可以看到，對于AETG＿I算法，隨著已經(jīng)生成的測試用例數(shù)不斷地增加，其每確定一個測試用例所需要生成的帶選擇用例數(shù)就會越來越少。對比AETG 算法每次都需要生成50 個待選擇測試用例，AETG＿I算法在時間復雜度上確定得到了很大的改進。

表1 AETG＿I算法與AETG 算法復雜度比較

2.4.2 結(jié)果分析

下面選取幾組實驗對比改進后的算法與原AETG 算法，見表2。

表2 AETG＿I算法與AETG 算法結(jié)果對比

其中：

實驗方案1：4個參數(shù)，每個參數(shù)都是3個取值。

實驗方案2：5個參數(shù)，每個參數(shù)都是6個取值。

實驗方案3：8個參數(shù)，其中2 個參數(shù)是3 個取值，2個參數(shù)是5個取值，3個參數(shù)是4個取值，1個參數(shù)是2個取值。

實驗方案4：13個參數(shù)，每個參數(shù)都是3個取值。

實驗方案5：21個參數(shù)，其中5個參數(shù)是2個取值，4個參數(shù)是4個取值，1個參數(shù)是5個取值，6個參數(shù)是3個取值，5個參數(shù)是3個取值。

觀察以上實驗情況，改進后的AETG 方法對比原方法在生成用例集的大小上也有很大的改進。而且觀察不同參數(shù)選擇情況可以發(fā)現(xiàn)，當參數(shù)的數(shù)量越來越多時，新的AETG 方法更能體現(xiàn)其優(yōu)越性。

3 結(jié)束語

傳統(tǒng)的AETG 算法弊端比較明顯，即參數(shù)選取的過程隨機性很大。將迭代次數(shù)定為50對于一些小型的待測系統(tǒng)而言，能夠取得不錯的結(jié)果。但是現(xiàn)在隨著軟件系統(tǒng)的日益龐大，輸入?yún)?shù)的數(shù)量和取值也隨著越來越多。在實際的測試工作中，執(zhí)行與分析一個測試用例的人員開銷要遠遠比生成測試用例所需要的時間寶貴。所以，如何能在一個合理的時間內(nèi)得到盡可能小的兩兩組合測試用例集才是組合測試問題的瓶頸。本文針對AETG 算法的這個缺陷進行了改進，將原來無序的參數(shù)選擇過程改為按照參數(shù)未被覆蓋的取值個數(shù)綜合起來決定參數(shù)的選擇順序。并進行了幾組實驗驗證了改進的算法確實能夠大幅度減少測試用例集的規(guī)模，尤其是當參數(shù)的取值逐漸增加時，改進后的算法優(yōu)勢更加明顯。當然，完成兩兩組合測試用例集的生成只是組合測試工作的第1步，如何快速的定位導致軟件失效的配對，以及更多元的配對組合測試用例集生成問題仍然是今后需要重點研究的方向。

［1］Maity S，Nayak A.Improved test generation algorithms for pair－wise testing ［C］／／16th IEEE International Symposium on Software Reliability Engineering，2005：235－244.

［2］ZHA Rijun，ZHANG Deping，NIE Changhai，et al.Test data generation algorithm of combinatorial testing and comparison based on cross－entropy and particle swarm optimization method［J］.Chinese Journal of Computers，2010，33 （10）：1896－1908 （in Chinese）. ［査日軍，張德平，聶長海，等.組合測試數(shù)據(jù)生成的交叉熵與粒子群算法及比較 ［J］.計算機學報，2010，33 （10）：1896－1908.］

［3］YAN Jun，ZHANG Jian.Combinatorial testing：Principles and methods［J］.Journal of Software，2009，20 （6）：1393－1405 （in Chinese）. ［嚴俊，張健.組合測試：原理與方法［J］.軟件學報，2009，20 （6）：1393－1405.］

［4］Myra B Cohen，Matthew B Dwyer，Shi Jiangfan.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］WU Yanjie.Research and implementation of algorithm for pairwise testing ［D］.Wuhan：Huazhong University of Science and Technology，2008 （in Chinese）.［吳彥杰.多元配對組合測試的算法研究與實現(xiàn) ［D］.武漢：華中科技大學，2008.］

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

［7］ZHOU Wujie，ZHANG Deping，XU Baowen.An adaptive algorithm of locating fault interactions based combinatorial testing［J］.Chinese Journal of Computers，2011，34 （8）：1509－1516 （in Chinese）. ［周吳杰，張德平，徐寶文.基于組合測試的軟件故障定位的自適應算法 ［J］.計算機學報，2011，34（8）：1509－1516.］

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

［9］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.

［10］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－268（in Chinese）.［黃隴，楊宇航，李虎.參數(shù)配對及n－way組合 覆 蓋 算 法 研 究 ［J］.計 算 機 學 報，2012，35 （2）：257－268.］

［11］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.

［12］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.

［13］Zhu Xiaojun.Research and implementation of software testing method based on parameter pairwise combination ［D］.Shanghai：Shanghai Normal University，2004.