基于樹模型和輸入參數關系的組合測試集精簡方法

摘 要:提出了一種精簡組合測試用例集的方法，該方法基于解空間樹模型，利用輸入參數之間的依賴關系來剪裁解空間樹中的枝葉，從而獲得精簡的組合測試用例集。該方法采用回溯算法來實現，在遍歷樹的同時，剪裁解空間樹并輸出組合測試用例。在算法的實現過程中，采用了一些策略以便提高算法的效率并節省空間。實驗結果證明該方法是可行和有效的，對于一些輸入參數依賴關系明確的被測系統，該方法能夠較大幅度地精簡全組合測試用例集。

關鍵詞:組合測試; 解空間樹; 依賴關系

中圖法分類號:TP311.5 文獻標志碼:A

文章編號:1001-3695(2010)03-0928-05

doi:10.3969/j.issn.1001-3695.2010.03.033

Reducing combinatorial test suite based on tree-model by using input parameters relationships

WANG Li-xin1， 2， YANG Jun3 ， WAN Ren-xia1 ， WANG Ming-jun1

(1.College of Information Science Technology， Donghua University， Shanghai 201620， China; 2.School of Electronics Information Engineering， Anhui Institute of Architecture Industry， Hefei 230022， China; 3.Dept. of Mathematics， Anyang Normal University， Anyang Henan 455002， China)

Abstract:This paper proposed a method to reduce combinatorial test suite. The main idea of the method was based on a solution space tree model and input parameters relationships. It first analyzed the dependent relationships among input parameters， and used the relationships to reduce a solution space tree breaches and then generated a small combinatorial test suite.It used back tracking algorithm to realize the idea of the method， and used some strategies to reduce the requirement of space and improve speed of the algorithm effectively. The experiments and case study show that the method is feasible and effective， and it can considerably reduce the number of combinatorial test cases for some SUT with definite dependent relationships among input parameters.

Key words:combinatorial test; solution space tree; dependent relationships

1985年，Mandl[1]第一次提出了組合覆蓋的概念，此后組合測試就成為了黑盒測試的主要方法之一。但是組合測試的最大難題就是組合爆炸引起測試用例數目的龐大，特別是在這些測試用例中有許多是冗余和無效的，因此逐個檢測這些測試用例是很困難的，并且是耗時耗力和不必要的。許多研究者已經提出了各種各樣的方法[2~7]來精簡組合測試用例集，有的方法已經被開發出了測試工具并應用于實際的測試工作中[2~4]。

就組合測試數據生成，文獻[8]給出了基于解空間樹的成對組合測試用例的生成方法，其重點是研究輸入參數的兩兩組合測試用例集的生成方法，但沒有利用輸入或輸出參數間的關系;而文獻[5~7]雖然利用輸入/輸出關系來精簡組合測試用例集，但文獻[5]僅僅給出基本思想，文獻[6，7]卻不考慮到輸入參數之間的依賴關系。本文方法主要研究怎樣利用輸入參數之間的關系來精簡全組合測試用例集，因此具有新穎性和獨特性。

本文方法是基于樹模型并利用輸入參數的關系來生成全組合測試用例集。其主要思想是利用實際存在的輸入參數之間的依賴關系來修剪用于生成測試用例的解空間樹模型的枝葉，然后遍歷這個修剪了的樹模型，輸出生成精簡的測試用例集。

1 求解組合測試用例集的樹模型

全組合測試用例集是由所有輸入參數取值的組合構成的。對于一個帶有多輸入參數的被測系統或程序，假設X是所有輸入參數的集合X={ x1，x2，…，xn}，并且每一個輸入參數有相應的取值域D(x1)， D(x2)， …， D(xn)。 那么完全的組合測試就是測試所有可能的輸入參數取值D(xi)(i=1，2，…，n)的組合。在這種情形下，組合測試用例集T就是所有輸入參數取值域的笛卡爾乘積[5]:

T = D(x1) × D(x2) ×…× D(xn)

