Incorporating SAT Solvers via Kodkod. The motivation behind incorporating the relational logic solver "Kodkod" into ProB was to evaluate how other technologies can complement ProB's constraint solving capabilities. A tight integration into ProB makes it 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. 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.
Incorporating SAT Solvers via Kodkod. Before starting our translation to Kodkod, we had experimented with several other alternate approaches to solve constraints in ProB. bddbddb [10] 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 [10] 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 [10] was too high, even for small models, and this avenue was abandoned. XXX is a model-checking framework combining a range of tools for reasoning about systems. The XXX 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 XXX turned out to be too big in general and no realistic way was found to handle important B operators. Kodkod has the advantage that is provides good support for relations and sets which play an essential role in Event-B's mathematical notation.
Incorporating SAT Solvers via Kodkod. 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. References [1] X. Xxxxxx, X. X. Xxxxxxx, and X. Xxxxxx. Xxxxxxxx/HOL - A Proof Assistant for Higher-Order Logic, volume 2283 of Lecture Notes in Computer Science. Springer, 2002. [2] X. X. Xxxxxxx. The foundation of a generic theorem prover. Journal of Automated Reasoning, 5(3):363-397, 1989. [3] X. X. Xxxxxxx. An Introduction to Mathematical Logic and Type Theory. Springer,2002. [4] A. Church. A formulation of the simple theory of types. Journal of Symbolic Logic,5(2):56-68, 1940.
