強生杰，任恩恩

(蘭州交通大學光電技術(shù)與智能控制教育部重點實驗室，蘭州 730070)

1 概述

鐵路聯(lián)鎖系統(tǒng)是典型的安全苛求系統(tǒng)，其可靠性和安全性是需要著重考慮的關(guān)鍵性因素。相應地，嵌入其中的聯(lián)鎖軟件的邏輯設計也必須做到合理及安全。在對聯(lián)鎖軟件進行軟件測試時，提高測試過程的自動化程度，改變傳統(tǒng)的依靠經(jīng)驗產(chǎn)生測試用例的做法，不僅可以提高軟件測試效率，減少測試工作量，同時也可以確保測試質(zhì)量。

Petri網(wǎng)是一種用于系統(tǒng)描述及模擬的數(shù)學分析工具，它可以較好地描述復雜系統(tǒng)中常見的同步、并發(fā)、沖突等現(xiàn)象并對其進行分析[1]。近年來，Petri網(wǎng)的有關(guān)理論已被應用到可靠性分析中[2-4]，它利用底層庫所代表某個原子故障事件，頂層庫所和中間庫所通常代表某些故障事件的邏輯組合，以有向弧的指示方向表示系統(tǒng)故障的傳播關(guān)系。通過Petri網(wǎng)表達系統(tǒng)的邏輯關(guān)系，完成知識表示和診斷推理；同時也可對被診斷對象建立行為模型并利用Petri網(wǎng)屬性進行基于模型的診斷推理。

文獻[5-6]利用故障樹的 Petri網(wǎng)求其最小割集(Minimal Cut Sets, MCS)。文獻[5]構(gòu)造網(wǎng)絡可達圖，設計一個針對可達標志圖搜索算法。文獻[6]提出直接利用關(guān)聯(lián)矩陣來求最小割集的方法。綜合多種方法的優(yōu)點，本文提出一種利用 Petri網(wǎng)安全需求模型的最小割集算法，在此基礎(chǔ)上給出一種基于形式化故障樹最小割集的安全性測試用例動態(tài)生成算法。

2 符號與定義

