一种基于时间自动机的可生存性评估方法1.doc

《一种基于时间自动机的可生存性评估方法1.doc》由会员分享，可在线阅读，更多相关《一种基于时间自动机的可生存性评估方法1.doc（9页珍藏版）》请在三一办公上搜索。

1、精品论文推荐一种基于时间自动机的可生存性评估方法1刘金亮，谭国真 大连理工大学计算机科学与工程系，大连 (116024) E-mail：jinliangl摘要：计算机系统在社会中发挥着重要作用的同时，人们对计算机系统的可生存性要求也 越来越高，而如何评价和提高系统的可生存性已成为一个重要的研究问题。本文介绍了可生存性和可生存性评估的基本概念，在 SNA(Survivable Network Analysis)方法的基础上，给出了一种系统可生存性的评估框架，重点介绍了一种基于时间自动机模型，利用时间自动机在 描述系统时间约束方面的优势，分析系统关键服务在各种威胁条件下的实时响应能力并量化 系统可

2、生存性的评估方法，并通过实验验证了本文所给出的生存性评估方法的可行和有效 性。最后对本文进行了总结，指出下一步工作的重点。 关键词：可生存性；时间自动机；量化分析方法；实时响应中图分类号：TP302.71引言可生存性是由Barnes等人于1993年提出来的概念1。可生存性其实不是一个新的概念名 词，在军事2和电信领域3早已出现并使用。但是可生存性的定义目前还没有形成统一的表 述。影响最大的是CMU/SEI的研究小组给出的定义4,5,6：可生存性是指在遭受攻击、故障或 意外事故时，系统能够及时的完成其关键任务的能力。目前对可生存性的定义还没有统一， 但是这已不是可生存性研究的重点，当前可生存性研

3、究的热点集中在两个方面：系统可生存 性增强技术研究和系统可生存性评估研究等。对系统可生存性进行评估，是对系统进行后续 可生存性研究工作的前提条件和首要参考标准。可生存性评估的目的是对系统进行分析，评估其生存性，衡量系统在不安全环境中提供服务的能力，提供系统的生存性信息及增强系统生存性的推荐策略。按照分析方法分类，系 统可生存性分析主要有定性和定量两种方法。定性分析方法是根据研究者的知识、经验、历 史教训和特殊变例等非量化资料对系统的安全状况做出判断的过程。定量分析方法是一种比 较精确的可生存性分析方法，一般采用数量指标对网络系统的可生存性进行评估。采用定量 分析方法能够使研究结果更科学、更严密

4、、更深刻。对可生存性评估的研究，国外特别是美 国的研究开展的较早，研究成果也比较多。Louca7将原始网络拓扑转化为一个Trellis图，利 用图论通过在Trellis图上查找k-best和最短路径来表述网络生存性问题；Jha8基于系统网络 结构，将系统网络中的每个节点及链路都用一个有限状态机来表示，综合利用模型检查、贝 叶斯分析以及概率系统等数学方法进行定性和定量分析；Gao9基于每一个系统服务，利用 一些关键规格来描述其生存性，通过一定的分解，将整个系统的生存性通过各个组件的生存 性来表示，最后形成一种树状模型。国内可生存性研究尚属起步阶段，西安电子科技大学的 郭渊博10利用分布式系统中服

5、务与配置及配置与配置之间的支持与依赖关系，通过对配置 的定量描述来定量刻画服务的可生存性；国防科技大学的黄遵国11等对可生存性技术及实 现框架进行了研究；哈尔滨工业大学的包秀国12等用割集和Monte-Carl模拟的方法分析了网 络信息系统的可生存性。可生存性概念主要关注的是系统的关键服务在各种事件的威胁下，仍然能够及时完成的 能力，其中“及时”强调了系统对关键服务响应时间的要求，现实中的许多系统，特别是关键 基础设施，例如交通运输、金融、电力资源等系统，对系统的实时响应能力要求更高。而当1本课题得到国家重点基础研究计划(973)（项目编号：2005CB321904）的资助。-3-前的可生存性

