WS－CDL測試路徑的生成與排序

劉翠翠 邱 棟 李必信

(東南大學計算機科學與工程學院，南京211189)

Web 服務編舞描述語言(Web service choreography description language，WS－CDL)［1－2］是一種應用廣泛的服務編舞語言.在使用WS－CDL 描述組合服務時，為盡早發(fā)現(xiàn)設計中的錯誤，減少維護開銷，需要對WS－CDL 進行測試.WS－CDL 規(guī)約指出，WS－CDL 不是一種可執(zhí)行的業(yè)務過程描述語言，也不是一種實現(xiàn)語言，因此目前沒有業(yè)界統(tǒng)一的執(zhí)行引擎，這也導致對WS－CDL 的測試工作研究甚少.文獻［3］將服務編舞行為建模成帶標簽的轉換系統(tǒng)，將XPath 和XML schema 與服務編舞的具體行為聯(lián)系起來，識別數(shù)據(jù)流，生成數(shù)據(jù)流測試準則.文獻［4］提出一種測試WS－CDL 的方法，該方法對當前路徑中的最后一個謂詞取反，得到下一條路徑再執(zhí)行;重復該過程直至所有路徑均被執(zhí)行則終止.該方法對WS－CDL 規(guī)約進行擴展，加入assertion 語句，用以描述WS－CDL 程序的設計者對程序的預期，便于在測試過程中與實際結果相比較.因此，若測試人員采用該方法對WS－CDL 程序進行測試，就需要以侵入方式修改內部代碼，從而改變了源程序.

對WS－CDL 組合流程進行測試時，如果運行所有的測試用例會導致測試開銷過高，因此研究者提出各種約簡測試集的方案［5－6］，以減小測試開銷，但這也可能會對錯誤定位有所影響.測試集排序技術［7－11］根據(jù)測試需求定義某種重要性準則，并對測試用例按重要性由高到低排序，即重要性高的測試用例優(yōu)先測試，這樣可以盡早地發(fā)現(xiàn)錯誤.

本文首先提出一種基于控制流圖的WS－CDL測試路徑生成方法，該方法對WS－CDL 程序進行解析，提取有用的元素信息，將程序轉換成WSCDL 控制流圖，并據(jù)此生成所有可能的測試路徑;然后提出2 種測試集排序策略對測試路徑進行排序，以提高發(fā)現(xiàn)錯誤的效率;最后通過實例分析，比較未排序和排序后的執(zhí)行效果.

1 WS－CDL 概述

WS－CDL 是基于XML 的描述語言，旨在從全局觀念出發(fā)，組合多個任意形式的參與者，通過點對點的交互方式進行協(xié)作，從而共同完成某個公共的目標.其中合作參與者的編程模型或平臺是任意的，點對點交互通過信道傳遞消息實現(xiàn).WS－CDL規(guī)約［2］中主要元素層次關系如圖1所示.

圖1 WS-CDL 主要元素的層次關系

2 WS－CDL 控制流圖CCFG

2.1 CCFG 定義

文獻［12］根據(jù)業(yè)務流程執(zhí)行語言(business process execution language，BPEL)的特點，提出適合BPEL 文檔結構的BPEL 流圖(BPEL flow graph，BFG)，用于對BPEL 測試.文獻［13］在BFG 基礎上擴充節(jié)點信息，形成擴展BPEL 流圖(eXtensive BPEL flow graph)，用于BPEL 的回歸測試.本文將此方法應用到WS－CDL 中，根據(jù)WSCDL 中元素特征，構造WS－CDL 文檔的WS－CDL控制流圖CCFG(choreography control flow graph).CCFG 的形式化定義如下:

