雷 航，陳麗敏

(1. 電子科技大學信息與軟件工程學院 成都 610054; 2. 電子科技大學計算機科學與工程學院 成都 610054)

軟件測試是軟件開發(fā)的重要步驟和軟件質(zhì)量保證的重要環(huán)節(jié)。就其目的而言，軟件測試可以分為兩類：1) 通過測試發(fā)現(xiàn)錯誤，并不斷改正錯誤，以期得到高質(zhì)量的軟件；2) 統(tǒng)計學的方法測試軟件的可靠性(reliability)。

基于模型的軟件測試屬統(tǒng)計測試的范疇，要求基于軟件的使用模型產(chǎn)生測試用例對軟件系統(tǒng)進行測試。根據(jù)統(tǒng)計測試結(jié)果，可以估計被測軟件的可靠性[1]，因此軟件統(tǒng)計測試也稱為軟件可靠性測試。

軟件的使用模型以一種形式化的方式表現(xiàn)出來，如有限狀態(tài)機、UML模型和Markov鏈。模型是對軟件使用情況的形式化建模，因此對測試的自動化起著重要作用?；谀Ｐ偷能浖y試，主要是面向測試的自動化。目前，基于模型的軟件測試研究主要集中在軟件測試模型本身的研究，即如何針對不同類型的軟件提取專用模型，又可從專用模型中抽象通用模型。而在測試用例生成方面，由于在以往的測試用例生成中主要采用邊界值、等價類劃分等分析方法，用于手動生成測試用例，而該類分析生成測試用例的方法不利于測試用例的自動生成。本文針對上述問題，在基于模型的測試用例自動生成方法上進行研究。

1 軟件使用模型

1.1 概述

軟件模型是對軟件的行為和結(jié)構(gòu)的一種抽象描述，軟件行為的描述方式有系統(tǒng)輸入序列、活動、條件、輸出邏輯和數(shù)據(jù)流等。軟件結(jié)構(gòu)可以使用組件圖、部署圖進行描述。針對不同的測試任務(wù)，對軟件結(jié)構(gòu)和功能進行抽象，并且用易于理解的方式進行描述，所獲得的模型即是對被測軟件系統(tǒng)精確的建模[2]，可以用于軟件測試。一般根據(jù)軟件的不同行為，采用不同的模型對軟件進行描述，如程序依賴圖、數(shù)據(jù)流圖和控制流圖表達了程序和代碼結(jié)構(gòu)間的行為關(guān)系，決策表和狀態(tài)機則可以描述軟件的外部行為。

基于模型的軟件測試可以根據(jù)軟件行為模型和結(jié)構(gòu)模型生成測試用例。目前的軟件規(guī)模龐大，使基于程序的測試十分困難，而基于模型的軟件測試方法不僅可以有效地提高測試效率[3]及測試用例生成的自動化程度，進行測試失效辨識，也有利于評價測試結(jié)果。

1.2 Markov鏈使用模型

軟件測試中使用的典型模型包括有限狀態(tài)機、UML模型[4]和Markov鏈等模型。

Markov鏈[5]是一種以統(tǒng)計理論為基礎(chǔ)的統(tǒng)計模型，在軟件統(tǒng)計測試中得到了廣泛的應(yīng)用。它是一種遷移具有概率特征的有限狀態(tài)機，可以根據(jù)狀態(tài)間遷移概率自動生成測試用例，還可以分析結(jié)果，對軟件性能指標和可靠性指標等進行度量[6-7]。另外，Markov鏈模型適用于對多種軟件進行統(tǒng)計測試[8]，并可以通過仿真得到狀態(tài)和遷移覆蓋的平均期望時間，有利于在開發(fā)早期對大規(guī)模軟件系統(tǒng)進行測試費用和時間的規(guī)劃。

本文涉及的Markov鏈均為“有限狀態(tài)、離散參數(shù)、時間齊次”。由Markov鏈描述的軟件使用模型可以用隨機遷移矩陣或帶遷移概率的狀態(tài)遷移圖表示。

一個簡單的軟件Markov鏈模型如圖1所示，該模型以遷移帶概率特征的狀態(tài)遷移圖表示。

