基于Petri网的联锁软件测试用例动态生成

强生杰，任恩恩

(兰州交通大学光电技术与智能控制教育部重点实验室，兰州 730070)

1 概述

铁路联锁系统是典型的安全苛求系统，其可靠性和安全性是需要着重考虑的关键性因素。相应地，嵌入其中的联锁软件的逻辑设计也必须做到合理及安全。在对联锁软件进行软件测试时，提高测试过程的自动化程度，改变传统的依靠经验产生测试用例的做法，不仅可以提高软件测试效率，减少测试工作量，同时也可以确保测试质量。

Petri网是一种用于系统描述及模拟的数学分析工具，它可以较好地描述复杂系统中常见的同步、并发、冲突等现象并对其进行分析[1]。近年来，Petri网的有关理论已被应用到可靠性分析中[2-4]，它利用底层库所代表某个原子故障事件，顶层库所和中间库所通常代表某些故障事件的逻辑组合，以有向弧的指示方向表示系统故障的传播关系。通过Petri网表达系统的逻辑关系，完成知识表示和诊断推理；同时也可对被诊断对象建立行为模型并利用Petri网属性进行基于模型的诊断推理。

文献[5-6]利用故障树的 Petri网求其最小割集(Minimal Cut Sets, MCS)。文献[5]构造网络可达图，设计一个针对可达标志图搜索算法。文献[6]提出直接利用关联矩阵来求最小割集的方法。综合多种方法的优点，本文提出一种利用 Petri网安全需求模型的最小割集算法，在此基础上给出一种基于形式化故障树最小割集的安全性测试用例动态生成算法。

2 符号与定义

