Traces abstraction in static analysis and program transformation.

Abstraction de traces en analyse statique et transformation de programmes.

Xavier Rival (1)

1 LIENS - Laboratoire d'informatique de l'école normale supérieure

We study of abstractions for sets of traces adapted to static analysis and program transformations in the abstract interpretation framework. In the first part, we propose a general framework for control-based trace partitioning in static analysis. In particular, this framework allows to use properties of the history of program executions in order to express disjunctions of abstract properties in static analyses. As a result, we obtain e±cient analyses, improving not only precision but also execution time in most cases. This method was implemented in the Astree analyzer, devoted to the analysis of C programs. Moreover, we report excellent result in the analysis of large critical real world programs. In the second part, we develop automatic techniques for the inspections of alarms produced by an analyzer such as Astree. Indeed, the analyzer is incomplete, so an alarm raised by Astree could be either a real bug or just be due to an imprecision inherent in the analysis. First, we propose to extract semantic slices, i.e. subsets of the program execution traces, which satisfy some given conditions; this approach allows to characterize more precisely the context corresponding to an alarm. Furthermore, in some cases, it helps to prove the alarm to be false; otherwise, it may help to find a real error scenario. Then, we define families of dependence analyses so as to track the origin of abnormal behaviors in programs, and to help for a more efficient diagnosis of the reason why an alarm was raised. We got encouraging results using a prototype, which we implemented. In the last part, we define a general formalization for compilation in the abstract interpretation framework and we integrate several approaches to certified compilation in our framework. First, we propose a method based on a translation of abstract invariants computed in an analysis of the source code and on the checking of the the soundness of the resulting invariants. This checking allows to trust the translated invariant independently from any assumption about the soundness of the translation or the source analysis. Second, we formalize the translation equivalence approach, which amounts to proving the correctness of compilation, by checking that the source program and the compiled program are equivalent. Last, we compare both techniques not only in the theoretical point of view but also in a practical experiment.

Cette thµese est consacree à l'etude d'abstractions d'ensemble de traces adaptees µa l'analyse statique et aux transformations de programmes. Cette etude a ete menee dans le cadre de l'interpretation abstraite. Dans une premiµere partie, nous proposons un cadre general permettant de definir des analyses effectuant un partitionnement des traces. Cela permet en particulier d'utiliser des proprietes definies par l'histoire des executions, pou ecrire des disjonctions de proprietes abstraites utiles lors de l'analyse statique. Ainsi, nous obtenons des analyses plus efficaces, qui sont non seulement plus precises mais aussi plus rapides. La methode a ete implementee et eprouvee dans l'analyseur de code C Astree, et on obtient d'excellents resultats lors de l'analyse d'applications industrielles de grande taille. La seconde partie est consacree au developpement de methodes permettant d'automatiser le diagnostique des alarmes produites par un analyseur tel qu'Astree. En eff en raison de l'incompletude de l'analyseur, une alarme peut, soit reveler une veritable erreur dans le programme, soit provenir d'une imprecision de l'analyse. Nous proposons tout d'abord d'extraire des slices semantiques, c'est à ire des sous-ensembles de traces du programme, satisfaisant certaines conditions ; cette technique permet de mieux caracteriser le contexte d'une alarme et peut aider, soit àprouver l'alarme fausse, soit à montrer un veritable contexte d'erreur. Ensuite, nous definissons des familles d'analyses de dependances adaptees µa la recherche d'origine de comportements anormaux dans un programme, afin d'aider µa un diagnostique plus efficace des raisons d'une alarme. Les resultats lors de l'implementation d'un prototype sont encourageants. Enfin, dans la troisiµeme partie, nous definissons une formalisation generale de la compilation dans le cadre de l'interpretation abstraite et integrons diverses techniques de compilation certifiee dans ce cadre. Tout d'abord, nous proposons une methode fondee sur la traduction d'invariants obtenus lors d'une analyse du code source et sur la verification independante des invariants traduits. Ensuite, nous formalisons la methode de preuve d'equivalence, qui produit une preuve de correction de la compilation, en prouvant l'equivalence du programme compile et du programme source. Enfin, nous comparons ces methodes du point de vue theorique et µa l'aide de resultats experimentaux.

Mots clés: Abstraction de traces; Analyse Statique; Tranformations de Programmes

Domaines: Informatique [cs]

Xavier Rival. Abstraction de traces en analyse statique et transformation de programmes.. Informatique [cs]. Ecole Polytechnique X, 2005. Français. ⟨NNT : ⟩. ⟨pastel-00001914⟩