基于時間擴展Petri網的實時嵌入式軟件體系結構建模及可靠性評估

許玉堂，殷永峰，孫靜，張弛，劉斌

（1.北京理工大學機電學院，北京100081；2.北京航空航天大學可靠性與系統工程學院，北京100191；3.中國兵器科學研究院，北京100089）

基于時間擴展Petri網的實時嵌入式軟件體系結構建模及可靠性評估

許玉堂1，殷永峰2，孫靜3，張弛2，劉斌2

（1.北京理工大學機電學院，北京100081；2.北京航空航天大學可靠性與系統工程學院，北京100191；3.中國兵器科學研究院，北京100089）

軟件可靠性是軟件質量評估最重要的指標之一，隨著軟件工程和組件重用技術的發展，近年來基于體系結構的軟件可靠性評估已經成為工程研究的熱點之一。為有效地提高軟件可靠性，調研現有體系結構的可靠性評估模型，給出了現有體系結構模型的分類和模型代表，并分析了現有模型的不足。由于Petri具有良好的擴展性并且對異步和并行軟件有良好的描述性，因此重點研究Petri網可靠性評估模型，通過劃分時間變遷和瞬時變遷，并引入時間相關的可靠度，包括延時可靠度與時序可靠度，對Petri網進行了擴展，給出了時間擴展的Petri網進行體系結構建模方法。通過研究組件狀態和系統可達狀態的關系，創建可達狀態轉移矩陣，對系統進行可靠性評估。將所研究的方法應用于某航電嵌入式系統軟件中，完成了體系結構建模及可靠性評估，并通過誤差分析驗證了該方法的有效性及準確性。

計算機軟件；軟件體系結構；可靠性評估；時間擴展Petri網

0　引言

隨著社會的不斷進步和計算機科學技術的飛速發展，計算機目前已經廣泛地應用于航空、航天、工業控制、交通、金融等各項領域。這些領域的系統越來越多地受到計算機的控制，而其控制軟件的結構也越來越復雜，軟件失效帶來的危害也日趨嚴重［1］。軟件可靠性是軟件質量的一項重要指標，提高軟件的可靠性已成為軟件產業發展和應用的迫切要求。

傳統的軟件可靠性評估模型主要應用于軟件測試、驗證或運行階段，它將軟件看作一個整體，僅僅考慮軟件的輸入和輸出，而不考慮軟件內部的結構，即黑盒測試方法［2］。黑盒測試通過用戶的操作剖面隨機生成測試用例并執行，獲得軟件的失效信息，并對其進行數學建模，在檢測出錯誤后立即修復，從而得到用于評估的可靠性增長模型［3-4］。目前基于黑盒的軟件可靠性評估技術已經比較成熟。但由于這些模型大都是基于失效數據的，需要在軟件測試階段進行，無法對軟件設計階段的錯誤進行預防；同時必須通過長時間基于運行剖面的測試才可以得到足夠多有意義的失效數據，勢必會浪費大量的人力物力［5-6］。

基于體系結構的開發是現代軟件開發的重要途徑，也是軟件工程的要求。軟件的體系結構與軟件本身的質量和性能息息相關。并且實踐表明，越早發現軟件中存在的錯誤，所花費的開銷就會越小。軟件的可靠性與組成軟件的構件可靠性和構件結構相關，因此利用軟件體系結構對軟件的可靠性進行分析和評估是一種很有價值的方法。

本文首先介紹了基于體系結構模型的可靠性評估的基本思路，并列舉了15種經典模型。由于Petri網能夠良好地描述并發和異構模式，而且具有良好的擴展能力，因此本文對Petri網進行可靠性評估的方法進行了深入研究。將Petri網中的變遷，劃分為瞬時變遷和時間變遷，并引入時間方面的可靠性，主要表現在延時可靠性和時序可靠性方面。隨后基于時間擴展的Petri網進行系統體系結構建模，并采用可達狀態圖的方法解決了組件和狀態并非一一對應的問題。由于時間Petri網可以同構成一個離散時間馬爾可夫鏈，采用狀態概率轉移矩陣計算整個系統的可靠性。最后將本文提出的方法運用到一個工程實例中，驗證模型的有效性及準確性。

1　基于體系結構的可靠性評估

1.1組件的概念及其可靠性

現有的基于體系結構的可靠性評估大都以組件為軟件的基本單元。一般認為組件是指具有一定功能，可明確辨識的軟件單位，是軟件系統計算或者存儲的對象，并且語法完整、語義正確，有重用的價值，一個組件可以包含多個接口，這些接口說明了組件怎樣通過提供或者請求操作與環境交互。組件一般具有獨立性、可替換、低耦合、高內聚等特點。對于基于體系結構的可靠性評估，還假設組件具有如下約束：

1）組件接口分為輸入接口和輸出接口；

2）組件所有的輸入和輸出域都映射到接口。也就是說組件所有的輸入和輸出都由接口來完成，沒有其他方式的信息傳遞通道；

3）除了常見的功能接口描述以外，組件還應有可靠性度量指標；

