面向WS-BPEL程序的變異測試優化技術

孫昌愛 王 真 潘 琳

1(北京科技大學計算機與通信工程學院 北京 100083)2 (宇航智能控制技術重點實驗室 北京 100854)

面向服務的架構(service-oriented architecture, SOA)已經成為分布式應用程序的主要開發范式[1].由于單一的Web服務提供的功能有限，無法滿足復雜需求，因此需要將多個服務組裝以實現復雜的業務流程.WS-BPEL(business process execution language for Web service)是一種基于XML的服務組裝語言[2]，可以將多個不同的Web服務編制起來實現復雜的業務流程.由于被組裝的Web服務的動態性、松耦合性、不確定性以及互聯網環境的開放性，如何保證WS-BPEL程序的可靠性成為一個挑戰性問題[3].

變異測試是一種基于故障的軟件測試技術[4]，具有較強的故障檢測能力，廣泛用于評估測試用例集的完備性和測試技術的有效性[5].然而，由于變異測試產生的變異體數量龐大、等價變異體識別困難、缺乏相應自動化支持工具等原因，變異測試難以在實際中廣泛應用.在WS-BPEL變異測試方面，人們提出面向WS-BPEL程序的變異算子[6]，為WS-BPEL程序的變異測試提供基礎[7].在課題組前期研究工作中[8-10]，我們提出了一種面向WS-BPEL程序的變異測試框架和支持工具，評估了變異算子的有效性和不同變異算子模擬的故障被檢測的難易程度，發現了部分變異算子之間的包含關系.

在前期工作基礎上，本文進一步研究如何降低面向WS-BPEL程序的變異測試的開銷問題，從二階變異測試和變異算子優先級2個方面探索面向WS-BPEL程序的變異測試優化技術.本文的主要貢獻有3個方面：

1) 提出了2種面向WS-BPEL程序的變異測試優化技術，即面向WS-BPEL程序的二階變異優化技術和基于變異算子優先級的優化技術.

2) 開發了面向WS-BPEL程序的變異測試集成化支持工具μBPEL，支持WS-BPEL程序變異測試的全過程，同時支持本文提出的變異測試優化技術.

3) 使用6個WS-BPEL程序實例驗證并評估提出的優化技術的有效性.

1 相關工作

介紹變異測試優化和WS-BPEL測試相關的研究工作.

1.1 變異測試優化技術

變異測試是一種基于故障的軟件測試技術[4].對待測程序P植入符合語法規則的錯誤，將錯誤版本的程序稱為變異體，植入的故障類型稱為變異算子.對于給定的變異體M,如果存在某個測試用例，使得P和M展現出不同的執行行為(通常為不同輸出結果)，則稱這個變異體M被“殺死”.如果對于任意的測試用例，P和M的執行結果均相同，則稱該變異體M為等價變異體.

變異測試具有較強的故障檢測能力[5]，可以產生較好的測試效果[11].然而，變異測試存在的主要不足有3個方面：1)變異體數量龐大導致的計算開銷；2)等價變異體識別困難；3)缺乏自動化支持工具.人們主要從變異體選擇和變異體執行2個角度研究變異測試的優化技術[5].

變異體選擇優化關注如何從生成的大量變異體中選擇出典型的變異體.Mathur和Wong[12]提出一種變異體隨機選擇方法，對Mothra系統中的22種變異算子產生的變異體，采用不同的比例隨機選擇變異體.該方法可以大幅度減少測試開銷，同時變異評分并沒有明顯降低.King和Offutt[13-14]提出了一種變異算子選擇方法，根據FORTRAN語言變異算子的測試有效性對其進行選擇，采用選擇后的變異算子能產生數目較少且更難被殺死的變異體.Hussain[15]根據測試用例的檢測能力對所有變異體進行聚類分析，選擇出變異體.Langdon等人[16]應用多目標方法指導生成高階變異體，該方法可以有效地產生比一階變異體更難檢測的高階變異體，同時產生等價變異體的概率更小，減少了測試開銷.在前期工作中，我們提出一種路徑感知的變異體精簡方法，利用程序的結構信息設計變異體精簡策略，有效地減少了變異測試的開銷[17].在WS-BPEL程序的變異測試優化技術方面，我們提出一種基于包含關系的變異算子優化技術[10]，分析WS-BPEL程序的變異算子產生的變異體檢測的包含關系，進行變異算子約簡.

