Skip to Main content Skip to Navigation
Reports

Fast inference of polynomial invariants for imperative programs

David Cachera 1 Thomas Jensen 1 Arnaud Jobin 1 Florent Kirchner 1 
1 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : We propose an abstract interpretation based method to compute polynomial invariants for imperative programs. Our analysis is a backward propagation approach that computes preconditions for equalities like g=0 to hold at the end of execution. It extends previous work by Müller-Olm and Seidl to a language that includes both polynomial equalities and disequalities. Properties are expressed using ideals, a structure that satisfies the descending chain condition, enabling fixpoints computations to terminate without use of a widening operator. In the general case, termination is characterized using ideal membership tests and Gröbner bases computations. In order to optimize computational complexity, we propose a specialized analysis dealing with inductive invariants which ensures fast termination of fixpoints computations. The optimized procedure has been shown by experiments to work well in practice, and to be two orders of magnitude faster than the state of the art analyzer of Carbonell and Kapur.
Document type :
Reports
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00595783
Contributor : David Cachera Connect in order to contact the contributor
Submitted on : Wednesday, May 25, 2011 - 3:32:12 PM
Last modification on : Thursday, January 20, 2022 - 5:33:16 PM
Long-term archiving on: : Friday, November 9, 2012 - 12:10:52 PM

File

RR-7627.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00595783, version 1

Citation

David Cachera, Thomas Jensen, Arnaud Jobin, Florent Kirchner. Fast inference of polynomial invariants for imperative programs. [Research Report] RR-7627, INRIA. 2011, pp.31. ⟨inria-00595783⟩

Share

Metrics

Record views

309

Files downloads

165