Web服務(wù)編排場(chǎng)景的XML Schema消息類(lèi)型精化

王 瑾 馬 凱 楊紅麗

(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 北京 100124)

Web服務(wù)編排場(chǎng)景的XML Schema消息類(lèi)型精化

王 瑾 馬 凱 楊紅麗

(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 北京 100124)

Web服務(wù)(Web Services)編排描述了Web服務(wù)組合的交互行為，在實(shí)際開(kāi)發(fā)中，Web服務(wù)組合的實(shí)現(xiàn)可能存在交互的數(shù)據(jù)類(lèi)型、交互序列與編排規(guī)范不相符的情況，為了測(cè)試Web服務(wù)(組合)與編排的相符性，需要從編排規(guī)范生成測(cè)試用例。由于編排場(chǎng)景描述了編排中各個(gè)參與方的交互序列及其交互消息的XML Schema類(lèi)型，從而可以根據(jù)場(chǎng)景中的XML Schema類(lèi)型生成測(cè)試數(shù)據(jù)。由于XML Schema類(lèi)型中指示器的作用導(dǎo)致類(lèi)型的不確定性，需要解決XML Schema類(lèi)型精化問(wèn)題，為此提出了基于組合測(cè)試的XML Schema類(lèi)型精化方法。通過(guò)定義XML Schema類(lèi)型樹(shù)，給出了基于組合測(cè)試工具Cascade的類(lèi)型精化算法，并通過(guò)實(shí)例表明該方法的有效性。

Web服務(wù)編排 XML Schema 指示器 類(lèi)型精化 組合測(cè)試

0 引 言

Web服務(wù)是針對(duì)因特網(wǎng)上分布計(jì)算提出的一種基于開(kāi)放標(biāo)準(zhǔn)、松散耦合及跨平臺(tái)的新型軟件構(gòu)件。但是單個(gè)Web服務(wù)已經(jīng)越來(lái)越難以滿(mǎn)足人們?nèi)找鎻?fù)雜的業(yè)務(wù)需求，Web服務(wù)組合應(yīng)運(yùn)而生。服務(wù)編排是從全局的角度描述Web服務(wù)組合之間的交互，從而確保服務(wù)組合各個(gè)參與方能夠協(xié)調(diào)完成一項(xiàng)業(yè)務(wù)邏輯。

編排結(jié)構(gòu)多樣，數(shù)據(jù)類(lèi)型復(fù)雜。國(guó)外的很多研究組都對(duì)編排進(jìn)行了研究，文獻(xiàn)[1-4]提出了基于模型檢查的方法驗(yàn)證服務(wù)編排；大部分工作著眼于編排的建模與模型檢查，驗(yàn)證的方法可以確保編排規(guī)范和角色需求的正確性，而測(cè)試可以保證在源碼不可知只能獲得實(shí)現(xiàn)端的接口時(shí)，編排實(shí)現(xiàn)的正確性，而基于編排的相符性的測(cè)試研究工作還很不成熟。本課題組提出了基于編排場(chǎng)景的Web服務(wù)組合的相符性測(cè)試框架[1]，編排場(chǎng)景可以理解為多個(gè)角色之間的確定的交互序列(不含選擇、循環(huán))[6]。根據(jù)編排中的控制流活動(dòng)抽取一組編排場(chǎng)景，每個(gè)編排場(chǎng)景的交互序列一定，從而在編排場(chǎng)景上進(jìn)行測(cè)試。

編排場(chǎng)景不僅描述了多個(gè)參與方的交互序列，還定義了交互的數(shù)據(jù)類(lèi)型，這些類(lèi)型被定義在XML Schema中。而相符性測(cè)試的測(cè)試數(shù)據(jù)由場(chǎng)景中的XML Schema產(chǎn)生。由于XML Schema中存在choice、minOccurs和maxOccurs這樣的指示器，造成變量類(lèi)型的多樣化，因此在生成測(cè)試數(shù)據(jù)之前要先對(duì)XML Schema中的指示器進(jìn)行劃分。多個(gè)指示器存在時(shí)，需要對(duì)劃分的子類(lèi)型進(jìn)行組合，如果采用全排列的組合方式容易造成組合爆炸，產(chǎn)生昂貴的測(cè)試代價(jià)[7-9]。本文采用了組合測(cè)試的思想對(duì)子類(lèi)型的劃分進(jìn)行組合，并將組合后的數(shù)據(jù)轉(zhuǎn)換為一組類(lèi)型確定的類(lèi)型樹(shù)，為測(cè)試數(shù)據(jù)的生成奠定基礎(chǔ)。首先，將XML Schema解析成類(lèi)型樹(shù)，方便與組合測(cè)試工具進(jìn)行模型轉(zhuǎn)換，然后通過(guò)遍歷類(lèi)型樹(shù)邊的指示器信息，對(duì)不同指示器進(jìn)行不同的處理，得到相應(yīng)組合測(cè)試工具輸入模型，通過(guò)組合測(cè)試工具的組合，得到的一組輸出模型，再將輸出值轉(zhuǎn)化為一組對(duì)應(yīng)的精化后的類(lèi)型樹(shù)。

1 相關(guān)概念

1.1 編排場(chǎng)景