定義1(WS－CDL 控制流圖CCFG)CCFG 是一個四元組〈N，E，s，f〉，其中N 為節(jié)點集，N =NN∪EBN ∪EMN ∪PBN ∪PMN ∪CBN ∪CMN ∪RBN∪RMN，且NN，EBN，EMN，PBN，PMN，CBN，CMN，RBN，RMN 分別為普通節(jié)點、單選分支節(jié)點、單選歸并節(jié)點、并發(fā)分支節(jié)點、并發(fā)歸并節(jié)點、選擇分支節(jié)點、選擇歸并節(jié)點、循環(huán)分支節(jié)點和循環(huán)歸并節(jié)點;E 為有向邊集;s 為開始節(jié)點;f 為終止節(jié)點;節(jié)點和有向邊統(tǒng)稱為CCFG 的元素.

進入節(jié)點的有向邊的數(shù)目稱為該節(jié)點的入度;從節(jié)點出去的邊的數(shù)目稱為該節(jié)點的出度.CCFG具有如下屬性:

1)普通節(jié)點的入度不大于1，出度大于等于1，如〈package〉，〈assign〉，〈interaction〉等.終止節(jié)點出度為0，入度大于等于1.普通節(jié)點和終止節(jié)點的所有入邊和出邊均會被觸發(fā).

2)分支節(jié)點和歸并節(jié)點是成對出現(xiàn)的，且分支節(jié)點的入度均為1，出度均大于1;歸并節(jié)點的入度均大于1，出度均為1.

3)EBN 和EMN 是一對單選節(jié)點(exclusive node)，對應WS－CDL 文檔中的〈choice〉，〈choice〉中描述2 個或多個活動，但每次執(zhí)行有且僅有一個活動被選擇，被選擇的活動對應的邊被觸發(fā).EBN的出度和EMN 的入度為〈choice〉中的活動數(shù)目.

4)PBN 和PMN 是一對并發(fā)節(jié)點(parallel node)，對應文檔中的〈parallel〉，〈parallel〉中包含多個并行執(zhí)行的活動，因此PBN 的出度和PMN 的入度為〈parallel〉中的活動數(shù)目，且所有的邊均被觸發(fā).

5)CBN 和 CMN 是一對選擇節(jié)點，由〈workunit〉的屬性guard 映射而來，guard 定義一個條件表達式，當〈workunit〉包含可選屬性guard 且該表達式為真時執(zhí)行〈workunit〉，否則跳過，因此CBN 的出度和CMN 的入度均為2.

6)RBN 和 RMN 是 一 對 循 環(huán) 節(jié) 點，由〈workunit〉的另一個可選屬性repeat 映射而來，repeat 類似于結構化程序中的while 結構，workunit 中的活動會重復執(zhí)行當且僅當repeat 對應的條件表達式為真，因此RBN 的出度和RMN 的入度均為2.

2.2 CCFG 構造

設N 是CCFG 的一個節(jié)點，則在WS－CDL 執(zhí)行過程中先于N 被執(zhí)行的第一個節(jié)點稱為節(jié)點N 的源節(jié)點;在N 被執(zhí)行后第一個執(zhí)行的節(jié)點稱為節(jié)點N 的目標節(jié)點.容易看出:

1)CCFG 的開始節(jié)點沒有源，終止節(jié)點沒有目標.

2)若N1的目標節(jié)點是N2，則N2的源節(jié)點是N1.

WS－CDL 中與活動流程密切相關的是〈choreography〉，而用于角色定義和信道類型定義的元素，如〈role〉，〈channelType〉等不影響控制流圖的結構，所以在構造CCFG 時忽略這些元素.又由上述性質2)可知源和目標是相互的，因此只要計算出所有節(jié)點的目標節(jié)點，根據(jù)相互性，所有節(jié)點的源節(jié)點也均被計算出.

構造CCFG 的流程如圖2所示.由于WS－CDL是基于XML 的描述語言，所以選擇XML 解析器DOM Parser 將WS－CDL 文檔解析成DOM 樹，然后根據(jù)DOM 樹提取有用的節(jié)點形成CCFG 節(jié)點，并確定各節(jié)點的源節(jié)點和目標節(jié)點，最后添加由源節(jié)點指向目標節(jié)點的有向邊，形成完整的CCFG.