4）組件可靠性與軟件運行的路徑無關。

對于組件的可靠性，部分模型假設單個組件可靠度為已知，文獻［7］使用傳統的可靠性增長模型來計算可靠度，但是耗時較長，還有文獻［8］指出使用故障注入等方式還進行計算，但到目前為止還沒有一個公認的方法能夠在體系結構評估過程中精確計算每個組件的可靠度。在此重點是對體系結構建立符合其運行特征的模型，并看單個組件可靠度的變化對整體可靠度的影響，因此對組件可靠度的計算不做深入討論，假設組件可靠度為已知。

1.2體系結構模型的類別和典型模型介紹

1.2.1體系結構評估模型分類

自1975年起，Parnas和Shooman開始提出了軟件結構對軟件可靠性影響的重要性，率先突破了軟件可靠性只考慮整體與外部交互的局面，第一次將軟件內部結構應用到可靠性評估當中。文獻［9-10］中將三十幾年間出現了基于體系結構的可靠性評估模型歸納為3類：狀態模型、路徑模型和其他模型，具體模型分類和各個模型基本情況見表1所示。

表1　體系結構評估模型分類Tab.1 Classification of architecture evaluation models

1.2.2典型模型介紹

1.2.2.1基于狀態的評估模型

基于軟件狀態的可靠性模型采用狀態控制流程圖來描述軟件的體系結構。由于構件被定義為邏輯上獨立的功能集合，可將一個構件的執行看成一個狀態。假設軟件系統處于某一個狀態時，那么它的下一時刻的狀態只與當前狀態有關，而與在此之前的狀態無關，那么各個狀態的轉移就符合馬爾可夫過程。狀態模型采用馬爾可夫鏈對軟件體系結構進行建模。而根據軟件體系結構和體系結構元素失效方式的建模方式不同，狀態模型又可分為組合模型和分層模型兩種。Cheung模型是最早考慮到模塊可靠度應用到軟件可靠性預測的模型之一［11］。該模型假設一個軟件系統中具有n個構件，各構件的可靠性和構件之間的轉移概率已知，并假設狀態圖中有唯一的開始節點和結束節點。將軟件體系結構用離散時間馬爾可夫過程（DTMC）進行建模，創建狀態轉移矩陣P=［pij］，通過n次計算得到系統可靠性。Wang W.在Cheung的研究基礎上做出了關系軟件體系結構風格評估的擴展工作［12］。利用Cheung氏馬爾可夫模型來評估不同體系結構風格下的可靠性。文獻［11］使用到的體系結構風格有：批處理；管道—過濾器；調用—返回和備份容錯。對于分層模型，最早的分層模型是Littlewood模型［13］，將軟件體系結構采用連續時間的馬爾可夫鏈過程（CTMC）進行建模，假設構件i轉移到構件j的平均執行時間是mij；構件i的失效符合參數為λi的泊松過程；構件i轉移到構件j時接口發生失效的概率是vij，并做出假設：

失效發生的次數要遠少于軟件控制權轉移的次數，則軟件系統的失效也符合泊松過程，軟件失效率為

1.2.2.2基于路徑的評估模型

基于路徑的可靠性模型與基于狀態的可靠性模型具有相似的分析方法，最主要的區別在于計算軟件系統可靠性時考慮了系統的執行路徑。最早的基于體系結構的路徑模型由Shooman等提出［14］。他從軟件的執行路徑角度對軟件體系結構進行了建模，每個軟件具有m個執行路徑，每條路徑i具有執行頻率fi，每條路徑還具有相應的失效概率qi.在軟件系統的N次運行中，失效總數為式中：Nfi代表路徑i執行總次數。則整個軟件系統的失效概率可以寫作Yacoub，Cukic和Ammar［2］結合了場景技術來計算軟件的可靠性，一個場景可以定義為一系列構件的相互作用，具有特定的外部激勵。運用場景技術，可以建立一個隨機概率模型：組件關系依賴圖（CDG）.CDG可以描述一個場景，其中包括執行過程的時間信息、系統組件間的交互以及可靠性信息等。CDG的特別之處在于運用統一建模語言UML建立了描述軟件系統運行的執行模型，并結合不同場景，遍歷模型，計算出不同場景下不同構件對軟件系統可靠性影響的大小。

1.2.2.3其他模型

其他模型包括仿真模型和增量模型。仿真模型［15］對軟件系統在時間域內的失效行為進行仿真，假設軟件構件的失效強度函數服從G-O模型λ（t）=αe-bτ，構件平均執行時間Φ和構件i、j之間轉移概率wij作為仿真需要的參數。通過一個離散時間仿真模型算法來驅動軟件系統運行，其中輸入為軟件系統運行一次時的可靠性和執行時間，通過設定相應的仿真算法，計算出軟件系統的可靠性。增量模型［16］沒有明顯的軟件體系結構特征，而主要是利用組件的失效數據來估計系統的可靠性。這些模型假設構件的可靠性可以用非齊次泊松過程（NHPP）建模，系統的失效強度可以用構件的失效強度和來表示。