圖1 Markov使用模型

圖1中的節(jié)點代表使用狀態(tài)(狀態(tài)是指軟件在t時刻的運行狀態(tài))向弧表示狀態(tài)之間的轉(zhuǎn)移，每條弧上都有一個激勵(輸入)與之對應(yīng)，并指定了對應(yīng)的概率，表明在當前的狀態(tài)下輸入激勵，使軟件轉(zhuǎn)移到下一個狀態(tài)，轉(zhuǎn)移概率之和應(yīng)為1。

每一個使用模型都有唯一的初態(tài)和終態(tài)。初態(tài)是每一次模型使用的開始狀態(tài)，終態(tài)是模型使用的終止狀態(tài)，是軟件每一次使用的終結(jié)。軟件的每一次使用即每一次操作都從初態(tài)開始，經(jīng)過若干個中間狀態(tài)，最后到達終態(tài)。

一條從最初的起始狀態(tài)到終止狀態(tài)的路徑(歷經(jīng)的狀態(tài)和弧序列)反映了軟件的一次運行。每一狀態(tài)轉(zhuǎn)移對應(yīng)一次輸入，即一次激勵。由于模型中可能有循環(huán)，會產(chǎn)生無窮序列。輸入序列可以通過遍歷狀態(tài)轉(zhuǎn)移圖得到。利用軟件的Markov鏈使用模型可以獲得大量的輸入序列。一個測試輸入就是根據(jù)Markov鏈使用模型從輸入域中隨機產(chǎn)生的一個有限輸入序列。

2 基于模型的測試用例生成

在基于模型的軟件測試中，測試用例的生成方法取決于所采用的模型。以有限狀態(tài)機模型為例，被遍歷路徑中弧的標記構(gòu)成的序列即是測試用例。在構(gòu)造滿足測試準則的路徑時，必須考慮約束條件，如路徑長度限制，統(tǒng)計測試時還要考慮遷移概率[3]。

在Markov鏈表示的軟件使用模型中，生成測試用例是在每一狀態(tài)處不斷選擇激勵，從而選擇下一個輸出狀態(tài)的過程。常用的激勵選擇方式采用完全隨機方法選擇當前激勵。運用該方法，理論上生成的激勵均勻分布。

假設(shè)已得到某軟件的Markov鏈模型，在常用的隨機方法的基礎(chǔ)上，考慮Markov鏈的狀態(tài)遷移概率，在激勵隨機選擇時加入一定的約束，使激勵選擇更符合軟件的實際使用，使測試用例更有效。該算法將遺傳算法中用于選擇種群的選擇算子——輪盤賭選擇算子用于對激勵進行選擇，根據(jù)使用模型中狀態(tài)間的轉(zhuǎn)移概率選擇激勵，從而得到軟件的下一狀態(tài)。

根據(jù)Markov鏈的測試充分性準則[9]要求，測試過程中測試用例的遷移覆蓋率與Markov鏈使用模型中的遷移概率相同[10]。

輪盤賭選擇算子對激勵進行的隨機性選擇符合軟件實際使用的隨機性，使所選激勵出現(xiàn)的概率與軟件實際使用中該輸入產(chǎn)生的概率一致，本文采用理論方法對此進行了證明。因此，該算法從根本上保證了基于Markov鏈的測試充分性準則要求。

2.1 輪盤賭算法

文獻[11]提出的輪盤賭選擇算子，是遺傳算法中選擇算子的一種。它是基于比例的選擇(proportional model)，利用各個個體適應(yīng)度所占比例的大小決定其子孫保留的可能性。

輪盤賭的整個賭盤被分為大小不同的一些扇面，分別對應(yīng)著價值各不相同的一些賭博物品。當旋轉(zhuǎn)著的賭盤自然停下時，其指針所指扇面上的物品就歸賭博者所有。雖然賭盤的指針具體停在哪個扇面無法預測，但指針指向各個扇面的概率卻是可以估計，它與各個扇面的圓心角大小成正比。圓心角越大，停在該扇面的可能性越大；圓心角越小，停在該扇面的可能性越小。

