軟件Markov鏈使用模型生成與化簡技術

馮俊池，于 磊，劉 洋

（1.信息工程大學，河南 鄭州450001；2.數學工程與先進計算國家重點實驗室，河南 鄭州450001）

0 引 言

基于使用模型的可靠性測試［1－4］采用使用模型來代表系統可能的運行情況和所發生的概率，使測試接近軟件的真實使用。在凈室軟件工程［5］中，采用Markov鏈描述軟件使用模型，其主要根據軟件的相關技術文檔生成，通過提取軟件運行中的激勵、響應以及之間的交互關系來確定使用模型的狀態與遷移，遷移概率可通過對早期版本使用情況進行分析等方式得到［6］。近年來，UML模型在面向對象軟件設計中得到廣泛應用，也逐漸被應用到使用模型生成技術中［7－9］。現有方法將軟件中每個消息的發生視為狀態的改變，以此生成Markov鏈使用模型，由于將每個消息進入的狀態作為使用模型中的一個狀態，生成的使用模型中存在部分冗余的狀態和遷移。吳彩華等將場景的發生視為軟件狀態的改變，場景的執行概率作為遷移概率，生成場景級的使用模型［8］，該方法生成的使用模型狀態空間較小，但狀態粒度較粗，無法反映用例內部的消息交互，用例執行過程中的相關輸入的依賴關系被忽略，有時不能真實體現軟件的實際使用情況；李秀華為每條消息增加約束條件，通過觀察消息發生前后的系統關鍵向量是否變化來消除使用模型中的冗余狀態和遷移［9］，但該做法增加了人員的工作量，且依賴于領域知識，適應性不強。

本文將代表了用例執行情況的順序圖［10］作為用例的不同場景，對UML 模型加以擴展，加入各場景的執行概率pf 和后置條件post 以及用例執行順序關系，通過分析UML模型中軟件與外部環境的消息交互來確定使用模型中的狀態，生成比較精確的Markov鏈使用模型。同時為了避免狀態空間爆炸問題，提出了冗余狀態與等價狀態的概念，設計了使用模型化簡算法，并給出了相關證明。

1 軟件使用模型

定義1 軟件Markov鏈使用模型定義為一個五元組（S，T，δ，q0，F），S 是軟件使用模型的狀態集合，每個狀態s∈S 是一個三元組 （Sn，Type，Notation），其中Sn是狀態編號，Type表示狀態是否是初始狀態或終止狀態，終止狀態的Notation為后置條件，在使用模型生成過程中用于識別相同的終止狀態，其余狀態該值為空；T 是狀態之間的遷移的集合，每個遷移t∈T 是一個二元組 （Trans，pf），其中Trans是以發生時間先后為全序關系的激勵響應對（sim，res）的有序集合，當其為空時代表不同場景或不同用例的模型之間的轉換，激勵sim 與響應res 來自消息集合；δ是狀態之間的遷移關系S×T→S；q0是使用模型的初始狀態，q0∈S；F 是使用模型的終止狀態集合，FS。

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

對于圖1 （a）所示的使用模型，軟件由狀態Si經過遷移tm到達狀態Sj，又經過遷移tn到達狀態Sk，狀態Si和Sk之間沒有直接遷移，狀態Sj為冗余狀態。可以通過將Sj與Sk合并來減少狀態冗余。合并時，刪除狀態Sj，創建遷移tk連接Si和Sk，tk.Trans＝tm.Trans ∪tn.Trans，tk.pf ＝tm.pf×tn.pf，化簡后如圖1 （b）所示。

圖1 冗余狀態

在軟件可靠性測試中，使用模型主要用來生成模擬真實使用情況的測試序列，根據測試序列執行測試。軟件的測試序列對應于使用模型從初始狀態到結束狀態的一條遷移遍歷路徑t＝ （t1，t2，…，tL），t的執行概率為

式中：pti——路徑t中第i個遷移的概率，L——路徑中遷移數量。

針對圖1中使用模型的冗余狀態Sj，將其與Sk合并化簡并不影響軟件可靠性測試，下面給出證明：

軟件可靠性測試與測試序列t的執行路徑及執行概率p（t）相關，將冗余狀態Sj化簡后，路徑t＝ （t1，…，tm，tn，…，tL）變為t＝ （t1，…，tk，…，tL），其中遷移tk對應執行路徑等同于tm和tn的執行路徑，軟件執行路徑并未改變。

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

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

對于圖2 （a）所示的使用模型，狀態Si和Sj具有相同的遷移tk指向Sk，Si和Sj的源狀態不同，Si和Sj為等價狀態。可將Si和Sj合并為狀態Sij，其出遷移tk指向Sk，原Si和Sj的入遷移指向Sij。

圖2 等價狀態

以圖2所示模型為例，下面針對等價狀態的合并不影響軟件可靠性測試給出證明：

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

2 軟件使用模型生成與化簡

根據擴展UML模型生成軟件Markov鏈使用模型，首先生成用例的使用模型，然后集成所有用例的使用模型得到軟件的使用模型，最后對使用模型進行狀態簡化。

2.1 生成用例的使用模型

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

然后通過集成場景的使用模型來構造用例的使用模型，算法如下：

步驟1 令c為第一個場景的使用模型，在c上集成其它場景的使用模型，對其它所有場景的使用模型ci做如下處理：

（1）令當前狀態cs指向c 的s0，對ci的所有遷移t 進行如下處理：

圖3 場景使用模型生成流程

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

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

