Skip to Main content Skip to Navigation
New interface
Journal articles

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

Antoine Miné 1, 2 
2 ABSTRACTION - Abstract Interpretation and Static Analysis
DI-ENS - Département d'informatique - ENS Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : 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.
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
Contributor : Antoine Miné Connect in order to contact the contributor
Submitted on : Tuesday, November 12, 2013 - 3:58:50 PM
Last modification on : Thursday, March 17, 2022 - 10:08:35 AM
Long-term archiving on: : Thursday, February 13, 2014 - 12:36:05 PM


Files produced by the author(s)




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⟩



Record views


Files downloads