Design and Implementation of a Special-Purpose Static Program Analyzer for Safety-Critical Real-Time Embedded Software

Bruno Blanchet, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, Antoine Miné, David Monniaux and Xavier Rival
Design and Implementation of a Special-Purpose Static Program Analyzer for Safety-Critical Real-Time Embedded Software.
In Torben Æ. Mogensen, David A. Schmidt and I. Hal Sudborough, editors, The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones, volume 2566 of Lecture Notes in Computer Science, pages 85--108.
Springer-Verlag, 2002.
Compressed PostScript (190K), DVI (122K), PDF (206K).
Abstract: We report on a successful preliminary experience in the design and implementation of a special-purpose Abstract Interpretation based static program analyzer for the verification of safety critical embedded real-time software. The analyzer is both precise (zero false alarm in the considered experiment) and efficient (less than one minute of analysis for 10,000 lines of code). Even if it is based on a simple interval analysis, many features have been added to obtain the desired precision: expansion of small arrays, widening with several thresholds, loop unrolling, trace partitioning, relations between loop counters and other variables. The efficiency of the tool mainly comes from a clever representation of abstract environments based on balanced binary search trees.

\bibitem{bccfmmmr02}
{\sc Blanchet, B., Cousot, P., Cousot, R., Feret, J., Mauborgne, L., Miné, A., 
     Monniaux, D., and Rival, X.}
\newblock {\em The Essence of Computation: Complexity, Analysis,
  Transformation. Essays Dedicated to Neil D. Jones}, chapter Design and
  Implementation of a Special-Purpose Static Program Analyzer for
  Safety-Critical Real-Time Embedded Software, pages 85--108.
\newblock Lecture Notes in Computer Science 2566. Springer-Verlag, 2002.


@inbook{bccfmmmr02,
editor = {Torben Mogensen and David Schmidt and I. Hal Sudborough},
author = "Bruno Blanchet and Patrick Cousot and Radhia Cousot and J{\'e}r{\^o}me
         Feret and Laurent Mauborgne and Antoine Min{\'e} and David Monniaux
         and Xavier Rival",
title = {The Essence of Computation:
             Complexity, Analysis, Transformation.
             Essays Dedicated to Neil D. Jones},
chapter = "Design and Implementation of a Special-Purpose Static Program 
Analyzer for Safety-Critical Real-Time Embedded Software",
pages = "85--108",
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science 2566},
year = {2002}
}

Email: Laurent.Mauborgne@ens.fr