基于Markov模型的Web服務軟件測試用例生成

申珅 黨向盈

摘要：軟件測試是保證 Web 服務軟件質(zhì)量的重要技術之一。變異測試是一種面向缺陷的測試技術，變異測試用例生成效率將影響 Web 服務測試的效率和成本。該文針對Web服務軟件，基于Markov模型高效生成變異測試用例。首先，隨機生成一定樣本容量的測試數(shù)據(jù)，針對每一個合約變異體，基于弱變異測試準則，執(zhí)行Web 服務方法及其變異體，根據(jù)合約變異預言來判斷變異體是否被殺死；然后基于Markov鏈預測模型，計算變異體之間的關聯(lián)度；再根據(jù)變異體之間關聯(lián)度，生成變異體序列，即與其他變異體關聯(lián)度大的變異體排在序列的前面；最后，采用遺傳算法，依次序列順序，生成殺死合約變異體的測試用例。

關鍵詞：Markov模型；Web服務軟件；測試用例生成；變異測試

中國分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）28-0265-03

Test Data Generation for Web Service Software Based on Markov Model

SHEN Shen， DANG Xiang-ying

（ Department of Information and Electrical Engineering， Xuzhou Institute of Technology， Xuzhou 221000，China）

Abstract： Software testing is one of the important technologies to ensure the quality of Web service software. Mutation testing is a defect-oriented testing technique. The efficiency of generating test data for mutation testing will affect the cost of Web service testing. In this paper， we generating test data for Web service software by mutation testing based on Markov model. Firstly， we randomly generate test data of a certain sample size， implement the mutants and its original Web service program based on the weak mutation test criterion， and determine whether the mutants is killed according to the contract mutation prediction. Then， we calculate the correlation between the mutants， based on which we generate the mutant sequence， i.e.， the mutants that have more correlation with other mutants are in the front of the sequence. Finally， we generate test data that kill mutants by the sequential order based on GA.

Key words： Markov model； web service software； test data generation； mutation testing

1 背景

2015年3月，李克強總理在政府工作報告中提出“互聯(lián)網(wǎng)+”行動計劃，“互聯(lián)網(wǎng)+”作為一項國家戰(zhàn)略，為未來的各領域的發(fā)展指明了方向，軟件的應用也因此迎來新的發(fā)展，但是軟件的可靠性和質(zhì)量卻沒有得到相應的提高，成為制約軟件產(chǎn)業(yè)發(fā)展的一個重要因素。Web服務是互聯(lián)網(wǎng)上共享數(shù)據(jù)和功能的一種有效手段，是基于通信協(xié)議、服務描述、服務發(fā)現(xiàn)、Web協(xié)議和開放性XML標準的新一代的分布式計算模式。

Web服務（Web Service）技術是基于互聯(lián)網(wǎng)的電子服務的基礎技術。Web服務是通過網(wǎng)絡實現(xiàn)發(fā)布、查找和調(diào)用的具有自描述能力的軟件構件，通過在網(wǎng)絡上暴露的應用接口，能夠方便地對其實現(xiàn)調(diào)用。Web服務采用Http協(xié)議進行通信，由于任何運行Web服務瀏覽器的機都在使用Http協(xié)議，因此，Web服務具有平臺無關性。在此之前，沒有一個應用程序通信標準是獨立于平臺、組建模型和編程語言。

Web服務測試用例自動生成，是軟件測試自動化研究的核心內(nèi)容之一[1]。由于無法得知服務組件的實現(xiàn)細節(jié)，服務接口描述信息就成為測試用例生成的重要依據(jù)。但是，僅憑接口描述直接生成的測試用例質(zhì)量差，無法滿足實際缺陷檢測的需要。

變異測試[2]是一種基于錯誤的測試方法，基本原理是使用變異算子，即合乎語法規(guī)則對程序源代碼做微小的改動，改動后的程序被稱作為變異體。如果某條測試用例允許原程序和變異體，能夠產(chǎn)生不同的輸出結果或影響，則稱其殺死了變異體，那么該測試用例是有效的，應該予以保留并利用。如果無法區(qū)分兩者，則認為測試用例無法定位錯誤、變異代碼沒有被執(zhí)行到。通過這種方法，可以生成殺死變異體的測試用例，從而有效擴充測試集，有利于測試用例的生成和選擇。變異測試也常被用于評價測試用例集的質(zhì)量，也被用于輔助生成具有很高缺陷檢測能力的測試用例，而且，在服務軟件測試中也已經(jīng)得到了初步應用。

基于Markov預測Zuckerman 等[3]最早提出了基于 Markov 模型的用戶訪問預測， Markov 模型是一種簡單而經(jīng)典的預測模型，但高階 Markov 模型所覆蓋的狀態(tài)空間十分龐大，導致計算復雜度過高；而低階 Markov 模型預測準確率較低。邢永康等[4]提出并建立了一種基于用戶分類的新模型，多Markov鏈預測模型提高了預測準確率，但時間復雜度較高。