6、分析方法对系统时间约束处理存在不足，部分评估方法甚至完全忽略了系统可生存性概念中这个关键属性。本文给出了一种基于时间自动机模型的可生存性评估方法，利 用时间自动机在描述系统时间约束方面的优势，结合K最短路径方法分析系统在各种威胁条 件下，关键服务的实时响应能力来评估系统生存性。2可生存性评估框架可生存性评估过程是一个复杂的工程，有必要给出一个规范的分析框架，以此来指导具 体的分析过程。在现有的分析框架中，美国卡耐基梅隆大学提出的SNA(Survivable Network Analysis)5分析方法曾成功地对一些商业和政府的系统进行生存性分析13,14，为生存性分析 提供了一套可行的思路和可

7、供参照的实践经验。本文在SNA分析框架的基础上给出了适合本 文基于时间自动机模型评估方法的分析框架。具体分析流程如图1所示：图 1 可生存性分析框架Fig.1 Analysis Framework of Survivability2.1 生存性需求定义根据具体服务需求、系统运行环境和资金预算来决定系统需要的生存性级别标准。以此 为基准对比实际的生存性分析结果，从而判定系统是否达到其生存性要求。2.2 建立系统模型根据系统设计说明书和系统拓扑图，以系统服务需求为依据，简化系统物理模型。在 此模型基础上，分析物理组件与系统服务的关联，给出对应的系统逻辑模型。这阶段主要是 建立系统的服务与逻辑组件以

8、及逻辑组件与物理组件之间的映射关系。建立系统的事件库和 受到的威胁库，事件库中的事件是可以使系统的状态发生变化的事件。威胁库是指系统运行 中可能遭受到的各种攻击、故障、意外等威胁事件集合。2.3 定义关键服务定义出关键服务和次要服务，用于后续的量化计算和分析。由于分析系统的可生存性时， 主要是面向系统的关键服务，所以定义出系统的关键服务和次要服务，会让整个评估结果更 准确。根据系统的生存性需求定义，定义系统的关键服务集合SESES1,ES2,ESn，定义关 键服务ESi对应的事件集SEESi，SEESi中的事件是对关键服务ESi的执行产生影响的事件。同时 根据各关键服务对系统的重要性，确定各关

9、键服务ESi对系统的权重Wi。2.4 受威胁定义根据系统关键服务的运作流程、运行环境、日常入侵及故障情况来分析系统缺陷，针对 每个关键服务ESi确定对其造成损害的威胁集，组成该关键服务的威胁集SFESi，根据威胁事 件的类型以及威胁的常见性、实现的难易程度、威胁危害的程度等信息确定相应的威胁事件 对关键服务ESi的影响权重FWi。2.5 可生存性测试在以上的分析中，定义了系统运行过程中可能受到的威胁事件的威胁库。系统在运行时 会遭遇各种不同的威胁，这些威胁随着环境的不同而改变。根据当前系统的威胁库，可以生 成有针对性的生存性测试方案。并对系统的逻辑组件和物理组件进行测试，以确定系统信息。2.6

10、 可生存性量化分析和评估一个系统的可生存性，要先对所要分析的系统进行建模，提取和概括出主要 的系统特征和必要的系统信息，用于下一步的可生存性分析和计算。系统可生存性主要特征 是：系统关键服务的生存能力，即：不论系统采用了何种策略，系统在外部事件发生的情况 下持续、及时的提供关键服务的能力。为了得到系统这一方面的属性值，通常用自动机模型 来描述系统在外部环境的影响下所产生的变化，从而进行分析和计算，但是用传统的自动机 模型描述系统状态时，往往忽略了系统在时间约束方面的要求，而时间约束对于系统可生存 性而言是一个十分重要的属性，本文采用时间自动机对系统的状态进行描述，并在此基础上 给出了系统可生存

