馮俊池，于 磊，劉 洋

（1.信息工程大學(xué)，河南 鄭州450001；2.數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州450001）

0 引 言

基于使用模型的可靠性測(cè)試［1－4］采用使用模型來代表系統(tǒng)可能的運(yùn)行情況和所發(fā)生的概率，使測(cè)試接近軟件的真實(shí)使用。在凈室軟件工程［5］中，采用Markov鏈描述軟件使用模型，其主要根據(jù)軟件的相關(guān)技術(shù)文檔生成，通過提取軟件運(yùn)行中的激勵(lì)、響應(yīng)以及之間的交互關(guān)系來確定使用模型的狀態(tài)與遷移，遷移概率可通過對(duì)早期版本使用情況進(jìn)行分析等方式得到［6］。近年來，UML模型在面向?qū)ο筌浖O(shè)計(jì)中得到廣泛應(yīng)用，也逐漸被應(yīng)用到使用模型生成技術(shù)中［7－9］?，F(xiàn)有方法將軟件中每個(gè)消息的發(fā)生視為狀態(tài)的改變，以此生成Markov鏈?zhǔn)褂媚Ｐ停捎趯⒚總€(gè)消息進(jìn)入的狀態(tài)作為使用模型中的一個(gè)狀態(tài)，生成的使用模型中存在部分冗余的狀態(tài)和遷移。吳彩華等將場(chǎng)景的發(fā)生視為軟件狀態(tài)的改變，場(chǎng)景的執(zhí)行概率作為遷移概率，生成場(chǎng)景級(jí)的使用模型［8］，該方法生成的使用模型狀態(tài)空間較小，但狀態(tài)粒度較粗，無法反映用例內(nèi)部的消息交互，用例執(zhí)行過程中的相關(guān)輸入的依賴關(guān)系被忽略，有時(shí)不能真實(shí)體現(xiàn)軟件的實(shí)際使用情況；李秀華為每條消息增加約束條件，通過觀察消息發(fā)生前后的系統(tǒng)關(guān)鍵向量是否變化來消除使用模型中的冗余狀態(tài)和遷移［9］，但該做法增加了人員的工作量，且依賴于領(lǐng)域知識(shí)，適應(yīng)性不強(qiáng)。

本文將代表了用例執(zhí)行情況的順序圖［10］作為用例的不同場(chǎng)景，對(duì)UML 模型加以擴(kuò)展，加入各場(chǎng)景的執(zhí)行概率pf 和后置條件post 以及用例執(zhí)行順序關(guān)系，通過分析UML模型中軟件與外部環(huán)境的消息交互來確定使用模型中的狀態(tài)，生成比較精確的Markov鏈?zhǔn)褂媚Ｐ汀Ｍ瑫r(shí)為了避免狀態(tài)空間爆炸問題，提出了冗余狀態(tài)與等價(jià)狀態(tài)的概念，設(shè)計(jì)了使用模型化簡(jiǎn)算法，并給出了相關(guān)證明。

1 軟件使用模型

定義1 軟件Markov鏈?zhǔn)褂媚Ｐ投x為一個(gè)五元組（S，T，δ，q0，F(xiàn)），S 是軟件使用模型的狀態(tài)集合，每個(gè)狀態(tài)s∈S 是一個(gè)三元組 （Sn，Type，Notation），其中Sn是狀態(tài)編號(hào)，Type表示狀態(tài)是否是初始狀態(tài)或終止?fàn)顟B(tài)，終止?fàn)顟B(tài)的Notation為后置條件，在使用模型生成過程中用于識(shí)別相同的終止?fàn)顟B(tài)，其余狀態(tài)該值為空；T 是狀態(tài)之間的遷移的集合，每個(gè)遷移t∈T 是一個(gè)二元組 （Trans，pf），其中Trans是以發(fā)生時(shí)間先后為全序關(guān)系的激勵(lì)響應(yīng)對(duì)（sim，res）的有序集合，當(dāng)其為空時(shí)代表不同場(chǎng)景或不同用例的模型之間的轉(zhuǎn)換，激勵(lì)sim 與響應(yīng)res 來自消息集合；δ是狀態(tài)之間的遷移關(guān)系S×T→S；q0是使用模型的初始狀態(tài)，q0∈S；F 是使用模型的終止?fàn)顟B(tài)集合，F(xiàn)S。