定義1 編排場(chǎng)景S是一個(gè)四元組：

S=

其中，R是角色聲明的有限集，分為被測(cè)服務(wù)和測(cè)試樁；I是交互類(lèi)型的有限集，被定義在外部的XML Schema中；V是變量聲明的有限集，每一個(gè)變量都對(duì)應(yīng)I中的一個(gè)變量；A是交互序列的有限集，分為請(qǐng)求型Request{R1.x op R2.y Guard}和響應(yīng)型Response{R1.x op R2.x Guard}。Request{R1.x op R2.y Guard}是指在滿(mǎn)足Guard前置條件的基礎(chǔ)上，將R1上的x變量通過(guò)操作op傳給R2的y變量；Response{R1.x op R2.x Guard}是指在滿(mǎn)足Guard前置條件的基礎(chǔ)上，將R2的變量y通過(guò)op操作傳給R1的x變量。

圖1 成功購(gòu)買(mǎi)場(chǎng)景

圖1的UML時(shí)序圖描述了購(gòu)買(mǎi)成功的場(chǎng)景。場(chǎng)景中包含客戶(hù)、網(wǎng)上商城、庫(kù)存和銀行四個(gè)角色。交互流程為：客戶(hù)發(fā)送訂單請(qǐng)求給網(wǎng)上商城；網(wǎng)上商城向庫(kù)存發(fā)送庫(kù)存檢查信息；庫(kù)存將檢查結(jié)果發(fā)送給商城；商城發(fā)送訂單完成的信息給客戶(hù)?？蛻?hù)發(fā)送銀行信息給商城；商城將付款信息發(fā)送給銀行；銀行向商城發(fā)送付款完成信息；商城發(fā)送訂購(gòu)成功信息給客戶(hù)。

1.2 XML Schema類(lèi)型劃分

XML Schema[10]是用于描述和規(guī)范XML文檔邏輯結(jié)構(gòu)的一種語(yǔ)言，通過(guò)指示器來(lái)控制元素的使用方式。指示器導(dǎo)致了變量類(lèi)型的多樣性，尤其是choice、minOccurs、maxOccurs三種指示器。表1給出了這三種指示器的劃分規(guī)則。

表1 指示器類(lèi)型劃分規(guī)則

1) 當(dāng)出現(xiàn)choice指示器時(shí)，someElement可以選擇c1、c2、c3、…，將其分別劃分為someElement子元素為c1、c2、c3、…多個(gè)子類(lèi)型。

2) 當(dāng)出現(xiàn)minOccurs=″k1″ maxOccurs=″k2″指示器時(shí)，someElement最少可以出現(xiàn)k1次，最多可以出現(xiàn)k2次，將其劃分為三個(gè)子類(lèi)型，分別為minOccurs=″k1″ maxOccurs =″k1″， minOccurs=″k2″ maxOccurs=″k2″，minOccurs=″k″ maxOccurs= ″k″ (k1

3) 當(dāng)出現(xiàn)minOccurs=″k1″ maxOccurs=″unbound″指示器時(shí)，將其劃分為兩種子類(lèi)型：minOccurs=″k1″ maxOccurs =″k1″，minOccurs=″k1+1″ maxOccurs =″k1+1″。

通過(guò)相應(yīng)的劃分規(guī)則，得到結(jié)構(gòu)確定的子類(lèi)型，并且使得該子類(lèi)型一定滿(mǎn)足XML Schema類(lèi)型定義。當(dāng)一個(gè)XML Schema中存在多個(gè)指示器時(shí)，對(duì)每個(gè)指示器進(jìn)行劃分并且重新組合，可以得到一組類(lèi)型確定并滿(mǎn)足初始XML Schema類(lèi)型的子類(lèi)型。如果采用全排列的方式對(duì)劃分后的元素進(jìn)行重組，勢(shì)必會(huì)產(chǎn)生一組數(shù)量龐大的子類(lèi)型，為了解決這個(gè)問(wèn)題，本文引入了組合的測(cè)試方法對(duì)劃分的子類(lèi)型進(jìn)行組合。

1.3 組合測(cè)試方法

組合測(cè)試方法旨在應(yīng)用較少的測(cè)試用例有效地檢查軟件系統(tǒng)中各個(gè)因素以及它們之間的互相作用對(duì)系統(tǒng)產(chǎn)生的影響。

針對(duì)具體待測(cè)軟件，在滿(mǎn)足給定組合覆蓋要求的前提下，生成規(guī)模盡可能小的測(cè)試用例集，以便在保證錯(cuò)誤檢測(cè)能力的前提下盡可能降低測(cè)試成本。

組合測(cè)試中的基本概念包括：

(1) 變量，表示軟件的輸入；

(2) 水平，表示變量的取值；

(3) 強(qiáng)度，表示變量之間相互作用的強(qiáng)度。

Cascade[11]是一款組合測(cè)試用例生成工具，工具支持的變量類(lèi)型有：string、integer、double。變量的水平由用戶(hù)輸入。用戶(hù)可以輸入蘊(yùn)含表達(dá)式對(duì)用例的生成進(jìn)行約束，表達(dá)式支持字符串以及數(shù)值的比較，支持邏輯和算數(shù)運(yùn)算符。

