基于UPPAAL的铁路车站信号联锁系统模型验证

详细介绍了适于描述实时系统的形式化方法,时间自动机以及基于时间自动机的模型验证工具UPPAAL.给出了铁路车站信号系统中的联锁功能进路建立的时间自动机模型,并利用UPPALL对其进行了分析与验证.     

时间自动机与信号自动机的互模拟算法

基于时间自动机的验证工具已被广泛应用于实时系统模型验证。信号自动机为一类实时系统建立了比时间自动机更适合的模型,但是它还不能用于实际的实时系统模型验证,因为没有验证算法可用。把信号自动机验证问题归约到了时间自动机验证问题：证明了两种自动机具有相同的识别语言能力,证明了二者具有双向模拟关系,并在此基础上提出了线性的互模拟算法。把互模拟算法和已有的时间自动机验证算法结合起来,就得到了信号自动机的验证算法,从而解决了对信号自动机模型的验证问题。     

时间ω-树自动机识别语言的一个条件

时间自动机被广泛用于实时系统验证和模型检验.为适应不同类型的系统验证需要,不少时间自动机的相关模型被提出.时间树自动机是这样的新模型之一.目前主要是针对时间树自动机识别的语言类及相关性质的研究.本文提出了时间树自动机识别语言的一个条件,并证明了结论的正确性.如果一个语言不能满足该条件,它一定不能被时间树自动机识别.这为证明一个具体语言不能被时间树自动机识别提供了思路.     

一种时间自动机时钟离散化算法

稠密时间自动机被广泛应用于实时系统自动验证.然而其在补操作下不封闭,因而导致多种线性实时性质不可验证.离散时间自动机虽不存在此问题,但该模型表达能力偏弱.因此,提出了一种时间自动机时钟离散化算法,结合时钟物理约束因素,证明了新方法可有效解决上述问题.     

基于时间自动机的动态服务组合方法研究

动态网络环境下,Web服务资源具有高度自治性和动态性,如何根据运行时具体的用户需求完成动态的服务组合是一个重要问题.时间自动机是一种形式化的实时并发系统模型,它为实时系统的行为描述提供了较好的分析方法.本文通过引入基于时间自动机的二部图表示可以实现对动态服务组合的建模与控制.     

矿井机车自主驾驶过程的建模及验证

文章首先使用自然语言描述了矿井机车自主驾驶系统的结构和控制过程;然后基于时间自动机理论对自主驾驶中涉及的机车控制器、机车运行服务器以及其他车载设备、被控对象建模,从而得到自主驾驶的时间自动机网络模型;最后应用时间自动机模型验证工具UPPAAL对自主驾驶模型进行了仿真分析和验证。验证结果表明建立的模型满足系统的功能性需求和实时性需求,证明了系统设计的正确性。     

确定的与非确定的公式时钟自动机的等价性

本文分析了传统的时间自动机在实时系统进行形式化验证方面所存在的问题,提出了一种新的形式化验证工具——公式时钟自动机,给出了公式时钟自动机的形式化定义。在公式时钟自动机中,每一个事件对应一个命题、并且针对给定命题集上的每个时态公式,我们定义两个时钟:公式记录时钟与公式预测时钟。前者记录公式最近一次被满足时距目前的时间,后者预测下一次公式将被满足时距目前的时间。最后讨论了公式时钟自动机的确定性和非确定性,并证明了确定的公式时钟自动机和非确定的公式时钟自动机的等价性。     

线性混合系统的一种验证方法

混合系统是指嵌入于物理环境中的数字实时系统．由于计算机技术的快速发展,混合系统在各行各业中都得到广泛应用,但是由于混合系统涉及到连续时间,因此其验证问题始终没有得到完善的解决．近年来,人们普遍采用模型检验方法对混合系统进行验证．由于线性混合系统在实际应用中可以表示大多数的嵌入式实时系统,因此我们着重研究这类混合系统的验证算法．本文首先介绍了混合系统的模型—混合自动机,然后提出了一种针对线性混合系统的基于区域的先划分再遍历的半确定性验证方法．经实例检验,该方法能够有效地验证线性混合系统．最后将本文的方法同有关的其它算法进行了比较     

一种基于UPPAAL的智能合约属性形式化验证方法

针对智能合约的属性验证问题,该文提出了一种基于UPPAAL的智能合约属性形式化验证方法.首先定义了Solidity基本语句的操作语义及其到时间自动机的转换,将智能合约转换成时间自动机网络模型;然后定义并描述智能合约常见的安全性和活性,再使用模型检测工具UPPAAL验证智能合约的属性;最后对购物合约进行了建模与验证,验证了该方法的有效性.     

一种基于有限运行时间自动机的基因网络模型

