房丙午,黃志球,李　勇,王　勇

(1.南京航空航天大學計算機科學與技術(shù)學院,江蘇南京 210016;2.安徽財貿(mào)職業(yè)學院電子信息系,安徽合肥 230061)

?

基于貝葉斯網(wǎng)絡(luò)的復雜系統(tǒng)動態(tài)故障樹定量分析方法

房丙午1,2,黃志球1,李勇1,王勇1

(1.南京航空航天大學計算機科學與技術(shù)學院,江蘇南京 210016;2.安徽財貿(mào)職業(yè)學院電子信息系,安徽合肥 230061)

動態(tài)故障樹的貝葉斯網(wǎng)絡(luò)分析方法存在局部組合爆炸和備件門節(jié)點失效時間僅能是指數(shù)分布的不足.首先,給出動態(tài)故障樹轉(zhuǎn)換為離散時間貝葉斯網(wǎng)絡(luò)的方法,該方法使用一個確定性函數(shù)來替代條件概率表,避免了局部組合爆炸.然后,根據(jù)備件門的失效機理和對應(yīng)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)特征,解決了備件節(jié)點失效時間僅能是指數(shù)分布的限制.最后,提出一種基于動態(tài)故障樹的貝葉斯網(wǎng)絡(luò)精確推理算法,基于該算法給出了系統(tǒng)失效分布、組件重要度等概率計算.實驗結(jié)果表明,該方法能有效地分析和評估安全攸關(guān)系統(tǒng)的概率特性.

動態(tài)故障樹;貝葉斯網(wǎng)絡(luò);定量分析;安全攸關(guān)系統(tǒng)

1　引言

動態(tài)故障樹(DFT)通過定義優(yōu)先與門,備件門和功能依賴門等動態(tài)門來擴展故障樹的建模能力,使其在具有時間相關(guān)性、功能相關(guān)性等復雜系統(tǒng)安全性分析領(lǐng)域獲得廣泛應(yīng)用[1,2].DFT是半形式化模型,需要轉(zhuǎn)換為數(shù)學模型進行分析[2],但是隨著系統(tǒng)規(guī)模和復雜性的增長,DFT模型也越來越復雜,目前的分析方法存在狀態(tài)空間爆炸和組件失效時間僅服從指數(shù)分布等缺點,難以適應(yīng)大型復雜系統(tǒng)DFT分析需求.

DFT分析方法主要分為狀態(tài)空間分析法[2～5],代數(shù)解析法[6～8],仿真方法[9,10]和貝葉斯網(wǎng)絡(luò)分析法(BN)[11～19]四類.狀態(tài)空間分析法存在狀態(tài)空間爆炸和只能處理組件失效時間服從指數(shù)分布.代數(shù)解析法理論性強,無工具支撐,建模工作量大、易出錯.仿真方法可以處理任意失效分布,但計算精度不高.BN分析法避免了全局狀態(tài)空間爆炸,但存在條件概率表的參數(shù)組合爆炸和備件節(jié)點失效時間僅能是指數(shù)分布.針對上述不足,本文在離散時間BN(Discrete-Time BN,DTBN)分析法的基礎(chǔ)上,提出針對大型復雜系統(tǒng)DFT分析方法:(1)給出一種DFT向DTBN轉(zhuǎn)換方法.將非根節(jié)點CPD表示為父節(jié)點的一個確定性函數(shù),避免條件概率表指數(shù)增長問題.(2)給出BN中備件節(jié)點CPD計算方法,克服了備件節(jié)點失效時間只能是指數(shù)分布的限制.(3)根據(jù)DFT轉(zhuǎn)換的BN結(jié)構(gòu)特征,提出一種基于DFT的BN推理算法.實驗結(jié)果表明,本文提出的方法計算效率和精度優(yōu)于DTBN方法,能有效地避免條件概率表指數(shù)增長并能分析任意失效分布,滿足大型復雜系統(tǒng)DFT分析需求.

2　DFT向BN轉(zhuǎn)換方法

DFT邏輯門包括與門(AND)、或門(OR)和K/M選舉門,動態(tài)門包括順序增強門(SequentialEnforcingGate,SEQ)、優(yōu)先與門(PriorityAND,PAND)、備件門(SPare,SP)和功能依賴門(FunctionalDEPendencygate,FDEP)[2,3].K/M選舉門可由與門和或門組合表示[4],SEQ可由備件門組合表示[11].本節(jié)給出AND、OR、PAND、SP和FDEP向BN轉(zhuǎn)換.DFT門表示、建模場景和失效機理參見相關(guān)文獻[2,3].

