基于时间自动机的动力调度岗位培训仿真机理建模

针对大型风洞群中压空气系统存在调度机理复杂、岗位人员素质要求高、系统实操培训代价大等问题,实施基于时间自动机的动力调度岗位培训仿真机理建模。通过混杂系统理论提出适合大型风洞群中压空气调度的扩展时间自动机模型,基于先来先服务策略构建资源申请、机组工作等队列,建立调度器、就地执行器等核心机理模型,并采用UPPAAL工具对模型进行验证。结果表明:该模型的建立不仅为岗位人员掌握设备结构原理、积累实操经验提供有效手段,而且为建立风洞试验调度仿真系统、合理有效实施风洞动力调度岗位培训打下了基础。

基于时间自动机的无信号交叉口车路协同系统建模与验证

车路协同系统(cooperative vehicle infrastructure system,CVIS)是提高交叉口车辆通行安全的重要解决方案之一。针对CVIS现有技术规范和标准未明确系统对象状态交互的动态时序及迁移过程,无法有效保障系统的通行控制逻辑安全问题,采用形式化语言对无信号交叉口车路协同系统功能逻辑进行描述,验证系统对象的状态交互和控制逻辑安全,提高无信号交叉口的车辆通行安全性。以单车无冲突、双车冲突和多车冲突场景分别进行仿真,明确状态交互和使能迁移路径;结合工具和需求规范语句进行系统安全属性验证,证明了控制逻辑的可靠性和安全性,为研发高安全架构的车路协同系统提供了可信依据。

基于时间自动机的列控系统等级转换建模与验证

随着列控系统的发展,我国现有铁路线路主要应用有CTCS-3级和CTCS-2级两种列控系统。等级转换是在列车运行控制过程中起到重要作用,其功能的正确性直接关系到列控系统的安全性。本文采用时间自动机建模方法,依据CTCS-3级列控系统总体基础方案的需求规范,对等级转换场景进行了功能性及实时性的需求分析,描述CTCS-3级和CTCS-2级列控系统转换过程中的功能特性和时间约束,对等级转换场景进行建模仿真,并通过形式化验证的方式检验模型的正确性。

异步多进程时间自动机的可覆盖性问题

已有的实时系统模型无法动态创建新进程.为此,基于时间自动机模型,提出了异步多进程时间自动机模型,将每个进程抽象为进程时间自动机,其部分状态能够触发新进程.考虑到队列会导致模型图灵完备,进程都被缓存在集合中,但仍可建模许多实时系统.通过将其编码到可读边时间Petri网,证明了该模型的可覆盖性问题可判定.

基于时间自动机的物联网网关安全系统的建模及验证

物联网是一个多网异构融合网络,其感知层常面临各类安全威胁。物联网网关作为感知层和网络层的桥梁,应当具备安全管理功能,防止安全问题向上层扩散。针对物联网网关目前安全方面的不足,以物联网网关中间件技术为平台,设计一个通用的物联网网关安全系统。该系统可以嵌入不同的安全协议或算法,然后进行建模与分析,能够辅助安全网关的设计和具体实现。利用时间自动机对系统进行形式化建模与验证,验证结果表明物联网网关安全系统满足机密性、可用性、真实性、顽健性、完整性和新鲜性6项安全需求。

基于时间自动机的物联网服务建模和验证

物联网服务的建模和验证是当前物联网服务提供中的一个重要问题.文中将物联网服务的行为建模为其与相关环境实体的交互,并引入环境实体以刻画物理世界各种物体的属性和行为,从而将物联网服务能力建模为它能够导致的环境实体发生的期望变化.文中以时间自动机为建模工具,分别为将要监测和要控制的物理环境实体以及不同种类的物联网服务独立建模,以表现它们的独立性和自主性.这些时间自动机形成一个网络,刻画完整的物联网服务的通信并发过程,物联网服务的实施过程表现为时间自动机网络上的状态变迁通路.最后,文中提出一组物联网服务要满足的性质,并利用模型检测工具UPPAAL验证物联网服务的正确性.

基于时间自动机的温室环境监控物联网系统建模

由于温室环境的复杂性,系统设计的不合理会直接导致数据的不确定和系统的不稳定。基于体系结构的物联网层次模型对物联网的实施具有指导意义,但是体系结构模型没有提供系统建模工具和模型验证的方法。基于时间自动机理论的建模与模型验证方法是一种对物联网系统建模的有效手段,能在系统设计时提高系统的稳定性,保证系统设计的正确性。通过对智能温室监控物联网系统的分析,从系统实施的角度重新对温室环境监控物联网系统进行了层次划分,利用时间自动机理论对系统中的相应组件进行建模,在对各个子系统分别建模的基础上形成了时间自动机网络模型。最后利用时间自动机建模工具UPPAAL,对已经建立的形式化模型进行了系统逻辑正确性验证与系统执行时序验证。结果表明,利用时间自动机理论及其建模工具UPPAAL可以对智能温室监控物联网系统进行建模及模型验证,可以在系统设计时对系统进行准确的模型分析,避免系统设计错误,降低系统设计缺陷,在系统投入运行中规避设计风险,从而提升系统的稳定性与可靠性,确保系统设计的正确性。

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

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

时变网络中国邮路问题的时间自动机模型

