基于新型随机Petri网可靠性模型的网络安全分析

1、基于新型随机Petri网可靠性模型的网络安全分析张海晖，陈永锋 (西安建筑科技大学.西安710055)摘要：本文结合随机Petri网（SPN）的动态特性和蒙特卡罗仿真方法，对以往的随机Petri网模型进行了修改，将一种较为完善的SPN模型进行“对折”，提出了一种新型的基于可靠性模型的SPN建模，使模型显得更为简单明了，易于理解。并对SPN中变迁的激发规则进行了修改，使模型能更准确地模拟系统的动态运行。最后，本文根据仿真的结果分析了系统的可靠度和平均无故障时间MTBF。关键字：随机Petri网，蒙特卡罗仿真，可靠性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 前言开放性网络的发展，使企业内部网(Intranet)与外部网(Internet)的关联愈来愈紧密，在带来极大方便的同时，也面临着更多的安全

5、威胁。因此，有必要对网络的可靠性，特别是局域网或服务器的可靠性，进行分析研究。对于系统可靠性分析的研究，从系统是否可修复，分为不可修复系统的可靠性分析与可修复系统的可靠性分析1。目前影响较为广泛的可靠性分析方法主要有：事故树分析法(Fault Tree Analysis, FTA)2和状态空间法，但这两种方法都存在一些缺陷3。求故障树最小割集的分析是一个存在NP困难的问题4，其复杂度是底事件数量的指数倍；状态空间法虽然能对系统动态特性进行建模分析，但是对系统状态的数目较为敏感，当系统状态空间较大时，状态转移图的可读性下降，使得状态空间的确定和系统特性的分析困难。近年来，有人开始将随机Petri

6、网(Stochastic Petri Net, SPN)作为分析方法，用于系统可靠性分析5,6。由于一个SPN同构于一个连续时间马尔可夫链(Markov Chain)。马尔可夫过程为SPN提供坚实的数学基础。因此本文鉴于SPN的优良特性，将其用于对网络可靠性的分析。并对随机Petri网模型进行蒙特卡罗方法仿真。1 随机Petri网基本概念及定义在Petri网系统模型中，Petri网的库所(place)表示系统所处的一个状态；变迁(transition)表示系统从一个状态到另一个状态的行为变化。随机Petri网与普通Petri网的区别在于：在每个变迁的可实施与实施之间联系一个随机的延迟时间7，这

7、种类型的Petri网有更强的模拟能力。定义1 一般地，一个随机Petri网是六元组：SPN=(P,T,F,W,m0,)其中P,T,F,W,和m0同基本Petri网中的意义相同，即：P=(p1,p2,.,pm)是库所的有限集合，pi表示系统所处的不同状态，其中i=1,2m；T=(t1,t2,.,tn)是变迁的有限集合，tj表示系统的行为，其中j=1,2n；是弧的有限集合；W:FN+是弧权函数；M0=(m01,m02,.,m0m)是初始标识，表示系统的初始状态；另外，=1,2,.,n是变迁平均实施速率集合。考虑到计算机网络安全的特性，以及便于对系统进行分析，我们在此对用SPN模拟的系统做出以下两个

8、假设：（）组成系统的各子状态及系统本身的状态都只有正常或失效两种状态；（）各子状态相互独立，即不考虑子状态之间的相关性。2 对随机Petri网模型的可靠性分析对随机Petri网模型的可靠性分析，不同于传统的系统可靠性分析，传统的可靠性框图、故障树等着眼于任务行为不会随着时间变化的系统，这些方法是一种静态的可靠性分析。静态可靠性分析对于系统的动态可靠性行为，如序列相关事件、动态冗余、人的因素等存在一定困难8。由于SPN本身的时间特性，可以动态地模拟系统的行为状态变化。因此，我们称这种随着系统时间的推进，动态分析系统可靠性的模型为动态可靠性模型。2.1 可靠性定义与基本系统可靠性模型产品的可靠度是

9、指：产品在规定条件下和规定时间t内，完成规定功能的概率。根据可靠性的定义，事件T>t的概率是单元在时刻t时的可靠性。即单元在(0,t)内不发生失效的概率。设R(t)是可靠性函数，则有：R(t)=PT>t (1)这里，P表示概率，事件Tt是事件T>t的补，它的概率常常被称作累积分布函数，用F(t)来表示，则有：F(t)=PTt=1-R(t) (2)其物理意义是单元在时间间隔(0,t)内失效的概率。另一个可靠性函数是概率密度函数，记为f(t)，定义为：f(t)=dF(t)/dt=-dR(t)/dt (3)其物理意义是在时间间隔(t,t+dt)内的单位时间内发生失效的概率。已知一个