Cascade蘊(yùn)含式約束的引入可以人為的減少無(wú)效組合的出現(xiàn)，有效提高用例集質(zhì)量。Cascade的約束表達(dá)式有兩種形式:

(1) expA -> expB 表示A蘊(yùn)含B，即若表達(dá)式A成立，那么B也必須成立。

(2) expA##(param_list), 表示如果表達(dá)式expA成立，那么param_list集合中的參數(shù)無(wú)意義，不參加組合。

下面給出Cascade的輸入和輸出模型定義：

定義2 Cascade的輸入模型

(1) { (Vi,Li) |i=1,2,…,n}。其中n為自然數(shù)。每個(gè)Vi都是一個(gè)變量，Li是該變量的水平。整個(gè)集合可以看作包含了多個(gè)VL對(duì)，每個(gè)VL表示一個(gè)指示器的劃分；

(2) Cons，約束表達(dá)式的集合。

定義3 Cascade的輸出模型

表示為{ |l1∈L1,l2∈L2,…,ln∈Ln}。集合中每個(gè)元素都表示了一種變量取值的組合情況。

1.4 類(lèi)型樹(shù)

為了方便將場(chǎng)景交互類(lèi)型XML Schema類(lèi)型與組合測(cè)試工具進(jìn)行轉(zhuǎn)換，需要對(duì)XML Schema類(lèi)型建模。本文用樹(shù)模型表示XML Schema類(lèi)型，稱(chēng)為XML Schema類(lèi)型樹(shù)，簡(jiǎn)稱(chēng)類(lèi)型樹(shù)，在類(lèi)型精化的過(guò)程中只需關(guān)注類(lèi)型樹(shù)邊上的指示器約束信息。下面給出類(lèi)型樹(shù)及精化后類(lèi)型樹(shù)的定義。

定義4 XML Schema類(lèi)型樹(shù)定義為一個(gè)四元組：

T=

其中，N是元素節(jié)點(diǎn)和控制節(jié)點(diǎn)的有窮集合，控制節(jié)點(diǎn)分為

sequence和choice兩種。

r是樹(shù)的根節(jié)點(diǎn)。

C是節(jié)點(diǎn)之間的指示器約束集合，本文涉及minOccurs、maxOccurs和choice三種指示器。其中指示器約束可以取以下約束中的一種或多種：

(1) True；

(2) (m=0,1,…,m)，表示了元素出現(xiàn)的最少次數(shù)為m，這里m為自然數(shù)；

(3) (n=0,1,…,unbounded)，表示元素出現(xiàn)的最多次數(shù)為n，可以取任意自然數(shù)或unbounded；

(4) ，b是choice指示器中子元素其中的一個(gè)。

E是邊的有窮集合。邊可以表示為e(m,c,n)，其中c∈C，m∈N∪r，n∈N。

圖2是圖1中第一個(gè)交互中訂單請(qǐng)求的XML Schema所對(duì)應(yīng)的類(lèi)型樹(shù)。purchaseOrder是該類(lèi)型樹(shù)的根節(jié)點(diǎn)。purchaseOrder_sequence、coupon_choice和goods_sequence是控制節(jié)點(diǎn)，其他節(jié)點(diǎn)均為元素節(jié)點(diǎn)。每一條邊上都有一種或多種指示器約束。例如邊e1對(duì)應(yīng)的約束c1&&表示coupon元素最少出現(xiàn)0次，最多出現(xiàn)1次；邊e4對(duì)應(yīng)的約束c4中表示cashback是coupon_choice指示器中的一個(gè)分支,&&表示coupon_choice可以出現(xiàn)最少0次，最多2次。

圖2 訂單類(lèi)型樹(shù)

2 XML Schema類(lèi)型精化算法

2.1 XML Schema類(lèi)型精化過(guò)程

如圖3所示，是XML Schema類(lèi)型精化的過(guò)程，包括四部分內(nèi)容。

圖3 XML Schema類(lèi)型精化過(guò)程

(1) 從場(chǎng)景中抽取XML Schema及衛(wèi)士信息(Guard), 通過(guò)分析文件中的XML Schema，提取指示器信息，生成相應(yīng)的類(lèi)型樹(shù)模型。

(2) 對(duì)解析生成的XML Schema類(lèi)型樹(shù)調(diào)用treeToCascade算法遍歷類(lèi)型樹(shù)邊上的約束信息，生成Cascade組合測(cè)試工具的輸入模型。

(3) 通過(guò)Cascade的組合，得到一組輸出數(shù)據(jù)，每一組數(shù)據(jù)代表類(lèi)型樹(shù)約束信息的確定取值，即Cascade的輸出模型。

(4) 對(duì)輸出的每組數(shù)據(jù)調(diào)用toTrees算法生成一個(gè)精化的類(lèi)型樹(shù)，得到一組精化的類(lèi)型樹(shù)集合。精化后的類(lèi)型樹(shù)中每個(gè)指示器信息都為確定值。

2.2 treeToCascade算法

treeToCascade算法是以類(lèi)型樹(shù)模型為輸入，通過(guò)遍歷邊上的指示器信息，將其自動(dòng)轉(zhuǎn)化為Cascade的輸入數(shù)據(jù)VL對(duì)和相應(yīng)的約束Cons。

1) 算法思路