變異體執行優化關注減少變異體的執行時間，主要包括變異體檢測優化、變異體變異優化和并行執行變異體優化方法[5].Krauser等人[18]提出一種基于SIMD(single instruction multiple data)計算機的并發執行變異體方法.此方法對變異體的無變異部分執行1次，變異的部分進行并發執行，有效地減少變異體執行時間.

1.2 WS-BPEL測試技術

與傳統程序相比，WS-BPEL程序具有4個新特點[19]：1)WS-BPEL提供一種顯式的集成機制組裝Web服務，而這樣的集成在傳統程序中是隱式；2)WS-BPEL程序的服務可以采用不同語言實現，而傳統程序中的模塊通常由同一種語言實現；3)WS-BPEL程序表示為XML文件，不同于傳統應用程序；4)WS-BPEL通過流(flow)活動支持并發機制、通過連接(link)支持同步機制.WS-BPEL程序的新特性，導致了WS-BPEL程序的故障類型不同于傳統應用程序.

人們提出了多種面向WS-BPEL程序的測試技術.文獻[20]將基于WS-BPEL描述的Web服務組裝轉化為擴展的著色Petri網(extended colored Petri net， ECPN)，提出了一種基于ECPN控制流和數據流結合的測試方法.針對WS-BPEL程序的并發特點，我們提出了一種面向場景的WS-BPEL測試用例生成方法[21]，并開發了相應的支持工具[22].Lee和Offutt[23]探索了將變異測試應用到Web服務測試中.Boonyakulsrirung等人[24]提出一種面向WS-BPEL的弱變異測試框架，通過犧牲變異得分來提高變異測試的效率.Estero-Botaro等人[7]使用遺傳算法來獲得變異體集合的子集，選擇出高質量的變異體.

目前，人們已經開發了多個面向WS-BPEL程序的變異測試支持工具.Domínguez-Jiménez等人[25]開發了WS-BPEL程序變異測試支持工具GAmera，支持變異體生成、測試用例執行和測試結果統計.Boonyakulsrirung和Suwannasart[26]開發了WeMuTe，支持WS-BPEL程序的弱變異測試.在前期研究工作中，我們開發了一個面向WS-BPEL程序的變異測試框架，并開發相應支持工具[8-9]，支持變異體生成、變異測試的執行及結果分析.

2 WS-BPEL程序變異測試優化技術

從二階變異測試和變異算子優先級2個方面，分別提出了變異測試的優化技術MuSOM和MuPri.

2.1 基于二階變異的優化技術MuSOM

一種減少變異測試中變異體數量的方法是高階變異體優化技術，由高階變異體替代一階變異體進行測試.一階變異體指對原始程序應用一個變異算子且植入一處錯誤生成的變異體；高階變異體指對原始程序植入多處錯誤生成的變異體.一個高階變異體可以看成由多個一階變異體復合而成.高階變異體優化技術的提出基于2個推測[5]：1)執行一次M階變異體等同于執行M個一階變異體；2)高階變異體比一階變異體產生等價變異體的概率小.基于這2個推測可以看出，高階變異體優化技術主要是通過減少待執行變異體數目和等價變異體識別開銷來降低變異測試的開銷.

本文提出一種面向WS-BPEL程序的二階變異優化技術(簡稱為MuSOM).二階變異體生成算法主要有3種，分別為LastToFirst，DifferentOperators，RandomMix算法[27].其中LastToFirst算法通過首尾組合2個一階變異體的方式生成二階變異體，生成的二階變異體數量為一階變異體數量的一半；DifferentOperators算法通過組合不同變異算子生成的一階變異體生成二階變異體，生成的二階變異體數量不小于生成變異體最多的變異算子產生的一階變異體的數量；RandomMix算法隨機組合2個一階變異體生成二階變異體，生成的二階變異體數量為一階變異體數量的一半.3種算法的基本思想都是通過一階變異體組合生成二階變異體，但限制生成的二階變異體數量的策略不同.其中，LastToFirst算法和RandomMix算法生成的二階變異體數量相對確定(約為一階變異體數量的50%)，而Different-Operators算法生成二階變異體數量不確定.本文研究的WS-BPEL程序可應用的變異算子的種類較少、不同變異算子生成的一階變異體數量不均衡，DifferentOperators算法不適用.RandomMix算法與LastToFirst算法相似，主要區別在于一階變異體的選擇次序.因此，本文采用LastToFirst算法生成二階變異體集合.

