基于新型隨機(jī)Petri網(wǎng)可靠性模型的網(wǎng)絡(luò)安全分析

1、基于新型隨機(jī)Petri網(wǎng)可靠性模型的網(wǎng)絡(luò)安全分析張海暉，陳永鋒 (西安建筑科技大學(xué).西安710055)摘要：本文結(jié)合隨機(jī)Petri網(wǎng)（SPN）的動(dòng)態(tài)特性和蒙特卡羅仿真方法，對(duì)以往的隨機(jī)Petri網(wǎng)模型進(jìn)行了修改，將一種較為完善的SPN模型進(jìn)行“對(duì)折”，提出了一種新型的基于可靠性模型的SPN建模，使模型顯得更為簡(jiǎn)單明了，易于理解。并對(duì)SPN中變遷的激發(fā)規(guī)則進(jìn)行了修改，使模型能更準(zhǔn)確地模擬系統(tǒng)的動(dòng)態(tài)運(yùn)行。最后，本文根據(jù)仿真的結(jié)果分析了系統(tǒng)的可靠度和平均無故障時(shí)間MTBF。關(guān)鍵字：隨機(jī)Petri網(wǎng)，蒙特卡羅仿真，可靠性Network Security Analysis Based on Reliab

2、ility Model of New Stochastic Petri NetZhang Hai-hui ,Chen Yong-feng (School of Management, Xian Universityof Architecture and Technology, Xian Shaanxi 710055)Abstract: The paper combines the dynamic characteristic of Stochastic Petri Net (SPN) and Monte Carlo simulation to modify the past stochasti

3、c Petri Net. And through “fold” a better SPN model, this paper puts forward a new kind of SPN based on Reliability model, which makes the new model more simple and more easily to understand. In this paper, the fire rules of SPN are also modified, and these new rules ensure the model simulating the s

4、ystem dynamic running more exactly. Finally, this paper analyses the reliability degree and Mean Time before Failure (MTBF) of the system by simulation results.Key words: Stochastic Petri Net, Monte Carlo simulation, Reliability0 前言開放性網(wǎng)絡(luò)的發(fā)展，使企業(yè)內(nèi)部網(wǎng)(Intranet)與外部網(wǎng)(Internet)的關(guān)聯(lián)愈來愈緊密，在帶來極大方便的同時(shí)，也面臨著更多的安全

5、威脅。因此，有必要對(duì)網(wǎng)絡(luò)的可靠性，特別是局域網(wǎng)或服務(wù)器的可靠性，進(jìn)行分析研究。對(duì)于系統(tǒng)可靠性分析的研究，從系統(tǒng)是否可修復(fù)，分為不可修復(fù)系統(tǒng)的可靠性分析與可修復(fù)系統(tǒng)的可靠性分析1。目前影響較為廣泛的可靠性分析方法主要有：事故樹分析法(Fault Tree Analysis, FTA)2和狀態(tài)空間法，但這兩種方法都存在一些缺陷3。求故障樹最小割集的分析是一個(gè)存在NP困難的問題4，其復(fù)雜度是底事件數(shù)量的指數(shù)倍；狀態(tài)空間法雖然能對(duì)系統(tǒng)動(dòng)態(tài)特性進(jìn)行建模分析，但是對(duì)系統(tǒng)狀態(tài)的數(shù)目較為敏感，當(dāng)系統(tǒng)狀態(tài)空間較大時(shí)，狀態(tài)轉(zhuǎn)移圖的可讀性下降，使得狀態(tài)空間的確定和系統(tǒng)特性的分析困難。近年來，有人開始將隨機(jī)Petri

