Polynomial Function Enclosures and Floating Point Software Verification

Jan Andrzej Duracz and Michal Konečný, in proceedings of Fifth International Workshop on Constraints in Formal Verification, Sydney, Australia, August 11, 2008

Abstract

Proving partial correctness of floating point programs is a hard verification problem. This is in part because error analysis of finite precision computation is difficult and in part due to the high complexity of the generated verification conditions. Typical verification conditions that arise in this context are predicates with real inequalities as atoms and therefore numerical constraint solvers seem a natural choice for the automation of such proofs.

Freely available numerical constraint solvers are typically based on interval arithmetic due to existence of mature interval algorithms and relatively low computational cost. However, the pathological loss of precision that such arithmetic incurs may limit the applicability of interval based solvers for the type of first order numerical constraints that result from floating point verification problems.

We propose to use function enclosures as the numerical type to base a dedicated solver on. We present a prototype implementation using polynomial bounds with arbitrary precision floating point coefficients and evaluate it on some example verification conditions.

BibTeX, pdf(a4)
Michal Konečný
Last modified: 7 August 2008