Inferring Frame Conditions with Static Correlation Analysis

OANA F. ANDREESCU, Internet of Trust, France
THOMAS JENSEN, Inria, France and ProvenRun, France
BENOÎT MONTAGU, ProvenRun, France


We introduce the abstract domain of correlations to denote equality relations between parts of inputs and outputs of programs. We formalise the theory of correlations, and mechanically verify their semantic properties. We design a static inter-procedural dataflow analysis for automatically inferring correlations for programs written in a first-order language equipped with algebraic data-types and arrays. The analysis, its precision and execution cost, have been evaluated on the code and functional specification of an industrial-size micro-kernel. We exploit the inferred correlations to automatically discharge two thirds of the proof obligations related to the preservation of invariants for this micro-kernel.

See this publication