10、单元在时刻t是工作的，它在时间间隔(t,t+dt)内的单位时间内发生失效的概率称为单元在时刻t的失效率(或风险率)，通常计作为r(t)(或h(t)，有： (4)系统可靠性模型中，最常用到的是串联模型和并联模型。（1）串联模型。串联系统的n个元件必须全部工作，系统才会正常工作，任一元件的故障都会导致系统故障。其可靠性框图如图2.1所示：图2.1 串联系统可靠性框图串联系统可靠性函数Rs(t)等于所有元件可以同时正常工作到时间t的概率。即Rs(t)为所有元件可靠性函数Ri(t)之乘积： (5)其累积分布函数为： (6)式(5)表明，串联系统中元件越多，则系统的可靠性越低。（2）并联模型。并联系统中

11、的n个元件都发生故障时系统才发生故障，只要有任何一个元件工作，系统就处在工作状态。因此并联系统可以提高系统可靠性。并联系统的可靠性逻辑框图如图2.2所示：图2.2 并联模型的可靠性框图2.2 基于SPN建模的可靠性分析为增强Petri网模型的描述能力，人们对SPN进行了扩充：（1）增加禁止弧：禁止弧由库所到变迁，当库所中含有禁止弧上所标注数量的托肯时，该变迁将被禁止实施；（2）增加瞬时变迁，瞬时变迁的实施延时为零；（3）当下一个标识下有多个可实施瞬时变迁时，定义一个随机开关，以确定它们之间实施概率的选择。文献8中比较完整地建立了串联系统和并联系统的随机Petri网模型，在此模型中将元件的工作状

12、态和故障状态分别用up和dn此模型中的串联系统和并联系统SPN模型如图2.3中(a)、(b)所示： (a) 串联系统 (b) 并联系统图2.3 文献8中的SPN模型图2.3中的模型可以很好地描述串联系统和并联系统的动态工作情况，但是此模型中有大量的自反馈弧和禁止弧，且将元件的工件状态和故障状态表示为不同的库所，使得模型看起来较为复杂，不易理解。在分析了此模型后，发现此模型有一定的对称性，左边是up状态，右边是dn状态，因此，我们可试图将此模型进行“对折”，使其简化。简化之后的串联系统和并联系统模型如图2.4中(a)、(b)所示： 图2.4 新型SPN模型在图2.4所示的新型SPN模型中，为了更

13、加准确地模拟系统的运行，我们对原有模型做了以下修改：（1）每一个库所（元件）上都对应有两个变迁，一个是元件从工作到故障的失效变迁ti，另一个是元件从故障到恢复工作的修复变迁，变迁ti和分别对应两个随机的延迟时间（服从不同分布的两个随机变量）；（2）库所（元件）只有两种状态，工作状态和故障状态，并且规定当元件处于工作状态时pi=1，当元件处于故障状态时pi=-1；（3）增加四种新的弧：正激发弧，从库所（元件）Pi到失效变迁ti，当pi=1时，此弧有效；负激发弧，从库所（元件）Pi到修复变迁，当pi=-1时，此弧有效；正自反馈弧，从修复变迁到库所（元件）Pi，当激发，此弧有效；负自反馈弧，从失效变

14、迁ti到库所（元件）Pi，当ti激发，此弧有效。（4）在新的模型中，变迁的激发规则有所变化： 当pi=1，且系统运行时间ts>ti时（用ti表示变迁ti的随机延迟），正激发弧此时有效，同时失效变迁ti激发，随即负自反馈弧有效，它将反馈值-1至库所Pi，Pi将处于失效状态。即失效变迁ti的激发将使Pi由工作状态变为失效状态。 当pi=-1，且系统运行时间ts>时（用表示变迁的随机延迟），负激发弧此时有效，同时修复变迁激发，随即正自反馈弧有效，它将反馈值1至库所Pi，Pi将处于工作状态。即修复变迁的激发将使Pi由失效状态变为工作状态。 串联系统中导致系统状态变化的瞬时变迁T的激发规则如

15、下：当min(p1, p2, pn)=1时，瞬时变迁T立即激发，此时PSys=1，系统将处于工作状态，由于抑制弧的存在，变迁T不再激发，直到min(p1, p2, pn)=-1时，瞬时变迁T将再次激发，此时PSys=-1，系统处于故障状态，由于抑制弧的存在，变迁T不再激发，直至再次min(p1, p2, pn)=1时 并联系统中导致系统状态变化的瞬时变迁Ti的激发规则如下：当pi=1时，瞬时变迁Ti立即激发，此时PSys=1，系统将处于工作状态，由于抑制弧的存在，变迁Tj(j=1,2,n，ji)不再激发，直至任一pi=-1(i=1,2,n)时，瞬时变迁Ti将再次激发，此时PSys=-1，系统处

16、于故障状态，由于抑制弧的存在，变迁Tj(j=1,2,n，ji)不再激发，直至再次pi=1(i=1,2,n)时经过修改与优化之后的新型SPN模型能更准确地模拟系统动态的运行的过程，并使模型显得更为简单明了。之前已叙述，SPN与马尔可夫链同构，但是基于Markov理论的直接求解法难以求解复杂系可靠性指标。这是因为，一方面随着元件数目的增加，系的状态空间急剧增加。利用Markov所得的大规模矩阵，不易求解。因此复杂系统的可靠性指标一般采用仿真方法实现。3 新型SPN模型的蒙特卡罗仿真3.1 蒙特卡罗仿真的基本流程蒙特卡罗方法采用随机模拟的方法，它是一种非常有用的方法，特别是当一个系统的输入变量较多，

17、且比较复杂的情况下，用来建立系统输出的随机模型时特别方便，因此，它被广泛地应用于解决工程实际问题。蒙特卡罗仿真的基本流程如下：（1）系统建模。根据系统的目标和结构构建一个合理的数学逻辑模型。建模型的方法有多种，在本文中对系统的动态变化建立系统的SPN模型。（2）确定随机变量及其分布，在可靠性仿真中，元件的寿命分布和维修时间分布是仿真的基础，这些分布函数的获得可以通过以往的经验及大量统计来完成。（3）确定随机变量的分布后，选择适当的随机变量抽样方法，实现对已知概率分布抽样。即通过产生随机数的方式进行对已知概率分布的抽样。这是蒙特卡罗仿真最为主要的一步，也是蒙特卡罗仿真思想的体现。（4）统计计算。

18、得到仿真数据后，对系统及元件进行可靠性指标分析。3.2 基于新型SPN模型的蒙特卡罗仿真若网络安全系统S的各部分状态的变化彼此独立，各部分状态是随机变化的。设SPN=(P,T,F,W,m0,)是一特定网络系统S的随机Petri网模型，其中P是网络系统S各安全部分状态（只有工作和故障两种状态）的集合，T是引起网络系统S的各部分状态变化的行为的集合，pi由工作（故障）状态经过失效变迁ti（修复变迁）变为故障（工作）状态所经历的时间服从不同分布。由于系统S各部分状态的变化是随机的，即各部分失效率和修复率为常数，对于这样的特性，工程应用中一般认为服从指数分布。因此，可以认为失效变迁ti和修复变迁服从参

19、数不同的指数分布。设失效变迁ti服从参数为i的指数分布，其失效概率密度函数表示为：设修复变迁服从参数为的指数分布，其失效概率密度函数表示为：对于失效变迁ti和修复变迁服从的指数分布的伪随机数序列（抽样序列），通过反函数法直接抽样8。具体过程为：a）抽样产生均匀分布随机数rU(0,1)；b）根据产生的均匀分布随机数r产生服从指数分布的随机数，可以利用下式： (7)那么，式(7)中X即服从参数为的指数分布。下面我们给出基于新型SPN模型的蒙特卡罗仿真的算法，在给出算法之前，先对算法用到的参数进行定义：M：仿真总次数；Tmax：每次仿真运行仿真时间；t：当前仿真次数；m：当前累积仿真次数；Mj：导致

20、网络系统S处于不安全的状态；Pj：状态Mj的稳态概率；Tf：可激发的延时变迁集合；tf：延时变迁抽样时间序列；新型SPN模型的蒙特卡罗仿真具体算法步骤如下：Step1 初始化，设定仿真总次数、每次仿真的结束时间，令m=0，设定SPN库所集初始状态M0；Step2 令运行时间t=0，m=m+1，判断m>M，如成立则转Step7；Step3 确定可以激发的延时变迁集Tf，依据式(7)抽样得到各变迁的延时时间序列tk，并对时间进行排序，得到最小值tmin，最小时间对应的变迁为T；Step4 运行时间t=t+tmin，依据2.2节中所述的变迁激发规则，激发T及可激发的瞬时变迁，将其它对应的变迁时

21、间减去tmin。Step5 判断T激发后的系统状态，变迁和库所的状态，并进行数据记录及参数更新；Step6 如果t>Tmax，则跳转至Step2，否则跳转至Step3；Step7 计算各种可靠性指标，算法结束。3.3 基于SPN模型蒙特卡罗仿真结果的可靠性分析仿真结束后，根据得到的仿真数据，便可以进行系统的可靠性分析。下面从系统的可靠度、平均无故障时间MTBF两个方面分析仿真结果的可靠性。从仿真数据得到状态Mj的总持续时间为rTj，状态Mj出现的总次数为nj，这样的状态Mj共有s个，即j=1,2,.,s。那么网络系统S的可靠度为： (8)平均无故障时间MTBF为： (9)至此，完成了基于SPN模型蒙特卡罗仿真的可靠性分析，利用随机Petri网和蒙特卡罗方法完成了对网络系统可靠性的建模和可靠性分析，得出了系统的可靠度和MTBF的仿真值。为较为复杂规模较大的系统，提供一种可靠性分析的方案。4 结论本文结合随机Petri网的动态特性和蒙特卡罗仿真方法，对以往的随机Petri网模型进行了修改，提出了一种新型的SPN模型，使模型显得更为简单明了，易于理解。由于蒙特卡罗方法良好的仿真能力，使得利用SPN对复杂系统建