基于Uppaal的时延Petri网到时间自动机等价模型验证*

时延Petri网和时间自动机都可以有效地对实时系统的行为进行模拟和性能分析。利用时延Petri网到时间自动机等价转换算法（简记作TPN-to-TA 转换）,将一个描述实时系统的时延Petri网模型转换成与其语义等价的一组时间自动机模型。使用时间自动机中成熟的模型验证工具Uppaal对此时延Petri网的模型进行验证。     

一类并发实时系统的自动验证

一个被广泛用于验证实时系统的方法是根据被验证的实时性质,使用适当的双向模拟等价关系使无限的状态空间转化为有限的状态等价类空间.算法只需要在这个有限的等价类空间里搜索就可以得到正确答案.但是,这个等价类空间的规模一般随着系统规模的增大而产生爆炸性的增长,以至于在很多情况下,穷尽搜索这个空间是不现实的.该文引入了一个等价关系来验证一个由多个实时自动机通过共享变量组成的并发系统是否满足一个线性时段特性.同时,还引入了格局之间的兼容关系来避免对状态等价类空间的穷尽搜索.基于这两个关系,文章提出了一个算法来验证是否一个实时自动机网满足一个线性时段特性.实例研究显示,此算法在某些情况下比其他一些工具有更好的时间和空间效率.     

一种基于时间自动机的实时系统模型检查算法的设计与实现

该文首先简介了时间自动机、时钟区域、区域等价、时钟带的概念,利用区域等价关系,可以将时间自动机的无穷状态空间转化为有穷。然后通过一个典型的实例完整地介绍了基于时间自动机的实时系统模型检查技术,并用Visual C++语言描述了实时特性验证中的数据结构,实现了实时特性验证算法,实验表明利用该算法可以进行实时系统的形式化验证。     

基于UPPAAL的实时系统模型验证

UPPAAL是一种使用时间自动机模型的实时系统验证工具，它可以避免时间自动机求积时状态空间的爆炸。介绍了时间自动机理论和工具UPPAAL，着重说明如何用UPPAAL进行模型检查，并给出了一个应用实例。     

基于场景构件式实时软件设计的一致性检验

在复杂的实时软件系统中使用构件式设计方法,已成为目前软件工程中的研究热点.如何有效地验证实时软件的设计是否满足给定的时间规约,是实时计算领域中的主要挑战之一.通过在接口自动机模型中添加时间区间标记,来扩展其对实时系统接口行为的表达能力;使用实时接口自动机网络来描述实时软件系统的构件式设计模型;使用带布尔不等式时间约束的UML顺序图表示基于场景的需求规约,对系统设计阶段实时软件构件的动态行为进行形式化分析与检验.通过对实时接口自动机网络状态空间的分析,构造了其可兼容的整型状态等价类空间的可达图,并在此基础上给出了验证算法,以检验构件式实时软件系统的设计与带时间约束的场景式规约之间的一致性.     

基于时间自动机的道岔自动控制研究

实时系统由于受时间约束,设计和验证具有很高的挑战性.用多个时间自动机来规范模拟道岔自动控制系统,给出了一种自动化的道岔控制模型(TTCQ),并采用UPPAAL作为模型验证工具,证明了该模型具有安全性、有效性和可控性.所采用的方法避免了积的等价类状态空间的爆炸,减少了验证的搜索空间,为铁路交通提供了一种可行的、安全的、智能的控制机制.     

基于时间自动机的道岔自动控制研究

实时系统由于受时间约束,设计和验证具有很高的挑战性。用多个时间自动机来规范模拟道岔自动控制系统,给出了一种自动化的道岔控制模型(TTCQ),并采用UPPAAL作为模型验证工具,证明了该模型具有安全性、有效性和可控性。所采用的方法避免了积的等价类状态空间的爆炸,减少了验证的搜索空间,为铁路交通提供了一种可行的、安全的、智能的控制机制。     

并发和实时系统的模型检验技术

模型检验是一种重要的自动验证技术,通过显式状态搜索或隐式不动点计算来验证并发或实时系统的模态／命题性质,以保证通信协议、数字电路等设计的正确性。详细阐述了模型检验技术的发展与研究现状。首先描述了并发系统分别基于自动机理论和符号化的两种主要模型检验策略,并给出解决状态爆炸问题的主要方法;然后介绍了针对实时系统以及面向对象设计的模型检验方法;对每种方法都介绍了相应的典型工具,最后分析了模型检验面临的困难以及今后的发展趋势。     

基于着色时间Petri网的实时系统的形式验证

嵌入式实时系统多数应用在安全性要求较高的场合,因此需要保证系统的正确性.复杂性不断增加的实时系统迫切需要在系统开发早期引入形式化分析技术来验证系统的期望性质.时间Petri网是有严格数学基础的图形表达工具,适合对实时系统建模;时间自动机(Timed Automata,TA)有成熟的验证工具,被广泛用于实时系统的模型检验和验证.本文提出一种基于着色时间Petri网(Colored Time Petri Net,CTPN)的实时系统的验证方法,用CTPN对带有控制流和数据流的实时系统建模,通过转换规则将CTPN模型转换成语义等价的TA模型,利用模型检验工具UPPAAL验证系统的性质.最后,用实例证明此方法有效.     

实时系统的模型检验中针对共享变量的优化技术