LastToFirst算法[27]按照首尾依次組合2個一階變異體的方式生成二階變異體，過程如圖1所示.其中，P指待測程序，M1至Mn代表待測程序P的一階變異體，M1,n及M2,n-1等代表通過首尾依次組合2個一階變異體生成的二階變異體.

Fig. 1 Procedure of LastToFirst algorithm圖1 LastToFirst 算法生成二階變異體過程

MuSOM描述的二階變異體生成步驟如下：

1) 根據給定WS-BPEL程序P生成一階變異體，得到的變異體集合表示為M1o={M1,M2,…,Mn}.我們按照一階變異體產生的順序對變異體命名并編號為1～n(n為一階變異體的總數).

2) 將M1o中的一階變異體首尾依次組合生成二階變異體，得到二階變異體集合為M2o={M1,n,M2,n-1,M3,n-2,…}.具體說來，將編號為1與編號為n的一階變異體組合得到二階變異體M1,n，編號為2與編號為n-1的一階變異體組合得到二階變異體M2,n-1，將編號為3與編號為n-2的一階變異體組合得到二階變異體M3,n-2,以此類推，生成二階變異體集合.當n為奇數時，將一階變異體M(n+1)2與M(n+1)2+1組合生成二階變異體.

2.2 基于變異算子優先級的優化技術MuPri

在變異測試中，有些變異算子生成的變異體可以被絕大多數測試用例檢測(“殺死”)，有些算子生成的變異體只能被特殊的測試用例檢測.若一些較難檢測的變異體都能被給定的測試用例集檢測，那么該測試用例集也能檢測那些容易被測殺的變異體.基于以上猜想，我們從變異體執行順序的角度，提出一種基于變異算子優先級的變異測試優化技術，首先使用可以產生較難檢測變異體的變異算子，然后再使用產生較易檢測變異體的變異算子.

為了評價變異算子產生的變異體檢測的難易程度，引入變異算子質量度量指標.這里約定P為待測的WS-BPEL程序；TS為測試用例集，TS={t1,t2,…,tn}，其中ti為測試用例集中第i個測試用例，n為測試用例集的用例總數；MO表示WS-BPEL的變異算子集合，MO={O1,O2,…,Ok}，其中Oi表示第i個變異算子，k為變異算子總數.

將變異算子質量定義為

(1)

其中，NOi表示Oi變異算子產生的非等價變異體總數.不難看出，上述定義可從故障檢測率(fault detection rate,FDR)推導而來.故障檢測率FDR定義為測試用例檢測變異體的比例，廣泛用來衡量測試用例的故障檢測能力:

(2)

基于變異算子質量定義，我們提出一種基于變異算子優先級的優化技術(簡稱為MuPri)，通過衡量變異算子質量，為變異算子分配測試優先級.具體過程為：首先，對大量的WS-BPEL程序進行變異測試；然后，根據測試結果計算變異算子的質量，按照質量由高到低的順序為其排序，質量好的變異算子在變異測試中分配較高的優先級，質量差的變異算子分配較低的優先級，即按照變異算子優先級順序指導生成變異體集合.

算法1. 測試用例排序算法.

輸入：實例程序P、變異算子集合O、有序的測試用例集TS={t1,t2,…,tm};

輸出：排序后的測試用例集TS′.

① 從O中選擇適用于P的變異算子集合OP；

② 對OP中變異算子按算子質量由高到低排序，得到變異算子序列OP：OP1,OP2,…,OPn；

③ 令i=1,TS′=?；

④ WHILEi≤nDO

⑤ 生成OPi的一階變異體集合MOi(P)={m1,m2,…,mk}；

⑥ WHILEMOi(P)≠? DO

⑦ 添加一個測試用例t到TS′;