2.1DFT門的BN結(jié)構(gòu)表示

DFT門對應(yīng)的BN結(jié)構(gòu)如圖1所示,其中X=(X1,X2,…,Xm)表示組件向量對應(yīng)BN根節(jié)點集合,Y表示(子)系統(tǒng),對應(yīng)BN的中間節(jié)點或葉節(jié)點. Y的CPD表示DFT門的一種邏輯或時序關(guān)系,是父節(jié)點的一個確定性函數(shù),如式(1)所示

(1)

其中,pay表示Y的父節(jié)點.

為了表達動態(tài)門時序關(guān)系將BN節(jié)點CPD按失效時間離散化[12].整個時間 [0,+∞)劃分成n+1個子區(qū)間,其中,任務(wù)時間區(qū)間[0,T]被分成n個長度相等的子區(qū)間,每個子區(qū)間的長度為Δ=T/n,第n+1個子區(qū)間是(t,∞).節(jié)點的狀態(tài)由子區(qū)間 (0,Δ],(Δ,2Δ],…,((n-1)Δ,nΔ],(nΔ,+∞)來表示.如果在任務(wù)時間T內(nèi),節(jié)點X在第i∈{1,2,…,n})個區(qū)間((i-1)Δ,iΔ]內(nèi)發(fā)生失效,記為X=i.X=n+1表示X在T內(nèi)未失效而是在[t,∞)內(nèi)失效.在整個時間[0,+∞)上,節(jié)點必然處在某一狀態(tài).

2.2BN中子系統(tǒng)節(jié)點參數(shù)表示

AND/OR/PAND門對應(yīng)的BN結(jié)構(gòu)相同,如圖1(a)所示,但Y的CPD是不同的.根據(jù)AND門失效機理,Y狀態(tài)是所有組件狀態(tài)值的最大值,Y的CPD由式(2)表示.根據(jù)OR門失效機理,Y狀態(tài)是所有組件狀態(tài)值的最小值,Y的CPD由式(3)表示.PAND門在AND門上增加組件失效時序約束,Y的CPD由式(4)表示.

(2)

(3)

P(Y=l|X)=

(4)

(5)

SP門包括溫備件門(WSP),冷備件門(CSP)和熱備件門(HSP).WSP和CSP門的BN結(jié)構(gòu)如圖1(c)和(d)所示,X1為主件,X2,…,Xm為備件,HSP門主件和備件同時處于工作狀態(tài),BN結(jié)構(gòu)和節(jié)點的CPD和AND門等價[14].根據(jù)WSP門失效機理,Y的CPD和AND門Y的CPD相同由式(2)表示.CSP對應(yīng)的BN中一旦Xm失效,Y立即失效,Y的CPD由式(6)表示.

(6)

2.3BN中備件節(jié)點CPD計算

在SP對應(yīng)的BN中,備件節(jié)點失效行為受父節(jié)點的影響,目前的BN分析方法僅能處理節(jié)點失效時間服從指數(shù)分布[12～14],本節(jié)根據(jù)備件門失效機理和對應(yīng)BN結(jié)構(gòu),將備件節(jié)點失效分布擴展為任意分布.

假設(shè)組件失效率為λ(t),作備件時,失效率由其工作狀態(tài)決定,處于激活狀態(tài)失效率為λ(t),處于備用狀態(tài)失效率為αλ(t)(冷備件α=0,熱備件α=1,溫備件0<αλ(t)<1).Xk-1和Xk是SP對應(yīng)BN中的兩個組件,Xk-1是Xk父節(jié)點,失效時間分別為tk和tk-1.首先給出WSP對應(yīng)BN備件節(jié)點的條件概率密度函數(shù),分兩種情況來討論:

(1)tk≤tk-1,Xk在Xk-1之前或同時失效,也就是Xk在備用狀態(tài)失效,Xk失效不受Xk-1影響,條件概率密度函數(shù)如式(7)所示.

=αfXk(tk)[1-FXk(tk)]α-1,tk≤tk-1

(7)