11、性量化方法，详细计算过程在下一节中介绍。2.7 结果分析报告根据计算结果产生生存性评估结果报告，包括对系统生存性的数值化表述，对比系统的 生存性需求，可判定系统的生存性设计是否达到了要求，以及系统改进建议等内容。3可生存性量化分析方法3.1 建立系统模型从可生存性定义中可以看出，可生存性强调关键服务的实时响应能力，对服务有时间约 束方面的要求，而时间自动机具有表达时间约束的优势，因此本方法使用时间自动机建立系 统模型。时间自动机的语义和语法定义如下15,16：时间自动机TA 可表示为六元组 (S , S0 , , X , I , E ) ，各元素涵义如下：(1) (2)(3)S ：有限状态的集

12、合；S 0 ：是初始状态的集合，是 S 的子集； ：是有限事件或指定信息的集合；(4) X ：时钟的有限集；(5)I ： S 中带有 ( x) 的时钟约束值的状态 s 的映射；(6) E ： E S 2 X ( X ) S 为状态转换的集合。 (s, a, , , st ) 状态转移表示系 统在事件 a 驱动下，可从状态 s 转移到状态 st ， 为 X 上的时钟约束条件，集合 X 表示这一状态转移将要复位的时钟。时间自动机TA 的语义为：与状态转移系统 STA 相关的任一 STA状态由 (s, v) 表示，其中：(1) s ：TA 的某一状态；(2)v ：约束时钟；精品论文推荐-9-(3)v

13、 I (S ) ， I (S ) 是不变式。TA 的全部状态的集合为 QA ，TA 的初始状态 (s, v) 可表示为 s0 ，其 s = s0 ， v( x) = 0 。STA 有如下两种转移类型：(1)由于时间流逝而使状态发生转移。对一个状态 (s, v) 和一个实数的时间增量 0 ，如果对所有的 0 ， v + I (S ) ，则有 (s, v) (s, v + ) ；(2) 由于满足事件要求而发生状态转移。对于状态 (s, v) 和 (s, a, , , st ) 有 v ，(s, v) a(st , v := 0) 。因此 STA 是具有 R 事件集合的状态转移系统。使用时间自动机中

14、的时钟变量表示系统执行某项服务耗费的时间，通过这种方式描述系统的响应时间约束。使用时间自动机模型对系统建立模型的步骤如下：(1)(2)定义 S 和 ：根据系统说明，分析系统特征。定义系统有限状态集合 S 和引起系统 状态发生转换的有限事件集合 。以系统的服务和用户需求为主线，忽略与系统关键服务分析联系不大的状态和事件，简化时间自动机模型；定义关键服务的开始状态和结束状态：确定系统的开始状态，根据定义的系统有限 状态集合 S 定义关键服务集SES中所有关键服务ESi的服务开始状态和完成状态；(3) 定义时间约束条件：根据系统说明的要求，定义对相应事件执行中的时间约束条件。在以上分析及定义的基础上

15、，建立系统自动机模型，需要指出的是在上面介绍的步骤(2)中，定义的系统关键服务的开始状态和完成状态是为了后续计算过程做的准备。3.2建立时间自动机模型的域图时间自动机中的状态是无穷的，无法用时间自动机的状态构建一个系统的自动机模型，区域自动机是通过在状态空间上定义一个等价类来将无穷多状态划分为有穷的状态，其时钟 区域的划分是要求时间的整数部分一致，并且所有时钟间的小数部分的变化顺序也一致。通 过转化为区域自动机，使得时间自动机中无穷的状态转化为了有穷的状态，简化了量化分析 方法的复杂性。转换方法如下15,16,17：一个时间自动机 TA = (S , S0 , , X , I , E ) 所对