⑧ FOR ALLmj∈MOi(P) DO

⑨ 以t測試用例執行mj;

⑩ IFmj被“殺死” THEN

MuPri技術不僅可以依據變異算子的優先級，優先使用質量好的變異算子生成變異體，提高變異體集質量，還可以為測試用例集合排序，得到故障檢測效率更高的測試用例集，解決測試用例優先級問題.MuPri實現的測試用例排序的過程如算法1所示.

3 支持工具μBPEL

Fig. 2 Architecture of μBPEL圖2 μBPEL工具系統結構圖

在前期工作中[8-9]，我們開發了一個面向WS-BPEL程序的變異測試支持工具μBPEL，支持變異體的生成、測試用例的執行和測試結果驗證.本文通過擴展μBPEL進一步支持本文提出的變異測試優化技術.圖2描述了μBPEL工具的系統結構.各個組件的功能描述如下：

1) 變異體生成.負責為待測WS-BPEL程序生成一階或二階變異體.

① WS-BPEL解析.解析WS-BPEL程序.

② 算子管理器.針對各種變異算子的匹配與操作，實現對相應節點的變異處理.

③ XML文件讀/寫.負責WS-BPEL程序文件的讀入和變異體輸出.

④ 變異體生成.生成一階或二階變異體.

2) 變異體優化.支持變異體隨機選擇優化.

① 參數配置.接收用戶輸入的待優化的變異體集合路徑和變異體精簡比例.

② 變異體獲取.根據變異體精簡比例，從變異體集合中隨機獲取相應數目的變異體.

3) 測試用例生成.根據WS-BPEL原始文件，輸出期望的測試用例.課題組前期研發了2種測試用例生成工具[22]，場景用例生成將WS-BPEL程序轉換為圖模型，基于給定的覆蓋準則生成測試場景和數據；隨機用例生成根據用戶輸入的約束條件，隨機生成滿足條件的測試用例.

4) 變異測試執行.執行測試用例并獲取輸出結果.

① 執行環境配置.根據WS-BPEL的配置信息，獲取WS-BPEL服務的端口號和操作名稱配置執行環境.

② 程序選取.通過用戶輸入的文件路徑，依次獲取原始程序和變異體程序文件.

③ 用例讀取.讀入并解析相應的測試用例文件，獲取用例輸入變量的類型、數目、值及用例個數等信息.

④ 待測程序執行.調用WS-BPEL引擎依次對原始程序和變異體執行測試用例集并輸出結果.

5) 測試結果評估.負責對輸出結果進行統計分析，由結果統計和報告獲取2個模塊組成.

① 結果統計.對執行相同測試用例的原始程序和變異體的輸出結果逐一進行對比.若二者結果不同，表明該測試用例將變異體“殺死”，標記為“T”；否則，記為“F”.依次記錄變異體被測殺的狀態，并統計出針對變異體的每個測試用例集合的故障檢測率信息.

② 報告獲取.根據結果統計的輸出結果，計算

① http://www.activevos.com/developers/sample-apps

變異得分并生成報告，包括變異體數目、被殺死變異體數目和變異得分信息.

4 實驗評估

采用經驗研究驗證與評估本文提出的面向WS-BPEL程序的變異測試優化技術的有效性.

4.1 實驗對象

實驗對象包括6個WS-BPEL程序實例：SupplyChain實例[19](P1)、SmartShelf實例(P2)[19]、SupplyCustomer實例(P3)[2]、LoanApproval實例(P4)[2]、CarEstimate實例(P5)①和TravelAgency[28]實例(P6).表1總結這些程序實例的具體信息.

Table 1 WS-BPEL Programs表1 WS-BPEL程序實例的基本信息

4.2 實驗指標

本文使用變異得分(mutation score,MS)、故障檢測率FDR(見式(2))、測試用例序列檢測故障的平均百分比(average of the percentage of faults detected,APFD)這3個指標度量變異測試優化方法的有效性.

1) 變異得分MS.對于給定的測試用例集TS，殺死變異體數量與非等價變異體數量的比例[4]，用來衡量測試用例集的充分程度.變異得分計算為

(3)