與此類似，在遺傳算法中，整個種群被各個個體所分割，各個個體的適應(yīng)度在全部個體的適應(yīng)度之和中所占比例也大小不一，該比例值瓜分了整個賭盤盤面(盤面設(shè)為1)，它們也決定了各個個體被遺傳到下一代群體中的概率。

若某個個體為i，其適應(yīng)度為F，種群大小為M，則該選擇算子的具體執(zhí)行過程為：

2.2 測試用例生成算法

步驟1)～步驟3)為對輪盤賭算法改進。

在根據(jù)軟件使用模型生成測試用例時：

2) 產(chǎn)生0～1隨機數(shù)序列，選取一種隨機數(shù)生成方法，如利用計算機產(chǎn)生偽隨機數(shù)序列。

3) 統(tǒng)計隨機數(shù)落在各個子段的頻率，頻率最高的子段對應(yīng)的元素被選中，即與子段對應(yīng)的輸出狀態(tài)被選中。至此，轉(zhuǎn)移的下一個狀態(tài)被選出，即輸出狀態(tài)被選出。

4) 在下一輸出狀態(tài)處繼續(xù)步驟1)～步驟3)，直到終止狀態(tài)停止。

測試用例是從起始狀態(tài)開始到達終止狀態(tài)的狀態(tài)和邊(或激勵)的序列。

不斷從軟件使用模型的初始狀態(tài)開始，執(zhí)行以上測試用例的生成過程，直到覆蓋從起始狀態(tài)到終止狀態(tài)各路徑的測試用例數(shù)目與狀態(tài)轉(zhuǎn)移概率相似時，停止測試用例生成。

2.3 算法有效性分析

根據(jù)伯努利大數(shù)定律：設(shè)X1,X2,…,Xn,…,相互獨立都服從(0-1)分布隨機變量。P{Xi=1}=p，P{Xi=0}=q(00，有：

假設(shè)xi表示激勵，軟件目前狀態(tài)為A，該狀態(tài)的激勵為一隨機變量X，其取值為{x1,x2,x3}3種。激勵的概率為Pk=P{X=xk,k=1,2,3}，以此類推。假設(shè)在N次隨機數(shù)選擇事件中，激勵xk(k=1,2,3)被選中的次數(shù)為ak,ak/N為事件{X=xk}的頻率。按照伯努利大數(shù)定理，當N充分大時，ak/N接近于Pk的概率等于1。因此，由模型得到的頻率ak/N近似等于所求量Pk，說明頻率收斂于概率。按該算法生成隨機數(shù)序列，選中某一激勵。在N次激勵選擇中，當N趨于某一值時，使該激勵被選中的頻率與期望概率近似相等，符合Markov鏈的測試充分性準則要求。

3 實驗分析

3.1 實驗過程

下面通過某軟件的Markov鏈使用模型進行實例研究。

以圖1為例，該Markov鏈使用模型由初始Enter、A、B、C、結(jié)束Exit共5個狀態(tài)組成。

1) Enter狀態(tài)僅有一個激勵a，其概率為1，狀態(tài)Enter輸出狀態(tài)集合為{A}。該激勵映射區(qū)間為[0.00，1.00]。產(chǎn)生的0-1隨機數(shù)序列均落在[0.00，1.00]區(qū)間內(nèi)，因此其輸出狀態(tài)只能為A。此時的軟件輸出狀態(tài)為A。

2) 對應(yīng)A狀態(tài)有b和c兩個不同激勵，其概率均為0.5。A狀態(tài)的輸出狀態(tài)集合為{B,C}，將輸出狀態(tài)映射到[0.00,1.00]區(qū)間，具體為B對應(yīng)區(qū)間為[0.00,0.50]，C對應(yīng)區(qū)間為[0.50,0.10]。

3) 隨機生成10個[0.00,1.00]區(qū)間的隨機數(shù)，分別為0.389 697，0.294 927，0.225 976，0.150 322，0.358 294，0.688 660，0.122 489，0.905 322，0.844 990，0.766 531。

4) 統(tǒng)計得出落在[0.00,0.50]區(qū)間中的隨機數(shù)為60%，落在[0.50,0.10]區(qū)間的隨機數(shù)為40%。