圖2 CCFG 的構造流程

從DOM 樹提取CCFG 節(jié)點并確定該節(jié)點的源節(jié)點和目標節(jié)點的規(guī)則如下:

1)〈package〉是WS－CDL 的根元素，因此將〈package〉作為CCFG 的開始節(jié)點，其源節(jié)點為空，目標節(jié)點是在初始節(jié)點之后第一個被映射的節(jié)點.

2)〈assign〉映射為普通節(jié)點N，N 的源節(jié)點是先于N 被映射的第一個節(jié)點，目標節(jié)點是N 之后第一個被映射的節(jié)點.

3)〈workunit〉包含2 個可選屬性guard 和repeat，根據(jù)屬性的不同確定〈workunit〉的節(jié)點類型.

①若〈workunit〉包含的屬性是guard，生成選擇分支節(jié)點CBN、選擇歸并節(jié)點CMN 和普通節(jié)點NN 3 個節(jié)點.CBN 的目標節(jié)點有2 個，一是〈workunit〉子元素中第一個被映射成的節(jié)點(guard 中條件表達式為真時〈workunit〉體被觸發(fā))，二是CMN(guard為假時，程序跳過〈workunit〉直接到CMN).若〈workunit〉的子元素均不需要被映射成CCFG 節(jié)點，則CBN 的2 個分支均會直接連接到CMN，此時可能會發(fā)生無法區(qū)分這2 條路徑的情況.為避免此情況發(fā)生，在guard 為真的分支上增加一個NN，即將CBN 的一個目標節(jié)點改為由guard 生成的NN，該NN 的目標節(jié)點是〈workunit〉子元素中第一個被映射成的節(jié)點或者CMN.〈workunit〉子元素中最后一個被映射成的節(jié)點或者NN(當〈workunit〉中沒有需要映射成CCFG 節(jié)點時是NN)的目標節(jié)點是CMN.CMN 的目標節(jié)點是下一個需要映射成CCFG節(jié)點的節(jié)點.

②若〈workunit〉包含的屬性是repeat，類似于guard 的情況，也生成循環(huán)分支節(jié)點RBN、循環(huán)歸并節(jié)點RMN 和普通節(jié)點NN.RBN 的目標節(jié)點包括新生成的NN 和RMN.〈workunit〉子元素中最后一個被映射成的節(jié)點或者NN 的目標節(jié)點是RBN，RMN 的目標節(jié)點是下一個需要映射成CCFG 節(jié)點的節(jié)點.

4)〈parallel〉映射為一對并發(fā)節(jié)點.并發(fā)分支節(jié)點 PBN 的目標是〈parallel〉所有子元素〈workunit〉對應的分支節(jié)點，并發(fā)歸并節(jié)點PMN的源是所有〈workunit〉對應的歸并節(jié)點.

5)〈choice〉映射為一對單選節(jié)點.為〈choice〉的每一個子活動生成一個普通節(jié)點，這些普通節(jié)點就是單選分支節(jié)點的目標節(jié)點.單選歸并節(jié)點的源是〈choice〉所有子活動對應的最后一個節(jié)點.

6)互為源和目標的2 個節(jié)點通過一條由源節(jié)點指向目標節(jié)點的有向邊連接.

3 基于CCFG 生成測試路徑

3.1 測試路徑的表示方法

對源代碼而言，程序的一次執(zhí)行經(jīng)過的部分構成一條路徑;對于CCFG 而言，一條路徑就是由相鄰的節(jié)點和邊按順序連接而成的，它始于初始節(jié)點s，止于終止節(jié)點f.在CCFG 中，2 個節(jié)點間最多只存在一條邊，因此，路徑pf可用節(jié)點序列表示，即pf={s，n1，…，nk，nk+1，…，nn，f}，其中n1為s的目標節(jié)點，nk+1為nk的目標節(jié)點(1≤k ＜n)，f為nn的目標節(jié)點.

