Formal verification of context and situation models in pervasive computing

Pervasive computing is a paradigm that focuses on the availability of computer resources anytime anywhere for any application and supports non-intrusive integration of computing services into everyday life. Context awareness is the core feature of pervasive computing. High-level context awareness can be enhanced by situation awareness that represents the ability to detect and reason about the real-life situations. In this article we propose, analyze and validate the formal verification method for situation definitions and demonstrate its feasibility and efficiency. Situations are often defined manually by domain experts and are, therefore, susceptible to definition inconsistencies and possible errors, which in turn can cause situation reasoning problems. The proposed method takes as an input properties of situations and dependencies among them as well as situation definitions in terms of low-level context features, and then either formally proves that the definitions do comply with the expected properties, or provides a complete set of counterexamples — context parameters that prove situation inconsistency. Evaluation and complexity analysis of the proposed approach are also presented and discussed. Examples and evaluation results demonstrate that the proposed approach can be used to verify real-life situation definitions, and detect non-obvious errors in situation specifications.     

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     

Formal verification of a pipelined microprocessor

The application of modern functional languages and supporting verification technology to a scaled-down but realistic microprocessor is described. The model is of an infinite stream of machine instructions consuming an infinite stream of interrupt signals and is specified at two levels: instruction and hardware design. A correctness criterion is stated for an appropriate sense of equivalent behavior of these levels and proved using a mechanically supported induction argument. The functional-language-based verification system Clio and the Mini Cayuga microprocessor are described. The formal specification and verification process are examined in detail     

Formal verification of Ada programs

The Penelope verification editor and its formal basis are described. Penelope is a prototype system for the interactive development and verification of programs that are written in a rich subset of sequential Ada. Because it generates verification conditions incrementally, Penelope can be used to develop a program and its correctness proof in concert. If an already-verified program is modified, one can attempt to prove the modified version by replaying and modifying the original sequence of proof steps. Verification conditions are generated by predicate transformers whose logical soundness can be proven by establishing a precise formal connection between predicate transformation and denotational definitions in the style of continuation semantics. Penelope's specification language, Larch/Ada, belongs to the family of Larch interface languages. It scales up properly, in the sense that one can demonstrate the soundness of decomposing an implementation hierarchically and reasoning locally about the implementation of each node in the hierarchy     

Formal verification of human-automation interaction

This paper discusses a formal and rigorous approach to the analysis of operator interaction with machines. It addresses the acute problem of detecting design errors in human-machine interaction and focuses on verifying the correctness of the interaction in complex and automated control systems. The paper describes a systematic methodology for evaluating whether the interface provides the necessary information about the machine to enable the operator to perform a specified task successfully and unambiguously. It also addresses the adequacy of information provided to the user via training material (e.g., user manual) about the machine's behavior. The essentials of the methodology, which can be automated and applied to the verification of large systems, are illustrated by several examples and through a case study of pilot interaction with an autopilot aboard a modern commercial aircraft. The expected application of this methodology is an augmentation and enhancement, by formal verification, of human-automation interfaces.     

Formal verification of SysML diagram using case studies of real-time system

System and software engineers use SysML models for the graphical modeling of the embedded systems. The SysML models are inadequate to express the discrete controllers with continuously evolving variables. The real-time constraints such as discrete and continuous dynamics are considered to be an important aspect in embedded systems. The lack of support of real-time aspect in SysML model can lead to inexplicit modeling of the embedded systems. The imprecise modeling could cause catastrophic results when an embedded system gets operational. In this paper, we propose hybrid automata-based semantics that supports the discrete and continuous behavior in upgraded SysML block diagram. The upgraded SysML block diagram is used for the modeling of the embedded system. Furthermore, we use model checker PRISM for the early design verification of upgraded SysML block diagram. Finally, we demonstrate the effectiveness of our proposed approach with the help of two case studies “temperature control system” and “water level control system”.

     

Formal verification of security protocol implementations: a survey

Automated formal verification of security protocols has been mostly focused on analyzing high-level abstract models which, however, are significantly different from real protocol implementations written in programming languages. Recently, some researchers have started investigating techniques that bring automated formal proofs closer to real implementations. This paper surveys these attempts, focusing on approaches that target the application code that implements protocol logic, rather than the libraries that implement cryptography. According to these approaches, libraries are assumed to correctly implement some models. The aim is to derive formal proofs that, under this assumption, give assurance about the application code that implements the protocol logic. The two main approaches of model extraction and code generation are presented, along with the main techniques adopted for each approach.     

Formal verification of a generic framework to synthesize SAT-provers

We present in this paper an application of the ACL2 system to generate and reason about propositional satisfiability provers. For that purpose, we develop a framework in which we define a generic S AT-prover based on transformation rules, and we formalize this generic framework in the ACL2 logic, carrying out a formal proof of its termination, soundness, and completeness. This generic framework can be instantiated to obtain a number of verified and executable SAT-provers in ACL2, and this instantiation can be done in an automated way. Three instantiations of the generic framework are considered: semantic tableaux, sequent calculus, and Davis-Putnam-Logeman-Loveland methods.     