現有的體系結構模型普遍存在參數準確性不足，假設條件過多，且部分假設與實際情況不符等缺點。并且在大部分模型中，將每個組件的運行看作一個狀態，但軟件在實際運行中，狀態可能需要不止一個組件來支持其實現，因此需要研究組件與系統運行狀態的關系。同時，對于航電嵌入式軟件，時間方面的可靠性也是需要重點考慮的因素，而這些情況現有的模型無法良好地描述［17］。

2　基于時間擴展Petri網的軟件體系結構建模及可靠性評估

2.1Petri網的體系結構建模及時間擴展研究

2.1.1Petri網簡介

Petri網是20世紀60年代由卡爾·A·佩里發明的，適合于描述異步、并發的計算機系統的模型。首先給出經典Petri網的定義：Petri網是一個四元組的集合Σ=（P，T，F，M0），其中：

1）P=｛p1，p2，…，pn｝是有限位置集合；

2）T=｛t1，t2，…，tm｝是有限變遷集合（P∪T≠?，P∩T=?）；

3）F∈（P×T）∪（T×P）為流關系；

4）M0是網的初始標識，Petri網的標識是位置集上的多重集，M0代表系統在最開始狀態時令牌在各個位置中的分布情況。

Petri網可用一個有向二部圖表示，其中包含兩類節點，并且用有向弧連接起來。兩類節點分別為位置和變遷，其中位置一般用圓圈表示，變遷一般采用矩形表示。Petri網除了具有以上靜態結構外，還包括了描述動態機制的行為。這一特征是通過允許位置中包含令牌，其中令牌用黑點表示。在含有令牌的Petri網中，依據遷移的使能條件，可以使得使能的遷移點火，遷移的點火會依據點火規則實現令牌的移動。不斷變化著的令牌重新分布就描述了系統的動態變化，一個典型的Petri網圖如圖1所示。

圖1　典型Petri網圖Fig.1 Typical Petri net

Petri網具有良好的擴展性，可實現針對實時嵌入式軟件的建模及驗證，特別是在安全關鍵軟件驗證領域已得到成功應用［18］，本文對Petri網的時間方面的擴展進行了研究，提出了一種基于時間擴展Petri網的體系結構建模方法，并在此基礎上為后續基于體系結構的可靠性評估奠定基礎。

2.1.2軟件體系結構的Petri網描述

在之前的研究中，通過引入時間要素已經出現了隨機Petri網（SPN）和時間Petri網（TPN）。SPN是一種引入時間因素的Petri網，引入的方法是：在每個變遷的可實施和實施之間聯系一個隨機的延遲時間，變遷在獲得系統資源后不會立即點火，而是設置一個定時器，當定時器時間變為0時變遷才會點火。時間Petri網也是將時間因素加入到變遷當中，與SPN不同的是，引入的時間延時不是一個隨機時間，而是一個時間區間，變遷在該區間內等可能引發。Petri網是一個描述系統動態運行的模型，系統中某個事件的發生通常用一個變遷來表示，軟件的運行需要一定的運行時間，因此將時間與變遷聯系起來也是合情合理的。

軟件體結構都是以組件為基礎，因此在進行Petri網建模時，將庫所看作組件的集合，庫所之間的轉移看作每個組件運行狀態的轉移，當組件獲得CPU和內存等系統資源時，即視為獲得令牌。對于變遷，可以按照廣義SPN的定義，將變遷分為瞬時變遷和時間變遷，可以將一些選擇狀態看作是瞬時變遷，其所花費的系統時間可以忽略不計。而對于時間變遷，一般為需要獲得系統資源（如CPU，內存等），進行一定時間運行的變遷，可將其看作是上一組件的運行時間。瞬時變遷用一個黑線表示，時間變遷用一個矩形框表示，如圖2所示。

圖2　兩類變遷的圖形表示Fig.2 Graphical representation of two types of changes

使用引入瞬時變遷和時間變遷的Petri網可以很好的描述并發，選擇等結構。對于選擇結構，組件可以分成兩個瞬時變遷，因為組件的選擇不需要占用太多的系統資源，可以看作是瞬時變遷，對于選擇結構中瞬時變遷，為變遷賦值該組件運行的概率，選擇結構后只有一個組件可以獲得令牌，選擇結構可以用圖3表示。

對于并行結構，可以使用兩個時間變遷進行描述，兩個組件都可以獲得令牌執行，并行結構的Petri網圖可用圖4表示。

圖3　選擇結構的Petri網表示Fig.3 Petri net represetation of selected structure

圖4　并行結構的Petri網表示Fig.4 Petri nets representation of parallel structure

2.1.3Petri網時間因素的引入

對于Petri網引入的時間要素，如何與可靠性評估結合起來，是本文研究的一個重點。在傳統的可靠性評估模型中，大都假設只有組件才具有小于等于1的可靠度。本文在此基礎上進行了擴展，除了組件具有單獨可靠度以外，部分變遷也具有可靠度，并不是所有的變遷可靠度都為1.對于瞬時變遷，引入執行該變遷的概率作為參數，不用考慮可靠性。而對于時間變遷引入可靠度參數，其值與時間因素相關，變遷失效的類型主要有以下方面：

