基于馬爾可夫鏈的RESTful服務(wù)可靠性評(píng)估優(yōu)化

江金蓮，關(guān)婷婷

（上海海事大學(xué)信息工程學(xué)院，上海 201804）

0 引言

軟件測(cè)試作為預(yù)測(cè)軟件質(zhì)量好壞的關(guān)鍵一環(huán)，在整個(gè)軟件生命周期中扮演著重要的角色[1]。軟件測(cè)試是為了發(fā)現(xiàn)軟件錯(cuò)誤和執(zhí)行程序的過程，提高測(cè)試效益，可以更好發(fā)揮軟件測(cè)試的效果。軟件統(tǒng)計(jì)測(cè)試通過對(duì)輸入統(tǒng)計(jì)分布進(jìn)行分析生成測(cè)試用例，可以通過軟件統(tǒng)計(jì)測(cè)試達(dá)到分析軟件質(zhì)量目的，并且提高軟件測(cè)試的安全性和可靠性的性價(jià)比[2]。為了保障軟件測(cè)試的充分性，優(yōu)化軟件測(cè)試方法，加速軟件測(cè)試，對(duì)于高質(zhì)量可靠性軟件，一些關(guān)鍵操作的使用概率較小，在測(cè)試過程中由于測(cè)試充分性不足，會(huì)導(dǎo)致嚴(yán)重的后果。針對(duì)該特性，提高關(guān)鍵性操作的權(quán)重，獲取軟件可靠性的無偏估計(jì)，利用重要抽樣方法選擇適合的抽樣分布，近似精確估計(jì)，從而達(dá)到軟件高可靠性要求[3]。

本文在保證軟件可靠性無偏估計(jì)的情況下，使用馬爾可夫鏈模型描述軟件使用過程，提高對(duì)模擬結(jié)果有重要貢獻(xiàn)的部分的概率，從而提高測(cè)試的充分性。利用啟發(fā)式遺傳算法迭代種群進(jìn)行馬爾可夫鏈矩陣概率優(yōu)化，提高關(guān)鍵操作轉(zhuǎn)移概率，加速軟件統(tǒng)計(jì)測(cè)試效率[4]。本文主要研究工作主要是：在保證軟件可靠性無偏估計(jì)的情況下，依據(jù)重要抽樣方法，選擇合適分布概率，利用遺傳算法適度函數(shù)，選擇個(gè)體，交叉并引入內(nèi)外部變異，最終得到轉(zhuǎn)移矩陣的最優(yōu)解與最小方差，本文最后仿真實(shí)驗(yàn)?zāi)M對(duì)比了模擬退火算法和標(biāo)準(zhǔn)統(tǒng)計(jì)方式，得出在可靠性無偏估計(jì)的情況下，關(guān)鍵操作執(zhí)行次數(shù)的增加，增強(qiáng)了軟件服務(wù)質(zhì)量的效率。

1 RESTful服務(wù)設(shè)計(jì)和實(shí)現(xiàn)

1.1 RESTful服務(wù)背景

RESTful服務(wù)將一切視為資源，資源的表現(xiàn)形式則是RESTful的表現(xiàn)層，客戶端和服務(wù)器之間傳遞的HTTP請(qǐng)求就是資源的表現(xiàn)層[6]。為了模擬用戶瀏覽器的請(qǐng)求行為，通過調(diào)用HTTPClient工具包進(jìn)行模擬瀏覽器發(fā)送post請(qǐng)求，指定URL,調(diào)用setEntity方法設(shè)置請(qǐng)求參數(shù)，execute方法執(zhí)行請(qǐng)求，最后調(diào)用HTTPRe?sponse的getHeaders方法獲取服務(wù)器的響應(yīng)頭信息，getEntity方法獲取服務(wù)器的響應(yīng)內(nèi)容。設(shè)計(jì)apiRe?quest請(qǐng)求類，客戶端通過 get、post、put、delete 等多httpType類型方式操作服務(wù)器,實(shí)現(xiàn)服務(wù)器的狀態(tài)轉(zhuǎn)換,由于狀態(tài)轉(zhuǎn)換是建立在表現(xiàn)層，則為表現(xiàn)層狀態(tài)轉(zhuǎn)換。

