基于Petri 網的軟件故障樹分析

2013-10-21 00:58:20楊瀚程

火控雷達技術 2013年4期

林紅楊瀚程

(電子科技大學成都 611731)

0 引言

軟件可靠性分析是保證軟件可靠性的重要步驟，是軟件可靠性工程一個重要的階段。其中，軟件故障樹分析［1］方法有著巨大的工程適用性和強大的生命力。故障樹可看做系統中故障的傳播關系，通過圖形表示和數學描述，通過演繹方式找出導致系統故障原因，求出系統薄弱環節，指導可靠性指標分配和可靠性設計。故障樹不僅能定性分析軟件系統可靠性，還能定量分析軟件系統可靠性。故障樹的分析方法主要有上行法和下行法。但對于大型復雜的故障樹采用上行和下行的方法顯得太過繁瑣。

Petri 網是C.A.Petri 于1962 年在他的博士論文中首次提出的［2］。Petri 網能夠刻畫系統的結構，且描述系統的動態行為，有直觀的圖形表示，同時能夠引入多種數學方法進行分析。經過幾十年的發展，Petri 網理論已經非常成熟，并且在計算機科學技術、自動化科學技術、機械設計與制造以及其他科學領域得到廣泛的應用。Petri 網具有豐富的圖形化和數學化分析方法，主要有可達標識圖與可覆蓋樹，關聯矩陣與狀態方程，Petri 網語言和Petri 網進程，這些方法都建立在堅實的數學基礎上，各有其使用方式。本文提出了通過Petri 網關聯矩陣法求解軟件系統故障樹最小割集的算法，并通過我院研制的ADS-B 系統中最重要的工作信息解碼分析進行了驗證。

1 軟件故障樹的Petri 網模型

故障樹以圖的形式表示事件之間的邏輯關系，它由規定的事件，邏輯門和其他符號描述系統中事件的因果關系［3］。邏輯門的輸入為因，輸出為果。位于故障樹最底層事件為底事件，位于故障樹頂端事件為頂事件，中間事件是除頂事件和底事件以外的事件。使用邏輯門，如與門、或門、表決門，非門等描述事件的因果關系。故障樹首先確定一個軟件中的故障，然后在一定環境和條件下分析軟件，找出不希望發生事件發生的確切方式，即原因。尋找導致系統故障的全部故障模式是故障樹分析的主要任務。故障模式即系統的薄弱環節，也即系統的割集，加強薄弱環節的設計可以提高軟件可靠性。如果割集中任一底事件不發生則頂事件不發生，這樣的割集稱為最小割集。求解最小割集對降低復雜系統潛在事故的風險具有重大的意義。

與一般系統模型類似，Petri 網有兩類元素構成:表狀態的元素和表變遷的元素。Petri 網采用S-元代表狀態元素，T-元代表變遷元素［5］。S-元和T-元同等對待，是分體的，兩者相互依賴。T-元引起S-元資源的流動，流關系用于聯系這兩者之間的關系，用F 表示。Petri 網的系統行為表現為資源的流動。在圖形表示中，用小圓圈表示一個S-元，用小矩形表示一個T-元，用有向邊表示S-元和T-元的關系。Petri 網具有可達性、有界性、安全性，可覆蓋性、可逆性以及守恒性等特性。這些優良的數學特性可以較好的描述復雜系統中常見的同步、并發、分布、沖突、資源共享等現象，同時有著豐富的分析方法。其中，關關聯矩陣分析法適合用于大規模的復雜性較高的Petri 網模型。關聯矩陣法充分利用線性代數方式解決網的分析，并易于使用計算機仿真分析。

對于軟件的故障樹模型，很容易轉化為Petri網［4］。故障樹的與門采用一個變遷代替，或門采用相應的多個變遷表示。對應關系如圖1 所示。然后使用Petri 網分析方法分析Petri 的狀態，由相應關系求解故障樹的參數，例如最小割集［5］。故障樹中通常出現重復事件，可使用Petri 網建模方式合并相同事件，縮小模型規模。