遍歷邊的過(guò)程中：

(1) 當(dāng)遇到指示器時(shí)，父節(jié)點(diǎn)的值作為Cascade的變量，子節(jié)點(diǎn)的值作為該變量的一個(gè)水平；

(2) 當(dāng)遇到 &&指示器時(shí)，子節(jié)點(diǎn)的值作為Cascade的變量，該變量的水平參照?qǐng)D1中 &&中提到的劃分規(guī)則；

(3) 當(dāng)choice節(jié)點(diǎn)的入度邊有 && 指示器信息時(shí)，需要考慮指示器的復(fù)合，引入新變量來(lái)表示不同choice節(jié)點(diǎn)的不同選擇。

對(duì)于choice節(jié)點(diǎn)可出現(xiàn)多次的情況，為choice節(jié)點(diǎn)增加額外的信息記錄其子節(jié)點(diǎn)出現(xiàn)的次序。同時(shí)引入新的組合變量即VL對(duì)，來(lái)表示choice節(jié)點(diǎn)每一次的子節(jié)點(diǎn)選擇。設(shè)choice節(jié)點(diǎn)的minOccurs為k1，maxOccurs為k2，且擁有的子節(jié)點(diǎn)為C1、C2、C3、C4。則引入的VL對(duì)如表2所示。

表2 choice出現(xiàn)多次的VL對(duì)

第一列表示的是choice節(jié)點(diǎn)的出現(xiàn)次數(shù)，剩下分別表示第i次choice子節(jié)點(diǎn)的選擇。為了減少無(wú)效組合數(shù)，同時(shí)為蘊(yùn)含式集和Cons添加新的約束集：

{choice=k ##(choicep) | k1<=k, k

若組合中choice節(jié)點(diǎn)出現(xiàn)次數(shù)取p，那么討論第p+1次choice節(jié)點(diǎn)的子節(jié)點(diǎn)顯然是沒(méi)有意義的。其中##(choicep)表示變量choicep不參與組合，是為了在實(shí)際組合用例的生成過(guò)程中去除無(wú)效VL對(duì)的影響，減少無(wú)效組合數(shù)量。

(4) 當(dāng)一個(gè)節(jié)點(diǎn)的入度邊有 && 指示器信息，出度邊上有&& &&指示器信息時(shí)，添加約束集：

{choice1!=C &&…&& choicek2!=C → C=0|C∈L(choice)}

如果每一次choice子節(jié)點(diǎn)的選擇都沒(méi)有出現(xiàn)C，那么C節(jié)點(diǎn)置為0。

2) 輔助函數(shù)

treeToCascade算法中用到的輔助函數(shù)有：

(1) addVL(V,k1,k2)的輸入為變量V、指示器minOccurs的值k1和maxOccurs的值k2。如果k1==k2，則L={k1}；如果k2==unbounded，則L={k1，k1+1}；否則L={k1,k2,mid(k1,k2)}，將該VL對(duì)加入到Cinput的{(V,L)}集合中。

(2) addVLs(m,j,L)的輸入為該邊的父節(jié)點(diǎn)、父節(jié)點(diǎn)入度邊maxOccurs指示器的值j和水平V。該函數(shù)的功能是將(m1，L) 、…、(mj，L)組(V,L)對(duì)加入到Cinput的{(V,L)}集合中。如果變量V已經(jīng)存在，將L的值并到V的水平中。

(3) addCon(con)的輸入為一條約束信息con，功能是將con約束加入Cinput中的{Cons}集合中。

(4) getL(V)的功能是返回Cinput中變量V的水平，setL(V,L)是將Cinput中變量V設(shè)置為L(zhǎng)。

3) 算法偽碼

treeToCascade算法

輸入：類(lèi)型樹(shù)T，場(chǎng)景中的衛(wèi)式信息(Guard)

輸出：Cinput={(Vi,Li)|i=1,2,3,...,n} ∪{Cons}

1 Cinput= ?

2 foreach e(m,c,n) ∈ T.E && c≠True do

3 if c==&& then

4 addVL(n, k1, k2)

5 if n is the node with choice then

