程 浩，周 輝，錢 巨

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106)E-mail：jqian@nuaa.edu.cn

1 引 言

Web服務(wù)是一種通過網(wǎng)絡(luò)支持可互操作的端到端交互的軟件系統(tǒng)(1)http://www.w3.org/TR/ws-gloss.Web服務(wù)因其所具有的高通用性、可互操作性與可重用性而受到廣泛關(guān)注.與其他軟件系統(tǒng)不同，Web服務(wù)使用了基于XML的WSDL標(biāo)準(zhǔn)文檔來描述服務(wù)接口，包括服務(wù)功能、輸入和輸出，對(duì)外隱藏了復(fù)雜業(yè)務(wù)邏輯的實(shí)現(xiàn).

Web服務(wù)與其他軟件系統(tǒng)一樣，也存在質(zhì)量問題，而且由于Web服務(wù)廣泛用于各種應(yīng)用，尤其是電子商務(wù)應(yīng)用，問題可能會(huì)更嚴(yán)重.為此，研究人員為Web服務(wù)的測試技術(shù)付出了很多努力[1]，在測試數(shù)據(jù)生成[2，3]、單元測試[4，5]、測試預(yù)言[6]、故障注入技術(shù)[7]、回歸測試[8]、安全測試[9]等方面的研究也取得了很多重要成果，但是挑戰(zhàn)依然存在.

Web服務(wù)測試的挑戰(zhàn)之一是生成高覆蓋率的測試數(shù)據(jù).人們[1]提出了多種測試數(shù)據(jù)生成方法，包括基于 XML Schema、基于模型、基于規(guī)約等方法，其中，基于 XML Schema 的方法根據(jù) WSDL 文檔提供的數(shù)據(jù)類型信息生成測試數(shù)據(jù)，基于模型的方法通過構(gòu)建服務(wù)內(nèi)部的行為模型(如自動(dòng)機(jī))來生成測試數(shù)據(jù)[10]，基于規(guī)約的方法一般根據(jù) Web 服務(wù)輸入和輸出的前置與后置條件來生成測試數(shù)據(jù)[11].相較而言，基于 XML Schema 的方法快而簡單，但只是根據(jù)粗粒度的數(shù)據(jù)類型信息生成數(shù)據(jù)，因此無法確保能夠生成有意義的代表性測試數(shù)據(jù).基于模型的方法主要適用于 BPEL 組合服務(wù)，對(duì)于原子服務(wù)來說該方法顯得過于復(fù)雜.與上述兩種方法相比，基于規(guī)約的測試數(shù)據(jù)生成方法不僅能夠生成更合理的服務(wù)輸入，而且在為原子服務(wù)生成測試數(shù)據(jù)時(shí)通常要比基于模型的方法更高效.

對(duì)于原子服務(wù)，文獻(xiàn)[12]提出了一種基于規(guī)約的Web服務(wù)測試數(shù)據(jù)生成方法，先用簡單的取值范圍約束(如(a≥0∧a≤10)∧(b≥0∧b≤10))來指定服務(wù)的輸入條件，再基于區(qū)間劃分技術(shù)生成測試數(shù)據(jù)，測試數(shù)據(jù)是通過選取每個(gè)輸入?yún)?shù)的數(shù)據(jù)分區(qū)中的值組合得到的，但該方法并不支持不同服務(wù)輸入?yún)?shù)之間的復(fù)雜約束，如a+b

在更廣泛的測試數(shù)據(jù)生成研究領(lǐng)域中[15,16]，還有一些根據(jù)規(guī)約約束生成測試數(shù)據(jù)的黑盒方法，但大多數(shù)只關(guān)注如何求解約束，并未解決如何操縱約束以生成高覆蓋率測試數(shù)據(jù)的問題[17]，而且很少有研究方法能夠定義明確的規(guī)約約束級(jí)測試覆蓋準(zhǔn)則，并利用這些準(zhǔn)則指導(dǎo)約束求解以生成測試數(shù)據(jù).

