Combinaison de sous et surapproximations de la memoire pour l'analyse de code bas-niveau // Combining over and underapproximation of memory abstractions for low-level code analysis

Le théorème de Rice énonçant qu'on ne peut pas avoir de méthode qui sache automatiquement dire si une propriété sur un programme est vraie ou non a conduit à séparer les outils de vérification en deux groupes: les outils sound fonctionnant par sur-approximation, comme l'interprétation abstraite, sont capables de prouver automatiquement que certaines propriétés sont vraies, mais ne savent parfois pas conclure et produisent des alarmes; à l'inverse, les outils complete fonctionnant par sous-approximation, comme l'exécution symbolique, savent produire des contre-exemples, mais pas démontrer si une propriété est vraie.

*Le but général de la thèse est d'étudier la combinaison entre méthodes sound et complete d'analyse de programme, et en particulier l'analyse statique par interprétation abstraite et la génération de formules sous-approximée par exécution symbolique*.

Nous nous intéresserons particulièrement à la combinaison d'abstractions sur et sous-approximantes, en particulier pour la mémoire. Les applications envisagées en priorité concernent les analyses de code au niveau binaire, telles que réalisées par la combinaison des plateformes d'analyse BINSEC et CODEX, pour pouvoir trouver des failles de securite automatiquement ou demontrer leur absence.



------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Rice's theorem stating that no method can automatically tell whether a property of a program is true or not has led to the separation of verification tools into two groups: sound tools operating by over-approximation, such as abstract interpretation, are able to automatically prove that certain properties are true, but are sometimes unable to conclude and produce alarms; conversely, complete tools operating by under-approximation, such as symbolic execution, are able to produce counter-examples, but are unable to demonstrate whether a property is true.

*The general aim of the thesis is to study the combination of sound and complete methods of programanalysis, and in particular static analysis by abstract interpretation and the generation of underapproximated formulae by symbolic execution*.

We are particularly interested in the combination of over- and sub-approximating abstractions, especially for memory. The priority applications envisaged concern the analysis of code at the binary level, as achieved by the combination of the BINSEC and CODEX analysis platforms, so as to automatically discover new security vulnerabilities, or prove their absence.


------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Pôle fr : Direction de la Recherche Technologique
Pôle en : Technological Research
Département : Département Ingénierie Logiciels et Systèmes (LIST)
Service : LSL (DILS)
Laboratoire : Laboratoire pour la Sûreté du Logiciel
Ecole doctorale : Sciences Mathématiques de Paris Centre (ED386)
Directeur de thèse : RIVAL Xavier
Organisme : INRIA
Laboratoire : INRIA/Ens ULM

Public/private mixed funding

Pôle fr : Direction de la Recherche Technologique
Pôle en : Technological Research
Département : Département Ingénierie Logiciels et Systèmes (LIST)
Service : LSL (DILS)