Catálogo de publicaciones - libros

We study the use of some verification techniques for reasoning about temporal properties of CommUnity designs. We concentrate on the verification of temporal properties in the context of branching-time temporal logic using the SMV tool.

We also discuss ways of modularising the temporal reasoning, by exploiting the various kinds of morphisms between designs available in CommUnity. Moreover, we combine SMV verification with some abstract interpretation mechanisms to overcome a limitation, with respect to the use of structure for simplification of verification, of CommUnity’s refinement morphisms, the lack of support for data refinement.

A formal specification, written in a mathematical notation, is beyond the comprehension of the average software customer. As a result, the customer cannot provide useful feedback regarding its correctness and completeness. To address this problem, we suggest the formalism expert to work with the customer to create precise scenarios. With only a few simple Z concepts, a precise scenario describes an operation by its effects on the system state. The customer would find a concrete precise scenario easier to understand than its corresponding abstract schema. The Z expert derives schemas based on the precise scenarios. Precise scenarios afford user involvement that improves the odds of a formal specification fully capturing the user requirements.

This paper describes an approach for the automated verification of mobile programs. Mobile systems are characterized by the explicit notion of locations (e.g., sites where they run) and the ability to execute at different locations, yielding a number of security issues. We give formal semantics to mobile systems as Labeled Kripke Structures, which encapsulate the notion of the location net. The location net summarizes the hierarchical nesting of threads constituting a mobile program and enables specifying security policies. We formalize a language for specifying security policies and show how mobile programs can be exhaustively analyzed against any given security policy by using model checking techniques.

We developed and experimented with a prototype framework for analysis of mobile code, using the SATABS model checker. Our approach relies on SATABS’s support for unbounded thread creation and enhances it with location net abstractions, which are essential for verifying large mobile programs. Our experimental results on various benchmarks are encouraging and demonstrate advantages of the model checking-based approach, which combines the validation of security properties with other checks, such as for buffer overflows.

The high-level specification language CSP-OZ-DC has been shown to be well-suited for modelling and analysing industrially relevant concurrent real-time systems. It allows us to model each of the most important functional aspects such as control flow, data, and real-time requirements in adequate notations, maintaining a common semantic foundation for subsequent verification. Slicing on the other hand has become an established technique to complement the fight against state space explosion during verification which inherently accompanies increasing system complexity. In this paper, we exploit the special structure of CSP-OZ-DC specifications by extending the dependence graph—which usually serves as a basis for slicing—with several new types of dependencies, including timing dependencies derived from the specification’s DC part. Based on this we show how to compute a specification slice and prove correctness of our approach.

We present a generic framework of UTP theories for describing systems whose behaviour is characterised by regular time-slots, compatible with the general structure of the language [WC01a]. This “slotted-” framework is parameterised by the particular way in which event histories are observable within a time-slot, and specifies what laws a desired parameterisation must obey in order for a satisfactory theory to emerge.

Two key results of this work are: the need to be very careful in formulating the healthiness conditions, particularly ; and the demonstration that synchronous theories like SCSP [Bar93] do not fit well with the way reactive systems are currently formulated in UTP and .

Safe data abstractions are widely used for verification purposes. Positive verification results can be transferred from the abstract to the concrete system. When a property is violated in the abstract system, one still has to check whether a concrete violation scenario exists. However, even when the violation scenario is not reproducible in the concrete system (a false negative), it may still contain information on possible sources of bugs.

Here, we propose a bug hunting framework based on abstract violation scenarios. We first extract a violation pattern from one abstract violation scenario. The violation pattern represents multiple abstract violation scenarios, increasing the chance that a corresponding concrete violation exists. Then, we look for a concrete violation that corresponds to the violation pattern by using constraint solving techniques. Finally, we define the class of counterexamples that we can handle and argue correctness of the proposed framework.

Our method combines two formal techniques, model checking and constraint solving. Through an analysis of contracting and precise abstractions, we are able to integrate overapproximation by abstraction with concrete counterexample generation.

This paper illustrates a technique to automatically derive intra-object behaviours (in the form of state diagrams) from an object model. We demonstrate how we may take specifications, written in a restricted language of pre- and postconditions, and generate protocols of usage that represent possible behaviours of the generated program. We discuss how to use these state diagrams to analyse the specification for errors, and how to produce correct abstractions to show a particular class of properties of a system. This approach proves successful and scalable for specific domains of application such as database systems and e-commerce websites.

This paper studies the laws of communicating sequential processes (CSP) with Z-like initial and final states. Instead of defining a large semantics including all observable aspects, we incrementally develop the model in three stages: partially correct relational model, then totally correct sequential model and finally the reactive-process model with states. The properties of each model are captured as algebraic laws. A law in one model may or may not be true in its submodels. We apply a technique based on healthiness conditions to identify the conditions for law inheritance. Such abstract conditions themselves can be captured as pattern laws of commutativity. The model uses a new approach to define parallel compositions using just the primitive commands, nondeterministic choice, conjunction and some unary (hiding) operators.

The notation has been developed as a method for systematically and traceably capturing user requirements. In this paper we extend the notation with behaviour, so that reliability, performance, and other dependability properties can be expressed. The semantics of probabilistic timed Behavior Trees is given by mapping them to probabilistic timed automata. We gain advantages for requirements capture using Behavior Trees by incorporating into the notation an existing elegant specification formalism (probabilistic timed automata) which has tool support for formal analysis of probabilistic user requirements.

Finding inductive invariants is a key issue in many domains such as program verification, model based testing, etc. However, few approaches help the designer in the task of writing a correct and meaningful model, where correction is used for consistency of the formal specification w.r.t. its inner invariant properties. Meaningfulness is obtained by providing many explicit views of the model, like animation, counter-example extraction, and so on. We propose to ease the task of writing a correct and meaningful formal specification by combining a panel of provers, a set-theoretical constraint solver and some model-checkers.