林 紅 楊瀚程

(電子科技大學(xué) 成都 611731)

0 引言

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

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

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

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

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

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

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

算法具體步驟如下:

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

圖1 故障樹表示與Petri 網(wǎng)表示對(duì)應(yīng)關(guān)系

B.求出故障樹對(duì)應(yīng)的Petri 網(wǎng)。對(duì)已形成的故障樹，與門采用一個(gè)變遷表示，或門采用多個(gè)變遷表示，事件用庫(kù)所表示，添加流關(guān)系，形成Petri 網(wǎng)。對(duì)故障樹的重復(fù)事件，Petri 網(wǎng)中使用一個(gè)庫(kù)所表示。

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

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

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

b.按次序?qū)ふ翼攷?kù)所對(duì)應(yīng)行的“1”，并按列尋找到“-1”，此“-1”代表此行對(duì)應(yīng)事件為頂庫(kù)所一個(gè)輸入事件，若有多個(gè)“-1”，說明同一變遷有多個(gè)輸入庫(kù)所，為“與”關(guān)系。

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

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

e.按照上面的“與”“或”關(guān)系，將底庫(kù)所展開，得到所有割集。

f.采用幾何化簡(jiǎn)方法化簡(jiǎn)割集，得到最小割集。

3 算法實(shí)例——ADS-B 解碼任務(wù)故障樹分析

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

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

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

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

圖3 對(duì)應(yīng)的Petri 網(wǎng)表示

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

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

b.對(duì)行16，15，14 分別找為1 的列，重復(fù)上述步驟，得到

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

將所有底庫(kù)所求出后，將以上算式逐級(jí)帶入，并整理后得:

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

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

4 結(jié)束語

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

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

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

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

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

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