1）變遷的發生超過其規定的時間；

2）兩個互斥事件的發生；

3）事件按照錯誤的順序發生。

2.1.3.1延時可靠性的引入

在擴展時間Petri網中，對于時間變遷，引入一個不確定時段，代表變遷可以在這一時間段實施，該時間段可以表示為X（t）=［tl，tu］［19-20］，其中0≤tl≤tu，tl和tu是相對時間，相對于系統初始運行的時刻，由系統決定。假設變遷在時刻s使能，實際觸發的時刻記為t*，則s+tl≤t*≤s+tu.對于瞬時變遷，可表示為X（t）=［0，0］，代表其實施不需要時間延遲。將時間因素引入到變遷當中主要應用于并發的發生，當兩個組件并發執行時，各個變遷的執行有各自的使能時間，而最后并發的變遷完成后需要合并，進入下一組件運行，此時兩個并發的變遷合并轉入下一組件時能否滿足系統內變遷的延遲，當變遷的發生大于該變遷規定的延遲時，則該變遷會發生失效，失效的可能性與變遷發生的時間段和系統定義的變遷時延有關。

圖5為典型的并行結構的Petri網，變遷T1和T2之間沒有直接的時間約束關系，圖5中表示到達S后經過瞬時變遷，使得T1，T2同時出發，這兩個變遷在相同標識中可獨立實施，一個變遷的運行不影響另一個變遷的運行，當兩個變遷都執行完畢后，經過同步，標識到達結束狀態E.用s1、s2、s分別表示變遷T1、T2、T的觸發使能時刻，分別表示變遷T1、T2和T的實際觸發時間。由于從S經過瞬時變遷使得T1和T2同時使能，因此s1=s2=s，由于Petri網的性質，可得因此T1、T2結束時間段為［s+t1l，s+ t1u］、［s+t2l，s+t2u］，最晚結束時間則為max（s+t1u，s+t2u），即T的等效觸發最早結束時間為max（s+t1l，s+t2l），最晚結束時間為max（s+t1u，s+t2u），因此可以得到s+max（t1l，t2l）≤t*≤s+max（t1u，t2u），通過Petri網的性質可以獲得變遷T發生的時間段為［max（t1l，t2l），max（t1u，t2u）］.

圖5　并行結構的Petri網視圖Fig.5 Petri nets of parallel structure

在軟件實際運行時，變遷T的發生也是有延時方面的限制，假設系統運行定義的變遷T發生的延時限制為t′，如果max（t1u，t2u）-max（t1l，t2l）≤t′，則代表兩個變遷合并之后其發生的時間段仍然小于系統規定時延，因此其可靠度為1，不會發生延時方面的失效。如果max（t1u，t2u）-max（t1l，t2l）＞t′，則根據Petri網運行推算出的時延大于系統規定時延，有可能發生延時方面失效，其可靠度

通過對變遷加入使能時間段，使得Petri網不僅能夠對系統運行狀態進行描述，還能夠分析系統每個時段各個組件的運行情況，滿足了嵌入式系統對于時間因素的敏感性，并且通過引入時間變遷的延時可靠度，對于并發結構變遷的延時情況進行了研究，使得評估更加符合實際情況。

2.1.3.2時序可靠性的引入

時間相關的后兩種情況，主要是系統資源互斥以及時序問題。軟件需要運行，必須要獲得一定的系統資源，而在不同的時間段各個模塊所獲得的系統資源也各不相同。在某些系統中，有些事件不能同時占用系統資源運行，這些事件就稱為互斥事件，當互斥事件發生時，也屬于一種失效。另一方面，在嵌入式系統中，某些變遷的發生需要之前變遷遵循一定的順序發生，只有滿足條件變遷才能正常使能，對于這種變遷，因此引入與時序相關的可靠性，增加可靠性評估的準確性。

對于如何描述系統時序方面的信息，引入時序Petri網中相關概念［21］。時序Petri網是在基本Petri網上引入時序邏輯公式，而這些邏輯公式對Petri網中的變遷引發順序加以限制。當且僅當變遷T滿足Petri網中的引發條件和邏輯公式時，T才能引發，其他描述與基本Petri網相同。時序公式是一組公式的集合并且具有如下性質：

1）命題p，↑t和t是原子命題，其中p∈P，t∈T；

2）如果f和g是公式，則┑f，f∧g，f∨g，f?g，○f，◇f，□f，f∪g也是公式。

上述性質中，p表示庫所獲得令牌，↑t表示變遷t在當前標識下使能，t表示變遷t在當前標識下引發。其中┑，∧，∨，?是布爾運算符。公式○f，◇f，□f和f∪g是時序邏輯符號?！餱表示下一狀態f為真；◇f表示從當前狀態（包括當前狀態）開始以后的所有狀態至少有一個狀態使得f為真；□f表示從當前狀態（包括當前狀態）開始以后的所有狀態都為真；f∪g表示f為真，直到g為真。

