快速生成兩兩組合測試用例集算法

周吳杰 張德平 徐寶文

(1東南大學(xué)計算機科學(xué)與工程學(xué)院，南京 210096)

(2南京大學(xué)軟件新技術(shù)國家重點實驗室，南京 210093)

(3南京航空航天大學(xué)信息科學(xué)與技術(shù)學(xué)院，南京 210016)

(4南京大學(xué)計算機科學(xué)與技術(shù)系，南京 210093)

組合測試是一種重要的軟件測試方法，旨在用較少的測試用例有效地檢測軟件系統(tǒng)中各個因素間的交互作用對系統(tǒng)產(chǎn)生的影響.組合測試的一個關(guān)鍵問題是組合測試用例生成問題，即在保證因素組合覆蓋能力的前提下，生成規(guī)模盡可能小的測試用例集，從而在保證測試用例錯誤檢測能力的基礎(chǔ)上盡可能節(jié)約測試成本.兩兩組合測試問題作為組合測試的簡單情形已有大量的研究并在軟件測試領(lǐng)域中獲得廣泛的應(yīng)用.研究者們通過數(shù)學(xué)構(gòu)造、貪心算法以及智能搜索等方法來生成規(guī)模盡可能小的測試用例集［1－7］，隨后高維以及變強度的組合測試用例生成問題也得到研究［8－9］.由于兩兩組合測試用例生成問題的 NP－complete性質(zhì)［1］，現(xiàn)有的近似算法均無法生成最優(yōu)解.有些生成測試用例的啟發(fā)式算法運行時間較長，只能在因素較少的測試場景中使用.本文提出一種簡單快速的數(shù)學(xué)構(gòu)造算法，該方法建立在二元的兩兩組合的最優(yōu)測試數(shù)據(jù)集的生成算法基礎(chǔ)上，在二元情形下能得到最優(yōu)解.對于一般的待測軟件系統(tǒng)，算法能確保得到的測試用例數(shù)據(jù)集規(guī)模是關(guān)于因素數(shù)目k對數(shù)階增長的.算法的時間復(fù)雜性為O(klog k)，所以對于大規(guī)模的待測系統(tǒng)，算法生成測試用例集的速度很快.算法是分層構(gòu)造的，這種分層性有利于測試結(jié)束后的故障定位，即一旦測試出軟件失效，算法生成的測試用例集的分層結(jié)構(gòu)有利于測試工作人員對導(dǎo)致軟件故障的錯誤交互進行有效的定位與偵測.

1 組合測試基本概念與模型

假設(shè)影響待測軟件系統(tǒng)(software under test，SUT)的因素共有 k個，用1，2，…，k表示，因素 i有vi(1≤i≤k)個可能的取值，用0，1，…，vi－1 表示.用記號［0，vi－1］表示集合{0，1，…，vi－1}.稱(v1，v2，…，vk)為 SUT 的因素可取值數(shù)目向量.假設(shè)這些參數(shù)的取值是相互獨立的，即某個參數(shù)的具體取值不會影響其他參數(shù)的取值或存在性.

定義1 設(shè) k維向量 T={T1，T2，…，Tk}，其中Ti∈［0，vi－1］，i=1，2，…，k，則稱該 k 維向量 T 為第i個因素取值為Ti的測試用例.

為了生成測試用例集，定義覆蓋表如下:

定義2 設(shè)A是一個n×k表，表中第i列元素都取自［0，vi－1］，任取 A 中 2列(第 i列和第 j列)，則所有的二維組合都被表中某一行所對應(yīng)的測試用例覆蓋，即對任意的有序?qū)?ai，aj)，ai∈［0，vi－1］，aj∈［0，vj－1］，至少存在一行 r，使得A［r，i］=ai，A［r，j］=aj.則稱表 A 是一個兩兩組合覆蓋表，記此表為 MCA(n;2，(v1，v2，…，vk)).稱使得 MCA(n;2，(v1，v2，…，vk))存在的最小整數(shù) n為兩兩覆蓋表數(shù)，記為 MCAN(2，(v1，v2，…，vk))，當(dāng) v1=v2=…=vk=v時，簡記為 CA(n;2，k，v)和 CAN(2，k，v).