基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.实验结果表明,该方法在求解精度上明显优于运筹学领域的方法.

基于时间自动机的Web服务模型检测

传统的基于有限状态机的组合Web服务模型检测方法不能保证带有时间约束的组合Web服务的正确性。把组合Web服务看成多智能体系统,将带有时间约束的Web服务智能体建模为时间自动机,通过并发组合构成时间自动机网络,从而用时间自动机验证工具UPPAAL对组合Web服务的运行过程进行模拟,并验证其活性、安全性和死锁等性质。采用该方法对雇员出差安排组合Web服务进行建模和验证,结果表明,该组合Web服务存在死锁问题。最后通过分析死锁产生的路径,完善该组合Web服务的通信协议,从而消除了死锁。

模型检测基于概率时间自动机的反例产生研究

模型检测基于概率系统的反例产生问题,在最近引起人们的关注.已有的工作主要围绕模型检测Markov链的反例产生而开展.基于概率时间自动机(PTA)是Markov链的不确定性和系统时钟的扩展.关注的是模型检测PTA的反例产生问题.首先通过在PTA上寻找概率之和恰好大于λ的k条最大概率的路径,并根据这些路径和原PTA构造原PTA的一个子图,从而快速找到违背性质的具有较少证据的反例.然后精化此结果——通过逐条加入上述各条最大概率的路径来精确地计算已加入路径所构成的PTA子图的最大概率.由于考虑到符号状态交集对概率系统的影响,可以得到证据更少的反例.

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

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

基于时间自动机的Ad hoc网络入侵检测

该文提出一种基于时间自动机分布式合作的入侵检测算法。首先,将整个网络分为子区域,每一区域随机选出簇头担任监视节点,负责本区域的入侵检测。其次,按照路由协议构筑节点正常行为和入侵行为的时间自动机,监视节点收集其邻居节点的行为信息,利用时间自动机分析节点的行为,识别入侵者。该算法不需要事先进行数据训练并能够实时检测入侵行为。最后,通过模拟实验证实了算法的有效性。

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

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

混杂系统的扩展时间自动机模型及验证研究

混杂系统复杂度高且涉及领域广,没有通用的方法来解决分析、设计等问题。为解决一类工业控制混杂系统的建模和验证问题,对时间自动机进行了语义扩展,使其含有连续变量以及映射在其上的约束,使用扩展后的时间自动机对此类混杂系统进行建模,采用验证工具UPPAAL进行模型分析模拟,并使用简化的CTL对系统需求规范进行验证。具体实例研究表明,该方法对于分析设计一类混杂系统具有可行性和有效性。

基于时间自动机的UML模型转换与验证研究

针对无法对UML模型进行形式化验证的问题,提出在元模型层将UML模型转换为时间自动机模型并进行验证的方法.形式化UML状态机的结构,抽象出UML和时间自动机的元模型,利用模型转换语言ATL对UML元模型和时间自动机元模型构造映射规则,实现UML模型到时间自动机模型的转换,在模型验证工具Uppaal中对转换结果进行形式化验证.最后进行实例研究,结果表明了此方法的有效性和先进性.

基于时间自动机的嵌入式系统AADL模型可调度性验证

采用时间自动机形式化模型检验方法建立了结构分析与设计语言(AADL)调度模型的自动机,实现了从AADL模型到时间自动机模型的自动转换与验证.首先,设计了周期、非周期的线程时间自动机模板及抢占、非可抢占的调度器时间自动机模板,建立了AADL调度模型到时间自动机模型的语义映射法则.然后,设计了自动化模型转换插件,并将其集成到OSATE建模工具中,实现了建模、转换、验证的集成开发环境.最后,利用UPPAAL工具对时间自动机模型进行模拟与验证.仿真实验结果表明,所建立的模型转换方法能够有效、实时地将AADL模型转换为时间自动机模型,并可在UPPAAL中分析原模型的可调度性.

时间自动机模型验证的研究进展

基于时间自动机的模型验证是一种形式化的实时并发系统时间性质验证技术,重大软件对时间行为、时序关系的高可靠性要求,不断刺激时间自动机模型验证技术的发展。介绍了时间自动机理论、模型验证算法及工具,对该领域的研究进展做了综述,指出了时间自动机模型验证存在的问题和研究方向。

时间自动机状态空间的一个极小化构造方法

对时间自动机的转换系统进行改进,提出了一个状态空间的极小化构造方法。该方法用位置和停留在该位置时的可能时钟值集合来表示状态,以此隐藏因时间流逝而引发的无穷状态,得到了改进的转换系统——时间段转换系统;并通过对转换可能发生时间的分析,去除无效转换;然后使用转换互模拟合并等价状态,实现了状态空间的极小化,有效地避免了状态空间爆炸。

一种层次式时间自动机模型检测方法

层次式时间自动机在软件系统建模过程中有着重要的应用。由于层次嵌套带来额外的复杂度,难以对之进行直接的形式化验证工作。提出一种平展算法,将层次式时间自动机转化为一组并行的顺序时间自动机,应用广播通道同步该自动机集合执行。在此基础之上实现一个原型系统可以将层次式时间自动机模型自动转化为模型检测工具UPPAAL的输入,从而可以对之进行验证。结合实时UML状态机图实例,证明了该方法的有效性。