Formal verification of mobile robot protocols

Mobile robot networks emerged in the past few years as a promising distributed computing model. Existing work in the literature typically ensures the correctness of mobile robot protocols via ad hoc handwritten proofs, which, in the case of asynchronous execution models, are both cumbersome and error-prone. Our contribution is twofold. We first propose a formal model to describe mobile robot protocols operating in a discrete space i.e., with a finite set of possible robot positions, under synchrony and asynchrony assumptions. We translate this formal model into the DVE language, which is the input format of the model-checkers DiVinE and ITS tools, and formally prove the equivalence of the two models. We then verify several instances of two existing protocols for variants of the ring exploration in an asynchronous setting: exploration with stop and perpetual exclusive exploration. For the first protocol we refine the correctness bounds and for the second one, we exhibit a counter-example. This protocol is then modified and we establish the correctness of the new version with an inductive proof.     

Formal verification of conflict detection algorithms

Safety assessment of new air traffic management systems is a main issue for civil aviation authorities. Standard techniques such as testing and simulation have serious limitations in new systems that are significantly more autonomous than the older ones. In this paper, we present an innovative approach for establishing the correctness of conflict detection systems. Fundamental to our approach is the concept of trajectory, and how we represent a continuous physical trajectory by a continuous path in the x-y plane constrained by physical laws and operational requirements. From the model of trajectories, we extract, and formally prove, high-level properties that can serve as a framework to analyze conflict scenarios. We use the AILS (Airborne Information for Lateral Spacing) alerting algorithm as a case study of our approach. Published online: 19 November 2002     

Formal verification of a Cooperative Automatic Repeat reQuest MAC protocol

Cooperative communications, in which a relay node helps the source node to deliver its packets to the destination node, are able to obtain significant benefits in terms of transmission reliability, coverage extension and energy efficiency. A Cooperative Automatic Repeat reQuest (C-ARQ) MAC protocol has been recently proposed to exploit cooperative diversity at the MAC layer. In this paper, we validate the integrity and the validity of the C-ARQ protocol using formal methods. The protocol logic is modeled in SDL and implemented in PROMELA. The functionality of the C-ARQ protocol is verified through simulations and verifications using SPIN.     

一种多功能网络即时通讯系统的设计

分析目前互联网即时通讯工具存在的问题,提出一种网络即时通讯系统的设计方案,阐述该方案的具体设计和实现方法,实现了人性化的界面设计与功能设计。经测试,系统能满足人们即时通讯的需求,达到预期的设计效果。     

Formal verification of algorithms for critical systems

The authors describe their experience with formal, machine-checked verification of algorithms for critical applications, concentrating on a Byzantine fault-tolerant algorithm for synchronizing the clocks in the replicated computers of a digital flight control system. The problems encountered in unsynchronized systems and the necessity, and criticality, of fault-tolerant synchronization are described. An overview of one such algorithm and of the arguments for its correctness are given. A verification of the algorithm performed using the authors' EHDM system for formal specification and verification is described. The errors found in the published analysis of the algorithm and benefits derived from the verification are indicated. Based on their experience, the authors derive some key requirements for a formal specification and verification system adequate to the task of verifying algorithms of the type considered. The conclusions regarding the benefits of formal verification in this domain and the capabilities required of verification systems in order to realize those benefits are summarized     

即时消息传递系统的安全性

即时消息传递(IM——Installt messaging)是Internet上日渐普及的一种通信方法。在介绍IM系统工作方式的基础上,讨论了当前IM系统由于设计上的脆弱性而导致的各种潜在的安全威胁,对如何保障IM系统的安全提出了一些方法和建议。     

Formal hardware verification methods: A survey

Growing advances in VLSI technology have led to an increased level of complexity in current hardware systems. Late detection of design errors typically results in higher costs due to the associated time delay as well as loss of production. Thus it is important that hardware designs be free of errors. Formal verification has become an increasingly important technique towards establishing the correctness of hardware designs. In this article we survey the research that has been done in this area, with an emphasis on more recent trends. We present a classification framework for the various methods, based on the forms of the specification, the implementation, and the proff method. This framework enables us to better highlight the relationships and interactions between seemingly different approaches.     

UML状态机模型形式化验证技术研究

系统建模是系统开发经常用到的分析设计方法,如何保证模型的正确性一直是人们关注的话题.为了验证系统设计的模型正确性,进而提高整个系统的质量,提出了一种通过模型检查技术对UML状态机模型进行动态语义验证的方法.对状态机模型进行形式化描述,根据定义的映射规则将图形信息映射成模型检查器可以读取的语言,分析待验证的性质内容,通过使用模型检查器得到验证结果.