1.2 RESTful服務(wù)轉(zhuǎn)移概率矩陣

在RESTful服務(wù)上編寫A、B、C等資源，對(duì)資源內(nèi)部進(jìn)行操作，例如對(duì)資源 A 進(jìn)行 get、post、delete、up?date、put和option操作屬于資源A的內(nèi)部操作；利用RESTful服務(wù)的過濾器，可以統(tǒng)計(jì)到資源A、B、C等在整個(gè)RESTful服務(wù)的使用中資源之間的轉(zhuǎn)移概率矩陣。在資源內(nèi)部的操作仍舊屬于資源A，由此統(tǒng)計(jì)出資源A的失效概率，且資源之間的操作路徑中任一資源的內(nèi)部操作失效，則認(rèn)為此次資源路徑失效，因此本文研究RESTful服務(wù)的可靠性不僅保證了資源本身的可靠，更加從內(nèi)部保證了資源操作的可靠性，保證了雙重可靠。

2 馬爾科夫鏈的軟件可靠性

2.1 馬爾可夫鏈背景

馬爾可夫鏈?zhǔn)菙?shù)學(xué)中具有馬爾可夫性質(zhì)的離散事件隨機(jī)過程。該過程中在給定當(dāng)前知識(shí)或信息情況下，過去對(duì)于預(yù)測(cè)將來是無關(guān)的[5]。P(Xi+1=x|X0,X1,…,Xi)=P(Xi+1=x|Xi)=公式顯示出，i+1的狀態(tài)只與狀態(tài)i有關(guān)。軟件測(cè)試的測(cè)試用例一般基于邏輯覆蓋和基本路徑生成，構(gòu)成一個(gè)完成的測(cè)試試驗(yàn)樣本控件，將測(cè)試用例的生成和發(fā)生概率和馬爾可夫鏈模型聯(lián)系起來。

2.2 馬爾可夫鏈?zhǔn)褂媚Ｐ?/h3>

馬爾可夫鏈軟件測(cè)試使用模型，初始狀態(tài)1表示軟件使用開始和終止?fàn)顟B(tài)n表示軟件使用結(jié)束。通常我們利用強(qiáng)有向圖G=（V,A）表示，其中V表示各個(gè)狀態(tài)V={1,2,…,n}，A表示狀態(tài)之間的邊，轉(zhuǎn)義概率表示從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率，Markov有初始轉(zhuǎn)移概率矩陣[7]。用n×n的矩陣P表示遷移矩陣概率，用 pij表示從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率，用 pij表示，且 pij必須滿足：0

2.3 軟件可靠性估計(jì)

軟件在一次使用過程中發(fā)生失效用函數(shù)Cf(x)表示，Cf(x)=1表示路徑x執(zhí)行過程中操作導(dǎo)致軟件失效，否則Cf(x)=0,因此Cf(X)的算術(shù)平均就是軟件失效概率的無偏估計(jì)，EP（Cf(X)）是失效概率的數(shù)學(xué)期望，用β表示。軟件在一次使用過程中完成規(guī)定功能的概率稱為軟件可靠性定義，本文此處將軟件可靠性表示為D，因此軟件的可靠性為D=1-EP（Cf(X)）。

3 基于重要抽樣統(tǒng)計(jì)測(cè)試設(shè)計(jì)

3.1 重要抽樣方法度量

重要抽樣方法是在保持樣本期望值不變的情況下，改變現(xiàn)有樣本空間的概率分布將方差減小，增加貢獻(xiàn)大的抽樣出現(xiàn)概率，使抽樣點(diǎn)更有效，以達(dá)到減少運(yùn)算時(shí)間，本文利用重要抽樣在保證軟件測(cè)試可靠性的情況下，加速了軟件測(cè)試速度[8]。