16、应的区域自动机 R(TA) 是定义在字符集 上的一个如下所示的转换系统，(1)R(TA) 的每一个状态都形如s, ，其中 s S ， 是一个时钟区域；(2)R(TA) 的起始状态形如s0 , v0 ，其中 s0 S0 ，并且 x X ， v0 ( x) = 0 ；R(TA) 中有一个状态转移s, , a,s , 当且仅当时间自动机 TA 中存在一个转 移s, a, , , s E 并且存在一个时钟区域 a 满足以下三个条件： a 是 的时间后继； a 满足时钟约束 ； a = 6 0 a 。3.3K 最短路径对系统 ES 集中的关键服务在各种事件威胁下的提供能力进行量化，可以得到系统生存性的直

17、观的描述。 系统中某种服务的开始与结束，在系统的时间自动机模型中表现为：从时间自动机中某一个或某几个特定状态开始，经过一定的状态转移，成功到达某个特定状态-该服务结束的 状态。当系统遭受某种事件Fi威胁时，Fi对应的关键服务集中的关键服务受其影响，服务的 实现将发生变化。在时间自动机模型中表现为与该关键服务相关的系统状态迁移路径的改精品论文推荐变。因此通过对关键服务ESi的各种实现方式中的执行能力的描述，然后对各种实现方式下的执行能力进行综合评定，就可以得到ESi的在系统中实时响应能力的评价。使用相同的方 法对系统关键服务集中的所有关键服务在各自受影响的事件威胁下的提供能力的评价，同时 综合考

18、虑各关键服务在系统不同环境中的权重信息，就可以实现对系统的生存能力的评估。在本文中我们采用求K条成功完成关键服务ESi功能的概率最大的实现路径，对关键服 务进行综合评价，K是一个变量，可以从系统需求、系统环境需求以及对关键服务生存性需 求等方面综合评定，灵活控制K的取值。对某关键服务的K种期望最大的实现路径的分析， 可以相对准确的实现对关键服务提供能力的评价。通过将时间自动机模型中的时间变量离散化，我们得到了一个区域自动机模型。将区域自动机中的状态s, 视为一个结点，状态之间的迁移视为一条弧，我们就得到了一个描述系统状态转换的图模型。结合生存性分析框架中生存性测试阶段获得的数据，通过以下方法

19、得到有权图模型，方法如下：对每一个域图中的结点s, ：i(1) 存在迁移事件aij的迁移边，根据事件aij发生的实际概率Pij值；(2)不存在迁移事件的时间流逝迁移边，根据其他存在迁移的边的概率之和，通过约束 条件；每个状态发出的所有迁移的概率之和为 1，可以求出时间流逝迁移边上的概 率。通过将迁移边上的权值设置为概率值的倒数(概率为零时，取无穷大)，求从关键服务ESi 开始状态到ESi完成状态之间的K最短路径，可以得到关键服务ESi成功完成该服务的概率最 大的K种实现方式。算法描述如下，其中：扩展节点表示上一条最短路径上的节点可能会在 求取下一条最短路径的过程中进行扩展 ，也就是在上次节点集

20、合的基础上增加相应的新节 点，这些新的节点均称为扩展节点，一个扩展节点仍然可能会在求取下一条最短路径的时候 进行扩展，前驱节点表示最短路径中某个节点的前一个节点：(1) (2) (3)(4)(5)利用 Dijkstra 算法求得有向图(N,A)中以开始节点 s 为根的最短路径树，标记从开始 节点 s 到结束节点 t 之间的最短路径为 pk，k=1；如果 k 小于要求的最短路径的最大数目 K，并且仍然有候选路径存在，令当前路径p=pk，转(3)。否则，程序结束；找出当前路径 p 中从第一个节点开始的入度大于 1 的第一个节点，记为 nh。如果 nh 的扩展节点 nh 不在节点集 N 中，则转(4

21、)，否则找出路径 p 中 nh 后面所有节点 中，其对应的扩展节点不在 N 中的第一个节点，记为 ni，转(5)；为节点 nh 构建一个扩展节点 nh，并把其添加到集合 N 中，同时从图(N,A)中所有 nh 的前驱节点连接一条到 nh 的弧，弧对应的权重不变，添加这些弧到弧集 A 中， 但 nh 在 p 中的前一个节点 nh-1 除外。计算从开始节点 s 到 nh 的最短路径，并记 ninh+1；对于 p 中从 ni 开始的所有后续节点，不妨记为 nj，依次执行如下操作：Step1: 添加 nj 的扩展节点 nj 到节点集合 N 中；Step2: 除了路径 p 中 nj 的前一个节点 nj-