6、網(wǎng)(Stochastic Petri Net, SPN)作為分析方法，用于系統(tǒng)可靠性分析5,6。由于一個(gè)SPN同構(gòu)于一個(gè)連續(xù)時(shí)間馬爾可夫鏈(Markov Chain)。馬爾可夫過程為SPN提供堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)。因此本文鑒于SPN的優(yōu)良特性，將其用于對(duì)網(wǎng)絡(luò)可靠性的分析。并對(duì)隨機(jī)Petri網(wǎng)模型進(jìn)行蒙特卡羅方法仿真。1 隨機(jī)Petri網(wǎng)基本概念及定義在Petri網(wǎng)系統(tǒng)模型中，Petri網(wǎng)的庫所(place)表示系統(tǒng)所處的一個(gè)狀態(tài)；變遷(transition)表示系統(tǒng)從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的行為變化。隨機(jī)Petri網(wǎng)與普通Petri網(wǎng)的區(qū)別在于：在每個(gè)變遷的可實(shí)施與實(shí)施之間聯(lián)系一個(gè)隨機(jī)的延遲時(shí)間7，這

7、種類型的Petri網(wǎng)有更強(qiáng)的模擬能力。定義1 一般地，一個(gè)隨機(jī)Petri網(wǎng)是六元組：SPN=(P,T,F,W,m0,)其中P,T,F,W,和m0同基本Petri網(wǎng)中的意義相同，即：P=(p1,p2,.,pm)是庫所的有限集合，pi表示系統(tǒng)所處的不同狀態(tài)，其中i=1,2m；T=(t1,t2,.,tn)是變遷的有限集合，tj表示系統(tǒng)的行為，其中j=1,2n；是弧的有限集合；W:FN+是弧權(quán)函數(shù)；M0=(m01,m02,.,m0m)是初始標(biāo)識(shí)，表示系統(tǒng)的初始狀態(tài)；另外，=1,2,.,n是變遷平均實(shí)施速率集合?？紤]到計(jì)算機(jī)網(wǎng)絡(luò)安全的特性，以及便于對(duì)系統(tǒng)進(jìn)行分析，我們?cè)诖藢?duì)用SPN模擬的系統(tǒng)做出以下兩個(gè)

8、假設(shè)：（）組成系統(tǒng)的各子狀態(tài)及系統(tǒng)本身的狀態(tài)都只有正?；蚴煞N狀態(tài)；（）各子狀態(tài)相互獨(dú)立，即不考慮子狀態(tài)之間的相關(guān)性。2 對(duì)隨機(jī)Petri網(wǎng)模型的可靠性分析對(duì)隨機(jī)Petri網(wǎng)模型的可靠性分析，不同于傳統(tǒng)的系統(tǒng)可靠性分析，傳統(tǒng)的可靠性框圖、故障樹等著眼于任務(wù)行為不會(huì)隨著時(shí)間變化的系統(tǒng)，這些方法是一種靜態(tài)的可靠性分析。靜態(tài)可靠性分析對(duì)于系統(tǒng)的動(dòng)態(tài)可靠性行為，如序列相關(guān)事件、動(dòng)態(tài)冗余、人的因素等存在一定困難8。由于SPN本身的時(shí)間特性，可以動(dòng)態(tài)地模擬系統(tǒng)的行為狀態(tài)變化。因此，我們稱這種隨著系統(tǒng)時(shí)間的推進(jìn)，動(dòng)態(tài)分析系統(tǒng)可靠性的模型為動(dòng)態(tài)可靠性模型。2.1 可靠性定義與基本系統(tǒng)可靠性模型產(chǎn)品的可靠度是

9、指：產(chǎn)品在規(guī)定條件下和規(guī)定時(shí)間t內(nèi)，完成規(guī)定功能的概率。根據(jù)可靠性的定義，事件T>t的概率是單元在時(shí)刻t時(shí)的可靠性。即單元在(0,t)內(nèi)不發(fā)生失效的概率。設(shè)R(t)是可靠性函數(shù)，則有：R(t)=PT>t (1)這里，P表示概率，事件Tt是事件T>t的補(bǔ)，它的概率常常被稱作累積分布函數(shù)，用F(t)來表示，則有：F(t)=PTt=1-R(t) (2)其物理意義是單元在時(shí)間間隔(0,t)內(nèi)失效的概率。另一個(gè)可靠性函數(shù)是概率密度函數(shù)，記為f(t)，定義為：f(t)=dF(t)/dt=-dR(t)/dt (3)其物理意義是在時(shí)間間隔(t,t+dt)內(nèi)的單位時(shí)間內(nèi)發(fā)生失效的概率。已知一個(gè)

