基于改進(jìn)Markov模型軟件測試策略

李澤雪,李相民,薛　亮

(1. 海軍航空工程學(xué)院,山東煙臺(tái)　264001; 2. 海軍裝備研究院，北京　100161)

基于改進(jìn)Markov模型軟件測試策略

李澤雪1,李相民1,薛亮2

(1. 海軍航空工程學(xué)院,山東煙臺(tái)264001; 2. 海軍裝備研究院，北京100161)

摘要:針對(duì)已有軟件測試Markov模型與工程實(shí)踐不符的情況,通過引入軟件需求覆蓋率改進(jìn)Markov模型。在改進(jìn)的Markov模型基礎(chǔ)上,本文以軟件測試過程中測試總代價(jià)最小為控制目標(biāo), 采用交叉熵方法修正測試剖面, 由優(yōu)化測試剖面生成測試用例序列。仿真結(jié)果表明這種方法能夠有效地降低軟件測試總代價(jià), 是一種有效的軟件測試方法。

關(guān)鍵詞:軟件測試;交叉熵法;覆蓋率

軟件測試是軟件生存周期中的一個(gè)重要組成部分,是保證軟件質(zhì)量的重要階段之一。軟件測試中,由于窮舉法的工作量太大[1],成本太高,在實(shí)際操作中一般不采用窮舉法。如何在對(duì)被測系統(tǒng)進(jìn)行有效測試的基礎(chǔ)上,通過優(yōu)化測試用例的選用盡可能地減少測試成本,是軟件測試領(lǐng)域中需要研究的一個(gè)關(guān)鍵性問題。

隨著測試剖面和Markov模型等概念的提出,使軟件測試在理論上有了一個(gè)大進(jìn)步?；跍y試剖面或Markov模型對(duì)測試用例進(jìn)行選取,能大幅提高測試用例選取的有效性。常見選取方式有:隨機(jī)選擇[2],這種方式根據(jù)測試剖面隨機(jī)的選擇測試用例;重要性測試,根據(jù)指定的權(quán)重大小選擇測試用例,測試那些用戶使用可能性高的路徑。

由于上述的測試方法沒有明確的優(yōu)化目標(biāo),成本都比較高。因此研究一種新的測試方法,對(duì)于降低軟件測試的總成本具有重要意義。

文獻(xiàn)[3]在解決測試資源分配問題時(shí),文獻(xiàn)[4]在采用搜索的方法測試時(shí),文獻(xiàn)[5]在提出改進(jìn)測試模型時(shí),文獻(xiàn)[6]討論Markov模型在軟件測試中的應(yīng)用時(shí),都提出了明確的優(yōu)化目標(biāo),證明這些測試方法在理論上十分有效,但這些測試方法與實(shí)際測試技術(shù)缺乏有效的切合點(diǎn),還沒有在工程實(shí)踐中得到應(yīng)用。

為了結(jié)合工程實(shí)踐,本文將測試需求覆蓋率引入到傳統(tǒng)的Markov模型中,并在傳統(tǒng)軟件測試方法學(xué)習(xí)的基礎(chǔ)上, 利用交叉熵法優(yōu)化軟件測試剖面,以軟件測試過程的總費(fèi)用最小為控制目標(biāo),優(yōu)化整個(gè)測試過程。

1Markov決策過程

Markov決策過程是一類重要的隨機(jī)過程,它最早是由俄國數(shù)學(xué)家Markov在1907年提出,Markov過程的核心是它的Markov性,即:如果系統(tǒng)在t0時(shí)刻所處的狀態(tài)是已知的,那么系統(tǒng)在t0時(shí)刻后將達(dá)到的狀態(tài)完全由系統(tǒng)在t0時(shí)刻所處的狀態(tài)決定,與系統(tǒng)在t0時(shí)刻之前所處的狀態(tài)沒有關(guān)系。這種“現(xiàn)在”已知的條件下,“過去”和“將來”相互獨(dú)立的特性叫做無后效性，也稱為Markov性,具有這種性質(zhì)的隨機(jī)過程叫做Markov過程[7]。這種性質(zhì)可以被用于模擬軟件測試的過程:軟件的下一狀態(tài)只與軟件當(dāng)前的狀態(tài)有關(guān)。

