基于线性时序逻辑的实时系统模型检查

模型检查是一种用于并发系统的性质验证的算法技术.LTLC(linear temporal logic with clocks)是一种连续时间时序逻辑,它是线性时序逻辑LTL的一种实时扩充.讨论实时系统关于LTLC公式的模型检查问题,将实时系统关于LTLC公式的模型检查化归为有穷状态转换系统关于LTL公式的模型检查,从而可以利用LTL的模型检查工具来对LTLC进行模型检查.由于LTLC既能表示实时系统的性质,又能表示实时系统的实现,这就使得时序逻辑LTLC的模型检查过程既能用于实时系统的性质验证,又能用于实时系统之间的一致性验证.     

基于线性时序逻辑的实时系统建模与求精

线性时序逻辑语言XYZ／E在统一的语义框架下．能表示从高层需求规范到低层实现模型之间的不同抽象层次的系统描述，也适于描述实时系统的模型和逐步求精过程．本文提出了一种基于构件的实时系统求精方法，并给出一个具体实例一电梯控制系统，采用XYZ／E语言描述了该系统的模型及其求精过程．     

自动验证并发实时系统的线性时段性质

介绍了一个就线性时段性验证实时系统正确性的工具的设计思想以及相关算法,使用时间自动机作为产时系统的描述模型,同时,为了便珩描述并发实时系统,使用带共享变量和通道的时间自动机网作为模型描述并发实时系统,在检验时间自动机网时,用户可以使用工具提供的合成程序将其合并为一个时间自动机然后进行检验,由于时间自动机的状态空间是无究的,通过引入整数状态和状态等价关系的概念,将整个状态0空间划分为有限的状态等价类空间,模型检验过程只需要通过对等价类空间的搜索就可以完成,但往往等价类空间的规模很大,超出了现在计算机的处理能力,原始搜索算法仅仅在理论上是可知地的,为了增工具的使用性,工具中使用的算法运用了一些优化技术来避免对等价类空间的穷尽搜索,使得工具在使用时具有比较好的时间和空间效率。     

基于IF的实时系统验证

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

实时系统的形式化验证

实时系统的设计对系统设计人员而言是一个巨大挑战。在缺乏严格的验证环境时 ,要避免设计错误是很困难的。本文将一种带时戳的时序逻辑及用于描述具体实时系统的时间变迁系统编码到 HOL定理证明器中 ,并实现了一个基本的规则策略库 ,从而实现了一个简单的交互式辅助验证环境L RP。实例 Fisher算法的互斥性在 IRP中得到了验证。     

混合投影时序逻辑与混合系统的形式化验证

为了描述混合系统的性质和行为，10多年来，各种时序逻辑，如Hybrid Temporal Logic等相继出现。这些时序逻辑适用于刻画混合系统的性质和规范，但不适宜表示描述系统的实现模型。本文定义了一个混合投影时序逻辑（Hybrid Projection Temporal Logic，简称HPTL），既能刻画混合系统的性质，又能表示混合系统的实现。这样，混合系统的验证就可以很方便地在统一的数学模型框架下进行。同时，给出了HPTL的基本的逻辑等价式系统和一个用HPTL进行混合系统验证的实例。     

基于B/S架构的实时系统建模验证工具

实时系统的建模与验证是实时系统开发过程中不可或缺的环节。由于目前业界中广泛使用的建模验证工具UPPAAL存在下载安装慢、拖拽控件不灵活且不支持多用户进行项目团队管理等弊端与局限性,在考虑UPPAAL缺点的同时结合实际应用需要,设计并实现基于B/S架构的实时系统的建模和验证工具。该工具通过浏览器即可访问,提供良好建模操作体验的同时支持多用户进行项目团队管理。使用该工具编辑运行具体实例,验证了实例系统的可达性、安全性等性质,获得了预期的正确结果,完成了该工具的功能测试。     

基于时间自动机的实时系统建模及验证

实时系统必须在一个事先定义好的时间限制内对来自外部或内部的事件进行响应,如何有效验证实时模型的正确性和安全性是一个难点.文章通过多个时间自动机来模拟实时系统中的各个对象,并用UPPAAL对模型进行验证,减少了模型验证的状态搜索空间,为实时嵌入式系统开发和验证提供了一种可行、安全的控制机制.实验结果显示了系统的有效性.     

并发系统的操作时序逻辑描述和验证

1.引言 近年来,为了在开发一个复杂系统的过程中尽量提高系统的正确性,减少开发过中重复、较琐的工作,国内外许多学者都从逻辑的角度进行研究,用逻辑系统对并发系统程序行描述、验证,以期通过逻辑系统的简洁和严密来保证友型并发系统的正确     

Compositional Verification of Multi-Agent Systems in Temporal Multi-Epistemic Logic