若SUT中因素可取值數(shù)目為vi的因素個數(shù)為pi(i=1，2，…，s)，k=p1+p2+…+ps，不妨設(shè) vi＞vj(i＜j)，則用一個簡單記號來記此SUT的因素可取值數(shù)目向量，這時覆蓋表記為MCA(n;2，).用覆蓋表產(chǎn)生測試用例時，表中每列對應(yīng)一個因素，每一行表示一個測試用例.

例如一個打印系統(tǒng)有2種類型打印機P1，P2，分別用0，1表示;打印的文件格式有JPEG，PDF，PS三種，分別用0，1，2表示.顏色及文件大小如表1所示.

表1 打印機系統(tǒng)的各個因素及其取值

如果對因素的所有可能取值組合進行測試，則需要2×3×2×3=36個測試用例，若只考慮任意2個因素之間的交互作用，則僅需要9條測試用例，如表2所示.

表2 打印機系統(tǒng)的兩兩組合測試用例集

稱所有因素取值都是二元的SUT為二元待測系統(tǒng)，該系統(tǒng)的二維最小覆蓋表構(gòu)造問題已解決，其覆蓋表數(shù) CAN(2，k，2)=n，其中 k＞1，n 是滿足條件的最小整數(shù)［10］.

對于一般的SUT，尋求最優(yōu)的測試用例集問題是 NP－complete 問題［1］.但顯然有 CAN(2，k，v)≥v2和所以表2中的測試用例集是最優(yōu)的.

本文以下都假設(shè)SUT中因素數(shù)目k＞1.

2 生成兩兩組合測試用例集的快速算法

2.1 vk情形

在二元待測系統(tǒng)中，記 n1為滿足條件的最小整數(shù)，構(gòu)造最優(yōu)的覆蓋表為n1×k表，其中第1行全取0，其余的n1－1行中，對每一列取個1，使得各列互不相同.用這種方法構(gòu)造出的二元覆蓋表作為一個基本塊，記為B(0，1).對任意的 a，b(a＜b)，記 B(a，b)為把基本塊B(0，1)中的0置換成a，1置換成b得到的新基本塊.這樣把所有的基本塊B(i，j)(0≤i＜j≤v－1)上下累加起來就構(gòu)成了兩兩組合覆蓋表.然而這種構(gòu)造出來的覆蓋表有很多冗余行，比如所有因素取值都為0的行有v－1行，為了消除這些冗余，需再引入另外的約簡塊 R(0，1).

在二元待測系統(tǒng)中，構(gòu)造另外一個表，使得表中任取 i，j兩列，(0，1)與(1，0)組合都至少在某一行出現(xiàn).設(shè)n2為滿足的最小整數(shù)，則根據(jù)Sperner定理，得到這種表的行數(shù)最少為n2，具有最少行數(shù) n2的表可這樣構(gòu)造:每列中取個1，其余取值為0，使得各列互不相同.所構(gòu)造出的滿足上述性質(zhì)的表稱為約簡塊，記為R(0，1).對任意的 a，b(a＜b)，記 R(a，b)為把約簡塊R(0，1)中的0置換成a，1置換成b得到的新約簡塊.

運用基本塊和約簡塊就可構(gòu)造一般的兩兩組合覆蓋表.對任意的 i，j(0≤i＜j≤v －1)，如果 i是偶數(shù)并且j=i+1時，用基本塊B(i，j)來構(gòu)造(i，j)對應(yīng)的塊，否則用約簡塊R(i，j)來構(gòu)造，最后把所有的基本塊B(i，j)和約簡塊R(i，j)上下累加起來就構(gòu)成了兩兩組合覆蓋表.具體算法如下.

