The ASTREÉ Analyzer

AI snapshot

**TL;DR** ASTREÉ is an abstract-interpretation-based static analyzer for C that aims to prove automatically the absence of runtime errors in large embedded control-command safety-critical real-time software generated from synchronous specifications. It reportedly produced correctness proofs with zero false alarms in a few hours on programs up to 400,000 lines. **Key findings** - ASTREÉ proved absence of runtime errors with 0 false alarms on 70,000-, 226,000-, and 400,000-line programs; the performance table reports 46mn, 3h57mn, and 11h48mn, with 599 Mb, 1.3 Gb, and 2.2 Gb memory and 32, 51, and 88 iterations, respectively. - Its multiple abstract domains include octagons, ellipsoid/filter domains, arithmetic-geometric progression, symbolic constants, Boolean relations, and trace partitioning; for the rate limiter, the octagon domain finds \(Y \in [-261,261]\) and stability for \(M \ge 144\), and for the IIR filter it over-approximates \(D2[0]\) by \([-6890.23, 6890.23]\). - The arithmetic-geometric progression domain bounds \( |B| \le 30.7191369175 \) with \(a = 1.00000011921\) and \(b = 5.87747175411e-39\). - ASTREÉ is described as sound, automatic, terminating, semantic-based, and scalable, with very few or no false alarms when adapted to an application domain. **Methods** - Static analysis by abstract interpretation directly on C source, using a concrete operational semantics based on ISO/IEC 9899:1999 with implementation-specific behaviors, user programming guidelines, and program-specific assertions; the abstract semantics abstracts trace-based reachable states. - Modular OCaml design selecting abstract domains, using an approximate reduced cardinal product of numerical and symbolic domains, widening/narrowing for convergence, fixpoint computation by structural induction on abstract syntax, and forward propagation for specification checking. - Applied to large embedded control-command safety-critical real-time software generated automatically from synchronous specifications; performance measured on 70,000, 226,000, and 400,000 lines on a 64-bit monoprocessor. **Limitations** - Paper-stated: ASTREÉ addresses only part of the verification challenge—absence of runtime errors in large embedded control-command safety-critical real-time software generated automatically from synchronous specifications—and excludes union types, dynamic memory allocation, unbounded recursive function calls, backward branching, conflicting side effects, and C libraries. - Paper-stated: extending beyond synchronous programs to more complex memory models and asynchronous programs will necessitate a complete redesign of the basic memory abstraction and fixpoint iterators. - Paper-stated: user-provided assertions are useful only when expressible in the analyzer’s abstract domains, and automatic refinement based on counter-examples has limits, as the filter ellipsoidal abstraction would require discovering sophisticated data representations and algorithms. Evident from the text: the evaluation is limited to the described industrial synchronous C programs, with no comparison to other analyzers reported.