国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于Markov鏈?zhǔn)褂媚P偷募铀俳y(tǒng)計(jì)測(cè)試方法

2011-08-24 06:11:22張德平查日軍
關(guān)鍵詞:總費(fèi)用概率分布測(cè)試數(shù)據(jù)

張德平 查日軍

(1南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 210016)

(2上海市計(jì)算機(jī)軟件評(píng)測(cè)重點(diǎn)實(shí)驗(yàn)室,上海 201112)

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

軟件測(cè)試過(guò)程中由于窮舉測(cè)試工作量太大,實(shí)踐上不可行,導(dǎo)致一切實(shí)際測(cè)試都不徹底,不能保證被測(cè)試程序中不存在軟件錯(cuò)誤.因此如何精選少量的測(cè)試用例對(duì)系統(tǒng)進(jìn)行有效的測(cè)試,是軟件測(cè)試研究中的關(guān)鍵問(wèn)題[1].目前,運(yùn)用統(tǒng)計(jì)學(xué)原理指導(dǎo)測(cè)試用例的產(chǎn)生和選擇,對(duì)測(cè)試數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析的軟件統(tǒng)計(jì)測(cè)試方法在理論上已經(jīng)取得了很大進(jìn)展,并在工程實(shí)踐中取得了良好的效果[2-10].

然而,對(duì)于高可靠軟件特別是安全關(guān)鍵軟件,其關(guān)鍵操作如緊急事故處理等操作,由于使用概率非常小,在基于使用的統(tǒng)計(jì)測(cè)試中往往得不到充分測(cè)試,而這類操作的可靠性要求往往很高,其失效會(huì)造成嚴(yán)重的后果.如果采用傳統(tǒng)的統(tǒng)計(jì)測(cè)試方法,即使花費(fèi)很長(zhǎng)的測(cè)試時(shí)間也難以有效地對(duì)該安全關(guān)鍵軟件實(shí)施充分的測(cè)試.因此,在軟件測(cè)試過(guò)程中,如果能有針對(duì)性地暴露出對(duì)軟件可靠性影響較大的軟件缺陷,加速軟件測(cè)試,將可以快速增加軟件可靠性,還可顯著減少軟件測(cè)試開銷.目前,國(guó)內(nèi)外針對(duì)軟件可靠性加速測(cè)試技術(shù)的研究還比較少[11],因此有必要對(duì)其進(jìn)行深入研究.

本文基于Markov鏈?zhǔn)褂媚P吞岢隽艘环N加速統(tǒng)計(jì)測(cè)試方法,以軟件總費(fèi)用最小為目標(biāo),引入一種新的測(cè)試充分性判定準(zhǔn)則來(lái)均衡測(cè)試成本與軟件投放后的失效風(fēng)險(xiǎn),利用交叉熵方法優(yōu)化軟件測(cè)試剖面,增加了關(guān)鍵操作的測(cè)試機(jī)會(huì),加速了軟件測(cè)試且降低了軟件總費(fèi)用.

1 基于費(fèi)用的Markov鏈?zhǔn)褂媚P?/h2>

Markov鏈?zhǔn)褂媚P褪且粋€(gè)具有唯一初態(tài)和終態(tài)的Markov鏈,可用強(qiáng)連通有向圖G=(V,A)和函數(shù)p:V×V→[0,1]表示,具有如下性質(zhì):

1)V={1,2,…,n}為節(jié)點(diǎn)集,表示軟件系統(tǒng)的使用狀態(tài).

2)A為邊集,其元素表示在某個(gè)狀態(tài)下選定某個(gè)操作時(shí)軟件狀態(tài)間的轉(zhuǎn)移.從狀態(tài)i到狀態(tài)j的邊e定義為一個(gè)有序?qū)?i,j),任意2個(gè)狀態(tài)i和j之間的一個(gè)方向最多只有一條有向邊相連.

3) 轉(zhuǎn)移概率 p(i,j)滿足0≤p(i,j)≤1,表示從狀態(tài)i一步轉(zhuǎn)移到狀態(tài)j的概率.整個(gè)軟件系統(tǒng)狀態(tài)之間的轉(zhuǎn)移概率p(i,j)可用轉(zhuǎn)移概率矩陣P表示,即 P=(p(i,j))n×n.