Markov決策過程主要包括決策時(shí)刻、狀態(tài)、決策、轉(zhuǎn)移概率和報(bào)酬這五個(gè)屬性?？捎梢粋€(gè)五元數(shù)組表示(S,A,{A(t)|st∈S},F,W),其中用S表示系統(tǒng)所有可能的狀態(tài)集合,即狀態(tài)空間,用A表示所有可用的決策組成的決策集,A也稱為決策空間,若在某一決策時(shí)刻,系統(tǒng)狀態(tài)st∈S,這時(shí)的所有可用決策可由集合{A(t)|st}表示,并且從集合{A(t)|st}中選取決策a作為這一時(shí)刻所采用的決策。該模型是一個(gè)在t=0,1,2,…上隨機(jī)可控的系統(tǒng),在某一決策時(shí)刻,系統(tǒng)的狀態(tài)為st,選取決策at∈A(t)后,會(huì)產(chǎn)生這樣一個(gè)結(jié)果:決策者將以代價(jià)Wst(A(t))使系統(tǒng)狀態(tài)由概率分布F(S|s,a)=P{St+1=s,At=a}轉(zhuǎn)移到下一個(gè)狀態(tài),一旦系統(tǒng)轉(zhuǎn)移到新的狀態(tài),系統(tǒng)將會(huì)選擇新的決策繼續(xù)循環(huán)決策過程。

2基于改進(jìn)Markov模型的軟件測試方法研究

在已有Markov模型中,測試結(jié)束的標(biāo)準(zhǔn)主要是所有缺陷都被檢測到[8]。相關(guān)研究表明這種方法能夠取得較好的測試效果。但是,這種測試方法還沒有在測試實(shí)踐中應(yīng)用。因?yàn)樵趯?shí)際測試過程中測試人員不可能知道軟件中缺陷的準(zhǔn)確數(shù)量,所以這種已有的測試方法并不符合實(shí)際情況。

在工程實(shí)踐中,測試人員通常把需求覆蓋率作為測試結(jié)束的標(biāo)準(zhǔn),實(shí)踐證明達(dá)到一定覆蓋率標(biāo)準(zhǔn)的軟件,通常其測試結(jié)果比較充分。因此本文將需求覆蓋率與軟件中剩余的缺陷數(shù)一起作為被測軟件的狀態(tài),并將需求覆蓋率和檢測到一定數(shù)量缺陷作為測試結(jié)束標(biāo)準(zhǔn)。

從缺陷數(shù)據(jù)庫中可得被測軟件不同版本的缺陷數(shù)量情況,由灰色模型預(yù)測理論預(yù)測軟件下一版本的缺陷數(shù)。假設(shè)被測軟件最初至少存在M個(gè)缺陷,測試的目標(biāo)是在測試覆蓋率到達(dá)100%的情況下至少發(fā)現(xiàn)軟件中的M個(gè)缺陷。在整個(gè)測試過程中,如果把每個(gè)決策時(shí)刻t(t=0,1,2,…)時(shí)軟件需求覆蓋率和軟件中的剩余缺陷數(shù)當(dāng)作t時(shí)刻系統(tǒng)的狀態(tài)st,決策是各個(gè)時(shí)刻t測試用例的選取,而且滿足t+1時(shí)刻系統(tǒng)的狀態(tài)st+1只與系統(tǒng)在t時(shí)刻所處的狀態(tài)st和采取的決策at有關(guān)。

定義

為了把Markov決策模型運(yùn)用到軟件測試過程中,對(duì)被測軟件作出如下一些假設(shè):

1) 用Nt表示被測系統(tǒng)t時(shí)刻的缺陷數(shù),初始時(shí)刻被測系統(tǒng)中至少含有M個(gè)缺陷;

2) 用Qt表示被測系統(tǒng)時(shí)刻的需求覆蓋率,初始時(shí)刻需求覆蓋率Q0=0;

3) 把每個(gè)決策時(shí)刻t(t=0,1,2,…)時(shí)軟件中的剩余缺陷數(shù)Nt和需求覆蓋率Qt作為t時(shí)刻系統(tǒng)的狀態(tài)St=(Nt,Qt);

4) 在每個(gè)時(shí)刻只需選取一個(gè)決策,并且最多只能發(fā)現(xiàn)一個(gè)缺陷;