T的基數是所有的輸入參數取值域中取值個數的乘積:

|T|=|D(x1)|*|D(x2)|*…*|D(xn)|

可以建立一個解空間樹[8，11]來對應這個組合測試用例集。假設解空間樹TR有n+1層，第一層是根節點v1，比如說對應輸入參數x1，那么v1有|D(x1)|個分支，每個分支表示|D(x1)|個對應的x1的取值;v1分支連接的節點叫做第二層節點，第二層的每個節點都有|D(x2)|個分支，表示|D(x2)|個對應的x2的取值;依此類推，直到第n層節點。在n層的每個節點都有|D(xn)|個分支，表示|D(xn)|個對應的xn的取值，分支連接的節點叫做葉子節點。如此建立的解空間樹，當從根節點遍歷到葉子節點時，其遍歷的路徑上的取值組合起來就是全組合測試用例集T中的一個元素。圖1顯示的是有三個輸入參數的全組合測試用例集所對應的解空間樹，其中n=3，D(x1)={a，b}，D(x2)={c， d， e}，D(x3)={f， g， h}。

在圖1中，當遍歷所有的葉子節點后，所有的從第一層節點到第四層節點的路徑組合的集合P = {acf， acg， ach， adf， adg， adh， aef， aeg， aeh， bcf， bcg， bch， bdf， bdg， bdh， bef， beg， beh}，這個集合P就是輸入參數的全組合測試用例集。

解空間樹有如下的一些性質:

性質1 對應n個輸入參數的解空間樹有n+1層節點。

性質2 解空間樹的葉子節點的個數為n個輸入參數的取值域的取值個數的乘積。

性質3 相同層次的每個節點有相同的分支數目。

在實際的全組合測試用例集T中，測試用例數目往往很大并且有冗余或者是無效的測試用例。既然如此，那么T對應的解空間樹就有冗余或者無效的枝葉。如何知道哪些枝葉是冗余無效的，又如何去剪裁這些冗余無效的枝葉?在下一章中將介紹如何利用輸入參數之間的關系來剪裁這些冗余無效的樹枝或樹葉。

2 輸入參數之間的依賴關系

2.1 輸入參數間的依賴關系分析

通常情況下，考慮較多的是利用輸入/輸出參數的關系來精簡測試用例集[5~7]。對于很多的被測系統或程序來說， 輸入參數之間的關系也是存在的并且是可以分析獲得的。比如，某個輸入參數的某個(或某些)取值是受制于另外的輸入參數的某個(某些)取值。在此情況下，輸入參數取值的全組合集中的某些組合就是沒有意義的，有時對于測試來說甚至是無效的。所以，在建模和生成測試用例的過程中，就應該系統地考慮并分析輸入參數之間的依賴關系。

假如有一被測系統，它的輸入界面有年、月、日和其他輸入選擇框。當選擇2月份后，那么在日選擇框中就有可選的日期集合是1，2，…，28或者1，2，…，29，但絕不會有30或31。換句話說，不可能得到這樣的輸入參數的組合(xxxx年，2月，30日)和(xxxx年，2月，31日)。通常情況下，由于在模塊或組件測試中已經對組合(xxxx年，2月，30日)和(xxxx年，2月，31日)進行了測試，并且在程序代碼中對月日間的輸入關聯性進行了限制，或者即使在模塊或組件中沒有對輸入關聯性設限，那么在系統集成或組合時，也會在所謂的膠水代碼中設限。所以在進行系統級的測試中，就會發現日期的選擇依賴于月份取值，上述的兩個輸入參數的組合對于測試來說就是無效的。

以上的例子可以看出，當某個輸入參數的取值集合隱含著一些對另外的輸入參數取值集合的限制時，就說這些輸入參數之間存在依賴關系，那么這些輸入參數之間的某些取值組合在這種情況下就是不允許的，也是無效的。對于這些無效的組合形成的測試用例，如果單純地用人工的方法來分析剔除是非常麻煩的，而且在有些復雜的情況下有可能不能全部找出這些無效的測試用例。因此有必要采用形式化的方法來分析和尋找全部的無效測試用例。