假定狀態(tài)1為初態(tài),狀態(tài)n為終態(tài),并且狀態(tài)n為吸收態(tài),它表示一旦進(jìn)入狀態(tài)n就不再離去,即 p(n,n)=1,p(n,j)=0,?j≠n.每一個(gè)狀態(tài) i∈V都是從初態(tài)可達(dá)的,即在G中總存在一條從狀態(tài)1到狀態(tài)i的有向路徑.每條邊e均可估計(jì)出如下參數(shù)[10]:失效概率 f(e),投放后的失效風(fēng)險(xiǎn)l(e),測(cè)試成本c(e),易知l(e)?c(e).不失一般性,假定失效邊在操作過(guò)程中總是失效,一旦經(jīng)過(guò)測(cè)試,失效邊均看作正確操作,不再造成軟件失效.進(jìn)一步假定[12]:

1)邊(i,j)的每一次操作運(yùn)行都有一個(gè)先驗(yàn)失效概率 f(i,j)≥0.

2)不同操作是否引起軟件失效相互獨(dú)立.

3)軟件投入運(yùn)行期間,失效邊(i,j)至少歷經(jīng)一次,造成失效風(fēng)險(xiǎn)l(i,j)發(fā)生.

4)總失效風(fēng)險(xiǎn)由各邊失效風(fēng)險(xiǎn)累加形成.

定義一個(gè)測(cè)試數(shù)據(jù)集 x={e1,e2,…,em},ek∈A(k=1,2,…,m)為包含初態(tài)1和終態(tài)n的一個(gè)測(cè)試數(shù)據(jù).根據(jù)規(guī)格說(shuō)明書或用戶實(shí)際使用生成測(cè)試數(shù)據(jù)集x的概率分布稱為操作剖面,即轉(zhuǎn)移概率矩陣P.邊e可以在測(cè)試數(shù)據(jù)集x中出現(xiàn)多次,即測(cè)試數(shù)據(jù)集x中可以包含多條從初態(tài)1到終態(tài)n的路徑.由假定可知,運(yùn)行測(cè)試數(shù)據(jù)集x的測(cè)試成本為

測(cè)試前,每條邊是否造成軟件失效是不確定的,定義示性函數(shù)If(e),對(duì)于給定的邊e,如果測(cè)試過(guò)程中相對(duì)于邊e的操作造成軟件失效,則令I(lǐng)f(e)=1,否則令 If(e)=0.顯然,E[If(e)]=f(e).

假定軟件投入運(yùn)行后,軟件失效均發(fā)生在平穩(wěn)狀態(tài)下.引入示性函數(shù)Ir(e)來(lái)描述過(guò)程是否達(dá)到平穩(wěn)狀態(tài),即如果隨機(jī)歷經(jīng)邊e的狀態(tài)是平穩(wěn)狀態(tài)時(shí)令I(lǐng)r(e)=1,否則Ir(e)=0.由示性函數(shù)If(e)與Ir(e)定義知,它們相互獨(dú)立.令ˉA?A表示未經(jīng)測(cè)試邊的集合,由假設(shè)可知只有ˉA中的邊才可能因失效造成失效風(fēng)險(xiǎn).則平穩(wěn)狀態(tài)下因未測(cè)試邊失效造成的失效風(fēng)險(xiǎn)的期望可表示為

由If(e)與Ir(e)的獨(dú)立性及期望的性質(zhì)可得

式中,E[Ir(e)]=q(i,j)=q(e)為平穩(wěn)狀態(tài)下邊 e=(i,j)被歷經(jīng)的概率.記πi為平穩(wěn)狀態(tài)下狀態(tài)i(i=1,2,…,n)發(fā)生的概率,由 Markov過(guò)程轉(zhuǎn)移概率與絕對(duì)概率之間的關(guān)系以及遍歷性定理可知,平穩(wěn)狀態(tài)下邊(i,j)被歷經(jīng)的概率為 q(i,j)=πip(i,j).