定義2 如果使用模型中的狀態(tài)s有且僅有一條入遷移t′和出遷移t″，t′的源狀態(tài)和t″的目的狀態(tài)之間沒有直接遷移，則狀態(tài)s為冗余狀態(tài)。

對(duì)于圖1 （a）所示的使用模型，軟件由狀態(tài)Si經(jīng)過遷移tm到達(dá)狀態(tài)Sj，又經(jīng)過遷移tn到達(dá)狀態(tài)Sk，狀態(tài)Si和Sk之間沒有直接遷移，狀態(tài)Sj為冗余狀態(tài)?？梢酝ㄟ^將Sj與Sk合并來減少狀態(tài)冗余。合并時(shí)，刪除狀態(tài)Sj，創(chuàng)建遷移tk連接Si和Sk，tk.Trans＝tm.Trans ∪tn.Trans，tk.pf ＝tm.pf×tn.pf，化簡(jiǎn)后如圖1 （b）所示。

圖1 冗余狀態(tài)

在軟件可靠性測(cè)試中，使用模型主要用來生成模擬真實(shí)使用情況的測(cè)試序列，根據(jù)測(cè)試序列執(zhí)行測(cè)試。軟件的測(cè)試序列對(duì)應(yīng)于使用模型從初始狀態(tài)到結(jié)束狀態(tài)的一條遷移遍歷路徑t＝ （t1，t2，…，tL），t的執(zhí)行概率為

式中：pti——路徑t中第i個(gè)遷移的概率，L——路徑中遷移數(shù)量。

針對(duì)圖1中使用模型的冗余狀態(tài)Sj，將其與Sk合并化簡(jiǎn)并不影響軟件可靠性測(cè)試，下面給出證明：

軟件可靠性測(cè)試與測(cè)試序列t的執(zhí)行路徑及執(zhí)行概率p（t）相關(guān)，將冗余狀態(tài)Sj化簡(jiǎn)后，路徑t＝ （t1，…，tm，tn，…，tL）變?yōu)閠＝ （t1，…，tk，…，tL），其中遷移tk對(duì)應(yīng)執(zhí)行路徑等同于tm和tn的執(zhí)行路徑，軟件執(zhí)行路徑并未改變。

原模型中ptm與化簡(jiǎn)后的模型中ptk相同，由于原模型中狀態(tài)Sj只有一條出邊，ptn＝1，由式 （1）可知路徑執(zhí)行概率p（t）未改變。因此冗余狀態(tài)的化簡(jiǎn)對(duì)軟件可靠性測(cè)試無影響。

定義3 如果使用模型的兩個(gè)狀態(tài)Si和Sj具有相同的遷移且遷移指向的下一狀態(tài)相同，Si和Sj的源狀態(tài)不同，則狀態(tài)Si和Sj為等價(jià)狀態(tài)。

對(duì)于圖2 （a）所示的使用模型，狀態(tài)Si和Sj具有相同的遷移tk指向Sk，Si和Sj的源狀態(tài)不同，Si和Sj為等價(jià)狀態(tài)?？蓪i和Sj合并為狀態(tài)Sij，其出遷移tk指向Sk，原Si和Sj的入遷移指向Sij。

圖2 等價(jià)狀態(tài)

以圖2所示模型為例，下面針對(duì)等價(jià)狀態(tài)的合并不影響軟件可靠性測(cè)試給出證明：

對(duì)經(jīng)過狀態(tài)Si的路徑t＝ （t1，…，tm，tk，…，tL），合并等價(jià)狀態(tài)后，由于原遷移tk相同，所以測(cè)試序列執(zhí)行路徑并未改變，執(zhí)行概率p（t）未變化，經(jīng)過狀態(tài)Sj的路徑也是如此。因此，等價(jià)狀態(tài)的合并對(duì)軟件可靠性測(cè)試無影響。

2 軟件使用模型生成與化簡(jiǎn)

根據(jù)擴(kuò)展UML模型生成軟件Markov鏈?zhǔn)褂媚Ｐ?，首先生成用例的使用模型，然后集成所有用例的使用模型得到軟件的使用模型，最后?duì)使用模型進(jìn)行狀態(tài)簡(jiǎn)化。

2.1 生成用例的使用模型

