2維約束覆蓋數(shù)組最小規(guī)模下限的提升

盛云龍,魏長安,姜守達(dá)，付 堯，趙偉志

(1.哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院 自動化測試與控制研究所,哈爾濱 150080；2.北京工業(yè)大學(xué),北京 100000)

組合測試是一種重要的黑盒測試技術(shù)[1-4]，利用更少的測試數(shù)據(jù)量，可以發(fā)現(xiàn)更多的由參數(shù)之間的相互作用引起的系統(tǒng)故障.通過對任意t個參數(shù)全部取值組合的覆蓋，可以發(fā)現(xiàn)幾乎100%的系統(tǒng)故障，因此又被稱為“偽窮舉測試”[5].

在實(shí)際測試中，參數(shù)之間往往存在約束條件，限制了參數(shù)之間的取值關(guān)系[6-8].這種情況下，組合測試的測試數(shù)據(jù)集被稱為t維約束覆蓋數(shù)組，其可覆蓋任意t個參數(shù)之間滿足約束的取值組合.t=2的約束覆蓋數(shù)組被稱為2維約束覆蓋數(shù)組，因?yàn)槠湟?guī)模小，所以最為常用.為了提高實(shí)際測試的效率，2維約束覆蓋數(shù)組的規(guī)模應(yīng)盡可能的小，最好找到理論上最小規(guī)模的2維約束覆蓋數(shù)組.然而找到規(guī)模最小的2維約束覆蓋數(shù)組已被證明是NP完全(Non-deterministic Polynomial Complete，NPC)問題[9-10]，因此為減少生成時間，很多測試數(shù)據(jù)搜索算法被應(yīng)用到尋找規(guī)模最小或近似最小的2維約束覆蓋數(shù)組.經(jīng)典算法有HSS[11]、SA_SAT[12]、mAETG_SAT[13]、PICT、TestCover、IPOG[14]、IPOG-F[15]、CTWT[16]等.前兩個算法屬于啟發(fā)式算法，其余算法屬于貪心算法.

為了評價這些算法的性能，需要將這些算法生成的2維約束覆蓋數(shù)組的規(guī)模與理論上的最小值進(jìn)行比較.目前可以得出的理論最小值是任意兩個參數(shù)之間滿足約束的取值組合數(shù)的最大值，然而這個值只表示了約束下需要覆蓋的取值組合數(shù)，并沒有考慮約束的影響.由于約束的影響，2維約束覆蓋數(shù)組不僅要考慮需要覆蓋的取值組合數(shù)，還要考慮約束情況，約束的存在使得原本可以在一條測試數(shù)據(jù)中覆蓋的取值組合，要被拆開放到多條測試數(shù)據(jù)中，這樣就增加了測試數(shù)據(jù)的數(shù)目，導(dǎo)致2維約束覆蓋數(shù)組的規(guī)模增加，因此2維約束覆蓋數(shù)組最小規(guī)模要考慮約束的影響.

本文提出一種禁忌邊分解方法，可以將描述被測系統(tǒng)輸入配置的圖分解成兩個子圖，通過計算覆蓋兩個子圖中全部頂點(diǎn)的子覆蓋數(shù)組的規(guī)模和剩余需要覆蓋的取值組合數(shù)，與單純計算需要覆蓋的取值組合數(shù)相比，提升了2維約束覆蓋數(shù)組的最小規(guī)模.提升的最小規(guī)?？梢杂糜谠u價現(xiàn)有算法生成的2維約束覆蓋數(shù)組，比較生成的2維約束覆蓋數(shù)組的規(guī)模與理論最小規(guī)模之間的差距，同時最小規(guī)模有助于判斷生成的2維約束覆蓋數(shù)組是否真實(shí)存在.

1 基本概念