考慮到上述問題，本文提出了一種基于規(guī)約約束的測試數(shù)據(jù)生成方法，用一階邏輯公式定義服務(wù)輸入和輸出的規(guī)約約束，能夠根據(jù)給定的規(guī)約約束生成高覆蓋的測試數(shù)據(jù).本方法的重點(diǎn)是測試原子服務(wù)，并支持復(fù)雜的一階邏輯約束，如(3*a+12)*2<100，以及描述變量間關(guān)聯(lián)關(guān)系的約束，如x+y>z.本文使用Z3 SMT約束求解器生成測試數(shù)據(jù)，而且為了生成高覆蓋率的測試數(shù)據(jù)，引入幾種規(guī)約約束級(jí)覆蓋準(zhǔn)則，并提出生成滿足這些準(zhǔn)則的測試數(shù)據(jù)的新算法.實(shí)驗(yàn)通過測試兩個(gè)目標(biāo)服務(wù)得到的結(jié)果表明，使用新的測試覆蓋準(zhǔn)則與相應(yīng)的測試數(shù)據(jù)生成算法，可以實(shí)現(xiàn)更高的代碼覆蓋率，因此本文提出的方法能夠提高Web服務(wù)測試數(shù)據(jù)的質(zhì)量.

2 背 景

2.1 Web服務(wù)

一個(gè)Web服務(wù)包含服務(wù)實(shí)現(xiàn)和服務(wù)接口描述，后者通常是由 WSDL 文檔表達(dá).WSDL 文檔內(nèi)容由抽象類型定義和部署描述兩部分組成.抽象類型定義包括 types、message、portType 等 XML 元素，其中 types 元素描述了該服務(wù)中使用的數(shù)據(jù)類型，可以是簡單數(shù)據(jù)類型如整型、字符串等，也可以是類似于 C 語言結(jié)構(gòu)體的復(fù)雜類型；message 元素描述了服務(wù)的輸入和輸出；portType 元素定義了服務(wù)支持的操作，操作就像是面向?qū)ο笳Z言中類的一個(gè)方法.部署描述定義了服務(wù)的 URL 和調(diào)用服務(wù)的協(xié)議.這些元素中，types 元素是測試數(shù)據(jù)生成的關(guān)鍵.

圖1是描述Web服務(wù)Sum的WSDL文檔，Sum服務(wù)有一個(gè)sum操作，由部分可知該服務(wù)接受三個(gè) int 類型的參數(shù)a，b，c，用戶可以通過URL地址調(diào)用這個(gè)服務(wù)，該服務(wù)的實(shí)現(xiàn)可以用任何語言，但對(duì)調(diào)用者來說是透明的，而WSDL文檔是用戶可見的.

2.2 基于規(guī)約的 Web 服務(wù)測試

在基于規(guī)約的原子Web服務(wù)測試中，每個(gè)測試目標(biāo)由一個(gè)三元組表示：

F=，

其中S表示待測的原子Web服務(wù)，O是服務(wù)S中可被調(diào)用的操作，C是由服務(wù)S中若干前置條件和后置條件組成的約束系統(tǒng).前置條件定義了服務(wù)輸入應(yīng)滿足的約束，用于生成Web服務(wù)的測試數(shù)據(jù)，后置條件則定義了服務(wù)輸出應(yīng)滿足的約束，用于檢查測試數(shù)據(jù)的執(zhí)行結(jié)果.

圖1 WSDL文檔示例
Fig.1 An example WSDL document

2.3 基于 SMT 約束求解器的測試數(shù)據(jù)生成

為了表達(dá)Web服務(wù)中輸入和輸出參數(shù)之間的關(guān)聯(lián)關(guān)系，本文擬采用一階邏輯公式定義約束，并基于SMT(Satisfiability Modulo Theories，可滿足性模理論)約束求解器[18]生成測試數(shù)據(jù).SMT 約束求解器用于查找滿足一階邏輯公式的一組數(shù)據(jù)，被廣泛用于軟件驗(yàn)證、測試用例生成等方面.

Z3是微軟發(fā)布的一款 SMT 約束求解器[19]，支持各種復(fù)雜的理論公式，包括算術(shù)表達(dá)式、布爾表達(dá)式、邏輯表達(dá)式等.本文將基于Z3約束求解器生成 Web 服務(wù)測試數(shù)據(jù).

但是直接使用Z3求解約束得到的測試數(shù)據(jù)無法保證能夠覆蓋所有的輸入方案，例如，對(duì)于以下約束：

a>20∨b<10∨a>b，

使用Z3求解可以得到一個(gè)有效的測試數(shù)據(jù)(a=15，b=12)，該數(shù)據(jù)只覆蓋了條件子句a>b，未覆蓋a>20和b<10，這種低覆蓋率的測試數(shù)據(jù)會(huì)影響Web服務(wù)故障的發(fā)現(xiàn).

3 基于Z3的測試數(shù)據(jù)生成方法概述

為了解決以上問題，本文提出了一種基于一階邏輯公式規(guī)約和Z3約束求解器的高覆蓋率測試數(shù)據(jù)生成方法，如圖2所示.

