分布式随机离散事件系统的模式故障预测

金衍伟 刘富春 赵 锐 曹卫华 崔洪刚

（1.广东工业大学计算机学院,广东广州 510006;2.东源县科技创新中心,广东河源 517500）

1 引言

近年来,随着计算机信息处理技术,通信和传感技术的快速发展,工业系统规模越来越大,系统的运行难免会出现故障.为保证系统可靠性,控制工程师应设计一个能在正常范围内安全运行的系统,并在系统故障发生前,尽可能预测出即将发生的故障,以采取相应措施,对故障进行规避.因此,对离散事件系统预测问题的研究具有重要的研究意义.在文献[1]中,通过构造一个从字符串到语言的投影函数来研究串预测问题.Genc在文献[2]中研究了不完全可观下离散事件系统的故障事件的预测.文献[3]研究了基于带标签的Petri网的故障预测问题.Chen和Kumar在文献[4]中将文献[3]的方法推广至随机离散事件系统,引入了m步可预测的概念来表示系统在故障事件发生前的m步作出预测的能力.

上述研究都是针对集中式系统的故障预测.然而,大型复杂系统往往是分布式的,这使得近年来针对分布式系统的预测算法得到广泛重视.Kumar等人提出了一种分布式预测方法[5],该方法引入联合预测能力的概念来描述通过分布式站点可以预测出所有故障的情况.Yin将该框架进行了拓展,对其性能边界及可靠性进行了研究,提出两种基于状态的分布式协议来研究分布式离散事件系统的预测问题[6—7].本文则在文献[8]中提出一种基于多项式验证器的分布式离散事件系统的离线故障预测算法.

值得指出的是,在实际应用中,系统的故障行为可以是单个错误事件,也可以是多个事件组成的事件串（称为模式故障）.为此,2006年,Jeron等在文献[9]中首次提出了离散事件系统模式故障的概念.而针对单个错误事件的传统故障预测方法也不再适用.文献[10]研究了经典离散事件系统的模式故障预测.本文也对基于模式的安全故障诊断[11]开展了相关研究.

注意到,关于分布式随机离散事件系统的模式故障预测研究仍未见报道.离散事件系统的模型有自动机、概率布尔网络[12—13]、随机有限域网络[14]等.本文以随机自动机为例,将文献[4,8,10]的故障预测方法拓展到分布式随机离散事件系统的模式故障预测中.先对分布式随机离散事件系统的模式故障可预测性进行形式化.通过构造模式故障识别器,得到一个模式故障预测的协同预测器,并提出基于协同预测器的分布式随机离散事件系统模式故障可预测的充分必要条件,然后提出了判断分布式随机系统是否具有模式故障可预测性的算法,并对其复杂度进行分析,得出该算法为多项式时间复杂度的结论.

2 分布式随机离散事件系统

一个随机离散事件系统[4]可用带有概率结构的有限状态自动机（finite state automation,FSA）来表示G=(X,Σ,δ,x0),其中X为有限状态空间,x0∈X为初始状态,Σ为有限事件集,δ:X ×Σ×X →[0,1]为状态转移概率函数:对任意x,x′ ∈X且σ ∈Σ,δ(x,σ,x′)表示状态x经过事件σ转移到状态x′的概率,它满足∀x ∈X,

事件集Σ可以分为可观事件集Σo和不可观事件集Σuo,即Σ=Σo∪Σuo.记Σ*为所有有限长事件串的集合,且包含空串ε,Σn表示n个事件组成的事件串集合.为简便起见,用δ(x,σ)来代替δ(x,σ,x′),并定义

其中:δ(x,σ,x′)＞0,s ∈Σ*.称X的子集X′,如果δ(X′,Σ)⊆X′,则称X′是稳定的.如果对任意x ∈X,都有Σ(x)=Σ,则称G是完备的,其中

对于事件串s,用pref(s)表示s的所有前缀,用|s|表示s的长度.对于给定的语言L1和L2,它们的连接为L1L2:={st:s ∈L1,t∈L2}.用L(G)或L表示G产生的语言,它是由正概率事件串的集合,即

对于有m个站点的分布式系统,站点投影Pi:Σ*→定义为Pi(ε)=ε,且对于任意的σ∈Σ,s∈Σ*,Pi(sσ)=Pi(s)Pi(σ),其中:

下面给出随机离散事件系统的模式故障的定义:

定义1系统G=(X,Σ,δG,x0)的模式故障定义为有限状态自动机Ω=(QΩ,Σ,δΩ,q0,FΩ),并称之为G的模式故障自动机,其中QΩ是Ω的状态集,FΩ是接收状态集,δΩ:QΩ×Σ →QΩ是Ω的转移函数.称Ω具有确定性,如果∀q ∈QΩ,∀σ ∈Σ,由δΩ(q,σ)=q′和δΩ(q,σ)=q′′可推出q′=q′′.记为到达接收状态的语言,G的模式故障语言定义为L(G)∩

3 模式故障协同可预测性的形式化

下面先构造模式故障识别器,以识别发生在系统G中的模式故障语言.

定义2给定系统G=(X,Σ,δG,x0)及其模式故障Ω=(QΩ,Σ,δΩ,q0,FΩ),构造模式故障识别器

例1考虑如图1所示的随机自动机G=(X,Σ,δG,x0),其中初始状态x0=0.

图1 一个随机自动机GFig.1 A stochastic automaton G

设有两个站点投影Pi:Σ* →i ∈{1,2},其中Σo,1={a,b,c},Σo,2={a,b,e}.

设其模式故障自动机Ω=(QΩ,Σ,δΩ,q0,FΩ)如图2所示.

图2 一个模式故障自动机ΩFig.2 A pattern fault automaton Ω

根据G和Ω,可构造模式故障识别器GΩ=G×Ω如图3所示.

图3 一个模式故障识别器GΩ=G×ΩFig.3 A pattern fault recognizer GΩ=G×Ω

定义3 设G有m个分布式站点,定义为站点i在观测到事件o ∈Pi(L)之后的n步之内不会出现模式故障的概率.为在分布式站点i观察到事件串o ∈Pi(L)之后有限步内不会出现模式故障的最小概率,即

其中LK=L(G)-Lm(GΩ).

定义4对于L(G)和Lm(GΩ)给出以下定义:

1）边界模式故障串集

2）先驱串集

3）永无模式故障串集

4）指示器无模式故障串集

5）非指示器无模式故障串集

直观上,∂表示所有已发生模式故障但其前缀无模式故障的事件串组成的集合;℘中的先驱串表示再经过一个事件就可能会发生模式故障;ℵ中的永无模式故障串表示即使再经过任意步长的串也不会发生模式故障;ℑ表示所有后续不发生模式故障的概率充分小的串组成的集合;Υ则与ℑ在LK中是互补关系,即Υ=LK -ℑ.

同时在模式故障识别器GΩ中有如下定义:

1）先驱状态集是指GΩ中(x0,q0)经过所有先驱串s ∈℘到达的状态集,即

2）非指示器无模式故障状态集是指GΩ中(x0,q0)经过所有非指示器无模式故障串s ∈Υ所到达的状态集,即

接下来,本文介绍模式故障协同可预测的定义.

定义5随机离散事件系统G关于模式故障自动机Ω和分布式站点投影Pi:Σ* →i ∈I={1,2,···,m}具有模式故障协同可预测性是指下式成立:

直观上,具有模式故障协同可预测性的系统G表示对任意阈值ρ和τ,系统内属于边界模式故障串集∂中的事件串s,其任意前缀u在所有分布式站点i ∈I观察到事件串Pi(u)之后的判断为“有限步内不会出现模式故障”的最小概率都大于ρ的可能性小于τ.

根据系统模式故障协同可预测性的定义,可以得到与之等价的引理1.

引理1随机离散事件系统G关于模式故障自动机Ω和分布式站点投影Pi:i ∈I具有模式故障协同可预测性,当且仅当

必要性:反证法证明.假设G具有模式故障协同可预测性,并且存在s′ ∈∂,使得∀u ∈pref(s′)-s′,∀i∈I,则有

根据定义5,该系统不是模式故障可预测的,这与假设相矛盾.证毕.

注1引理1中的式（3）表示系统内所有属于边界模式故障串集∂中的事件串s,都存在其前缀u,存在分布式站点i ∈I对其投影相同且无模式故障的串都属于指示器无模式故障串集ℑ.

定理1随机离散事件系统G关于模式故障自动机Ω和分布式站点投影Pi:i ∈I具有模式故障协同可预测性,当且仅当

证因为Υ=L-Lm(GΩ)-ℑ,可将式（4）变为

充分性:若式（4）成立,∀s ∈℘,{s}Σ∩∂/=∅.因此,∀s′ ∈∂,∃s ∈pref(s′)-s′,∃i ∈I,有

