張德平 查日軍

(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)褂媚Ｐ吞岢隽艘环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)褂媚Ｐ?/h2>

Markov鏈?zhǔn)褂媚Ｐ褪且粋€(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)褂媚Ｐ偷慕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)褂媚Ｐ?

圖1 列車信息系統(tǒng)的Markov鏈?zhǔn)褂媚Ｐ?/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.