Trace partitioning in abstract interpretation based static analyzers. (English) Zbl 1108.68427

Mauborgne, Laurent; Rival, Xavier

Sagiv, Mooly (ed.), Programming languages and systems. 14th European symposium on programming, ESOP 2005, held as part of the joint European conferences on theory and practice of software, ETAPS 2005, Edinburgh, UK, April 4–8, 2005. Proceedings. Berlin: Springer (ISBN 3-540-25435-8/pbk). Lecture Notes in Computer Science 3444, 5-20 (2005).

Summary: When designing a tractable static analysis, one usually needs to approximate the trace semantics. This paper proposes a systematic way of regaining some knowledge about the traces by performing the abstraction over a partition of the set of traces instead of the set itself. This systematic refinement is not only theoretical but tractable: we give automatic procedures to build pertinent partitions of the traces and show the efficiency on an implementation integrated in the Astrée static analyzer, a tool capable of dealing with industrial-size software.
For the entire collection see [Zbl 1068.68008].

MSC:

68N99

Theory of software

Software:

ASTREE; Octagon