Tank Monitoring: A pAMN Case Study

The introduction of probabilistic behaviour into the B-Method is a recent development. In addition to allowing probabilistic behaviour to be modelled, the relationship between expected values of the machine state can be expressed and verified. This paper explores the application of probabilistic B to a simple case study: tracking the volume of liquid held in a tank by measuring the flow of liquid into it. The flow can change as time progresses, and sensors are used to measure the flow with some degree of accuracy and reliability, modelled as non-deterministic and probabilistic behaviour respectively. At the specification level, the analysis is concerned with the expectation clause in the probabilistic B machine and its consistency with machine operations. At the refinement level, refinement and equivalence laws on probabilistic GSL are used to establish that a particular design of sensors delivers the required level of reliability.     

ArcAngel: a Tactic Language for Refinement

Morgan's refinement calculus is a successful technique for developing software in a precise and consistent way. This technique, however, can be hard to use, as developments may be long and repetitive. Many authors have pointed out that a lot can be gained by identifying commonly used development strategies, documenting them as tactics, and using them as single transformation rules. Also, it is useful to have a notation for describing derivations, so that they can be analysed and modified. In this paper, we present ArcAngel, a language for defining such refinement tactics; we present the language, its semantics, and some of its algebraic laws. Apart from Angel, a general-purpose tactic language that we are extending, no other tactic language has a denotational semantics and proof theory of its own.     

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.     

Retrenching partial requirements into system definitions: a simple feature interaction case study

In conventional model-oriented formal refinement, the abstract model is supposed to capture all the properties of interest in the system, in an as-clutter-free-as-possible manner. Subsequently, the refinement process guides development inexorably towards a faithful implementation. However, refinement says nothing about how to obtain the abstract model in the first place. In reality developers experiment with prototype models and their refinements until a workable arrangement is discovered.Retrenchment is a formal technique intended to capture some of the informal approach to a refinable abstract model in a formal manner that will integrate with refinement. This is in order that the benefits of a formal approach can migrate further up the development hierarchy. The basic ideas of retrenchment are presented, and a simple telephone system feature interaction case study is elaborated. This illustrates not only how retrenchment can relate incompatible and partial models to a more definitive consolidated model during the development of the contracted specification, but also that the same formalism is applicable in a re-engineering context, where the subsequent evolution of a system may be partly incompatible with earlier design decisions. The case study illustrates how the natural method of composing retrenchments can give results that are too liberal in certain cases, and stronger laws of composition are derived for systems possessing suitable properties. It is shown that the methodology can encompass more ad hoc and custom-built techniques such as Zave's layered feature engineering approach to applications exhibiting a feature-oriented architecture (such as telephony).

Using formal methods to increase confidence in a home network system implementation: a case study

A home network system consists of multiple networked appliances, intended to provide more convenient and comfortable living for home users. Before being deployed, one has to guarantee the correctness, the safety, and the security of the system. Here, we present the approach chosen to validate the Java implementation of a home network system. We rely on the Java Modelling Language to formally specify and validate an abstraction of the system. This is a substantially revised version of our paper that appeared in the proceedings of the Workshop On Leveraging Applications of Formal Methods, Verification and Validation (ISoLA), Poitiers-Futuroscope, France, December 2007.     

Sound refactorings

Refactoring consists in restructuring an object-oriented program without changing its behaviour. In this paper, we present refactorings as transformation rules for programs written in a refinement language inspired on Java that allows reasoning about object-oriented programs and specifications. A set of programming laws is available for the imperative constructs of this language as well as for its object-oriented features; soundness of the laws is proved against a weakest precondition semantics. The proof that the refactoring rules preserve behaviour (semantics) is accomplished by the application of these programming laws and data simulation. As illustration of our approach to refactoring, we use our rules to restructure a program to be in accordance with a design pattern.     

Formal models for user interface design artefacts