22、1 外，分别连接一条从 nj 前驱节点到其扩 展节点 nj 的弧，弧上的权值保持不变，并把这些弧添加到弧集 A 中。另外， 如果 p 中 nj 的前一个节点 nj-1 具有扩展节点 nj-1 的话，也需要连接一条从 nj-1 到 nj 的弧，权值和弧(nj-1 , nj)的权值相等；(6)Step3: 计算从开始节点 s 到 nj 的最短路径；更新当前最短路径树，求得从开始节点 s 到结束节点的当前扩展节点 t(k)之间的最 短路径为第 k 条最短路径，令 k=k+1，转(2)继续。3.4生存性计算根据上节的计算，我们就可以得到实现某一关键服务在系统中 K 条成功完成服务的概率最大的执行路径，

23、即：求出了该关键服务在系统中的 K 种实现方式以及相应路径的执行 事件，以此为基础，我们可以进一步对系统的生存性进行评估。设某关键服务ESi的K期望路径分别为集合SPip1,p2,pk，设其中路径pi对应的成功完 成的概率为pesi，执行时间为tesi，则关键服务ESi服务能够成功完成的概率的计算公式为：PESi =iSPpesi(1)而服务的期望执行时间的计算公式为：TESi =iSPpesi tesi(2)通过以上两个公式的计算，可以得到系统中关键服务集ES中各关键服务的响应能力和 执行时间，因此通过与系统生存性需求定义中确定的各关键服务的提供能力和执行时间进行 比较，就可以得到所评测系统

24、中各关键服务的执行能力，假设系统生存性需求中关键服务 ESi的期望完成概率为EPESi，期望执行时间为ETESi，则评估公式如下：PerESi =(PESi TESi ) (EPESi ETESi )(3)服务的提供能力与实现的概率成正比，与执行时间成反比。将计算所得的提供能力值与执行时间的比值，和系统生存性定义中期望的提供能力与期望执行时间的比值进行比较，可 以直观的得到系统中该关键服务的执行能力。在建立系统模型阶段中建立了影响系统状态发生转移的事件与各种威胁事件之间的映 射，因此通过对系统中某服务相关事件的分析，即可得到系统处理各种威胁事件的能力。因 为系统中应对各种威胁事件的处理过程在模

25、型中都以状态之间迁移的形式表达出来，即：系 统的时间自动机模型描述了系统的行为，在模型中系统状态之间的迁移就是对系统的行为的 描述。因此对模型中的各事件的分析，可以实现对系统处理各种威胁事件的分析。假 设 关键服 务 ESi 的 威胁集 为 SFESi=f1,f2, ,fk ；对应的 威 胁权值为 SWFESi=w1,w2,wk；ESi的事件集为：SEESi=e1,e2,em，集合中为引起系统状态转移的事件；各事件对应的威胁集为：SFei SFESi；设关键服务对应的所有事件集SEESi对应的威胁集合的并集为：SFEESi=f1,f2,fn，集合SFEESi中各威胁对关键服务ESi的威胁权重分

26、别为fw1,fw2,fwn,则，关键服务处理各种威胁事件的能力定义如下：nCESi = fwii =1(4)权值CESi表示的是服务在执行过程中，提供了处理方式的相应威胁的威胁权值之和。这个值直观的表示了服务处理过程中对各种威胁事件的应变能力。 下面将对如何计算系统的生存性给出一个生存性函数，该生存性函数和其它文献度量系统生存性的方法不同的是，它通过系统提供关键服务的生存性来描述系统的生存性，因为当 系统能提供关键服务的能力恰恰是系统生存性的体现。在系统的关键服务集ES中，各种关键服务是有区别的，因此根据它们在系统中的重要性的不同，给不同的关键服务赋予不同的权值是合理的。在对某个特定的的关键服