6 addCon({n=k ##(np)| k1<=k, k

7 if c== then

8 if m.fatherEdge.c==&& then

9 addVLs(m,k2,b)

10 else

11 addVL(m,b)

12 if c==&&&& then

13 addVL(n, k1, k2)

14 if m.fatherEdge.c== && then

15 addVLs(m,k2’ , b)

16 addCon({m1!=C &&...&& mk2’!=C → C=0 |C∈L(cho)})

17 else

18 addVL(m,b)

19 if n.guard != null then

20 e’=e

21 foreach m’ != root do

22 if c’==&& then

23 setL(n’,getL(n)>0)

24 if c’== then

25 setL(m’, b)

26 if c’==&&&& then

27 setL(n’,getL(n)>0)

28 setL(m’, b)

29 m’=m’.father

30 return Cinput

算法中，第3-6行處理了類(lèi)型樹(shù)邊上的約束c為 && 的情況，添加VL對(duì)，變量為n，水平為k1至k2。當(dāng)孩子節(jié)點(diǎn)n為choice節(jié)點(diǎn)時(shí)，添加約束addCon({n=k ##(np)| k1<=k, k

第7-11行處理了c為的情況。第8-9行表示choice結(jié)點(diǎn)的入度邊為&&時(shí)，將水平b添加到m1到mk2個(gè)變量中。第10-11行表示，choice節(jié)點(diǎn)入度邊不為復(fù)合類(lèi)型時(shí)，將水平b添加給m變量。

第12-18行處理了c為&& &&的情況。第15-16行表示添加VL對(duì)n及n的水平。第14-16行表示m節(jié)點(diǎn)的入度邊為&& 時(shí)，將水平b添加到m1到mk2’變量中，并且添加約束信息addCons({ m1!=C &&…&& mmax!=C → C=0|C∈L(cho)})。第17-18行表示，m節(jié)點(diǎn)的入度邊沒(méi)有&& 指示器時(shí)，直接將b賦給m變量。

第19-29行處理Guard約束標(biāo)記的節(jié)點(diǎn)。衛(wèi)式信息(Guard)來(lái)自編排規(guī)范，在場(chǎng)景抽取的過(guò)程中，每一個(gè)交互都帶有一個(gè)衛(wèi)式作為前置約束條件，對(duì)本次交互變量數(shù)據(jù)的全部或部分片段取值進(jìn)行約束。當(dāng)n節(jié)點(diǎn)含有衛(wèi)式標(biāo)記時(shí)，生成測(cè)試數(shù)據(jù)時(shí)，要保證該節(jié)點(diǎn)一定存在。表現(xiàn)為：

(1) 當(dāng)root節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑中，遇到choice指示器時(shí)choice=此邊的節(jié)點(diǎn)；

(2) 當(dāng)root節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑中，遇到occurrence指示器時(shí)，此邊的孩子節(jié)點(diǎn)occurrence>0。

4) 算法時(shí)間復(fù)雜度

依據(jù)算法的設(shè)計(jì)，算法的時(shí)間復(fù)雜度主要體現(xiàn)在遍歷類(lèi)型樹(shù)的邊以及當(dāng)節(jié)點(diǎn)含有衛(wèi)式信息時(shí)要回溯到根節(jié)點(diǎn)處理相應(yīng)的指示器上。當(dāng)類(lèi)型樹(shù)邊的數(shù)量為n, 則遍歷類(lèi)型樹(shù)邊的時(shí)間復(fù)雜度為O(n),設(shè)有m個(gè)節(jié)點(diǎn)含有衛(wèi)式信息，含衛(wèi)式信息的節(jié)點(diǎn)到根節(jié)點(diǎn)的平均距離為p,這里的距離是指節(jié)點(diǎn)到根節(jié)點(diǎn)之間的邊樹(shù)，則treeToCascade算法的時(shí)間復(fù)雜度為O(n)+mO(p)。

2.3 toTrees算法

通過(guò)輸入Cascade的變量、水平及約束，工具可以輸出變量的組合(稱(chēng)為組合覆蓋數(shù)組)，表示為Coutput：{ | l1∈L1, l2∈L2,…, ln∈Ln}。所有組合調(diào)用toTrees算法用來(lái)生成一個(gè)精化的類(lèi)型樹(shù)集合。

toTrees(T,a)算法中，a是Coutput中的一種組合，T是原來(lái)的類(lèi)型樹(shù)模型集合。算法的輸出為精化后的類(lèi)型樹(shù)集合。反復(fù)調(diào)用toTrees(T,a)算法處理Coutput中的每一條記錄，將得到每一種組合情況對(duì)應(yīng)的子類(lèi)型。

算法用到的輔助函數(shù)有：

1) getVar(T,l)的輸入為類(lèi)型樹(shù)T和水平中的某個(gè)值l，返回一個(gè)變量，這個(gè)變量的水平包含l且對(duì)應(yīng)的節(jié)點(diǎn)在類(lèi)型樹(shù)T中。

2) add(V,T)的輸入為變量V和類(lèi)型樹(shù)T，功能是添加變量V在T中對(duì)應(yīng)的節(jié)點(diǎn)及所有的子孫。

3) delete(V, T)的輸入為變量V和類(lèi)型樹(shù)T，功能是刪除變量V在T中對(duì)應(yīng)的節(jié)點(diǎn)及其所有的子孫。

4) changeConstraint(y, c, V, T)的功能是改變特定邊上的約束為c，這條邊的父節(jié)點(diǎn)是y，子節(jié)點(diǎn)是變量V在類(lèi)型樹(shù)T上對(duì)應(yīng)的節(jié)點(diǎn)。

toTrees算法

輸入：類(lèi)型樹(shù)T, a= (a ∈ Coutput, li ∈ ln)

輸出：精化類(lèi)型樹(shù)集合T’s

1 T’s= ?

2 T’=T

3 foreach li in a do

4 Vi=getVar(T’,li)

5 if Vi is a choice node && !isNode(li) then

6 for i=1to li

7 Vi.father.add(Vi, T’)

8 name=getName(Vi)

9 changeName(Vi,name+”i”)

10 delete(Vi,T’)

11 else if isNode(li) then

12 foreach n in Vi.childrenlist do

13 if n!=li then delete(n, T’)

14 else if li==0 then delete(Vi, T’)

15 else if li==”#” continue

16 else

17 y=Vi.father

18 c=

