Verifying a signature architecture: a comparative case study

We report on a case study in applying different formal methods to model and verify an architecture for administrating digital signatures. The architecture comprises several concurrently executing systems that authenticate users and generate and store digital signatures by passing security relevant data through a tightly controlled interface. The architecture is interesting from a formal-methods perspective as it involves complex operations on data as well as process coordination and hence is a candidate for both data-oriented and process-oriented formal methods. We have built and verified two models of the signature architecture using two representative formal methods. In the first, we specify a data model of the architecture in Z that we extend to a trace model and interactively verify by theorem proving. In the second, we model the architecture as a system of communicating processes that we verify by finite-state model checking. We provide a detailed comparison of these two different approaches to formalization (infinite state with rich data types versus finite state) and verification (theorem proving versus model checking). Contrary to common belief, our case study suggests that Z is well suited for temporal reasoning about process models with complex operations on data. Moreover, our comparison highlights the advantages of proving theorems about such models and provides evidence that, in the hands of an experienced user, theorem proving may be neither substantially more time-consuming nor more complex than model checking.     

How to model and prove hybrid systems with KeYmaera: a tutorial on safety

This paper is a tutorial on how to model hybrid systems as hybrid programs in differential dynamic logic and how to prove complex properties about these complex hybrid systems in KeYmaera, an automatic and interactive formal verification tool for hybrid systems. Hybrid systems can model highly nontrivial controllers of physical plants, whose behaviors are often safety critical such as trains, cars, airplanes, or medical devices. Formal methods can help design systems that work correctly. This paper illustrates how KeYmaera can be used to systematically model, validate, and verify hybrid systems. We develop tutorial examples that illustrate challenges arising in many real-world systems. In the context of this tutorial, we identify the impact that modeling decisions have on the suitability of the model for verification purposes. We show how the interactive features of KeYmaera can help users understand their system designs better and prove complex properties for which the automatic prover of KeYmaera still takes an impractical amount of time. We hope this paper is a helpful resource for designers of embedded and cyber–physical systems and that it illustrates how to master common practical challenges in hybrid systems verification.     

A formal analysis of bluetooth device discovery

This paper presents a formal analysis of the device discovery phase of the Bluetooth wireless communication protocol. The performance of this process is the result of a complex interaction between several devices, some of which exhibit random behaviour. We use probabilistic model checking and, in particular, the tool PRISM to compute the best- and worst-case performance of device discovery: the expected time for the process to complete and the expected power consumption. We illustrate the utility of performing an exhaustive, low-level analysis to produce exact results in contrast to simulation techniques, where additional probabilistic assumptions must be made. We demonstrate an example of how seemingly innocuous assumptions can lead to incorrect performance estimations. We also analyse the effectiveness of improvements made between versions 1.1 and 1.2 of the Bluetooth specification.     

Verifying an infinite systolic algorithm using third-order equational methods

We consider using third-order equational methods to formally verify that an infinite systolic algorithm correctly implements a family of convolution functions. The detailed case study we present illustrates the use of third-order algebra as a formal framework for developing families of computing systems. It also provides an interesting insight into the use of infinite algorithms as a means of verifying a family of finite algorithms. We consider using purely equational reasoning in our verification proofs and in particular, using the rule of free variable induction. We conclude by considering how our verification proofs can be automated using rewriting techniques.     

A formal verification framework for SysML activity diagrams

SysML activity diagrams are OMG/INCOSE standard diagrams used for modeling and specifying probabilistic systems. They support systems composition by call behavior and send/receive artifacts. For verification, the existing approaches dedicated to these diagrams are limited to a restricted set of artifacts. In this paper, we propose a formal verification framework for these diagrams that supports the most important artifacts. It is based on mapping a composition of SysML activity diagrams to the input language of the probabilistic symbolic model checker called “PRISM”. To prove the soundness of our mapping approach, we capture the underlying semantics of both the SysML activity diagrams and their generated PRISM code. We found that the probabilistic equivalence relation between both semantics preserve the satisfaction of the system requirements. Finally, we demonstrate the effectiveness of our approach by presenting real case studies.     

基于UPPAAL的微内核操作系统程序验证方法研究