按照操作剖面P生成測(cè)試數(shù)據(jù)集x進(jìn)行測(cè)試,當(dāng)測(cè)試數(shù)據(jù)集足夠大時(shí),有可能測(cè)試完所有的邊,使得ˉA=?,此時(shí)失效風(fēng)險(xiǎn)的期望L(ˉA)=0.然而,隨著測(cè)試數(shù)據(jù)集x邊數(shù)的增長(zhǎng),相應(yīng)的測(cè)試成本C(x)也會(huì)增加,因此軟件測(cè)試停止時(shí)間取決于失效風(fēng)險(xiǎn)與測(cè)試成本的均衡.即生成測(cè)試數(shù)據(jù)集的最佳邊數(shù)是使得軟件總費(fèi)用(失效風(fēng)險(xiǎn)與測(cè)試成本)最小時(shí)的邊數(shù).然而,這樣生成測(cè)試數(shù)據(jù)集依然存在一個(gè)問(wèn)題:小概率高風(fēng)險(xiǎn)的操作被測(cè)試到的可能性很小,生成的測(cè)試數(shù)據(jù)集并不一定是最佳測(cè)試數(shù)據(jù)集.為解決此問(wèn)題,本文采用一種導(dǎo)向性啟發(fā)式方法調(diào)節(jié)轉(zhuǎn)移概率,確定一個(gè)最優(yōu)(或近優(yōu))測(cè)試剖面(即測(cè)試中用來(lái)生成測(cè)試數(shù)據(jù)的概率分布),然后根據(jù)最優(yōu)測(cè)試剖面,均衡失效風(fēng)險(xiǎn)和測(cè)試成本生成最優(yōu)(或近似最優(yōu))測(cè)試數(shù)據(jù)集.這類問(wèn)題可歸結(jié)為:確定一個(gè)最優(yōu)測(cè)試剖面T*,根據(jù)T*生成測(cè)試數(shù)據(jù)集x使得期望軟件總費(fèi)用S(x)最小,即

式中,參數(shù)a說(shuō)明失效風(fēng)險(xiǎn)相對(duì)于測(cè)試成本的重要程度,與合同、客戶人數(shù)、市場(chǎng)信譽(yù)等因素有關(guān),在實(shí)際應(yīng)用中需要事先估計(jì).

2 測(cè)試充分性準(zhǔn)則

當(dāng)測(cè)試資源不受約束時(shí),統(tǒng)計(jì)測(cè)試按最優(yōu)測(cè)試剖面選擇邊進(jìn)行測(cè)試.測(cè)試初始階段,測(cè)試成本隨測(cè)試邊數(shù)的增加而增加,而失效風(fēng)險(xiǎn)則隨測(cè)試邊數(shù)的增加而減少,并且由失效風(fēng)險(xiǎn)降低的費(fèi)用要遠(yuǎn)比增加的測(cè)試成本多,因此軟件總費(fèi)用呈下降趨勢(shì);隨著已測(cè)試邊數(shù)的增加,失效風(fēng)險(xiǎn)降低速度減小,測(cè)試成本增加,測(cè)試一定數(shù)量的邊后,軟件總費(fèi)用降到最低;隨后,增加的測(cè)試成本多于失效風(fēng)險(xiǎn)減少的費(fèi)用,軟件總費(fèi)用呈上升趨勢(shì).

記 S(xi-k),S(xi)和 S(xi+k)分別表示測(cè)試數(shù)據(jù)集為 xi-k={e1,e2,…,ei-k}, xi={e1,e2,…,ei}和 xi+k={e1,e2,…,ei+k}時(shí)的軟件總費(fèi)用.由最優(yōu)停止理論,統(tǒng)計(jì)測(cè)試的最優(yōu)停止準(zhǔn)則可采用一步向前看準(zhǔn)則(1-stage look-ahead rule):令k=1,從初始狀態(tài)出發(fā),依據(jù)轉(zhuǎn)移概率矩陣選取下一次操作(增加測(cè)試邊),如果滿足

則在測(cè)試數(shù)據(jù)集中停止增加測(cè)試邊,最佳測(cè)試數(shù)據(jù)集為xi.然而,在實(shí)際應(yīng)用中由于選擇測(cè)試邊的測(cè)試剖面并不一定為最優(yōu)測(cè)試剖面,相繼選擇的幾條邊并不一定能減少失效風(fēng)險(xiǎn),這樣可能會(huì)造成軟件總費(fèi)用有一個(gè)小的上升擾動(dòng)后繼續(xù)降低.為避免得到一個(gè)局部最優(yōu)測(cè)試數(shù)據(jù)集,這里采用向前看k步準(zhǔn)則(k-stage look-ahead rule).即對(duì)于給定正整數(shù)k,如果軟件總費(fèi)用滿足

則在測(cè)試數(shù)據(jù)集中停止增加邊,最佳測(cè)試數(shù)據(jù)集為xi.

3 加速統(tǒng)計(jì)測(cè)試技術(shù)

3.1 交叉熵方法

應(yīng)用交叉熵方法[13]需解決的問(wèn)題是:如何產(chǎn)生隨機(jī)樣本以及如何在每一次迭代中修正參數(shù).