10、單元在時(shí)刻t是工作的，它在時(shí)間間隔(t,t+dt)內(nèi)的單位時(shí)間內(nèi)發(fā)生失效的概率稱為單元在時(shí)刻t的失效率(或風(fēng)險(xiǎn)率)，通常計(jì)作為r(t)(或h(t)，有： (4)系統(tǒng)可靠性模型中，最常用到的是串聯(lián)模型和并聯(lián)模型。（1）串聯(lián)模型。串聯(lián)系統(tǒng)的n個(gè)元件必須全部工作，系統(tǒng)才會(huì)正常工作，任一元件的故障都會(huì)導(dǎo)致系統(tǒng)故障。其可靠性框圖如圖2.1所示：圖2.1 串聯(lián)系統(tǒng)可靠性框圖串聯(lián)系統(tǒng)可靠性函數(shù)Rs(t)等于所有元件可以同時(shí)正常工作到時(shí)間t的概率。即Rs(t)為所有元件可靠性函數(shù)Ri(t)之乘積： (5)其累積分布函數(shù)為： (6)式(5)表明，串聯(lián)系統(tǒng)中元件越多，則系統(tǒng)的可靠性越低。（2）并聯(lián)模型。并聯(lián)系統(tǒng)中

11、的n個(gè)元件都發(fā)生故障時(shí)系統(tǒng)才發(fā)生故障，只要有任何一個(gè)元件工作，系統(tǒng)就處在工作狀態(tài)。因此并聯(lián)系統(tǒng)可以提高系統(tǒng)可靠性。并聯(lián)系統(tǒng)的可靠性邏輯框圖如圖2.2所示：圖2.2 并聯(lián)模型的可靠性框圖2.2 基于SPN建模的可靠性分析為增強(qiáng)Petri網(wǎng)模型的描述能力，人們對(duì)SPN進(jìn)行了擴(kuò)充：（1）增加禁止?。航够∮蓭焖阶冞w，當(dāng)庫所中含有禁止弧上所標(biāo)注數(shù)量的托肯時(shí)，該變遷將被禁止實(shí)施；（2）增加瞬時(shí)變遷，瞬時(shí)變遷的實(shí)施延時(shí)為零；（3）當(dāng)下一個(gè)標(biāo)識(shí)下有多個(gè)可實(shí)施瞬時(shí)變遷時(shí)，定義一個(gè)隨機(jī)開關(guān)，以確定它們之間實(shí)施概率的選擇。文獻(xiàn)8中比較完整地建立了串聯(lián)系統(tǒng)和并聯(lián)系統(tǒng)的隨機(jī)Petri網(wǎng)模型，在此模型中將元件的工作狀

12、態(tài)和故障狀態(tài)分別用up和dn表示，系統(tǒng)的工作狀態(tài)和故障狀態(tài)分別用Sys.up和Sys.dn表示。此模型中的串聯(lián)系統(tǒng)和并聯(lián)系統(tǒng)SPN模型如圖2.3中(a)、(b)所示： (a) 串聯(lián)系統(tǒng) (b) 并聯(lián)系統(tǒng)圖2.3 文獻(xiàn)8中的SPN模型圖2.3中的模型可以很好地描述串聯(lián)系統(tǒng)和并聯(lián)系統(tǒng)的動(dòng)態(tài)工作情況，但是此模型中有大量的自反饋弧和禁止弧，且將元件的工件狀態(tài)和故障狀態(tài)表示為不同的庫所，使得模型看起來較為復(fù)雜，不易理解。在分析了此模型后，發(fā)現(xiàn)此模型有一定的對(duì)稱性，左邊是up狀態(tài)，右邊是dn狀態(tài)，因此，我們可試圖將此模型進(jìn)行“對(duì)折”，使其簡(jiǎn)化。簡(jiǎn)化之后的串聯(lián)系統(tǒng)和并聯(lián)系統(tǒng)模型如圖2.4中(a)、(b)所示

13、： 圖2.4 新型SPN模型在圖2.4所示的新型SPN模型中，為了更加準(zhǔn)確地模擬系統(tǒng)的運(yùn)行，我們對(duì)原有模型做了以下修改：（1）每一個(gè)庫所（元件）上都對(duì)應(yīng)有兩個(gè)變遷，一個(gè)是元件從工作到故障的失效變遷ti，另一個(gè)是元件從故障到恢復(fù)工作的修復(fù)變遷，變遷ti和分別對(duì)應(yīng)兩個(gè)隨機(jī)的延遲時(shí)間（服從不同分布的兩個(gè)隨機(jī)變量）；（2）庫所（元件）只有兩種狀態(tài)，工作狀態(tài)和故障狀態(tài)，并且規(guī)定當(dāng)元件處于工作狀態(tài)時(shí)pi=1，當(dāng)元件處于故障狀態(tài)時(shí)pi=-1；（3）增加四種新的?。赫ぐl(fā)弧，從庫所（元件）Pi到失效變遷ti，當(dāng)pi=1時(shí)，此弧有效；負(fù)激發(fā)弧，從庫所（元件）Pi到修復(fù)變遷，當(dāng)pi=-1時(shí)，此弧有效；正自反饋弧，

14、從修復(fù)變遷到庫所（元件）Pi，當(dāng)激發(fā)，此弧有效；負(fù)自反饋弧，從失效變遷ti到庫所（元件）Pi，當(dāng)ti激發(fā)，此弧有效。（4）在新的模型中，變遷的激發(fā)規(guī)則有所變化： 當(dāng)pi=1，且系統(tǒng)運(yùn)行時(shí)間ts>ti時(shí)（用ti表示變遷ti的隨機(jī)延遲），正激發(fā)弧此時(shí)有效，同時(shí)失效變遷ti激發(fā)，隨即負(fù)自反饋弧有效，它將反饋值-1至庫所Pi，Pi將處于失效狀態(tài)。即失效變遷ti的激發(fā)將使Pi由工作狀態(tài)變?yōu)槭顟B(tài)。 當(dāng)pi=-1，且系統(tǒng)運(yùn)行時(shí)間ts>時(shí)（用表示變遷的隨機(jī)延遲），負(fù)激發(fā)弧此時(shí)有效，同時(shí)修復(fù)變遷激發(fā)，隨即正自反饋弧有效，它將反饋值1至庫所Pi，Pi將處于工作狀態(tài)。即修復(fù)變遷的激發(fā)將使Pi由失效狀