在Petri網中引入時序邏輯公式后，需要將其運用到可靠性評估中。首先分析系統中的時序邏輯公式，確定系統運行需要遵循的規則，對于一個規則，例如時序約束公式（Fe1）□（t1?◇t2），表示t1不能一直使能，以后需要有一個狀態讓t2使能，否則t2就會一直無法獲得系統資源而處于饑餓狀態。對變遷t2加入一個時序可靠性，該變遷時序失效率λ為系統一直執行t1而不執行t2的概率，該變遷的時序可靠性即為1-λ.并非所有的變遷都具有時序相關可靠性，在進行可靠性評估時，首先需要了解系統運行的一些特定規則，定義系統運行的時序邏輯公式，根據公式確定哪些變遷的使能具有時序相關特性，并計算時序相關的可靠性。通過引入時序邏輯公式和變遷時序可靠性，可以描述嵌入式系統中的互斥事件和特定事件序列，進一步提高了Petri網可靠性評估模型的準確性。

在進行體系結構的可靠性評估時，很多時候是因為軟件不適合進行系統地測試，無法使用黑盒的測試方法通過可靠性增長模型獲得整個系統可靠度。只能通過對軟件分開測試，獲得各個組件的基本信息，如運行時間、單獨可靠度等。然后依據系統的架構建立相應的評估模型。因此如何描述系統的實際運行情況是可靠性評估的一個重點。對于嵌入式軟件，時間因素的描述是一個重要環節，本文通過引入TPN和時序Petri網中的相關概念，將其與可靠性評估結合起來，增強了Petri網描述嵌入式軟件的能力。而由于Petri網具有良好的擴展性，因此這些概念的引入不會影響其本身的描述能力。

2.2基于TPN的可靠性評估

在完成了對Petri網的擴展后，需要通過該網絡進行可靠性評估。首先需要繪制體系結構的Petri網模型。對于系統中的組件，定義其為Petri網中的庫所，通過令牌在庫所中的轉移來描述系統的運行。然后通過分析系統的運行時間和時序關系等特征，計算出某些變遷的時間相關可靠度。

在獲得了單獨組建可靠度和變遷可靠度時，需要建立計算系統可靠性的模型。首先需要獲得系統運行狀態的可靠度與運行組件可靠度之間的關系。在系統實際運行時，一個系統狀態的運行可能需要不止一個組件來支持。因此對于系統的運行狀態，如果系統中有n個組件，可定義一個n維向量Mi=（s1，s2，…，sn）來描述該狀態，如果在此狀態下第i個組件處于運行狀態，則s1置為1，否則置0.對于狀態可靠度與運行組件可靠度之間的計算關系，擬采用如下方式進行計算：

1）如果當且僅當所有的組件都正常運行時該狀態才能正常運行，則為串聯狀態，該狀態的可靠度為所有組件可靠度的乘積；

2）如果只要某一個組件能夠正常運行該狀態便可以正常運行下去，則為并聯狀態，該狀態的失效率為所有組件失效率的乘積，可靠度則為一減去失效率；

3）如果系統既有串聯運行狀態也有并聯運行狀態，則為混聯運行狀態。此時的可靠性計算可以采用遞歸的方法：每次依據串聯或者并聯的形式，進行逐層分解，直到分解所得的每一部分均含有單純串聯或者并聯狀態為止，再利用上述串/并聯狀態可靠性計算方法逐層回溯，最終得到該狀態的可靠度。

獲得了系統各個狀態可靠度和變遷的可靠度后，可以通過狀態模型來計算系統的可靠度，對于可靠性計算方法進行如下假設：

假設1 軟件任意可達狀態發生失效，都視為軟件系統的失效；

假設2 軟件各個狀態發生的失效相互獨立，軟件某個狀態發生的失效不會受到其他狀態的影響；

假設3 假設軟件各個狀態之間的轉移服從DTMC.軟件狀態之間的轉移概率由軟件系統的剖面決定，狀態間的控制轉移只與當前狀態有關，而與此狀態之前的狀態無關。

基于如上假設，構建系統的狀態轉移矩陣，假設系統由n個可達狀態構成｛M1，M2，…，Mn｝，其中M1為初始狀態，Mn為終止狀態，每個狀態的可靠度用Ri表示，用pij表示系統正常從狀態i運行到狀態j的概率，如果狀態轉移的變遷存在可靠度，則其值為轉移的概率與變遷可靠度的乘積。矩陣第i行、j列代表狀態i不發生失效并正確轉移到狀態j的概率，即Ripij，因此可得到如下矩陣：

對現有狀態空間進行擴充，加入兩個吸收狀態S和F，其中：S代表軟件正確完成并結束的概率，該狀態只能由最終狀態Mn轉移得到；F為軟件某一個狀態發生失效，可以由任意狀態獲得。這樣狀態空間擴充為｛S，F，M1，M2，…，Mn｝，擴展的狀態轉移矩陣如下所示：