5) 當(dāng)缺陷被檢測到時(shí),則認(rèn)為被檢測到的缺陷被剔除,即如果Nt=j,Zt=1,那么Nt+1=j-1;

6) 用qa表示測試用例a的覆蓋率,每使用一個(gè)用例,那么Qt+1=Qt+qa;

7) 若沒有檢測到缺陷,即若Nt=j,Zt=0,則Nt+1=j;

8) 目標(biāo)狀態(tài)是St=(0,100%)；

9) 系統(tǒng)在不同狀態(tài)下都有n個(gè)可選決策,用A表示可選的決策集合;

10) 時(shí)刻執(zhí)行決策a后,不論是否檢測到缺陷,花費(fèi)的代價(jià)都為Wst,本文主要指測試時(shí)間;

11) 不考慮缺陷移除所花費(fèi)的代價(jià)。若用τ表示系統(tǒng)狀態(tài)到達(dá)目標(biāo)狀態(tài)時(shí)所花費(fèi)的時(shí)間,則有

(1)

(12) 其中,ω表示軟件測試方法,由它決定測試過程中測試用例的選取,Eω表示相對(duì)于測試方法ω求期望值,WS(At)表示執(zhí)行選取的測試用例要花費(fèi)的代價(jià),Jω(N)表示測試過程中產(chǎn)生的總代價(jià)的期望值。

那么就可以把軟件測試過程當(dāng)作Markov決策過程,如圖1所示。

圖1　Markov決策過程

3基于交叉熵法求解測試目標(biāo)

交叉熵法是一種估計(jì)復(fù)雜隨機(jī)網(wǎng)絡(luò)中小概率事件發(fā)生概率的算法,其可以很好地解決組合優(yōu)化問題,因此近年來受到了廣泛的關(guān)注。Rubinstein首先創(chuàng)造性地提出了交叉熵法。并且在小概率事件的組合優(yōu)化模擬中運(yùn)用了這種方法。文獻(xiàn)[9]利用交叉熵法很好地解決了旅行商問題。文獻(xiàn)[10]將交叉熵法用于到緩沖區(qū)分配問題中。交叉熵法在最大割問題中[11]也體現(xiàn)出極大的優(yōu)勢。交叉熵法的獨(dú)特優(yōu)勢是定義了一個(gè)用來對(duì)算法進(jìn)行快速引導(dǎo)的精確的數(shù)學(xué)框架。從某種意義上說,交叉熵法是一種基于先期模擬理論的優(yōu)化學(xué)習(xí)算法。

用X=(X1,X2,…,Xn)表示測試用例按某個(gè)概率分布生成的序列集,其中隨機(jī)變量Xi=(i=1,2,…,n)按照測試剖面進(jìn)行選取,用pij表示在狀態(tài)Nt=i選擇決策a的概率,P=(pij)M×K是概率矩陣。定義γ*為采用不同測試方法ω生成測試用例序列X時(shí)花費(fèi)代價(jià)Jω的最小值,即

γ*=minJω

(2)

用f(x,u)表示測試用例序列x的聯(lián)合概率分布,f(x,u)由概率矩陣P唯一確定,那么測試問題則轉(zhuǎn)化為如何使式(2)取優(yōu)的問題。定義I(Jω≤γ)為測試用例X上不同γ∈R值的示性函數(shù)的集合,那么最優(yōu)選擇概率的確定問題可轉(zhuǎn)換為概率估計(jì)問題來求解:

(3)

其中,Pu和Eu分別是概率分布f(·,u)的概率測度和期望。

當(dāng)γ=γ*時(shí),估計(jì)l(γ)最直接的方法是采用重要抽樣法:根據(jù)決策集A上的概率分布g來抽取樣本x1,x2,…,xn,則l(γ)的估計(jì)為

(4)

顯然,當(dāng)概率分布g取

(5)

時(shí),只需要抽取一個(gè)樣本,即N=1就能得到1的一個(gè)無偏估計(jì)形式:

(6)

由上式可以看出,g*(xi)的選取依賴于未知參數(shù)l,而l難以確定。所以采用在概率分布f(·,u)的概率分布簇{f(·,υ)}中選取概率分布g的方法來解決這個(gè)問題,即選擇參數(shù)v使得概率分布簇f(·,υ)與概率分布g*(xi)之間差別最小。衡量兩個(gè)概率分布差別大小的常用測度是Kullback-leibler距離或交叉熵。定義Kullback-leibler距離為