設(shè)x為根據(jù)轉(zhuǎn)移概率矩陣P生成的一個(gè)測(cè)試數(shù)據(jù)集,則由Markov鏈的馬氏性知測(cè)試數(shù)據(jù)集x出現(xiàn)的概率為

式中,i為測(cè)試數(shù)據(jù)集x中所有出現(xiàn)過(guò)的狀態(tài);j為依附邊(i,j)∈A的狀態(tài).令γ*為失效風(fēng)險(xiǎn)S(x)在所有測(cè)試數(shù)據(jù)集組成的集合X中的最小值,則問(wèn)題可改寫為確定一個(gè)最佳轉(zhuǎn)移概率矩陣(即測(cè)試剖面),由此測(cè)試剖面生成測(cè)試數(shù)據(jù)集x*,使得

定義{I{S(x)≤γ}}為X上不同γ∈R值的示性函數(shù)集合,則式(6)中最優(yōu)測(cè)試剖面確定問(wèn)題可轉(zhuǎn)化為如下概率估計(jì)問(wèn)題來(lái)求解:

式中,Pu和Eu為相對(duì)于概率分布f(·;u)的概率測(cè)度和期望.

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

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

時(shí)只需抽取一個(gè)樣本即可得l的一個(gè)方差為零的無(wú)偏估計(jì).

從式(9)可看出,g*依賴于未知參數(shù)l,很難確定.因此一般在概率分布f(·;u)的概率分布簇{f(·;v)}中選取概率分布g來(lái)解決這個(gè)問(wèn)題,即確定推斷參數(shù)v使得f(·;v)與概率分布g*差別達(dá)到最小.常用來(lái)衡量2個(gè)概率分布差別大小的測(cè)度是K-L距離或交叉熵[13].

這樣,最優(yōu)測(cè)試剖面的確定問(wèn)題就轉(zhuǎn)化為確定推斷參數(shù)v,使得f(·;v)與概率分布g*的交叉熵最小,即

將式(9)代入式(10)可得如下等價(jià)推斷參數(shù)確定形式:

由于測(cè)試數(shù)據(jù)集x={e1,e2,…}是根據(jù)轉(zhuǎn)移概率矩陣P生成的,概率矩陣P可用推斷參數(shù)v表示.測(cè)試數(shù)據(jù)集x的聯(lián)合概率分布為

由拉格朗日乘子法,則式(11)的優(yōu)化問(wèn)題可轉(zhuǎn)化為

式中,事件I{x∈Xij}表示測(cè)試數(shù)據(jù)集x在測(cè)試中歷經(jīng)狀態(tài)i并從狀態(tài)i轉(zhuǎn)移到狀態(tài)j.

由此可得最優(yōu)測(cè)試剖面中不同狀態(tài)之間的轉(zhuǎn)移概率為

則最優(yōu)測(cè)試剖面T*的每個(gè)轉(zhuǎn)移概率的估計(jì)為

式(14)為不同狀態(tài)之間轉(zhuǎn)移概率的修正公式,其直觀含義為:從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率為所有目標(biāo)函數(shù)值(軟件總費(fèi)用)不大于γ的測(cè)試數(shù)據(jù)集中,從狀態(tài)i一步轉(zhuǎn)移到狀態(tài)j的次數(shù)與測(cè)試歷經(jīng)狀態(tài)i的次數(shù)之比.由此可知,在每一個(gè)狀態(tài)中參數(shù)(不同狀態(tài)下的轉(zhuǎn)移概率)修正都是選用最有利于接近最優(yōu)目標(biāo)的“精英”測(cè)試數(shù)據(jù)集來(lái)修正.這樣修正后使得下一次生成的測(cè)試數(shù)據(jù)集更接近于最優(yōu)測(cè)試數(shù)據(jù)集,該機(jī)制使得每個(gè)狀態(tài)的最優(yōu)轉(zhuǎn)移概率很容易找到,最終得到最優(yōu)測(cè)試剖面,加速統(tǒng)計(jì)測(cè)試.

3.2 應(yīng)用交叉熵方法加速統(tǒng)計(jì)測(cè)試

在基于Markov鏈?zhǔn)褂媚P偷慕y(tǒng)計(jì)測(cè)試中應(yīng)用交叉熵方法,可以由一個(gè)兩步迭代過(guò)程實(shí)現(xiàn):

① 適應(yīng)修正 γt.對(duì)于固定的 vt-1,令 γt為在參數(shù)vt-1下目標(biāo)函數(shù)值序列S(x)的ρ·100%分位數(shù).即 γt滿足

