林 紅 楊瀚程

(電子科技大學 成都 611731)

0 引言

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

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

1 軟件故障樹的Petri 網(wǎng)模型

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

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

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

2 使用Petri 網(wǎng)關聯(lián)矩陣求解故障樹最小割集算法

算法具體步驟如下:

A.畫出軟件系統(tǒng)各事件間的邏輯關系，構成故障樹。分析軟件系統(tǒng)中最重要的故障，作為頂事件，逐層細化分析造成頂事件的原因。

圖1 故障樹表示與Petri 網(wǎng)表示對應關系

B.求出故障樹對應的Petri 網(wǎng)。對已形成的故障樹，與門采用一個變遷表示，或門采用多個變遷表示，事件用庫所表示，添加流關系，形成Petri 網(wǎng)。對故障樹的重復事件，Petri 網(wǎng)中使用一個庫所表示。

C.求解關聯(lián)矩陣。文獻［2］詳細描述了求解關聯(lián)矩陣的算法，這里不再贅述。

D.由關聯(lián)矩陣求解系統(tǒng)最小割集，步驟如下:

a.找出關聯(lián)矩陣中只有“1”和“0”，沒有“-1”的行，則此行代表的庫所只有輸入庫所，沒有輸出庫所，則此行為對應事件頂庫所。

b.按次序?qū)ふ翼攷焖鶎械摹?”，并按列尋找到“-1”，此“-1”代表此行對應事件為頂庫所一個輸入事件，若有多個“-1”，說明同一變遷有多個輸入庫所，為“與”關系。

c.由(b)中找到的“-1”按行尋找“1”，若存在“1”說明是中間庫所。繼續(xù)按(b)的步驟循環(huán)查找，直到所在行沒有“1”為止。所在行沒有“1”，代表該行對應庫所為底庫所。若此行有多個“1”，說明對應的庫所對應多個變遷，為“或”關系。

d.按步驟(b)、步驟(c)繼續(xù)查找，直到查找到最底層庫所。

e.按照上面的“與”“或”關系，將底庫所展開，得到所有割集。

f.采用幾何化簡方法化簡割集，得到最小割集。

3 算法實例——ADS-B 解碼任務故障樹分析

我院研制的ADS-B 地面系統(tǒng)實現(xiàn)了ADS-B消息的接收與解碼，并將解碼后的消息送入主控。其中ADS-B 消息的解碼是本系統(tǒng)的核心單元。下面將使用這個任務驗證本文的算法，解碼采用協(xié)議為RTCA DO-260A。

該任務的主要功能為由特定的時間條件，或中斷條件接受FPGA 從外部接收的數(shù)據(jù)，對接收按飛行器分類處理，再對消息按消息類型分類，判斷是否是經(jīng)緯度消息，速度消息等，按照一定的解碼協(xié)議解碼，解碼后由一定的條件發(fā)送出去。

由系統(tǒng)分析，故障樹形式［7］如圖2 所示。根據(jù)以上算法，求出對應的Petri 網(wǎng)如圖3 所示。求出關聯(lián)矩陣如公式(1)所示。

圖2 解碼ADS-B 消息故障樹表示

圖3 對應的Petri 網(wǎng)表示

以下由關聯(lián)矩陣求故障樹最小割集:

a.搜索只有“1”和“0”沒有“-1”的行，此例中為17 行，得

b.對行16，15，14 分別找為1 的列，重復上述步驟，得到

c.重復上述步驟，依次向下分解，得到

將所有底庫所求出后，將以上算式逐級帶入，并整理后得:

因此，求出故障樹的最小割集為{P13}，{P12}，{P10}，{P9}，{P6，P5}，{P3}，{P4}，{P2，P1}。

通過以上實例可以看到，基于Petri 網(wǎng)關聯(lián)矩陣法能夠有效求解故障樹最小割集，算法清晰，易于計算機實現(xiàn)。同時適用于大型且結(jié)構比較復雜的系統(tǒng)。

4 結(jié)束語

故障樹轉(zhuǎn)換為Petri 網(wǎng)能夠有效的縮小軟件故障樹規(guī)模。故障樹與Petri 網(wǎng)的結(jié)合有效的利用了故障樹描述系統(tǒng)故障的能力以及Petri 網(wǎng)豐富的化簡和分析方法。文中使用Petri 網(wǎng)的關聯(lián)矩陣法求解故障樹的最小割集能夠較好應對大型復雜的系統(tǒng)，算法易實現(xiàn)。

［1］孫志安，裴曉黎，宋昕.軟件可靠性工程［M］.北京：北京航空航天大學出版社，2009.

［2］吳哲輝.Petri 網(wǎng)導論［M］.北京：機械工業(yè)出版社，2006.

［3］程鵬，雋吉昌，龔潔.基于故障樹的軟件分析技術(SFTA) 淺析［J］.中國新技術新產(chǎn)品，2009，21：35.

［4］秦興秋，邢昌風.一種基于Petri 網(wǎng)模型求解故障樹最小割集的算法［J］.計算機應用，2004，6，24：209-306.

［5］嚴傳龍.組合導航系統(tǒng)軟件可靠性分析與研究［D］.哈爾濱：哈爾濱工程大學，2008.