圖2 測試數(shù)據(jù)生成過程Fig.2 Test data generation process

方法的輸入包括待測Web服務(wù)的WSDL文檔、服務(wù)對(duì)應(yīng)的前置條件約束以及選定的覆蓋準(zhǔn)則，方法的輸出是一個(gè)滿足輸入覆蓋準(zhǔn)則的測試集.測試數(shù)據(jù)生成的過程包括兩個(gè)主要步驟：1)根據(jù)覆蓋準(zhǔn)則進(jìn)行約束轉(zhuǎn)換；2)基于Z3 SMT約束求解器的測試數(shù)據(jù)生成.生成的測試數(shù)據(jù)將被封裝于SOAP包中用于 Web 服務(wù)測試.表1給出了測試數(shù)據(jù)生成的一個(gè)實(shí)例，其中最后一列的測試數(shù)據(jù)是根據(jù)第一列中給定的前置條件生成的.本文主要關(guān)注整數(shù)類型的變量.

表1 測試數(shù)據(jù)生成示例Table 1 An example for test data generation

3.1 Web 服務(wù)規(guī)約語言

Web服務(wù)的測試規(guī)約由前置條件和后置條件給定，它們都是用一階邏輯公式表達(dá)的約束，而且是 SMT 求解器可求解的.與傳統(tǒng)范圍約束(如a<10)只能限定單個(gè)變量不同，一階邏輯公式約束能夠定義不同變量之間的關(guān)聯(lián)關(guān)系，例如，a=b或a+b<10 等描述的復(fù)雜關(guān)系.

規(guī)約語言的語法如圖3所示，其中 Variable，Value分別表示約束變量與常數(shù)值，expr，bexpr 分別是算術(shù)表達(dá)式和布爾表達(dá)式，constraint 表示約束中的邏輯公式.

圖3 規(guī)約語法Fig.3 Grammar of the specification language

規(guī)約語法中的約束變量對(duì)應(yīng)于服務(wù)操作的輸入或輸出參數(shù)，例如，對(duì)于圖1中的 Sum 服務(wù)，參數(shù)a可以表示為：

value(svc/sum/a)，

其中，svc是給定服務(wù)的宏定義，svc/sum表示Sum服務(wù)支持的操作sum.假定Sum服務(wù)的輸入?yún)?shù)必須滿足都相等或者都不相等，對(duì)應(yīng)的規(guī)約如圖4所示.規(guī)約可以保存在獨(dú)立的文件中，也可以集成到XML文檔中.規(guī)約提供了更多服務(wù)操作的輸入空間信息，通過全面探索輸入空間可以獲得更高覆蓋率的測試數(shù)據(jù).

圖4 規(guī)約示例Fig.4 An example specification

3.2 WSDL 描述中的限定

目前 WSDL 規(guī)范支持一種限定(restriction)機(jī)制，以限制服務(wù)輸入和輸出的取值，常用的限定類型包括范圍限定和枚舉限定.范圍限定用于限制變量的最大或最小值，圖5(a) 表示參數(shù)a的取值范圍是[0，10].枚舉限定給出了變量的有效取值集合，圖5(b) 限定參數(shù)b只能取0或1.

(a)范圍限定 (b)枚舉限定

除上述兩種限定之外，還有其他更為復(fù)雜的限定在本文中沒有用到.為了生成合理的測試數(shù)據(jù)，WSDL 描述中的這些限定將被轉(zhuǎn)換成邏輯約束，并加到約束系統(tǒng)中.結(jié)合圖4和圖5可得，Sum 服務(wù)中 sum 操作完整的前置條件如下：

Csum=(a≥0∧a≤10)∧(b=0∨b=1)∧

((a≠b∧b≠c)∨(a=b∧b=c))，

本文將使用該約束生成測試數(shù)據(jù).

4 基于規(guī)約約束的測試覆蓋準(zhǔn)則

為了對(duì)給定的Web服務(wù)生成充足的測試數(shù)據(jù)，本文定義了幾種規(guī)約約束級(jí)測試覆蓋準(zhǔn)則，涵蓋了更多基于規(guī)約約束的情形，基于這些準(zhǔn)則進(jìn)行測試可以為指定服務(wù)測試更多的輸入方案.規(guī)約約束級(jí)測試覆蓋準(zhǔn)則包括判定覆蓋、條件覆蓋、判定條件覆蓋、范式子句覆蓋，這些準(zhǔn)則借鑒了白盒測試中代碼級(jí)覆蓋的部分概念.