式中,x~f(·;vt-1).最簡(jiǎn)單的估計(jì)是根據(jù)參數(shù)vt-1抽樣出的測(cè)試數(shù)據(jù)集 x1,x2,…,xN計(jì)算出目標(biāo)函數(shù)值S(x),并將其按從小到大排列(S(1)≤S(2)≤…≤S(N)),最后用N個(gè)目標(biāo)函數(shù)值中的第ρ·100%個(gè)來(lái)估計(jì)γt,即^γt=S[ρN].

② 適應(yīng)修正 vt.對(duì)于固定的 γt和 vt-1,由式(14)得到修正的 ~vt,并采用平滑技術(shù)得到vt的修正值[13]:

步驟②中采用平滑技術(shù)主要是為了避免^vt的元素^vt,i取值為0,不能得到全局最優(yōu)解.首次循環(huán)中,初始化轉(zhuǎn)移概率矩陣為操作剖面P.由迭代過(guò)程可得^γ1和^v1,如此循環(huán),可得序列對(duì){(^γt,^vt),t=1,2,…}.由文獻(xiàn)[14]易知^γt→γ*,由此可得用于生成最優(yōu)或近似最優(yōu)測(cè)試數(shù)據(jù)集的測(cè)試剖面,具體算法如下.

算法1 最優(yōu)測(cè)試剖面生成算法

① 初始化^v0為操作剖面P,令t=1.

② 根據(jù)參數(shù)^vt-1及相應(yīng)的測(cè)試充分性判定準(zhǔn)則自動(dòng)生成隨機(jī)測(cè)試數(shù)據(jù)集 x的樣本 x1,x2,…,xN,計(jì)算各個(gè)測(cè)試數(shù)據(jù)集樣本對(duì)應(yīng)的目標(biāo)函數(shù)值S(x)并排序 S(1),S(2),…,S(N),找出 N 個(gè)目標(biāo)函數(shù)值的ρ·100%分位數(shù)^γt=S[ρN].

③ 用同樣的測(cè)試數(shù)據(jù)集樣本 x1,x2,…,xN,由式(14)解出~vt,應(yīng)用式(15)的平滑技術(shù)得到 ^vt.

④令t=t+1,重復(fù)步驟②和③,直到滿足停止條件.

⑤輸出最優(yōu)測(cè)試剖面.

測(cè)試數(shù)據(jù)集x1,x2,…,xN的自動(dòng)生成過(guò)程可根據(jù)Markov過(guò)程性質(zhì)及相應(yīng)測(cè)試充分性判定準(zhǔn)則運(yùn)用蒙特卡羅方法來(lái)仿真生成,具體算法如下.

算法2 測(cè)試數(shù)據(jù)集的自動(dòng)生成算法

輸入:測(cè)試剖面T,各邊失效概率,失效風(fēng)險(xiǎn),測(cè)試成本.

輸出:N個(gè)測(cè)試數(shù)據(jù)集及相應(yīng)的目標(biāo)函數(shù)值S(xi),i=1,2,…,N.

For i=1 to N

初始化當(dāng)前狀態(tài)為初態(tài)1.

重復(fù)如下步驟,直到滿足測(cè)試充分性準(zhǔn)則:

①根據(jù)測(cè)試剖面T,在當(dāng)前狀態(tài)選取下一條邊,若當(dāng)前狀態(tài)為終態(tài),則下一狀態(tài)為初態(tài)1;

②修改相應(yīng)測(cè)試邊的遍歷次數(shù)及當(dāng)前所在狀態(tài);

③計(jì)算目標(biāo)函數(shù)樣本值S(xi).

4 實(shí)例及靈敏度分析

4.1 實(shí)例分析

為了更好地說(shuō)明利用交叉熵方法優(yōu)化測(cè)試剖面的有效性,用一個(gè)列車調(diào)度信息系統(tǒng)軟件[4-6,12-14]實(shí)例加以驗(yàn)證.圖 1 給出了列車調(diào)度的Markov鏈?zhǔn)褂媚P?

圖1 列車信息系統(tǒng)的Markov鏈?zhǔn)褂媚P?/p>

軟件包括12個(gè)操作,每次執(zhí)行從操作1開始,操作12是軟件終止運(yùn)行時(shí)執(zhí)行的操作,邊(8,9)和(8,10)導(dǎo)致關(guān)鍵操作9和10執(zhí)行.假定每條邊(i,j)的失效概率 f(i,j)、失效風(fēng)險(xiǎn) l(i,j)和測(cè)試成本c(i,j)已估計(jì)出,如表1所示.

