×

Static analysis by policy iteration on relational domains. (English) Zbl 1187.68151

De Nicola, Rocco (ed.), Programming languages and systems. 16th European symposium of programming, ESOP 2007, held as part of the joint European conferences on theory and practice of software, ETAPS 2007, Braga, Portugal, March 24 – April 1, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-71314-2/pbk). Lecture Notes in Computer Science 4421, 237-252 (2007).
Summary: We give a new practical algorithm to compute, in finite time, a fixpoint (and often the least fixpoint) of a system of equations in the abstract numerical domains of zones and templates used for static analysis of programs by abstract interpretation. This paper extends previous work on the non-relational domain of intervals to relational domains. The algorithm is based on policy iteration techniques- rather than Kleene iterations as used classically in static analysis- and generates from the system of equations a finite set of simpler systems that we call policies. This set of policies satisfies a selection property which ensures that the minimal fixpoint of the original system of equations is the minimum of the fixpoints of the policies. Computing a fixpoint of a policy is done by linear programming. It is shown, through experiments made on a prototype analyzer, compared in particular to analyzers such as LPInv or the Octagon Analyzer, to be in general more precise and faster than the usual Kleene iteration combined with widening and narrowing techniques.
For the entire collection see [Zbl 1116.68003].

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)

Software:

Octagon
PDFBibTeX XMLCite
Full Text: DOI