根据引理1可得该随机离散事件系统G具有模式故障协同可预测性.

必要性:利用反证法.假设系统G关于模式故障自动机Ω和分布式站点投影Pi:Σ* →i ∈I具有模式故障协同可预测性,并且存在s ∈℘,对任意的i∈I,有则存在s′∈使得s′ ∈Υ,则

对于任意的u ∈pref(s),存在u′ ∈pref(s′),使得u′∈并且

则可得u′ ∈Υ.因此,若所有分布式站点对串s的观测不都属于指示器无模式故障串集ℑ,则对其前缀的观测也不都属于指示器无模式故障串集ℑ.根据引理1,该系统不是模式故障协同可预测的,则反之成立.

证毕.

注2定理1中式（4）表示系统G具有模式故障协同可预测性,系统内所有属于边界模式故障串集∂中的串s,均存在分布式站点i ∈I对其投影相同的串与非指示器无模式故障串Υ不存在交集.

4 模式故障协同可预测性的判定算法

本节将构造一个以经典自动机为模型的模式故障协同预测器,并在此基础上提出一个具有多项式复杂度的模式故障协同可预测性的判定算法.

下面先构造一个模式故障协同预测器,步骤如下:

步骤1对给定的随机离散事件系统G=(X,Σ,δG,x0)及其模式故障自动机Ω=(QΩ,Σ,δΩ,q0,FΩ),构造模式故障识别器GΩ=G×Ω.

步骤2构造GΩ的协同预测器为一个非确定型自动机GV=(QV,ΣV,δV,ϱ0),其中QV=是GV的状态集,初始状态为

δV:QV×ΣV→QV为转移函数.为简单起见,本文在只考虑|I|=2的情况,定义δV:QV×ΣV→如下:对任意的ϱ=((x0,q0);(x1,q1);(x2,q2))∈QV和σ ∈ΣV分以下4种情况:

定理2随机离散事件系统G具有模式故障协同可预测性当且仅当在协同预测器GV中第1分量为(x0,q0)∈℘(X ×QΩ)的所有状态

均存在i ∈I使得(xi,qi)/∈Υ(X ×QΩ).

证充分性:通过构建协同预测器GV的过程可以得到,对于任意的s ∈L和s′ ∈LK,若存在i ∈I使得Pi(s)=Pi(s′),那么当且仅当在协同预测器GV中存在状态ϱ=((x0,q0);(x1,q1);···;(xm,qm))使得有s,(x0,q0))和s′,(xi,qi))均大于0,所以在GV中第1分量(x0,q0)∈℘(X×QΩ)的所有状态ϱ=((x0,q0);(x1,q1);···;(xm,qm))均存在i ∈I使得(xi,qi)/∈Υ(X×QΩ),即

根据定理1,G是模式故障协同可预测的.

必要性:反证法证明.若存在

使得(x0,q0)∈℘(X ×QΩ),并且对任意的i ∈I都有(xi,qi)∈Υ(X ×QΩ),则在GΩ中必有s,(x0,q0))和δG×Ω((x0,q0),s′,(xi,qi))均大于0,且Pi(s)=Pi(s′),使得根据定理1可得,G不是模式故障协同可预测的.证毕.

算法1分布式随机离散事件系统模式故障的协同可预测性判断算法.

输入:分布式随机离散事件系统G=(X,Σ,δG,x0)及其模式故障自动机Ω=(QΩ,Σ,δΩ,q0,FΩ).

输出:该分布式随机离散事件系统G是/不是模式故障协同可预测的.

步骤1构造模式故障识别器GΩ=G×Ω,并计算GΩ中的先驱状态集℘(X ×QΩ)和非指示器无模式故障状态集Υ(X ×QΩ).

步骤2构造GΩ的协同预测器GV=(QV,ΣV,δV,ϱ0),其第1分量为GV执行的转移,其第i+1个分量为执行在分布式站点i投影后与第1分量无差别的转移.

步骤3检查GV中第1分量属于先驱状态集℘(X ×QΩ)的ϱ,是否均存在i ∈I使得

若是,则输出系统G为模式故障协同可预测的.否则,输出G不是模式故障协同可预测的.

