建立和分析安全关键系统的错误传递图

0 引 言
随着计算机系统的发展 各种各样的控制程序被
广泛应用于各个领域例如航空、飞行控制系统化工
厂、核工厂的关闭系统工业自动控制系统医疗设备
控制系统、 轿车的刹车系统 嵌入式系统中的微处理
器、操作系统和其他电子设备等。 一旦这类系统出现故
障往往会对环境和公众造成极大的危害。
一个安全系统在安全监测和分析方面 还存在判
断错误不够及时、不够准确等许多问题解决这些问题
需要对系统进行不间断地、精确地监测重点是监测系
统的功能、行为、运行状态等参数同时要予以分析并
快速地找出发生错误的源头 尽可能在事故发生前消
除错误。
近 来 年 在安全领域的研究取得了不少进 展 。
Yiannis 提出了利用广泛的在线监测来检测系统的各
种功能是否运行正常从而控制和减少事故的发生。 这
种方法使对复杂系统的静态或动态行为和结构进行有
层次的评估起了促进的作用[1]。
Frantz 提出了使用形式方法 结合错误传递图
FPG来分析错误的源头并且使用严重程度分类方法
来分析节点的警报器放置的问题[2]。
1 建立安全关键系统的 FPG
一个系统的行为和功能可以通过构造一个 FPG
来体现出来 而且 FPG 能够动态地展现系统内部的错
误的传递情况可用来辅助系统监控。 尤其适合具有成
千上万个部件的大型安全关键系统。 节点、边、箭头以
及放置在节点上的警报器都是 FPG 的组成要素。
为了识别一个系统内部的错误来源 可 以 使 用
MFD 算法来消除和错误出现不相关的节点 并计算出
错误的源头节点。MFD 算法可以用 Z 语言来描述。Z 语
言是属于形式方法的一种描述语言 它的符号是由集
合论和数理逻辑发展而来的[3]。
1.1 为什么要建立 FPG
以往识别错误和找出错误的源头主要是依靠操作
员的知识和经验去判断。 没有自动化过程的监测提供
帮助人工的检查费时费力。 而且如果一个错误是在
一个复杂而庞大的系统内部发生的 想在短时间里识
别它并找出故障的来源相当困难因为需要考虑的部
件实在是太多了。
在一个大型的系统内 有故障时还可能是多个错
趥趮
研究与开发
现代计算机 2011.10
f
b
k
g
c
a

    




