Difference between pages "D45 Code Generation" and "D45 Prover Enhancement"
imported>Andy |
imported>Leuschel (→Status) |
||
| Line 1: | Line 1: | ||
= Overview = | = Overview = | ||
| − | The | + | * 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. |
| + | * The ProB plug-in allows to find and visualize counter examples to the invariant and deadlock preservation proof obligations. ProB has also been used for finding count examples to proof rules of the industrial partner Siemens. | ||
| + | * 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 = | = 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 == | |
| − | + | ||
| − | + | The proportion of automatically discharged proof obligations heavily depends on Auto-Tactic configuration. | |
| − | + | Sometimes, the automatic prover fails because the tactics are applied in a 'wrong' order - 'wrong' for a given PO - even though all needed tactics are present. | |
| + | Early version of Rodin provided preferences for automatic tactics that enabled to reorder them, but the ordering was lost at each change: one could not record a particular tactic order in order to reuse it later. | ||
| + | |||
| + | Another issue is to have more than one possibility to combine the tactics. Indeed, the only implicit combination of tactics available consisted in trying to apply them in turn for every open node of a proof. In the proving area, there exists a notion of ''tactic combinators'', also called ''tacticals'', that allow to combine tactics in various specific manners, thus providing a sort of tactic arithmetic. | ||
| + | |||
| + | The advanced preferences for auto-tactics solved these two issues. | ||
| + | |||
| + | == Isabelle Plug-in == | ||
| + | {{TODO}} ''To be completed by Matthias Schmaltz'' | ||
| + | == ProB Disprover == | ||
| + | |||
| + | ProB can be used to find counterexamples to invariant preservation and deadlock preservation proof obligations. | ||
| + | This feature relies on the constraint solving capabilities of the ProB kernel. It is available from the ProB plugin after loading an Event-B model. | ||
| + | |||
| + | WIthin the context of WP2 (Transportation) ProB has also been used to try and find counterexamples to individual proof rules in the Siemens proof rule database. | ||
| + | For this, the ProB command line tool has been extended to load proof rule files (using a Prolog parser to avoid the JVM startup time) and then applies the ProB constraint solver to try and find counter examples to each proof rule. | ||
| + | This work has already identified several errors in the Siemens rule database and the work is still ongoing. | ||
| + | A current issue is the addition of explicit well-definedness conditions into the proof rules, as well as the fact that some proof rules use substations inside predicates. | ||
| + | |||
| + | |||
| + | |||
| + | == SMT Solver Integration == | ||
| + | The integration of SMT solvers into the Rodin platform is motivated by two main reasons. On the one hand, the enhancement of its proving capability, especially in the field of arithmetics. On the other hand, the ability of extracting some useful informations from the proofs produced by these solvers, such as unsatisfiable cores, in order to significantly decrease the time necessary to prove a modified model. | ||
| + | |||
| + | == Incorporating SAT Solvers via Kodkod == | ||
| + | {{TODO}} ''To be completed by Daniel Plagge'' | ||
| + | |||
| + | We have integrated the Kodkod high-level interface to SAT-solvers into the kernel of ProB. | ||
| + | It is thus available as well for model checking, animation as well as for the disproving capabilities mentioned above. | ||
| + | Our integration allows predicates from Event-B (and B, Z and TLA+ as well) to be solved using a mixture of SAT-solving and ProB's own constraint-solving capabilities developed using constraint logic programming: the first-order parts which can be dealt with by Kodkod and the remaining parts solved by the existing ProB kernel. | ||
| + | We have conducted a first empirical evaluation and analyzed the respective merits of SAT-solving and classical constraint solving. | ||
| + | We also compare to using SMT solvers via recently available translators for Event-B. | ||
| + | |||
| + | === Conclusion === | ||
| + | After about three years or works and several attempts our translation to Kodkod is now mature enough to be put into practice and has been integrated into the latest version of the ProB toolset. | ||
| + | The development required a considerable number of subsidiary techniques to be implemented. | ||
| + | Our experiments have shown that the translation can be highly beneficial for certain kinds of constraints, and as such opens up new ways to analyze and validate formal specifications in Event-B. | ||
| + | However, the experiments have also shown that the constraint logic programming approach of ProB can be superior in a considerable number of scenarios; the translation to Kodkod and down to SAT is not (yet) the panacea. | ||
| + | The same can be said of the existing translations from B to SMT. | ||
| + | As such, we believe that much more research required to reap the best of both worlds (SAT/SMT and constraint programming). | ||
| + | An interesting side-effect of our work is that the ProB toolset now provides a double-chain (relying on technology developed independently and using different programming languages and paradigms) of validation for first-order predicates, which should prove relevant in high safety integrity level contexts. | ||
= Choices / Decisions = | = Choices / Decisions = | ||
| − | + | == New rewriting and inference rules == | |
| − | + | {{TODO}} ''To be completed by Laurent Voisin'' | |
| − | + | == Advanced Preferences for Auto-tactics == | |
| − | + | ||
| − | + | Since Rodin 2.1, one can create his own tactic profiles. A tactic profile allows to set and record a particular order of chosen basic tactics. Furthermore, a profile can be applied either globally (as before), or specifically for a given project. | |
| − | + | ||
| − | + | Since Rodin 2.3, tacticals and parameterization have been added to the profiles, thus increasing the potential of such proving feature. | |
| − | + | A tactic profile may now be composed of tacticals, that combine any number of basic tactics and other profiles. | |
| − | + | The parameterization allows for example to set a custom timeout on external provers such as AtelierB P1. | |
| − | |||
| − | + | == Isabelle Plug-in == | |
| + | {{TODO}} ''To be completed by Matthias Schmaltz'' | ||
| + | == ProB Disprover == | ||
| − | + | Currently the constraint based invariant and deadlock checker is run from within the ProB plug-in and not from the prover interface on individual proof obligations. | |
| − | + | Indeed, for invariant preservation the disprover thus checks an event for all invariants, rather than being applied on individual proof obligations related to that event. | |
| + | However, ProB does know which invariants have already been proven to be preserved by that particular event. | ||
| + | The rationale for running the invariant preservation checks in this way is that: | ||
| + | * the counterexample is a full valuation of the models variables and constants which can be displayed using the ProB interface, | ||
| + | * the invariants and guards truth values can be inspected in detail using the ProB interface, make the counter-example intelligible to the user, | ||
| + | * ProB can find out which of the axioms are theorems and ignore them. Indeed in the old ProB disprover approach all of the assumptions were fed, and ProB did not know which ones are relevant to find correct values for the constants and variables. In fact, some of the theorems turned out to be very complicated to check, and prevented ProB from finding counterexamples. | ||
| − | + | Similarly, the constraint-based deadlock checker is run from the ProB plug-in on a loaded model. As Rodin does not currently generate the deadlock freedom proof obligations, this was an obvious choice. Also, it enables the user to type in additional predicates to find "particularly interesting" counter examples (see ICLP'2011 article below). | |
| − | + | Also, another advantage is that, again, the counter example can be inspected using the ProB interface. | |
| − | == | + | == SMT Solver Integration == |
| − | + | The translation of Event-B language into the SMT-LIB language is the main issue of this integration. Two approaches were developed for this. The more efficient one is based on the translation capabilities of the integrated predicate prover of the Rodin platform (PP). It is completed by translating membership using an uninterpreted predicate symbol, refined with an axiom of the set theory. | |
| − | The | + | Technically, the plug-in classes extend the existing XProverCall, XProverInput, XProverReasoner, AbstractLazilyConstrTactic and ITacticParametizer classes which make it easy to integrate new tactics, reasoners and external prover calls. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == | + | == Incorporating SAT Solvers via Kodkod == |
| − | To | + | {{TODO}} ''To be completed by Daniel Plagge'' |
| − | + | ||
| + | Before starting our translation to Kodkod, we had experimented with several other alternate approaches to solve constraints in ProB. | ||
| + | [http://bddbddb.sourceforge.net/ bddbddb] offers the user a Datalog-like language that aims to support program analysis. | ||
| + | It uses BDDs to represent relations and compute queries on these relations. | ||
| + | In particular, one has to represent a state of the model as a bit-vector and events have to be implemented as relations between two of those bit-vectors. | ||
| + | These relations have to be constructed by creating BDDs directly with the underlying BDD library (JavaBDD) and storing them into a file. | ||
| + | Soon after starting experimenting with [http://bddbddb.sourceforge.net/ bddbddb] it became apparent that due to the lack of more abstract data types than bit vectors, the complexity of a direct translation from B to [http://bddbddb.sourceforge.net/ bddbddb] was too high, even for small models, and this avenue was abandoned. | ||
| + | |||
| + | SAL is a model-checking framework combining a range of tools for reasoning about systems. | ||
| + | The SAL tool suite includes a state of the art symbolic (BDD-based) and bounded (SAT-based) model checkers. | ||
| + | Some first results were encouraging for a small subset of the Event-B language, but the gap between B and SAL turned out to be too big in general and no realistic way was found to handle important B operators. | ||
= Available Documentation = | = Available Documentation = | ||
| − | + | * {{TODO}} Links for New rewriting and inference rules | |
| − | + | * {{TODO}} Links for Advanced Preferences for Auto-tactics | |
| + | * {{TODO}} Links for Isabelle Plug-in | ||
| + | * Links for ProB Disprover | ||
| + | ** [http://www.stups.uni-duesseldorf.de/w/Special:Publication/HaLe2011 Constraint-Based Deadlock Checking of High-Level Specifications. In Proceedings ICLP'2011, Cambridge University Press, 2011.] | ||
| + | * Links for ProB Kodkod Integration | ||
| + | ** [http://www.stups.uni-duesseldorf.de/w/Special:Publication/PlaggeLeuschel_Kodkod2012 Validating B,Z and TLA+ using ProB and Kodkod. Technical Report, 2012.] | ||
| + | * {{TODO}} Links for SMT Solver Integration | ||
= Status = | = Status = | ||
| + | == New rewriting and inference rules == | ||
| + | {{TODO}} ''To be completed by Laurent Voisin'' | ||
| + | == Advanced Preferences for Auto-tactics == | ||
| + | |||
| + | Advanced Preferences for Auto-tactics are functional in Rodin 2.3. This release provides a first set of tacticals and parameterization options. | ||
| + | |||
| + | Further releases may offer additional tacticals and options, according to user feedback. | ||
| + | |||
| + | == Isabelle Plug-in == | ||
| + | {{TODO}} ''To be completed by Matthias Schmaltz'' | ||
| + | == ProB Disprover == | ||
| + | |||
| + | The ProB constraint-based invariant and deadlock checkers are available in the current release of ProB for Rodin. The deadlock checker has been applied successfully on a very large industrial model within WP1 (automotive). | ||
| + | There is of course always the scope to improve the capabilities of the tool by improving the constraint solving capabilities. | ||
| + | In particular, further simplification of existential quantifiers will be important for the deadlock checker to be applied effectively on certain models. | ||
| + | |||
| + | The Siemens proof rule database validation work is still ongoing. | ||
| + | This work has already identified several errors in the Siemens rule database. | ||
| + | However, a current issue is the addition of explicit well-definedness conditions into the proof rules, as well as the fact that some proof rules use substations inside predicates. | ||
| + | |||
| + | == SMT Solver Integration == | ||
| + | {{TODO}} ''Laurent Voisin & Yoann Guyot'' | ||
| − | + | == Incorporating SAT Solvers via Kodkod == | |
| + | {{TODO}} ''To be completed by Daniel Plagge'' | ||
| − | + | The Kodkod integration is available in the latest nightly build version of ProB (1.3.5-beta7). | |
| − | + | The scope of the translations is being extended, the work has been partially carried out within the ADVANCE project and will be continued within that project. | |
[[Category:D45 Deliverable]] | [[Category:D45 Deliverable]] | ||
Revision as of 08:07, 19 March 2012
Overview
- 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.
- The ProB plug-in allows to find and visualize counter examples to the invariant and deadlock preservation proof obligations. ProB has also been used for finding count examples to proof rules of the industrial partner Siemens.
- 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
The proportion of automatically discharged proof obligations heavily depends on Auto-Tactic configuration. Sometimes, the automatic prover fails because the tactics are applied in a 'wrong' order - 'wrong' for a given PO - even though all needed tactics are present. Early version of Rodin provided preferences for automatic tactics that enabled to reorder them, but the ordering was lost at each change: one could not record a particular tactic order in order to reuse it later.
Another issue is to have more than one possibility to combine the tactics. Indeed, the only implicit combination of tactics available consisted in trying to apply them in turn for every open node of a proof. In the proving area, there exists a notion of tactic combinators, also called tacticals, that allow to combine tactics in various specific manners, thus providing a sort of tactic arithmetic.
The advanced preferences for auto-tactics solved these two issues.
Isabelle Plug-in
TODO To be completed by Matthias Schmaltz
ProB Disprover
ProB can be used to find counterexamples to invariant preservation and deadlock preservation proof obligations. This feature relies on the constraint solving capabilities of the ProB kernel. It is available from the ProB plugin after loading an Event-B model.
WIthin the context of WP2 (Transportation) ProB has also been used to try and find counterexamples to individual proof rules in the Siemens proof rule database. For this, the ProB command line tool has been extended to load proof rule files (using a Prolog parser to avoid the JVM startup time) and then applies the ProB constraint solver to try and find counter examples to each proof rule. This work has already identified several errors in the Siemens rule database and the work is still ongoing. A current issue is the addition of explicit well-definedness conditions into the proof rules, as well as the fact that some proof rules use substations inside predicates.
SMT Solver Integration
The integration of SMT solvers into the Rodin platform is motivated by two main reasons. On the one hand, the enhancement of its proving capability, especially in the field of arithmetics. On the other hand, the ability of extracting some useful informations from the proofs produced by these solvers, such as unsatisfiable cores, in order to significantly decrease the time necessary to prove a modified model.
Incorporating SAT Solvers via Kodkod
TODO To be completed by Daniel Plagge
We have integrated the Kodkod high-level interface to SAT-solvers into the kernel of ProB. It is thus available as well for model checking, animation as well as for the disproving capabilities mentioned above. Our integration allows predicates from Event-B (and B, Z and TLA+ as well) to be solved using a mixture of SAT-solving and ProB's own constraint-solving capabilities developed using constraint logic programming: the first-order parts which can be dealt with by Kodkod and the remaining parts solved by the existing ProB kernel. We have conducted a first empirical evaluation and analyzed the respective merits of SAT-solving and classical constraint solving. We also compare to using SMT solvers via recently available translators for Event-B.
Conclusion
After about three years or works and several attempts our translation to Kodkod is now mature enough to be put into practice and has been integrated into the latest version of the ProB toolset. The development required a considerable number of subsidiary techniques to be implemented. Our experiments have shown that the translation can be highly beneficial for certain kinds of constraints, and as such opens up new ways to analyze and validate formal specifications in Event-B. However, the experiments have also shown that the constraint logic programming approach of ProB can be superior in a considerable number of scenarios; the translation to Kodkod and down to SAT is not (yet) the panacea. The same can be said of the existing translations from B to SMT. As such, we believe that much more research required to reap the best of both worlds (SAT/SMT and constraint programming). An interesting side-effect of our work is that the ProB toolset now provides a double-chain (relying on technology developed independently and using different programming languages and paradigms) of validation for first-order predicates, which should prove relevant in high safety integrity level contexts.
Choices / Decisions
New rewriting and inference rules
TODO To be completed by Laurent Voisin
Advanced Preferences for Auto-tactics
Since Rodin 2.1, one can create his own tactic profiles. A tactic profile allows to set and record a particular order of chosen basic tactics. Furthermore, a profile can be applied either globally (as before), or specifically for a given project.
Since Rodin 2.3, tacticals and parameterization have been added to the profiles, thus increasing the potential of such proving feature. A tactic profile may now be composed of tacticals, that combine any number of basic tactics and other profiles. The parameterization allows for example to set a custom timeout on external provers such as AtelierB P1.
Isabelle Plug-in
TODO To be completed by Matthias Schmaltz
ProB Disprover
Currently the constraint based invariant and deadlock checker is run from within the ProB plug-in and not from the prover interface on individual proof obligations. Indeed, for invariant preservation the disprover thus checks an event for all invariants, rather than being applied on individual proof obligations related to that event. However, ProB does know which invariants have already been proven to be preserved by that particular event. The rationale for running the invariant preservation checks in this way is that:
- the counterexample is a full valuation of the models variables and constants which can be displayed using the ProB interface,
- the invariants and guards truth values can be inspected in detail using the ProB interface, make the counter-example intelligible to the user,
- ProB can find out which of the axioms are theorems and ignore them. Indeed in the old ProB disprover approach all of the assumptions were fed, and ProB did not know which ones are relevant to find correct values for the constants and variables. In fact, some of the theorems turned out to be very complicated to check, and prevented ProB from finding counterexamples.
Similarly, the constraint-based deadlock checker is run from the ProB plug-in on a loaded model. As Rodin does not currently generate the deadlock freedom proof obligations, this was an obvious choice. Also, it enables the user to type in additional predicates to find "particularly interesting" counter examples (see ICLP'2011 article below). Also, another advantage is that, again, the counter example can be inspected using the ProB interface.
SMT Solver Integration
The translation of Event-B language into the SMT-LIB language is the main issue of this integration. Two approaches were developed for this. The more efficient one is based on the translation capabilities of the integrated predicate prover of the Rodin platform (PP). It is completed by translating membership using an uninterpreted predicate symbol, refined with an axiom of the set theory. Technically, the plug-in classes extend the existing XProverCall, XProverInput, XProverReasoner, AbstractLazilyConstrTactic and ITacticParametizer classes which make it easy to integrate new tactics, reasoners and external prover calls.
Incorporating SAT Solvers via Kodkod
TODO To be completed by Daniel Plagge
Before starting our translation to Kodkod, we had experimented with several other alternate approaches to solve constraints in ProB. bddbddb offers the user a Datalog-like language that aims to support program analysis. It uses BDDs to represent relations and compute queries on these relations. In particular, one has to represent a state of the model as a bit-vector and events have to be implemented as relations between two of those bit-vectors. These relations have to be constructed by creating BDDs directly with the underlying BDD library (JavaBDD) and storing them into a file. Soon after starting experimenting with bddbddb it became apparent that due to the lack of more abstract data types than bit vectors, the complexity of a direct translation from B to bddbddb was too high, even for small models, and this avenue was abandoned.
SAL is a model-checking framework combining a range of tools for reasoning about systems. The SAL tool suite includes a state of the art symbolic (BDD-based) and bounded (SAT-based) model checkers. Some first results were encouraging for a small subset of the Event-B language, but the gap between B and SAL turned out to be too big in general and no realistic way was found to handle important B operators.
Available Documentation
- TODO Links for New rewriting and inference rules
- TODO Links for Advanced Preferences for Auto-tactics
- TODO Links for Isabelle Plug-in
- Links for ProB Disprover
- Links for ProB Kodkod Integration
- TODO Links for SMT Solver Integration
Status
New rewriting and inference rules
TODO To be completed by Laurent Voisin
Advanced Preferences for Auto-tactics
Advanced Preferences for Auto-tactics are functional in Rodin 2.3. This release provides a first set of tacticals and parameterization options.
Further releases may offer additional tacticals and options, according to user feedback.
Isabelle Plug-in
TODO To be completed by Matthias Schmaltz
ProB Disprover
The ProB constraint-based invariant and deadlock checkers are available in the current release of ProB for Rodin. The deadlock checker has been applied successfully on a very large industrial model within WP1 (automotive). There is of course always the scope to improve the capabilities of the tool by improving the constraint solving capabilities. In particular, further simplification of existential quantifiers will be important for the deadlock checker to be applied effectively on certain models.
The Siemens proof rule database validation work is still ongoing. This work has already identified several errors in the Siemens rule database. However, a current issue is the addition of explicit well-definedness conditions into the proof rules, as well as the fact that some proof rules use substations inside predicates.
SMT Solver Integration
TODO Laurent Voisin & Yoann Guyot
Incorporating SAT Solvers via Kodkod
TODO To be completed by Daniel Plagge
The Kodkod integration is available in the latest nightly build version of ProB (1.3.5-beta7). The scope of the translations is being extended, the work has been partially carried out within the ADVANCE project and will be continued within that project.