19 changeConstraint(y, c, Vi, T’)

20 T’s=T’s∪{T’}

21 return T’s

算法中第5-10行是處理choice節(jié)點(diǎn)可出現(xiàn)多次的情況，首先獲取choice子節(jié)點(diǎn)數(shù)量n，根據(jù)子節(jié)點(diǎn)的數(shù)量，對(duì)該choice節(jié)點(diǎn)進(jìn)行n次拷貝，這里的拷貝是指遞歸的對(duì)子節(jié)點(diǎn)及其孩子信息進(jìn)行深度的拷貝。

第11-13行處理li對(duì)應(yīng)一個(gè)節(jié)點(diǎn)的值的情況，說(shuō)明該li對(duì)應(yīng)的變量為一個(gè)choice節(jié)點(diǎn)，刪除該choice節(jié)點(diǎn)除li對(duì)應(yīng)的子節(jié)點(diǎn)外的其他孩子節(jié)點(diǎn)。

第14-15行是指當(dāng)li==0時(shí)，代表li對(duì)應(yīng)的節(jié)點(diǎn)出現(xiàn)次數(shù)為0，刪除該節(jié)點(diǎn)。當(dāng)li==”#”，代表該li無(wú)效，不做任何處理。

第19-21行表示將li所對(duì)應(yīng)節(jié)點(diǎn)的入度邊的約束改為。

3 XML Schema類(lèi)型精化實(shí)例

3.1 訂單類(lèi)型樹(shù)的Cascade輸入模型

圖2所示的訂單類(lèi)型樹(shù)，調(diào)用treeToCascade算法后，可以得到表3所示的變量及水平。

表3中，共有6個(gè)參數(shù)及水平，2個(gè)約束表達(dá)式，其中coupon_choice == ″1″ ##(coupon_choice2) 表示當(dāng)參數(shù)coupon_choice取值為1時(shí)，參數(shù)coupon_choice2則不參與組合，coupon_choice1!= ″cashback″ && coupon_choice2!= ″cashback″ -> cashback == ″0″表示當(dāng)coupon_choice1和coupon_choice2都不為cashback，則將cashback 的值置為0。強(qiáng)度設(shè)置為2，可以手動(dòng)添加。

表3 訂單類(lèi)型的Cascade的輸入

3.2 Cascade的輸出模型

通過(guò)Cascade的組合，表3中Cascade輸入模型會(huì)轉(zhuǎn)化為表4中的Cascade的輸出。每一行代表一組Cascade輸入變量的值的組合。表3中6個(gè)變量產(chǎn)生了9組值的組合。

例如第1行表示，coupon取值為0，coupon_choice取值為2，coupon_choice1取值為discount，coupon_choice2取值為discount，cashback取值為0，goods取值為2。

3.3 精化后的類(lèi)型樹(shù)

對(duì)每一條Cascade的輸出調(diào)用toTrees算法后，會(huì)產(chǎn)生一組相應(yīng)的精化后的類(lèi)型樹(shù)。如圖4所示，表示表6中第4條輸出調(diào)用toTrees算法后得到精化的類(lèi)型樹(shù)。coupon節(jié)點(diǎn)的入度邊上的指示器信息為minOccurs=1&&maxOccurs=1，代表coupon節(jié)點(diǎn)只出現(xiàn)一次；coupon_choice為1代表coupon_choice指示器只出現(xiàn)一次，由conpon_choice1表示；coupon_choice1值為discount；goods入度邊上的指示器信息為minOccurs=2&&maxOccurs=2，代表goods出現(xiàn)的次數(shù)確定為2。

通過(guò)實(shí)例分析可得，每一顆精化后的類(lèi)型樹(shù)的指示器信息都是確定的。在沒(méi)有借助Cascade組合測(cè)試工具時(shí)，訂單請(qǐng)求的XML Schema類(lèi)型通過(guò)劃分和全排列的組合，會(huì)產(chǎn)生96組子類(lèi)型，并且會(huì)產(chǎn)生一些無(wú)效的組合，例如當(dāng)coupon_choice選擇1時(shí)，討論coupon_choice2變量的組合沒(méi)有意義。在Cascade組合測(cè)試工具的幫助下，得到了9組子類(lèi)型并覆蓋了所有需要被組合的變量的取值。

圖4 精化后的類(lèi)型樹(shù)

利用組合測(cè)試的思想實(shí)現(xiàn)XML Schema的類(lèi)型精化，不僅可以減少精化后的類(lèi)型樹(shù)的數(shù)量，從而極大地減少測(cè)試數(shù)據(jù)的數(shù)量，降低了測(cè)試代價(jià)；同時(shí)提高了測(cè)試數(shù)據(jù)生成的可控性。為測(cè)試數(shù)據(jù)的生成及相符性測(cè)試奠定了重要的基礎(chǔ)。

4 相關(guān)工作