為了方便問題的闡述，文中的 Petri網(wǎng)用六元組表示，設∑=(S, T; F )為有限P/T_系統(tǒng)，并假定其基網(wǎng)(S, T; F）是單純的，其中，S=｛s1, s2,… ,sm｝為有限庫所集合；T = ｛t1,t2,… ,tn｝為有限變遷集合。

定義1 以 S×T為序標集的矩陣 C稱作Σ的關(guān)聯(lián)矩 陣(Incidence Matrix)，其矩陣元素為 ：C(si, tj)=W(tj,si) ?W(si, tj)，1≤i≤m，1≤j≤ n 。

定義2 ∑?= (S, T; F?1）稱為 ∑=(S, T; F）的逆網(wǎng)(Reverse Net)。

定義3 在安全需求模型的底事件組合中，若某個集合中的底事件的發(fā)生會導致頂事件的發(fā)生，則這個集合稱為割集(Cut Sets, CS)。若一個割集去掉某個底事件后就不再是割集，那么這個割集就稱為最小割集)。

3 聯(lián)鎖軟件安全需求Petri網(wǎng)模型

通過對行車事故的分析和總結(jié)，可以提煉出列機車撞車事故故障樹[7-8]，并將相關(guān)語義直接映射到如圖 1所示的聯(lián)鎖系統(tǒng)安全性需求的 Petri網(wǎng)故障樹模型中。該模型將庫所分為底層庫所、頂層庫所和中間庫所3類。底層庫所代表某個原子故障事件，它只能作為變遷的輸入庫所，頂層庫所和中間庫所通常代表某些故障事件的邏輯組合，其中，頂層庫所是整個系統(tǒng)中最需要避免的故障事件。

圖1 聯(lián)鎖軟件安全需求Petri網(wǎng)模型

由圖1的結(jié)構(gòu)可以看出，該Petri網(wǎng)含有11個底層庫所、6個中間庫所和1個頂層庫所。其中，頂層庫所M07的含義為發(fā)生故障。中間庫所如表1所示，底層庫所如表2所示。

表1 中間庫所

表2 底層庫所

4 基于Petri網(wǎng)的改進最小割集算法

安全需求樹分析的目的是在于尋找導致頂層事件發(fā)生的原因和原因組合。最小割集可以表示出故障發(fā)生的所有可能組合，安全分析的主要任務是找出故障樹中的所有最小割集。為了方便將 Petri網(wǎng)在計算機上的表示和數(shù)據(jù)處理，使用一個二維數(shù)組表示圖的關(guān)聯(lián)矩陣是一種可行的方法，但對于稀疏矩陣而言，使用數(shù)組表示法會造成存儲空間的浪費，尤其是當圖中結(jié)點數(shù)目巨大時。以圖1為例，存儲關(guān)聯(lián)矩陣需要開拓18×13個空間，而實際上只使用了其中的30個，顯然造成很大的浪費。本文利用鄰接表(adjacency list)來實現(xiàn) Petri網(wǎng)故障樹，提出一種改進的最小割集求解方法，通過遍歷故障樹中所有的結(jié)點來構(gòu)造其最小割集。

4.1 算法及其流程

算法設計思路為：對原 Petri網(wǎng)模型的逆網(wǎng)做簡單的映射變化，將網(wǎng)絡中的變遷與庫所同時轉(zhuǎn)化為圖中的結(jié)點而不必去區(qū)分，同時不改變它們之間的邏輯關(guān)系；通過建立逆網(wǎng)模型的鄰接表來實現(xiàn)Petri網(wǎng)的存儲。通過求解原安全需求 Petri網(wǎng)模型的逆，將問題轉(zhuǎn)化為由頂事件自頂而下的求解最小割集，從而降低算法的復雜度；將網(wǎng)絡中的庫所以及變遷同時轉(zhuǎn)化為圖中的結(jié)點是為了方便使用鄰接表和算法的實現(xiàn)。算法中庫所結(jié)點與變遷結(jié)點的定義如下：

算法l 基于Petri網(wǎng)故障樹的最小割集求解算法

輸入 故障樹的Petri網(wǎng)模型PN=(P, T; F)以及頂層庫所事件

輸出 故障樹的最小割集

我校2012級碩士生（非中醫(yī)）共有23人，前置專業(yè)主要為文學、西醫(yī)學、藥學專業(yè)，在校攻讀專業(yè)主要為醫(yī)史文獻、中醫(yī)臨床基礎(chǔ)、中西醫(yī)結(jié)合臨床、中藥學專業(yè)。中醫(yī)及相關(guān)專業(yè)的本科、研究生教學內(nèi)容相對于碩士生（非中醫(yī)）而言，存在內(nèi)容多、學時少、方劑組成難記、藥物配伍意義難理解、方與方主治易混淆、應用變化繁多等問題。要從根本上解決這一問題，需明確教學目的，減少方劑掌握數(shù)量，強調(diào)方劑的組成與主治證，注重方劑的實用性與實效性。

Step1 構(gòu)造僅含有頂層庫所結(jié)點的集合 S，并將其作為活結(jié)點。

Step2 利用廣度優(yōu)先的策略搜索 Petri網(wǎng)中活結(jié)點的所有子結(jié)點，若活結(jié)點在 Petri網(wǎng)中為變遷結(jié)點且其子結(jié)點為庫所結(jié)點，則把活結(jié)點的所有子結(jié)點都加入到當前活結(jié)點所在的集合中，同時將該活結(jié)點從集合中刪除；若活結(jié)點是庫所結(jié)點且其n個子結(jié)點為變遷結(jié)點，則構(gòu)造出n個集合，將每一個子結(jié)點添加到相應的集合中，同時將該活結(jié)點刪除。

Step3 若活結(jié)點不為頂層庫所結(jié)點且已搜索完畢，則選擇該結(jié)點的父結(jié)點為當前的活結(jié)點，從活結(jié)點的子結(jié)點集合中選擇一個未擴展的結(jié)點為活結(jié)點，進而轉(zhuǎn)到 Step2；若活結(jié)點為頂層庫所結(jié)點且已搜索完畢，則搜索結(jié)束。

Step4 檢查生成的所有集合中的元素，按照布爾吸收律或素數(shù)法去除重復或多余的元素便可求得最小割集。

4.2 求解聯(lián)鎖軟件安全需求的最小割集

系統(tǒng)故障可以通過其故障模式的最小割集來表示，最小割集中底層事件的發(fā)生會導致頂層失效事件的出現(xiàn)[9]。為了使系統(tǒng)輸出滿足安全性需求，可以通過構(gòu)造安全性約束條件來避免最小割集中底層故障事件的出現(xiàn)。

對于鐵路聯(lián)鎖系統(tǒng)而言，根據(jù)安全性需求建立聯(lián)鎖軟件中列車正常通過進路的模型，根據(jù)算法1的設計要求建立該邏輯的逆模型鄰接表，在VC中編程實現(xiàn)，模型鄰接表如圖 2所示，圖中 Λ表示空指針NULL。

圖2 聯(lián)鎖軟件安全需求Petri網(wǎng)模型的鄰接表表示形式

利用算法 1，求得聯(lián)鎖軟件安全性需求的 Petri網(wǎng)模型的最小割集：

安全約束條件是故障樹分析結(jié)果的否定，進而可以求出安全約束條件：

5 基于最小割集的安全性測試用例動態(tài)生成

算法 2 基于形式化故障樹最小割集的測試用例自動生成算法

輸入 逐一輸入安全需求的最小割集

輸出 對應最小割集的測試用例

Step1 在基礎(chǔ)測試數(shù)據(jù)中任取一個滿足條件且未被測試的向量作為當前測試用例的測試數(shù)據(jù)加載到被測安全軟件。

Step2 判斷該最小割集所有可控事件的底事件是否都已經(jīng)擴展。若是，則無需繼續(xù)擴展；若不是，則根據(jù)聯(lián)鎖規(guī)則任意擴展一個可控底層事件，生成對應的測試數(shù)據(jù)以及相應的預期輸出，記為[input/output]。

Step3 加載輸入數(shù)據(jù)inputs到被測軟件中，得到被測軟件的實際輸出。若測試結(jié)果與預期的輸出一致，則轉(zhuǎn)到Step2，繼續(xù)擴展G中未被測試的可控底事件；若兩者不一致，由于最小割集中的底事件之間是邏輯與的關(guān)系，因此表明可控底事件沒有發(fā)生，從而基于該最小割集的安全性測試用例也就無需再進行擴展，測試用例結(jié)束。

可以看出，基于最小割集的安全性測試用例生成算法是一個不斷擴展的動態(tài)過程。在算法的執(zhí)行過程中：

(1)實現(xiàn)了安全需求測試用例的自動生成和動態(tài)擴展；

(2)實現(xiàn)了對測試結(jié)果的正確性判定。

為了驗證所提算法的合理性以及可操作性，測試選取了一個具有7組道岔、16架信號機和13個區(qū)段的虛擬站場為測試對象。在實施安全性測試的過程中，應當在遵循鐵道部有關(guān)技術(shù)規(guī)范的前提下以確保安全為原則來產(chǎn)生測試數(shù)據(jù)。在對聯(lián)鎖軟件的測試過程中，要重點保證對聯(lián)鎖邏輯以及故障或失效的測試，測試數(shù)據(jù)的選擇要盡可能暴露出軟件設計中存在的問題，尤其是對實際中出現(xiàn)的極端特殊情況的測試。在具體測試中，首先利用安全性需求的形式化Petri網(wǎng)來表示軟件中的各級安全性需求，其次搜索生成安全需求樹中所蘊含的最小割集，最后利用算法2實現(xiàn)安全性測試用例的動態(tài)生成并對聯(lián)鎖軟件進行測試。

6 結(jié)束語

本文利用 Petri網(wǎng)可動態(tài)描述和分析系統(tǒng)行為的特性，給出鐵路計算機聯(lián)鎖軟件的安全需求 Petri網(wǎng)模型，進而提出最小割集生成算法以及安全性測試用例動態(tài)生成算法。從對虛擬站場進行的測試結(jié)果可以看出，該算法可以有效地分析和建立聯(lián)鎖軟件的安全性需求，其軟件測試效率得到大幅提高。今后研究的重點為安全需求 Petri網(wǎng)模型子模塊的細化以及結(jié)合其他定量分析方法對模型可靠性的定量判斷。

[1]袁崇義.Petri網(wǎng)原理及應用[M].北京: 電子工業(yè)出版社,2005.

[2]葉 俊, 龍志強.基于Petri Net的故障診斷理論研究[J].控制與決策, 2007, 22(12): 1403-1407.

[3]Chung S W C, Jeng M D.Failure Diagnosis: A Case Study on Modeling and Analysis by Petri Nets[C]//Proc.of IEEE International Conference on Systems, Man and Cybernetics.[S.l.]: IEEE Press, 2003.

[4]Manyari-Rivera M, Basilio J C, Bhaya A.Integrated Fault Diagnosis Based on Petri Net Models[C]//Proc.of the 16th International Conference on Control Applications Part of IEEE Multi-conference on Systems and Control.Singapore: IEEE Press, 2007.

[5]張福新, 杜玉越.改進的最小割集生成算法與聯(lián)鎖系統(tǒng)模型的安全性測試[J].計算機應用研究, 2009, 26(8):3039-3043.

[6]武 瀅, 謝里陽, 李進冬.應用Petri網(wǎng)的關(guān)聯(lián)矩陣求最小割集的新方法[J].中國機械工程, 2008, 19(9): 1044-1047.

[7]杜軍偉, 徐中偉.聯(lián)鎖邏輯模型的安全性分析[J].計算機工程與應用, 2007, 43(2): 1-4.

[8]魏 臻, 周 霞, 鮑紅杰, 等.基于 Petri網(wǎng)的聯(lián)鎖軟件安全性測試的研究[J].計算機工程與應用, 2005, 41(17):123-125, 138.

[9]王仲生.智能故障診斷與容錯控制[M].西安: 西北工業(yè)大學出版社, 2005.

[10]徐中偉, 吳芳美.形式化故障樹分析建模和軟件安全性測試[J].同濟大學學報, 2001, 29(11): 1299-1302.