算法1 構(gòu)造兩兩組合覆蓋表CA

輸入:k，v(k＞1).

輸出:覆蓋表CA.

從基本塊B(0，1)與約簡塊R(0，1)的構(gòu)造，可得到如下定理:

定理1 算法1返回的CA就是覆蓋表CA(n;2，k，v)，其行數(shù)為

證明 在CA中任取2列i，j列，對任意的組合(a，b)(0≤a，b≤v－1)，證明如下:

1) 當(dāng)a＜b時，因為基本塊B(0，1)或R(0，1)中都至少存在一行覆蓋了組合(0，1)，所以對應(yīng)的塊 B(a，b)或 R(a，b)覆蓋了(a，b).

2) 當(dāng)a＞b時，基本塊 B(0，1)或 R(0，1)中都至少存在一行覆蓋了組合(1，0)，所以對應(yīng)的塊B(b，a)或 R(b，a)覆蓋了(a，b).

3)當(dāng)a為奇數(shù)，則組合(a，a)在基本塊B(a－1，a)中被覆蓋，當(dāng)a為偶數(shù)且a≠v－1時，則組合(a，a)在基本塊B(a，a+1)中被覆蓋，當(dāng)a為偶數(shù)且a=v－1時，則組合(a，a)被在算法1中最后添加的恒等行(v－1，v－1，…，v－1)所覆蓋，所以算法1返回的CA是覆蓋表CA(n;2，k，v).

由于算法1在構(gòu)造過程中用了v(v－1)/2個塊，當(dāng)v為偶數(shù)時，基本塊有v/2個，其余都是約簡塊，所以返回的覆蓋表 CA的行數(shù);當(dāng)v為奇數(shù)時，基本塊有(v－1)/2個，其余是約簡塊，最后是一個恒等行，所以覆蓋表CA的行數(shù).證畢.

定理2 算法1返回的覆蓋表為CA(n;2，k，v)，其行數(shù) n≤v(v－1)logk+1(k≥16).

證明 由于塊B(0，1)或R(0，1)的每列互不相同，而互不相同的列最多有2n1或2n2個，所以2n1≥k，2n2≥k，即 n1≥logk，n2≥logk.

因為n1是滿足條件的最小整數(shù)，所以，即

所以

而

故當(dāng)n1≥14時，

因此，n1≤2logk(n1≥14).當(dāng) n1＜14時，列表3依次討論.得到當(dāng) n1≥8時，即 k≥16時，n1≤2logk.

表3 n1＜14時因素數(shù)目k與n1的對應(yīng)關(guān)系

與上述討論類似，n2滿足條件

即

所以

故當(dāng)n2≥6時，

因此n2≤2logk(n2≥6).當(dāng) n2＜6時，列表4依次驗證.得到對任意的k，都有n2≤2logk.

所以，n1與n2都滿足

而算法1返回的覆蓋表CA(n;2，k，v)是由v(v－1)/2個基本塊或約簡塊構(gòu)成，當(dāng)v為奇數(shù)時再加上一個恒等行，所以其行數(shù)n≤v(v－1)logk+1(k≥16).證畢.

表4 n2＜6時因素數(shù)目k與n2的對應(yīng)關(guān)系

由定理2知，當(dāng)k→∞時，算法1返回的覆蓋表行數(shù)是關(guān)于因素數(shù)目k對數(shù)階增長的.

證明 由于生成塊B(0，1)或R(0，1)是向表中每個位置寫0或1操作，所以其時間復(fù)雜性是O(klogk)，所以算法1的時間復(fù)雜性為klogk).證畢.