=∫g(x)lng(x)dx-∫g(x)lnf(x)dx

(7)

這樣,最優(yōu)抽樣分布的確定問題就轉(zhuǎn)化成確定推斷參數(shù)υ,使得概率分布簇f(·,υ)與概率分布g*(xi)交叉熵最小的問,即

υ*=argmin-∫g*(x)lnf(x,υ)dx

(8)

然后有

υ*=argmaxEu[I(Jω≤γ)lnf(x,υ)]

(9)

由于測試用例序列x=(a0,a1,…)是根據(jù)概率矩陣P生成的,概率矩陣P就是推斷參數(shù)υ,而測試用例序列x的聯(lián)合概率分布為

(10)

滿足：

(11)

其中，i為測試用例序列x在運(yùn)行中經(jīng)歷的所有狀態(tài),j為測試用例序列x中在狀態(tài)st=i時(shí)選取的決策。

由拉格朗日乘法,建立如下方程:

(12)

(13)

由拉格朗日乘法可得最優(yōu)的決策選擇概率為

(14)

決策選擇概率估計(jì)為

(15)

在應(yīng)用交叉熵法時(shí),關(guān)鍵的問題是參數(shù)怎么在迭代中被修正。通常參數(shù)的修正是在一個(gè)兩步迭代過程中實(shí)現(xiàn)的。

1)適應(yīng)性修正γt。

2)適應(yīng)性修正vt

(16)

算法可如下表示:

Begin

Update(p)∥更新測試用例選擇概率

pij=1/K∥初始化為均勻分布

While(γt≠γt-1)∥中止條件

{

get(X);∥模擬生成測試序列

Updata(pij)∥更新測試用例選取概率

t++

}

End

算法流程圖如圖2所示。

圖2　求解最優(yōu)選擇概率流程圖

4仿真分析

為驗(yàn)證交叉熵法測試決策選擇概率的有效性,本節(jié)采用仿真的方法,比較交叉熵法與隨機(jī)測試的測試總成本。

由灰色預(yù)測理論,假設(shè)開始時(shí)軟件中至少含有缺陷數(shù)為M=7。決策空間A={1,2,3,4,5,6},相應(yīng)的缺陷檢測率為θ1=0.3,θ2=0.1,θ3=0.2,θ4=0.125,θ5=0.25,θ6=0.15,在不同狀態(tài)下采用不同行動(dòng)的測試代價(jià)用表1表示。

表1　不同狀態(tài)s下采用不同行動(dòng)a的測試成本

測試用例與需求覆蓋關(guān)系如表2所示。

算法中取N=1000,ρ=0.25,α=0.4時(shí),用交叉熵法進(jìn)行迭代過程中γ的變化曲線，如圖3所示。

圖3　參數(shù)日γ變化曲線

從仿真結(jié)果來看,參數(shù)在迭代中不斷修正,參數(shù)γ的變化趨勢不斷變小,并且朝著最優(yōu)值的方向逼近。從生成的最優(yōu)測試剖面可以看出:優(yōu)化測試剖面與Ws(a)/θs的比率和測試用例覆蓋情況有關(guān),比率較小的決策會(huì)被優(yōu)先選擇。因此,這些決策被選擇的概率要大于其它行動(dòng)。這與實(shí)際情況[12]是一致的。

表2　測試用例需求覆蓋情況

采用優(yōu)化測試剖面Popt和隨機(jī)測試分別進(jìn)行10輪抽樣1000次的測試模擬,兩種測試方法所需要的平均測試成本如圖4所示。

圖4　測試成本

5結(jié)束語

軟件測試的Markov模型將軟件測試過程當(dāng)作一個(gè)隨機(jī)過程來處理。本文給出了一個(gè)軟件測試的改進(jìn)Markov決策模型,在原始Markov模型的基礎(chǔ)上引入軟件需求覆蓋率,使模型更適用于工程實(shí)踐。將軟件測試的總費(fèi)用最小作為控制目標(biāo),并且采用交叉熵法來搜索軟件測試的最優(yōu)測試剖面,以優(yōu)化軟件的測試過程。仿真結(jié)果表明用這種方法優(yōu)化得到的測試剖面要優(yōu)于隨機(jī)測試方法的測試剖面,它可以顯著地減少測試用成本。這種方法使優(yōu)化軟件測試過程研究的實(shí)踐化向前邁進(jìn)了一步,為“基于搜索的軟件工程”[11]的研究提供了一種新嘗試。由于該方法采用的交叉熵法本身具有很強(qiáng)的適應(yīng)力,只需要處理較少的參數(shù)就可以保證算法的收斂性,它比其它方法具有更強(qiáng)的穩(wěn)健性[13-14],因此這種方法可以在軟件測試領(lǐng)域種廣泛的運(yùn)用。