表1 馬爾可夫使用模型中各邊失效概率、失效風(fēng)險(xiǎn)和測(cè)試成本

失效風(fēng)險(xiǎn)重要程度參數(shù)a=105,每次迭代抽樣的樣本數(shù)N=1 000,ρ=0.02,d=4(或最大迭代步數(shù)為50),平滑參數(shù)α=0.4,采用向前看30步停止準(zhǔn)則生成最優(yōu)測(cè)試剖面T*.分別根據(jù)最優(yōu)測(cè)試T*和操作剖面P生成500個(gè)測(cè)試數(shù)據(jù)集.采用最優(yōu)測(cè)試剖面T*時(shí)平均軟件總費(fèi)用為3 774,平均每個(gè)測(cè)試數(shù)據(jù)集遍歷的邊數(shù)為47;采用操作剖面P時(shí)平均最小軟件總費(fèi)用為8 983,平均每個(gè)測(cè)試用例集遍歷的邊數(shù)為22.兩種情形下的平均失效風(fēng)險(xiǎn)、平均測(cè)試成本及平均軟件總費(fèi)用在測(cè)試邊數(shù)增加時(shí)的變化曲線如圖2和圖3所示.

圖2 采用最優(yōu)測(cè)試剖面時(shí)的費(fèi)用變化趨勢(shì)

圖3 采用操作剖面時(shí)的費(fèi)用變化趨勢(shì)

從圖2和圖3中可看出隨著測(cè)試邊數(shù)的增加,2種情形下平均失效風(fēng)險(xiǎn)都在降低并且下降速度逐漸變小,測(cè)試成本不斷增加,軟件總費(fèi)用由高逐漸降低至最少,平均失效風(fēng)險(xiǎn)的減少量也逐漸變小.當(dāng)平均失效風(fēng)險(xiǎn)減少量低于測(cè)試成本增加量時(shí),軟件總費(fèi)用呈上升趨勢(shì),與前面的分析一致.采用最優(yōu)測(cè)試剖面T*測(cè)試時(shí)平均失效風(fēng)險(xiǎn)下降的幅度要比采用操作剖面P時(shí)的大,平均軟件總費(fèi)用要比采用操作剖面時(shí)小.

圖4和圖5給出了按最優(yōu)測(cè)試剖面和操作剖面分別生成的500個(gè)測(cè)試數(shù)據(jù)集中,各邊累積遍歷次數(shù)的柱狀圖.

圖4 采用最優(yōu)測(cè)試剖面時(shí)各測(cè)試邊的遍歷次數(shù)

圖5 采用操作剖面時(shí)各測(cè)試邊的遍歷次數(shù)

采用操作剖面時(shí),操作8被遍歷的次數(shù)為53,關(guān)鍵操作9和10被遍歷的次數(shù)分別為38和28.而采用最優(yōu)測(cè)試剖面時(shí),操作8被遍歷的次數(shù)為761,關(guān)鍵操作9和10被遍歷的次數(shù)分別為547和1 005.

4.2 靈敏度分析

為了研究算法1中各參數(shù)對(duì)測(cè)試效率的影響,采用向前看30步停止準(zhǔn)則,d=4或最大迭代次數(shù)設(shè)定為50次,研究了在其他參數(shù)不變的情形下,100次仿真實(shí)驗(yàn)中參數(shù)α、迭代次數(shù)N和ρ分別變化時(shí)對(duì)平均軟件總費(fèi)用的影響.

實(shí)驗(yàn)1 參數(shù)α取值對(duì)總費(fèi)用的影響

在參數(shù)ρ=0.01,N=1 000的情形下,α分別取0.3,0.4,…,0.9時(shí),100次仿真試驗(yàn)的平均總費(fèi)用變化曲線如圖6所示.

圖6 不同α取值下平均總費(fèi)用變化曲線

從圖6可看出,在其他參數(shù)保持不變的情形下,參數(shù)α在[0.3,0.9]之間取值時(shí),對(duì)平均總費(fèi)用沒(méi)有顯著的影響.在實(shí)際應(yīng)用過(guò)程中,α值一般根據(jù)問(wèn)題的復(fù)雜程度選取,如果問(wèn)題復(fù)雜,不易收斂,則α值應(yīng)偏大一些;若算法易收斂,則α值應(yīng)偏小一些.