There are many different ways of building software applications and of tackling the problems of understanding the system to be built, designing that system and finally implementing the design. One approach is to use formal methods, which we can generalise as meaning we follow a process which uses some formal language to specify the behaviour of the intended system, techniques such as theorem proving or model-checking to ensure the specification is valid (i.e., meets the requirements and has been shown, perhaps by proof or other means of inspection, to have the properties the client requires of it) and a refinement process to transform the specification into an implementation. Conversely, the approach we take may be less structured and rely on informal techniques. The design stage may involve jotting down ideas on paper, brainstorming with users etc. We may use prototyping to transform these ideas into working software and get users to test the implementation to find problems. Formal methods have been shown to be beneficial in describing the functionality of systems, what we may call application logic, and underlying system behaviour. Informal techniques, however, have also been shown to be useful in the design of the user interface to systems. Given that both styles of development are beneficial to different parts of the system we would like to be able to use both approaches in one integrated software development process. Their differences, however, make this a challenging objective. In this paper we describe models and techniques which allow us to incorporate informal design artefacts into a formal software development process.     

Model evolution and refinement

Software changes during its lifetime. Likewise, software models change during their design time, e.g. by removing, adding or changing operations and classes. This is referred to as model evolution. In a refinement-based approach to software design, we moreover do not deal with a single but with a chain of models (viz. formal specifications), related via refinement. Changes thus need to be consistently made to all specifications in the chain so as to keep the refinement structure.In this paper, we develop co-evolutions of models in the context of the formal method Object-Z. More specifically, given a particular evolution of a specification we show how to construct a corresponding evolution for its refinements such that the refinement relationship is kept. A chain of models can thus be systematically and consistently evolved, while maintaining the given refinement structure.     

The NDB database specified in the RAISE specification language

This paper answers a challenge designed to test the modularization features of specification languages. The RAISE Specification Language (RSL) is shown to have the power necessary to meet the challenge.Basic features of RSL, particularly those useful for the problem, are introduced. Two solutions to the problem are exhibited. The first follows the structure of the challenge problem very closely and is model-based in style. The second shows how RSL may be written in an algebraic style.An example of a proof of implementation is also given.     

Specifications: Formal and informal—a case study

Formal specifications (algebraic) are given for an informally specified small subsystem of the Change Management Automatic Build System. A comparison of the two specifications shows that although informal specifications are easier to read, the formal specifications are clearer, specify operation domains precisely, define the interaction between the operations, show the incompleteness of the informal specifications and are devoid of implementation details. The formal specifications pointed to the need of a function not in the subsystem whose inclusion would improve the system design. This inclusion is now being considered. However, the use of algebraic specifications requires practice and experience. Although the formal specification of large systems is somewhat impractical at the moment, experience in using formal specifications can lead to better informal specifications.     

Mutation Testing in the Refinement Calculus

This article discusses mutation testing strategies in the context of refinement. Here, a novel generalisation of mutation testing techniques is presented to be applied to contracts ranging from formal specifications to programs. It is demonstrated that refinement and its dual abstraction are the key notions leading to a precise and yet simple theory of mutation testing. The refinement calculus of Back and von Wright is used to express concepts like contracts, useful mutations, test cases and test coverage.     

Formal specification and testing: A case study

Z is a formal notation for writing system specifications that has been growing in popularity over recent years. This paper examines some of the issues involved in applying a ‘partition based’ testing method to a system specified in Z. Details of an extensive case study are given, from specification and implementation of the system to the development and execution of test cases. The strategy is found to have benefits compared to those based on less formal specifications, but there are limitations to the approach, and difficulties that need addressing.     

Simulation-based analysis of UML statechart diagrams: methods and case studies