首先生成每個(gè)場(chǎng)景的使用模型，當(dāng)軟件接收外部激勵(lì)消息并做出響應(yīng)時(shí)，認(rèn)為其狀態(tài)發(fā)生了改變，因此將外部激勵(lì)與軟件響應(yīng)作為狀態(tài)間遷移，每個(gè)遷移對(duì)應(yīng)著一個(gè)新狀態(tài)，逐步建立使用模型。由于存在軟件先后接收多條激勵(lì)消息或發(fā)出多條響應(yīng)消息的情況，為便于處理，將第二條及之后的每條激勵(lì)或響應(yīng)單獨(dú)作為激勵(lì)響應(yīng)對(duì)，其中對(duì)應(yīng)的響應(yīng)或激勵(lì)設(shè)為null。算法流程如圖3 所示，場(chǎng)景執(zhí)行概率為pf，執(zhí)行后置條件為post，消息數(shù)量為L(zhǎng)，這里只考慮軟件與外部交互的消息。

然后通過集成場(chǎng)景的使用模型來構(gòu)造用例的使用模型，算法如下：

步驟1 令c為第一個(gè)場(chǎng)景的使用模型，在c上集成其它場(chǎng)景的使用模型，對(duì)其它所有場(chǎng)景的使用模型ci做如下處理：

（1）令當(dāng)前狀態(tài)cs指向c 的s0，對(duì)ci的所有遷移t 進(jìn)行如下處理：

圖3 場(chǎng)景使用模型生成流程

1）如果cs的遷移t′與t的Trans 不同，新建狀態(tài)s，δ（cs，t）＝s，cs指向s；

2）如果t′與t的Trans相同，令t′的遷移概率pf′疊加上t的遷移概率pf，cs指向t′的目的狀態(tài)。判斷是否滿足如下情況：如果t是最后一條遷移，則插入新狀態(tài)s，令遷移t″＝ （，pf），δ（cs，t″）＝s，將cs指向s；如果cs是終止?fàn)顟B(tài)，則插入新狀態(tài)s，將cs的Type 和Notation 值賦給s，令t″＝ （，pf′－pf），δ（cs，t″）＝s；

（2）將ci的終止?fàn)顟B(tài)的Type 和Notation 值賦給cs，如果存在和cs的Type 和Notation 值相同的狀態(tài)s，cs的入遷移為t，前一狀態(tài)為s′，令δ（s′，t）＝s，將cs刪除，繼續(xù)集成下一場(chǎng)景；

步驟2 所有場(chǎng)景集成后，對(duì)各個(gè)狀態(tài)出遷移的概率進(jìn)行歸一化，令其概率之和為1。

2.2 集成各用例的使用模型

根據(jù)用例執(zhí)行順序關(guān)系集成各用例的使用模型，用例執(zhí)行順序關(guān)系即一個(gè)用例執(zhí)行完成后進(jìn)入某狀態(tài)并執(zhí)行另一用例的概率，定義為UcSeq＝ （Uci，post，Ucj，pf），代表用例Uci執(zhí)行完成的后置條件為post 時(shí)，下一個(gè)執(zhí)行的用例是Ucj的概率是pf。

步驟1 遍歷用例執(zhí)行順序關(guān)系UcSeq：

對(duì)Uci中狀態(tài)的Notation 值為post的終止?fàn)顟B(tài)s1，Ucj的初始狀態(tài)s2，令遷移t＝ （，pf），δ（s1，t）＝s2；

步驟2 確定軟件使用模型的初始狀態(tài)q0，將結(jié)束狀態(tài)加入集合F。

2.3 使用模型化簡(jiǎn)

將軟件使用模型的狀態(tài)化簡(jiǎn)，由于合并等價(jià)狀態(tài)之后會(huì)出現(xiàn)新的冗余狀態(tài)，因此在合并等價(jià)狀態(tài)之后消除冗余狀態(tài)，算法如下：

步驟1 合并等價(jià)狀態(tài)，對(duì)所有狀態(tài)s：

（1）若s 存在多個(gè)入遷移，記s 的上一狀態(tài)集合為Spre，判斷是否存在集合S′preSpre，S′pre中狀態(tài)數(shù)量至少兩個(gè)并且滿足：狀態(tài)的出遷移相同；狀態(tài)的上一狀態(tài)不同；

（2）若存在集合S′pre，將S′pre中狀態(tài)合并為新狀態(tài)。標(biāo)記s已遍歷，轉(zhuǎn)到新狀態(tài)；

（3）否則，標(biāo)記s已遍歷，轉(zhuǎn)到下一狀態(tài)。