實(shí)驗(yàn)2 參數(shù)ρ取值對(duì)總費(fèi)用的影響

在參數(shù)α=0.4,N=1 000的情形下,ρ分別取0.01,0.02,…,0.1時(shí),100次仿真試驗(yàn)的平均總費(fèi)用變化曲線如圖7所示.

圖7 不同ρ取值下平均總費(fèi)用變化曲線

由圖7可看出,在其他參數(shù)保持不變的情形下,參數(shù)ρ的取值較小時(shí),平均總費(fèi)用也較小,隨著ρ的增加,平均總費(fèi)用逐漸增加.其實(shí)質(zhì)是在測(cè)試數(shù)據(jù)集的選擇過(guò)程中,選擇測(cè)試數(shù)據(jù)集的質(zhì)量直接影響算法的性能.當(dāng)測(cè)試數(shù)據(jù)集愈接近于最優(yōu)測(cè)試數(shù)據(jù)集時(shí),優(yōu)化后的測(cè)試剖面更接近于最優(yōu)測(cè)試剖面,這樣經(jīng)過(guò)多次迭代后得到的測(cè)試剖面就為最優(yōu)(或近優(yōu))測(cè)試剖面.因此,對(duì)于參數(shù)ρ的選取應(yīng)盡可能小,使參加測(cè)試剖面更新的樣本適應(yīng)值更接近于最優(yōu)值.

實(shí)驗(yàn)3 參數(shù)N取值對(duì)總費(fèi)用的影響

在參數(shù)α=0.4,ρ=0.01的情形下,樣本容量N 分別取500,1 000,…,5 000時(shí),100次仿真試驗(yàn)的平均總費(fèi)用變化曲線如圖8所示.

圖8 樣本容量對(duì)平均總費(fèi)用的影響曲線

從圖8可看出,在其他參數(shù)保持不變的情形下,隨著樣本容量N取值增加,平均總費(fèi)用先急劇降低,然后趨于穩(wěn)定.因此,參數(shù)N的選取應(yīng)該在資源允許的前提下使測(cè)試數(shù)據(jù)個(gè)數(shù)最大.即如果能在每一次迭代中提高選擇的測(cè)試數(shù)據(jù)集質(zhì)量,就能達(dá)到提高算法收斂速度的目的.

5 結(jié)語(yǔ)

本文利用交叉熵方法通過(guò)一種修正機(jī)制調(diào)節(jié)操作剖面,增加小概率關(guān)鍵操作的測(cè)試機(jī)會(huì),加速軟件測(cè)試,在提高軟件系統(tǒng)質(zhì)量的同時(shí)降低軟件總費(fèi)用.應(yīng)用軟件加速統(tǒng)計(jì)測(cè)試技術(shù)需要確定某些參數(shù)值,如:邊的失效率、失效風(fēng)險(xiǎn)和測(cè)試成本.實(shí)際使用中一般采用測(cè)試過(guò)程中得到的經(jīng)驗(yàn)數(shù)據(jù)或通過(guò)專家經(jīng)驗(yàn)進(jìn)行估計(jì),參數(shù)估計(jì)的精確性直接影響測(cè)試數(shù)據(jù)的有效性,如何利用測(cè)試過(guò)程中觀察到的數(shù)據(jù)及以往經(jīng)驗(yàn)數(shù)據(jù)對(duì)這些參數(shù)進(jìn)行精確估計(jì)需作進(jìn)一步研究.

References)

[1]陳火旺,王戟,董威.高可信軟件工程技術(shù)[J].電子學(xué)報(bào),2003,31(12):1933-1938.Chen Huowang,Wang Ji,Dong Wei.High confidence software engineering technologies[J].Acta Electronica Sinica,2003,31(12):1933-1938.(in Chinese)

[2]趙亮,王建民,孫家廣.統(tǒng)計(jì)測(cè)試的軟件可靠性保障能力研究[J].軟件學(xué)報(bào),2008,19(6):1379-1385.Zhao Liang,Wang Jianmin,Sun Jiaguang.Study on the assurance ability of statistical test on software reliability[J].Journal of Software,2008,19(6):1379-1385.(in Chinese)

[3] Gutjahr W J.Failure risk estimation via Markov software usage models[C]//Proc 15th International Conference on Computer Safety,Reliability and Security.Vienna,Austria,1997:183-192.

[4] Gutjahr W J.Importance sampling of test cases in Markovian software usage models[J].Probability in the Engineering and Informational Sciences,1997,11:19-36.