要使用依賴關系來精簡測試用例，必須對依賴關系進行分析。那么下面給出依賴關系的具體定義。

定義1 設輸入參數組合的形式為DF(X1，X2，…，Xn)，DF={(x1i，x2j，…，xnk)|x1i∈X1， x2j∈X2，…， xnk∈Xn， and i∈{1，2，…， |X1|}， j∈{1，2，…，|X2|}，…， k∈{1，2，…，|Xn|}}，DF是T=D(x1)×D(x2)×…×D(xn)的一個子集。假設Y和Z均為{X1，X2，…，Xn}的子集，對于DF中的值r來說，當其中任意兩個組合元素u，v中對應于X的那些輸入參數分量的值均相等時，則有u，v中對應于Y的那些輸入參數分量的值也相等，稱X決定Y，或Y依賴于X，記為X→Y[9]。

為了討論的方便，提出了以下兩個假設:

假設1 已經有了一個依賴關系集合DR。

假設2 依賴是單向的、可傳遞的，但沒有循環。

從依賴的定義形式上看，也適合于Armstrong公理及三個推理，即自反律、增廣律和傳遞律，并且可適用于三個規則，即合并規則、偽傳遞規則和分解規則[9]。

在依賴集DR中并沒有規定無冗余的依賴關系。消除DR中的冗余將有利于解空間樹的構建。根據相關的理論[9]可得出每個依賴關系集DR都有其最小依賴關系集，且前人的研究結果已給出了求解最小依賴關系集的方法。

為了闡述相關概念和方法的方便，本文對以上依賴關系定義進行了形式上的變換。先看兩個輸入參數之間的依賴關系定義。

定義2 假設有兩個輸入參數xi和xj，它們的取值集合為D(xi)和D(xj)。其中，D(xi)={D1(xi)， D2(xi)， …， Dk(xi)| 1≤t， m≤k， t≠m， Dt(xi)∩Dm(xi) =}，D(xj)={ D1(xj)， D2(xj)， …， Dq(xj)}。如果D(xj)依賴于D(xi)， 那么可以說在D(xi)和D(xj)中子集之間總有依賴關系。本文用另外一種形式f(a∈Dt(xi))=b∈Ds(xj) (1≤t≤k， 1≤s≤q) 來表示這種關系。

如圖2所示，設A、B、C、D、E是輸入參數，對于多輸入參數之間的依賴關系，具體可以分為這樣幾類:

a)1對1，就是一個參數取值集的子集或全集依賴于另外一個參數取值集的子集或全集，如圖2中的B依賴于A;

b)1對n，多個參數取值集的子集或全集依賴于另外一個參數取值集的子集或全集，如圖2中的D和E依賴于C;

c)n對1，一個參數取值集的子集或全集依賴于另外多個參數取值集中的子集或全集，如圖2中的D依賴于B和C;

d)n對m，多個參數取值集中的子集或全集依賴于另外多個參數取值集中的子集或全集。

比如，年Y值域是{1999，2000}，月M值域是{1， 2， …， 12}， 日D值域是{1， 2， …， 31}。把Y的值域分為{{平年:1999}， {閏年:2000}}兩部分。把M的值域分為{{1，3，5，7，8，10，12}， {4，6，9，11}， {2}}三部分，那么D的值域就分為{{1~28}， {1~29}，{1~30}，{1~31}}四部分。

依賴關系如下:

f(y∈{平年:1999})=d∈{{1~28}，{1~30}，{1~31}};

f(y∈{閏年:2000})=d∈{{1~29}，{1~30}，{1~31}};

f(m∈{ 1，3，5，7，8，10，12})=d∈{{1~31}};

f(m∈{4，6，9，11})=d∈{{1~30}};

f(m∈{2})=d∈{{1~28}，{1~29}};