假設(shè)一個被測系統(tǒng)具有k個參數(shù)，分別為P1,P2,…,Pk，每個參數(shù)分別對應(yīng)v1,v2,…,vk個取值，即對于任意參數(shù)Pi(1≤i≤k)其有vi個取值，具體表示為集合{0,1,…,vi-1}，簡記為[0,vi-1]，各個參數(shù)之間取值均相互獨(dú)立.記參數(shù)集合P={P1,P2,…,Pk}，取值個數(shù)集合V={v1,v2,…,vk}，配置空間模型(Configuration Space Model，CSM)M=，組合測試根據(jù)被測系統(tǒng)的配置空間模型來構(gòu)造測試數(shù)據(jù)集.

定義1(約束覆蓋數(shù)組，約束混合覆蓋數(shù)組)[17]：設(shè)A是一個n×k的矩陣，約束元組f=(a1,a2,…,ak)是一個k維向量，用于限制取值組合的出現(xiàn)，ai∈[0,vi-1]∪[x](1≤i≤k)，如果約束中沒有指定第j個參數(shù)的取值，則aj=x.對任意一個出現(xiàn)在測試數(shù)據(jù)中，且不會引起測試數(shù)據(jù)中出現(xiàn)約束元組的t維組合I={(Pi1,ai1),(Pi2,ai2),…,(Pit,ait)}，aij∈[0,vij-1](1≤j≤t)，如果A至少存在一行r，使得A[r,ij]=aij且不覆蓋約束元組，則稱A為約束覆蓋數(shù)組(Constrained Covering Array，CCA)，記為CCA(n;t,k,v;F)，其中F是約束元組f的全集.

定義2(帶有禁忌邊的覆蓋數(shù)組)[9]設(shè)A是一個n×k的帶有禁忌邊的覆蓋數(shù)組(Covering Array with Forbidden Edges，CAFE)，表示為CAFE(n,G)，其中G=G(g1,g2,…,gk)是參數(shù)取值構(gòu)成的圖，gi(1≤i≤k)是圖中第i列頂點(diǎn)的集合，E(G)是G中的邊集，簡記為E或EG.對A中任意一列，其取值范圍為[0,|gi|-1].對任意的不屬于同一列的兩個頂點(diǎn)ai∈[0,|gi|-1]和bj∈[0,|gj|-1](i≠j)，如果{ai,bj}?E(G)且滿足約束一致性，則A中一定存在一行r，使得A[r,i]=a，A[r,j]=b.

E中的邊就是約束，在圖中被稱為邊或禁忌邊.CAFE(n,G)是力度為2的約束覆蓋數(shù)組.N或NG用來表示對應(yīng)于圖G的覆蓋力度為2的帶有禁忌邊的覆蓋數(shù)組的最小規(guī)模.從圖G中容易得出如下式所示關(guān)系式：

NG≥max1≤i

(1)

式(1)中Eij表示圖G中第i列和第j列中滿足約束一致性的邊，NG的下限是圖G中任意兩列滿足約束一致性的取值組合個數(shù)的最大值.

定義3(頂點(diǎn)子圖)Gi,a是圖G的一個子圖，移除了圖G中第i列除了a之外的全部頂點(diǎn)(1≤i≤k)，并且移除了與第i列中頂點(diǎn)a構(gòu)成邊的頂點(diǎn).

定義4(頂點(diǎn)帶禁忌邊的覆蓋數(shù)組)A是頂點(diǎn)子圖Gi,a的一個n×k的頂點(diǎn)帶有禁忌邊的覆蓋數(shù)組，頂點(diǎn)帶有禁忌邊的覆蓋數(shù)組簡記為CAFE(n,Gi,a)，對頂點(diǎn)子圖Gi,a中的任意一個頂點(diǎn)bj，A中一定存在一行r滿足約束一致性且A[r,j]=b.

定義5(兩列的取值組合個數(shù))Ii,j(AGi,a)表示CAFE(n,Gi,a)中覆蓋的第i列和第j列的取值組合個數(shù).如果取值組合重復(fù)出現(xiàn)，則只記錄一次.

2 基于禁忌邊分解方法的約束覆蓋數(shù)組最小規(guī)模下限的提升