假設(shè)關(guān)于隨機(jī)變量X的概率密度函數(shù)為f(x),求軟件失效概率的數(shù)學(xué)期望β，即：

可得重要抽樣分布函數(shù)與隨機(jī)變量X的期望相同，即重要抽樣的失效概率無偏估計(jì)是隨機(jī)變量X的失效概率無偏估計(jì)。R（x）稱為重要抽樣權(quán)函數(shù)，亦可以稱為似然率，R（x）=f(x)/h(x)。其中 h（x）為重要抽樣分布密度函數(shù)。失效概率的無偏估計(jì)：

校驗(yàn)無偏估計(jì)公式為：

可以得出，計(jì)算方差的公式為：

因此，可以得出結(jié)論Var（β）最小的函數(shù)即為最優(yōu)矩陣函數(shù)。在保證失效概率無偏估計(jì)的情況下，方差越小，軟件可靠性越穩(wěn)定，統(tǒng)計(jì)測(cè)試花費(fèi)開銷越小。

3.2 測(cè)試路徑選擇度量

本文研究對(duì)象是針對(duì)RESTful服務(wù)構(gòu)建的馬爾科夫鏈轉(zhuǎn)移概率矩陣，基于上述公式論證可以得出軟件質(zhì)量服務(wù)的可靠性是基于轉(zhuǎn)移概率矩陣的方差必要條件，如何選擇出最優(yōu)矩陣是可靠性評(píng)估的核心問題所在。

在仿真求解最優(yōu)方差矩陣過程中，需要選擇合適的測(cè)試路徑。一條好的測(cè)試路徑不僅能夠找到所有可能的埋點(diǎn)，而且能夠?qū)Φ蛨?zhí)行概率關(guān)鍵操作做到一定的覆蓋。本文依據(jù)當(dāng)前的最優(yōu)轉(zhuǎn)移概率矩陣，基于當(dāng)前的操作狀態(tài)作為起始態(tài)，提出利用隨機(jī)投擲統(tǒng)計(jì)概率方法選擇下一個(gè)操作狀態(tài)，直至最終的操作末態(tài)，一條測(cè)試路徑選擇終止。隨機(jī)投擲統(tǒng)計(jì)概率方法如下：

（1）依據(jù)當(dāng)前轉(zhuǎn)移概率矩陣行各個(gè)操作的執(zhí)行概率，建立坐標(biāo)軸概率分布。

（2）生成隨機(jī)投擲數(shù)random（0,1），記錄散落在坐標(biāo)軸位置屬于相應(yīng)操作點(diǎn)，并記數(shù)累加。

（3）循環(huán)執(zhí)行一定次數(shù)n，統(tǒng)計(jì)得到n次的各個(gè)操作落入的點(diǎn)數(shù)。

（4）統(tǒng)計(jì)各個(gè)操作的落入點(diǎn)數(shù)占比，選擇占比率大于自身轉(zhuǎn)移概率的操作，作為下一個(gè)轉(zhuǎn)移操作狀態(tài)。

（5）重復(fù)遞歸選擇，直至選擇操作狀態(tài)為末態(tài)操作。

4 重要抽樣遺傳算法的設(shè)計(jì)實(shí)現(xiàn)

遺傳算法思想源于適者生存的自然界動(dòng)物生存規(guī)律和生物遺傳學(xué)，遺傳算法通過模擬達(dá)爾文生物進(jìn)化論中遺傳算子的組合交叉和變異產(chǎn)生出新的種群解集，通過基因進(jìn)化過程，搜索最優(yōu)解[9]。通過重要抽樣法的分析可知，在保障可靠性的情況下，得到統(tǒng)計(jì)測(cè)試加速的關(guān)鍵在于求得失效概率方差最小的矩陣，可以減少工作量和保證測(cè)試的充分性。本文通過比較個(gè)體方差得到最優(yōu)解，將遺傳算法和重要抽樣結(jié)合，利用遺傳算法搜索最優(yōu)解，算法描述如下：