15、態(tài)變?yōu)楣ぷ鳡顟B(tài)。 串聯(lián)系統(tǒng)中導(dǎo)致系統(tǒng)狀態(tài)變化的瞬時(shí)變遷T的激發(fā)規(guī)則如下：當(dāng)min(p1, p2, pn)=1時(shí)，瞬時(shí)變遷T立即激發(fā)，此時(shí)PSys=1，系統(tǒng)將處于工作狀態(tài)，由于抑制弧的存在，變遷T不再激發(fā)，直到min(p1, p2, pn)=-1時(shí)，瞬時(shí)變遷T將再次激發(fā)，此時(shí)PSys=-1，系統(tǒng)處于故障狀態(tài)，由于抑制弧的存在，變遷T不再激發(fā)，直至再次min(p1, p2, pn)=1時(shí) 并聯(lián)系統(tǒng)中導(dǎo)致系統(tǒng)狀態(tài)變化的瞬時(shí)變遷Ti的激發(fā)規(guī)則如下：當(dāng)pi=1時(shí)，瞬時(shí)變遷Ti立即激發(fā)，此時(shí)PSys=1，系統(tǒng)將處于工作狀態(tài)，由于抑制弧的存在，變遷Tj(j=1,2,n，ji)不再激發(fā)，直至任一pi=-1(i

16、=1,2,n)時(shí)，瞬時(shí)變遷Ti將再次激發(fā)，此時(shí)PSys=-1，系統(tǒng)處于故障狀態(tài)，由于抑制弧的存在，變遷Tj(j=1,2,n，ji)不再激發(fā)，直至再次pi=1(i=1,2,n)時(shí)經(jīng)過修改與優(yōu)化之后的新型SPN模型能更準(zhǔn)確地模擬系統(tǒng)動(dòng)態(tài)的運(yùn)行的過程，并使模型顯得更為簡(jiǎn)單明了。之前已敘述，SPN與馬爾可夫鏈同構(gòu)，但是基于Markov理論的直接求解法難以求解復(fù)雜系可靠性指標(biāo)。這是因?yàn)?，一方面隨著元件數(shù)目的增加，系的狀態(tài)空間急劇增加。利用Markov所得的大規(guī)模矩陣，不易求解。因此復(fù)雜系統(tǒng)的可靠性指標(biāo)一般采用仿真方法實(shí)現(xiàn)。3 新型SPN模型的蒙特卡羅仿真3.1 蒙特卡羅仿真的基本流程蒙特卡羅方法采用隨機(jī)