为了方便问题的阐述，文中的 Petri网用六元组表示，设∑=(S, T; F )为有限P/T_系统，并假定其基网(S, T; F）是单纯的，其中，S=｛s1, s2,… ,sm｝为有限库所集合；T = ｛t1,t2,… ,tn｝为有限变迁集合。

定义1 以 S×T为序标集的矩阵 C称作Σ的关联矩 阵(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）的逆网(Reverse Net)。

定义3 在安全需求模型的底事件组合中，若某个集合中的底事件的发生会导致顶事件的发生，则这个集合称为割集(Cut Sets, CS)。若一个割集去掉某个底事件后就不再是割集，那么这个割集就称为最小割集)。

3 联锁软件安全需求Petri网模型

通过对行车事故的分析和总结，可以提炼出列机车撞车事故故障树[7-8]，并将相关语义直接映射到如图 1所示的联锁系统安全性需求的 Petri网故障树模型中。该模型将库所分为底层库所、顶层库所和中间库所3类。底层库所代表某个原子故障事件，它只能作为变迁的输入库所，顶层库所和中间库所通常代表某些故障事件的逻辑组合，其中，顶层库所是整个系统中最需要避免的故障事件。

图1 联锁软件安全需求Petri网模型

由图1的结构可以看出，该Petri网含有11个底层库所、6个中间库所和1个顶层库所。其中，顶层库所M07的含义为发生故障。中间库所如表1所示，底层库所如表2所示。

表1 中间库所

表2 底层库所

4 基于Petri网的改进最小割集算法

安全需求树分析的目的是在于寻找导致顶层事件发生的原因和原因组合。最小割集可以表示出故障发生的所有可能组合，安全分析的主要任务是找出故障树中的所有最小割集。为了方便将 Petri网在计算机上的表示和数据处理，使用一个二维数组表示图的关联矩阵是一种可行的方法，但对于稀疏矩阵而言，使用数组表示法会造成存储空间的浪费，尤其是当图中结点数目巨大时。以图1为例，存储关联矩阵需要开拓18×13个空间，而实际上只使用了其中的30个，显然造成很大的浪费。本文利用邻接表(adjacency list)来实现 Petri网故障树，提出一种改进的最小割集求解方法，通过遍历故障树中所有的结点来构造其最小割集。

4.1 算法及其流程

算法设计思路为：对原 Petri网模型的逆网做简单的映射变化，将网络中的变迁与库所同时转化为图中的结点而不必去区分，同时不改变它们之间的逻辑关系；通过建立逆网模型的邻接表来实现Petri网的存储。通过求解原安全需求 Petri网模型的逆，将问题转化为由顶事件自顶而下的求解最小割集，从而降低算法的复杂度；将网络中的库所以及变迁同时转化为图中的结点是为了方便使用邻接表和算法的实现。算法中库所结点与变迁结点的定义如下：

算法l 基于Petri网故障树的最小割集求解算法

输入 故障树的Petri网模型PN=(P, T; F)以及顶层库所事件

输出 故障树的最小割集

我校2012级硕士生（非中医）共有23人，前置专业主要为文学、西医学、药学专业，在校攻读专业主要为医史文献、中医临床基础、中西医结合临床、中药学专业。中医及相关专业的本科、研究生教学内容相对于硕士生（非中医）而言，存在内容多、学时少、方剂组成难记、药物配伍意义难理解、方与方主治易混淆、应用变化繁多等问题。要从根本上解决这一问题，需明确教学目的，减少方剂掌握数量，强调方剂的组成与主治证，注重方剂的实用性与实效性。

Step1 构造仅含有顶层库所结点的集合 S，并将其作为活结点。

Step2 利用广度优先的策略搜索 Petri网中活结点的所有子结点，若活结点在 Petri网中为变迁结点且其子结点为库所结点，则把活结点的所有子结点都加入到当前活结点所在的集合中，同时将该活结点从集合中删除；若活结点是库所结点且其n个子结点为变迁结点，则构造出n个集合，将每一个子结点添加到相应的集合中，同时将该活结点删除。

Step3 若活结点不为顶层库所结点且已搜索完毕，则选择该结点的父结点为当前的活结点，从活结点的子结点集合中选择一个未扩展的结点为活结点，进而转到 Step2；若活结点为顶层库所结点且已搜索完毕，则搜索结束。

Step4 检查生成的所有集合中的元素，按照布尔吸收律或素数法去除重复或多余的元素便可求得最小割集。

4.2 求解联锁软件安全需求的最小割集

系统故障可以通过其故障模式的最小割集来表示，最小割集中底层事件的发生会导致顶层失效事件的出现[9]。为了使系统输出满足安全性需求，可以通过构造安全性约束条件来避免最小割集中底层故障事件的出现。

对于铁路联锁系统而言，根据安全性需求建立联锁软件中列车正常通过进路的模型，根据算法1的设计要求建立该逻辑的逆模型邻接表，在VC中编程实现，模型邻接表如图 2所示，图中 Λ表示空指针NULL。

图2 联锁软件安全需求Petri网模型的邻接表表示形式

利用算法 1，求得联锁软件安全性需求的 Petri网模型的最小割集：

安全约束条件是故障树分析结果的否定，进而可以求出安全约束条件：

5 基于最小割集的安全性测试用例动态生成

算法 2 基于形式化故障树最小割集的测试用例自动生成算法

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

输出 对应最小割集的测试用例

Step1 在基础测试数据中任取一个满足条件且未被测试的向量作为当前测试用例的测试数据加载到被测安全软件。

Step2 判断该最小割集所有可控事件的底事件是否都已经扩展。若是，则无需继续扩展；若不是，则根据联锁规则任意扩展一个可控底层事件，生成对应的测试数据以及相应的预期输出，记为[input/output]。

Step3 加载输入数据inputs到被测软件中，得到被测软件的实际输出。若测试结果与预期的输出一致，则转到Step2，继续扩展G中未被测试的可控底事件；若两者不一致，由于最小割集中的底事件之间是逻辑与的关系，因此表明可控底事件没有发生，从而基于该最小割集的安全性测试用例也就无需再进行扩展，测试用例结束。

可以看出，基于最小割集的安全性测试用例生成算法是一个不断扩展的动态过程。在算法的执行过程中：

(1)实现了安全需求测试用例的自动生成和动态扩展；

(2)实现了对测试结果的正确性判定。

为了验证所提算法的合理性以及可操作性，测试选取了一个具有7组道岔、16架信号机和13个区段的虚拟站场为测试对象。在实施安全性测试的过程中，应当在遵循铁道部有关技术规范的前提下以确保安全为原则来产生测试数据。在对联锁软件的测试过程中，要重点保证对联锁逻辑以及故障或失效的测试，测试数据的选择要尽可能暴露出软件设计中存在的问题，尤其是对实际中出现的极端特殊情况的测试。在具体测试中，首先利用安全性需求的形式化Petri网来表示软件中的各级安全性需求，其次搜索生成安全需求树中所蕴含的最小割集，最后利用算法2实现安全性测试用例的动态生成并对联锁软件进行测试。

6 结束语

本文利用 Petri网可动态描述和分析系统行为的特性，给出铁路计算机联锁软件的安全需求 Petri网模型，进而提出最小割集生成算法以及安全性测试用例动态生成算法。从对虚拟站场进行的测试结果可以看出，该算法可以有效地分析和建立联锁软件的安全性需求，其软件测试效率得到大幅提高。今后研究的重点为安全需求 Petri网模型子模块的细化以及结合其他定量分析方法对模型可靠性的定量判断。

[1]袁崇义.Petri网原理及应用[M].北京: 电子工业出版社,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]张福新, 杜玉越.改进的最小割集生成算法与联锁系统模型的安全性测试[J].计算机应用研究, 2009, 26(8):3039-3043.

[6]武 滢, 谢里阳, 李进冬.应用Petri网的关联矩阵求最小割集的新方法[J].中国机械工程, 2008, 19(9): 1044-1047.

[7]杜军伟, 徐中伟.联锁逻辑模型的安全性分析[J].计算机工程与应用, 2007, 43(2): 1-4.

[8]魏 臻, 周 霞, 鲍红杰, 等.基于 Petri网的联锁软件安全性测试的研究[J].计算机工程与应用, 2005, 41(17):123-125, 138.

[9]王仲生.智能故障诊断与容错控制[M].西安: 西北工业大学出版社, 2005.

[10]徐中伟, 吴芳美.形式化故障树分析建模和软件安全性测试[J].同济大学学报, 2001, 29(11): 1299-1302.