該文基于Markov鏈使用模型，分析變異體的約束組合關系，以及生成有效覆蓋所有變異體的服務測試數(shù)據(jù)生成技術。將軟件測試結果的分析問題轉化為一個經(jīng)典概率問題，并基于馬爾可夫（Markov）鏈模型建立變異體之間的關聯(lián)，通過數(shù)學方法實現(xiàn)了軟件測試模型的簡化，加速測試用例的生成，從而降低了測試的復雜度。

2 Web服務軟件變異測試過程

整個的測試過程應該由以下幾個步驟組成：

1）解析0WL-S文檔，提取輸入信息和流程信息。

2）根據(jù)提取的輸入信息，生成初始測試數(shù)據(jù)集，可以隨機生成，也可采用等價劃分、邊界法等常規(guī)的測試用例生成方法。

3）分析流程信息，找到文檔中滿足變異條件的點，結合具體變異的方法，生成變異體。

4）分別執(zhí)行原服務和變異后的服務，比較結果，相同則選取或設計新的測試用例。結果不同，意味著變異體被殺死，標記測試用例為有效。

5）變異充分度達到要求時，測試過程結束。

變異體生成工具主要分為兩個部分：解析OWL-S文檔，提取需要的輸入信息和工作流信息；對OWL-S進行改動，生成變異體。通過對OWL-S進行變換可以生成變異體，變異體的生成可以通過XSLT對OWL-S進行變換完成。解析OWL-S文檔需要充分利用已有的關于解析XML語言的工具包。

變異算子可根據(jù)具體的Web服務進行調(diào)整，可以包含簡單的傳統(tǒng)變異算子，也可以包含專門 針對待測Web服務所對應的OWL-S文檔而設計的變異算子。利用這些變異算子生成變異體后，以殺死變異體為目標，生成測試用例，作為最后的輸出。

由此可見，變異體盡早被殺死，則執(zhí)行的次數(shù)越少，測試用例的選擇決定了變異體是否能盡早被殺死，因此如何對測試用例進行選擇，將影響著變異測試的效率。該文提出的測試用例選擇策略，實質(zhì)是對變異體選擇策略，優(yōu)先選擇的變異體生成的測試用例質(zhì)量越高。而且從執(zhí)行的測試用例的數(shù)量進行考慮，基于Markov鏈模型選擇的測試用例數(shù)量，最大限度地減少執(zhí)行次數(shù)，降低測試代價，提高效率。

3 Markov預測模型

Markov是俄國著名數(shù)學家，由于最早提出了預測方法，命名馬爾可夫方法[5]。Markov方法的基本思想來源于現(xiàn)實世界的這樣一類事物，它的變化只與近期狀態(tài)有關，而與過去的狀態(tài)無關。該文中Markov的狀態(tài)為變異體，變異體被殺死的狀態(tài)與另一（多）個變異體被殺死之間的關聯(lián)。

設初始狀態(tài)為[S0]，它可以經(jīng)過多中狀態(tài)變化，記這些狀態(tài)為[S0，S0，...，Sn-1，Sn]，到事物經(jīng)過n次變化，到了狀態(tài)[Sn]，該狀態(tài)只與前一次狀態(tài)[Sn-1]有關，而n-1次之前的狀態(tài)無關，這也是狀態(tài)轉移的后無關性。如果多個事物在變動的狀態(tài)轉移過程中，每一次變動的狀態(tài)都具有無后效性，那么這些事物的集合，稱為馬爾可夫鏈[6]。

馬爾可夫過程體現(xiàn)了事物狀態(tài)變化的一個特點，事物由前一種狀態(tài)變化到后一種狀態(tài)，雖然與以往狀態(tài)無關，但在變化的過程中需要有個轉移中間狀態(tài)，設定事物的前一種狀態(tài)為[Sn-1]，后一種狀態(tài)為[Sn]，轉移中間狀態(tài)為D，三者關系為

[Sn=Sn-1×D] （1）

公式（1）可以遞推得到

[Sn=S0×Dn-1] （2）

式（2）代表了馬爾可夫本人創(chuàng)立的預測理論的基本推導過程。

運用馬爾可夫理論對系統(tǒng)進行可靠性分析，首先馬爾可夫過程屬于隨機過程，需要有三個基本的描述量[33]，即概率向量、概率矩陣和轉移概率矩陣。記概率向量為[Δ（a1，a2，...，an）]，其中[a1，a2，...，an≥0，i=1nai=1]；概率矩陣為[n×n]的方陣；轉移矩陣為[D]。Markov過程具有遍歷性，無論在哪個狀態(tài)開始，經(jīng)過相當多的轉移次數(shù)后，到達預定狀態(tài)的概率接近一個常數(shù)。這個性質(zhì)可以幫助預測系統(tǒng)在經(jīng)過相當長的狀態(tài)轉移后，能夠到達一個穩(wěn)定的狀態(tài)。