实时系统可以使用由多个并发的时间自动机组成的时间自动机网络来建模。网络中的时间自动机通过共享变量和/或信道交互。带有不同共享变量取值的自动机网络的状态是截然不同的。因此,共享变量也是引起状态空间爆炸问题的原因之一。本文提出了在不同共享变量取值之间的兼容性关系的概念。使用这种兼容性关系,时间自动机网络的可达性分析算法就可以减少需要遍历的状态的个数。本文给出了检测符号化状态中共享变量的取值所能兼容的其它取值的算法以及进一步进行这种兼容性关系检测的增强算法。最后还给出了使用了这两种算法进行优化之后的可迭性分析算法。实验结果显示经优化的可达性分析算法的空间效率得到了显著的提高。     

一种基于时间自动机的域构造方法

模型检验是一种重要的形式化自动验证技术,通过状态空间搜索来保证软硬件设计的正确性。由于TCTL不是针对时间自动机,而是针对有限状态变迁系统的,从而无法使用TCTL直接对时间自动机进行模型检验。给出了一种从时间自动机到有限状态变迁系统的方法,并在不改变时间自动机的语义上,使时间自动机等价后的域状态数尽可能少,在一定程度上有效地解决了状态空间爆炸问题。     

一种基于时间自动机的时钟等价性优化方法

提出了一种优化模型检验时间自动机的时钟等价规则,通过优化的时钟等价规则,使时间自动机等价后的域自动机状态数尽可能少,并在此基础上定义了适合于优化时钟等价规则的域自动机.优化时钟等价规则,在一定程度上有效地解决了状态空间爆炸问题.     

时间自动机可达性分析中的状态空间约减技术综述

时间自动机是检验实时系统建模的有效工具，其可达性分析可以检验系统是否可能达到某些特定的状态，其算法通常采用对符号状态的枚举来遍历其状态空间。因为引入了时钟变量，时间自动机的可达性分析算法会产生大量的中间状态，需要巨大的存储空间，往往超出了计算机能力的极限，导致分析和检验不能完成。这就是所谓的“状态空间爆炸”。研究人员设计了很多种优化技术来约减可迭性分析所需的存储空间，以解决或者缓解这个问题。本文首先介绍了时间自动机及其可达性分析的基本概念，然后分类讨论了现有的空间约减优化技术并对此做出总结，最后提出了一些未来的研究方向。     

Checking timed automata for linear duration properties

It is proved in this paper that checking a timed automaton M with respect to a linear duration property D can be done by investigating only the integral timed states of M,An equivalence relation is introduced in this paper to divide the infinite number of integral timed states into finite number of equivalence classes.Based on this,a method is proposed for checking whether M satisfies D.In some cases,the number of equivalence classes is too large for a computer to mainpulate,A technique for reducing the search-space for checking linear duration propoerty is also described.This technique is more suitable for the case in this paper than those in the literature because most of those techniques are designed for reachablility analysis.     

State feedback control of real-time discrete event systems with infinite states

In this paper, we study a state feedback supervisory control of timed discrete event systems (TDESs) with infinite number of states modelled as timed automata. To this end, we represent a timed automaton with infinite number of untimed states (called locations) by a finite set of conditional assignment statements. Predicates and predicate transformers are employed to finitely represent the behaviour and specification of a TDES with infinite number of locations. In addition, the notion of clock regions in timed automata is used to identify the reachable states of a TDES with an infinite time space. For a real-time specification described as a predicate, we present the controllability condition for the existence of a state feedback supervisor that restricts the behaviour of the controlled TDES within the specification.     

离散时段演算的符号模型验证

模型验证是对有限状态系统的一种形式化确认方法，近几年，模型验证方法已逐步扩展到实时系统应用中，为解决实时系统的模型验证问题，本文采用离散时段演算人实时系统规格说明的形式语言，用时间自动机作为实时系统的实现模型，对模型验证问题进行了细致的分析，并提出了一种具有实际应用价值的方法－商技术，该方法可以在避免当多个时间自动机并行组合时可能产生的状态空间组合爆炸问题，同时还可以简化整个模型验证问题。     

对时间自动机进行空性检测的过程和改进

为了提高对时间自动机进行空性检测的效率,研究了使用基于时钟区域(zone)的符号化方法和抽象对时间自动机进行空性检测,提出了针对时间自动机自身特点对检测过程进行改进的方法.通过使用基于zone的符号化表示方法和抽象,一个符号化状态表示显式的状态的集合,时间自动机的状态空间会显著缩小,不同的抽象方法对状态空间有不同的效果.符号化状态间不仅有相等关系还有包含关系,通过判断这种包含关系可以尽早的找到接收路径和避免不必要的状态展开从而提高空性检测的效率.实现了改进的检测过程,对一些例子进行了数据比较,取得了较好的实验结果.     

有限精度时间自动机的可达性检测

为了缓解状态空间爆炸问题,减小模型检测过程中生成的状态空间,加快模型检测速度,引入有限精度时间自动机(finite precision timed automata,简称FPTA)作为实时系统的形式模型,并提出了一种数据结构SDS(series of delay sequence)符号化表示状态空间中的状态集.FPTA只记录时钟变量的整数值及时钟变化的先后次序,从而减小生成的状态空间.在一定的时间约束下,Alur与Dill提出的时间自动机的可达性检测可简化为FPTA的可达性检测.举例描述了状态空间的生成过程和表示方法.最后,列出部分初步的实验结果,分析了SDS的特点及不足.