Compositional verification aims at managing the complexity of theverification process by exploiting compositionality of the systemarchitecture. In this paper we explore the use of a temporal epistemiclogic to formalize the process of verification of compositionalmulti-agent systems. The specification of a system, its properties andtheir proofs are of a compositional nature, and are formalized within acompositional temporal logic: Temporal Multi-Epistemic Logic. It isshown that compositional proofs are valid under certain conditions.Moreover, the possibility of incorporating default persistence ofinformation in a system, is explored. A completion operation on aspecific type of temporal theories, temporal completion, is introducedto be able to use classical proof techniques in verification withrespect to non-classical semantics covering default persistence.     

A Multi-Agent Spatial Logic for Scenario-Based Decision Modeling and Verification in Platoon Systems

To cater for the scenario of coordinated transportation of multiple trucks on the highway,a platoon system for autonomous driving has been extensively explored in the industry.Before such a platoon is deployed,it is necessary to ensure the safety of its driving behavior,whereby each vehicle's behavior is commanded by the decision-making function whose decision is based on the observed driving scenario.However,there is currently a lack of verification methods to ensure the reliability of the scenario-based decision-making process in the platoon system.In this paper,we focus on the platoon driving scenario,whereby the platoon is composed of intelligent heavy trucks driving on cross-sea highways.We propose a formal modeling and verification approach to provide safety assurance for platoon vehicles'cooperative driving behaviors.The existing Multi-Lane Spatial Logic(MLSL) with a dedicated abstract model can express driving scene spatial properties and prove the safety of multi-lane traffic maneuvers under the single-vehicle perspective.To cater for the platoon system's multi-vehicle perspective,we modify the existing abstract model and propose a Multi-Agent Spatial Logic(MASL) that extends MLSL by relative orientation and multi-agent observation.We then utilize a timed automata type supporting MASL formulas to model vehicles'decision controllers for platoon driving.Taking the behavior of a human-driven vehicle(HDV) joining the platoon as a case study,we have implemented the model and verified safety properties on the UPPAAL tool to illustrate the viability of our framework.     

时态逻辑与程序验证

近年来,时态逻辑大量应用于程序验证,采取的途径随使用的时态逻辑的形式和方法的不同而异。本文用自动机理论研究几种时态逻辑(LTL,BTL,POTL)的模型和模型生成子,并讨论用时态逻辑进行程序验证的的重要途径。     

一种结合线性时序逻辑和故障树的软件安全验证方法

嵌入式软件在安全关键领域的广泛应用使得保障软件的安全性成为学界的研究热点。故障树技术是工业界常用的传统的安全分析方法之一。然而,传统的故障树无法精确描述安全关键系统中具有时序特征的系统故障。针对此问题,给出了一种结合线性时序逻辑和故障树的安全验证方法。该方法运用线性时序逻辑对故障树进行形式化规约,从中抽取出软件安全属性并用时序逻辑公式进行描述,用以支持对安全关键软件的模型检验。最后,以某机载控制系统软件数据处理故障模块的模型检验为例,来说明该方法的有效性和可行性。     

基于动态时序描述逻辑的动作理论

动态时序描述逻辑(DLTLDL)是一类描述逻辑的动态时序扩展。提出一种基于DLTLALCIO的动态域建模方法,利用该方法可构造出刻画动态域知识的DLTLALCIO理论,并解决动作推理中的框架问题和分支问题。动作推理问题,如动作可执行性和投影问题等,可归结为关于DLTLALCIO理论的推理问题,并最终归结为DLTLALCIO的公式可满足性问题。DLTLALCIO公式可表达动作和时间约束,相对于其他基于描述逻辑的动作形式,基于DLTLALCIO的动作形式在需要执行复杂查询,尤其是含时间或动作的查询的应用场合具有更好的适用性。     

基于时序逻辑的面向实现的协议规范语言

在多种形式化描述语言和时序逻辑原理的研究之上；针对通讯协议的特点提出一个协议模型思想，并设计了实现此模型协议描述语言．本方法的特点是：基于时序逻辑；引入了面向对象的概念，对事件有强的描述能力，让描述更接近于现实；扩展了对事件的描述．能描述事件的随机发生，我们已将之成功地应用于对超文本协议的描述．     

Compact Data Structures and State-Space Reduction for Model-Checking Real-Time Systems

During the past few years, a number of verification tools have been developed for real-time systems in the framework of timed automata. One of the major problems in applying these tools to industrial-sized systems is the huge memory-usage for the exploration of the state-space of a network (or product) of timed automata, as the model-checkers must keep information about not only the control structure of the automata but also the clock values specified by clock constraints. In this paper, we present a compact data structure for representing clock constraints. The data structure is based on an O(n ³) algorithm which, given a constraint system over real-valued variables consisting of bounds on differences, constructs an equivalent system with a minimal number of constraints. In addition, we have developed an on-the-fly reduction technique to minimize the space-usage. Based on static analysis of the control structure of a network of timed automata, we are able to compute a set of symbolic states that cover all the dynamic loops of the network in an on-the-fly searching algorithm, and thus ensure termination in reachability analysis. The two techniques and their combination have been implemented in the tool UPPAAL. Our experimental results demonstrate that the techniques result in truly significant space-reductions: for six examples from the literature, the space saving is between 75% and 94%, and in (nearly) all examples time-performance is improved. Noteworthy is also the observation that the two techniques are completely orthogonal.