4 優(yōu)先選擇變異體策略

變異算子是變異系統(tǒng)的重要部分，是產(chǎn)生變異體的依據(jù)。與傳統(tǒng)的程序變異類似，通過對形式化的合約定義，做微小的語法修改來產(chǎn)生變異后的合約，但并未給出所采用的合約變異算子及變異預言。我們借鑒了傳統(tǒng)程序變異中的成熟變異算子。

表1中的變異算子，可對 Web 服務方法的合約進行變異，產(chǎn)生合約變異體。由于合約語句比一般的程序少很多，因此它生成的變異體個數(shù)和花費的時間都低于傳統(tǒng)的程序變異。合約變異體將與原 Web 服務組合形成 Web 服務的變異體。

在針對程序語句的變異測試中，一般采用程序的運行結果作為區(qū)分變異體與原程序的條件。由于我們變異Web服務的內(nèi)部實現(xiàn)，Web服務的運行結果不會在變異前后發(fā)生改變，因此將合約檢查結果的一致與否作為判斷變異體是否被殺死的條件。

首先采用隨機發(fā)生成一定樣本容量的測試數(shù)據(jù)，針對每一個變異體，基于弱變異測試準則，執(zhí)行Web 服務方法及其變異體，根據(jù)合約變異預言來判斷變異體是否被殺死；然后再基于Markov鏈預測模型，計算變異體之間的關聯(lián)；再根據(jù)變異體之間關聯(lián)度，排序變異體，即與其他變異體關聯(lián)性大的變異體排在前面；最后，采用遺傳算法，依次殺死排序好的變異體。

該文基于Markov鏈預測模型排序變異體，那么先殺死的變異體，測試用例生成的質(zhì)量越高，它們殺死其他變異體的概率越大，那么序列后面的變異體，就不用再生成測試用例，這說明，該方法可以提高變異測試的效率，降低了反復執(zhí)行變異體的代價。

此外，由于變異充分度可被用于評價測試用例集的優(yōu)劣，因此存在以殺死盡可能多的變異體為目標來生成測試用例生成策略。為了求解變異得分，設生成的合約變異體為的數(shù)量為[M]，等價變異體數(shù)目為[Mq]，那么生成的測試用例測試集，執(zhí)行Web 服務方法及其變異體，統(tǒng)計殺死的變異體為[Mkill]，則變異得分為

[Qkill=MkillM-Mq] （3）

由式（3）可知，[Qkill]越大，說明測試充分性越大。

5 實驗結果和分析

為了驗證該文所提出方法的有效性 我們基于測試 Web 服務的原型，采用傳統(tǒng)方法和該文方法，測試5個Web服務軟件，考察生成合約變異體數(shù)目，執(zhí)行次數(shù)，變異得分情況。

從該表中可以看出，針對5個被測程序，該文方法生成的測試用例數(shù)目更少，變異得分更高。說明，該文方法是高效的，有利于降低合約變異測試代價，提高Web服務測試的效率。

6 結束語

Web服務得到了廣泛關注和應用，其測試需求也日益增大。但由于Web服務的源代碼不對用戶公開，用戶只能獲得包含接口信息的OWL-S文檔，其該文檔描述了服務組合的功能、模型和流程，增加相關信息和執(zhí)行語義，可從中提取一些測試所需的信息。該文提出的方法直接以OWL-S文檔合約作為變異對象，針對不同的測試需求采用不同的變異算子，基于Markov鏈預測模型確定變異體優(yōu)先選擇策略，優(yōu)先生成序列前面的變異測試用例，從而降低測試的代價，提高Web服務測試的效率。

參考文獻：

[1] Dalley J L. The art of software testing[J]. Aerospace & Electronics Conference， 1979， 17（2）： 757-760. vol.2.

[2] DeMillo R A， Lipton R J， Sayward F G. Hints on test data selection： help for the practicing programmer[J]. IEEE Computer， 1978， 11（4）： 34-41.

[3] Zukerman I， Albrecht D W， Nicholson A E. Predicting Users Requests on the WWW[C]// International Conference on User Modeling. Springer-Verlag New York， Inc. 1999： 275-284.

[4] 刑永康， 馬少平. 多Markov鏈用戶瀏覽預測模型[J]. 計算機學報， 2003（11）： 1510-1517.

[5] Fei H， Wang Z， Wang S. A Reliability Assessment Method of Urban Mass Transport Software Based on Markov Model[C]// Fourth International Conference on Computational Intelligence and Communication Networks. IEEE， 2012： 943-947.

[6] Wang R， Ma S. Stability and stabilization for nonlinear discrete-time singular Markov jump systems with time-varying delay[C]// Control and Decision Conference. IEEE， 2013： 3874-3879.

【通聯(lián)編輯：謝媛媛】