由于在實踐中很多SUT的各個因素可取值數(shù)目不一定都相等，所以需要把上述算法推廣到因素可取值數(shù)目不一致的情形.假設(shè)因素可取值數(shù)目向量簡寫為，其中k=p1+p2+…+ps，且 vi＞vj(i＜ j).用 B(0，1，k)與 R(0，1，k)分別表示k列滿足覆蓋條件表中元素取值為0，1的基本塊與約簡塊，另外若 k=1時，記 B(0，1，1)=R(0，1，1)=(1)，即為1 ×1 的表，表中唯一的元素取值為1，對任意的a，b(a＜b)，用B(a，b，k)和R(a，b，k)表示相應(yīng)的置換后的基本塊與約簡塊.用記號C(i)表示取值全是i的列向量，用D(i)表示每個元素可在［0，i－1］集合內(nèi)任意取值的列向量.這時對任意的i，j，覆蓋表中層的構(gòu)造方法如下:

① 當(dāng)0≤i＜j≤vs－1時，用具有 k列的塊B(i，j，k)或 R(i，j，k)來構(gòu)造.

② 當(dāng) i＜j且 vs－1 ＜j≤vs－1－1 時，用具有 k－ps列的塊 B(i，j，k－ps)或 R(i，j，k－ps)來構(gòu)造前面k－ps列.當(dāng)0＜i≤vs－1時，后面的 ps列均為 C(i);當(dāng) vs－1 ＜ i≤vs－1－1 時，后面的 ps列均為D(vs).

③ 當(dāng)i＜j且vs－1－1 ＜j≤vs－2－1 時，用具有k－ps－1－ps列的塊 B(i，j，k －ps－1－ ps)或 R(i，j，k－ps－1－ps)來構(gòu)造前面的列.當(dāng)0 ＜i≤vs－1 時，后面的 ps－1+ps列均為 C(i);當(dāng) vs－1 ＜ i≤vs－1－1時，后面的列中前面ps－1列均為C(i)，后面的ps列均為 D(vs);當(dāng) vs－1－1 ＜ i≤vs－2－1 時，后面的ps－1+ps列中前 ps－1列均為 D(vs－1)，后 ps列均為D(vs).

如此繼續(xù)進行，直至對0＜i＜j＜k都構(gòu)造出相應(yīng)的層.如果v1為奇數(shù)，最后并上1行，該行前P1個因素取值為v1－1，后k－p1個因素可取任意合法值.這樣就可得到兩兩組合覆蓋表，具體算法如下.

算法2 構(gòu)造兩兩組合覆蓋表MCA

輸出:覆蓋表MCA.

本文稱算法2為 SpeedyPair算法，簡稱 SP算法.

根據(jù)上述分析及定理1～3，可得如下定理:

為了更清楚地看出SP算法中各個塊的構(gòu)成，舉一個具體的例子如下:

假設(shè)SUT的因素可取值數(shù)目向量為5233210，用SP算法生成的兩兩組合覆蓋表如圖1所示.圖中－1的位置表示“不關(guān)心”的位置，可用任意合法數(shù)值代替.

圖1 CA(32;2，5233210)及其各個構(gòu)成塊

3 實驗分析

為了研究SP算法的性能，本文通過實驗比較了 AETG 系統(tǒng)［2］、PAIRTEST 系統(tǒng)［1］、Kobayashi等提出的代數(shù)方法［3］、Williams 提出的代數(shù)方法［4］，基于解空間樹的組合測試工具［5］生成測試用例的規(guī)模，如表5所示.表5中前5種方法的試驗數(shù)據(jù)均來自文獻［5］.從表5中可看出，當(dāng)各因素可取值數(shù)目較小時，SP算法效果較好，如 2100和41339235;當(dāng)各因素可取值數(shù)目比較大時，如53443122，SP算法生成測試用例集比較大，甚至在34情形，SP算法沒有生成最優(yōu)解.

表5 測試用例集規(guī)模比較