17、模擬的方法，它是一種非常有用的方法，特別是當(dāng)一個(gè)系統(tǒng)的輸入變量較多，且比較復(fù)雜的情況下，用來建立系統(tǒng)輸出的隨機(jī)模型時(shí)特別方便，因此，它被廣泛地應(yīng)用于解決工程實(shí)際問題。蒙特卡羅仿真的基本流程如下：（1）系統(tǒng)建模。根據(jù)系統(tǒng)的目標(biāo)和結(jié)構(gòu)構(gòu)建一個(gè)合理的數(shù)學(xué)邏輯模型。建模型的方法有多種，在本文中對(duì)系統(tǒng)的動(dòng)態(tài)變化建立系統(tǒng)的SPN模型。（2）確定隨機(jī)變量及其分布，在可靠性仿真中，元件的壽命分布和維修時(shí)間分布是仿真的基礎(chǔ)，這些分布函數(shù)的獲得可以通過以往的經(jīng)驗(yàn)及大量統(tǒng)計(jì)來完成。（3）確定隨機(jī)變量的分布后，選擇適當(dāng)?shù)碾S機(jī)變量抽樣方法，實(shí)現(xiàn)對(duì)已知概率分布抽樣。即通過產(chǎn)生隨機(jī)數(shù)的方式進(jìn)行對(duì)已知概率分布的抽樣。這是蒙特

18、卡羅仿真最為主要的一步，也是蒙特卡羅仿真思想的體現(xiàn)。（4）統(tǒng)計(jì)計(jì)算。得到仿真數(shù)據(jù)后，對(duì)系統(tǒng)及元件進(jìn)行可靠性指標(biāo)分析。3.2 基于新型SPN模型的蒙特卡羅仿真若網(wǎng)絡(luò)安全系統(tǒng)S的各部分狀態(tài)的變化彼此獨(dú)立，各部分狀態(tài)是隨機(jī)變化的。設(shè)SPN=(P,T,F,W,m0,)是一特定網(wǎng)絡(luò)系統(tǒng)S的隨機(jī)Petri網(wǎng)模型，其中P是網(wǎng)絡(luò)系統(tǒng)S各安全部分狀態(tài)（只有工作和故障兩種狀態(tài)）的集合，T是引起網(wǎng)絡(luò)系統(tǒng)S的各部分狀態(tài)變化的行為的集合，pi由工作（故障）狀態(tài)經(jīng)過失效變遷ti（修復(fù)變遷）變?yōu)楣收希üぷ鳎顟B(tài)所經(jīng)歷的時(shí)間服從不同分布。由于系統(tǒng)S各部分狀態(tài)的變化是隨機(jī)的，即各部分失效率和修復(fù)率為常數(shù)，對(duì)于這樣的特性，工程應(yīng)

19、用中一般認(rèn)為服從指數(shù)分布。因此，可以認(rèn)為失效變遷ti和修復(fù)變遷服從參數(shù)不同的指數(shù)分布。設(shè)失效變遷ti服從參數(shù)為i的指數(shù)分布，其失效概率密度函數(shù)表示為：設(shè)修復(fù)變遷服從參數(shù)為的指數(shù)分布，其失效概率密度函數(shù)表示為：對(duì)于失效變遷ti和修復(fù)變遷服從的指數(shù)分布的偽隨機(jī)數(shù)序列（抽樣序列），通過反函數(shù)法直接抽樣8。具體過程為：a）抽樣產(chǎn)生均勻分布隨機(jī)數(shù)rU(0,1)；b）根據(jù)產(chǎn)生的均勻分布隨機(jī)數(shù)r產(chǎn)生服從指數(shù)分布的隨機(jī)數(shù)，可以利用下式： (7)那么，式(7)中X即服從參數(shù)為的指數(shù)分布。下面我們給出基于新型SPN模型的蒙特卡羅仿真的算法，在給出算法之前，先對(duì)算法用到的參數(shù)進(jìn)行定義：M：仿真總次數(shù)；Tmax：每次