輸入?yún)?shù)：使用Markov的概率遷移矩陣，關(guān)鍵操縱的集合S，事先確定的每個(gè)操作的失效概率；

輸出參數(shù)：優(yōu)化隨機(jī)矩陣Q。

重要抽樣和仿真過程：

（1）在遺傳算法每次產(chǎn)生變異體之后進(jìn)行隨機(jī)生成N條測(cè)試路徑；

（2）初始化路徑Xi，遍歷Xi中每一個(gè)操作，若ran?dom（0,1）小于對(duì)應(yīng)操作失效概率，則路徑Xi的失效概率函數(shù)Cf(Xi)=1；

（3）失效概率方差計(jì)算公式：

遺傳算法與重要抽樣結(jié)合算法過程：

（1）隨機(jī)生成M個(gè)個(gè)初始種群即M個(gè)矩陣，以及矩陣Q為n×n的0矩陣，其中關(guān)鍵操作的概率不得小于初始矩陣P中的概率，M個(gè)個(gè)體生成的矩陣必須與pij=0和 pij=1保持一致且必須滿足markov軟件模型

（2）根據(jù)場景這里確定適度函數(shù)為矩陣失效概率方差，初始值為設(shè)置為無窮大，記為varmin=9999（表示無窮大），優(yōu)化矩陣初始化Q=P；

（3）根據(jù)輪盤賭選擇方法，先計(jì)算出個(gè)體個(gè)體在總體個(gè)體適應(yīng)度中的概率，然后計(jì)算出個(gè)體的累計(jì)概率，random（）隨機(jī)生成一個(gè)[0,1]之間的數(shù)，該數(shù)在哪個(gè)個(gè)體的累計(jì)概率中，則選擇哪個(gè)個(gè)體，因此選取兩個(gè)矩陣最為交叉?zhèn)€體；

（4）交叉選擇的兩個(gè)矩陣，因?yàn)榫仃囀嵌嘈卸嗔?，此處選擇k-opt交換方法，根據(jù)k-opt方法直接將兩個(gè)矩陣A和B內(nèi)部的幾行進(jìn)行交換，本文利用矩陣長度：index 1=random.randint（0,len（A））,index2=random.rand?int（0,len（A））得到A需要與B交換的幾行，將A的[in?dex1:index2]與B[index1:index2]的進(jìn)行互換；

（6）利用重要抽樣將變異之后的矩陣進(jìn)行重要抽樣，隨機(jī)抽樣出N條測(cè)試路徑，并且進(jìn)行路徑失效仿真，得軟件失效概率方差，若小于varmin，則將新值替換varmin，并且將其賦值給Q；

（7）若是孕育發(fā)生新的個(gè)體數(shù)達(dá)到M個(gè)，則將產(chǎn)生新一輪的群體替代老群體；

（8）當(dāng)新群體代數(shù)達(dá)到T終止循環(huán)，得到失效概率最小矩陣Q，輸出。

圖1 遺傳算法流程圖

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

5.1 RESTful服務(wù)實(shí)例

基于遺傳算法的軟件可靠性重要抽樣，利用本文已經(jīng)實(shí)現(xiàn)的軟件說明。RESTful服務(wù)總共包含8個(gè)資源，初始狀態(tài)為1，終止?fàn)顟B(tài)為8,（3,4）,（4,6）和（6,7）導(dǎo)致關(guān)鍵操作為4,6,7。各個(gè)資源失效概率（0,0.001,0.001,0.001,0.001,0.0001,0.001,0.001,0.0001）。依據(jù)服務(wù)歷史統(tǒng)計(jì)數(shù)據(jù)分析，構(gòu)建初始Markov轉(zhuǎn)移概率矩陣如下：