區(qū)間[0.00,0.50]被選中的頻率最高，所以選擇B為輸出狀態(tài)。

5) 在輸出狀態(tài)B上執(zhí)行步驟2)和步驟3)。對應(yīng)B狀態(tài)有b、c和e共3個不同激勵，其概率分別為0.50、0.25、0.25。B狀態(tài)的輸出狀態(tài)集合為{B,C,Exit}；將輸出狀態(tài)映射到[0.00,1.00]區(qū)間，具體為B對應(yīng)區(qū)間為[0.00,0.50]，C對應(yīng)區(qū)間為[0.50,0.75]，Exit對應(yīng)區(qū)間為[0.75,1.00]。

隨機生成10個[0.00,1.00]區(qū)間的隨機數(shù)，分別為0.061 545，0.974 183，0.217 532，0.072 705，0.358 106，0.953 033，0.662 193，0.856 298，0.439 755，0.104 917。落在[0.00,0.50]區(qū)間中的隨機數(shù)為60%，落在[0.50,0.75]區(qū)間的隨機數(shù)為10%，落在[0.75,1.00]區(qū)間的隨機數(shù)為30%。

區(qū)間[0.00,0.50]被選中的頻率最高，所以選擇B為輸出狀態(tài)。

6) 在B狀態(tài)繼續(xù)執(zhí)行步驟2)和步驟3)。隨機生成10個[0.00,1.00]區(qū)間的隨機數(shù)，分別為0.668 492，0.483 965，0.092 351，0.996 575，0.273 176，0.409 635，0.890 488，0.638 671，0.736 871，0.884 251。落在[0.00,0.50]區(qū)間中的隨機數(shù)為40%，落在[0.50,0.75]區(qū)間的隨機數(shù)為30%，落在落在[0.75,1.00]之間的隨機數(shù)為30%。

區(qū)間[0.00,0.50]被選中的頻率最高，所以仍然選擇B為輸出狀態(tài)。

7) 在B狀態(tài)繼續(xù)執(zhí)行步驟2)和步驟3)。隨機生成10個[0.00,1.00]區(qū)間的隨機數(shù)，分別為0.825 414，0.495 734，0.086 770，0.710 631，0.050 235，0.939 459，0.853 754，0.584 155，0.704 494，0.837 837。落在[0.00,0.50]區(qū)間中的隨機數(shù)為30%，落在[0.50,0.75]區(qū)間的隨機數(shù)為30%，落在[0.75,1.00]區(qū)間的隨機數(shù)為40%。

區(qū)間[0.75,1.00]被選中的頻率最高，所以選擇C為輸出狀態(tài)。

8) 在C狀態(tài)執(zhí)行步驟2)和步驟3)，具體步驟略。最后選擇Exit為輸出狀態(tài)。

至此，產(chǎn)生了一個完整的測試用例，如表1所示。

以上方法僅是示例，在實際生成測試用例過程中，可在[0.00,1.00]區(qū)間生成更多數(shù)目的隨機數(shù)，根據(jù)選中區(qū)間選擇激勵，以便更準確地體現(xiàn)轉(zhuǎn)移概率。

表1 測試用例示例

3.2 結(jié)果分析

以圖1中C狀態(tài)為例，E(C)={A,Exit}；P(C)={a,e,f}；F(C,a)=A，F(xiàn)(C,e)=Exit，F(xiàn)(C,f) =Exit；P(a|C)=1/4，P(e|C)=1/2，P(f|C) =1/4。利用完全隨機方法和帶概率約束的隨機方法選擇當前激勵，激勵被選中的頻率如表2所示。

表2 結(jié)果對照

采用完全隨機方法，激勵被選擇的概率比為34/100:34/100:32/100=1:1:0.941 2，采用帶概率約束的隨機算法，激勵被選擇的概率比為22/100:49/100:29/100=1:2.227 3:1.318 2。與P(a|C):P(e|C):P(f|C)=1/4:1/2:1/4=1:2:1相比，后者更接近軟件Markov鏈使用模型中的轉(zhuǎn)移概率比，由此可知，采用帶概率約束的隨機算法生成的測試用例更符合軟件的實際使用。

