基于Markov模型的Web服務(wù)軟件測(cè)試用例生成

申珅 黨向盈

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

關(guān)鍵詞：Markov模型；Web服務(wù)軟件；測(cè)試用例生成；變異測(cè)試

中國(guó)分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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月，李克強(qiáng)總理在政府工作報(bào)告中提出“互聯(lián)網(wǎng)+”行動(dòng)計(jì)劃，“互聯(lián)網(wǎng)+”作為一項(xiàng)國(guó)家戰(zhàn)略，為未來(lái)的各領(lǐng)域的發(fā)展指明了方向，軟件的應(yīng)用也因此迎來(lái)新的發(fā)展，但是軟件的可靠性和質(zhì)量卻沒有得到相應(yīng)的提高，成為制約軟件產(chǎn)業(yè)發(fā)展的一個(gè)重要因素。Web服務(wù)是互聯(lián)網(wǎng)上共享數(shù)據(jù)和功能的一種有效手段，是基于通信協(xié)議、服務(wù)描述、服務(wù)發(fā)現(xiàn)、Web協(xié)議和開放性XML標(biāo)準(zhǔn)的新一代的分布式計(jì)算模式。

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

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

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

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

該文基于Markov鏈?zhǔn)褂媚Ｐ停治鲎儺愺w的約束組合關(guān)系，以及生成有效覆蓋所有變異體的服務(wù)測(cè)試數(shù)據(jù)生成技術(shù)。將軟件測(cè)試結(jié)果的分析問題轉(zhuǎn)化為一個(gè)經(jīng)典概率問題，并基于馬爾可夫（Markov）鏈模型建立變異體之間的關(guān)聯(lián)，通過數(shù)學(xué)方法實(shí)現(xiàn)了軟件測(cè)試模型的簡(jiǎn)化，加速測(cè)試用例的生成，從而降低了測(cè)試的復(fù)雜度。

2 Web服務(wù)軟件變異測(cè)試過程

整個(gè)的測(cè)試過程應(yīng)該由以下幾個(gè)步驟組成：

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

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

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

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

5）變異充分度達(dá)到要求時(shí)，測(cè)試過程結(jié)束。

變異體生成工具主要分為兩個(gè)部分：解析OWL-S文檔，提取需要的輸入信息和工作流信息；對(duì)OWL-S進(jìn)行改動(dòng)，生成變異體。通過對(duì)OWL-S進(jìn)行變換可以生成變異體，變異體的生成可以通過XSLT對(duì)OWL-S進(jìn)行變換完成。解析OWL-S文檔需要充分利用已有的關(guān)于解析XML語(yǔ)言的工具包。

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

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

3 Markov預(yù)測(cè)模型

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

設(shè)初始狀態(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]有關(guān)，而n-1次之前的狀態(tài)無(wú)關(guān)，這也是狀態(tài)轉(zhuǎn)移的后無(wú)關(guān)性。如果多個(gè)事物在變動(dòng)的狀態(tài)轉(zhuǎn)移過程中，每一次變動(dòng)的狀態(tài)都具有無(wú)后效性，那么這些事物的集合，稱為馬爾可夫鏈[6]。

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

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

公式（1）可以遞推得到

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

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

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

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

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

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

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

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

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

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

[Qkill=MkillM-Mq] （3）

由式（3）可知，[Qkill]越大，說(shuō)明測(cè)試充分性越大。

5 實(shí)驗(yàn)結(jié)果和分析

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

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

6 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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鏈用戶瀏覽預(yù)測(cè)模型[J]. 計(jì)算機(jī)學(xué)報(bào)， 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)編輯：謝媛媛】