[0,1,0,0,0,0,0,0],

[0,0,0.85,0,0,0,0,0.15],

[0,0.09,0,0.03,0,0.1,0,0.78],

[0,0,0.29,0,0.37,0.03,0.15,0.16],

[0,0,0,1,0,0,0,0],

[0,0,0.6,0,0.18,0.19,0.03,0],

[0,0,0,0,1,0,0,0],

[0,0,0,0,0,0,0,1]]

5.2 仿真結(jié)果對(duì)比

本文根據(jù)模擬退火算法和遺傳算法以及標(biāo)準(zhǔn)統(tǒng)計(jì)測(cè)試分別抽樣1000條測(cè)試路徑仿真100次，得到軟件操作執(zhí)行次數(shù)測(cè)試實(shí)驗(yàn)結(jié)果如表1所示：

表1 仿真關(guān)鍵操作執(zhí)行次數(shù)對(duì)比

從上述100次仿真結(jié)果可以看出，基于標(biāo)準(zhǔn)統(tǒng)計(jì)測(cè)試，模擬退火算法和遺傳算法都能很好地使關(guān)鍵操作4,6,7得到充分測(cè)試，遺傳算法較大地提高了關(guān)鍵操作的執(zhí)行次數(shù)，增大了關(guān)鍵操作的執(zhí)行概率。根據(jù)模擬退火算法和遺傳算法以及標(biāo)準(zhǔn)統(tǒng)計(jì)測(cè)試分別抽樣1000條測(cè)試路徑仿真100次，得到方差實(shí)驗(yàn)結(jié)果如表2所示：

表2 平均方差對(duì)比

從上述100次仿真結(jié)果可以看出，基于標(biāo)準(zhǔn)統(tǒng)計(jì)測(cè)試，優(yōu)化矩陣的方差為3.5×10-2；基于模擬退火算法優(yōu)化矩陣的方差為2.43×10-3；基于遺傳算法優(yōu)化矩陣的方差為1.44×10-5；顯然，遺傳算法比模擬退火算法能更好地降低估計(jì)方差。

在100次仿真中，每次仿真遍歷路徑1000條，每次仿真得到100個(gè)最優(yōu)矩陣和最優(yōu)方差，遺傳算法與模擬退火算法相比，執(zhí)行次數(shù)更加充分；針對(duì)方差方面，模擬退火相比基本統(tǒng)計(jì)測(cè)試失效概率方差更小，統(tǒng)計(jì)測(cè)試開銷花費(fèi)較少。因此，遺傳算法不僅保障了軟件測(cè)試可靠性，且相比于模擬退火使得關(guān)鍵操作的測(cè)試更加充分，使得加速統(tǒng)計(jì)測(cè)試得到更好體現(xiàn)。

6 結(jié)語

本文通過將遺傳算法和重要抽樣結(jié)合，得到一種新的軟件統(tǒng)計(jì)測(cè)試的加速方法，在保障RESTful服務(wù)的軟件測(cè)試可靠性的前提下，提高了關(guān)鍵操作的概率，保證了測(cè)試充分性?；赗ESTful服務(wù)資源的可靠性，且與已有的模擬退火算法作比較，與模擬退火算法相比，本文提出的遺傳算法具有更優(yōu)性。但是遺傳算法求失效概率方差最小的矩陣Q時(shí)，需要記錄仿真中間輸出結(jié)果需要花費(fèi)一定的性能損耗代價(jià)，并且無法得到最優(yōu)解，只能在有限的仿真次數(shù)范圍內(nèi)盡可能得到可靠性無偏估計(jì)的近似最優(yōu)解。但是也發(fā)揮了重要抽樣的優(yōu)點(diǎn)，降低了方差，使得關(guān)鍵步驟操作概率增加提高測(cè)試效率和速度，加速了軟件測(cè)試，并且通過仿真實(shí)驗(yàn)結(jié)果證明了此方法的有效性。