基于Petri網(wǎng)的聯(lián)鎖軟件測(cè)試用例動(dòng)態(tài)生成

強(qiáng)生杰，任恩恩

(蘭州交通大學(xué)光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室，蘭州 730070)

1 概述

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

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

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

2 符號(hào)與定義

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

定義1 以 S×T為序標(biāo)集的矩陣 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 在安全需求模型的底事件組合中，若某個(gè)集合中的底事件的發(fā)生會(huì)導(dǎo)致頂事件的發(fā)生，則這個(gè)集合稱為割集(Cut Sets, CS)。若一個(gè)割集去掉某個(gè)底事件后就不再是割集，那么這個(gè)割集就稱為最小割集)。

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

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

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

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

表1 中間庫(kù)所

表2 底層庫(kù)所

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

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

4.1 算法及其流程

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

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

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

輸出 故障樹(shù)的最小割集

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

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

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

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

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

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

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

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

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

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

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

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

算法 2 基于形式化故障樹(shù)最小割集的測(cè)試用例自動(dòng)生成算法

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

輸出 對(duì)應(yīng)最小割集的測(cè)試用例

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

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

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

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

(1)實(shí)現(xiàn)了安全需求測(cè)試用例的自動(dòng)生成和動(dòng)態(tài)擴(kuò)展；

(2)實(shí)現(xiàn)了對(duì)測(cè)試結(jié)果的正確性判定。

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

6 結(jié)束語(yǔ)

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

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

[2]葉 俊, 龍志強(qiáng).基于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]張福新, 杜玉越.改進(jìn)的最小割集生成算法與聯(lián)鎖系統(tǒng)模型的安全性測(cè)試[J].計(jì)算機(jī)應(yīng)用研究, 2009, 26(8):3039-3043.

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

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

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

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

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