（2）將ci的終止狀態的Type 和Notation 值賦給cs，如果存在和cs的Type 和Notation 值相同的狀態s，cs的入遷移為t，前一狀態為s′，令δ（s′，t）＝s，將cs刪除，繼續集成下一場景；

步驟2 所有場景集成后，對各個狀態出遷移的概率進行歸一化，令其概率之和為1。

2.2 集成各用例的使用模型

根據用例執行順序關系集成各用例的使用模型，用例執行順序關系即一個用例執行完成后進入某狀態并執行另一用例的概率，定義為UcSeq＝ （Uci，post，Ucj，pf），代表用例Uci執行完成的后置條件為post 時，下一個執行的用例是Ucj的概率是pf。

步驟1 遍歷用例執行順序關系UcSeq：

對Uci中狀態的Notation 值為post的終止狀態s1，Ucj的初始狀態s2，令遷移t＝ （，pf），δ（s1，t）＝s2；

步驟2 確定軟件使用模型的初始狀態q0，將結束狀態加入集合F。

2.3 使用模型化簡

將軟件使用模型的狀態化簡，由于合并等價狀態之后會出現新的冗余狀態，因此在合并等價狀態之后消除冗余狀態，算法如下：

步驟1 合并等價狀態，對所有狀態s：

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

（2）若存在集合S′pre，將S′pre中狀態合并為新狀態。標記s已遍歷，轉到新狀態；

（3）否則，標記s已遍歷，轉到下一狀態。

步驟2 消除冗余狀態，對所有狀態s：

（1）判斷s是否為冗余狀態；

（2）若s為冗余狀態，將s刪除，并修改相關遷移，轉到下一狀態；

（3）若s 不是冗余狀態，標記s 已遍歷，轉到下一狀態。

3 使用模型生成實例

模 擬 電 話 交 換 系 統 （telephone switching simulation system，TSSS）由交換機 （Switch）、主叫方 （PhoneA）和被叫方 （PhoneB）組成，用例包含有摘機、撥號、應答、主叫掛機、主叫遇忙掛機和被叫掛機。

部分用例執行順序關系為： （撥號，待接通，應答，1），（應答，通話，主叫掛機，0.5）， （應答，通話，被叫掛機，0.5）。

圖4、圖5分別是撥號及應答兩個用例的順序圖。表1是部分用例的順序圖的執行后置條件和概率。系統中消息所對應的含義為：OFK：摘機；RDT：發撥號音；DIA：撥號；SDT：停撥號音；RET：發錯誤音；RFR：查詢空閑；FRE：返回空閑；BUY：返回忙；RBT：發忙音；RCT：發振鈴音；RKT：發回鈴音；NRE：無應答；SCT：停振鈴音；SKT：停回鈴音；ONK：掛機；SET：停錯誤音；SBT：停忙音。

圖4 撥號用例的順序

圖5 應答用例的順序

對TSSS系統構造使用模型，狀態化簡前如圖6所示，其中以虛線表示的狀態屬于冗余狀態，狀態S18和S19互為等價狀態。最終生成的模型如圖7所示，其中遷移為：

在可靠性測試數據生成中，根據遷移發生概率所占的比例大小選擇當前狀態發生的遷移，得到由初始狀態到終止狀態的一條遷移路徑，將其中的null去掉后的激勵響應序列即為一條測試數據。對TSSS軟件，遷移序列t1→t3→t5→t7→t10→t12對應的測試數據為： （OFK，RDT，DIA，RFR，FRE，RCT，RKT，OFK，SCT，SKT，ONK，RBT，ONK，SBT），表示了雙方通話結束后主叫掛機的一種情況。

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

圖6 化簡前的TSSS軟件使用模型

圖7 TSSS軟件使用模型

4 實驗及數據分析

為了驗證使用模型化簡算法的有效性，采用仿真方法得到若干使用模型進行化簡前后的對比實驗。

將每個狀態的遷移限定為1～3條，隨機生成狀態數在300到500之間的使用模型，并對其進行化簡。化簡前后的使用模型狀態數量對比如圖8所示。

圖8 使用模型狀態數量

針對圖8中的使用模型進行實驗，統計生成10000 條測試數據所用時間，對比情況如圖9所示。

圖9 測試數據生成時間

由化簡前后的使用模型狀態數及測試數據生成時間對比可以看出，化簡后的使用模型中狀態數量比化簡前大量減少，降低了使用模型的復雜度，在一定程度上解決了狀態空間爆炸問題；生成相同數量的測試數據所需時間只占化簡前所需時間的30%到50%，節省了大量測試數據生成時間。

5 結束語

本文改進了基于擴展UML模型的軟件Markov鏈使用模型生成方法，并提出了一種使用模型化簡方法。通過實驗驗證了該方法的有效性，采用該方法生成的使用模型在一定程度上解決了狀態空間爆炸問題，有利于測試數據的自動生成與軟件的可靠性測試效率的提高。

該方法中場景執行概率需要人為給出，因此如何更好地估計軟件場景執行概率需要進一步的研究。

［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鏈使用模型的軟件可靠性測評方法研究 ［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的軟件可靠性測試用例生成的混合模型 ［J］.西安交通大學學報，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鏈使用模型的構建 ［J］.計算機研究與發展，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模型的軟件可靠性測試技術的研究與實現［D］.成都：電子科技大學，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 順序圖中消息的形式化描述與相關特性分析［J］.計算機工程與設計，2010，31 （15）：3427－3431.］