f(y∈{1999} and m∈{2})=d∈{{1~28}};

f(y∈{2000} and m∈{2})=d∈{{1~29}}。

對于上面的例子，如果不考慮輸入參數的關系進行全組合測試，那么全組合的測試用例數為2×12×31=744。 但由于在模塊或組件編碼實現過程中已經考慮了這些依賴關系，并且在實現代碼中作了一些限制，那么對這些模塊或組件組成的系統進行黑盒測試時，有些輸入參數的組合就不能被選擇了，如(1999，2，29)等，換句話說，系統測試中不可能對這個用例進行測試，或者說該用例是無效的，需要從全組合測試集中移除。

2.2 利用依賴關系剪裁解空間樹

下面說明對于不同類型的依賴關系，如何對解空間樹進行剪裁。以下是幾種形式的依賴關系進行的剪裁過程。

a)剪裁相鄰的下層分支。對于圖1來說，如果有依賴f(x1∈{a})=x2∈{c}，那么第一層節點的狀態值為a的分支向下遍歷，找到與分支值為a相連的節點，然后把給節點上的除c以外的分支(包括子樹)全部剪除。見圖3的精簡示例1的根節點的左子樹。

b)剪裁不相鄰的下層分支。對于圖1來說，如果有依賴f(x1∈{b})=x3∈{ f }，從根節點的分支值為b的分支向下遍歷，找到x3所表示的那層節點，只保留所有節點下分支值為f的分支。見圖3的精簡示例1的根節點的右子樹。

c)剪裁依賴關系左部是多條件的下層分支。對于圖1來說，如果有依賴f(x1∈{a} and x2∈g0gggggg)=x3∈{ g }，那么從根節點的分支值為a的分支向下層遍歷到依賴關系式左部的x2所表示的那個節點，再尋找分支為d所連接的那個節點，刪掉除g以外的其他分支。見圖4的精簡示例2。

通過上面的這幾個示例可以看到，用給定的依賴關系來剪裁解空間樹上的冗余無效枝葉的方法并不復雜。這里為了討論簡單，本文給出了明確的條件限制(兩個假設)。如何找到和取舍這些依賴關系以使依賴關系的簡單化是筆者下一步的研究目標。本文的重點是如何通過已知的依賴關系來剪裁解空間樹，以求得小的測試用例集。

3 求解組合測試用例集的樹模型算法

3.1 基于解空間樹的全組合測試用例生成流程

全組合測試用例的生成有多種方法，用n重循環來實現是算法實現的方法之一。在循環中檢查每個n維的參數組合，如果滿足依賴集中的某個依賴關系就輸出，否則就拋棄。這種方式簡單明了，但當n較大或|D(xi)|較大時，該方法時間耗費將是極高的，其時間復雜度為O(∏ni=1|D(xi)|)。

然而利用解空間樹來獲得全組合測試用例就是為了以較小的代價獲得所需要的組合測試用例集。當然基于解空間樹也有多種方式可以實現測試用例集的精簡:

a)先生成解空間樹，再利用依賴關系裁剪枝和葉;然后遍歷裁剪后的樹，生成測試用例集。該方法簡單清晰，容易實現，但占用空間較大，很多情況下是不可行的。

b)用回溯法來求解。對解空間樹進行遍歷，同時利用依賴關系對樹的枝葉進行剪裁;當遍歷到葉子時，把符合條件的根到葉子之間的路徑組合輸出。這種方法占用空間較少，時間復雜度也相對比方式a)要好;其次是應用比較靈活，可以適應特點不同的依賴關系集。該方式的算法實現和提高算法效率的策略是本文討論的主要方面。

基于解空間樹生成全組合測試用例集的基本流程如下:

a)尋找輸入參數依賴關系，生成依賴關系集，并且利用已知的關系理論和方法求出最小依賴關系集;

b)對該依賴關系集按照依賴和被依賴的方向畫出依賴圖，通過依賴圖得出輸入參數的排列順序表;

