Skip to Main content Skip to Navigation
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
CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
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

https://hal.inria.fr/hal-00903628
Contributor : Antoine Miné <>
Submitted on : Tuesday, November 12, 2013 - 3:58:50 PM
Last modification on : Thursday, July 1, 2021 - 5:58:03 PM
Long-term archiving on: : Thursday, February 13, 2014 - 12:36:05 PM

File

journal_SCP_ok.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

486

Files downloads

694