20、仿真運(yùn)行仿真時(shí)間；t：當(dāng)前仿真次數(shù)；m：當(dāng)前累積仿真次數(shù)；Mj：導(dǎo)致網(wǎng)絡(luò)系統(tǒng)S處于不安全的狀態(tài)；Pj：狀態(tài)Mj的穩(wěn)態(tài)概率；Tf：可激發(fā)的延時(shí)變遷集合；tf：延時(shí)變遷抽樣時(shí)間序列；新型SPN模型的蒙特卡羅仿真具體算法步驟如下：Step1 初始化，設(shè)定仿真總次數(shù)、每次仿真的結(jié)束時(shí)間，令m=0，設(shè)定SPN庫所集初始狀態(tài)M0；Step2 令運(yùn)行時(shí)間t=0，m=m+1，判斷m>M，如成立則轉(zhuǎn)Step7；Step3 確定可以激發(fā)的延時(shí)變遷集Tf，依據(jù)式(7)抽樣得到各變遷的延時(shí)時(shí)間序列tk，并對(duì)時(shí)間進(jìn)行排序，得到最小值tmin，最小時(shí)間對(duì)應(yīng)的變遷為T；Step4 運(yùn)行時(shí)間t=t+tmin，依據(jù)2.2

21、節(jié)中所述的變遷激發(fā)規(guī)則，激發(fā)T及可激發(fā)的瞬時(shí)變遷，將其它對(duì)應(yīng)的變遷時(shí)間減去tmin。Step5 判斷T激發(fā)后的系統(tǒng)狀態(tài)，變遷和庫所的狀態(tài)，并進(jìn)行數(shù)據(jù)記錄及參數(shù)更新；Step6 如果t>Tmax，則跳轉(zhuǎn)至Step2，否則跳轉(zhuǎn)至Step3；Step7 計(jì)算各種可靠性指標(biāo)，算法結(jié)束。3.3 基于SPN模型蒙特卡羅仿真結(jié)果的可靠性分析仿真結(jié)束后，根據(jù)得到的仿真數(shù)據(jù)，便可以進(jìn)行系統(tǒng)的可靠性分析。下面從系統(tǒng)的可靠度、平均無故障時(shí)間MTBF兩個(gè)方面分析仿真結(jié)果的可靠性。從仿真數(shù)據(jù)得到狀態(tài)Mj的總持續(xù)時(shí)間為rTj，狀態(tài)Mj出現(xiàn)的總次數(shù)為nj，這樣的狀態(tài)Mj共有s個(gè)，即j=1,2,.,s。那么網(wǎng)絡(luò)系統(tǒng)S的可靠度為： (8)平均無故障時(shí)間MTBF為： (9)至此，完成了基于SPN模型蒙特卡羅仿真的可靠性分析，利用隨機(jī)Petri網(wǎng)和蒙特卡羅方法完成了對(duì)網(wǎng)絡(luò)系統(tǒng)可靠性的建模和可靠性分析，得出了系統(tǒng)的可靠度和MTBF的仿真值。為較為復(fù)雜規(guī)模較大的系統(tǒng)，提供一種可靠性分析的方案。4 結(jié)論本文結(jié)合隨機(jī)Petri網(wǎng)的動(dòng)態(tài)特性和蒙特卡羅仿真方法，對(duì)以往的隨機(jī)Petri網(wǎng)模型進(jìn)行了修改，提出了一種新型的SPN模型，使模型顯得更為簡(jiǎn)單明了，易于理解。由于蒙特卡羅方法良好的仿真能力，使得利用SPN對(duì)復(fù)雜