c)根據輸入參數排列順序決定輸入參數在解空間樹中的層次位置;

d)遍歷解空間樹并利用輸入參數關系來生成精簡了的測試用例集。

3.2 遍歷解空間樹的回溯算法及提效策略

當依賴關系和解空間樹建立好后，本文采用回溯法來遍歷、剪裁枝葉并輸出全組合測試用例。回溯法的基本步驟如下:

a)針對所給問題定義問題的解空間。對于多輸入參數的全組合測試用例的生成問題，可利用解空間樹的方式表達。具體的問題定義已在第1章中進行了詳細的說明。

b)確定易于搜索的解空間結構。采用回溯法生成全組合測試用例，首先要說明非葉子樹節點的結構。非葉子樹節點中有一個分支數目域，有Dm(Dm=maxl≤i≤n|D(xi)|)個域用于存儲分支值，即D(xi)中的取值;另外有Dm個域用于存儲分支節點鏈接的，即存儲和D(xi)中的取值相對應的分支節點鏈接，用于指向下一層節點。其中同層的節點使用的域數目是相同的，但不同層的域使用數目可能不同，即有空閑的域存在。最下一層節點的分支值相對應鏈接域存放葉子的標志，但為了表達的直觀性，在上文的相關圖中，本文還是畫出了葉子節點。

此外，本文定義與依賴關系相關的一些概念。對于形如f(xi∈Si and xj∈Sj)=xk∈Sk的依賴關系，稱等式“=”的左右兩邊為被依賴部分和依賴部分，被依賴部分xi和xj為被依賴參數取值變量，Si和Sj為被依賴參數取值變量xi和xj的取值集合;依賴部分的xk為依賴參數取值變量，Sk為依賴參數取值變量xk的取值集合。兩部分中，參數的先后順序是按照在樹中的層次來排的，層次高的排在前面，層次低的排在后面。

為了回溯法編程實現的方便，把依賴關系簡化為1∶1和n∶1兩類。其中被依賴參數的取值集合是單個元素，并且把形如f(xi∈{a} and xj∈g0gggggg)=xk∈{ g }的依賴關系寫成字符串形式:“adg”(假設i、j和k是相連的數字)，該串的特點就是最后的字符代表依賴參數值，“g”前面的子串是被依賴參數串，它們分別屬于不同輸入參數取值集合。如果i、j和k不是相連的數字，如f(x1∈{a} and x3∈g0gggggg)=x4∈{ g }，那么依賴關系字符串形式就要寫成“a?dg”，用“?”表示中間的那層節點是任意的取值。

c)以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。基于解空間樹的組合測試用例生成的回溯法的基本任務就是搜索一條從根節點到葉子節點的路徑值的組合并輸出。在解空間樹中，按深度優先策略，從根節點出發搜索解空間樹，搜索至解空間樹的任意一點時，先判斷該節點是否是要保留的，還是要把它剪裁掉，這就需要與依賴關系進行比較。遍歷的同時依照依賴關系進行枝葉剪裁，主要是為了去掉不合法的無效測試用例，同時也是為了減少遍歷的比較次數。當到達葉子節點時，如果符合依賴關系則輸出從根節點到葉子節點之間的路徑值組合，即輸出一個有效的全組合測試用例;然后再尋找相同父節點中的其他符合要求的葉子節點，逐層向其祖先節點回溯，搜索其祖先節點的其他兄弟子樹，繼續按深度優先策略搜索。

把輸入參數的依賴關系稱做剪枝函數。在圖3的精簡示例1中，對于節點1和2之間僅僅有依賴關系f(x1∈{a})=x2∈{c}，可簡化表示為a→c;對于節點1和2之間如果有依賴關系f(x1∈{a})=x2∈{c，d}，可表示為a→/e，其含義是把a分支所連的下層節點中e分支剪掉，而保留分支c和d。這種形式上的變化主要是根據實際依賴關系集合的特點，是為了盡可能地提高編程效率之用的。