式(1)在估計NG的范圍時，只是根據(jù)兩個參數(shù)之間滿足約束的取值組合數(shù)進(jìn)行估計，并沒有依據(jù)實(shí)際的約束的特點(diǎn)進(jìn)行估計，因此得出的NG的范圍較為寬泛，通過對禁忌邊進(jìn)行分解可以更準(zhǔn)確的估計NG的范圍.

通常把地表500 m以下的礦床和礦體統(tǒng)稱為深部礦。進(jìn)行深部找礦的主要目的是為了找尋更多的礦產(chǎn)接替資源，以促進(jìn)我國礦產(chǎn)資源的可持續(xù)發(fā)展。深部找礦主要在勘查程度較高的地區(qū)和現(xiàn)有礦山及其外圍進(jìn)行，其勘查對象主要是隱伏礦床(體)。

通過對圖中的邊進(jìn)行分解，進(jìn)一步分析組合約束對其余取值的限制關(guān)系，可以更為準(zhǔn)確的得到CAFE(n,G)的最小規(guī)模NG的下限，式(2)所示為對G中的一條邊(ai,bj)進(jìn)行分解得到的NG的下限.

NG≥max1≤iNGj,b-Ii,j(AGi,a)-Ii,j(AGj,b)).

(2)

如式(2)所示，(ai,bj)是圖G中的任意一條邊，基于邊(ai,bj)中的兩個頂點(diǎn)可以從圖G中分出兩個頂點(diǎn)子圖Gi,a和Gj,b.AGi,a和AGj,b是Gi,a和Gj,b對應(yīng)的兩個頂點(diǎn)帶禁忌邊的約束覆蓋數(shù)組，NGi,a和NGj,b是AGi,a和AGj,b的規(guī)模，Ii,j(AGi,a)和Ii,j(AGj,b)是AGi,a和AGj,b中i和j兩列參數(shù)的取值組合數(shù).

式(2)的含義有如下兩種解釋：

1)為了覆蓋第i列和第j列參數(shù)的|gi||gj|-|Eij|個取值組合，CAFE(n,G)規(guī)定一定包含頂點(diǎn)ai與第j列參數(shù)的全部滿足約束的取值組合和頂點(diǎn)bj與第i列參數(shù)的全部滿足約束的取值組合，這兩組參數(shù)取值組合分別在規(guī)模最小的AGi,a和AGj,b中被覆蓋，然而CAFE(n,G)中仍有|(|gi||gj|-|Eij|-Ii,j(AGi,a)-Ii,j(AGj,b)個滿足約束的取值組合需要覆蓋，加上已經(jīng)生成的規(guī)模NGi,a+NGj,b，即得到NG的下限.

2)因?yàn)樽罱K生成的覆蓋數(shù)組中一定覆蓋了包含頂點(diǎn)ai與第j列參數(shù)的全部滿足約束一致性的取值組合，和頂點(diǎn)bj與第i列參數(shù)的全部滿足約束的取值組合，所以規(guī)模最小的AGi,a和AGj,b一定存在于CAFE(n,G)中，原本CAFE(n,G)的最小規(guī)模為|gi||gj|-|Eij|，但是為了覆蓋其中的Ii,j(AGi,a)個參數(shù)取值組合，需要增加的測試數(shù)據(jù)規(guī)模為NGi,a-Ii,j(AGi,a)，為了覆蓋Ii,j(AGj,b)個參數(shù)取值組合，需要增加的測試數(shù)據(jù)規(guī)模為NGj,b-Ii,j(AGj,b)，所以為了覆蓋|gi||gj|-|Eij|個取值組合，至少還要在其基礎(chǔ)上增加NGi,a+NGj,b-Ii,j(AGi,a)-Ii,j(AGj,b)條測試數(shù)據(jù).