复杂性分析:给定的随机自动机G=(X,Σ,δG,x0)及其模式故障自动机Ω=(QΩ,Σ,δΩ,q0,FΩ)设|X|=n1,|QΩ|=n2,|Σ|=n3,分布式站点数|I|=m.首先,根据算法1,构造模式故障识别器GΩ=G×Ω,状态数为O(n1n2),转移数为O(n3).因此,协同预测器的状态最多为(n1n2)m+1.由式（5）—（8）可知,每个状态最多有(m+2)n3个转移,因此该模式故障协同预测器构建的时间复杂度为且在步骤2中,计算出先驱状态集℘(X ×QΩ)的时间复杂度为O(n1n2n3).另外,利用文献[15]中的算法,通过确定在GΩ中的所有无模式故障且封闭的强连通分量,计算ℑ的复杂度为因为Υ=LK -ℑ,所以计算Υ(X×QΩ)的时间复杂度也为于是得到算法1的时间复杂度为

5 实例分析

下面在遵循匿名性协议的计算机网络集群系统的安全性设计中考虑其模式故障可预测性.

在计算机网络集群系统中,匿名性协议是用来保护信息发送者身份的协议.当一个发起者决定发送一个信息给网络服务器并同时想隐藏这个信息的来源时,可通过集群系统将信息等概率路由给系统中的其他用户.当集群系统中一个用户收到这个信息,其可选择将信息发送给网络服务器或集群系统的另一个用户,这样则可避免网络服务器识别信息来源.但是,在集群系统中,有一些用户在接收信息时,可能会丢失信息的头文件.其中头文件中含有该信息的发送地址,导致不明该信息的去向,而将信息一直留在本地.由于本地主机的漏洞存在,最终可能导致信息被木马窃取.如果将“丢失信息头文件并随后该信息被木马窃取”视为一个模式故障,则本文考虑的问题是:对于一个给定计算机网络集群系统（如图4所示）,能否提前预测该模式故障的发生以采取相应预防措施?

图4 一个计算机网络集群系统Fig.4 A computer network cluster system

考虑如图4所示的4个用户的计算机集群系统,其中可能会造成头文件丢失的用户为用户2和用户4,并设其有3个状态,分别为接收信息、丢失信息的头文件以及信息被木马窃取,其中信息被木马窃取是接收状态,表明模式故障已经发生.由于用户的本地日志分享有局限性,每个用户只能看到当前自己主机及其相近主机的操作日志,所以可以将该系统看作是分布式系统.假设该集群系统用如图5所示的自动机来描述,可以将系统对操作日志的观测看成由两个分布式站点的投影Pi:Σ* -→i ∈{1,2},其中:

图5 自动机GFig.5 Automaton G

bf为模式故障,事件描述及概率转移如表1所示.

表1 计算机集群系统的事件描述及其生发概率Table 1 Event description and occurrence probability of computer cluster system

因此可以得到如图6所示的模式故障自动机Ω,其中包含模式故障bf的边界模式故障串集

图6 模式故障自动机ΩFig.6 Pattern fault automata Ω

下面利用算法1求解.根据系统G与其模式故障自动机Ω=(QΩ,Σ,δΩ,q0,FΩ)构造模式故障识别器GΩ=G×Ω如图7所示,并计算出先驱状态集

图7 模式故障识别器GΩFig.7 Pattern fault recognizer GΩ

和非指示器无模式故障状态集

根据步骤2,构造协同预测器GV如图8所示.最后,检查GV中第1分量属于先驱状态集的ϱ,有

图8 模式故障协同预测器GVFig.8 Pattern fault coprognoser GV

均存在i ∈{1,2}使得(xi,qi)/∈Υ(X ×QΩ).根据定理2可知,该系统是模式故障协同可预测的,这表明对该系统中存在至少一个站点能够对任意因为信息头文件丢失导致信息被木马窃取这种模式故障在其发生之前将它预测出来.因此,本文在设计这样的计算机集群系统时,可以通过算法1来判断所设计的系统是否能够对诸如“丢失信息头文件并随后该信息被木马窃取”的模式故障进行预测.一旦预测到模式故障将要发生,则可以在信息被窃取前采取相应的控制手段（如在一段时间检测不到信息头文件之后,将信息删除,以免造成更大的损失）,以规避模式故障的发生.

6 总结

本文对分布式随机离散事件系统的模式故障预测进行了研究.本文将模式故障定义为一个自动机,并将其与系统结合组成一个模式故障识别器来进行模式故障预测.再用各站点观测到模式故障识别器的行为组成一个协同预测器来进行分布式预测,降低了集中式模型的复杂性.同时,提出模式故障协同可预测的充分必要条件及其相应的协同可预测算法,从而解决分布式随机离散事件系统中模式故障的预测问题.