其中，P代表被測程序，Nk表示被殺死的變異體數量，Nm表示變異體總數量，Ne代表等價變異體的數量.變異得分越高，說明測試用例集“殺死”的變異體越多，測試用例集越有效.

2) 測試用例序列檢測故障的平均百分比APFD.用于評價測試用例集的故障檢測效率，常用于衡量不同測試用例優先級技術的排序效果[29].APFD的計算公式為

(4)

其中，TS表示具有特定序列的測試用例集，P表示待測程序，n表示測試用例的個數，m表示被檢測故障的總數，reveal(i,TS)表示最早檢測出第i個故障所執行的測試用例的位置.APFD量化了測試用例序列的效率和效能，即APFD的數值越大，測試用例集故障檢測效率越高.本文采用APFD來度量序列化的測試用例的故障檢測效率.

4.3 實驗設置

討論與2種變異測試優化技術評估相關的變異體生成和測試用例集.

1) 一階和二階變異體生成.針對表1中的WS-BPEL程序實例，采用本文開發的μBPEL工具生成一階變異體集合(記為M1o)和二階變異體集合(記為M2o).表2總結了生成的一階變異體和二階變異體情況.

Table 2 First-Order and Second-Order Mutants ofWS-BPEL Programs

2) 測試用例生成.在前期工作中[10]，我們采用等價類劃分[30]、邊界值分析[30]、面向場景測試技術[22]和隨機測試技術[30]這4種技術生成測試用例.為了減少不同測試用例生成技術對變異測試結果的影響，最終生成5組測試用例集，分別記為Tx，Ty，Tz，Tu，Tw，如表3所示.|Tx|，|Ty|，|Tz|，|Tu|，|Tw|表示WS-BPEL程序實例對應的每組測試用例集的大小.需要指出的是，測試用例集的數量依賴于程序的規模和所使用的測試用例生成技術.為了保證實驗的公平性，本文采用這些測試用例集評估優化技術的有效性.

Table 3 Test Suits of WS-BPEL Programs表3 WS-BPEL實例的測試用例集合

4.4 優化技術評估結果與分析

4.4.1 MuSOM技術評估結果

MuSOM技術有效性的評估過程描述如下：首先，采用測試用例集Tx對一階變異體集合M1o和二階變異體集合M2o進行變異測試，得到能夠殺死所有變異體的測試用例集TC；然后，采用測試用例集TC對一階變異體集合M1o進行變異測試，統計變異得分.

表4總結了生成的二階變異體集合中的等價變異體情況；圖3統計了一階變異體集合和二階變異體集合的變異得分情況.

Table 4 Equivalent Mutant of WS-BPEL Programs表4 WS-BPEL程序實例的等價變異體情況

Fig. 3 Mutation score of WS-BPEL programs圖3 WS-BPEL程序的一階與二階變異體的變異得分

上述實驗結果表明：

1) 在使用同樣數目和種類的變異算子情況下，M2o集合數量約為M1o的一半，相對于一階變異測試，減少了約50%的待測變異體(如表2所示)；M2o中的等價變異體數目(NE)總和為0，而M1o中存在48個等價變異體(如表4所示)，主要原因是，與一階變異體相比，二階變異體中植入了多處錯誤，降低了等價變異體的生成概率.由此可見，MuSOM技術極大地減少了等價變異體的出現概率(一階變異測試中等價變異體約為28%)，大幅度降低等價變異體識別帶來的計算開銷.

2) 在采用相同的測試用例集情況下，二階變異測試的變異得分均為100%，而一階變異測試的變異得分有所不同.其中，P3和P5實例中的變異得分為100%；P1和P6實例中的變異得分分別是97.1%和97.5%，接近于100%；P2和P4實例的變異得分分別是72.6%和73.1%.主要原因是，二階變異體中存在多處錯誤，更容易被檢測出來.相應地，在相同測試用例集情況下，二階變異測試的變異得分高于一階變異測試.

綜上所述，相對于傳統的(一階)變異測試而言，二階變異測試技術可以減少約50%的變異體和減少約28%的等價變異體識別開銷，同時并沒有大幅度降低衡量測試用例集充分性的能力.

4.4.2 MuPri技術評估結果