3.2 測試路徑集的構造

從s 出發(fā)遍歷CCFG，每一個分支都對應有新路徑產(chǎn)生，遍歷結束時所有可能的路徑均生成，即完成了測試路徑集的構造.對于并發(fā)結構，由于特定的輸入數(shù)據(jù)所產(chǎn)生的路徑具有相同的執(zhí)行條件和期望輸出，因此本文將它們視為同一條路徑.對于循環(huán)結構，為了避免環(huán)帶來的路徑的無限循環(huán)，僅構造2 條路徑以覆蓋循環(huán)分支上的所有節(jié)點.具體構造過程如下.

算法1 構造測試路徑集

4 測試路徑的排序

測試用例排序技術［7－11］按照某種準則對測試用例排序，使得高優(yōu)先級的測試用例可以先于低優(yōu)先級的測試用例進行測試.文獻［7］給出了其形式化定義.

定義2(測試用例排序問題)給定測試集T，PT 為T 的全排列，函數(shù)f 將PT 中的元素映射成實數(shù)，求解T′∈PT，使得

每個測試用例均與一條測試路徑一一對應，因而本文測試用例的排序問題即為對測試路徑的排序.本文給出2 種排序算法，并在下文給出案例分析，對比排序效果.

WS－CDL 是基于XML 的語言，其文檔由XML結構的元素組成，且WS－CDL 元素被映射成CCFG中的節(jié)點，而測試路徑是由節(jié)點構成的，因此可以認為測試路徑對應著WS－CDL 文檔中的部分元素，本文提出的2 種排序策略均是基于路徑中的元素數(shù)量的.

4.1 基于路徑中元素總數(shù)的排序策略

該排序策略基于以下假設:如果測試用例中覆蓋的代碼越多，則發(fā)現(xiàn)錯誤的可能性越大，因此為盡早地發(fā)現(xiàn)錯誤，應優(yōu)先選擇覆蓋代碼較多的測試用例.路徑中的節(jié)點對應WS－CDL 文檔中的元素，路徑中節(jié)點數(shù)越多說明該路徑對應的測試用例覆蓋的WS－CDL 元素也越多.因此本文提出的第1 個排序策略(簡稱T1)是以路徑中節(jié)點對應的元素數(shù)為排序準則，即計算每條路徑中的元素數(shù)，按照元素數(shù)由多到少對測試路徑排序，具體算法如下.

算法2 按路徑中元素總數(shù)遞減的排序算法

4.2 基于路徑中未覆蓋元素總數(shù)的排序策略

對于第1 種排序策略，可能存在以下情況:設有路徑p1，p2，p3，且3 條路徑中節(jié)點數(shù)依次減少，因此3 條路徑的排序序列是p1，p2，p3.p2優(yōu)先于p3，但p2中的部分節(jié)點可能在p1中已被覆蓋，此時p3中未被覆蓋的節(jié)點數(shù)比p2多，因此應優(yōu)先選擇p3，這是本文提出的對T1 的改進排序策略T2，具體算法如下.

算法3 按路徑中未覆蓋元素總數(shù)遞減的排序算法

5 實例分析

本節(jié)通過解析一個WS－CDL 實例程序構造出對應的CCFG，遍歷CCFG 后生成所有可能的測試用例，形成測試用例集，然后用2 種排序算法對測試路徑集排序，最后利用APFD(average percentage of faults detected)準則［7］比較初始路徑集和排序后路徑集的查錯效果.

圖3給出了一個簡單WS－CDL 程序的CCFG，該文檔由2 個〈choreography〉組成，包含3 個分支結構，其中第1 個〈choice〉嵌套了1 個〈workunit〉.存在錯誤的節(jié)點用黑色底紋標注.