(2)tk>tk-1,Xk-1在Xk之前失效,由于Xk-1失效,使Xk進入工作狀態(tài),Xk失效受Xk-1影響且Xk和Xk-1都在激活狀態(tài)失效,條件概率密度函數(shù)如式(8)所示.Xk的CPD分別由式(9)計算.

fXk|Xk-1(tk|tk-1)

=fXk(tk)[1-FXk(tk-1)]α-1,tk>tk-1

(8)

P(Xk=i|Xk-1=j)=

(9)

對于CSP門,α=0,Xk不會在Xk-1之前失效,Xk的CPD由式(10)計算,

P(Xk=i|Xk-1=j)=

(10)

3　基于DFT的BN推理算法

DFT轉(zhuǎn)換的BN是典型的層次結(jié)構(gòu),失效行為傳播方式是自底向上的,利用該特征來優(yōu)化通用BN推理算法,以提高分析效率.算法1通過BN中子系統(tǒng)節(jié)點來組織變量消元.基本操作是CPD相乘和求和操作.節(jié)點CPD是父節(jié)點的確定性函數(shù),采用決策樹存儲CPD[20].在算法1中,Ф表示子系統(tǒng)的后驗邊緣分布,Ψ表示節(jié)點CPD,Xij和Yij分別表示第i層第j個組件和子系統(tǒng),Z和C分別表示Yij擁有的下層子系統(tǒng)和組件集合,P表示Xij父節(jié)點的集合.

算法1效率分析,(1)時間復雜度用第10行函數(shù)來度量,該函數(shù)變量個數(shù)是|C|+|Z|+1,假設(shè)BN中子系統(tǒng)結(jié)點個數(shù)為m,組件個數(shù)為k(一般k遠大于m),節(jié)點的狀態(tài)數(shù)為n,那么算法1 時間復雜度為O(mn|C|+|Z|+1),而采用連接樹推理算法[20]時間復雜度大于O((m+k)n|C|+|Z|+1).(2)存儲空間方面,采用決策樹存儲CPD,存儲空間由O(mnm)降低為O(mn)解決了局部存儲空間爆炸問題(m為某一節(jié)點的父節(jié)點數(shù)).

4　實驗分析

根據(jù)DFT到BN轉(zhuǎn)換方法,圖2給出了心臟輔助系統(tǒng)(Cardiac Assist System,CAS)DFT模型[12]等價的BN結(jié)構(gòu).BN采用SamIam分析工具,CTMC采用Galieo DFT分析工具,代數(shù)解析法(Algebraic Analysis,AA)采用MATLAB進行輔助計算.實驗平臺配置為CPU型號為Intel I5,主頻為2.6 GHz,內(nèi)存為4GB.本文提出的方法記為IDTBN,分別與DTBN、CTMC和AA進行比較.

4.1性能分析

假設(shè)CAS各組件的失效時間服從指數(shù)分布,WSP中α=0.5,各組件失效率如表1所示.

表1　CAS系統(tǒng)各組件的失效率

表2給出不同的離散時間粒度下IDTBN和DTBN的執(zhí)行時間.從表2可以看出,隨著n的增大,IDTBN時間性能明顯優(yōu)于DTBN,當n=30時計算時間相差兩個數(shù)量級,IDTBN時間性能基本滿足系統(tǒng)實時分析的需求.

表3給出n=3時,T從1h到10h,分別使用CTMC、IDTBN和DTBN計算的CAS失效概率.

IDTBN和DTBN計算結(jié)果相對CTMC的誤差如圖3(a)所示,DTBN最大相對誤差為5.47‰,算術(shù)平均誤差是2.29‰.標準誤差是3.13‰;IDTBN最大相對誤差為3.42‰,算術(shù)平均誤差是1.39‰.標準誤差是1.92‰,從計算結(jié)果可以看出,IDTBN計算精度要優(yōu)于DTBN.

表2　IDTBN和DTBN方法的執(zhí)行時間

表3　CTMCs 、IDTBN和DTBN方法計算的系統(tǒng)失效概率

選取CPUs子系統(tǒng)驗證IDTBN處理失效時間服從任意分布的有效性,假設(shè)組件失效時間服從威布爾分布,尺度參數(shù)a=500,形狀參數(shù)b=3,T=1000h,n=3.圖3(b)分別給出了IDTBN與AA計算的CPUs子系統(tǒng)失效概率和相對誤差,其中最大相對誤差為8.17‰,算術(shù)平均誤差是3.08‰.標準誤差是4.52‰.

