Compositional verification of real-time systems using Ecdar

We present a specification theory for timed systems implemented in the Ecdar tool. We illustrate the operations of the specification theory on a running example, showing the models and verification checks. To demonstrate the power of the compositional verification, we perform an in depth case study of a leader election protocol; Modeling it in Ecdar as Timed input/output automata Specifications and performing both monolithic and compositional verification of two interesting properties on it. We compare the execution time of the compositional to the classical verification showing a huge difference in favor of compositional verification.     

Evaluating a new communication protocol for real-time distributed control

The recent trend in distributed automation and control systems has been towards event-triggered system architectures such as UML and IEC 61499. Although existing communication protocols (e.g., Ethernet) can support high-level communication within these systems, there is contention as to which low-level protocol to use, or if any exist that meet the requirements of being event-triggered and hard real-time. This paper proposes a new way to measure communication performance. The goal of the new measurement method is to stress the necessity that a real-time communication protocol needs to be both efficient and fair. This is illustrated by comparing three communication strategies: Controller Area Network (CAN), Time-Triggered CAN (TTCAN) and Escalating Priority CAN (EPCAN). The first two represent the extremes between event-triggered and time-triggered communication strategies; the third is introduced to illustrate the benefits of a new event-based communication protocol proposed by the authors.     

Compositional verification of real-time systems with Explicit Clock Temporal Logic

To specify and verify real-time systems, we consider a real-time version of temporal logic called Explicit Clock Temporal Logic. Timing properties are specified by extending the classical framework of temporal logic with a special variable which explicitly refers to a global notion of time. Programs are written in an Occam-like real-time language with synchronous message passing. To show that a program satisfies a specification, we formulate a proof system which is proved to be sound and relatively complete. The proof system is compositional, which makes it possible to decompose the design of a large system into the design of subsystems. This is shown by the verification of a small part of an avionics system.This research was supported by ESPRIT-BRA project 3096 Formal Methods and Tools for the Development of Distributed and Real-Time Systems (SPEC).     

Efficient verification of distributed real-time systems with broadcasting behaviors

Binary synchronization has been used extensively in the construction of mathematical models for the verification of embedded systems. Although it allows for the modeling of complex cooperation among many processes in a natural environment, not many tools have been developed to support the modeling capability in this regard. In this article, we first give examples to argue that special algorithms are needed for the efficient verification of systems with complex synchronizations. We then define our models of distributed real-time systems with synchronized cooperation among many processes. We present algorithms for the construction of BDD-like diagrams for the characterization of complex synchronizations among many processes. We present weakest precondition algorithms that take advantage of the just-mentioned BDD-like diagrams for the efficient verification of complex real-time systems. Finally, we report experiments and argue that the techniques could be useful in practice.     

基于仲裁的身份真实性实时确认机制的研究与实现

信息加密技术是信息安全的基础与核心。经典加密法、现代加密法和消息或消息认证码的结合使用很好地解决了信息交换过程中的机密性、抗否定性与完整性。这三大特性构成了安全信息交换的前提与基础,在此过程中,人们忽略了因公钥的不安全性和私钥管理不善而造成的身份真实性确认的虚假性。该文通过仲裁、公钥系统和用户生成的第二把随机私钥与对称加密算法相结合使用的技术将为公钥系统的安全性确认和收发双方的身份的真实性确认提供一条新的思路与方法。     

A distributed multicast routing protocol for real-time multicast applications

Multicast routing is establishing a tree which is rooted from the source node and contains all the multicast destinations. A delay bounded routing tree is a tree in which the accumulated delay from the source node to any destination along the tree does not exceed a pre-specified bound. This paper presents a distributed routing protocol which constructs delay bounded routing trees for real-time multicast connections. A constructed routing tree has a near optimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages required, and flexible in multicast membership changes. A large number of simulations have been done to show the network cost of the routing trees generated by our method is better than the other major existing algorithms.     

Compositional semantics of a real-time prototyping language

The formal semantics of a prototyping language for hard real-time systems, PSDL, is given. PSDL provides a data flow notation augmented by application-orientation timing and control constraints to describe a system as a hierarchy of networks of processing units communicating via data streams. The semantics of PSDL are defined in terms of algebraic high-level Petri nets. This formalism combines algebraic specifications of abstract data types with process and concurrency concepts of Petri nets. Its data abstraction facilities are used to define the meaning of PSDL data types, while high-level Petri nets serve to model the casual and timing behavior of a system. The net model exposes potential concurrency of computation and makes all synchronization needs implied by timing and control constraints explicit and precise. Time is treated as state of clocks, and clocks are modeled as ordinary system components. The net semantics provides the basis for applying analysis techniques and semantic tools available for high-level Petri nets     

On design and formal verification of SNSP: a novel real-time communication protocol for safety-critical applications

The correct operation of time-triggered protocols highly depends on the well-synchronized clocks of the system. To maintain the global time, one strict constraint must be exerted on communication activities (e.g. temporal padding and sparse time base etc.), which not only increases complexity of the protocol design but also incurs a penalty in the network utilization. While for event-triggered protocols, it is difficult to achieve the real-time requirement and determinism. Therefore, it is necessary to explore the combination of the advantages of these two categories of protocol for applications in different scenarios. This paper proposes the Safe Node Sequence Protocol (SNSP), which is a variant of full time-triggered protocol TTP/C. In SNSP, a strict node sequence is defined and the order of communication events is established by this pre-configured order without binding to global time, so the protocol changes communication activities and error detection to an event-triggered model. Therefore, SNSP possesses the characteristics of both time-triggered and event-triggered model. Also, the potential impact of global time, such as byzantine clock failure, on the protocol is eliminated. At the same time, the formal verification of SNSP is much easier in the absence of global time. Moreover, we model the protocol and use formal checker SPIN to validate the basic fault-tolerant requirement of SNSP. The simulation results show the protocol enables better resource utilization and is more effective.     

