Analyse statique de types algébriques et de tableaux

Résumé :
Pour assurer l’absence d’erreurs dans les logiciels critiques, la vérification formelle peut s’appuyer sur des méthodes d’analyse statique, telle que l’interprétation abstraite, qui déduisent des propriétés sur les programmes à partir de leur code source. Cependant, les domaines d’interprétation abstraite existants se concentrent majoritairement sur des programmes où les variables contiennent des nombres ou des pointeurs. Cette thèse étudie la possibilité de développer une interprétation abstraite pour des langages de programmation où les variables contiennent des valeurs de types algébriques, ou des tableaux de telles valeurs. Nous présentons une façon générique d’étendre les domaines numériques existants pour calculer des résumés du comportement entrée-sortie des fonctions manipulant des valeurs de types algébriques et des tableaux ; pourvu que les types algébriques en question soient non-récursifs. L’aspect entrée-sortie de notre analyse lui permet d’être modulaire, n’analysant qu’une seule fois chaque fonction. Un prototype de notre analyse pour les types algébriques (mais pas pour les tableaux) a été implémenté en OCaml et testé sur 43 exemples, dont certains inspirés du code du micro-noyeau seL4.

Mot clés : Interprétation abstraite, types algébriques, tableaux, segmentations

Static Analysis of Algebraic Data Types and Arrays

Abstract: In order to ensure that critical software  as no error, formal verification may rely on static analysis. Static analysis methods, such as abstract interpretation, infer the properties of a program by analysing its source code. However, the existing domains of abstract interpretation mainly focus on programs where the variables hold numbers or pointers. In this thesis, we study the possibility of developping an abstract interpretation for programming languages with algebraic types and arrays of values from algebraic types. We present a generic way of extending already existing numeric domains in order to infer inputoutput summaries of functions manipulating both numbers, values of algebraic types and arrays. A limitation of our approach is that we only handle non-recursive algebraic types. The input-output aspect of our function summaries allows for a modular analysis, where each function is analysed only once. A prototype of our analysis of algebraic types (without the analysis of arrays) was implemented in OCaml.

Keywords: Abstract interpretation, algebraic types, arrays, segmentations