Formalising the Hybrid ERTMS Level 3 specification in iUML-B and Event-B

We demonstrate refinement-based formal development of the hybrid, ‘fixed virtual block’ approach to train movement control for the emerging European Rail Traffic Management System (ERTMS) level 3. Our approach uses iUML-B diagrams as a front end to the Event-B modelling language. We use abstraction to verify the principle of movement authority before gradually developing the details of the Virtual Block Detector component in subsequent refinements, thus verifying that it preserves the safety properties. We animate the refined models to demonstrate their validity using the scenarios from the Hybrid ERTMS Level 3 (HLIII) specification. We reflect on our team-based approach to finding useful modelling abstractions and demonstrate a systematic modelling method based on the state and class diagrams of iUML-B. The component and control flow architectures of the application, its environment and interacting systems emerge through the layered refinement process. The runtime semantics of the specification’s state-machine behaviour are modelled in the final refinements. We discuss how the model could be used to generate an implementation using code generation tools and techniques.

     

Comparison of formal specification methods and object-oriented paradigms

Object orientation and formal methods are widely regarded as two fields with significant potential for new software engineering techniques. This paper discusses the relations between these two approaches. We present various specification techniques which incorporate object-oriented paradigms, discuss their place in software development process, and analyse possible benefits from their applications.     

Comparison of EEG signal decomposition methods in classification of motor-imagery BCI

A brain–computer interface (BCI) provides a link between the human brain and a computer. The task of discriminating four classes (left and right hands and feet) of motor imagery movements of a simple limb-based BCI is still challenging because most imaginary movements in the motor cortex have close spatial representations. We aimed to classify binary limb movements, rather than the direction of movement within one limb. We also investigated joint time-frequency methods to improve classification accuracies. Neither of these, to our knowledge, has been investigated previously in BCI. We recorded EEG data from eleven participants, and demonstrated the classification of four classes of simple-limb motor imagery with an accuracy of 91.46% using intrinsic time-scale decomposition and 88.99% using empirical mode decomposition. In binary classifications, we achieved average accuracies of 89.90% when classifying imaginary movements of left hand versus right hand, 93.1% for left hand versus right foot, 94.00% for left hand versus left foot, 83.82% for left foot versus right foot, 97.62% for right hand versus left foot, and 95.11% for right hand versus right foot. The results show that the binary classification performance is slightly better than that of four-class classification. Our results also show that there is no significant difference in terms of spatial distribution between left and right foot motor imagery movements. There is also no difference in classification performances involving left or right foot movement. This work demonstrates that binary and four-class movements of the left and right feet and hands can be classified using recorded EEG signals of the motor cortex, and an intrinsic time-scale decomposition (ITD) feature extraction method can be used for real time brain computer interface.

     

Developing topology discovery in Event-B

We present a formal development in Event-B of a distributed topology discovery algorithm. Distributed topology discovery is at the core of several routing algorithms and is the problem of each node in a network discovering and maintaining information on the network topology. One of the key challenges in developing this algorithm is specifying the problem itself. We provide a specification that includes both safety properties, formalizing invariants that should hold in all system states, and liveness properties that characterize when the system reaches stable states. We prove these properties by appropriately combining proofs of invariants, event refinement, event convergence, and deadlock freedom. The combination of these features is novel and should be useful for formalizing and developing other kinds of semi-reactive systems, which are systems that react to, but do not modify, their environment. Our entire development has been formalized and machine checked using the Rodin tool.     

The specification and verified decomposition of system requirementsusing CSP

A formal method for decomposing the critical requirements of a system into requirements of its component processes and a minimal, possibly empty, set of synchronization requirements is described. The trace model of Hoare's communicating sequential processes (CSP) is the basis for the formal method. The method is applied to an abstract voice transmitter and describes the role that the EHDM verification system plays in the transmitter's decomposition is described. In combination with other verification techniques, it is expected that this method will promote the development of more trustworthy systems     

Refinement-based Validation of Event-B Specifications

The validation of formal specifications is a challenging task. It is one of the factors that impede the penetration of formal methods into the common practices of software development. This paper discusses the issue of validating formal models by executing them in the context of Event-B. The most important problem lies in the non-determinism which often prevents purely automatic tools to execute models. In this paper, we first present and discuss the techniques we have created to allow the execution of models at all levels of abstraction. These techniques rely on users to overcome the barriers resulting from non-deterministic features by either modifying the model or providing ad hoc implementations. Then, we present our main contribution, the formal definition of the notion of fidelity, that guarantees that all the observable behaviors of the executable models are indeed specified by the original (non-deterministic) models. The notion of fidelity can be expressed in terms of proof obligations.     

A decomposition of a formal specification: an improvedconstraint-oriented method

In this paper, the authors propose a decomposition method for a formal specification that divides the specification into two subspecifications composed by a parallel operator. To make these specification behaviors equivalent before and after decomposition, the method automatically synthesizes an additional control specification, which contains the synchronization information of the decomposed subspecifications. The authors prove that a parallel composition of the decomposed subspecifications synchronized with the control specification is strongly equivalent with the original (monolithic) specification. The authors also write formal specifications of the OSI application layer's association-control service and decompose it using their method as an example of decomposition of a practical specification. Their decomposition method can be applied to top-down system development based on stepwise refinement     

Application of decomposition methods in optimization

The problem of optimization of the composition of a production association of diverse enterprises is considered. The participating enterprises in the association model can be represented by relations of the input-output balance. Decomposition methods are used to construct models, describing the operation of such a system in the market environment for various methods of its regulation and to find conditions of asymptotic stability for the equilibrium. It is shown that this equilibrium coincides with the optimal solution to the global problem of the association, depending on the properties of the association balance matrix, the equilibrium can be inflationary rather than economical, when the production volume and income diminish to zero for rather high prices.     