随着航天、航空工业的发展,机载嵌入式软件的可信属性验证是新一代飞机研制最关注的软件质量保障问题。形式化方法具有严密的数学基础,能够准确的对系统进行建模、描述和验证,能够在软件系统的设计初期发现潜在的错误,是保证机载软件可信性和安全性的软件正确性验证技术。形式化验证以形式化描述为基础,对所描述系统的特性进行分析和验证,以评判系统是否满足期望的性质,分为定理证明和模型检测两类。文章研究模型检测方法应用于程序形式化描述和验证的技术,提出基于模型检测的验证程序正确性的方案,并进行微内核操作系统程序分析,最后在UPPAAL中进行程序属性的验证。     

Automatic verification of the IEEE 1394 root contention protocol with KRONOS and PRISM

We report on the automatic verification of timed probabilistic properties of the IEEE 1394 root contention protocol combining two existing tools: the real-time model checker Kronos and the probabilistic model checker Prism. The system is modelled as a probabilistic timed automaton. We first use Kronos to perform a symbolic forwards reachability analysis to generate the set of states that are reachable with non-zero probability from the initial state and before the deadline expires. We then encode this information as a Markov decision process to be analyzed with Prism. We apply this technique to compute the minimal probability of a leader being elected before a deadline, for different deadlines, and study how this minimal probability is influenced by using a biased coin and considering different wire lengths.     

MODEL CHECKING A KNOWLEDGE EXCHANGE SCENARIO

We are interested in applying model checking techniques to the verification of communication protocols that require safe communication. Typically, in such scenarios, one desires to demonstrate that one party can reliably communicate information to another party without a third party being able to determine this information. Our approach involves using the modal logic of knowledge, which has only relatively recently been studied in the context of security protocols. We demonstrate our approach by means of a detailed case study: the Russian cards problem. This is an example of a security protocol with nontrivial requirements on the knowledge of the agents involved. Using the Russian cards problem as an example, it is shown how the satisfaction of properties involving knowledge can be verified in a standard model checker, which in our case is SPIN.     

Checking Finite Traces Using Alternating Automata

Alternating automata have been commonly used as a basis for static verification of reactive systems. In this paper we show how alternating automata can be used in runtime verification. We present three algorithms to check at runtime whether a reactive program satisfies a temporal specification, expressed by a linear-time temporal logic formula. The three methods start from the same alternating automaton but traverse the automaton in different ways: depth-first, breadth-first, and backwards, respectively. We then show how an extension of these algorithms, that collects statistical data while verifying the execution trace, can be used for a more detailed analysis of the runtime behavior. All three methods have been implemented and experimental results are presented.     

Towards modeling and runtime verification of self-organizing systems

According to the fact that the intrinsic dynamism of self-organizing systems challenges the existing methods of engineering for modeling reliable complex systems, in this paper, we propose a new formal-based method to model self-organizing systems. The capabilities of the proposed method which are used to address several challenges in design, development and analysis of self-organizing systems are: modularity and robustness, decentralized control and scalability, required adaptation types, flexible and adaptive control mechanism, separation of adaptation and business logic, and safe adaptation. To evaluate the proposed method, we use self-organizing traffic management system as a case study and exploit the proposed method for modeling this dynamic system. Moreover, we propose and employ a novel policy-based runtime verification mechanism to ensure that the safety properties are satisfied by the implementation at runtime. We provide our case study prototype using Java and the Ponder2 toolkit and apply our runtime verification method to show its proper reaction capabilities to the property violations. This benefit is the result of using dynamic policies in our method to control the behavior of systems.     

Model checking agent programming languages

In this paper we describe a verification system for multi-agent programs. This is the first comprehensive approach to the verification of programs developed using programming languages based on the BDI (belief-desire-intention) model of agency. In particular, we have developed a specific layer of abstraction, sitting between the underlying verification system and the agent programming language, that maps the semantics of agent programs into the relevant model-checking framework. Crucially, this abstraction layer is both flexible and extensible; not only can a variety of different agent programming languages be implemented and verified, but even heterogeneous multi-agent programs can be captured semantically. In addition to describing this layer, and the semantic mapping inherent within it, we describe how the underlying model-checker is driven and how agent properties are checked. We also present several examples showing how the system can be used. As this is the first system of its kind, it is relatively slow, so we also indicate further work that needs to be tackled to improve performance.     

An object based algebra for specifying a fault tolerant software architecture

In this paper we present an algebra of actors extended with mechanisms to model crash failures and their detection. We show how this extended algebra of actors can be successfully used to specify distributed software architectures. The main components of a software architecture can be specified following an object-oriented style and then they can be composed using asynchronous message passing or more complex interaction patterns. This formal specification can be used to show that several requirements of a software system are satisfied at the architectural level despite failures. We illustrate this process by means of a case study: the specification of a software architecture for intelligent agents which supports a fault tolerant anonymous interaction protocol.     