為了便于生成測試路徑，在構造CCFG 時有些元素需要映射為一對節(jié)點.根元素〈package〉標志流程的開始，與其對應的〈/package〉標志流程的結束，因 此 解 析 WS－CDL 時，將〈package〉和〈/package〉分別映射為開始節(jié)點s 和終止節(jié)點f;表示分支結構的元素如〈workunit〉，〈parallel〉和〈choice〉，在CCFG 中也需要用一對節(jié)點表示，例如圖3中節(jié)點10 和節(jié)點11 表示同一個元素〈workunit〉.排序算法中是以元素數(shù)量作為準則的，因此從路徑中計算元素數(shù)量時應去除重復的節(jié)點，圖中重復元素用虛線表示.可看出，根據(jù)算法1圖3中共存在8 條測試路徑，按照生成的路徑順序(A-B-C-D-E-F-G-H)構成初始測試路徑集，如表1所示.

圖3 CCFG 實例

表1 路徑集和錯誤分布

根據(jù)算法2，即將路徑按元素總數(shù)遞減排序，則排序后的路徑序列為G-H-C-A-D-B-E-F;根據(jù)算法3，即將路徑按未覆蓋元素總數(shù)遞減排序，排序后的路徑序列為G-D-A-B-C-E-F-H.

按照未排序的測試路徑序列(A-B-C-D-E-FG-H)進行測試，執(zhí)行第1 條測試路徑A 發(fā)現(xiàn)錯誤f1;執(zhí)行第2 條測試路徑B 發(fā)現(xiàn)錯誤f1和f6，即多發(fā)現(xiàn)了一個錯誤，此時共發(fā)現(xiàn)2 個錯誤;執(zhí)行路徑C 后新發(fā)現(xiàn)錯誤f2和f3，此時共發(fā)現(xiàn)4 個錯誤;執(zhí)行路徑D 后發(fā)現(xiàn)錯誤f2，f3和f6，這些錯誤均已在前面的路徑中發(fā)現(xiàn)，因此此時發(fā)現(xiàn)的錯誤總數(shù)仍是4;執(zhí)行路徑E 后新發(fā)現(xiàn)錯誤f4，此時共發(fā)現(xiàn)5 個錯誤;執(zhí)行路徑F 后沒有發(fā)現(xiàn)新錯誤;執(zhí)行路徑G后，最后一個錯誤f5被發(fā)現(xiàn)，即經(jīng)過7 條測試路徑才找到所有的錯誤.

按照算法2 的測試路徑序列進行測試，路徑G，H，C，A 分別發(fā)現(xiàn)新錯誤2，1，2，1 個，即在執(zhí)行第4 條路徑后發(fā)現(xiàn)所有的錯誤.

按照算法3 的測試路徑序列進行測試，執(zhí)行第1 條測試路徑G 后發(fā)現(xiàn)2 個錯誤;第2 條測試路徑D 新發(fā)現(xiàn)3 個錯誤，第3 條測試路徑A 發(fā)現(xiàn)最后一個錯誤，即在執(zhí)行第3 條路徑后發(fā)現(xiàn)所有的錯誤.

圖4 3 種路徑序列的APFD

APFD 是一種常用的衡量排序技術的準則.圖4給出了3 種路徑序列APFD 值的比較.圖中8 條測試路徑將橫坐標8 等分，縱坐標表示已找到的錯誤占所有錯誤的百分數(shù)，圖中陰影部分的面積就表示APFD 值，其取值范圍為0～1，APFD 值越大，說明錯誤發(fā)現(xiàn)得越快.文獻［11］給出了APFD 的計算公式:

式中，m 表示程序中包含的錯誤數(shù);n 表示測試用例數(shù);Tm(1≤i≤m)表示第一次發(fā)現(xiàn)錯誤fi的測試用例在測試集中的位置.根據(jù)式(1)計算3 種情況下的APFD，分別為58.3%，77.1%和83.3%.可見，排序后可以更快地發(fā)現(xiàn)所有錯誤，并且基于未覆蓋元素總數(shù)的排序策略由于在選擇下一條最優(yōu)路徑時忽略已覆蓋的元素，避免覆蓋重復的錯誤，其找錯效率更高.