參考文獻(xiàn):

[1]Jeya Mala D, Mohan V, Kamalapriya M. Automated software test optimisation framework Anartificial bee colony optimisation based approach[J]. Source: IET Software, 2010, 4(5): 334-348.

[2]Whittaker J A, Thomason M Q. A Markov chain model for statistical software testing[J]. IEEE Transaction on Software Engineering, 1994, 20: 812-824.

[3]Wang Zai, Ke Tang, Xin Yao. Multi-objective approaches to optimal testing resource allocation in modular software systems[J]. IEEE Transactions on Reliability, 2010,59(3):563-75.

[4]Anand Saswat, Burke Edmund K. An orchestrated survey of methodologies for automated software test case generation[J]. Journal of Systems and Software,2013,86(8):1978-2001.

[5]秦強(qiáng),胡昌振. 基于馬爾科夫決策過程的軟件測試與仿真[J]. 數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用, 2014,35(2):92-102.

[6]Bao Xiao’an, Yao Lan. Adaptive software testing based on controlled Markov chain[J]. Jisuanji Yanjiu yu Fazhan/Computer Research and Development,2012,49(6):1332-1338.

[7]劉克. 實(shí)用馬爾可夫決策過程[M]. 北京:清華大學(xué)出版社, 2004:3-15.

[8]Cai KY, Chen T.Y, Li Y. C., et al. Adaptive Testing of Software Components[J]. Proceedings of The 20thAnnual ACM Symposium on Applied Computing, Santa Fe, New Mexico, 2005: 1463-1469.

[9]Boer D P T, Kroese D P, Mannor S, Rubinstein R Y. A tutorial on the Cross-Entropy Method[J]. Annals of operations Research, 2005, 134(1): 19-67.

[10]Alon G, Kroese D P, Raviv T and Rubinstein R Y. Application of the Cross-Entropy Method to the Buffer Allocation Problem in a Simulation-Based Environment[J]. Annals of operations Research, 134:19-67.

[11]Rubinstein R Y. Cross-Entropy and Rara-Events for Maximal Cut and Bisect1ition Problems[C]. ACM Transactions on Modeling and Computer Simulation,27-53.[12]Margolin L. on the convergence of the cross-entropy method[J]. Annals of Operations Research, 2005,134(1):201-214.

[13]Harman M, Jones BF. Search-Based software engineering[J]. Information and Software Technology, 2001,43(14):833-839.

[14]Cai KY, Li YC, Ning YW. optimal software testing in the setting of controlled Markov chains[J]. European Journal of Operational Research, 2005,162(2):552-579.

Software Testing Strategy Based on Improved Markov Model

LI Ze-xue1, LI Xiang-min1, XUE Liang2

(1.Naval Aeronautical and Astronautical University, Yantai 264001;2.Naval Academy of Armament, Beijing 100161, China)

Abstract:A software testing method of optimizing testing strategy based on improved Markov model is presented in this paper. This method uses a new stochastic optimization method called Cross Entropy method. By iterative correcting of the testing profile in Markov model, we consider the minimization of testing cost and try to generate testing data automatically. The experimental results show that this optimization method is a promising option for tackling this problem. It can reduce the software testing cost effectively.

Key words:software testing; cross entropy method; rate of coverage

文章編號(hào)：1673-3819(2016)03-0108-05

收稿日期：2016-03-07

作者簡介：李澤雪(1991-),男,河北秦皇島人,碩士研究生,研究方向?yàn)榭刂评碚摷皯?yīng)用。 李相民(1965-),男,教授,博士生導(dǎo)師。

中圖分類號(hào):TP311.53

文獻(xiàn)標(biāo)志碼:A

DOI:10.3969/j.issn.1673-3819.2016.03.021

修回日期： 2016-03-14

薛亮(1976-),男,工程師。