基于SMT的时钟约束语言CCSL的形式化分析方法与工具

时钟约束语言CCSL是一种用于描述实时嵌入式系统中事件之间约束的形式化语言.它是UML针对实时嵌入式系统建模的扩展包MARTE （Modeling and Analysis of Real-Time and Embedded systems）中用于对时间建模的一个子语言.给定一组由CCSL定义的时钟约束条件,需要判断是否存在某种调度策略满足约束,是否所有满足这些约束的行为都不会导致系统死锁等分析.针对CCSL的形式化分析目前已经有一定的研究工作,如基于状态迁移系统与时间自动机的方法等.但这些方法要么只针对某种特定的分析,要么只适用于部分CCSL约束,要么分析效率较低.本文提出一种基于SMT的统一且高效的CCSL形式化分析方法.统一性体现在其可用于有效性证明、迹分析、死锁检测、LTL模型检测等方面的验证与分析.基于该方法开发了原型工具同时支持上述四种验证功能.工具集成了当前最高效的SMT求解器Z3和CVC4.得益于SMT求解器的高效性,实验中大部分的验证可以在短时间内完成.     

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

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

一类时间自动机的时间约束可满足性判定方法

时间自动机是一种有效描述实时系统行为的计算模型。借助时间自动机对实时系统进行分析、设计能够保证所开发的实时系统具有较高的可靠性。在此过程中对时间自动机的验证是非常关键的一步。验证的主要目的是为了保证时间自动机能够正确地描述实时系统。其中迁移的时间约束可满足性就是需要验证的性质之一。常用的方法是通过构造时间区域自动机来实现,但该方法所涉及的状态数目巨大。该文针对一类时间自动机的特点给出了基于时间关系矩阵来判定时间约束可满足性的方法,结果表明该方法能够有效地减少状态数。     

一种改进的区域自动机构造方法

用时间自动机验证一个有穷状态实时系统的正确性，可归结为判定两个时间正则语言的包含问题，亦可归结为判定两个时间正则语言的交是否为空的问题。在判定一个时间正则语言是否为空时，先要将时间自动机转化为无时间的区域自动机。Alur和Dill给出的构造区域自动机的算法，存在许多不可达或虽可达但无用的状态。通过对时钟约束进行分析，在求时钟区域和时间后继的过程中，不断地将一些不可达或无用状态筛掉，使构造出的区域自动机更为优化，改进了Alur等人给出的算法。     

构建度量区时序逻辑的时间自动机

在实时系统的形式验证中,为了直接验证带有明显时间约束的性质,选用了一种被广泛接受的(线性时间)实时时序逻辑——度量区时序逻辑来描述待验证的性质;提出了基于迁移的扩展时间B chi自动机;构建了度量区时序逻辑的基于迁移的扩展时间B chi自动机。这样扩展了已有实时系统模型检测工具的性质规范语言的表达能力,使其能直接处理和验证带有明显时间约束的性质。实现的工具表明,该算法有效且可行,并且显著地减少了结果自动机节点和迁移的数量,从而降低了结果自动机的大小,有利于进一步的模型检测过程。     

实时时序逻辑语言XYZ/RE到时间自动机的映射

时间自动机是一种重要的实时系统建模工具。本文建立了实时时序逻辑语言XYZ/RE到时间自动机的一种映射机制,将XYZ/RE所描述的系统进程直接转换为时间自动机,这样不但可以准确捕获实时系统功能和控制行为,还可以利用基于时间自动机的验证工具UPPAAL对XYZ/RE描述的系统正确性进行检测。最后本文通过一个实例的描述与检测,验证了映射机制的有效性。     

对时间自动机中时钟约束的处理

在实时系统建模中,时间自动机是一个普便使用的工具,在求解状态可达性关系时对时钟约束的处理是关键,本文在分析已有理论的基础上提出了如何对含有不同时钟相互约束的系统处理.     

基于IF的实时系统验证

IF是一个对异步实时系统建模和验证的开放环境,建立在具有丰富表达能力,基于时间自动机的中间语言IF符号集之上。文章描述了IF的组成,包括其体系结构,所使用的符号集;然后给出了IF对实时系统验证的方法,并运用此验证方法对一个实时系统实例进行了验证。     

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

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

一种基于区域分解的实时测试用例生成技术研究

实时系统是指与运行环境的交互行为存在时间约束的系统。由于时间约束的无穷状态空间问题,增加了实时系统测试难度。本文基于时间自动机,利用时间区域分解的方法,将无穷状态空间的时钟区域在时钟数量对应的坐标图中等价划分为各个类,在生成的测试路径中取到相应的点坐标,简化取点的个数,有效减少测试用例的生成数量,进而相对减少状态空间爆炸的可能性,为实时系统功能、安全性验证提供理论基础。