误同时发生。 系统的操作员除了要具备丰富的知识和
多年操作经验还要对系统操作非常熟悉并具有敏锐
的判断力。 但即使在这样的情况在危急关头操作员
也可能会因紧张导致犹豫不决或者直接判断失误。
假设有一个直观的图形能够实时地显示系统的状
态和行为 在发生错误时能展现错误在不同部件之间
传递的情况还能够自动地计算出错误的来源那么操
作员就可以借助于计算的结果并结合自己的判断定
位错误的源头采取相应的应急措施避免更严重的事
故发生。 为系统建立一个 FPG 就能实现上述的所有功
能配合 MFD 算法找出错误的源头。
1.2 FPG 的内部结构
建立一个 FPG 首先要了解它内部的各个元素然
后对一个系统进行分解将部件用节点来表示。 用边和
箭头表示部件之间的关系 以及错误传递的路径和方
向。 FPG 包含的元素如下
节点: 每个节点代表了系统的一个组成部分。对于
软件来说 一个节点可以代表程序的一个方法或者函
数。
边和箭头图 1 中的边代表着系统部件之间的依
赖关系箭头代表着错误传递的方向。
有向图是一个由节点和有向边组成的图。 节点之
间的边都是唯一且有方向的 节点之间不存在多条边
或者具有环路的边。 FPG 实质上是一个有向图。
触发的警报是指有错误发生并被节点检测到以
致触发警报。
触发节点是指警报器被触发了的节点。
未触发的警报是指带有警报器的节点但没有被
触发警报。
未触发的节点是指带有未触发的警报器的节点。
1.3 FPG 的数学描述
FPG 可以用数学的符号和集合关系来描述[2]。 每一
个顶点 v 至少有一条边 e让 νv1,…vn 表示一个部
件节点的集合εe1,…, en 表示错误传递。 Gs=ν, ε
表示一个系统的错误传递模型。 一些节点安装了警报
器 当某个节点发生了异常或者一个错误从之前的节
点传过来时那些警报器就会被触发。 让 αa1,…,an 表
示警报器的集合覬a1,…, an 表示激活的警报器的集
合。
输入的集合可以描述为节点 νv1,…vn变量序
列 v1<…<vn警 报 器 αa1,…, an当存在一个节点 v
v∈ν安装了警报器 aa∈α那么存在节点 v∈ν 警报
器 a∈α 并且 a∈覬。
输出的集合可以解析为可能出错的主要源头 Φ
for Gs=ν, ε。
1.4 FPG 的一个具体例子
由边和节点组成的 FPG 某些节点需要安装上警
报器警报器可以分为两类触发的和未触发的如图 1
所示
图 1 FPG 的一个例子
2 应用多重错误检测MFD算法
在 FPG 中应用多重错误检测算法步骤如下:
1识别所有的触发节点及其路径
①需要识别所有触发的节点和所有通向触发节点
的路径。 目的是为了识别存在于所有路径中的可能导
致警报器触发的单个节点或多个节点。 因为当错误出
现时所经过的有警报器的节点就会被触发。 此时错
误有可能会是由邻近的节点传递过来的 或者就是在
自身节点内产生且没有被消除掉。 错误如果在某个放
置了报警器的节点产生的 该节点的警报器就一定会
被触发。
由图 1 得知节点“g”和“k”是被触发了于是我们
得到连接这个节点的路径是 “b→f→k”, “b→g→k” 和
“a→c→g→k”如图 2 所示。
2识别所有与触发节点相连接的那些节点
在识别完所有触发节点及路径后 现在需要识别
触发节点的源节点。 源节点指的是可以到达触发节点
的那些节点。
如图 2a所示在路径“b→f→k” 中节点 “b” 可到
达触发节点“k”而未触发节点“f”可到达触发节点“k”。
趥趯
研究与开发
现代计算机 2011.10
如图 2b所示在路径“b→g→k”中节点“b”可到
达节点“g” 和 “k”。
如图 2c所示 在路径“a→c→g→k”中没装警
报器的节点 “a” 和 “c”可到达节点“g” 和 “k”。
a b c
图 2 连接触发警报的节点“g”和“k”的路径分别
是ab和c
3选择一条到达触发节点的路径
对于被认为是可能产生错误的路径 路径上的节
点都需要记录下来。 如图 2 可能产生错误的路径有
“b→f→k” “b→g→k”“a→c→g→k”。 当这些路径被
选择时需要记录的节点集合就是 {b, f, k}, {b, g, k},
和 {a, c, g, k}。
4去掉连接触发节点的未触发节点包括连接未
触发节点的边。
如果路径中的节点带警报器但是没被触发 它们
需要连同到达它们的节点一起被去除。
如图 2a所示, 节点“f”可以被去除因为当路径
“b→f→k”被选中时它是一个未触发节点。 节点“b”也
可以去除掉因为它是连接未触发节点“f”的。 那么在
路径“b→f→k”中剩下的节点集合为 {k}。
如图 2b所示当路径“b→g→k”被选中时因为路
径中没有未触发节点所以节点的集合记录为{b, g, k}。
如图 2c所示当路径“a→c→g→k”被选中时同
样路径中也没有未触发节点因此节点“a”, “c”, “g”
和 “k”被记录下来成为集合{a, c, g, k}。
5记录结果并找出错误来源
观察集合{k}, {b, g, k}{a, c, g, k}可以得到所有可
能的通往触发节点“g” 和 “k”的单源头节点集合为{a,
c, b}。
在图 1 中节点“b”是通往未触发节点“f”和已触发
节点“g”和 “k”。 节点“b”不大可能是错误的源头因为
如果它有一个错误的话就会同时触发两个节点“f” 和
“g”。 然而节点“f” 并不是一个触发节点。 所以在集合
{a, c, b} 中可以去掉节点“b”。 于是新的可能的错误来
源就是集合{a, c}了。
6完成分析后生成报表并记录应用 MFD 算法
的过程。表 1 就记录了图 1 中的 FPG 的应用 MFD 算法
分析的过程。
表 1 使用 MFD 算法分析图 1 的 FPG 的过程
3 用形式方法来描述 MFD 算法
形式方法是用一些数学的方法和符号来描述对象
的方法它准确而严谨。 为了推导 MFD 算法需要预先
定义一些属性类型。 这里使用了 Z3 语言来编写语句
定义 MFD 算法的属性和描述节点之间的边的关系。 属
性类型的包括同一关系、非反射闭合、反射闭包、传递
闭包、反射-传递闭包、关系映像、连接性[1]。
FPG 由一个节点集合[NODE]来建立, 是利用在节
点之间的存在关系的边建立错误传递路径的一种模型。
FPG 实际上是一个有向非循环图DAG即图中节点与
节点之间都是相连的且每个节点是没有环路通向自身
的节点之间的关系边形成了错误传递的路径。 图 3 用
形式语言描述了一个 FPG 的节点和有向边的关系。
图3 用形式方法来描述 FPG[1]
f
b
k
g
c
a
b
k
g
k
趥趰
研究与开发
现代计算机 2011.10
图 4 中的形式方法描述的是使用 MFD 算法识别
出图 1 的 FPG 中错误来源节点。 这段描述通过在 FPG
中选取了的路径、安装了警报器的节点和触发节点来
推测出错误来源的节点。 错误的来源节点最后被证明
是节点“a”和“c”。
图 4 对图 1 中的 FPG 使用MFD 算法识别错误来源
4 警报器放置的问题
在大型系统的每一个部件上都放置警报器是不现
实的因为那样将会花费很多时间和代价使系统的负
担越来越重且系统的运行速度变慢。 为了减少系统的
负担和不必要的开支 一些不是很重要或者出现冗余
的警报器会被去除以达到优化的目的。 这里就需要使
用一种有效的分析方法来选择节点来放置警报器。 这
样就能减少计算的代价 同时也保证了错误监测的精
确性和准确度。
既要在节点上有选择地放置警报器 又要保证警
报器的数量足以能够监测到潜在的错误。 我们可以采
用错误模式和后果分析方法FMEA, 它也属于严重程
度分析的一种方法。
使用 FMEA 可以识别出系统的各个部件以及这些
部件的失效模式。 每个失效模式对系统或者其他部件
造成的后果也会同样被识别出来。 FMEA 可以识别出
系统的各个部件的功能、失效模式、失效后果和后果严
重程度。 后果严重程度可以分为以下几个[4]
●灾难性的Catastrophic造成死亡或者系统完
全失败是最高级别。
●危急的Critical: 导致严重伤害或者系统大部
分损坏。
●轻度的Marginal: 致使少量伤害或者系统小部
分损坏。
●微小的Minor: 不会导致伤害或者系统损坏。
使用 FMEA 分析出系统部件的后果严重程度之
后最严重级别的部件会被最先放置警报器。 表 2 是一
个使用 FMEA 来分析燃气监测系统的部分组成部件的
例子。
表 2 使用 FMEA 分析燃气监测系统的部分组成部件
5 结 语
安全的监测已经被广泛应用到各种高安全需求的
行业中去 在这些行业的安全关键系统中加入错误监
测和错误来源识别的功能 可以最大可能地在错误发
生的早期检测到警报及时找出错误的源头采取措施
避免重大事故或灾难的发生。
FPG 是一种根据系统的功能和行为建立的一种图
形 它能展示系统的内部结构及系统的各个部件之间
的关系。运用 MFD 算法可以分析错误在 FPG 中的传递
方向和触发的节点 并按照算法的步骤来逐步识别出
错误来源的节点 无论错误的源头是单一的节点或者
是多个节点。 为了解决优化警报器放置的问题可以使
用 FMEA 方法来划分节点失效的后果严重程度 根据
严重程度的高低有选择地放置警报器 既保证错误不
会被漏检又减少了系统的负担