Difference between pages "D45 Prover Enhancement" and "Event-B Examples"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Tommy
 
imported>WikiSysop
 
Line 1: Line 1:
−
= Overview =
+
{{TOCright}}
−
* Two tasks concerned the prover performance from the core platform: the addition of rewriting and inference rules, and the addition of a mechanism to allow the customization and the parametrization or combination of tactics. While the addition of rewriting and inference rules has always been a regular task to enhance the Rodin integrated prover during DEPLOY lifetime, a new way to manage tactics has been implemented. In fact, the user is now able to define various types of tactics called 'profiles' which could be customized and parameterized tactics to discharge some specific proof obligations.
+
This page is for listing available example Event-B/Rodin projects.
−
* {{TODO}} An overview of the contribution about the ProB Disprover (Daniel Plagge, Jens Bendiposto)
 
−
* The SMT Solvers plug-in allowing to use the SMT solvers within Rodin is an effective alternative to the Atelier-B provers, particularly when reasoning on linear arithmetic. {{TODO}} (Laurent Voisin, Yoann Guyot)
 
  
−
= Motivations =
 
−
== New rewriting and inference rules ==
 
−
In an Event-B development, more than 60% of the time is spent on proofs. It has been a continuous aim to increase the number of automatically discharged proof obligations (POs) by improving the capabilities of the integrated sequent prover through the addition of rewriting and inference rules. These rules were provided through tactics, or existing or newly created. These tactics were automatic, or manual, or sometimes both. Providing new proving rules, even if it sometimes does not increase directly the number of automatically discharged POs aims to help the user to interactively discharge them and spare his time.
 
  
−
== Advanced Preferences for Auto-tactics ==
+
== Year 2009 ==
−
{{TODO}} ''To be completed by Nicolas Beauger''
 