4.2系統(tǒng)組件重要度及后驗失效分布計算

在表1的參數(shù)設(shè)置下,n=3,T=10h,IDTBN和CTMC的組件Birnbaum重要度計算結(jié)果如表4所示.雖然結(jié)果存在一定的誤差,但這并不影響組件重要度的定性.

和CTMC等其他方法相比,IDTBN法能夠在給定證據(jù)下進行后驗概率查詢.當CAS系統(tǒng)失效時,IDTBN計算的各子系統(tǒng)以及組件后驗失效分布如圖4所示.

表4　組件Birnbaum重要度

5　總結(jié)

IDTBN方法,克服了BN節(jié)點CPD組合爆炸缺點,消除了BN備件節(jié)點失效時間僅能是指數(shù)分布的限制,提高了分析效率和分析能力.在實驗中,將IDTBN和DTBN,CTMC等方法在時間性能、計算精度方法進行比較,然后利用該方法對系統(tǒng)失效分布和組件重要度等安全攸關(guān)系統(tǒng)概率特性計算,實驗結(jié)果表明,IDTBN方法的分析能力和效率優(yōu)于現(xiàn)存的分析方法.

[1]黃志球,徐丙鳳,闞雙龍,等.嵌入式機載軟件安全性分析標準、方法及工具研究綜述[J].軟件學報,2014,25(2):200-218.

HuangZQ,XuBF,KanSL,etal.Surveyonembeddedsoftwaresafetyanalysisstandards,methodsandtoolsforairbornesystem[J].JournalofSoftware,2014,25(2):200-218.(inChinese)

[2]JBDugan,SJBavuso,MABoyd.Dynamicfault-treeforfault-tolerantcomputersystems[J].IEEETransactionsonReliability,1992,41(3):363-377.

[3]JBDugan,KJSullivan,DCoppit.Developingalowcosthigh-qualitysoftwaretoolfordynamicfault-treeanalysis[J].IEEETransactionsonReliability,2000,49(1):49-59.

[4]LiudongXing,MorrissetteBA,DuganJB.Combinatorialreliabilityanalysisofimperfectcoveragesystemssubjecttofunctionaldependence[J].IEEETransactionsonReliability,2014,63(1):367-383.

[5]徐丙鳳,黃志球,胡軍,等.一種狀態(tài)事件故障樹的定量分析方法[J].電子學報,2013,41(8):1480-1486.XUBing-feng,HUANGZhi-qiu,HUJun,etal.Amethodforquantitativeanalysisofstate/eventfaulttree[J].ActaElectronicaSinica,2013,41(8):1480-1486.(inChinese)

[6]GMerle,JMRoussel,JJLesage,etal.Probabilisticalgebraicanalysisoffaulttreeswithprioritydynamicgatesandrepeatedevents[J].IEEETransactionsonReliability,2010,59(1):250-261.

[7]JunNi,WenchengTang,YanXing.Asimplealgebraforfaulttreeanalysisofstaticanddynamicsystems[J].IEEETransactionsonReliability,2013,62(4):856-872.

[8]DaochuanGe,MengLin,YanhuaYang,etal.Quantitativeanalysisofdynamicfaulttreesusingimprovedsequentialbinarydecisiondiagrams[J].ReliabilityEngineeringandSystemSafety,2015,142(10):289-299.

[9]KDRao,VGopika,VVSSRao,etal.Dynamicfaulttreeanalysisusingmontecarlosimulationinprobabilisticsafetyassessment[J].ReliabilityEngineeringandSystemSafety,2009,94(4):872-883.

[10]PeicanZhu,JieHan,LeiboLiu,etal.Astochasticapproachfortheanalysisoffaulttreeswithpriorityandgates[J].IEEETransactionsonReliability,2014,63(2):480-495.

[11]MontaniS,PortinaleL,BobbioA,etal.RADYBAN:atoolforreliabilityanalysisofdynamicfaulttreesthroughconversionintodynamicBayesiannetworks[J].ReliabilityEngineeringandSystemSafety,2008,93(7):922-932.

[12]BoudaliH,DuganJB.Adiscrete-timeBayesiannetworkreliabilitymodelingandanalysisframework[J].ReliabilityEngineeringandSystemSafety,2005,87(3):337-349.

