Difference between pages "D32 Model Animation" and "Parallel Composition using Event-B"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Daniel
 
imported>Mathieu
 
Line 1: Line 1:
−
= Model Animation =
+
[[User:Renato]] at [[Southampton]] is in charge of the [[Parallel Composition using Event-B]].
  
−
== Overview ==
+
Composition is the process by which it is possible to combine different sub-systems into a larger system. Known and studied in several areas, this has the advantage of reusability and combination of systems especially when it comes to distributed systems. While applying composition, properties must be maintained and proofs obligations need to be discharged in order for the final result to be considered valid. Our goal is to add this feature to the Rodin Platform (using Event-B notation) and study the concerns, properties, conditions, proof obligations, advantages and disadvantages when create/analysing system specifications. Since the composition maintains the monotonicity property of the systems, the sub-systems can be refined independently on a further stage, preserving composition properties.
−
=== Siemens Application===
 
−
The most important additions of the last 12 months are:
 
−
* Application of ProB in three active deployments, namely the upgrading of the Paris Metro Line 1 for driverless trains, line 4 of the S\~{a}o Paulo metro and line 9 of the Barcelona metro. We also briefly report on experiments on the models of the CDGVAL shuttle. The paper <ref name="fm2009">Leuschel et al. FM'2009</ref> only contained the initial San Juan case study, which was used to evaluate the potential of our approach.
 
−
* In this article we describe the previous method adopted by Siemens in much more detail,  as well as explaining the performance issues with Atelier B.
 
−
* Comparisons and empirical evaluations with other potential approaches and alternate tools (Brama, AnimB, BZ-TT and TLC) have been conducted.
 
−
* We provide more details about the ongoing validation process of ProB, which is required by Siemens for it to use ProB to replace the existing method.
 
  
−
The validation also lead to the discovery of errors in the English version of the Atelier B reference manual.
+
[[Image:share_event_machine.jpeg]]
−
 