−
Sometimes, the automatic proofs fail because the order of the applied tactics doesn't lead to the proof obligation discharge. Previously the ordering of tactics was lost at each change. Another issue is to have more than one possibility to combine the tactics. Indeed, various combinators called ''tacticals'' allow to combine tactics in a specific manner thus providing a sort of tactic arithmetic. The advanced preferences for auto-tactics solved this two issues.
 
  
−
== Isabelle Plug-in ==
+
=== [http://deploy-eprints.ecs.soton.ac.uk/107/ Real-time controller for a water tank]===  
−
{{TODO}} ''To be completed by Matthias Schmaltz''
+
By Michael Butler.
−
== ProB Disprover ==
 
−
{{TODO}} ''Daniel Plagge, Jens Bendiposto''
 
−
== SMT Solver Integration ==
 
−
{{TODO}} ''Laurent Voisin'' & ''Yoann Guyot''
 
  
−
= Choices / Decisions =
+
The draft paper outlines an approach to treating continuous behaviour in Event-B by a discrete approximation.
−
== New rewriting and inference rules ==
+
An example of a water tank system is used to illustrate the proposed approach. The archive containts the
−
{{TODO}} ''To be completed by Laurent Voisin''
+
Event-B development for the water tank system.
−
== Advanced Preferences for Auto-tactics ==
 
−
{{TODO}} ''To be completed by Nicolas Beauger''
 
−
Since Rodin 2.1, tactic profiles have been added. They allow to define more than one ordered way to apply the basic tactics. Since Rodin 2.3, the user is able to combine and parametrize these profiles increasing even more the potential of such proving feature. The combinators allow for exemple to loop on a subset of tactics, including existing profiles, and the parameterisation allows for example to set a timeout on external provers such as AtelierB P1.
 
  
−
== Isabelle Plug-in ==
+
=== [http://deploy-eprints.ecs.soton.ac.uk/95/ UML-B Development of an ATM]===  
−
{{TODO}} ''To be completed by Matthias Schmaltz''
+
By Mar Yah Said, Michael Butler and Colin Snook.
−
== ProB Disprover ==
 
−
{{TODO}} ''Daniel Plagge, Jens Bendiposto''
 
−
== SMT Solver Integration ==
 
−
{{TODO}} ''Laurent Voisin'' & ''Yoann Guyot''
 
  
−
= Available Documentation =
+
This paper outlines support for refinement of classes and statemachines in UML-B and issustrates these
−
* {{TODO}} Links for New rewriting and inference rules
+
with an Automated Teller Machine (ATM) example.  The ATM development is contained in a Rodin
−
* {{TODO}} Links for Advanced Preferences for Auto-tactics
+
archive.  It consists of an abstract model focusing on bank account updates.  The ATM, pin cards and
−
* {{TODO}} Links for Isabelle Plug-in
+
messaging between ATMs and a bank server are introduced in successive refinements.
−
* {{TODO}} Links for ProB Disprover
 
−
* {{TODO}} Links for SMT Solver Integration
 
  
−
= Status =
+
=== [http://deploy-eprints.ecs.soton.ac.uk/84/ MIDAS: A Formally Constructed Virtual Machine]===  
−
== New rewriting and inference rules ==
+
By [[Steve]].
−
{{TODO}} ''To be completed by Laurent Voisin''
 
−
== Advanced Preferences for Auto-tactics ==
 
−
{{TODO}} ''To be completed by Nicolas Beauger''
 
−
== Isabelle Plug-in ==
 
−
{{TODO}} ''To be completed by Matthias Schmaltz''
 
−
== ProB Disprover ==
 
−
{{TODO}} ''Daniel Plagge, Jens Bendiposto''
 
−
== SMT Solver Integration ==
 
−
{{TODO}} ''Laurent Voisin'' & ''Yoann Guyot''
 
  
−
[[Category:D45 Deliverable]]
+
MIDAS (Microprocessor Instruction and Data Abstraction System) is a specification of an Instruction Set Architecture (ISA). It is refined to a usable Virtual Machine (VM) capable of executing binary images compiled from the C language. It was developed to demonstrate a methodology for formal construction of various ISAs in Event-B via a generic model. There are two variants: a stack-based machine and a randomly accessible register array machine. The two variants employ the same instruction codes, the differences being limited to register file behavior.
 +
 
 +
The archive supplied at the Deploy repository contains: C-coded prototypes of the MIDAS VMs, an Event-B model refinement constructing the same VMs, the B2C Event-B to C auto-generation tool, C compiler/assembler/linkers for the VMs, an example C test suite, and execution environments for running compiled C on the machines.
 +
 
 +
=== [http://deploy-eprints.ecs.soton.ac.uk/82/ Development of a Network Topology Discovery Algorithm]===
 +
By ''Hoang, Thai Son and Basin, David and Kuruma, Hironobu and Abrial, Jean-Raymond''.
 +
 
 +
This paper and this Rodin development is another version of the [[#Link State Routing Development|Link State Routing Development]] presented in 2008.
 +
 
 +
== Year 2008 ==
 +
=== [http://deploy-eprints.ecs.soton.ac.uk/31/ Link State Routing Development]===
 +
By ''Hoang, Thai Son and Basin, David and Kuruma, Hironobu and Abrial, Jean-Raymond''.
 +
 
 +
We present a formal development in Event-B of a distributed topology discovery algorithm. Distributed topology discovery is at the core 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 specify these by appropriately combining invariants, event refinement, and proofs of 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.
 +
 
 +
=== [http://deploy-eprints.ecs.soton.ac.uk/22/ Modelling and proof of a Tree-structured File System] ===
 +
By ''Damchoom, Kriangsak and Butler, Michael and Abrial, Jean-Raymond''.
 +
 
 +
We present a verified model of a tree-structured file system which was carried out using Event-B and the Rodin platform. The model is focused on basic functionalities affecting the tree structure including create, copy, delete and move. This work is aimed at constructing a clear and accurate model with all proof obligations discharged. While constructing the model of a file system, we begin with an abstract model of a file system and subsequently refine it by adding more details through refinement steps.  We have found that careful formulation of invariants and useful theorems that can be reused for discharging similar proof obligations make models simpler and easier to prove.
 +
 
 +
=== [http://deploy-eprints.ecs.soton.ac.uk/56/ Deliverable D8 D10.1 "Teaching Materials"] ===
 +
By ''Abrial, Jean-Raymond and Hoang, Thai Son and Schmalz, Matthias''.
 +
 
 +
==Year 2007==
 +
=== [http://deploy-eprints.ecs.soton.ac.uk/9/ Redevelopment of an Industrial Case Study Using Event-B and Rodin]===
 +
From ''Rezazadeh, Abdolbaghi and Butler, Michael and Evans, Neil''.
 +
 
 +
CDIS is a commercial air traffic information system that was developed using formal methods 15 years ago by Praxis, and it is still in operation today. This system is an example of an industrial scale system that has been developed using formal methods. In particular, the functional requirements of the system were specified using VVSL -- a variant of VDM. A subset of the original specification has been chosen to be reconstructed on the Rodin platform based on the new Event-B formalism. The goal of our reconstruction was to overcome three key difficulties of the original formalisation, namely the difficulty of comprehending the original specification, the lack of any mechanical proof of the consistency of the specification and the difficulty of dealing with distribution and atomicity refinement. In this paper we elucidate how a new formal notation and tool can help to overcome these difficulties.
 +
 
 +
[[Category:Examples]]

Revision as of 12:37, 18 June 2009

This page is for listing available example Event-B/Rodin projects.


Year 2009

Real-time controller for a water tank

By Michael Butler.

The draft paper outlines an approach to treating continuous behaviour in Event-B by a discrete approximation. An example of a water tank system is used to illustrate the proposed approach. The archive containts the Event-B development for the water tank system.

UML-B Development of an ATM

By Mar Yah Said, Michael Butler and Colin Snook.

This paper outlines support for refinement of classes and statemachines in UML-B and issustrates these with an Automated Teller Machine (ATM) example. The ATM development is contained in a Rodin archive. It consists of an abstract model focusing on bank account updates. The ATM, pin cards and messaging between ATMs and a bank server are introduced in successive refinements.

MIDAS: A Formally Constructed Virtual Machine

By Steve.

MIDAS (Microprocessor Instruction and Data Abstraction System) is a specification of an Instruction Set Architecture (ISA). It is refined to a usable Virtual Machine (VM) capable of executing binary images compiled from the C language. It was developed to demonstrate a methodology for formal construction of various ISAs in Event-B via a generic model. There are two variants: a stack-based machine and a randomly accessible register array machine. The two variants employ the same instruction codes, the differences being limited to register file behavior.

The archive supplied at the Deploy repository contains: C-coded prototypes of the MIDAS VMs, an Event-B model refinement constructing the same VMs, the B2C Event-B to C auto-generation tool, C compiler/assembler/linkers for the VMs, an example C test suite, and execution environments for running compiled C on the machines.

Development of a Network Topology Discovery Algorithm

By Hoang, Thai Son and Basin, David and Kuruma, Hironobu and Abrial, Jean-Raymond.

This paper and this Rodin development is another version of the Link State Routing Development presented in 2008.

Year 2008

Link State Routing Development

By Hoang, Thai Son and Basin, David and Kuruma, Hironobu and Abrial, Jean-Raymond.

We present a formal development in Event-B of a distributed topology discovery algorithm. Distributed topology discovery is at the core 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 specify these by appropriately combining invariants, event refinement, and proofs of 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.

Modelling and proof of a Tree-structured File System

By Damchoom, Kriangsak and Butler, Michael and Abrial, Jean-Raymond.

We present a verified model of a tree-structured file system which was carried out using Event-B and the Rodin platform. The model is focused on basic functionalities affecting the tree structure including create, copy, delete and move. This work is aimed at constructing a clear and accurate model with all proof obligations discharged. While constructing the model of a file system, we begin with an abstract model of a file system and subsequently refine it by adding more details through refinement steps. We have found that careful formulation of invariants and useful theorems that can be reused for discharging similar proof obligations make models simpler and easier to prove.

Deliverable D8 D10.1 "Teaching Materials"

By Abrial, Jean-Raymond and Hoang, Thai Son and Schmalz, Matthias.

Year 2007

Redevelopment of an Industrial Case Study Using Event-B and Rodin

From Rezazadeh, Abdolbaghi and Butler, Michael and Evans, Neil.

CDIS is a commercial air traffic information system that was developed using formal methods 15 years ago by Praxis, and it is still in operation today. This system is an example of an industrial scale system that has been developed using formal methods. In particular, the functional requirements of the system were specified using VVSL -- a variant of VDM. A subset of the original specification has been chosen to be reconstructed on the Rodin platform based on the new Event-B formalism. The goal of our reconstruction was to overcome three key difficulties of the original formalisation, namely the difficulty of comprehending the original specification, the lack of any mechanical proof of the consistency of the specification and the difficulty of dealing with distribution and atomicity refinement. In this paper we elucidate how a new formal notation and tool can help to overcome these difficulties.

Retrieved from ‘https://wiki.event-b.org/index.php?title=D45_Prover_Enhancement&oldid=4077’