Catálogo de publicaciones - libros

Computational grids have become popular for constructing large scale distributed systems. Grid applications typically run in a very heterogeneous environment and fault tolerance is therefore very important for their correctness. Since the construction of correct distributed systems is difficult with traditional development methods we propose the use of formal methods. We use Event B as our formal framework, which we extend with new constructs such as remote procedures and notifications for reasoning about grid systems. The extended language, called Distributed B, ensures that the application can handle both node and network failures. Furthermore, the new constructs in Distributed B enable straightforward implementation of the specifications, as well as automatic generation of the needed proof obligations.

In this paper, we relate an experiment whose aim is to study how to combine two existing approaches for ensuring software correctness: Domain Specific Languages (DSLs) and formal methods. As examples, we consider the Bossa DSL and the B formal method. Bossa is dedicated to the development of process schedulers and has been used in the context of Linux and Chorus. B is a refinement based formal method which has especially been used in the domain of railway systems. In this paper, we use B to express the correctness of a Bossa specification. Furthermore, we show how B can be used as an alternative to the existing Bossa tools for the production of certified schedulers.

eb ^3 is a trace-based formal language created for the specification of information systems (IS). Attributes, linked to entities and associations of an IS, are computed in eb ^3 by recursive functions on the valid traces of the system. On the other hand, B is a state-based formal language also well adapted for the specification of IS. In this paper, we deal with the synthesis of B specifications that correspond to eb ^3 attribute definitions, in order to specify and verify safety properties like data integrity constraints. Each action in the eb ^3 specification is translated into a B operation. The substitutions are obtained by an analysis of the CAML-like patterns used in the recursive functions that define the attributes in eb ^3. Our technique is illustrated by an example of a simple library management system.

Community Z Tools (CZT) is an integrated framework for the Z formal specification language. In this paper, we show how it is also designed to support extensions of Z, in a way that minimises the work required to build a new Z extension. The goals of the framework are to maximise extensibility and reuse, and minimise code duplication and maintenance effort. To achieve these goals, CZT uses a variety of different reuse mechanisms, including generation of Java code from a hierarchy of XML schemas, XML templates for shared code, and several design patterns for maximising reuse of Java code. The CZT framework is being used to implement several integrated formal methods, which add object-orientation, real-time features and process algebra extensions to Z. The effort required to implement such extensions of Z has been dramatically reduced by using the CZT framework.

We present an embedding of the stable failures model of CSP in the PVS theorem prover. Our work, extending a previous embedding of the traces model of CSP in [6], provides a platform for the formal verification not only of safety specifications, but also of liveness specifications of concurrent systems in theorem provers. Such a platform is particularly good at analyzing infinite-state systems with an arbitrary number of components. We demonstrate the power of this embedding by using it to construct formal proofs that the asymmetric dining philosophers problem with an arbitrary number of philosophers is deterministic and deadlock-free, and that an industrial-scale example, a ‘virtual network’ [21], with any number of dimensions, is deadlock-free. We have established some generic proof tactics for verification of properties of networks with many components. In addition, our technique of integrating FDR and PVS in our demonstration allows for handling of systems that would be difficult or impossible to analyze using either tool on its own.

We present an industrial project conducted at Ericsson Danmark A/S, Telebit where formal methods in the form of Coloured Petri Nets (CP-nets or CPNs) have been used for the specification of an interoperability protocol for routing packets between fixed core networks and mobile ad-hoc networks. The interoperability protocol ensures that a packet flow between a host in a core network and a mobile node in an ad-hoc network is always relayed via one of the closest gateways connecting the core network and the mobile ad-hoc network. This paper shows how integrated use of CP-nets and application-specific visualisation have been applied to build a model-based prototype of the interoperability protocol. The prototype consists of two parts: a CPN model that formally specifies the protocol mechanisms and a graphical user interface for experimenting with the protocol. The project demonstrates that the use of formal modelling combined with the use of application-specific visualisation can be an effective approach to rapidly construct an executable prototype of a communication protocol.

A natural approach for the description of asynchronous hardware designs are hardware process algebras, such as Martin’s Chp (Communicating Hardware Processes) , Tangram , or Balsa , which are extensions of standard process algebras with particular operators exploiting the implementation of synchronisation using handshake protocols. In this paper, we give a structural operational semantics for value-passing Chp . Compared to existing semantics of Chp defined by translation into Petri nets, our semantics handles value-passing Chp with communication channels open to the environment and is independent of any particular (2- or 4-phase) handshake protocol used for circuit implementation. In a second step, we describe the translation of Chp into the standard process algebra Lotos, in order to allow the application of the Cadp verification toolbox to asynchronous hardware designs. A prototype translator from Chp to Lotos has been successfully used for the compositional veri.cation of the control part of an asynchronous circuit implementing the DES (Data Encryption Standard) .

IVR (Interactive Voice Response) services are introduced with reference to VoiceXML (Voice eXtensible Markup Language). It is explained how IVR services can benefit from an underlying formalism and rigorous analysis. IVR services are modelled using Cress (Chisel Representation Employing Systematic Specification) as a high-level graphical notation. Apart from being able to describe services, Cress also introduces the notion of features. The translation of IVR descriptions into SDL is explored, along with how the generated SDL can be formally analysed.

We present a fixpoint semantics of event systems. The semantics is presented in a general framework without concerns of fairness. Soundness and completeness of rules for deriving leads-to properties are proved in this general framework. The general framework is instantiated to minimal progress and weak fairness assumptions and similar results are obtained. We show the power of these results by deriving sufficient conditions for leads-to under minimal progress proving soundness of proof obligations without reasoning over state-traces.

UML 2.0, like UML 1.x, provides only a set of notations for specifying different aspects of a system. The problem of checking consistency between various types of models in software development is still not fully addressed. In this paper, we suggest the use of an algebraic approach for verifying whether consistency between sequence diagrams and statechart diagrams is preserved. First, statechart diagrams are encoded in the π -calculus. Then, each object in a sequence diagram is translated into its equivalent π -calculus definitions and verified against the corresponding statechart diagram represented in the π -calculus using the Mobility Workbench. The applicability of the proposed approach is illustrated with an agent-based payment protocol.