4.1 判定覆蓋

在白盒測試中，判定覆蓋要求測試用例能夠覆蓋每個(gè)判定中真或假的結(jié)果.在基于規(guī)約約束的測試中，判定覆蓋則要求測試數(shù)據(jù)不僅要滿足規(guī)約約束(有效數(shù)據(jù))，還要滿足約束的否定形式(無效數(shù)據(jù)).

定義1.(判定覆蓋) 對(duì)于給定前置條件C的服務(wù)，如果測試集T滿足以下條件：

?t∈T，eval(C，t)=true∧?t′∈T，eval(C，t′)=false，

就稱測試集T滿足判定覆蓋，其中eval(C，t) 用于判斷測試數(shù)據(jù)t是否滿足約束C.

對(duì)于3.2節(jié)給出的規(guī)約約束Csum，測試集Tdc(a，b，c)={(1，1，1)，(20，1，1)} 覆蓋了有效數(shù)據(jù)和無效數(shù)據(jù)，因此該測試集滿足判定覆蓋.

4.2 條件覆蓋

判定覆蓋無法保證給定的測試集能夠覆蓋所有產(chǎn)生有效測試數(shù)據(jù)或者無效數(shù)據(jù)的不同情形.例如，Tdc沒有覆蓋b=0的情況.一種提高覆蓋率的途徑是要求測試集能覆蓋每個(gè)基本條件的不同結(jié)果.在白盒測試中，這種覆蓋叫做條件覆蓋，本文將其引入到規(guī)約約束級(jí)覆蓋準(zhǔn)則中.在基于規(guī)約約束的測試中，條件覆蓋要求測試數(shù)據(jù)不僅要滿足服務(wù)參數(shù)前置條件中的原子條件，還要滿足各原子條件的否定形式.

定義2.(條件覆蓋) 對(duì)于給定前置條件C的服務(wù)，如果測試集T滿足以下條件：

?e∈BExpr(C){?t∈T，eval(e，t)=true
∧?t′∈T，eval(e，t′)=false}，

就稱測試集T滿足判定覆蓋，其中BExpr(C)是前置條件C中原子條件的集合.

對(duì)于3.2節(jié)給出的規(guī)約約束Csum，測試集Tcc(a，b，c)={(1，1，1)，(-1，0，-1)，(20，0，20)} 能保證覆蓋所有的原子條件及各自的否定形式，因此該測試集滿足條件覆蓋.

4.3 判定條件覆蓋

對(duì)于(a>b∨c>d)類似的約束，覆蓋每個(gè)原子條件的不同結(jié)果并不能保證覆蓋整個(gè)約束真或假的結(jié)果.為此，本文定義了規(guī)約約束級(jí)的判定條件覆蓋準(zhǔn)則.在基于規(guī)約約束的測試中，判定條件覆蓋要求為給定前置條件的Web服務(wù)生成的測試數(shù)據(jù)不僅要滿足判定覆蓋，還要滿足條件覆蓋.

定義3.(判定條件覆蓋) 對(duì)于給定前置條件C的服務(wù)，如果測試集T滿足以下條件：

?t∈T，eval(C，t)=true∧?t′∈T，eval(C，t′)=false
∧?e∈BExpr(C){?t∈T，eval(e，t)=true
∧?t′∈T，eval(e，t′)=false}，

就稱測試集T滿足判定條件覆蓋.

對(duì)于3.2節(jié)給出的規(guī)約約束Csum，4.2節(jié)中的測試集Tcc符合上述定義，因此該測試集滿足判定條件覆蓋.

4.4 范式子句覆蓋

對(duì)于規(guī)約約束，當(dāng)測試數(shù)據(jù)有效時(shí)析取范式(DNF)會(huì)有不同的情況，當(dāng)測試數(shù)據(jù)無效時(shí)合取范式的否定則會(huì)有不同的情況.這些情況常對(duì)應(yīng)于 Web 服務(wù)的不同行為，因此應(yīng)更好地被測試集覆蓋.然而條件覆蓋和判定條件覆蓋都不能保證這些情況都能被覆蓋.例如，測試集Tcc雖然覆蓋了b=0和b=1的情況，但是并未覆蓋b的取值不在集合{0，1}中的情況.

為此，本文介紹一種范式子句覆蓋準(zhǔn)則，要求測試數(shù)據(jù)不僅要滿足前置條件中析取范式的每個(gè)子句，還要滿足合取范式中每個(gè)子句的否定.這樣一來，產(chǎn)生有效數(shù)據(jù)或無效數(shù)據(jù)的不同情形都能被覆蓋到.

