周吳杰 張德平 徐寶文

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

(2南京大學(xué)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京 210093)

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

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

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

1 組合測(cè)試基本概念與模型

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 vk情形

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

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

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

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

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

輸出:覆蓋表CA.

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

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

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

1) 當(dāng)a＜b時(shí)，因?yàn)榛緣KB(0，1)或R(0，1)中都至少存在一行覆蓋了組合(0，1)，所以對(duì)應(yīng)的塊 B(a，b)或 R(a，b)覆蓋了(a，b).

2) 當(dāng)a＞b時(shí)，基本塊 B(0，1)或 R(0，1)中都至少存在一行覆蓋了組合(1，0)，所以對(duì)應(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時(shí)，則組合(a，a)在基本塊B(a，a+1)中被覆蓋，當(dāng)a為偶數(shù)且a=v－1時(shí)，則組合(a，a)被在算法1中最后添加的恒等行(v－1，v－1，…，v－1)所覆蓋，所以算法1返回的CA是覆蓋表CA(n;2，k，v).

由于算法1在構(gòu)造過(guò)程中用了v(v－1)/2個(gè)塊，當(dāng)v為偶數(shù)時(shí)，基本塊有v/2個(gè)，其余都是約簡(jiǎn)塊，所以返回的覆蓋表 CA的行數(shù);當(dāng)v為奇數(shù)時(shí)，基本塊有(v－1)/2個(gè)，其余是約簡(jiǎn)塊，最后是一個(gè)恒等行，所以覆蓋表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個(gè)，所以2n1≥k，2n2≥k，即 n1≥logk，n2≥logk.

因?yàn)閚1是滿足條件的最小整數(shù)，所以，即

所以

而

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

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

表3 n1＜14時(shí)因素?cái)?shù)目k與n1的對(duì)應(yīng)關(guān)系

與上述討論類(lèi)似，n2滿足條件

即

所以

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

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

所以，n1與n2都滿足

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

表4 n2＜6時(shí)因素?cái)?shù)目k與n2的對(duì)應(yīng)關(guān)系

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

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

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

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

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

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

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

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

輸出:覆蓋表MCA.

本文稱(chēng)算法2為 SpeedyPair算法，簡(jiǎn)稱(chēng) SP算法.

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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］史亮，聶長(zhǎng)海，徐寶文.基于解空間樹(shù)的組合測(cè)試數(shù)據(jù)生成［J］.計(jì)算機(jī)學(xué)報(bào)，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］査日軍，張德平，聶長(zhǎng)海，等.組合測(cè)試數(shù)據(jù)生成的交叉熵與粒子群算法及比較［J］.計(jì)算機(jī)學(xué)報(bào)，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.