27、务，将表示服务执行能力的因子PerESi与服务重要性的权值Wi相乘，这个值就描述了该服务的实时可 提供程度，由此给出生存性函数的定义如下：3.5Surv =生存性分析ESi ESCESi PerESi Wi (5)结合在建立系统模型阶段中确定的系统服务与逻辑组件以及逻辑组件与物理组件之间 的映射关系，可以将服务的某一条执行路径与系统的逻辑组件和物理组件之间建立联系。通 过对某一个系统转移路径的分析，可以建立对系统各逻辑组件以及物理组件的评估。通过这 样的评估过程可以找到对系统的生存性影响最大的逻辑组件以及物理组件集合，以及系统中 待改善的脆弱点。4. 实验结果与总结为验证本方法的可行性和有效性

28、，以对本实验室开发完成的单路段交通流预测系统中实 时交通数据获取子系统进行可生存性评估实验。实时交通数据子系统负责收集路口控制单元 的交通数据，是交通控制系统中实时自适应信号控制、动态交通分配、路径诱导等模块正常 工作的基础，但是由于交通信息采集物理部件故障、数据传输网络遭受攻击、堵塞、数据包 丢失、数据库发生意外等影响实时交通数据采集子系统的正常工作，因此提高实时交通数据 采集子模块的可生存性十分重要。交通数据获取子系统的关键服务如表 1 所示：表 1 关键服务描述Tab.1 Description of essential service关键服务关键服务描述W(权重)ES1获取实时路段数据

29、0.9ES2数据预处理0.1系统的威胁事件包括f1：传感器故障、维护、损伤等；f2：传输网络异常；f3：数据丢 失；f4：数据库异常；f5：网络攻击；f6：软件故障；f7：系统断电、崩溃等意外等；使用本文中给出的方法对ES1和ES2进行生存性评估，结果如表 2 所示：表 2 系统修改前生存性计算结果Tab.2 Computational result before system updating关键服务PESTES /msCESEPESEPET/msPreESES199.2%1.2860.8599.9%31.51ES298.1%0.5760.9599.8%31.57由于系统设计时，没有考虑针对

30、历史数据库发生异常的威胁事件的处理方式，因此ES1的 CES只有 0.85，在增加了在某路段数据缺失，且历史数据库异常时，使用其他路段实时数据 间接预测该路段数据的处理方式之后，重新对系统的生存性进行评估，结果如表 3 所示：表 3 系统修改后生存性计算结果Tab.3 Computational result after system updating关键服务PESTES /msCESEPESEPET/msPreESES199.4%1.6450.9599.9%31.815ES298.1%0.5760.9599.8%31.57实验结果表明，本文所描述的以系统关键服务实时响应能力的基础，能够在一定

31、程度上 反应系统的生存性状态，评估系统可生存性的方法是可行和有效的。本文实验中的软件故障、网络攻击威胁方面的数据来自经验，因此，下一步的主要工作 是研究基于时间自动机模型的自动化测试技术，完善系统可生存性的量化评估模型，从而减 少人为因素对评估准确性的影响，使得评估结果更加准确的描述待评估系统可生存性的水平。参考文献1 Hollwya B. A., Neumann P.G. Survivable computer-communication systems: The Problem and working group recommendationsR. Washington: US Army

32、Research Laboratory, 1993.2 Jiang T. Z. A New Definition of Survivability of Communication Networks. Military CommunicationsConference: Military Communications Changing World. IEEE, 1991:2007-2012P.3 Jianxu Shi, Fonseka. Traffic-based Survivability Analysis of Telecommunications Networks. GlobalTele

33、communications Conference, IEEE, 1995(12):1615-1616P.4 Howard F. Lipson, David A. Fisher. Survivability-A New Technical and Business Perspective on Security.Proceedings of the New Security Paradigms Workshop, 1999.5 Nancy R. Mead, Robert J. Ellison, Richard C. et al. “Survivable Network Analysis Met