定義4.(范式子句覆蓋)對(duì)于給定前置條件C的服務(wù)，如果測試集T滿足以下條件：

?f∈DNF(C)，?t∈T，eval(f，t)=true
∧?f∈CNF(C)，?t′∈T，eval(f，t′)=false，

就稱測試集T滿足范式子句覆蓋，其中DNF(C)、CNF(C) 分別是前置條件C中析取范式子句、合取范式子句的集合.

對(duì)于3.2節(jié)給出的規(guī)約約束Csum，析取范式子句有：

(a≥0∧a≤10)∧(b=0)∧(a≠b∧b≠c)，

(a≥0∧a≤10)∧(b=0)∧(a=b∧b=c)，

(a≥0∧a≤10)∧(b=1)∧(a≠b∧b≠c)，

(a≥0∧a≤10)∧(b=1)∧(a=b∧b=c)，

合取范式包括：

a≥0，a≤10，(b=0∨b=1)，(a≠b∨a=b)，

(b≠c∨a=b)，(a≠b∨b=c)，(b≠c∨b=c).

根據(jù)這些子句生成的測試集Tnfcc(a，b，c)={(1，0，2)，(0，0，0)，(0，1，2)，(1，1，1)，((1，0，2)，(11，0，2)，(1，2，2)，(1，1，0)，(0，1，1)} 滿足范式子句覆蓋.

5 測試數(shù)據(jù)生成算法

設(shè)Z3是根據(jù)給定約束生成有效隨機(jī)數(shù)據(jù)的函數(shù)，本節(jié)將基于Z3函數(shù)介紹滿足不同測試覆蓋準(zhǔn)則的測試數(shù)據(jù)生成算法.

5.1 滿足判定覆蓋的測試數(shù)據(jù)生成算法

對(duì)于給定前置條件C的服務(wù)，通過將Z3函數(shù)作用于條件C及其否定形式C，可以生成滿足判定覆蓋的測試集T：

T={Z3(C)，Z3(C)}.

對(duì)于3.2節(jié)給出的規(guī)約，滿足判定覆蓋的測試集可通過將Csum代入上式得到：

Tdc(a，b，c)={(1，1，1)，(20，1，1)}.

5.2 滿足條件覆蓋的測試數(shù)據(jù)生成算法

對(duì)于給定前置條件C的服務(wù)，其中C的原子條件集合為BExpr(C)，若要生成滿足條件覆蓋的測試集，則要求數(shù)據(jù)集同時(shí)滿足BExpr(C)中的每個(gè)條件e及其否定形式e.由于滿足條件e的測試數(shù)據(jù)也可能滿足其他條件，因此根據(jù)每個(gè)條件直接生成對(duì)應(yīng)的數(shù)據(jù)會(huì)帶來冗余，為此，本文使用算法1所示的工作隊(duì)列算法來生成整個(gè)測試集.

算法1.滿足條件覆蓋的測試數(shù)據(jù)生成算法

Input：C：規(guī)約約束

Output：T：測試集

Begin

E=BExpr(C)∪ {e|e∈BExpr(C)};

whileE≠?do

removeeifromE;

t：=Z3(ei∧C);

ift≠ nullthenT：=T∪ {t};

else

t：=Z3(ei∧C);

ift≠ nullthenT：=T∪ {t}；end

end

foreachek∈Edo

ifeval(ek，t)==truethen

E：=E-{ek}；

end

end

end

returnT;

End

算法首先創(chuàng)建包含所有需要覆蓋的條件的工作隊(duì)列E，然后根據(jù)E中的每個(gè)條件ei使用Z3生成對(duì)應(yīng)的服務(wù)輸入t.為了生成合理的完整輸入，需要先將ei和前置條件C(或其否定形式C)進(jìn)行邏輯與操作，再用Z3 求解得到輸入數(shù)據(jù)t，此時(shí)從工作隊(duì)列E中刪除ei，而且t滿足的其他條件也要?jiǎng)h除.當(dāng)工作隊(duì)列E為空時(shí)算法終止.

對(duì)于3.2節(jié)給出的規(guī)約約束Csum，首先創(chuàng)建工作隊(duì)列E={e1=(a≥0)，e2=(a≤10)，e3=(b=0)，e4=(b=1)，e5=(a≠b)，e6=(b≠c)，e7=(a=b)，e8=(b=c)，e1，e2，e3，e4，e5，e6，e7，e8}，然后根據(jù)條件e1使用Z32http://axis.apache.org/axis2/java/core