由（4）式可以看出，矩陣M′為M增加了前兩列，其中：第1列為各狀態轉移到狀態S的概率，即軟件正常執行的概率；第2列為各構件狀態轉移到狀態F的轉移概率，即發生失效的概率。在矩陣M中，最后一行元素為0，而在矩陣M′中，最后一行元素和仍為0，這意味著終止狀態Mn只能轉移到S或F狀態。

Mk（i，j）代表狀態i經過k步轉移，到達狀態j的概率，因此Mk（1，n）為軟件初始狀態，經過k步轉移，到達終止狀態n的概率。這樣可以得出：

式中：I為單位矩陣；E為（I-M）矩陣中刪除第n行和第1列后的矩陣。

則軟件的系統可靠度：

利用狀態之間轉移的馬爾可夫模型進行可靠性評估具有良好的效果，特別是當系統中存在循環路徑時。如果采用路徑的模型，可能需要對循環路徑進行處理，需要對路徑循環執行的次數進行研究，計算方法較為復雜并且可能不太準確。但是基于狀態轉移的馬爾可夫過程可以依據自身數學計算的特征順利地解決循環路徑的問題。

3　實例研究

3.1被測軟件介紹

本節將之前的可靠性評估方法帶入到一個具體實例中，下面以某飛控系統中的縱向控制軟件為例，首先對其體系結構進行Petri網建模，然后進行可靠性評估，并將計算結果的誤差與傳統模型進行比較。飛控系統是飛機上的核心系統之一，包含了復雜的并發、異步等活動，系統共包含4個軟件模塊，包括系統自檢（BIT），縱向操控軟件，橫航向操控軟件以及操作系統軟件。

為了驗證上述可靠性評估方法的有效性和準確性，本文選取縱向操控軟件進行實例研究，縱向系統主要包含兩個子系統，分別為縱向控制增穩軟件和縱向自動駕駛軟件，工作流程如下：

1）當縱向控制增穩按鈕按下時，駕駛員的操作處于主導，通過操縱桿控制飛機的高度，系統軟件處于縱向控制增穩功能，主要進行控制增穩控制律的計算，以及控制律的調參，并控制俯仰角以避免出現危險情況，進而輔助飛行員進行駕駛；

2）當縱向自動駕駛按鈕按下時，系統進入縱向自動駕駛狀態，此時飛行狀態主要由軟件進行控制，系統除了進行各種調參之外，還需要對飛機俯仰姿態進行跟蹤控制，并且當駕駛員對駕駛儀進行拉高或者俯沖操作時進行控制律的計算，當到達指定高度后改平俯仰狀態使飛機進入一個穩定狀態。

3.2飛控系統建模

通過查閱文檔和代碼，根據3.1.1節中的建模方法，可以繪制該飛控縱向控制軟件體系結構的Petri網圖，如圖6所示。

圖6　某飛控縱向控制軟件的Petri網結構圖Fig.6 Longitudinal control of a flight control software structure of Petri nets

開始狀態為縱向飛行的穩定狀態，飛行員通過操縱界面對飛機縱向飛行狀態進行控制，分別進入縱向控制增穩狀態和縱向自動駕駛狀態，在完成了對飛行姿態的控制以后，最后飛機再次進入一個縱航向上的穩定飛行狀態，圖中各個組件和變遷和含義見表2.

3.3基于體系結構的可靠性評估

通過構建Petri網模型，對系統組件的信息以及組件之間的轉移進行了描述。Petri網通過令牌的運行來模擬整個軟件系統的運行，在某一時刻如果組件獲得令牌則處于運行狀態，通過令牌的轉移可以獲得整個系統的可達狀態標識，進而得到Petri網的可達狀態標識轉移圖，如圖7所示。

系統有12個組件，因此對于每一個可達狀態標識，定義一個12個元素的向量表示，當組件在該狀態運行時則其值為1，否則為0，系統每個狀態的含義以及向量表示見表3.

表2　飛控縱向控制軟件組件和變遷名稱Tab.2 Names of flight control longitudinal control software components and changes

表3　可達狀態標識含義及向量表示Tab.3 Identification meaning of reachable states and vector representation

在使用Petri網建立其體系結構模型之后，需要添加可靠性信息。根據軟件測試獲得失效數據，運用可靠性增長模型，可以得到各個組件的單獨可靠度為Rs1=0.999 2，Rs2=0.995 1，Rs3=0.994 8，Rs4= 0.987 5，Rs5=0.984 7，Rs6=0.994 5，Rs7=0.993 2，Rs8=0.994 8，Rs9=0.982 4，Rs10=0.991 2，Rs11= 0.991 2，Rs12=0.9981.幾個選擇變遷執行的概率分別為：t1=0.7，t2=0.3，t4=0.8，t5=0.2，t10=0.5，t11=0.5，t3=0.2，t′3=1-t3=0.8，t9=0.2，t′9=1-t9=0.8.