34、hod”, Technical Report, CMU/SEI-2000-TR-013 http:/www.cert.org/archive/pdf/00tr013.pdf .6 Nancy R. Mead, Robert Ellison, Richard C. Linger, et al. Life-Cycle Models for Survivable Systems.Proceedings of 3rd Information Survivability Workshop, 2000.7 Louca Soulla, Pitsillides Andreas, Samaras George.

35、 On Network Survivability Algorithms Based on TrellisGrpah Transformations. In: the Fourth IEEE Symposium on Computers and Communications(ISCC, 99);1999 July6-8, 1999; RedSea, EgPyt; 1999.P.235-243.8 Jha Sanjay K., Wing Jeannette M., Linger Richard. Survivability Analysis of Network Specifications.

36、In: Workshop on Dependability Despite Malicious Faults, 2000 International Conference on Dependable Systems and Networks(DSN2000); 2000June25-28, 2000;NewYork, NY USA:IEEE Computer Soeiety:2000.9 Gao Zhixing, Ong Chen Hui, Tan Woon Kiong. Survivability Assessment:Modeling Dependencies inInformation

37、Systems. In: the 4th IEEE/CMU/SEI Information Survivability Workshop (ISW-2001/2002):2001 October 15-17, 2001; Vancouver, BC Canada; 2001.10 郭渊博, 马建峰. 分布式系统中服务可生存性的定量分析J. 同济大学学报, 2002 30(10):1190-1193.11 黄遵国, 卢锡城, 王怀民. 可生存性技术及其实现框架研究J, 国防科技大学学报, 2002, 24(5):29-32. 12 包秀国, 胡铭曾, 张宏莉. 两种网络安全管理系统的生存性定量分

38、析方法J, 通信学报, 2004,25(9):34-41.13 Ellison Robert J., Linger Richard C., Longstaff Thomas. A Case study in Survivable Network SystemAnalysis J. Technical Report, CMU/SEI-98-TR-01, Carnegie Mellon University 1998.14 Ellison Robert J., Linger Richard C., Longstaff Thomas. A Survivable Network System Anal

39、ysis: A CaseStudy J. IEEE Software. 1999, 16(4):70-77.15 R. Alur, D.L. Dill, A Theory of Timed Automata. Theoretical Computer Science, 1994, Vol.(126): pages183-235.16 R. Alur, Timed Automata. 11th International Conference on Computer-Aided Verification, CAV99. Italy, Lecture Notes in Computer Scien

40、ce, Springer-Verlag Berlin Heidelberg, 1999, Vol.(1633): pages 8-22.17 R. Alur, D.L. Dill. Automata-theoretic Verification of Real-time Systems. In Formal Methods for Real TimeComputing, Trends in Software Series, John Wiley & Sons Publishers, 1996, Vol. (12): pages 55-82.Methods Based on the Timed

41、Automata for SurvivabilityEvaluationLiu Jinliang，Tan GuozhenDepartment of Computer Science and Engineering, Dalian University of Technology, Dalian, PRC, (116024)AbstractAs the computer system is playing an important role in modern society, ensuring survivability of system has increased greatly in d

42、emand. How to evaluate and improve system survivability has becomean important research problem. In this paper, basic theory about system survivability and survivability evaluation is introduced. A kind of evaluation framework of system survivability based on frameworkof Survivable Network Analysis

43、is proposed, with the emphasis on the timed automata model. Taking advantage of the constraint function of timed automata while describing system time, we quantifiedsystem survivability by real-time response ability in threatened condition. And the experiments showthe feasibility and effectiveness of the survivability assessment method given in this paper. Finally we make a conclusion and indicate future research direction.Keywords: Survivability; Timed automata; Quantitative analysis; Real-time response作者简介：刘金亮，男，1981 年生，硕士研究生，主要研究方向系统可生存性研究。