MuPri技術依據變異算子質量對測試用例集進行排序.通過對比排序前后的測試用例集的APFD評估MuPri技術的有效性.具體步驟有3個：

1) 變異算子優先級排序.首先采用測試用例集Tx，Ty，Tz，Tu，Tw分別執行實例程序和其一階變異體集合M1o，計算變異得分(MS)和故障檢測率(FDR).需要說明的是，如下變異算子在實例程序中不適用：EAA，EEU，ELL，EMD，EMF，AFP，AIS，AWR，AJC，APM，APA，XMC，XMT，XTF，XER，XEE；變異算子ECC和EAP產生的均為等價變異體.限于篇幅，我們不列出每個變異算子的變異得分和故障檢測率(參考文獻[9]).

表5列出了可適用的變異算子優先級排序結果.依據變異算子質量Qo的平均值，對變異算子排序并分配優先級.優先級的數值越小，表示該變異算子的優先級越高.

Table 5 Priority of Mutation Operators表5 變異算子優先級

2) 測試用例集排序.針對每個WS-BPEL程序P，首先得到變異得分100%的測試用例集TS，使用變異算子優先級得到排序的測試用例集TS′，分別計算測試用例集TS和TS′的APFD值.以SupplyChain程序為例，表5列出了適用的變異算子優先級序列為：CDE→CCO→CDC→ERR→AIE→ASF→AEL→CFA→EIN→ASI→ACI.采用測試用例排序過程(算法1)對SupplyChain實例的測試用例集進行排序，結果如表6所示.表6中，“√”表示測試用例集TS中第1個將該變異體“殺死”的用例.最終得到測試用例集TS的順序是“T1→T2→T3”.

Table 6 Results of Executing Test Suite (TS) on SupplyChain表6 SupplyChain程序執行測試用例TS結果

Note:“√” means the first test case that kills the mutant.

使用排序后的測試用例集TS執行沒有排序的變異體集合，結果如表7所示.其中“√”表示第1個將變異體“殺死”的測試用例，Location表示該用例在TS中的位置，“×”表示測試用例不能“殺死”變異體，“～”表示測試用例沒有執行.最終計算得到APFD的值是74.5%.類似地，我們可以得到其他WS-BPEL程序優化前后的APFD值.

Table 7 Results of Mutation Testing表7 變異體測試結果

Notes:“√” means that the test case kills the mutant; “×” means that the test case cannot kill the mutant; “～” means that the test case is not executed to kill the mutant.

3) 比較排序前后測試用例集的有效性.表8列出了每個WS-BPEL程序的變異算子優化前后的測試用例集的APFD.

Table 8 Comparison Between APFD of Original Test Suiteand that of Prioritized Test Suite Using MuPri

上述實驗結果表明：使用MuPri優化技術后得到的測試用例序列的APFD值都大于或等于優化前的APFD值.MuPri優化技術優先使用較難被檢測的變異算子生成變異體，采用這樣的變異體集合為測試用例集排序，可以得到故障檢測效率更高的測試用例集.因此，MuPri技術通過對變異算子進行優先級排序提高了測試用例集的故障檢測效率.

5 總 結

本文針對WS-BPEL程序的變異測試開銷大的問題，提出了2種面向WS-BPEL程序的變異測試優化技術MuSOM和MuPri.其中，MuSOM從變異體數量精簡角度，將二階變異應用WS-BPEL測試；MuPri提出了變異算子質量的概念，通過度量變異算子優先級指導變異體的使用順序.開發了面向WS-BPEL程序的變異測試支持工具μBPEL，該工具實現了本文提出的優化技術，有助于對WS-BPEL程序進行高效的變異測試.最后，采用6個WS-BPEL程序實例驗證并評估了提出的變異測試優化技術的有效性.實驗結果表明:本文提出的變異測試優化技術極大地降低了WS-BPEL程序的變異測試開銷，提高了變異測試的效率.

未來將在2個方面進一步開展研究工作：1)與其他相關的優化技術進行比較，評估所提出的優化技術的效率；2)擴展驗證的WS-BPEL程序集，特別地，目前的程序集適用的變異算子種類較少，需要采用更大規模的實例程序對優化技術進行更全面的評估.