在時間變遷中變遷t8具有延時方面的可靠性，t12具有時序方面的可靠性。由于變遷t8屬于兩個并行變遷t6、t7運行之后的合并變遷，因此具有合并后的延時的可靠性。由系統運行情況可知，變遷t7運行的時間段可以表示為［46 ms，98 ms］，變遷t6運行的時間段為［47 ms，90 ms］，因此可以獲得變遷t8期望的運行時間段為［47 ms，96 ms］.而系統中對于延時的要求為50 ms，因此可得該變遷的延時可靠度Rt8=50/51=0.980 4.對于變遷t12，根據Petri網圖以及變遷可以獲得時序邏輯公式為t11?◇t9∧t12，根據系統實際運行情況，計算可得t12的時序可靠度為Rt12=0.992 0.

在獲得了所有可靠性信息以后，根據上文描述的計算方法，可以獲得可達狀態的概率轉移矩陣：

圖7　某飛控系統可達狀態轉移圖Fig.7 State transition of a flight control system

根據（6）式，計算得到整個系統的可靠度R= 0.963 4.

3.4誤差分析及與傳統模型的比對

基于軟件體系結構的可靠性評估結果是否可以準確反應軟件系統的真實可靠性水平，是多年來一直困擾研究者的問題，文獻［22］提出了將模型評估結果與來自軟件測試數據的可靠性評估結果作對比，定義軟件可靠性的相對誤差為

式中：Ra是利用軟件系統測試的失效數據得到的系統“真實”可靠度；Rs是通過評估模型計算得出的可靠性。根據測試收集的失效數據，得出該軟件的“真實”可靠度為0.955 1，因此有相對誤差

本文選用傳統的狀態模型［11］對軟件進行可靠性評估，并與時間擴展Petri網的可靠性評估模型的結果進行對比。選用該狀態模型的原因是在現有的基于體系結構的可靠性評估模型中，其評估結果的準確度被認為是最高的，同時也是應用最為廣泛的模型。根據文獻［2］描述的方法，創建馬爾可夫狀態轉移矩陣，計算可靠度為0.974 4，因此有相對誤差

通過相對誤差分析，可以證明本文提出的基于時間擴展Petri網的可靠性評估模型比傳統模型具有更高的準確性。

4　結論

基于體系結構的可靠性評估主要有兩個方面的意義：一方面有些軟件無法進行系統的黑盒測試，只能對各個組件單獨測試，然后建立體系結構的可靠性評估模型來計算整個系統的可靠性；另一方面，可以在軟件開發的早期建立起軟件的體系結構模型，因為經過大量的工程實踐表明，軟件的很多缺陷都是在設計階段產生的，通過在開發時期建立體系結構的可靠性模型，能夠對開發有一定的指導意義。通過對各個組件進行靈敏度分析，可以獲得對系統可靠性影響較大的關鍵組件，作為軟件開發階段的重點，避免不必要的錯誤，在開發階段可以有效提高系統的可靠性，從而節省在后期驗證階段耗費的人力物力。

本文首先總結了現有的基于體系結構的可靠性評估模型，介紹了組件和基本Petri網的概念。然后對于基于組件的軟件體系結構，提出了時間擴展的Petri網模型，通過引入時間變遷和瞬時變遷，并對時間變遷引入與時間關聯的可靠度，提高了模型對實時嵌入式軟件的描述能力。最后選用一個典型的嵌入式軟件——飛控系統，對其中的縱向操控軟件，建立其Petri網圖，帶入相應的可靠性信息，計算整個系統的可靠度，并進行相對誤差分析，驗證了模型的準確性。

TPN模型會隨著庫所和變遷等建模元素的增長呈指數級增長，會導致出現狀態空間的爆炸問題，如何緩解狀態空間，對模型進行精簡，又不降低其描述能力，現在正在成為一個研究方向。而進行體系結構的可靠性評估時，對于單個組件可靠度和變遷可靠度，如何能夠進一步提高計算的準確性，也是今后研究的一個重點。

（

）

［1］YIN Y F，LIU B，NI H Y.Real-time embedded software testing method based on extend finite state machine［J］.Journal of Systems Engineering and Electronics，2012，23（2）：276-285.

［2］Goseva-Popstojanova K，Trivedi K S.Architecture-based approach to reliability assessment of software systems［J］.Performance Evaluation Journal，2001，45（2/3）：179-204.

［3］Ramamoorthy C V，Bastani F B.Software reliability-status and perspectives［J］.IEEE Transactions on Software Engineering，1982，8（4）：354-371.

［4］Goel A L.Software reliability models：assumptions，limitations，and applicability［J］.IEEE Transactions on Software Engineering，1985，11（12）：1411-1423.

［5］Horgan J R，Mathur A P.Perils of software reliability modeling［R］.US：Software Engineering Research Center，Purdue University，1995.

［6］Hsu C J，Huang C Y.An adaptive reliability analysis using path testing for complex component-based software systems.［J］，Reliability，2011，60（1）：158-170.

［7］Fiondella L，Rajasekaran S，Gokhale S S，et al.Efficient software reliability analysis with correlated component failures［J］.IEEE Transactions on Reliability，2013，（6）2：244-255.