此外，把形如1∶1的依賴關系叫做二參數依賴關系，把n∶1的依賴關系稱為多參數依賴關系。在n∶1中的形如f(x1∈{a} and x2∈g0gggggg)=x3∈{ g }的依賴關系稱為三參數依賴關系，那么可以有四參數依賴關系，最高的可以為n參數依賴關系。為了減少程序中查找依賴關系的次數，提高程序的運行效率，可以把依賴關系按照參數的數目分為若干個依賴關系集合，可以在遍歷到不同層次時應用相應的依賴關系子集，使得所需要的比較運算次數減少，從而更快地找到被剪裁的枝葉。

3.3 回溯算法的實現及其復雜度分析

生成組合測試用例的回溯算法描述如下:

BackTrackForTestcase()

{輸入參數的符號化表示;

依賴關系的串化表示;

{依賴關系字符串分層集合化;

建立節點棧、用例字符串棧和分支遍歷起始位置棧;

建立根節點; /*調用建立節點函數，填分支值，并根據依賴關系在鏈接域中填相應的標志:①有子樹，②無子樹，③鏈接域對應的子樹已被遍歷，④是葉子*/

根節點首個分支值入用例字符串棧，相應鏈接域置③;

根節點入節點棧;

下次遍歷根節點的起始位置入分支遍歷起始位置棧;

iLevel=1; //iLevel表示層次

while (iLevel>=0)

{{if (向下遍歷)

{if (下一層節點是非葉子)

{建立非葉子節點;根據鏈域的標志向下遍歷; }

if(下層節點是葉子)

{建立葉子節點; 遍歷葉子節點;

對符合依賴關系條件的用例字符串輸出;

回溯到上層節點; }

else //是回溯

{獲得回溯的節點信息; 遍歷該節點的下一個分支;

如果已經遍歷到了該節點的最后一個分支，

那么再向上一層回溯; }

} }

}

在上述的回溯算法中，剪枝函數體現在每層節點的建立過程中。當調用建立節點的函數時，分支值被填入的同時，也把該值入字符串棧，并與依賴關系字符串進行比較。如字符串棧中的字符串是依賴關系字符串集合中的元素，那么在該節點的該分支值對應的鏈接域填入標志①，表示該節點有子樹;如字符串棧中的字符串不是依賴關系字符串集合中的元素，那么在該節點的該分支值對應的鏈接域填入標志②，表示無子樹;當該分支值已經入字符串棧，且該節點已經入節點棧，那么該分支值對應地在鏈接域中填入標志③，表示該分支值對應的子樹已被遍歷;對于第n層節點來說，如字符串棧中的字符串是依賴關系字符串集合中的元素，那么在該節點的該分支值對應的鏈接域填入標志④，表示是葉子。

假設一個SUT的輸入參數為n個，每個參數的取值個數用|D(i)|(i=1，2，…，n)表示。

1)空間復雜性 用回溯法解題的一個顯著特征是在搜索過程中動態產生問題的解空間。在任何時刻，算法只保存從根節點到當前擴展節點的路徑。如果解空間樹中從根節點到葉子節點的最長路徑長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內存空間。

2)時間復雜性 該算法在最壞的情況下，它的時間復雜度為O(|D(x1)|*…*|D(Xn)|)。在實際的算法過程中，由于有一些輸入參數的依賴關系，在算法的執行過程中同時根據這些依賴關系來對解空間樹進行剪枝的，就會不同程度地減少遍歷的節點數目。特別是當建立的解空間樹的剪裁分支是離根節點越近，那么被剪裁的節點數目就越大一些，遍歷的時間花費將大大減少。

輸入參數的全組合測試通常是在測試要求比較嚴格的情況下進行的，但由于組合爆炸的原因，測試所有的用例是困難的，然而通過輸入參數之間的依賴關系可以精簡測試用例集。利用回溯法對整個解空間樹進行遍歷，這樣不會遺漏有用的測試用例，同時利用輸入參數之間的依賴關系剪裁枝葉，減少了算法遍歷的節點數。這樣就能使得算法對空間資源需求變得可行，時間上的效率也得到很大的改進和提高。

