2012-01-28 Verification day

Program

David Monniaux: Implicit representations for static analysis

Static analysis by abstract interpretation traditionally follows the control-flow graph of the programs, with one inductive invariant being computed for every control node, computed by forward (or backward) propagation along control edges.

Thao Dang: Reachability analysis for polynomial dynamical systems using the Bernstein expansion

This paper is concerned with the reachability computation problem for polynomial discrete-time dynamical systems. Such computations constitute a crucial component in algorithmic verification tools for hybrid systems and embedded software with polynomial dynamics, which have found applications in many engineering domains. We describe two methods for over-approximating the reachable sets of such systems; these methods are based on a combination of the Bernstein expansion of polynomial functions and a representation of reachable sets by template polyhedra. Using a prototype implementation, the performance of the methods was demonstrated on a number of examples of control systems and biological systems.

Marie-Laure Potet: Les besoins pour l'analyse de vulnérabilités

(20 minutes)

Nous présentons nos travaux en cours dans le cadre de l'analyse de code vulnérable, en insistant notamment sur :

• les particularités de ce type d'analyse : code binaire, modèle mémoire ad hoc
• les conséquences sur les techniques d'analyse à utiliser ou développer

Laurent Mounier: Analyse de teinte sur du code binaire

(~ 20 minutes)

Nous présentons un exemple concret d'analyse développée pour la recherche de vulnérabilités : l'analyse de teinte.

Radu Iosif: Acceleration Techniques for Program Verification

By acceleration we understand the class of techniques based on a precise computation of the transitive closure of (a part of) the transition relation of the program. In the first part of this talk we show how acceleration can be combined with interpolation to generate inductive interpolants which are crucial in abstraction refinement. This combined method applies to sequential non-recursive programs. In the second part of this talk, we show how acceleration can be applied, in a modular fashion, to recursive program schemes. The result is a Newtonian underapproximation sequence that converges to the tuple of summary relations of all procedures in the program. We also define a class of programs for which our method is shown to be complete i.e. terminate with the precise result.

Joint work with EPFL (Lausanne), IMDEA (Madrid), FIT BUT (Brno)

Nicolas Halbwachs: When the decreasing sequence fails

The classical method for program analysis by abstract interpretation consists in computing an increasing sequence with widening, which converges towards a correct solution, then computing a decreasing sequence of correct solutions without widening. It is generally admitted that, when the decreasing sequence reaches a fixpoint, it cannot be improved further. As a consequence, all efforts for improving the precision of an analysis have been devoted to improving the limit of the increasing sequence. In this paper, we propose a method to improve a fixpoint after its computation. The method consists in projecting the solution onto well-chosen components and to start again increasing and decreasing sequences from the result of the projection.