但是SP算法的時間、空間效率高，針對大規(guī)模的待測系統(tǒng)，生成的測試用例集速度非?？?，在編程語言為 Matlab，操作系統(tǒng)為 Windows XP，CPU 為 INTEL Pentium IV 2.93 GHZ，內(nèi)存為512 MB的PC機上對大規(guī)模待測系統(tǒng)運行SP算法，結(jié)果如表6所示.

表6 大規(guī)模待測系統(tǒng)的運行效果

從表6中可看出SP算法時間效率很高，對大規(guī)模的SUT如有1.0×105個因素，每個因素有4個取值的 SUT，計算出兩兩組合覆蓋表只需16.620 s.

用兩兩組合測試用例集來執(zhí)行測試時，測試結(jié)束后如果檢測出故障，就必須進行故障定位，這需要運行許多附加的測試用例.由于SP算法是分層的，發(fā)現(xiàn)故障后會很快確定哪一層出現(xiàn)故障，從而對故障定位階段的工作提供幫助.

4 結(jié)語

本文提出了快速生成兩兩組合測試用例集的SP算法，其優(yōu)點在于快速、簡捷，當(dāng)SUT是二元時能生成最小的測試用例集.實驗表明該算法產(chǎn)生的測試數(shù)據(jù)與同類算法相比具有一定的特點與優(yōu)勢，可作為已有方法的重要補充.

由于SP算法局限在兩兩組合測試場景，如何把算法思想推廣到多維組合測試場景，是需要進一步研究的問題.其次，SP算法生成的覆蓋表有很強的分層結(jié)構(gòu)性質(zhì)，所以還需研究其結(jié)構(gòu)，以便在故障出現(xiàn)時幫助和減輕在故障定位階段的工作.

References)

［1］ Lei Y，Tai K C.In－Parameter－Oder:a test generation strategy for pairwise testing，TR－2001－03 ［R］.Raleigh，NC，USA:Department of Computer Science，North Carolina State University，2001.

［2］ Cohen D M，Dalal S R，F(xiàn)redman M L，et al.The AETG system:an approach to testing based on combinatorial design［J］.IEEE Transactions on Software Engineering，1997，23(7):437－444.

［3］ Kobayashi N，Tsuchiya T，Kikuno T.A new method for constructing pair－wise covering designs for software testing［J］.Information Processing Letters，2002，81(2):85－91.

［4］Williams A W.Software component interaction testing:coverage measurement and generation of configurations［D］.Ottawa，Ontario，Canada:Ottawa－Carleton Institute for Computer Science，School of Information Technology and Engineering，University of Ottawa，2002.

［5］史亮，聶長海，徐寶文.基于解空間樹的組合測試數(shù)據(jù)生成［J］.計算機學(xué)報，2006，29(6):849－857.Shi Liang，Nie Changhai，Xu Baowen.Pairwise test data generation based on solution space tree［J］.Chinese Journal of Computers，2006，29(6):849－857.(in Chinese)

［6］査日軍，張德平，聶長海，等.組合測試數(shù)據(jù)生成的交叉熵與粒子群算法及比較［J］.計算機學(xué)報，2010，33(10):1896－1908.Zha Rijun，Zhang Deping，Nie Changhai，et al.Test data generation algorithms 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)

［7］ Yan J，Zhang J.A backtracking search tool for constructing combinatorial test suites［J］.The Journal of Systems and Software，2008，81(10):1681－1693.

［8］ Lei Y，Kacker R，Kuhn D R，et al.IPOG－D:efficient test generation for multi－way combinatorial testing ［J］.Software Testing，Verification and Reliability，2008，18(3):125－148.

［9］ Cheng Xiang，Gu Qing，Li Ang，et al.Variable strength interaction testing with an ant colony system approach［C］//16th Asia-Pacific Software Engineering Conference.Batu Ferringhi，Penang，Malaysia，2009:160－167.

［10］Hartman A.Software and hardware testing using combinatorial covering suites［C］//Interdisciplinary Applications of Graph Theory，Combinatorics，and Algorithms.Norwell，MA，USA，2005:237－266.