生成服務(wù)輸入t1=(1，1，1)，t1也滿足條件e2，e4，e7，e8，e3，e5以及e6，因此將這些條件從E中刪除，得到E={e3，e5，e6，e1，e2，e4，e7，e8}.接下來根據(jù)條件e3使用Z3生成另一個(gè)服務(wù)輸入t2=(-1，0，-1)，t2也滿足條件e5，e6，e1，e4，e7以及e8，將這些條件從工作隊(duì)列中刪除后得到E={e2}.最后使用Z3求解到服務(wù)輸入(20，0，20)，算法終止.最終的測試數(shù)據(jù)集合為Tcc(a，b，c)={(1，1，1)，(-1，0，-1)，(20，0，20)}.

5.3 滿足判定條件覆蓋的測試數(shù)據(jù)生成算法

對(duì)于給定前置條件C的服務(wù)，要生成滿足判定條件覆蓋的測試集，可以先生成滿足條件覆蓋的測試數(shù)據(jù)集，再向其中加入必要的測試數(shù)據(jù)以確保滿足判定覆蓋.詳細(xì)的測試數(shù)據(jù)生成算法如算法2所示.算法首先調(diào)用CC(C)生成滿足BExpr(C) 中的每個(gè)條件e及其否定形式e的測試數(shù)據(jù)集，然后判斷該數(shù)據(jù)集是否同時(shí)滿足條件C及其否定形式C，若不滿足條件C，則根據(jù)條件C使用Z3生成服務(wù)輸入；若不滿足條件C，則根據(jù)條件C使用Z3生成對(duì)應(yīng)的服務(wù)輸入.

算法2.滿足判定條件覆蓋的測試數(shù)據(jù)生成算法

Input：C：規(guī)約約束

Output：T：測試集

Begin

T：=CC(C);

B：=?；

foreacht∈TdoB：=B∪ {eval(C，t) };end

iftrue?BthenT：=T∪Z3(C);

elseiffalse?BthenT：=T∪Z3(C);

end

returnT;

End

對(duì)于3.2節(jié)給出的規(guī)約約束Csum，算法首先使用CC(C)得到滿足條件覆蓋的測試集Tdcc={(1，1，1)，(-1，0，-1)，(20，0，20)}，Tdcc同時(shí)滿足條件C及其否定形式C，因此Tdcc滿足判定條件覆蓋，無需生成額外的輸入以滿足判定覆蓋.

5.4 滿足范式子句覆蓋的測試數(shù)據(jù)生成算法

對(duì)于給定前置條件C的服務(wù)，其中C的析取范式子句集合、合取范式子句集合分別為DNF(C)、CNF(C)，為了生成滿足范式子句覆蓋的測試集，需要生成包括滿足DNF(C)中每個(gè)子句的數(shù)據(jù)，以及不滿足CNF(C)中每個(gè)子句的數(shù)據(jù)，具體過程如算法3所示.

算法3.滿足范式子句覆蓋的測試數(shù)據(jù)生成算法

Input：C：規(guī)約約束

Output：T：測試集

Begin

F=DNF(C)∪{e|e∈CNF(C)};

foreache∈Fdo

t：=Z3(e);

T：=T∪{t};

end

returnT;

End

對(duì)于3.2節(jié)給出的規(guī)約約束Csum，算法首先得到需要覆蓋的9個(gè)范式子句，由4.4節(jié)中給出，然后使用Z3 為每個(gè)子句生成相應(yīng)的服務(wù)輸入，最終的數(shù)據(jù)集為4.4節(jié)中的Tnfcc.

6 實(shí) 驗(yàn)

為了驗(yàn)證本方法的有效性，我們實(shí)現(xiàn)了該方法并在兩個(gè) Web 服務(wù)上對(duì)其進(jìn)行測試，以回答以下的研究問題：

問題1.本文提出的測試覆蓋準(zhǔn)則在缺陷檢測方面的表現(xiàn)如何？

實(shí)驗(yàn)并未為服務(wù)注入故障，主要通過檢查這些測試覆蓋準(zhǔn)則是否可以帶來更高的代碼級(jí)覆蓋率來回答這個(gè)問題.

問題2.本文中的測試數(shù)據(jù)生成算法能否用更少的測試數(shù)據(jù)來滿足文中提出的測試覆蓋準(zhǔn)則？

問題3.測試數(shù)據(jù)生成算法的效率如何？