4 實驗及實例分析

為了檢驗上述基于解空間樹模型的回溯法在生成全組合測試用例過程中的實際性能和效果，本文編程實現了基于輸入參數的依賴關系來精簡全組合測試用例集的算法。

4.1 實例研究

先看這樣一個實例:有一個交友網站的頁面[10]，它有八個文本輸入框，一個單選按鈕(性別)，九個單選下拉列表(地區(省、市(區))，出生年、月、日，婚姻狀況，最高學歷，職業，月薪)，一個多選框，一個確認按鈕。其中的出生年、月和日，省和市(區)在程序中已經進行了約束。

對實例中幾個主要輸入參數進行了依賴關系的分析，把輸入參數的類型分為單輸入和可多選輸入。對上述的實例頁面來說，九個單選下拉列表中的六個是本文測試的重點。表1是該頁面的輸入參數及各參數的具體取值。盡管該頁面已經有了一些約束關系，但仍可從中發現一些輸入參數之間的約束關系沒有建立。比如，性別和從事職業有依賴關系，男性是不能選擇空姐這個職業的;職業和月薪有依賴關系，一個藍領月薪兩萬以上可信度低;年齡和最高學歷有依賴關系，一個18歲的人是博士后的可能性太低;年齡和婚姻也有依賴關系，一個20歲的男性已婚是違法的等。從這些輸入中可以找出盡可能多的依賴關系，并在程序中加以限制，這樣對于信息的正確性輸入和組合測試用例的精簡是有益的。

表1 實例頁面的主要輸入參數及其取值表

主要輸入參數參數取值個數具體取值

性別(S)2男，女

出生年(Y)591931，1932，1933，…，1988，1989

婚姻(M)3未婚，離異，喪偶

學歷(E)6 大專，本科，雙學士，碩士，博士，博士后

職業(P)24企業家，高級管理，經理，白領，工程師，藍

領，職員，留學生，公務員，教師，醫生…

月薪(W)6<3k，3k~5k，5k~8k，8k~12k， 12k~20k，>20k

表2列出了該頁面的輸入參數之間是否存在依賴關系。在這個實例頁面中，為了測試的方便，本文把出生的年份取值范圍縮小，假設為1961—1989。那么利用找出的輸入參數之間的依賴關系，運行回溯算法程序得到了相應的組合測試用例結果，見表3的最后一項。

表2實例頁面的輸入參數依賴關系表

輸入參數性別(S) 出生年(Y) 婚姻(M) 學歷(E) 職業(P) 月薪(W)

性別(S)√

出生年(Y)√√√

婚姻(M)√

學歷(E)√

職業(P)√√√

月薪(W)√

4.2 實驗數據分析

本文對幾個實際的和理論上的例子用回溯算法程序進行了實驗。所有的實驗都是在Intel2.2 GHz CPU，內存512 MB的PC機上進行的;操作系統是Windows XP，算法實現用C++ Builder 6。在每個實驗之前必須先建立一個初始化文本文件，在其中包含有輸入參數的個數、每個輸入參數的具體符號化取值集合、依賴關系的按層數的分類集合。實驗運行結果如表3所示。表中的1、2、6、7項是實際的被測程序的實驗項目結果，而3、4、5項是作為理論上的假設項目的實驗結果。

表3 回溯算法實際運行結果表

序號 實驗項目依賴關系數全組合用例數A 精簡后用例數R R/A/% 運行時間/s

14462568834.40.01

24472564015.6 0.01

3 55103 125425 13.6 0.1

456 11 15 625 2 750 17.61

5661146 656 7 77616.63

632×43×24159 2161 413 15.30.1

721×291×31×62×24111150 336 106 70470.925