6 結語

本文提出一種用于生成服務編舞描述語言WS－CDL 測試路徑的控制流圖CCFG.根據(jù)WSCDL 元素特點，定義了普通節(jié)點、單選節(jié)點、并發(fā)節(jié)點、選擇節(jié)點和循環(huán)節(jié)點，并通過由源節(jié)點指向目標節(jié)點的有向邊連接成CCFG，基于CCFG 構造所有可能的路徑.為提高發(fā)現(xiàn)錯誤的效率，提出2種基于路徑中元素總數(shù)的排序算法，對路徑的執(zhí)行順序進行排序.通過實驗比較可知，按照排序后的序列測試WS－CDL，能夠更快地發(fā)現(xiàn)錯誤.基于路徑中未覆蓋元素總數(shù)的排序策略在選擇下一條最優(yōu)路徑時，忽略已覆蓋的元素，避免覆蓋重復的錯誤，可以更快地定位錯誤.

本文根據(jù)WS－CDL 的結構特點生成測試路徑，忽略了WS－CDL 中的數(shù)據(jù)信息，下一步將考慮在CCFG 中擴展數(shù)據(jù)信息，獲取更全面的WSCDL 信息.

向為本文提供寶貴意見的孫小兵、朱敏、吳曉娜、李加凱、齊珊珊等同學表示感謝.

References)

［1］Papazoglou M P，Traverso P，Dustdar S，et al.Service oriented computing:state of the art and research challenges［J］.Computer，2007，40(11):38－45.

［2］Kavantzas N，Burdett D，Ritzinger G，et al.Web services choreography description language version 1.0［EB/OL］.(2005－11－09)［2010－06－19］.http://www.w3.org/TR/ws－cdl－10/.

［3］Mei L，Chan W K，Tse T H.Data flow testing of service choreography［C］//Proceedings of the Joint 12th European Software Engineering Conference and 17th ACM SIGSOFT Symposium on the Foundations of Software Engineering.Amsterdam， The Netherlands，2009:151－160.

［4］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.Shanghai，China，2010:138－154.

［5］Michael R，Sehun T.Towards automating regression test selection for Web services［C］//Proceedings of the 16th International Conference on World Wide Web.New York，2007:1265－1266.

［6］Rohtermel G，Harrold M J，Ostrin J，et al.An empirical study of the effects of minimization on the fault detection capabilities of test suites ［C］//Proceedings of the International Conference on Software Maintenance.Bethesda，MD，USA，1998:34－43.

［7］Rothermel G，Untch R，Chu H C，et al.Prioritizing test cases for regression testing［J］.IEEE Transactions on Software Engineering，2001，27(10):929－948.

［8］Rothermel G，Untch R H，Chu C，et al.Test case prioritization:an empirical study［C］//Proceedings of the International Conference on Software Maintenance.Oxford，UK，1999:179－188.

［9］Mei L，Chan W K，Tse T H，et al.XML－manipulating test case prioritization for XML－manipulating services［J］.Journal of Systems and Software，2011，84(4):603－619.

［10］Mei L，Zhang Z，Chan W K，et al.Test case prioritization for regression testing of service－oriented business applications［C］//Proceedings of the 9th International Conference on Quality Software.New York，2009:901－910.

［11］Elbaum S，Malishevsky A G，Rothermel G.Test case prioritization:a family of empirical studies［J］.IEEE Transactions on Software Engineering，2002，28(2):159－182.

［12］Yuan Y，Li Z J，Sun W.A graph－search based approach to BPEL4WS test generation ［C］//Proceedings of the International Conference on Software Engineering Advances.Tahiti，Polynesia，2006:4031799.

［13］Wang D，Li B，Cai J.Regression testing of composite service:an XBFG－based approach［C］//Proceedings of Congress on Services Part Ⅱ.Beijing，China，2008:112－119.