6.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)用本文提出的方法分別測試了兩個(gè)典型的Web服務(wù)：Triangle與MiddleNumber[12，20，21]，這些服務(wù)的變體廣泛用于軟件測試研究中.Triangle服務(wù)根據(jù)輸入三角形的三條邊長a，b，c判斷該三角形是一般三角形、等腰三角形還是等邊三角形，MiddleNumber服務(wù)根據(jù)輸入的三個(gè)數(shù)i，j，k判斷k是否為介于i和j之間的中間數(shù)字.實(shí)驗(yàn)用Java實(shí)現(xiàn)這些服務(wù)，并將它們部署在Axis2容器2中，測試數(shù)據(jù)生成算法也用Java實(shí)現(xiàn)，實(shí)驗(yàn)用Java版的Z3進(jìn)行約束求解.

為了生成測試數(shù)據(jù)，實(shí)驗(yàn)為兩個(gè)服務(wù)定義了前置條件.實(shí)驗(yàn)對(duì)本文提出的測試數(shù)據(jù)生成算法與現(xiàn)有方法進(jìn)行代碼覆蓋率和效率的比較，以說明本方法的有效性.

Triangle服務(wù)的前置條件如下：

CT=C1∧C2，

C1=(a>0)∧(b>0)∧(c>0)∧(a<100)

∧(b<100)∧(c<100)∧(a+b>c)

∧(b+c>a)∧(a+c>b)，

C2=((a=b∧a≠c)∨(b=c∧b≠a)∨(a=c∧a≠b))

∨(a=b∧b=c)∨(a≠b∧a≠c∧c≠b)).

其中，條件C1對(duì)邊長的范圍做出限制以形成一個(gè)有效的三角形，條件C2列舉了所有可能的三角形類型的條件，以覆蓋更多的輸入情況.

MiddleNumber服務(wù)的前置條件如下：

CM=(i>0)∧(j>0)∧(k>0)

∧(i<100)∧(j<100)∧(k<100)

∧((k>i)∧(kj)).

該條件對(duì)輸入?yún)?shù)的值進(jìn)行范圍限制，并要求k介于i和j之間.

表2列出了Triangle和MiddleNumber服務(wù)的前置條件約束，其中文獻(xiàn)[12]提出的測試生成方法(本文稱其為MATDG)并不支持變量之間的關(guān)聯(lián)約束，表中的約束是簡化后得到的.

6.2 實(shí)驗(yàn)結(jié)果

問題1.本文提出的測試覆蓋準(zhǔn)則在缺陷檢測方面的表現(xiàn)如何？

實(shí)驗(yàn)通過比較MATDG[12]、隨機(jī)方法以及本文所提方法的代碼級(jí)語句覆蓋率和分支覆蓋率來回答這個(gè)問題：代碼覆蓋率越高，缺陷檢測能力越好.

實(shí)驗(yàn)分別對(duì)Triangle和MiddleNumber服務(wù)進(jìn)行測試，實(shí)驗(yàn)結(jié)果如表3所列，其中SC%、BC%分別表示語句覆蓋率和分支覆蓋率，CN是不同方法生成的測試數(shù)據(jù)數(shù)量，Avg是每種方法對(duì)應(yīng)統(tǒng)計(jì)項(xiàng)的均值.

對(duì)于MATDG方法，實(shí)驗(yàn)在兩種典型配置下生成測試數(shù)據(jù)<0，1>與<1，1>(配置表示分別為參數(shù)的每個(gè)無效等價(jià)類和有效等價(jià)類生成m和n個(gè)輸入，然后將它們組合成不同的測試數(shù)據(jù))；對(duì)于隨機(jī)方法，實(shí)驗(yàn)分別生成5個(gè)、10個(gè)測試數(shù)據(jù)以評(píng)估隨機(jī)方法的有效性；對(duì)于本文基于規(guī)約的方法，實(shí)驗(yàn)分別生成滿足第4節(jié)中四種覆蓋準(zhǔn)則的測試數(shù)據(jù).表3為每個(gè)服務(wù)分別統(tǒng)計(jì)了幾種代碼的覆蓋率，包括用于拒絕非法輸入的防御代碼、用于正常計(jì)算的代碼以及總代碼.根據(jù)表3的結(jié)果，圖6中(a)和(b)分別用條形圖對(duì)三種方法的語句覆蓋率和分支覆蓋率進(jìn)行更直觀地比較.顯然，本文基于規(guī)約約束的方法同時(shí)具有最高的語句覆蓋率和分支覆蓋率.

表2 Web服務(wù)的規(guī)約約束Table 2 Specification constraints of Web services