［8］Noh Y J，Choi K K，Du L.Reliability-based design optimization of problems with correlated input variables using a Gaussian Copula［J］. Structural and Multidisciplinary Optimization，2009，38（1）：1-16.

［9］Gokhale S S，Trivedi K S.Structure-based software reliability prediction［C］∥Proceedings of 5th International Conference on Advanced Computing.Chennai，India：IEEE，1997：447-452.

［10］Gokhale S S，John R C，William H F.System availability analysis considering failure severities［J］.International Journal of Performability Engineering，2007，3（4）：467.

［11］Li Q Y，Lei L，Jun A，et al.The determination method for software reliability qualitative indices［C］∥Software Security and Reliability（SERE），2013 IEEE 7th International Conference on.Gaithersburg，MD：IEEE，2013：237-245.

［12］Inoue S J，Shigeru Y D.Two-dimensional software reliability measurement technologies［C］∥Industrial Engineering and Engineering Management.Hongkong：IEEE，2009：223-227.

［13］Littlewood B.Software reliability model for modular program structure［J］.IEEE Transactions on Reliability，1979，28（3）：241-246.

［14］Park J，Kim H J，Shin J H，et al.An Embedded Software Reliability Model with Consideration of Hardware Related Software Failures［C］∥IEEE Sixth International Conference on Software Security andReliability.Gaithersburg，MD：IEEE，2012：207-214.

［15］Lee W B，Boo G J，Jongmoon B.Early reliability prediction：An approach to software reliability assessment in open software adoption stage［C］∥Second International Conference on Secure System Integration and Reliability Improvement.Yokohama：IEEE，2008：226-227.

［16］Inoue S J，Shiho H，Shigeru Y.Toward practical software reliability assessment with change-point based on hazard rate models［C］∥2013 IEEE 37th Annual Computer Software and Applications Conference（COMPSAC）.Kyoto，Japan：IEEE Computer Society，2013.

［17］Nelsen R B，Manuel'U Flores.The lattice-theoretic structure of sets of bivariate copulas and quasi-copulas［J］.Comptes Rendus Mathematique.2005，341（9）：583-586.

［18］Noh Y J，Choi K K，Liu D.Reliability-based design optimization of problems with correlated input variables using a Gaussian copula［J］.Structural and Multidisciplinary Optimization，2009，38（1）：1-16.

［19］Huang C，Lin C，Kuo S，et al.Software reliability growth models incorporating fault dependency with various debugging time lags［C］∥Proceedings of the 28th Annual International Conference on Computer Software and Applications.Hongkong：IEEE，2004：186-191.

［20］Kaneishi T，Tadashi D.Software reliability modeling and evaluation under incomplete knowledge on fault distribution［C］∥7th International Conference on Software Security and Reliability（SERE）.Gaithersburg，MD：IEEE，2013.

［21］Chandra B，Koizumi T，Hayashi M，et al.A study on network reliability evaluation for developing countries［C］∥2012 18th Asia-Pacific Conference on Communications.Jeju Island Korea：IEEE，2012.

［22］Zeng J T，Li J Z，Zeng X H，et al.A prototype system of software reliability prediction and estimation［C］∥2010 Third International Symposium on Intelligent Information Technology and Security Informatics（IITSI）.Jinggangshan：IEEE，2010.

Real-time Embedded Software Architecture Modeling and Reliability Estimation Based on Time-extended Petri Net

XU Yu-tang1，YIN Yong-feng2，SUN Jing3，ZHANG Chi2，LIU Bin2
（1.School of Mechatronical Engineering，Beijing Institute of Technology，Beijing 100081，China；2.School of Reliability and System Engineering，Beihang University，Beijing 100191，China；3.Ordnance Science and Research Academy of China，Beijing 100089，China）

Software reliability is one of the most important quality indices in software quality evaluation. With the development of software engineering and component reusing，the reliability analysis based on software architecture has become a researching hotspot.This paper puts a research on existed architecture-based reliability estimation models at first，then proposes existing architecture based reliability estimation types and typical models，putting forward the shortage of these models as well.As Petri net has a well expansibility and descriptive power of concurrency and asynchronism，this paper focuses on the research of Petri net model，divides transition into time transition and instant transition，and adds time-related reliability—time-delay reliability and temporal reliability，by this means establish the software archi-tecture modeling.The reachable state transition matrix is set up and the system reliability estimation is made by studing the relationship between component state and system reachable state.At last，the method is used in a avionics embedded software for architecture modeling，reliability estimation and error analysis，proving the effectiveness and accuracy of this method.

computer software；software architecture；reliability estimation；time-extended Petri net

文獻標志碼：A文章編號：1000-1093（2015）02-0363-11

10.3969/j.issn.1000-1093.2015.02.025

2014-04-15

航空科學基金項目（20140751008）；中央高?；究蒲袠I務費專項資金項目（YWF-11-03-Q-114）

許玉堂（1978—），男，博士生研究生。E-mail：xyutang@foxmail.com；殷永峰（1978—），男，副教授。E-mail：yyf@buaa.edu.cn