AdaCore Blog

Research Corner - Floating-Point Computations in SPARK

by Yannick Moy

It is notoriously hard to prove properties of floating-point computations, including the simpler bounding properties that state safe bounds on the values taken by entities in the program. Thanks to the recent changes in SPARK 17, users can now benefit from much better provability for these programs, by combining the capabilities of different provers. For the harder cases, this requires using ghost code to state intermediate assertions proved by one of the provers, to be used by others. This work is described in an article which was accepted at VSTTE 2017 conference. In this article, we describe the mechanisms for adapting the formulas to prove to different provers based on  different technologies to interpret floating-point computations. As we already presented on this blog, the improvements in particular with the abstract interpreter CodePeer and the SMT prover Z3 are very important.

One figure from the article which explains well the current situation is the following:

In order to prove the postcondition of the procedure analyzed (last line), it is necessary to insert 12 intermediate assertions in the source code, which are proved each by one of the provers provided with SPARK Pro (CVC4, ALt-Ergo, Z3 and CodePeer). The green cells in that figure correspond to provers which prove the corresponding formula, with the time they take for that in seconds. Some of these assertions require the use of ghost code to define entities only meant for verification.

While this may seem like a lot of work to prove here a single postcondition, you may convince yourself by reading the article (where we give a mathematical argument for the proof) that this is not trivial either. And the improvements we observed with provers not (yet) included in SPARK (the provers AE_fpa and Colibri on the right hand side of the figure) give us much hope that the situation is going to improve a lot in the coming year.

Posted in #Formal Verification    #SPARK   

About Yannick Moy

Yannick Moy

Yannick Moy is Head of the Static Analysis Unit at AdaCore. Yannick contributes to the development of SPARK, a software source code analyzer aiming at verifying safety/security properties of programs. He frequently talks about SPARK in articles, conferences, classes and blogs (in particular Yannick previously worked on source code analyzers for PolySpace (now The MathWorks) and at Université Paris-Sud.