江金蓮，關婷婷

（上海海事大學信息工程學院，上海 201804）

0 引言

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

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

1 RESTful服務設計和實現(xiàn)

1.1 RESTful服務背景

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

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

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

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

2.1 馬爾可夫鏈背景

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

2.2 馬爾可夫鏈使用模型

馬爾可夫鏈軟件測試使用模型，初始狀態(tài)1表示軟件使用開始和終止狀態(tài)n表示軟件使用結(jié)束。通常我們利用強有向圖G=（V,A）表示，其中V表示各個狀態(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 軟件可靠性估計

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

3 基于重要抽樣統(tǒng)計測試設計

3.1 重要抽樣方法度量

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

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

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

校驗無偏估計公式為：

可以得出，計算方差的公式為：

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

3.2 測試路徑選擇度量

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

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

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

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

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

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

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

4 重要抽樣遺傳算法的設計實現(xiàn)

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

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

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

重要抽樣和仿真過程：

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

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

（3）失效概率方差計算公式：

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

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

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

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

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

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

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

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

圖1 遺傳算法流程圖

5 實驗結(jié)果與分析

5.1 RESTful服務實例

基于遺傳算法的軟件可靠性重要抽樣，利用本文已經(jīng)實現(xiàn)的軟件說明。RESTful服務總共包含8個資源，初始狀態(tài)為1，終止狀態(tài)為8,（3,4）,（4,6）和（6,7）導致關鍵操作為4,6,7。各個資源失效概率（0,0.001,0.001,0.001,0.001,0.0001,0.001,0.001,0.0001）。依據(jù)服務歷史統(tǒng)計數(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é)果對比

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

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

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

表2 平均方差對比

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

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

6 結(jié)語

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