Backward under-approximations in numeric abstract domains to automatically infer sufficient program conditions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Science of Computer Programming Année : 2013

Backward under-approximations in numeric abstract domains to automatically infer sufficient program conditions

Résumé

In this article, we discuss the automatic inference of sufficient preconditions by abstract interpretation and sketch the construction of an under-approximating backward analysis. We focus on numeric properties of variables and revisit three classic numeric abstract domains: intervals, octagons, and polyhedra, with new under-approximating backward transfer functions, including the support for non-deterministic expressions, as well as lower widenings to handle loops. We show that effective under-approximation is possible natively in these domains without necessarily resorting to disjunctive completion nor domain complementation. Applications include the derivation of sufficient conditions for a program to never step outside an envelope of safe states, or dually to force it to eventually fail. We built a proof-of-concept prototype implementation and tried it on simple examples. Our construction and our implementation are very preliminary and mostly untried; our hope is to convince the reader that this constitutes a worthy avenue of research.
Fichier principal
Vignette du fichier
journal_SCP_ok.pdf (396 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00903628 , version 1 (12-11-2013)

Identifiants

Citer

Antoine Miné. Backward under-approximations in numeric abstract domains to automatically infer sufficient program conditions. Science of Computer Programming, 2013, ⟨10.1016/j.scico.2013.09.014⟩. ⟨hal-00903628⟩
233 Consultations
522 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More