A Three-tier Strategy for Reasoning about Floating-Point Numbers in SMT

Sylvain Conchon 1, 2 Mohamed Iguernlala 1, 3 Kailiang Ji 1 Guillaume Melquiond 1, 2 Clément Fumex 1, 2
2 TOCCATA - Certified Programs, Certified Tools, Certified Floating-Point Computations
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : The SMT-LIB standard defines a formal semantics for a theory of floating-point (FP) arithmetic (FPA). This formalization reduces FP operations to reals by means of a rounding operator, as done in the IEEE-754 standard. Closely following this description, we propose a three-tier strategy to reason about FPA in SMT solvers. The first layer is a purely axiomatic implementation of the automatable semantics of the SMT-LIB standard. It reasons with exceptional cases (e.g. overflows, division by zero, undefined operations) and reduces finite representable FP expressions to reals using the rounding operator. At the core of our strategy, a second layer handles a set of lemmas about the properties of rounding. For these lemmas to be used effectively, we extend the instantiation mechanism of SMT solvers to tightly cooperate with the third layer, the NRA engine of SMT solvers, which provides interval information. We implemented our strategy in the Alt-Ergo SMT solver and validated it on a set of benchmarks coming from the SMT-LIB competition, but also from the deductive verification of C and SPARK programs. The results show that our approach is promising and compete with existing techniques implemented in state-of-the-art SMT solvers.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01522770
Contributeur : Guillaume Melquiond <>
Soumis le : lundi 15 mai 2017 - 15:08:46
Dernière modification le : jeudi 15 juin 2017 - 09:09:21

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01522770, version 1

Citation

Sylvain Conchon, Mohamed Iguernlala, Kailiang Ji, Guillaume Melquiond, Clément Fumex. A Three-tier Strategy for Reasoning about Floating-Point Numbers in SMT. 2017. <hal-01522770>

Partager

Métriques

Consultations de
la notice

117

Téléchargements du document

66