表3 生成測試數(shù)據(jù)的語句覆蓋率(SC)和分支覆蓋率(BC)Table 3 Generated test data and their statement coverage(SC) and branch coverage(BC) rates

圖6 比較三種方法的語句覆蓋率和分支覆蓋率Fig.6 Comparison of the three evaluated approaches in source code level statement and branch coverages

然而，有些語句和分支仍未覆蓋到，這是因?yàn)槭褂糜邢迶?shù)量的測試用例很難覆蓋所有的條件組合，滿足范式子句覆蓋的測試用例覆蓋了最多的分支和語句，尤其是正常計(jì)算代碼的覆蓋方面.

問題2.本文中的測試數(shù)據(jù)生成算法能否用更少的測試數(shù)據(jù)來滿足文中提出的測試覆蓋準(zhǔn)則？

實(shí)驗(yàn)通過比較達(dá)到相同規(guī)約約束級(jí)覆蓋率時(shí)隨機(jī)方法生成的測試用例數(shù)量與本文所提方法生成的測試用例數(shù)量來回答這個(gè)問題：數(shù)量越少，效果越好.

表4列出了滿足四種規(guī)約約束級(jí)覆蓋準(zhǔn)則所需的測試用例數(shù)量，可以看出，基于規(guī)約約束的方法只要使用少許幾個(gè)測試用例就能滿足規(guī)約約束級(jí)覆蓋準(zhǔn)則，而隨機(jī)方法需要數(shù)百個(gè)用例才能達(dá)到相同的覆蓋率，因此基于 Z3 的算法在給定覆蓋準(zhǔn)則下可以更為有效地生成低冗余的測試用例.

問題3.測試數(shù)據(jù)生成算法的效率如何？

圖7 生成測試數(shù)據(jù)的時(shí)間Fig.7 Time spent on test data generation

實(shí)驗(yàn)通過收集生成分別滿足四個(gè)規(guī)約約束級(jí)覆蓋標(biāo)準(zhǔn)的測試數(shù)據(jù)所花費(fèi)的時(shí)間來說明測試數(shù)據(jù)生成算法的效率.圖7給出了為Triangle 服務(wù)和 MiddleNumber 服務(wù)生成測試數(shù)據(jù)時(shí)所花費(fèi)的時(shí)間，可以看出，生成滿足判定覆蓋(DC)的測試數(shù)據(jù)所花時(shí)間最少，生成滿足范式子句覆蓋(NFCC)的測試數(shù)據(jù)所花時(shí)間稍多一點(diǎn)，而生成滿足條件覆蓋(CC)和判定條件覆蓋(DCC)的測試數(shù)據(jù)需要花費(fèi)更多的時(shí)間.結(jié)合表3中的語句和分支覆蓋率可以得到以下結(jié)論：使用范式子句覆蓋準(zhǔn)則生成的測試數(shù)據(jù)更有效，而且效率更高.

表4 達(dá)到不同規(guī)約約束級(jí)覆蓋率時(shí)的測試用例數(shù)量Table 4 Test cases needed to achieve coverages at the different level of specification constraints

7 結(jié)束語

本文提出了一種基于規(guī)約約束的 Web 服務(wù)測試數(shù)據(jù)生成方法，該方法中使用的規(guī)約約束系統(tǒng)不僅支持簡單的服務(wù)輸入取值范圍約束，而且還支持服務(wù)輸入?yún)?shù)之間的復(fù)雜關(guān)聯(lián)約束.本文還提出了四種規(guī)約約束級(jí)覆蓋準(zhǔn)則——判定覆蓋、條件覆蓋、判定條件覆蓋以及范式子句覆蓋.利用這些覆蓋準(zhǔn)則，可以通過 Z3 SMT 求解器產(chǎn)生高覆蓋率的測試數(shù)據(jù)，從而更好地揭示服務(wù)中的缺陷.本文的研究仍然存在一些不足，首先，實(shí)驗(yàn)論證還有待在更大規(guī)模、更復(fù)雜 Web 服務(wù)上做進(jìn)一步加強(qiáng)，另外，盡管本文的方法已經(jīng)能夠達(dá)到較高測試覆蓋率，但仍有進(jìn)一步提升的空間.為此，未來將開展更多實(shí)驗(yàn)研究，為方法的應(yīng)用提供更多參考.同時(shí)，計(jì)劃不斷研究新的覆蓋準(zhǔn)則，如結(jié)構(gòu)化測試中的修正條件判定覆蓋準(zhǔn)則(MC/DC)[22]等，以完善所提出的方法.