Experiments in program verification using Event-B

The Event-B method can be used to model all sorts of discrete event systems, among them sequential programs. In this article we describe our experiences with using Event-B by way of two examples. We present a simple model of a factorial program, explaining the method, and a more intricate model of the Quicksort algorithm, providing some insights into strengths and weaknesses of Event-B. The two models are interspersed with our observations and some suggestions of how, we believe, Event-B could evolve. This evaluation of Event-B is intended to serve for determining directions for the evolution of Event-B and judging progress. It is our hope that the observations and suggestions can also be put to use for similar modelling formalisms, such as Z, ASM or VDM.     

On methods for interface specification and design

In this paper we analyse a subsystem, MINICON, of the UNICON interface to the UNIX operating system using two well-known formal methods, Reisner's Formal Grammar and Moran's Command Language Grammar. The contribution each technique is able to make towards a complete specification of interface systems is then identified and discussed.     

The behavioural semantics of Event-B refinement

Event-B provides a flexible framework for stepwise system development via refinement. The framework supports steps for (a) refining events (one-by-one), (b) splitting events (one-by-many), and (c) introducing new events. In each of the steps events can be indicated as convergent (to be made internal) or anticipated (treatment deferred to a later refinement step). All such steps are accompanied with precise proof obligations. However, no behavioural semantics has been provided to validate the proof obligations, and no formal justification has previously been given for the application of these rules in a refinement chain. Behavioural semantics expresses a clear relationship between the first and last machines in a refinement chain. The framework we present provides a coherent justification for Abrial’s approach to refinement in Event-B, and its generalisation to interface extension: adding events to the interface. In this paper, we give a behavioural semantics for Event-B refinement, with a treatment for the first time of splitting events and of anticipated events, adding to the well-understood treatment of convergent events. To this end, we define a CSP semantics for Event-B and show how the different forms of Event-B refinement can be captured as CSP refinement. It turns out that the appropriate CSP refinement relationship is influenced by the particular Event-B development strategy taken. We present two such strategies, one allowing, the other disallowing interface extensions.     

On the purpose of Event-B proof obligations

Event-B is a formal modelling method which is claimed to be suitable for diverse modelling domains, such as reactive systems and sequential program development. This claim hinges on the fact that any particular model has an appropriate semantics. In Event-B, this semantics is provided implicitly by proof obligations associated with a model. There is no fixed semantics though. In this article we argue that this approach is beneficial to modelling because we can use similar proof obligations across a variety of modelling domains. By way of two examples we show how similar proof obligations are linked to different semantics. A small set of proof obligations is thus suitable for a whole range of modelling problems in diverse modelling domains.     

The landing gear system in multi-machine Hybrid Event-B

A system development case study problem based on a set of aircraft landing gear is examined in Hybrid Event-B (an extension of Event-B that includes provision for continuously varying behaviour as well as the usual discrete changes of state). Although tool support for Hybrid Event-B is currently lacking, the complexity of the case study provides a valuable challenge for the expressivity and modelling capabilities of the Hybrid Event-B formalism. The size of the case study, and in particular, the number of overtly independent subcomponents that the problem domain contains, both significantly exercise the multi-machine and coordination capabilities of the modelling formalism. These aspects of the case study, vital in the development of realistic cyberphysical systems in general, have contributed significant improvements in the theoretical formulation of multi-machine Hybrid Event-B itself.

     

Non-overlapping domain decomposition methods in structural mechanics

Summary The modern design of industrial structures leads to very complex simulations characterized by nonlinearities, high heterogeneities, tortuous geometries... Whatever the modelization may be, such an analysis leads to the solution to a family of large ill-conditioned linear systems. In this paper we study strategies to efficiently solve to linear system based on non-overlapping domain decomposition methods. We present a review of most employed approaches and their strong connection. We outline their mechanical interpretations as well as the practical issues when willing to implement and use them. Numerical properties are illustrated by various assessments from academic to industrial problems. An hybrid approach, mainly designed for multifield problems, is also introduced as it provides a general framework of such approaches.     

Parallel efficiency of domain decomposition methods

Data communication among processors is a key problem to increase performance of parallel algorithms for multiprocessors. In this paper, we investigate different types of domain decomposition methods on the distributed memory multiprocessor and give the estimates of their speedup and efficiency based on the computational complexity and the communication overheads.     

A framework for evaluating specification methods for reactivesystems-experience report

Numerous formal specification methods for reactive systems have been proposed in the literature. Because the significant differences between the methods are hard to determine, choosing the best method for a particular application can be difficult. We have applied several different methods, including Modechart, VFSM, ESTEREL, Basic LOTOS, Z, SDL, and C, to an application problem encountered in the design of software for AT&T's 5ESS telephone switching system. We have developed a set of criteria for evaluating and comparing the different specification methods. We argue that the evaluation of a method must take into account not only academic concerns, but also the maturity of the method, its compatibility with the existing software development process and system execution environment, and its suitability for the chosen application domain     

An incremental development of the Mondex system in Event-B

A development of the Mondex system was undertaken using Event-B and its associated proof tools. An incremental approach was used whereby the refinement between the abstract specification of the system and its detailed design was verified through a series of refinements. The consequence of this incremental approach was that we achieved a very high degree of automatic proof. The essential features of our development are outlined. We also present some modelling and proof guidelines that we found helped us gain a deep understanding of the system and achieve the high degree of automatic proof. J. C. P. Woodcock