步驟2 消除冗余狀態(tài)，對(duì)所有狀態(tài)s：

（1）判斷s是否為冗余狀態(tài)；

（2）若s為冗余狀態(tài)，將s刪除，并修改相關(guān)遷移，轉(zhuǎn)到下一狀態(tài)；

（3）若s 不是冗余狀態(tài)，標(biāo)記s 已遍歷，轉(zhuǎn)到下一狀態(tài)。

3 使用模型生成實(shí)例

模 擬 電 話 交 換 系 統(tǒng) （telephone switching simulation system，TSSS）由交換機(jī) （Switch）、主叫方 （PhoneA）和被叫方 （PhoneB）組成，用例包含有摘機(jī)、撥號(hào)、應(yīng)答、主叫掛機(jī)、主叫遇忙掛機(jī)和被叫掛機(jī)。

部分用例執(zhí)行順序關(guān)系為： （撥號(hào)，待接通，應(yīng)答，1），（應(yīng)答，通話，主叫掛機(jī)，0.5）， （應(yīng)答，通話，被叫掛機(jī)，0.5）。

圖4、圖5分別是撥號(hào)及應(yīng)答兩個(gè)用例的順序圖。表1是部分用例的順序圖的執(zhí)行后置條件和概率。系統(tǒng)中消息所對(duì)應(yīng)的含義為：OFK：摘機(jī)；RDT：發(fā)撥號(hào)音；DIA：撥號(hào)；SDT：停撥號(hào)音；RET：發(fā)錯(cuò)誤音；RFR：查詢空閑；FRE：返回空閑；BUY：返回忙；RBT：發(fā)忙音；RCT：發(fā)振鈴音；RKT：發(fā)回鈴音；NRE：無應(yīng)答；SCT：停振鈴音；SKT：停回鈴音；ONK：掛機(jī)；SET：停錯(cuò)誤音；SBT：停忙音。

圖4 撥號(hào)用例的順序

圖5 應(yīng)答用例的順序

對(duì)TSSS系統(tǒng)構(gòu)造使用模型，狀態(tài)化簡(jiǎn)前如圖6所示，其中以虛線表示的狀態(tài)屬于冗余狀態(tài)，狀態(tài)S18和S19互為等價(jià)狀態(tài)。最終生成的模型如圖7所示，其中遷移為：

在可靠性測(cè)試數(shù)據(jù)生成中，根據(jù)遷移發(fā)生概率所占的比例大小選擇當(dāng)前狀態(tài)發(fā)生的遷移，得到由初始狀態(tài)到終止?fàn)顟B(tài)的一條遷移路徑，將其中的null去掉后的激勵(lì)響應(yīng)序列即為一條測(cè)試數(shù)據(jù)。對(duì)TSSS軟件，遷移序列t1→t3→t5→t7→t10→t12對(duì)應(yīng)的測(cè)試數(shù)據(jù)為： （OFK，RDT，DIA，RFR，F(xiàn)RE，RCT，RKT，OFK，SCT，SKT，ONK，RBT，ONK，SBT），表示了雙方通話結(jié)束后主叫掛機(jī)的一種情況。

表1 部分用例順序圖執(zhí)行后置條件和概率

圖6 化簡(jiǎn)前的TSSS軟件使用模型

圖7 TSSS軟件使用模型

4 實(shí)驗(yàn)及數(shù)據(jù)分析

為了驗(yàn)證使用模型化簡(jiǎn)算法的有效性，采用仿真方法得到若干使用模型進(jìn)行化簡(jiǎn)前后的對(duì)比實(shí)驗(yàn)。

將每個(gè)狀態(tài)的遷移限定為1～3條，隨機(jī)生成狀態(tài)數(shù)在300到500之間的使用模型，并對(duì)其進(jìn)行化簡(jiǎn)?；?jiǎn)前后的使用模型狀態(tài)數(shù)量對(duì)比如圖8所示。

圖8 使用模型狀態(tài)數(shù)量

針對(duì)圖8中的使用模型進(jìn)行實(shí)驗(yàn)，統(tǒng)計(jì)生成10000 條測(cè)試數(shù)據(jù)所用時(shí)間，對(duì)比情況如圖9所示。

圖9 測(cè)試數(shù)據(jù)生成時(shí)間