−
Also, since  <ref name="fm2009"/>, ProB itself has been further improved inspired by the application, resulting in new optimisations in the kernel (see below).
 
  
−
More details:
+
[[Image:share_event_mach_comp1.jpeg]]
−
* <ref>Leuschel et al. FAC, special issue of FM'2009</ref>
+
[[Image:share_event_machine_comp2.jpg]]
−
* <ref>Leuschel et al. Draft of Validation Report</ref>
 
  
−
=== Multi-level Animation ===
+
A machine '''''S''''' with events '''''e1, e2, e3''''' and '''''e4''''' and variables '''''v1, v2''''' and '''''v3''''' can be decomposed using event (de)-composition of event ''e2'' (as can be seen above). This would result in the machine '''''S1''''' and '''''S2''''' that have a partial part of the event ''e2'': machine ''S1'' has the part related to the variable ''v1'' (''e2''') and machine ''S2'' has the part related to the machine ''v2'' (''e2''<nowiki>''</nowiki>). Also some other events are separated (''e1'' and ''v1'' only exist on machine ''S1'' and events ''e3'' and ''e4'' with variable ''v3'' only exist on the machine ''S2'') as can be seen above.
−
(ABZ'2010 & SCP journal paper)
 
  
−
=== Evaluation of the ProB Constraint Solver ===
+
The composition is based on proposals for parallel composition in Event-B in the following paper: [http://deploy-eprints.ecs.soton.ac.uk/51/].
−
Various industrial applications have shown the need for improved constraint-solving capabilities (see CBC Deadlock, Test-Case Generation). In order to evaluate ProB, and detect areas for improvement, we have studied to what extent classical constraint satisfaction problems can be  conveniently expressed as B predicates, and then solved by ProB. In particular, we have studied problems such as the n-Queens problem, graph colouring, graph isomorphism detection, time tabling, Sudoku, Hanoi, magic squares, Alphametic puzzles, and several more. We have then compared the performance with respect to other tools, such as the model checker TLC  for TLA+, AnimB for Event-B,  and Alloy.
 
−
 
 
−
The experiments show that some constraint satisfaction problems can be expressed very conveniently in B and solved very effectively with ProB. For example, TLC takes 8747 seconds (2 hours 25 minuts) to solve the 9-queens problem expressed as a logical predicate; Alloy 4.1.10 with minisat takes 0.406 seconds, ProB 1.3.3 takes 0.01 seconds. For 32 queens, ProB 1.3.3 takes 0.28 seconds, while Alloy 4.1.10 with minisat takes over 4 minutes (TLC was only able to solve the n-queens problem up until n=9, or n=14 when reformulating the problem as a model checking problem rather than a constraint-solving problem). In another small experiment, we checked whether two graphs with 9 nodes of out-degree exactly one are isomorphic by checking for the existence of a permutation which preserved the graph structure. TLC finds a permutation after 2 hours 6 minutes and 28 seconds; ProB 1.3.3 takes 0.01 seconds to find the same solution, while Alloy takes 0.11 seconds with SAT4J and 0.05 seconds with minisat.
 
−
For some other examples (in particular time-tabling) involving operators such as the relational image, the performance of ProB is still sub-optimal with respect to, e.g., Alloy; we plan to overcome this shortcoming in the future. Our long term goal is that B can not only be used to as a formal method for developing safety critical software, but also as a high-level constraint  programming language.
 
  
−
=== Constraint-Based Deadlock Checking ===
+
A release of the composition plugin for Rodin 0.8.2 is available (email me:ras07r@ecs.soton.ac.uk).  
−
Ensuring the absence of deadlocks is important for certain applications, in particular for Bosch's Adaptive Cruise Control. We are tackling the problem of finding deadlocks via constraint solving rather than by model checking. Indeed, model checking is problematic when the out-degree is very large. In particular, quite often there can be a practically infinite number of ways to instantiate the constants of a B model. In this case, model checking will only find deadlocks for the given constants
 
−
chosen.
 
  
−
Idea: solve constraints of axioms, invariant together with a constraint specifying a deadlock.
+
A release for Rodin 0.9.2.1 is now available from the Rodin Main Update Site.
  
−
Required Developments:
+
1. To create a new composition file (bcp file), go to Toolbar (on top), New>>Other... Event-B>>Composition Machine. Then select the project (if not selected already) and filename (by default is cm.bcp).
−
* implementation of the algorithm, with semantic relevance filtering (to be able to restrict the deadlock search to certain scenarios: in Bosch's case due to the flow plugin, one wants to restrict deadlock checking e.g. to states with the variable Counter set to 10).
 
−
* Improvements to ProB's constraint solving engine: (reification of constraints, more precise information propagation for membership constraints, performance improvments in the typchecker and other parts of the kernel)
 
  
−
Success: Model 1 and Model 2: CrCtrl_Comb2Final;
+
2. Bcp files are visible on Event-B perspective(from Rodin 0.9). For Rodin 0.8.2, go to Resource or Java perspective to edit the file.
−
relevance of Counter=10 due to flow
 
  
−
Deadlock Freedom PO: 34 pages of ASCII, could not be loaded in Rodin "Java Heap Space Error". Counter examples found for 8 versions in 1-18 seconds.
+
3. After editing the properties of the bcp file, you can generate a new bum file (machine), by using the green button on the toolbar (CM - symbol of machine) or by right clicling on the bcp file and choose the option :'Create Composed Machine'. You will have to introduce a name for the new machine and after that is just press 'OK'.
  
−
=== BMotionStudio for Industrial Models ===
 
  
−
Previously, we presented BMotion Studio, a visual editor which enables the developer of a formal model to set-up easily a domain specific visualization for discussing it with the domain expert. However, BMotion Studio had not yet reached the status of an Industrial strength tool due to the lack of important features known from modern editors.
+
'''
 +
==User Manual==
 +
'''
  
−
In this work we present the improvements to BMotion Studio mainly aimed at upgrading it to an industrial strength tool and to show that we can apply the benefits of BMotion Studio for visualizing more complex models which are on the level of industrial applications. In order to reach this level the contribution of this work consists of three parts:
+
The Shared Event Composition Plugin is divided in 6 sections:
  
−
* We added a lot of new features to the graphical editor known from modern editors like: Copy-paste support, undo-redo support, rulers, guides and error reporting. One step towards was the redesign of the graphical editor with GEF.
+
* '''Refines''' : allows to define an abstract machine of this composed machine. It is a valid machine that exists on the project.
−
* Since extensibility is a very important design principle for reaching the level of an industrial strength tool we pointed up the extensibility options of BMotion Studio.
+
* '''Includes''': to compose a model, it is necessary to define which sub-systems(machines) interact. The machines must be abstract (not refinements of other machines) and have to be valid. It is also possible to choose if the included machine invariant should be visible to the composed machine or not (for proof optimization).
−
* We introduced the visualization for two models which are on the level of industrial applications in order to demonstrate that we can apply the benefits of BMotion Studio for visualizing more complex models. The first model is a mechanical press controller and the second model is a train system which manages the crossing of trains in a certain track network.
+
* '''Sees''': allows to add contexts to the composed machine. The contexts seen by the ''included machines'' are visible to the composed machine. So it is only allowed to see contexts that are not already seen by the composed machine.
 +
* '''Invariants''': allows the inclusion of invariant clauses to the composed file. The inclusion of more invariants (from the included machines) depends on the user’s choice on ''Includes''. The defined invariants on the composed machine are “joint” properties between the included machines (gluing invariants), so variables and contexts from all the included machines become part of the composed machine scope.
 +
*'''Variant''': since the composed machine can be a refinement of an abstract model, there is the possibility of introducing new events. In order to avoid divergence, variants are necessary for the new events.
 +
*'''Composes Events''': the interaction between systems only happens when the composed events are synchronised and ready to be executed. The systems can interact through shared parameters. It is possible to define the following properties for composes events:
 +
** Name: name of the composes event
 +
** Extended/Not Extended: in the composes machine refines an abstract machine and if there are events with the same name, the concrete event can extend the abstract one (from Rodin 0.9).
 +
** Convergence: event can be chosen from ''Ordinary'', ''Convergence'' or ''Anticipated''.
  
−
=== Various other improvements ===
 
  
−
mainly inspired by Siemens and Bosch Applications
+
Still under '''Composes Events''', there are more properties that characterise a composed event:
 +
* '''Refines''' : possibility to choose if the composes event it is a refinement of an abstract event
 +
* '''Combines Event''': selection of the events that shall be composed. First the machine (out from the included machine list) is chosen and after, which event is supposed to be combined. It is possible to have only one combined event.
  
−
Improved AVL algorithms, more operators
 
  
−
record support, treatment of infinite sets,
+
The '''Combination of Events''' can be expressed as:
 +
* The parameters are listed in one single (composed) event. Parameters (from different events) with the same name will be merged (becoming only one parameter). This correspond to the shared event composition with message passing, where a parameter is passed from one event to other.
 +
* The guards from the different combined events are merged using conjuction. So this composed event will be available if all the guards are true.
 +
* the actions are also merged and executed in parallel.
  
−
== Motivations ==
+
Like mention above,a machine can be generated containing all the properties defined on the composed machine file. The generation of the new machine can be executed by using the green button on the toolbar (CM - symbol of machine) or by right clicling on the bcp file and choosing the option :''Create Composed Machine''. A name for the new machine have to be introduced (a name is suggested by default ) and by clicking 'OK' or 'Override', a new machine file is generated.
  
−
The above works were motivated mainly to support the following three industrial deployments:
 
−
* Siemens: enable Siemens to use ProB in their SIL4 development chain, replacing Atelier B for data validation.
 
−
* Bosch: provide animation and constraint-based deadlock detection for the Adaptive Cruise Control
 
−
* SAP: provide a way to generate test cases using constraint-based animation
 
  
−
== Available Documentation ==
 
  
−
=== References ===
 
−
<references/>
 
  
−
== Planning ==
+
[[Category:Parallel composition plugin]]
−
 
+
[[Category:User documentation]]
−
* Finish Validation Report
 
−
* Write up Constraint-Based Deadlock Checking and integrate fully into Rodin Platform
 
−
* Support mathematical extensions in ProB
 
−
* Further improvements in the constraint-solving kernel of ProB; in particular for relations and operators. A Kodkod translator is being developed.
 

Revision as of 08:59, 4 March 2009

User:Renato at Southampton is in charge of the Parallel Composition using Event-B.

Composition is the process by which it is possible to combine different sub-systems into a larger system. Known and studied in several areas, this has the advantage of reusability and combination of systems especially when it comes to distributed systems. While applying composition, properties must be maintained and proofs obligations need to be discharged in order for the final result to be considered valid. Our goal is to add this feature to the Rodin Platform (using Event-B notation) and study the concerns, properties, conditions, proof obligations, advantages and disadvantages when create/analysing system specifications. Since the composition maintains the monotonicity property of the systems, the sub-systems can be refined independently on a further stage, preserving composition properties.

Share event machine.jpeg

Share event mach comp1.jpeg Share event machine comp2.jpg

A machine S with events e1, e2, e3 and e4 and variables v1, v2 and v3 can be decomposed using event (de)-composition of event e2 (as can be seen above). This would result in the machine S1 and S2 that have a partial part of the event e2: machine S1 has the part related to the variable v1 (e2') and machine S2 has the part related to the machine v2 (e2''). Also some other events are separated (e1 and v1 only exist on machine S1 and events e3 and e4 with variable v3 only exist on the machine S2) as can be seen above.

The composition is based on proposals for parallel composition in Event-B in the following paper: [1].

A release of the composition plugin for Rodin 0.8.2 is available (email me:ras07r@ecs.soton.ac.uk).

A release for Rodin 0.9.2.1 is now available from the Rodin Main Update Site.

1. To create a new composition file (bcp file), go to Toolbar (on top), New>>Other... Event-B>>Composition Machine. Then select the project (if not selected already) and filename (by default is cm.bcp).

2. Bcp files are visible on Event-B perspective(from Rodin 0.9). For Rodin 0.8.2, go to Resource or Java perspective to edit the file.

3. After editing the properties of the bcp file, you can generate a new bum file (machine), by using the green button on the toolbar (CM - symbol of machine) or by right clicling on the bcp file and choose the option :'Create Composed Machine'. You will have to introduce a name for the new machine and after that is just press 'OK'.


User Manual

The Shared Event Composition Plugin is divided in 6 sections:

  • Refines : allows to define an abstract machine of this composed machine. It is a valid machine that exists on the project.
  • Includes: to compose a model, it is necessary to define which sub-systems(machines) interact. The machines must be abstract (not refinements of other machines) and have to be valid. It is also possible to choose if the included machine invariant should be visible to the composed machine or not (for proof optimization).
  • Sees: allows to add contexts to the composed machine. The contexts seen by the included machines are visible to the composed machine. So it is only allowed to see contexts that are not already seen by the composed machine.
  • Invariants: allows the inclusion of invariant clauses to the composed file. The inclusion of more invariants (from the included machines) depends on the user’s choice on Includes. The defined invariants on the composed machine are “joint” properties between the included machines (gluing invariants), so variables and contexts from all the included machines become part of the composed machine scope.
  • Variant: since the composed machine can be a refinement of an abstract model, there is the possibility of introducing new events. In order to avoid divergence, variants are necessary for the new events.
  • Composes Events: the interaction between systems only happens when the composed events are synchronised and ready to be executed. The systems can interact through shared parameters. It is possible to define the following properties for composes events:
    • Name: name of the composes event
    • Extended/Not Extended: in the composes machine refines an abstract machine and if there are events with the same name, the concrete event can extend the abstract one (from Rodin 0.9).
    • Convergence: event can be chosen from Ordinary, Convergence or Anticipated.


Still under Composes Events, there are more properties that characterise a composed event:

  • Refines : possibility to choose if the composes event it is a refinement of an abstract event
  • Combines Event: selection of the events that shall be composed. First the machine (out from the included machine list) is chosen and after, which event is supposed to be combined. It is possible to have only one combined event.


The Combination of Events can be expressed as:

  • The parameters are listed in one single (composed) event. Parameters (from different events) with the same name will be merged (becoming only one parameter). This correspond to the shared event composition with message passing, where a parameter is passed from one event to other.
  • The guards from the different combined events are merged using conjuction. So this composed event will be available if all the guards are true.
  • the actions are also merged and executed in parallel.

Like mention above,a machine can be generated containing all the properties defined on the composed machine file. The generation of the new machine can be executed by using the green button on the toolbar (CM - symbol of machine) or by right clicling on the bcp file and choosing the option :Create Composed Machine. A name for the new machine have to be introduced (a name is suggested by default ) and by clicking 'OK' or 'Override', a new machine file is generated.

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