Trace Partitioning in Abstract Interpretation Based Static Analyzers

Laurent Mauborgne and Xavier Rival.
Trace Partitioning in Abstract Interpretation Based Static Analyzers.
In Mooly Sagiv, editor, European Symposium on Programming (ESOP 2005), volume 3444 of Lecture Notes in Computer Science, pages 5--20.
Springer-Verlag, 2005.
Compressed PostScript (225K), DVI (75K), PDF (302K).
Abstract: 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.

\bibitem{mauborgne:rival05}
{\sc Mauborgne, L., and Rival, X.}
\newblock Trace Partitioning in Abstract Interpretation Based Static Analyzers.
\newblock In {\em European Symposium on Programming (ESOP 2005)\/} (2005),
  M.~Sagiv, Ed., vol.~3444 of {\em Lecture Notes in Computer Science},
  Springer-Verlag, pp.~5--20.

@inproceedings{mauborgne:rival05,
author = "Laurent Mauborgne and Xavier Rival",
title = "Trace Partitioning in Abstract Interpretation Based Static Analyzers",
booktitle = "European Symposium on Programming (ESOP'05)",
volume = 3444,
series = "Lecture Notes in Computer Science",
year = 2005,
publisher = "Springer-Verlag",
editor = "M. Sagiv",
pages = "5--20",
}

Email: Laurent.Mauborgne@ens.fr