由化簡(jiǎn)前后的使用模型狀態(tài)數(shù)及測(cè)試數(shù)據(jù)生成時(shí)間對(duì)比可以看出，化簡(jiǎn)后的使用模型中狀態(tài)數(shù)量比化簡(jiǎn)前大量減少，降低了使用模型的復(fù)雜度，在一定程度上解決了狀態(tài)空間爆炸問題；生成相同數(shù)量的測(cè)試數(shù)據(jù)所需時(shí)間只占化簡(jiǎn)前所需時(shí)間的30%到50%，節(jié)省了大量測(cè)試數(shù)據(jù)生成時(shí)間。

5 結(jié)束語

本文改進(jìn)了基于擴(kuò)展UML模型的軟件Markov鏈?zhǔn)褂媚Ｐ蜕煞椒?，并提出了一種使用模型化簡(jiǎn)方法。通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性，采用該方法生成的使用模型在一定程度上解決了狀態(tài)空間爆炸問題，有利于測(cè)試數(shù)據(jù)的自動(dòng)生成與軟件的可靠性測(cè)試效率的提高。

該方法中場(chǎng)景執(zhí)行概率需要人為給出，因此如何更好地估計(jì)軟件場(chǎng)景執(zhí)行概率需要進(jìn)一步的研究。

［1］Gayen Tirthankar，Misra R B.Operational profile based relia－bility assessment of COTS software［J］.International Journal of Computer Applications，2010，4 （1）：14－18.

［2］Li Qiuying，Li Xiang，Wang Jian，et al.Study on the accelerated software reliability demonstration testing for high reliability software based on strengthened operational profile ［C］／／Proceedings of the 2nd International Conference on Computer Technology and Development.Cairo：IEEE Computer Society Press，2010：655－662.

［3］Bohr Frank.Model based statistical testing of embedded systems［C］／／Proceedings of the fourth International Conference on Software Testing，Verification and Validation Workshops.Berlin：IEEE Computer Society Press，2011：18－25.

［4］CHEN Zhenhua，WANG Feng.Software reliability test and evaluation based on Markov chain usage model［J］.Computer Engineering and Design，2007，28 （12）：2768－2771 （in Chinese）.［陳振華，王峰.基于Markov鏈?zhǔn)褂媚Ｐ偷能浖煽啃詼y(cè)評(píng)方法研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28 （12）：2768－2771.］

［5］Sastry J K R，Chandra P V.A formal framework for verification and validation of external behavioral models of embedded systems represented through black box structures ［C］／／Proceedings of the 2nd International Advance Computing Conference.Patiala：IEEE Computer Society Press，2010：430－435.

［6］Feliachi Abderrahmane，Le Guen Hélène.Generating transition probabilities for automatic model－based test generation［C］／／Proceedings of the third International Conference on Software Testing，Verification and Validation，2010：99－102.

［7］WANG Xin，QIN Zheng，HAN Fengyan.UML based hybrid model for generation of software reliability test cases［J］.Journal of Xi’an Jiaotong University，2007，41 （4）：421－425 （in Chinese）.［王昕，覃征，韓峰巖.基于UML的軟件可靠性測(cè)試用例生成的混合模型 ［J］.西安交通大學(xué)學(xué)報(bào)，2007，41（4）：421－425.］

［8］WU Caihua，LIU Juntao，PENG Shirui，et al.Deriving Markov chain usage model from UML model［J］.Journal of Computer Research and Development，2012，49 （8）：1811－1819 （in Chinese）. ［吳彩華，劉俊濤，彭世蕤，等.基于UML的軟件Markov鏈?zhǔn)褂媚Ｐ偷臉?gòu)建 ［J］.計(jì)算機(jī)研究與發(fā)展，2012，49 （8）：1811－1819.］

［9］LI Xiuhua.Research and implementation of software reliability testing technology based on UML model［D］.Chengdu：University of Electronic Science and Technology of China，2007：47－51 （in Chinese）.［李秀華.基于UML模型的軟件可靠性測(cè)試技術(shù)的研究與實(shí)現(xiàn)［D］.成都：電子科技大學(xué)，2007：47－51.］

［10］HUANG Long，YANG Yuhang，LI Hu.Formalization description of message in UML sequence diagram and corresponding feature analysis［J］.Computer Engineering and Design，2010，31 （15）：3427－3431 （in Chinese）. ［黃隴，楊宇航，李虎.UML 順序圖中消息的形式化描述與相關(guān)特性分析［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31 （15）：3427－3431.］