[5] Gutjahr W J.Software dependability evaluation based on Markov usage models[J].Performance Evaluation,2000,40(4):199-222.

[6] Doerner K,Laure E.High performance computing in the optimization of software test plans[J].Optimization and Engineering,2002,3:67-87.

[7] Doerner K,Gutjahr W J.Extracting test sequences from a Markov software usage model by ACO[C]//Genetic and Evolutionary Computation Conference.Chicago,IL,USA,2003:2465-2476.

[8] Yan J,Zhou K P,Deng C H,et al.Importance sampling based safety-critical software statistical testing acceleration[C]//2010 International Conference on Computational Intelligence and Software Engineering.Wuhan,China,2010:1-4.

[9]徐云青,徐義峰,李舟軍.基于使用模型的軟件可靠性加速測(cè)試[J].計(jì)算機(jī)應(yīng)用與軟件,2009,26(3):147-148.Xu Yunqing,Xu Yifeng,Li Zhoujun.Software reliability accelerated testing based on usage model[J].Computer Applications and Software,2009,26(3):147-148.(in Chinese)

[10]張德平,聶長(zhǎng)海,徐寶文.軟件可靠性評(píng)估的重要抽樣方法研究[J].軟件學(xué)報(bào),2009,20(10):2859-2866.Zhang Deping,Nie Changhai,Xu Baowen.Importance sampling method of software reliability estimation[J].Journal of Software,2009,20(10):2859-2866.(in Chinese)

[11]吳玉美,阮鐮.軟件可靠性加速測(cè)試的加速機(jī)理研究[J].計(jì)算機(jī)應(yīng)用,2006,26(6):1449-1551.Wu Yumei,Ruan Lian.Research on the acceleration principle of software reliability testing[J].Computer Applications,2006,26(6):1449-1551.(in Chinese)

[12]張德平,聶長(zhǎng)海,徐寶文.測(cè)試資源受約束的安全關(guān)鍵軟件加速測(cè)試方法[J].計(jì)算機(jī)科學(xué),2009,36(5):138-141.Zhang Deping,Nie Changhai,Xu Baowen.Acceleration testing method of safety-critical software with testing resource constraint[J].Computer Science,2009,36(5):138-141.(in Chinese)

[13] Boer D P-T,Kroese D P,Mannor S et al.A tutorial on the cross-entropy method[J].Annals of Operations Research,2005,134:19-67.

[14] Margolin L.On the convergence of the cross-entropy method[J].Annals of Operations Research,2005,134:201-214.

猜你喜歡
總費(fèi)用概率分布測(cè)試數(shù)據(jù)
離散型概率分布的ORB圖像特征點(diǎn)誤匹配剔除算法
“健康中國(guó)2030”背景下京、津、滬、渝四直轄市衛(wèi)生總費(fèi)用的比較研究
測(cè)試數(shù)據(jù)管理系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)
關(guān)于概率分布函數(shù)定義的辨析
科技視界(2016年19期)2017-05-18 10:18:46
基于概率分布的PPP項(xiàng)目風(fēng)險(xiǎn)承擔(dān)支出測(cè)算
基于自適應(yīng)粒子群優(yōu)化算法的測(cè)試數(shù)據(jù)擴(kuò)增方法
空間co-location挖掘模式在學(xué)生體能測(cè)試數(shù)據(jù)中的應(yīng)用
體育科技(2016年2期)2016-02-28 17:06:21
一種相依極小P值統(tǒng)計(jì)量概率分布的近似計(jì)算方法
影響《標(biāo)準(zhǔn)》測(cè)試數(shù)據(jù)真實(shí)性的因素及破解策略
體育師友(2011年5期)2011-03-20 15:29:51
21世紀(jì)我國(guó)衛(wèi)生總費(fèi)用占GDP比例首次低于4%
404 Not Found

404 Not Found


nginx
合肥市| 尖扎县| 潮安县| 长治市| 临汾市| 河北省| 精河县| 修水县| 凤翔县| 泰安市| 白水县| 涡阳县| 兴文县| 稷山县| 青田县| 阳谷县| 大姚县| 屯留县| 双鸭山市| 陆川县| 盈江县| 手机| 鸡泽县| 和硕县| 小金县| 邹城市| 南陵县| 阿鲁科尔沁旗| 神池县| 喀什市| 贺州市| 清水河县| 环江| 施秉县| 靖江市| 米脂县| 凌海市| 西平县| 商南县| 泽州县| 星子县|