4 結(jié) 束 語

測試自動化的意義重大，基于模型的測試用例生成為測試自動化打下了基礎(chǔ)。本文通過采用輪盤賭選擇算子，根據(jù)狀態(tài)轉(zhuǎn)移概率對激勵進行選擇，使生成的測試用例符合軟件的實際使用。測試用例具有針對性，對提高軟件可靠性具有重要的意義。

[1] JOHN D M. Software reliability engineering[M]. New York:The McGraw-Hill Companies, Inc. , 1999.

[2] 李軍義. 軟件測試用例自動生成技術(shù)研究[D]. 湖南: 湖南大學, 2007.LI Jun-yi. Research on techniques for software test case automatic generation[D]. Hunan: Hunan University, 2007.

[3] AVRITZER A, WEYUKER E J. The automatic generation of load test suites and the assessment of the resulting software[J]. IEEE Transaction on Software Engineering,1995, 21(9): 705-715.

[4] 顏炯, 王戟, 陳火旺. 基于UML的軟件Markov鏈使用模型構(gòu)造研究[J]. 軟件學報, 2005, 16(8): 1386-1394.YAN Jiong, WANG Ji, CHEN Huo-wang. Deriving software markov chain usage model from uml models[J]. Journal of Software, 2005, 16(8): 1386-1394.

[5] HU Hai, JIANG Chang-hai, CAI Kai-yuan. Adaptive software testing in the context of an improved controlled Markov chain model[J]. IEEE on Computer Software and Applications, 2008, 32: 853-858.

[6] STACY J P, CARMEN J T, RICHARD C L, et al. 凈室軟件工程: 技術(shù)與過程[M]. 賁可榮, 張志祥, 張秀山, 等譯.北京: 電子工業(yè)出版社, 2001.STACY J P, CARMEN J T, RICHARD C L, et al.Cleanroom software engineering: Process and technology[M]. Translated by BI Ke-rong, ZHANG Zhi-xiang, ZHANG Xiu-shan, et al. Beijing: Publishing House of Electronics Industry, 2001.

[7] POORE J H. Introduction to the special issue on:model-based statistical testing of software intensive systems[J]. Information and Software Technology, 2000,42(12): 797-799.

[8] 沙曉婷. 統(tǒng)計方法在軟件測試中的研究與實現(xiàn)[D]. 北京:北京交通大學, 2008.SHA Xiao-ting. Research and implementation on software testing with statistical method[D]. Beijing: Beijing Jiaotong University, 2008.

[9] 高海昌, 馮博琴, 曾明, 等. 基于Markov鏈路徑使用模型的軟件統(tǒng)計測試[J]. 計算機工程, 2006, 32(19): 20-22.GAO Hai-chang, FENG Bo-qin, ZENG Ming, et al.Statistical software test based on Markov chain path usage model[J]. Computer Engineering, 2006, 32(19): 20-22.

[10] 沈海華, 衛(wèi)文麗, 陳云霽. 覆蓋率驅(qū)動的隨機測試生成技術(shù)綜述[J]. 計算機輔助設(shè)計與圖形學學報, 2009,21(4): 419-431, 441.SHEN Hai-hua, WEI Wen-li, CHEN Yun-ji. A survey on coverage directed generation technology[J]. Journal of Computer-aided Design &Computer Graphics, 2009, 21(4):419-431,441.

[11] 王小平, 曹立明. 遺傳算法——理論, 應(yīng)用與軟件實現(xiàn)[M]. 西安: 西安交通大學出版社, 2002.WANG Xiao-ping, CAO Li-ming. Genetic algorithmtheory, application and software implementation[M]. Xi’an:Xi’an Jiaotong Universiy Press, 2002.

[12] 馬春燕, 胡飛, 張云鵬. 基于Markov鏈使用模型的組件復用的統(tǒng)計測試[J]. 計算機應(yīng)用研究, 2008, 25(4): 1051-1053, 1056 MA Chun-yan, HU Fei, ZHANG Yun-peng. Statistical testing of component reuse using Markov chain usage model[J]. Application Research of Computers, 2008, 25(4):1051-1053, 1056