國(guó)內(nèi)外關(guān)于Web服務(wù)組合測(cè)試的工作有很多。Zhou等[12]采用動(dòng)態(tài)符號(hào)執(zhí)行的方法產(chǎn)生測(cè)試的輸入和斷言從而進(jìn)行WS-CDL的測(cè)試。Tsai等[13]從服務(wù)請(qǐng)求者和UDDI服務(wù)中介兩個(gè)角度考慮Web服務(wù)的測(cè)試，提出了一種使用多層次場(chǎng)景描述的方法來(lái)描述系統(tǒng)行為。張大勇等[14]著眼于Web服務(wù)的的交互以及交互之間對(duì)Web服務(wù)行為的影響對(duì)Web服務(wù)進(jìn)行測(cè)試。Bravetti等[15]提出了一個(gè)有效的方法驗(yàn)證包含了給定合約的服務(wù)是否可以在編排中正確地扮演自己的角色，這個(gè)過(guò)程是通過(guò)編排的組合與合約的精化實(shí)現(xiàn)的。

基于編排的測(cè)試工作主要包括：Besson等[16]開(kāi)發(fā)了一個(gè)測(cè)試框架來(lái)支持測(cè)試驅(qū)動(dòng)的編排開(kāi)發(fā)。Nguyen等[17]提出了基于編排的消極的相符性測(cè)試框架。本研究組采用積極測(cè)試，并從編排中對(duì)控制流進(jìn)行抽取生成編排場(chǎng)景進(jìn)行相符性測(cè)試。

諸多關(guān)于測(cè)試數(shù)據(jù)生成的工作涉及到XML Schema以及XML Schema指示器的劃分。Li等[18]擴(kuò)展了適用于XML Schema常規(guī)改變的方法并提出了分析改變后XML Schema的語(yǔ)義正確性的技術(shù)。Bai等[19]將WSDL解析成結(jié)構(gòu)化的DOM樹(shù)，通過(guò)分析標(biāo)準(zhǔn)XML Schema語(yǔ)法來(lái)生成測(cè)試數(shù)據(jù)。Xu等[20]考慮了Web服務(wù)交互中的XML Schema信息，提出基于擾動(dòng)算子對(duì)XML Schema進(jìn)行修改和實(shí)例化，進(jìn)而測(cè)試基于XML的通信應(yīng)用。Bulbul等[21]基于給定的數(shù)據(jù)定義實(shí)現(xiàn)了測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)。Bertolino等[22]去掉XML Schema中不影響結(jié)構(gòu)的屬性，根據(jù)XML-Schema的指示器進(jìn)行等價(jià)劃分，本文的思路與其類(lèi)似，但是利用了組合測(cè)試用例的生成技術(shù)，控制了測(cè)試用例的數(shù)量，降低了測(cè)試代價(jià)，并且在指示器的復(fù)合問(wèn)題上考慮得更為詳細(xì)。Cohen等解釋了數(shù)學(xué)組合理論以及多個(gè)因素下，幾個(gè)因素值域覆蓋的理論[23]。王子元等說(shuō)明了組合測(cè)試用例生成技術(shù)，并解釋了組合測(cè)試的覆蓋標(biāo)準(zhǔn)[24]。

5 結(jié) 語(yǔ)

測(cè)試數(shù)據(jù)的生成為編排與web服務(wù)組合的相符性測(cè)試提供了基礎(chǔ)。XML Schema類(lèi)型精化是測(cè)試數(shù)據(jù)生成過(guò)程中必不可少的部分。本文主要研究編排場(chǎng)景消息交互的XML Schema類(lèi)型精化：

(1) 在測(cè)試數(shù)據(jù)生成過(guò)程中，XML Schema指示器的存在為測(cè)試數(shù)據(jù)的生成增加了難度，本文提出了類(lèi)型精化的概念。即通過(guò)指示器的劃分和組合，產(chǎn)生一組類(lèi)型確定的精化后的類(lèi)型樹(shù)。

(2) 在指示器的組合過(guò)程中，為了避免組合數(shù)量爆炸，造成測(cè)試代價(jià)過(guò)高。本文采用的組合的測(cè)試思想，在保證覆蓋率的情況下，極大的減少組合數(shù)量。

(3) 由于組合的過(guò)程中需要用到組合測(cè)試工具Cascade，本文提出了treeToCascade算法和toTrees算法完成類(lèi)型樹(shù)到Cascade工具輸入模型和Cascade輸出模型到精化后的類(lèi)型樹(shù)之間的轉(zhuǎn)換。并在轉(zhuǎn)換過(guò)程中，考慮到指示器的各種情況，旨在可以處理任何指示器的復(fù)合情況，覆蓋更多的子類(lèi)型，并通過(guò)蘊(yùn)含式減少無(wú)用的組合數(shù)據(jù)。

本文的進(jìn)一步工作主要圍繞通過(guò)精化后的類(lèi)型樹(shù)產(chǎn)生測(cè)試數(shù)據(jù)集。通過(guò)相應(yīng)的數(shù)據(jù)集生成規(guī)則為精化后的類(lèi)型樹(shù)的葉子結(jié)點(diǎn)產(chǎn)生測(cè)試數(shù)據(jù)，并在測(cè)試數(shù)據(jù)生成過(guò)程中提取場(chǎng)景中的衛(wèi)式信息對(duì)葉子結(jié)點(diǎn)進(jìn)行標(biāo)記，以滿(mǎn)足交互序列執(zhí)行的條件。在得到一組測(cè)試數(shù)據(jù)集后，基于編排場(chǎng)景對(duì)Web服務(wù)組合進(jìn)行相符性測(cè)試。