阐述了最近几年来国外基因网络系统逻辑行为的研究新进展——基于有限状态自动机模型的方法,针对该方法的局限性,提出了一种基于有限运行时间自动机的基因网络模型,以描述网络行为的时间约束.     

嵌入式实时软件建模方法研究

随着硬件设备计算能力的迅速提高以及社会需求的不断变化和增长,嵌入式实时软件变得越来越复杂.为了提高系统的安全性和可靠性,将基于UML的建模方法与形式化建模方法相结合,可以为嵌入式实时软件建模和验证提供一种良好的解决方案.采用UML扩展机制,在UML2.0顺序图中加入嵌入式实时软件建模所需的时间特性,并提出一种由UML2.0顺序图构造出时间自动机的方法,为下一步验证奠定理论基础.     

Rigorous Modeling of Real-time System Based on UML and PVS

Rigorous modeling could improve the correctness and reduce cost in embedded real-time system development for models could be verified. Tools are needed for rigorous modeling of embedded real-time system. UML is an industrial standard modeling language which provides a powerful expressi-veness, intuitive and easy to use interface to model. UML is widely accepted by software developer. However, for lack of precisely defined semantics, especially on the dynamic diagrams, UML model is hard to be verified. PVS is a general formal method which provides a high-order logic specification language and integrated with model checking and theorem proving tools. Combining the widely used UML with PVS, this paper provides a novel modeling and verification approach for embedded real-time system. In this approach, we provide 1) a timed extended UML statechart for modeling dynamic behavior of an embedded real-time system; 2) an approach to capture timed automata based semantics from timed statechart; and 3) an algorithm to generate a finite state model expressed in PVS specification for model checking. The benefits of our approach include flexible and friendly in modeling, extendable in formalization and verification content, and better performance. Time constraints are modeled and verified and its a highlight of this paper.     

多视点实时形式化方法的应用模式

RT-Z结合了Z的状态描述能力和Timed CSP对并发实时进程的描述能力,成为一种有效的实时并发软件的开发手段。RT-Z不但是一种规格说明语言,也可以用于建模．多视点的软件开发方法的研究从不同的视点观察系统,分离各自的关注点。简化了系统的设计．本文在形式化方法RT-Z的基础上扩充语法框架,以支持多视点工程的思想,充分利用形式化方法的精化推理机制,同时具有对实时约束的描述能力,可作为并发实时系统开发中的基本模式．     

一个新的基于时间Petri网的多媒体同步模型

多媒体同步是多媒体应用的一个重要需求。本文提出了一种基于时间Ｐｅｔｒｉ网的多媒体同步模型,以对具有时间约束关系的多媒体合成进行抽象和形式化描述,并给出了处理异步用户交互的算法     

基于UPPAAL的NS密码协议模型检测分析

形式化分析方法是目前密码协议分析的主流方法。然而,典型的密码协议形式化验证方法没有考虑时间因素,这个选择使得分析简单化。本文提出了运用基于时间自动机的模型检测工具UPPAAL分析密码协议的方法,并对著名的Needham—Schroeder协议（简称NS协议）的简单版本进行了分析。在对NS协议进行建模时,考虑消息实际传输需花费时间,引入消息的时间信息,从而构建NS协议的时间自动机模型。该方法利用UPPAAL的检查引擎所用的先进技术使其克服了一般时间自动机应用存在的状态空间爆炸问题。实验结果UPPAAL给出了NS协议认证失败的一种可能之一。分析结果表明,入侵者可以轻松地对NS公钥协议进行有效攻击。从而证明UPPAAL工具可以成功检测出NS协议的缺陷。     

时间依赖的交通网络模型及最短路径算法

为了解决传统最短路径算法不能很好地应用于实时公交查询系统的问题,研究了时间依赖的交通网络模型和理论基础,提出了一种时间依赖的最短路径算法,以此算法为基础实现了南京市公交查询系统。实践证明,时间依赖的交通网络模型能更好地反映实际交通网络的运行情况。     

耦合触发细胞自动机加密算法研究

该文提出了1种新的耦合触发细胞自动机加密模型。根据耦合和触发细胞自动机的性质,采用相互作用的n个细胞自动机作为一个整体,构造出耦合触发细胞自动机加密系统。计算机仿真结果表明：该算法极大地提高了密钥空间,有效地阻止了蛮力攻击;同时,加密时随机数的引入使得攻击者不可能获得唯一的明文密文对,从而有效地抵御了已知明文攻击和选择密文的攻击。     

实时调度问题的形式化描述及分析

使用自动机理论建立了一个用于分析实时调度问题的、可化简归并的形式化方法。通过分析单个任务的状态变化过程来构造实时系统的自动机。对自动机的状态进行化简和归并,大大降低了讨论实时调度问题的复杂度。以优先级上限协议为例构造了确定有穷自动机并使用该自动机证明了优先级上限协议的性质。