以一個有4個參數(shù)的被測系統(tǒng)為例，其第1個參數(shù)有2個取值(0和1)，其余參數(shù)有3個取值(0、1和2)，其中參數(shù)2和參數(shù)3的取值組合(0，0)、參數(shù)2和參數(shù)4的取值組合(2，2)、參數(shù)3和參數(shù)4的取值組合(1，1)是約束，如圖1所示.

圖1 被測系統(tǒng)參數(shù)及取值配置對應(yīng)圖舉例

Fig.1 Example graph of the parameters and value configurations of the system under test

為其生成帶有禁忌邊的覆蓋數(shù)組時，按照式(1)的結(jié)論，可以得出NG≥9-1=8.然而在實(shí)際構(gòu)造帶有禁忌邊的約束覆蓋數(shù)組時，由于約束的存在，需要增加一定的測試數(shù)據(jù)才能覆蓋8個取值組合，其最小規(guī)模為10，如表1所示.為了證明其最小規(guī)模為10，采用禁忌邊分解方法首先對圖進(jìn)行分解，然后計算需要覆蓋的參數(shù)間的取值組合數(shù).

表1 帶有禁忌邊的覆蓋數(shù)組舉例

圖2和圖3分別是頂點(diǎn)子圖G2,0和G3,0，在G2,0中移除了與第2個參數(shù)頂點(diǎn)0同一列的其他取值，同時移除了與頂點(diǎn)0構(gòu)成邊的其余參數(shù)的頂點(diǎn)，參數(shù)3的頂點(diǎn)0.同理可得G3,0.表2和表3分別是對應(yīng)頂點(diǎn)子圖G2,0和G3,0的CAFE(3,G2,0)和CAFE(3,G3,0)，記為AG2,0和AG3,0，其規(guī)模都為3.因?yàn)槊總€頂點(diǎn)子圖中，參數(shù)4最多有3個取值，所以覆蓋這兩個頂點(diǎn)子圖中的全部頂點(diǎn)(取值)至少需要3條測試數(shù)據(jù).所以AG2,0和AG3,0都具有最小規(guī)模，且覆蓋的參數(shù)2和參數(shù)3的取值組合數(shù)I2,3(AG2,0)和I2,3(AG3,0)都是2，所以由式(2)可得NG≥3×3-1+3+3-2-2=10，從另外的兩個邊著手也可以得到相同的NG的下限，因此可以得出NG的下限就是10.

圖2 G2,0

圖3 G3,0

表2 CAFE(3,G2,0)

表3 CAFE(3,G3,0)

根據(jù)對圖中邊進(jìn)行分解計算CAFE(n,G)的最小規(guī)模下限的過程，可以得出如下推論：

如果一個圖滿足下面3個條件：

1)所有的列具有相同的頂點(diǎn)數(shù)，即被測系統(tǒng)的每個參數(shù)具有相同的取值個數(shù)|g1|=|g2|=…=|gk|=g；

2)參數(shù)i和j之間只有一條邊(ai,bj)，a,b∈[0,g-1]，i,j∈[1,k]且i≠j；

3)不存在任意頂點(diǎn)cl，c∈[0,g-1]且l∈[1,k]，使得(cl,ai),(cl,bj)?EG.

則有如下關(guān)系：

NG≥|gi||gj|-1+|gi|-(|gi|-1)+

|gj|-(|gj|-1)=|gi||gj|+1=g2+1

上述推論的證明過程與上例計算NG的過程相同.該推論可以用一個簡單的例子來理解，假設(shè)圖G中每一列都有g(shù)個頂點(diǎn)，G中沒有邊時NG≥g2.假設(shè)存在一個帶約束的禁忌覆蓋數(shù)組AG覆蓋了全部參數(shù)的取值組合，其規(guī)模為g2，當(dāng)G中有一條邊時，AG中一定存在至少一行違反了約束，違反約束的行至少要被擴(kuò)展成兩行才能滿足約束，所以CAFE(n,G)的規(guī)模至少要增加1，因此，帶有一條邊的圖G滿足NG≥g2+1.

