Design and Implementation of a Special-Purpose Static Program Analyzer for Safety-Critical Real-Time Embedded Software, invited chapter.
In The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones, T. Mogensen, D.A. Schmidt and I.H. Sudborough (Eds.), Lecture Notes in Computer Science 2566, pp. 85—108, © Springer-Verlag, Berlin, October 2002.
: PDF (511.8 KB)
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{BlanchetCousotEtAl02-NJ}
B{.} Blanchet, P{.} Cousot, R{.} Cousot, J{.} Feret, L{.} Mauborgne,
A{.} Min{\'e}, D{.} Monniaux and X{.} Rival.
\newblock Design and Implementation of a Special-Purpose Static Program
Analyzer for Safety-Critical Real-Time Embedded Software, invited chapter.
\newblock \emph{The Essence of Computation: Complexity, Analysis,
Transformation. Essays Dedicated to Neil D{.} Jones}, T{.} Mogensen,
D{.}A{.} Schmidt and I{.}H{.} Sudborough (Eds.), pp.\ 85--108, October
2002. LNCS 2566, Springer\discretionary{-}{}{-}Verlag, Berlin, 2002.
@inCollection{BlanchetCousotEtAl02-NJ,
author = {B{.} Blanchet and P{.} Cousot and R{.} Cousot and J{.} Feret and
L{.} Mauborgne and A{.} Min{\'e} and D{.} Monniaux and X{.} Rival},
title = {Design and Implementation of a Special-Purpose Static Program
Analyzer for Safety-Critical Real-Time Embedded Software,
invited chapter},
booktitle = {The Essence of Computation: Complexity, Analysis, Transformation.
Essays Dedicated to Neil D{.} Jones},
editor = {T{.} Mogensen and D{.}A{.} Schmidt and I{.}H{.} Sudborough},
series = {LNCS 2566},
pages = {85--108},
publisher = {Springer\discretionary{-}{}{-}Verlag},
month = oct,
year = 2002,
isbn = {3-540-00326-6},
}