We present a comprehensive unified modeling language (UML) statechart diagram analysis framework. This framework allows one to progressively perform different analysis operations to analyze UML statechart diagrams at different levels of model complexity. The analysis operations supported by the framework are based on analyzing Petri net models converted from UML statechart diagrams using a previously proposed transformation approach. After introducing the general framework, the paper emphasizes two simulation-based analysis operations from the framework: direct MSC inspection, which provides a visual representation of system behavior described by statechart diagrams; and a pattern-based trace query technique, which can be used to define and query system properties. Two case-study examples are presented with different emphasis. The gas station example is a simple multi-object system used to demonstrate both the visual and query-based analysis operations. The early warning system example uses only one object, but features composite states and includes analysis specifically aimed at one composite state feature, history states.

State explosion in almost-sure probabilistic reachability

We show that the problem of reaching a state set with probability 1 in probabilistic-nondeterministic systems operating in parallel is EXPTIME-complete. We then show that this probabilistic reachability problem is EXPTIME-complete also for probabilistic timed automata.     

Using probabilistic model checking for dynamic power management

Dynamic power management (DPM) refers to the use of runtime strategies in order to achieve a tradeoff between the performance and power consumption of a system and its components. We present an approach to analysing stochastic DPM strategies using probabilistic model checking as the formal framework. This is a novel application of probabilistic model checking to the area of system design. This approach allows us to obtain performance measures of strategies by automated analytical means without expensive simulations. Moreover, one can formally establish various probabilistically quantified properties pertaining to buffer sizes, delays, energy usage etc., for each derived strategy.Received November 2003Revised September 2004Accepted December 2004 by M. Leuschel and D. J. Cooke     

Reachability problems for Markov chains

We consider the following decision problem: given a finite Markov chain with distinguished source and target states, and given a rational number r, does there exist an integer n such that the probability to reach the target from the source in n steps is r? This problem, which is not known to be decidable, lies at the heart of many model checking questions on Markov chains. We provide evidence of the hardness of the problem by giving a reduction from the Skolem Problem: a number-theoretic decision problem whose decidability has been open for many decades.     

Precise visual modeling: A case-study

We develop an abstract model for our case-study: software to support a “video rental service.” This illustrates how a visual formalism, constraint diagrams, may be used in order to specify such systems precisely.     

VPM: A visual,precise and multilevel metamodeling framework for describing mathematical domains and UML (The Mathematics of Metamodeling is Metamodeling Mathematics)

As UML 2.0 is evolving into a family of languages with individually specified semantics, there is an increasing need for automated and provenly correct model transformations that (i) assure the integration of local views (different diagrams) of the system into a consistent global view, and, (ii) provide a well-founded mapping from UML models to different semantic domains (Petri nets, Kripke automaton, process algebras, etc.) for formal analysis purposes as foreseen, for instance, in submissions for the OMG RFP for Schedulability, Performance and Time. However, such transformations into different semantic domains typically require the deep understanding of the underlying mathematics, which hinders the use of formal specification techniques in industrial applications. In the paper, we propose a multilevel metamodeling technique with precise static and dynamic semantics (based on a refinement calculus and graph transformation) where the structure and operational semantics of mathematical models can be defined in a UML notation without cumbersome mathematical formulae.     

Road network monitoring: algorithms and a case study

Road network monitoring is an activity conducted daily by the Ministry of Transportation of Quebec. The complete network must be monitored every 2 weeks. In this setting, the usual objective in arc routing of minimizing the total travel distance is irrelevant. The vehicles are equipped with global positioning systems (GPS) locating devices to monitor events and trace routes. Since most planned route are not completed because of events on the network, there is a need to continuously re-plan and re-schedule routes. We developed a methodology to achieve this task by gathering data from the GPS trace, matching it to the planned routes within a geographic information systems (GIS) and then use mathematical algorithms to propose a new schedule with new routes. The interurban road network studied consists in a hierarchy of three classes of roads that have different monitoring standards. We tested three different methods using different objectives depending on the operators’ needs. Results show that the method that implies rescheduling based on assignment and reconstruction of routes with an arc-adding method gives the best coverage for each class of road.