[13]周忠寶,周經(jīng)倫,孫權(quán).基于離散時間貝葉斯網(wǎng)絡(luò)的動態(tài)故障樹分析方法[J].西安交通大學學報,2007,41(6):732-736.

ZhouZhongbao,ZhouJinglun,SunQuan.DynamicfaulttreeanalysisbasedondynamicBayesiannetworks[J].JournalofXianJiaoTongUniversity,2007,41(6):732-736.(inChinese)

[14]NKhakzad,FKhan,PAmyotte.Risk-baseddesignofprocesssystemsusingdiscrete-timeBayesiannetworks[J].ReliabilityEngineeringandSystemSafety,2013,109(1):5-17.

[15]BoudaliH,DuganJB.Acontinuous-timeBayesiannetworkreliabilitymodelingandanalysisframework[J].IEEETransactionsonReliability,2006,55(1):86-97.

[16]Yan-FengLi,Hong-ZhongHuang,YuLiu,etal.Anoveldynamicfaulttreeanalysismethod[A].TheProceedingsof2013InternationalConferenceonQuality,Reliability,Risk,Maintenance,andSafetyEngineering[C].Piscatawa:IEEE,2013.81-84.

[17]DanieleCodetta-Raiteri,LuigiPortinale.ModelingandanalysisofdependablesystemsthroughgeneralizedcontinuoustimeBayesiannetworks[A].ReliabilityandMaintainabilitySymposium(RAMS),2015Annual[C].Piscataway:IEEE,2015.1-6.

[18]XiaopengLi,NanAo,LeileiWu.Therefiningreliabilitymodelingmethodforthesatellitesystem[A].TheProceedingsof2014 10thInternationalConferenceonReliabilityMaintainabilityandSafety[C].Piscataway:IEEE,2014.484-488.

[19]王楨珍,姜欣,武小悅,等.信息安全風險概率計算的貝葉斯網(wǎng)絡(luò)模型[J].電子學報,2010,38(2A):18-22.

WANGZhen-zhen,JIANGXin,WUXiao-yue,etal.Planningexploitationgraph-Bayesiannetworksmodelforinformationsecurityriskfrequencymeasurement[J].ActaElectronicaSinica,2010,38(2A):18-22.(inChinese)

[20]KollerD,FriedmanN.ProbabilisticGraphicalModels:PrinciplesandTechniques[M].Cambridge:MITPress,2009.

房丙午男,1974年生于安徽安慶.現(xiàn)為南京航空航天大學計算機科學與技術(shù)學院博士研究生,副教授.主要研究方向軟件工程,軟件系統(tǒng)安全性分析.

E-mail:bingwufang@163.com

黃志球(通信作者)男,1965 年生于江蘇南京.現(xiàn)為南京航空航天大學教授,博士生導師,CCF杰出會員.主要研究方向為軟件工程,形式化方法,軟件分析與驗證.

E-mail:zqhuang@nuaa.edu.cn

Quantitative Analysis Method of Dynamic Fault Tree of Complex System Using Bayesian Network

FANG Bing-wu1,2,HUANG Zhi-qiu1,LI Yong1,WANG Yong1

(1.CollegeofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing,Jiangsu210016,China; 2.DepartmentofElectronicsandInformation,AnhuiVocationalCollegeofFinanceandTrade,Hefei,Anhui230061,China)

There exist limitations of local combinatorial explosion and only exponential distribution of spare nodes in Bayesian network(BN)-based dynamic fault tree(DFT) analysis method.First,an approach of mapping DFT into discrete-time BN is proposed in which a deterministic function instead of conditional probability tables is used to avoid local combinatorial explosion.Second,according to the failure mechanism and BN structure of spare door,we remove the limitation that the failure time of spare nodes in BN is only exponential distribution.Finally,an exact inference algorithm of DFT-based BN is presented and based on which the failure distribution of system and the importance measurement of components is calculated.Experimental results show that the proposed method can analyze and evaluate the probability characteristics of safety-critical systems effectively.

dynamic fault tree;Bayesian network;quantitative analysis;safety-critical system

2015-06-15;

2015-08-26;責任編輯:覃懷銀

國家自然科學基金(No.61272083,No.61562087);安徽省教育廳自然科學基金 (No.KJ2013B009,No.KJ2015A400)

TP311

A

0372-2112 (2016)05-1234-06

電子學報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.032