注:表中實驗項目欄中的參數說明:mn——n輸入參數個數，m為每個輸入參數的取值個數;mn ×qp——共有輸入參數個數為n+p，其中有n個參數的取值個數為m，p個輸入參數的取值個數為q。

從表3中可以看出，利用輸入參數的依賴關系可以不同程度地精簡全組合的測試用例數目。其中精簡后的用例集中的用例數和所有全組合用例數之比最大為70.9%，最小為13.6%，這說明應用輸入參數之間的依賴關系對于一些SUT可以較大幅度地精簡全組合測試用例集或者是剔除無效的用例。對于程序運行時間上的可行性，總體看來是可以接受的。

5 結束語

本文提出了一種基于樹模型和輸入參數關系的組合測試用例集的精簡和生成方法。這種方法首先用解空間樹來表示多輸入參數的組合測試用例，并給出了解空間樹和輸入參數之間的關系;然后分析了輸入參數之間的依賴關系，并給出了兩種用于不同目的依賴關系的定義形式，總結了依賴關系的幾種分類，說明了如何利用依賴關系來剪裁解空間樹的冗余無效的枝葉;最后給出了生成解空間樹、裁剪冗余無效枝葉和生成組合測試用例集的算法。實驗表明該方法在一定的范圍中具有較好的性能和實際的應用性。

由于輸入參數的全組合數目龐大，對于大數目的全組合集來說，用該方法精簡后的測試用例數目仍然是比較大的，如果用人工來進行測試，這將是很大的挑戰。因此，利用輸入參數之間的依賴關系來精簡全組合測試用例集，其仍將有一定的應用局限性。利用輸入參數關系來精簡組合測試用例集合往往會有很好的效果，但是得到這些關系卻是比較困難的。本文是在假設輸入參數依賴關系已經存在的前提下，提出如何利用其來精簡組合測試用例集的。因此如何獲得輸入參數之間的依賴關系將是筆者下一步的研究方向之一。此外，研究如何更進一步精簡測試用例集或者說如何按照一定的標準挑選更典型的測試用例，也是筆者下一步研究的目標。參考文獻:

[1]MANDL R. Orthogonal Latin squares: an application of experimental design to compiler testing[J]. Communications of the ACM， 1985， 28(10): 1054-1058.

[2]COHEN D M， DALAL S R， FREDMAN M L， et al. The AETG system: an approach to testing based on combinatorial design[J]. IEEE Trans on Software Engineering， 1997， 23(7): 437-444.

[3]TAI K C， LEI Y. A test generation strategy for 2-dimension testing[J]. IEEE Trans on Software Engineering， 2002， 28 (1): 109-111.

[4]WILLIAMS A W， PROBERT R L. A measure for component interaction test coverage[C]// Proc of ACS/IEEE International Confe-rence on Computer System and Applications.Washington DC: IEEE Computer Society， 2001:304-314.

[5]SCHROEDER P J， KOREL B. Black-box test reduction using input-output analysis[C]// Proc of ACM SIGSOFT International Symposium on Software Testing and Analysis.New York: ACM Press， 2000:173-177.

[6]SARAPH P， LAST M， KANDEL A. Test case generation and reduction by automated input-output analysis[C]// Proc of IEEE International Conference on Systems， Man Cybernetics. Washington DC: IEEE Computer Society， 2003: 5-8.

[7]CHENG C， DUMITRESCU A， SCHROEDER P. Generating small combinatorial test suites to cover input-output relationships[C]// Proc of the 3rd International Conference on Quality Software. Washington DC: IEEE Computer Society， 2003: 76-82.

[8]史亮，聶長海，史寶文.基于解空間樹的組合測試數據生成[J]. 計算機學報，2006，29(6):849-857.

[9]王珊. 數據庫系統概論[M]. 北京:清華大學出版社，2006.

[10][EB/OL].http://www.juedui100.com/register/register1.jsp.

[11]CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to algorithms[M]. Cambridge: MIT Press， 2001.