3 試驗(yàn)結(jié)果與分析

本文利用禁忌邊分解方法給出5個典型被測系統(tǒng)的2維約束覆蓋數(shù)組的最小規(guī)模的下限，典型的被測系統(tǒng)的配置如表4所示，這些系統(tǒng)來自于文獻(xiàn)[11]和[16].現(xiàn)有算法生成的2維約束覆蓋數(shù)組的規(guī)模如表5所示.禁忌邊分解方法給出的最小規(guī)模的下限如表6所示.通過與生成的約束覆蓋數(shù)組的規(guī)模進(jìn)行比較，可以看出除了HSS為第2個被測系統(tǒng)生成的規(guī)模16小于下限17，其余結(jié)果都大于等于給出的下限.小于基于禁忌邊分解方法給出的最小規(guī)模下限的約束覆蓋數(shù)組一定不存在，可通過實(shí)際的生成過程來說明.

表4 被測系統(tǒng)的配置

表5 現(xiàn)有算法生成的2維約束覆蓋數(shù)組的規(guī)模

Tab.5 Sizes of the 2-way constrained covering arrays generated by the existing algorithms

方法被測系統(tǒng)12345HSS1016263651SA_SAT1017263652mAETG_SAT1017263752PICT1019273956TestCover1017303854IPOG1117283955IPOG-F1018283854CTWT1017273852

表6 禁忌邊分解方法給出的最小規(guī)模的下限

Tab.6 Lower bounds of the minimum sizes obtained by the forbidden edge decomposing method

被測系統(tǒng)12345最小規(guī)模下限1017253650生成規(guī)模1016263651

圖4是第2個被測系統(tǒng)參數(shù)及取值配置對應(yīng)的圖，圖5和圖6是選取其中第1個參數(shù)的值0和第2個參數(shù)的值1構(gòu)成的兩個頂點(diǎn)子圖.對應(yīng)這兩個頂點(diǎn)子圖，能得到表7和表8給出的CAFE(4,G1,0)和CAFE(4,G2,1)，記為AG1,0和AG2,1，其規(guī)模都為4，表中覆蓋了第1個參數(shù)和第2個參數(shù)的5個取值組合，但是仍有9個取值組合沒有被覆蓋，如表9所示.所以可得出NG≥4+4+9=17，即第2個被測系統(tǒng)的約束覆蓋數(shù)組規(guī)模的最小值不能小于17.違反禁忌邊分解方法給出的最小規(guī)模的下限時，覆蓋數(shù)組一定不存在，沒有違反也不一定能夠說明約束覆蓋數(shù)組不存在，此時只有得到實(shí)際生成的約束覆蓋數(shù)組才能進(jìn)行驗(yàn)證.

Fig.4 Graph of the parameters and value configurations of the 2nd system under test

圖5 第2個被測系統(tǒng)的G1,0

圖6 第2個被測系統(tǒng)的G2,1

表7 第2個被測系統(tǒng)的CAFE(4,G1,0)

表8 第2個被測系統(tǒng)的CAFE(4,G2,1)

表9 第2個被測系統(tǒng)的未被覆蓋的取值組合

Tab.9 Uncovered value combinations of the 2nd system under test

序號參數(shù)1參數(shù)2110212313420522623730832933

4 結(jié) 論

本文提出了一種分析2維約束覆蓋數(shù)組最小規(guī)模的禁忌邊分解方法.通過將圖分解成兩個頂點(diǎn)子圖，生成兩個頂點(diǎn)帶有禁忌邊的覆蓋數(shù)組，計算其規(guī)模和剩余需要覆蓋的取值組合數(shù)，提升了2維約束覆蓋數(shù)組的最小規(guī)模.該方法能夠得到提升的2維約束覆蓋數(shù)組的最小規(guī)模，更逼近真實(shí)值.生成的最小規(guī)?？梢杂糜谠u價現(xiàn)有算法生成的2維約束覆蓋數(shù)組，有助于判斷其是否真實(shí)存在.