Invariant-based verification of a distributed deadlock detectionalgorithm

It is argued that most previous proposals for distributed deadlock detection are incorrect because they have used informal/intuitive arguments to prove the correctness of their algorithms. Informal and intuitive arguments are prone to errors because of the highly complex nature of distributed deadlock detection/resolution algorithms. The priority-based probe algorithm for distributed deadlock detection and resolution of A.L. Choudhary et al. (1989) is corrected, and it is formally proven that the modified algorithm is correct (i.e., that it does detect all deadlocks and does not report phantom deadlocks). The proof technique is novel in that the authors first abstract the properties of the deadlock detection and resolution algorithm by invariants, and then show that the invariants imply the desired correctness of the algorithm     

Compositional analysis for verification of parameterized systems

Many safety-critical systems that have been considered by the verification community are parameterized by the number of concurrent components in the system, and hence describe an infinite family of systems. Traditional model checking techniques can only be used to verify specific instances of this family. In this paper, we present a technique based on compositional model checking and program analysis for automatic verification of infinite families of systems. The technique views a parameterized system as an expression in a process algebra (CCS) and interprets this expression over a domain of formulas (modal mu-calculus), considering a process as a property transformer. The transformers are constructed using partial model checking techniques. At its core, our technique solves the verification problem by finding the limit of a chain of formulas. We present a widening operation to find such a limit for properties expressible in a subset of modal mu-calculus. We describe the verification of a number of parameterized systems using our technique to demonstrate its utility.     

Compositional verification of sequential programs with procedures

We present a method for algorithmic, compositional verification of control-flow-based safety properties of sequential programs with procedures. The application of the method involves three steps: (1) decomposing the desired global property into local properties of the components, (2) proving the correctness of the property decomposition by using a maximal model construction, and (3) verifying that the component implementations obey their local specifications. We consider safety properties of both the structure and the behaviour of program control flow. Our compositional verification method builds on a technique proposed by Grumberg and Long that uses maximal models to reduce compositional verification of finite-state parallel processes to standard model checking. We present a novel maximal model construction for the fragment of the modal μ-calculus with boxes and greatest fixed points only, and adapt it to control-flow graphs modelling components described in a sequential procedural language. We extend our verification method to programs with private procedures by defining an abstraction, presented as an inlining transformation. All algorithms have been implemented in a tool set automating all required verification steps. We validate our approach on an electronic purse case study.     

HARTS: a distributed real-time architecture

The design, implementation, and evaluation of a distributed real-time architecture called HARTS (hexagonal architecture for real-time systems) are discussed, emphasizing its support of time-constrained, fault-tolerant communications and I/O (input/output) requirements. HARTS consists of shared-memory multiprocessor nodes, interconnected by a wrapped hexagonal mesh. This architecture is intended to meet three main requirements of real-time computing: high performance, high reliability, and extensive I/O. The high-level and low-level architecture is described. The evaluation of HARTS, using modeling and simulation with actual parameters derived from its implementation, is reported. Fault-tolerant routing, clock synchronization and the I/O architecture are examined     

Automatic verification for a class of distributed systems

Summary. The paper presents a new analysis method for a class of concurrent systems which are formed of several interacting components with the same structure. The model for these systems is composed of a control process and a set of homogeneous user processes. The control and user processes are modeled by finite labeled state transition systems which interact by means of enabling functions and triggering mechanisms. Based on this structure, an analysis method is presented which allows system properties, derived by reachability analysis for a finite number of user processes, to be generalized to an arbitrary number of user processes. A procedure for the automatic verification of properties such as mutual exclusion and absence of deadlocks is presented and is then used to provide for the first time a fully automated verification of the Lamport's fast mutual exclusion algorithm. Received: October 1998/Accepted January 2000     

Symbolic path-based protocol verification

The principal problem in protocol verification is state explosion problem. In our work (W.C. Liu, C.G. Chung, Path-based Protocol Verification Approach, Technical Report, Department of Computer Science and Information Engineering, National Chiao-Tung University, Hsin-Chu, Taiwan, ROC, 1998), we have proposed a “divide and conquer” approach to alleviate this problem, the path-based approach. This approach separates the protocol into a set of concurrent paths, each of which can be generated and verified independently of the others. However, reachability analysis is used to identify the concurrent paths from the Cartesian product of unit paths, and it is time-consuming. Therefore, in this paper, we propose a simple and efficient checking algorithm to identify the concurrent paths from the Cartesian product, using only Boolean and simple arithmetic operations.     

Compositional verification of concurrent systems by combining bisimulations

Formal Methods in System Design - One approach to verify a property expressed as a modal $$mu $$ -calculus formula on a system with several concurrent processes is to build the underlying state...     

Formal development and verification of a distributed railwaycontrol system

The authors introduce the concept for a distributed railway control system and present the specification and verification of the main algorithm used for safe distributed control. Our design and verification approach is based on the RAISE method, starting with highly abstract algebraic specifications which are transformed into directly implementable distributed control processes by applying a series of refinement and verification steps. Concrete safety requirements are derived from an abstract version that can be easily validated with respect to soundness and completeness. Complexity is further reduced by separating the system model into a domain model and a controller model. The domain model describes the physical system in absence of control and the controller model introduces the safety-related control mechanisms as a separate entity monitoring observables of the physical system to decide whether it is safe for a train to move or for a point to be switched