Difference between pages "Tasking Event-B Tutorial" and "User:Nicolas/Collections/ADVANCE D3.4 Model Checking"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Andy
 
imported>Ladenberger
 
Line 1: Line 1:
For more information contact Andy Edmunds - University of Southampton - mailto:ae2@ecs.soton.ac.uk
+
== Overview ==
=== Tasking Event-B Tutorial Overview ===
 
  
<span style="color: RED">'''Caution''': This Page is under Construction - some parts are incomplete</span>
+
In this period we have worked on scalability of the tools, by improving ProB for theories, for the WP1 and WP2 case study demands, and by adding dedicated support for fairness properties.
 +
We have also provided a link to the TLC model checker for large state space of more concrete formal models.
 +
We have also added new features to the model checking core of ProB, in feedback from the other work packages.
  
This tutorial follows on from the abstract development described [http://wiki.event-b.org/index.php/Development_of_a_Heating_Controller_System here].
+
== Motivations / Decisions ==
  
This code generation tutorial extends the Heating Controller tutorial example, and makes use of example projects from the download site. The code generation stage produces implementable Ada code, and also an Event-B model. It is a model of the implementation, and contains flow control variables that model the flow of execution through the task body. The Ada code is produced from an intermediate model that is not visible to the user. The Common Language model (CLM), is generated from the Tasking Event-B by a translation tool. Ada (and other implementations) may be generated from the CLM. An overview of Tasking Event-B can be found [http://wiki.event-b.org/index.php/Tasking_Event-B_Overview here].
+
=== LTL Fairness ===
  
In the example so far, the Heating Controller has been refined to the point where we wish to add implementation constructs. The Event-B language is not expressive enough to fully describe the implementation. Tasking Event-B facilitates this final step to implementation, by extending Event-B with the necessary constructs. Event-B machines modelling tasks, shared objects and the environment are identified, and  extended with the appropriate implementation details.
+
Fairness is a notion where the search for counterexamples is restricted to paths that do not ignore infinitely the execution of a set of enabled actions imposed by the user as fair constraints. One possibility to set fairness constraints in ProB is to encode them in the LTL<sup>e</sup> formula intended to be checked. For example, for a given LTL<sup>e</sup> formula "f" a set of weak fairness conditions {e1,…,en} (where e1,...,en are some events) can be given as follows:
  
The example/tutorial projects are are available in the [http://deploy-eprints.ecs.soton.ac.uk/304/ e-prints archive], or on [https://codegenerationd.svn.sourceforge.net/svnroot/codegenerationd/Examples/Heating_ControllerTutorial_v0.2.0/ SVN].
+
(FG e(e1) => GF [e1]) & … & (FG e(en) => GF [en]) => f.
  
{| border="1"
+
In a similar way, strong fairness constraints can be imposed expressed by means of an LTLe formula:
|Heating_ControllerTutorial2_Completed
+
(GF e(e1) => GF [e1]) & … & (GF e(en) => GF [en]) => f.
|An example project with an environment simulation. The environment variables are monitored and controlled using subroutine calls. The project contains a complete Tasking Development with generated Event-B and Ada code.
 
|-
 
|Heating_ControllerTutorial2_Partial1
 
|A project with the final decomposition completed, ready to begin Tasking Event-B Development.
 
|-
 
|Heating_ControllerTutorial2_Partial2
 
|A partially completed tasking specification for the continuation of the tutorial.
 
|-
 
|TheoriesForCG
 
|Contains the mathematical language translations; encoded as rules in a theory plug-in rule-base.
 
|}
 
  
== Using the Tasking Extension ==
+
Checking fairness in this way is very often considered to be inefficient as usually the number of atoms (the possible valuations of the property) of the LTL property is exponential in the size of the formula <ref>O. Lichtenstein and A. Pnueli: ''Checking that Finite State Concurrent Programs Satisfy Their Linear Specification''. POPL '85, Proceedings of the 12th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, ACM, 1985</ref> <ref>D. Plagge and M. Leuschel: ''Seven at one stroke: LTL model checking for High-level Specifications in B, Z, CSP, and more''. STTT, 12(1): 9-21, Feb 2010</ref>.
The steps needed to generate code from an Event-B model, in this tutorial, are as follows,
 
* Step 1 - [[Tasking Event-B_Tutorial#Adding the Implementation Level Refinement|Adding the Implementation Level Refinement]]
 
* Step 2 - [[Tasking Event-B_Tutorial#Pre-processing|Pre-processing]]
 
* Step 3 - [[Tasking Event-B_Tutorial#Providing the Annotations for Implementations|Add Tasking annotations]].
 
* Step 4 - [[Tasking Event-B_Tutorial#Invoking the Translation|Invoke translators]].
 
=== Download and Copy the Theories ===
 
The translations of the Event-B mathematical language to the target language constructs are specified as rules in the theory plug-in. Two rule files are included for the example, and are available in the [https://codegenerationd.svn.sourceforge.net/svnroot/codegenerationd/Examples/Heating_ControllerTutorial_v0.2.0/ SVN]. The files can be downloaded and copied into an Event-B project called ''MathExtensions''. The theory must then be deployed. Right-Click on the theory file and select deploy to do this. The non-Event-B project, the original download may now be deleted.
 
  
=== Adding the Implementation Level Refinement ===
+
For this reason, the search algorithm of the LTL model checker in ProB has been extended in order to allow fairness to be checked efficiently. In addition, new operators have been added to the ProB’s LTL parser for setting fairness constraints to an LTL<sup>e</sup> property. The new operators are WF(-) and SF(-) and both accept as argument an operation. The fairness constraints must be given by means of implication: "fair => f", where "f" is the property to be checked and "fair" the fairness constraints.  
The final decomposition generates the machines that are required for code generation. However, it is not possible to edit the machines since they are machine generated, and therefore this is prohibited. In order to be able to modify the models we will refine the generated machines. This is where we begin with the ''Heating_ControllerTutorial2_Partial1'' project. To refine the machines we can use the automatic refinement feature, but this presents us with two problems that are dealt with in the pre-processing step. It is also at this stage that any remaining non-deterministic constructs should be removed by replacing them with deterministic constructs.
 
  
TIP: Non-deterministic constructs cause strange characters to appear in the source code. If you see strange characters in the generated code, check for non-deterministic constructs in the implementation level machines.
+
In particular, "fair" can have one of the forms: "wfair", "sfair", "wfair & sfair", and "sfair & wfair", where "wfair" and "sfair" represent the imposed weak and strong fairness constraints, respectively.
  
Alter_Temperature_Sensor1 in Envir1Impl: action becomes ts1 := ts1 + 1
+
Basically, "wfair" and "sfair" are expressed by means of logical formulas having the following syntax:
Alter_Temperature_Sensor2 in Envir1Impl: action becomes ts1 := ts1 + 1
+
* Weak fair conditions ("wfair"):
Alter_Heater_Status in Envir1Impl: action becomes hss := FALSE
+
** `WF(a)`, where `a` is an operation
INITIALISATION in Heater_Monitor_TaskImpl: becomes shs := FALSE
+
** `&` and `or`: conjunction and disjunction
 +
* Strong fair conditions ("sfair"):
 +
** `SF(a)`, where `a` is an operation
 +
** `&` and `or`: conjunction and disjunction
  
We also need to add a typing flag to an invariant. We need to add it in only one place, and this is where an invariant is used type a variable, in the Heating Controller machine. The flag is used to guide the translator to the typing invariant. This is because there is more than one invariant involving that particular variable. They may also be added to guards where parameters are typed in guards, and the parameters are referred to in more than one guard.
+
More information on setting fairness to LTL formulas and the LTL Model Checker is available on the ProB User Manual website <ref name="LTL">ProB User Manual: LTL Model Checking,
 +
http://www.stups.uni-duesseldorf.de/ProB/index.php5/LTL_Model_Checking</ref>.
  
* Go to the ''Heater_Monitor_TaskImpl typing_shs'' invariant.
+
==== Use Case ====
* Add the typing flag, by right-clicking on the invariant and selecting typing from the menu.
 
  
=== Pre-processing ===
+
Consider an Event-B model formalising an algorithm for mutual exclusion with semaphores for two concurrent processes <math>P_1</math> and <math>P_2</math>. Each process has been simplified to perform three types of events: request (for entering in the critical section), enter (entering the critical section), and release (exiting the critical section). (For more information on the algorithm and the design of the model see <ref>C.Baier and J.-P. Katoen. “Principles of Model Checking”, The MIT Press, 2008, pages 43-45.</ref>).
 +
 +
Each of the actions of a process are represented by an respective event:
  
The pre-processing step should be a temporary, the solutions can be incorporated into the tool to automatically perform the changes that are required.  
+
[[File:MUTEX_Events_horizontal.png]]
  
* The Code Generator requires a flattened version of each machine; all of the Event-B elements should be available in the implementation level machine.  
+
Each process <math>P_i</math> has three possible states that are denoted by the constants <math>noncrit_{i}</math> (the state in which <math>P_i</math> performs noncritical actions), <math>wait_{i}</math> (the state in which <math>P_{i}</math> waits to enter the critical section), and <math>crit_{i}</math> (representing the state in which <math>P_{i}</math> is in the critical section). Both processes share the binary semaphore y where y=1 indicates that the semaphore is free and y=0 that the semaphore is currently processed by one of the processes.
* Composed machines are not currently able to be refined, so anything that requires synchronization of events requires some manual updates.
+
 +
There are several requirements that the mutual exclusion algorithm should satisfy. The most important one is the mutual exclusion property that says always at most one process is in its critical section. This can be simply expressed, for example, as an invariant of the respective Event-B model: not(p1 = crit1 & p2 = crit2). However, there are other properties that can be easily expressed by means of LTL formulas and automatically checked on the model. For example, the requirement each process will enter infinitely often its critical section can be specified by the LTL formula `GF {p1 = crit1} & GF {p2 = crit2}` or the starvation freedom property that states each waiting process will eventually enter its critical section:
  
===== 'Flattening' the Implementation Machines =====
+
G ({p1 = wait1} => F {p1 = crit1}) & G ({p2 = wait2} => F {p2=crit2})
 +
Running the LTL model checker of ProB will provide for the last two properties above a counterexample since the model permits that a process may perform infinitely often consecutively the events request, enter and release, and in this way to ignore the other process infinitely. An example trace that describes this behavior could be <math>\langle Req2,Req1,Enter1,Rel1,Req1,Enter1,\ldots\rangle</math>.
 +
 +
On the other hand, such behaviors can be considered as unrealistic computations for the later implementation of the algorithm. Therefore fairness constraints can be set in order to discard such behaviors. For example, checking the property process <math>P_1</math> will enter its critical section infinitely often (as LTL property: `GF {p1 = crit1}`) can be checked by restricting that the event  `Req1` will not be continuously ignored and that the event `Enter1` will not be ignored infinitely often. Both conditions on the property can be given by means of an LTL<sup>e</sup> formula on the right side of the implication as follows:
 +
 +
(FG e(Req1) => GF [Req1]) & (GF e(Enter1) => GF [Enter1]) => GF {p1 = crit1}
 +
For checking the formula the LTL model checker generates 13312 atoms and 7515 transitions and needs overall 509 ms to prove the property. On the other hand, using the extension of the LTL model checker for checking fairness (by entering the formula `WF(Req1) & SF(Enter1) => GF {p1=crit1}`), the model checker generates 32 atoms and 39 transitions (the atoms and transitions generated just for `GF {p1 = crit1}`) and an overall time of 50 ms.
 +
 +
For checking the requirement each process will enter infinitely often its critical section the LTL formula ` GF {p1 = crit1} & GF {p2 = crit2}` should be checked with the following fairness constraints:
  
The temporary solution for flattening:
+
(WF(Req1) & WF(Req2)) & (SF(Enter1) & SF(Enter2))
* Make events ''not extended''.
+
Encoding these fairness conditions as an LTL<sup>e</sup> formula will blow up exponentially the number of atoms and the transitions and thus make practically impossible to check the above property in a reasonable time.
* Copy missing invariants.
 
  
I found the Event-B Machine Editor's synthesis view useful for this. Invariants can be copy-pasted into the implementation machine from the abstraction. (A dummy invariant can be added and selected for pasting)
+
==== New LTL Patterns ====
 
+
===== Providing the correct Composed Machine =====
+
The ABZ landing gear case study <ref>F. Boniol, V. Wiels, “The Landing Gear System Case Study”, ABZ 2014</ref> was formalised in Event-B and validated with ProB. <ref>D. Hansen, L. Ladenberger, H. Wiegard, J. Bendisposto, M. Leuschel, “Validation of the ABZ Landing Gear System using ProB”, ABZ 2014: The Landing Gear Case Study, 2014, pages 66-79, Springer International Publisher.</ref>  In the course of the validation of the model new features have been developed in ProB for checking relative deadlock freedom and determinism.
 
+
The composed machine problem is sub-divided into two sub-problems. Firstly composed machines cannot be refined, and secondly when a machine is further decomposed there is no link between the first composed machine and the newly generated composed machine. So one or both of these problems may occur, depending on the number of decompositions.
+
Since it has turned out that the features were a key part of the validation of the model and the authors believe that they will be of use for other Event-B system developments, the LTL model checker has been extended to support these features as new patterns within LTL<sup>e</sup> formulas:
 
 
We must manually add the information to the composed machines to address these two problems.
 
 
 
The temporary solution for composed machines:
 
* Modify the lowest level decomposed machine, HCtrl_M1_cmp, to ''include'' the implementation level machines (task names ending in *Impl). To do this,
 
* open the composed machine editor. Open the INCLUDES edit feature.
 
* Select the second drop-down box and find the *Impl version of each machine.
 
* Save the composed machine.
 
* Now add missing synchronizations to the composed machine. Add the ''Envir1Impl'' to the includes of HCtrl_M1_cmp.
 
* Each composed event in the task, that synchronizes with the Environ machine, must have the remote event synchronization added manually. This can only be done by inspection of each composed event. We need to update Sense_Temperatures, Display_Current_Temperature, Actuate_OverHeat_Alram, Actuate_Heat_Source, Sense_Heater_Status, Actuate_NoHeat_Alarm, Sense_PressIncrease_Target_Temperature, Sense_PressDecrease_Target_Temperature, Display_Target_Temperature. One by one, expand the events in the composed events section of the composed machine editor; add a new event in the combines events section, select ''Envir1Impl'' and add the synchronizing event from the list-box to the right.
 
 
 
=== Adding Tasking Event-B ===
 
Each Machine should be completed as follows.
 
==== The Temp_Ctrl_TaskImpl Machine ====
 
Continuing with the tutorial project ''Heating_ControllerTutorial2_Partial2'', we need to make changes to the following machines. During the tutorial we will cut and paste from ''Heating_ControllerTutorial2_Completed'' model when, specifying the task bodies, to save typing.
 
 
 
*Add the ''Auto Task'' extension.
 
**Right-Click on the Machine node in the Rose tree-editor,
 
**and click on ''New Child Element/Auto Task Machine'' menu option.
 
 
 
''Auto Tasks'' are tasks that will be declared and defined in the ''Main'' procedure of the implementation. The effect of this is that the ''Auto Tasks'' are created when the program first loads, and then activated (made ready to run) before the ''Main'' procedure body runs.
 
 
 
*'''Edit the TaskBody'''.
 
**Open the properties editor for the task body.
 
**Copy and paste the task body from ''Heating_ControllerTutorial2_Completed/Temp_Ctrl_Task1Impl''
 
**Set the task type to ''Periodic'',  
 
**Set a period of 250 milliseconds.
 
**Click on the Set Task Body button.
 
 
 
The task body is parsed, and if successful will add the structure to the EMF tree. If parsing is not successful an error panel will display the source of the error.
 
  
We now look at the sensing event ''Sense_Temperatures'' event in ''Temp_Ctrl_TaskImpl''. In order to assist with the translation we add the following annotation:
+
* deadlock(e1,e2,...,ek), where e1,e2,...,ek with k>0 are events. Used to check relative deadlocks, more precisely to check if a set of events are disabled in a state.
 +
* deterministic(e1,e2,…,ek), where e1,e2,...,ek with k>0 are events. Used to check that maximum one of the events in the parentheses is enabled in a state. Note that if the atomic proposition is checked in a state where no one of the events e1,e2,...,ek is enabled, the test will succeed.
 +
* controller(e1,e2,…,ek) , where e1,e2,...,ek with k>0 are events. Used to check that exactly one of the events e1,e2,...,ek is enabled in a state.
  
*'''Add a Sensed Event Annotation'''.
+
=== Theory Support ===
** Right-click on the ''Sense_Temperatures'' Event node.
 
** Select ''New Child/Implementation'' from the menu.
 
** Go to the Implementation properties view and set the ''Implementation Type'' property to ''Sensing''.
 
 
 
We now look at the actuating event ''Display_Current_Temperatures'' event in ''Temp_Ctrl_TaskImpl''. In order to assist with the translation we add the following annotation:
 
 
 
*'''Add an Actuating Event Annotation'''.
 
** Right-click on the ''Display_Current_Temperatures'' Event node.
 
** Select ''New Child/Implementation'' from the menu.
 
** Go to the Implementation properties view and set the ''Implementation Type'' property to ''Actuating''.
 
 
 
==== The Shared Machine ====
 
 
 
The next step is to identify the ''Shared_ObjectImpl'' machine as a ''Shared Machine''.
 
* Right-click on the ''Shared_Object'' Machine node in the Rose tree-editor.
 
* Select ''New Child/Shared Machine'' from the menu.
 
 
 
==== The Environ Machine ====
 
In the prepared machine we identify the ''Envir1Impl'' as an ''Environ Machine'',
 
 
 
*Add the ''Environ Machine'' extension.
 
**Right-click on the Machine node in the Rose tree-editor.
 
**Select
 
 
 
 
 
 
 
''Envir1Impl'' models a task that simulates the environment, and can be used to generate simulation code. For deployment in a non-simulated environment the environ machine's generated code can be ignored; we provide details of non-simulated code using addressed variables later. As before, a screenshot is available [http://wiki.event-b.org/images/Envir1Impl_2.pdf here]. In the prepared Environment Machine we have already set task type to ''Periodic'' extension, and set a period of 100 milliseconds.
 
 
We will now complete the sequence that has been partially defined in the task body. The following specification models simulation of a temperature change; the temperature value is represented by a monitored variable in the environment. The generated code simulates the temperature change in the environment by changing the monitored value. 
 
  
*'''Model Temperature Change in the environment'''.
+
Theory Support was relevant for a variety of case studies, and is relevant for simulation, model checking and proving.
??????
+
We ensured that the Disprover also works with theories
 +
We have also improved the constraint propagation of the ProB kernel for records and freetypes, which are used to represent Event-B inductive datatypes.
 +
(As a side note, this feature is also being used by another EU project to use ProB for validating VDM specifications within the Ouverture tool).
 +
Finally, the treatment of recursive functions within the ProB kernel has been improved, also in light of dealing with recursive operators of Event-B Theories.
  
* Output to the screen during the simulation can be specified as follows:
+
=== Physical Units ===
??????
 
  
The generated code will print the text, and the value of the variable, to the screen.  
+
The physical units analysis has been further stabilised, several reported bugs have been fixed.
 +
Support for physical units has been extended to theories along with the general theory-related improvements of ProB mentioned in the previous paragraph.
 +
The plug-in was ported to Rodin 3, all bugfixes and changes could be back ported to Rodin 2 successfully.
  
The final step is to complete the ''ENSense_Temperatures'' event. The event is a sensing event, sensing is a kind of synchronisation, it synchronises with the ''TCSense_Temperatures'' event in the ''Temp_Ctrl_Task1'' tasking machine. We add formal parameters annotations corresponding to the actual parameters that we have already defined in the task.
+
Further extension to the unit analysis include:
 +
* Support for the analysis of units throughout refinement relations.
 +
* Support for abstract units like "length" that can later be concretised to standard SI units.
  
*'''Add a Sensed Event Annotation'''.
+
=== B to TLA+ ===
** Right-click on the ''Sense_Temperatures'' Event node.
 
** Select ''New Child/Implementation'' from the menu.
 
** Go to the Implementation properties view and set the ''Implementation Type'' property to ''Sensing''.
 
  
*'''Add an Actuating Event Annotation'''.
+
We are interested in validating the correctness of our translation from B to TLA+.
** Right-click on the ''Display_Current_Temperatures'' Event node.
+
Hence, we have conducted extensive tests to validate our approach.
** Select ''New Child/Implementation'' from the menu.
+
For example, we use a range of models encoding mathematical laws to stress test our translation.
** Go to the Implementation properties view and set the ''Implementation Type'' property to ''Actuating''.
+
These have proven to be very useful for detecting bugs in our translation and libraries.
 +
In addition, we have uncovered a bug in the model checker TLC.
 +
Moreover, we use a wide variety of benchmarks, checking that ProB and TLC produce the same result and generate the same number of states.  
  
=== A Summary of Steps ===
+
The current version of our translator covers almost all operators of a abstract B machine.
For a Tasking Machine definition:
+
Moreover, TLC can be used to validate liveness properties (LTL formulas) for B specifications under fairness conditions.
# Add the Tasking Machine type (Auto etc).
+
Our approach has been published at the ABZ’2014 conference in Toulouse.
# Set the task type (Periodic etc.).
+
A technical report is available <ref>http://stups.hhu.de/w/Special:Publication/HansenLeuschel_TLC4B_techreport</ref>.
# Set the task priority.
 
# Specify the task body.
 
# For sensing/actuating events, add the Event Type.
 
  
For a Shared Machine definition:
+
=== Performance Improvements ===
# Add the ''SharedMachine'' Machine type.
+
Various performance improvements have been made to the model checker and animator for Event-B models, both in terms of memory consumption and speed.
 +
For example, ProB now executes the models from WP1 and WP2 considerably faster than at the beginning of the project and than at the beginning of the last period of the project.
 +
Another example is an Event-B model of the Early parser by JR Abrial (a standard benchmark used for ProB regression testing) is now running an order of magnitude faster than before the beginning of the project.
  
For an Environ Machine definition:
+
== Available Documentation ==
# Make the type an Environ Machine type.
 
# Set the task type Periodic; a shorter period than the shortest task period is best for simulation.
 
# Set the task priority.
 
# Specify the task body, it will contain a simulation of changes in the environment.
 
# For each sensing/actuating event, add the Event Type.
 
  
== Invoking the Translators ==
+
'''ProB'''<br>
 +
The ProB Website<ref>ProB Website: http://www.stups.uni-duesseldorf.de/ProB/</ref> is the place where we collect information on the ProB toolset. There are several tutorials on ProB available in the User manual section<ref>ProB User Manual: http://www.stups.uni-duesseldorf.de/ProB/index.php5/User_Manual</ref>. We also supply documentation on extending ProB for developers<ref>ProB Developer Manual: http://www.stups.uni-duesseldorf.de/ProB/index.php5/Developer_Manual</ref>. Documentation and tutorials on the new LTL features available<ref name="LTL"/>. Recently, a tutorial for the LTL counter-example view in Rodin has been written<ref>LTL View in Rodin: http://www.stups.uni-duesseldorf.de/ProB/index.php5/Tutorial_LTL_Counter-example_View</ref>.
  
* To generate Ada code,
+
The physical unit support is explained here<ref>Unit Plugin: http://www.stups.uni-duesseldorf.de/ProB/index.php5/Tutorial_Unit_Plugin</ref>.
** Right-Click on the composed machine, or any tasking machine in the development, select ''Code Generation/Translate Event-B to Ada''.
 
** Open the generated ''code'' directory in the project to view the source files. A refresh will be necessary to make the code visible. The .gpr file has been provided for AdaCore GPS users.
 
  
* To create the Event-B model of the implementation,
+
The TLC for B model checking support is explained here<ref>TLC: http://www.stups.uni-duesseldorf.de/ProB/index.php5/TLC</ref>.
** Right-Click on the composed machine, or any tasking machine in the development, select ''Code Generation/Translate Tasking Event-B to Event-B''.
 
** The Event-B model should be updated with the flow control variables. Users are not able to manually edit the generated elements. The additions can be removed using the menu option ''Code Generation/Remove Generated Event-B''
 
  
== Generated Code ==
+
In addition we run a bug tracking system<ref>Bug Tracking System: http://jira.cobra.cs.uni-duesseldorf.de/</ref> to document known bugs, workarounds and feature requests.
The Ada Code generated by the translator is available at the following links:
 
  
for simulation of environment without addressed variables, [http://wiki.event-b.org/images/Code_Heating_ControllerTutorial_Completed.pdf Heating_ControllerTutorial_Completed]
+
{{TODO}}
  
for simulation of environment with addressed variables, [http://wiki.event-b.org/images/Code_Heating_Controller5AddressedSim_Completed.pdf Heating_Controller5AddressedSim_Completed]
+
== Conclusion ==
  
Removal of the environment task from the ''Heating_Controller5AddressedSim_Completed'' should be deployable.
+
With TLC4B we have provided a new scalable model checking approach for low-level B models. It should be particularly interesting for hardware models or lower-level models with very large state spaces.
 +
Fairness is often important for real-life temporal properties; by adding these we have made the ProB LTL model checker much more convenient and effective to use.
 +
The new LTL patterns arose multiple times in the various case studies; by providing them directly within the LTL language we have made the specification task much easier.
 +
Finally, theories in Rodin are very important and have played an important role in both WP1 and WP2 case studies.
 +
The support provided by ProB was thus essential for the success in these work packages.
  
[[Category:User documentation]]
+
== References ==
 +
<references/>

Revision as of 12:58, 7 November 2014

Overview

In this period we have worked on scalability of the tools, by improving ProB for theories, for the WP1 and WP2 case study demands, and by adding dedicated support for fairness properties. We have also provided a link to the TLC model checker for large state space of more concrete formal models. We have also added new features to the model checking core of ProB, in feedback from the other work packages.

Motivations / Decisions

LTL Fairness

Fairness is a notion where the search for counterexamples is restricted to paths that do not ignore infinitely the execution of a set of enabled actions imposed by the user as fair constraints. One possibility to set fairness constraints in ProB is to encode them in the LTLe formula intended to be checked. For example, for a given LTLe formula "f" a set of weak fairness conditions {e1,…,en} (where e1,...,en are some events) can be given as follows:

(FG e(e1) => GF [e1]) & … & (FG e(en) => GF [en]) => f.

In a similar way, strong fairness constraints can be imposed expressed by means of an LTLe formula:

(GF e(e1) => GF [e1]) & … & (GF e(en) => GF [en]) => f.

Checking fairness in this way is very often considered to be inefficient as usually the number of atoms (the possible valuations of the property) of the LTL property is exponential in the size of the formula [1] [2].

For this reason, the search algorithm of the LTL model checker in ProB has been extended in order to allow fairness to be checked efficiently. In addition, new operators have been added to the ProB’s LTL parser for setting fairness constraints to an LTLe property. The new operators are WF(-) and SF(-) and both accept as argument an operation. The fairness constraints must be given by means of implication: "fair => f", where "f" is the property to be checked and "fair" the fairness constraints.

In particular, "fair" can have one of the forms: "wfair", "sfair", "wfair & sfair", and "sfair & wfair", where "wfair" and "sfair" represent the imposed weak and strong fairness constraints, respectively.

Basically, "wfair" and "sfair" are expressed by means of logical formulas having the following syntax:

  • Weak fair conditions ("wfair"):
    • `WF(a)`, where `a` is an operation
    • `&` and `or`: conjunction and disjunction
  • Strong fair conditions ("sfair"):
    • `SF(a)`, where `a` is an operation
    • `&` and `or`: conjunction and disjunction

More information on setting fairness to LTL formulas and the LTL Model Checker is available on the ProB User Manual website [3].

Use Case

Consider an Event-B model formalising an algorithm for mutual exclusion with semaphores for two concurrent processes P_1 and P_2. Each process has been simplified to perform three types of events: request (for entering in the critical section), enter (entering the critical section), and release (exiting the critical section). (For more information on the algorithm and the design of the model see [4]).

Each of the actions of a process are represented by an respective event:

MUTEX Events horizontal.png

Each process P_i has three possible states that are denoted by the constants noncrit_{i} (the state in which P_i performs noncritical actions), wait_{i} (the state in which P_{i} waits to enter the critical section), and crit_{i} (representing the state in which P_{i} is in the critical section). Both processes share the binary semaphore y where y=1 indicates that the semaphore is free and y=0 that the semaphore is currently processed by one of the processes.

There are several requirements that the mutual exclusion algorithm should satisfy. The most important one is the mutual exclusion property that says always at most one process is in its critical section. This can be simply expressed, for example, as an invariant of the respective Event-B model: not(p1 = crit1 & p2 = crit2). However, there are other properties that can be easily expressed by means of LTL formulas and automatically checked on the model. For example, the requirement each process will enter infinitely often its critical section can be specified by the LTL formula `GF {p1 = crit1} & GF {p2 = crit2}` or the starvation freedom property that states each waiting process will eventually enter its critical section:

G ({p1 = wait1} => F {p1 = crit1}) & G ({p2 = wait2} => F {p2=crit2}) 

Running the LTL model checker of ProB will provide for the last two properties above a counterexample since the model permits that a process may perform infinitely often consecutively the events request, enter and release, and in this way to ignore the other process infinitely. An example trace that describes this behavior could be \langle Req2,Req1,Enter1,Rel1,Req1,Enter1,\ldots\rangle.

On the other hand, such behaviors can be considered as unrealistic computations for the later implementation of the algorithm. Therefore fairness constraints can be set in order to discard such behaviors. For example, checking the property process P_1 will enter its critical section infinitely often (as LTL property: `GF {p1 = crit1}`) can be checked by restricting that the event `Req1` will not be continuously ignored and that the event `Enter1` will not be ignored infinitely often. Both conditions on the property can be given by means of an LTLe formula on the right side of the implication as follows:

(FG e(Req1) => GF [Req1]) & (GF e(Enter1) => GF [Enter1]) => GF {p1 = crit1} 

For checking the formula the LTL model checker generates 13312 atoms and 7515 transitions and needs overall 509 ms to prove the property. On the other hand, using the extension of the LTL model checker for checking fairness (by entering the formula `WF(Req1) & SF(Enter1) => GF {p1=crit1}`), the model checker generates 32 atoms and 39 transitions (the atoms and transitions generated just for `GF {p1 = crit1}`) and an overall time of 50 ms.

For checking the requirement each process will enter infinitely often its critical section the LTL formula ` GF {p1 = crit1} & GF {p2 = crit2}` should be checked with the following fairness constraints:

(WF(Req1) & WF(Req2)) & (SF(Enter1) & SF(Enter2))

Encoding these fairness conditions as an LTLe formula will blow up exponentially the number of atoms and the transitions and thus make practically impossible to check the above property in a reasonable time.

New LTL Patterns

The ABZ landing gear case study [5] was formalised in Event-B and validated with ProB. [6] In the course of the validation of the model new features have been developed in ProB for checking relative deadlock freedom and determinism.

Since it has turned out that the features were a key part of the validation of the model and the authors believe that they will be of use for other Event-B system developments, the LTL model checker has been extended to support these features as new patterns within LTLe formulas:

  • deadlock(e1,e2,...,ek), where e1,e2,...,ek with k>0 are events. Used to check relative deadlocks, more precisely to check if a set of events are disabled in a state.
  • deterministic(e1,e2,…,ek), where e1,e2,...,ek with k>0 are events. Used to check that maximum one of the events in the parentheses is enabled in a state. Note that if the atomic proposition is checked in a state where no one of the events e1,e2,...,ek is enabled, the test will succeed.
  • controller(e1,e2,…,ek) , where e1,e2,...,ek with k>0 are events. Used to check that exactly one of the events e1,e2,...,ek is enabled in a state.

Theory Support

Theory Support was relevant for a variety of case studies, and is relevant for simulation, model checking and proving. We ensured that the Disprover also works with theories We have also improved the constraint propagation of the ProB kernel for records and freetypes, which are used to represent Event-B inductive datatypes. (As a side note, this feature is also being used by another EU project to use ProB for validating VDM specifications within the Ouverture tool). Finally, the treatment of recursive functions within the ProB kernel has been improved, also in light of dealing with recursive operators of Event-B Theories.

Physical Units

The physical units analysis has been further stabilised, several reported bugs have been fixed. Support for physical units has been extended to theories along with the general theory-related improvements of ProB mentioned in the previous paragraph. The plug-in was ported to Rodin 3, all bugfixes and changes could be back ported to Rodin 2 successfully.

Further extension to the unit analysis include:

  • Support for the analysis of units throughout refinement relations.
  • Support for abstract units like "length" that can later be concretised to standard SI units.

B to TLA+

We are interested in validating the correctness of our translation from B to TLA+. Hence, we have conducted extensive tests to validate our approach. For example, we use a range of models encoding mathematical laws to stress test our translation. These have proven to be very useful for detecting bugs in our translation and libraries. In addition, we have uncovered a bug in the model checker TLC. Moreover, we use a wide variety of benchmarks, checking that ProB and TLC produce the same result and generate the same number of states.

The current version of our translator covers almost all operators of a abstract B machine. Moreover, TLC can be used to validate liveness properties (LTL formulas) for B specifications under fairness conditions. Our approach has been published at the ABZ’2014 conference in Toulouse. A technical report is available [7].

Performance Improvements

Various performance improvements have been made to the model checker and animator for Event-B models, both in terms of memory consumption and speed. For example, ProB now executes the models from WP1 and WP2 considerably faster than at the beginning of the project and than at the beginning of the last period of the project. Another example is an Event-B model of the Early parser by JR Abrial (a standard benchmark used for ProB regression testing) is now running an order of magnitude faster than before the beginning of the project.

Available Documentation

ProB
The ProB Website[8] is the place where we collect information on the ProB toolset. There are several tutorials on ProB available in the User manual section[9]. We also supply documentation on extending ProB for developers[10]. Documentation and tutorials on the new LTL features available[3]. Recently, a tutorial for the LTL counter-example view in Rodin has been written[11].

The physical unit support is explained here[12].

The TLC for B model checking support is explained here[13].

In addition we run a bug tracking system[14] to document known bugs, workarounds and feature requests.

TODO

Conclusion

With TLC4B we have provided a new scalable model checking approach for low-level B models. It should be particularly interesting for hardware models or lower-level models with very large state spaces. Fairness is often important for real-life temporal properties; by adding these we have made the ProB LTL model checker much more convenient and effective to use. The new LTL patterns arose multiple times in the various case studies; by providing them directly within the LTL language we have made the specification task much easier. Finally, theories in Rodin are very important and have played an important role in both WP1 and WP2 case studies. The support provided by ProB was thus essential for the success in these work packages.

References

  1. O. Lichtenstein and A. Pnueli: Checking that Finite State Concurrent Programs Satisfy Their Linear Specification. POPL '85, Proceedings of the 12th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, ACM, 1985
  2. D. Plagge and M. Leuschel: Seven at one stroke: LTL model checking for High-level Specifications in B, Z, CSP, and more. STTT, 12(1): 9-21, Feb 2010
  3. 3.0 3.1 ProB User Manual: LTL Model Checking, http://www.stups.uni-duesseldorf.de/ProB/index.php5/LTL_Model_Checking
  4. C.Baier and J.-P. Katoen. “Principles of Model Checking”, The MIT Press, 2008, pages 43-45.
  5. F. Boniol, V. Wiels, “The Landing Gear System Case Study”, ABZ 2014
  6. D. Hansen, L. Ladenberger, H. Wiegard, J. Bendisposto, M. Leuschel, “Validation of the ABZ Landing Gear System using ProB”, ABZ 2014: The Landing Gear Case Study, 2014, pages 66-79, Springer International Publisher.
  7. http://stups.hhu.de/w/Special:Publication/HansenLeuschel_TLC4B_techreport
  8. ProB Website: http://www.stups.uni-duesseldorf.de/ProB/
  9. ProB User Manual: http://www.stups.uni-duesseldorf.de/ProB/index.php5/User_Manual
  10. ProB Developer Manual: http://www.stups.uni-duesseldorf.de/ProB/index.php5/Developer_Manual
  11. LTL View in Rodin: http://www.stups.uni-duesseldorf.de/ProB/index.php5/Tutorial_LTL_Counter-example_View
  12. Unit Plugin: http://www.stups.uni-duesseldorf.de/ProB/index.php5/Tutorial_Unit_Plugin
  13. TLC: http://www.stups.uni-duesseldorf.de/ProB/index.php5/TLC
  14. Bug Tracking System: http://jira.cobra.cs.uni-duesseldorf.de/