[1] Salauün G, Bultan T, Roohi N. Realizability of choreographies using process algebra encodings[J].IEEE Transactions on Services Computing, 2012, 5(3):290-304.

[2] Pi4SOA[OL]. http://www.pi4soa.org.

[3] Salauün G, Roohi N. On realizability and dynamic reconfiguration of choreographies[C]//Proceedings of WASELF’09, 2009.

[4] Bozkurt M, Harman M, Hassoun Y. Testing web services: a survey: TR-10-01[R]. Technical Report of King’s College London, 2010.

[5] 周亮. 基于編排規(guī)范的Web服務(wù)相符性測(cè)試[D]. 北京：北京工業(yè)大學(xué), 2011.

[6] 鄧晨. Web服務(wù)編排的場(chǎng)景研究[D]. 北京：北京工業(yè)大學(xué), 2012.

[7] Yang H, Ma K, Deng C, et al. Towards conformance testing of choreography based on scenario[C]//Proceedings of the 2013 International Symposium on Theoretical Aspects of Software Engineering. IEEE Computer Society, 2013:59-62.

[8] Ma K, Wang J, Yang H, et al. Choreography scenario-based test data generation[C]//2014 Theoretical Aspects of Software Engineering Conference (TASE). IEEE Computer Society, 2014:70-73.

[9] 馬凱. 基于編排場(chǎng)景的Web服務(wù)相符性測(cè)試[D]. 北京：北京工業(yè)大學(xué), 2014.

[10] XML Schema教程[OL]. http://www.w3school.com.cn/schema/index.asp.

[11] Cascade: CAS Covering Array DEsigner[OL]. http://lcs.ios.ac.cn/zhangzq/cTtoolkit.html.

[12] Zhou L, Ping J, Xiao H, et al. Automatically testing web services choreography with assertions[C]//Proceedings of the 12th International Conference on Formal Engineering Methods and Software Engineering. Springer, 2010:138-154.

[13] Tsai W T, Paul R, Yu L, et al. Scenario-based web services testing with distributed agents[J]. IEICE Transactions on Information and Systems, 2003, 86(10):2130-2144.

[14] 張大勇, 黃寧, 余瑩, 等. Web服務(wù)交互測(cè)試中SOAP消息的控制和分析[J]. 計(jì)算機(jī)與數(shù)字工程, 2005, 33(9):10-14.

[15] Bravetti M, Zavattaro G. Towards a unifying theory for choreography conformance and contract compliance[C]//Proceedings of the 6th International Conference on Software Composition. Springer, 2007:34-50.

[16] Besson F M, Leal P M B, Kon F, et al. Towards automated testing of web service choreographies[C]//Proceedings of the 6th International Workshop on Automation of Software Test, 2011:109-110.

[17] Nguyen H N, Poizat P, Za?di F. Passive conformance testing of service choreographies[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing, 2012:1528-1535.

[18] Li J B, Miller J. Testing the semantics of W3C XML schema[C]//29th Annual International Conference on Computer Software and Applications. IEEE, 2005:443-448.

[19] Bai X, Dong W, Tsai W T, et al. WSDL-based automatic test case generation for web services testing[C]//2005 IEEE International Workshop on Service-Oriented System Engineering. IEEE, 2005:207-212.

[20] Xu W, Offutt J, Luo J. Testing web services by XML perturbation[C]//Proceedings of the 16th IEEE International Symposium on Software Reliability Engineering. Washington, DC, USA: IEEE Computer Society, 2005:257-266.

[21] Bulbul H I, Bakir T. XML-based automatic test data generation[J]. Computing & Informatics, 2008, 27:681-698.

[22] Bertolino A, Gao J, Marchetti E, et al. Automatic test data generation for XML schema-based partition testing[C]//Second International Workshop on Automation and Software Test. IEEE Computer Society, 2007:4.

[23] Cohen D M, Dalal S R, Fredman 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.

[24] 王子元, 徐寶文, 聶長(zhǎng)海. 組合測(cè)試用例生成技術(shù)[J]. 計(jì)算機(jī)科學(xué)與探索, 2008, 2(6):571-588.

THE REFINEMENT OF XML SCHEMA TYPE OF WEB SERVICES ARRANGEMENT SCENE

Wang Jin Ma Kai Yang Hongli

(CollegeofComputerScience,BeijingUniversityofTechnology,Beijing100124,China)

Web Services arrangement specifies the interaction among multiple Web services. In the actual development, interactive data type and interactive sequence may not be consistent with arrangement standard. It needs to generate the test data to check the conformance of the implementation with reference to the arrangement standard. Since arrangement scene describes the interactions sequence of each participant and the XML Schema type of its interaction information, the test data can be generated by the XML Schema. The indicators in XML Schema type lead to the uncertainty of the data type, so the method of the XML Schema type refinement is proposed to solve the problem based on combined test. By defining the XML Schema type tree and presenting the type tree refinement algorithm based on the combinatorial tool Cascade, the effectiveness is proved by examples.

Web Services arrangement XML Schema Indicator Type refinement Combined test

2015-12-24。王瑾，碩士，主研領(lǐng)域：Web服務(wù)編排。馬凱，碩士。楊紅麗，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.02.005