Modeling dynamic reconfigurations in Reo using high-level replacement systems

Reo is a channel-based coordination language, wherein circuit-like connectors model and implement interaction protocols in heterogeneous environments that coordinate components or services. Connectors are constructed from primitive channels and can be reconfigured dynamically. Reconfigurations can even execute within a pending I/O transaction. In this article, we formally model and analyze dynamic reconfigurations and show how running coordinators can be reconfigured without the cooperation of their engaged components.We utilize the theory of high-level replacement systems to model rule-based reconfigurations of connectors. This allows us to perform a complex reconfiguration as an atomic step and analyze it using formal verification techniques. Specifically, we formalize the structure of connectors as typed hypergraphs and use critical pair and state space analyses for verification of dynamic reconfigurations. We provide a full implementation of our approach in a framework that includes tools for the definition, analysis, and execution of reconfigurations, and is integrated with two execution engines for Reo. Our framework, moreover, integrates with the graph transformation tools AGG and GROOVE for formal analysis, as well as the Eclipse platform and standard web service technologies.     

Dynamic epistemic logic of belief change in legal judgments

This study realizes belief/reliability change of a judge in a legal judgment by dynamic epistemic logic (DEL). A key feature of DEL is that possibilities in an agent’s belief can be represented by a Kripke model. This study addresses two difficulties in applying DEL to a legal case. First, since there are several methods for constructing a Kripke model, our question is how we can construct the model from a legal case. Second, since this study employs several dynamic operators, our question is how we can decide which operators are to be applied for belief/reliability change of a judge. In order to solve these difficulties, we have implemented a computer system which provides two functions. First, the system can generate a Kripke model from a legal case. Second, the system provides an inconsistency solving algorithm which can automatically perform several operations in order to reduce the effort needed to decide which operators are to be applied. By our implementation, the above questions can be adequately solved. With our analysis method, six legal cases are analyzed to demonstrate our implementation.     

Vulnerability analysis of networks to detect multiphase attacks using the actor-based language Rebeca

Increasing use of networks and their complexity make the task of security analysis more and more complicated. Accordingly, automatic verification approaches have received more attention recently. In this paper, we investigate applying of an actor-based language based on reactive objects for analyzing a network environment communicating via Transport Protocol Layer (TCP). The formal foundation of the language and available tools for model checking provide us with formal verification support. Having the model of a typical network including client and server, we show how an attacker may combine simple attacks to construct a complex multiphase attack. We use Rebeca language to model the network of hosts and its model checker to find counter-examples as violations of security of the system. Some simple attacks have been modeled in previous works in this area, here we detect these simple attacks in our model and then verify the model to find more complex attacks which may include simpler attacks as their steps. We choose Rebeca because of its powerful yet simple actor-based paradigm in modeling concurrent and distributed systems. As the real network environment is asynchronous and event-based, Rebeca can be utilized to specify and verify the asynchronous systems, including network protocols.     

On robust performance in

In this paper we consider the robust performance problem in with scalar perturbations. We illustrate how the worst case performance can be regarded as an norm of a function of several complex variables. Based on this characterization we show how the worst case performance can be obtained from the norm of a single system. This system is constructed from the original nominal system with the perturbations replaced by certain all-pass functions. We show that as the order of the all-pass functions goes to infinity, this norm converges to the worst case performance. The implications of this characterization for computing the complex structured singular value and robust synthesis are discussed, though at present, this method does not seem to provide an efficient algorithm for this computation.     

Verifying compiled file system code

This article presents a case study on retrospective verification of the Linux Virtual File System (VFS), which is aimed at checking violations of API usage rules and memory properties. Since VFS maintains dynamic data structures and is written in a mixture of C and inlined assembly, modern software model checkers cannot be applied. Our case study centres around our novel automated software verification tool, the SOCA Verifier, which symbolically executes and analyses compiled code. We describe how this verifier deals with complex features such as memory access, pointer aliasing and computed jumps in the VFS implementation, while reducing manual modelling to a minimum. Our results show that the SOCA Verifier is capable of analysing the complex Linux VFS implementation reliably and efficiently, thereby going beyond traditional testing tools and into niches that current software model checkers do not reach. This testifies to the SOCA Verifier’s suitability as an effective and efficient bug-finding tool during the development of operating system components.