基于AETG 算法的兩兩組合測試用例生成方法

梁 凡，宋曉秋

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

0 引 言

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

1 兩兩組合測試算法簡介

1.1 正交拉丁算法簡介

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

1.2 AETG 算法簡介

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

1.3 IPO 算法簡介

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

1.4 各種算法比較

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

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

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

2 基于AETG 算法的改進(jìn)方法

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ù)值，如果本次應(yīng)選取的參數(shù)是Fi，則計算Fi的所有參數(shù)值，選擇與已形成的F1，F(xiàn)2……Fi－1的各個值構(gòu)成的配對在UC中出現(xiàn)最多的那個參數(shù)值，將其添加進(jìn)已形成的參數(shù)組中，接著再用相同的方法擴(kuò)展Fi＋1。

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

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

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

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

2.2 AETG 算法的改進(jìn)

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

2.2.1 AETG＿I算法改進(jìn)的第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）。當(dāng)生成第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次擴(kuò)展A 更加合適，這主要是因為參數(shù)A 中的A1在UC中出現(xiàn)的次數(shù)占據(jù)絕對優(yōu)勢。所以當(dāng)有2個或更多的參數(shù)其值在UC 中出現(xiàn)的次數(shù)相同時，應(yīng)該優(yōu)先選擇包含某個出現(xiàn)次數(shù)絕對多的取值的那個參數(shù)。

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

如果某個待測系統(tǒng)有5個參數(shù)A，B，C，D，E，每個參數(shù)各有2種取值。當(dāng)前的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。

綜上，改進(jìn)的第 （2）步描述為：

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

（3）第3步與原方法大致相同，但是原AETG 方法在進(jìn)行參數(shù)值選擇時采用的是向前對比的方法，這種方法存在一個問題，例如某個待測系統(tǒng)有4 個參數(shù)，每個參數(shù)有3個取值，生成某個測試用例時參數(shù)擴(kuò)展順序定為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算法改進(jìn)的第2部分

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

下面給出改進(jìn)的AETG 算法的算法描述，如圖1所示。

2.4 AETG＿I算法分析

2.4.1 間復(fù)雜度分析

因為改進(jìn)后的方法迭代次數(shù)在用例生成工作的后期會越來越小，所以新方法在時間復(fù)雜度上根據(jù)待測系統(tǒng)的不同會不同程度的小于原AETG 方法。尤其是當(dāng)參數(shù)的取值每個之間都存在差異，也就是參數(shù)取值情況參差不齊的時候，算法能很容易的找到每次待擴(kuò)展的參數(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 算法來講，當(dāng)參數(shù)數(shù)量超過6（5?。?20）時，AETG 算法每一次都必須取到50 個測試用例。所以AETG 算法的時間復(fù)雜度上限為

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

AETG＿I算法與AETG 算法復(fù)雜度比較見表1。

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

表1 AETG＿I算法與AETG 算法復(fù)雜度比較

2.4.2 結(jié)果分析

下面選取幾組實驗對比改進(jìn)后的算法與原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個取值。

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

3 結(jié)束語

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

［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］.計算機(jī)學(xué)報，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）. ［嚴(yán)俊，張健.組合測試：原理與方法［J］.軟件學(xué)報，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］.武漢：華中科技大學(xué)，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）. ［周吳杰，張德平，徐寶文.基于組合測試的軟件故障定位的自適應(yīng)算法 ［J］.計算機(jī)學(xué)報，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ìn)展 ［J］.計算機(jī)科學(xué)，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］.計 算 機(jī) 學(xué) 報，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.