劉翠翠 邱 棟 李必信

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京211189)

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

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

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

1 WS－CDL 概述

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

圖1 WS-CDL 主要元素的層次關(guān)系

2 WS－CDL 控制流圖CCFG

2.1 CCFG 定義

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

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

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

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

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

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

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

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

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

2.2 CCFG 構(gòu)造

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

1)CCFG 的開始節(jié)點(diǎn)沒有源，終止節(jié)點(diǎn)沒有目標(biāo).

2)若N1的目標(biāo)節(jié)點(diǎn)是N2，則N2的源節(jié)點(diǎn)是N1.

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

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

圖2 CCFG 的構(gòu)造流程

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

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

2)〈assign〉映射為普通節(jié)點(diǎn)N，N 的源節(jié)點(diǎn)是先于N 被映射的第一個(gè)節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)是N 之后第一個(gè)被映射的節(jié)點(diǎn).

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

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

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

4)〈parallel〉映射為一對(duì)并發(fā)節(jié)點(diǎn).并發(fā)分支節(jié)點(diǎn) PBN 的目標(biāo)是〈parallel〉所有子元素〈workunit〉對(duì)應(yīng)的分支節(jié)點(diǎn)，并發(fā)歸并節(jié)點(diǎn)PMN的源是所有〈workunit〉對(duì)應(yīng)的歸并節(jié)點(diǎn).

5)〈choice〉映射為一對(duì)單選節(jié)點(diǎn).為〈choice〉的每一個(gè)子活動(dòng)生成一個(gè)普通節(jié)點(diǎn)，這些普通節(jié)點(diǎn)就是單選分支節(jié)點(diǎn)的目標(biāo)節(jié)點(diǎn).單選歸并節(jié)點(diǎn)的源是〈choice〉所有子活動(dòng)對(duì)應(yīng)的最后一個(gè)節(jié)點(diǎn).

6)互為源和目標(biāo)的2 個(gè)節(jié)點(diǎn)通過一條由源節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)的有向邊連接.

3 基于CCFG 生成測(cè)試路徑

3.1 測(cè)試路徑的表示方法

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

3.2 測(cè)試路徑集的構(gòu)造

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

算法1 構(gòu)造測(cè)試路徑集

4 測(cè)試路徑的排序

測(cè)試用例排序技術(shù)［7－11］按照某種準(zhǔn)則對(duì)測(cè)試用例排序，使得高優(yōu)先級(jí)的測(cè)試用例可以先于低優(yōu)先級(jí)的測(cè)試用例進(jìn)行測(cè)試.文獻(xiàn)［7］給出了其形式化定義.

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

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

WS－CDL 是基于XML 的語言，其文檔由XML結(jié)構(gòu)的元素組成，且WS－CDL 元素被映射成CCFG中的節(jié)點(diǎn)，而測(cè)試路徑是由節(jié)點(diǎn)構(gòu)成的，因此可以認(rèn)為測(cè)試路徑對(duì)應(yīng)著WS－CDL 文檔中的部分元素，本文提出的2 種排序策略均是基于路徑中的元素?cái)?shù)量的.

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

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

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

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

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

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

5 實(shí)例分析

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

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

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

圖3 CCFG 實(shí)例

表1 路徑集和錯(cuò)誤分布

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

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

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

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

圖4 3 種路徑序列的APFD

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

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

6 結(jié)語

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

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

向?yàn)楸疚奶峁氋F意見的孫小兵、朱敏、吳曉娜、李加凱、齊珊珊等同學(xué)表示感謝.

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.