thesis

Conception et mise en oeuvre d'un système informatique de compréhension de code exécutable

Defense date:

Jan. 1, 2005

Edit

Institution:

Paris 11

Disciplines:

Authors:

Directors:

Abstract EN:

The purpose of this study is the understanding of machine codes, using a computer system able to work automatically to a large extent. Here, "comprehension" means description of machine codes in another language which is more comprehensible for a human operator : When the choosed target language is a programming language, this transformation is named decompilation. Production of source code from machine code improves the expressiveness of the programs, giving representations that are suited during the verification process of the expected program properties. Decompilation is not only assumed to permit the recovery of information lost during the program compilation process, but it is also intended to extract a kind of information that is exclusively available at the machine level. Fundamentally, the main outcome of this study is a progress in the field of decompilation theory : Concerning the interpretation of machine codes, we present a generic assembly language, potentially suited for the description of machine programs on any target microprocessor or microcontroller. We also present a generalization of the control-flow analysis algorithms, to avoid graph structuring with the usual empirical methods that rely on pattern-matching of specific cases. Furthermore, we have extended the capabilities of the data-flow analysis techniques, by adapting type inference methods derived from the compilation theory and exploiting them within data propagation algorithms. At all significant stage of this study, our theory has been deployed and tested on a decompiler prototype dedicated to the analysis of industrial embedded real-time software.

Abstract FR:

L'objectif de cette étude est la compréhension de codes exécutables de machines à l'aide d'un système informatique essentiellement automatique. La " compréhension " signifie ici la description des codes exécutables dans un langage plus intelligible pour l'opérateur humain : si le langage cible est un tangage de programmation, on parle alors de décompilation. L'obtention du code source des programmes à partir de leur code exécutable accroît l'expressivité des programmes, ce qui rend plus facile la vérification des propriétés qu'ils sont supposés posséder. Par la décompilation il ne s'agît pas exclusivement de retrouver les informations perdues lors de la compilation, mais il s'agit aussi d'extraire d'autres informations qui ne sont accessibles qu'au niveau machine. Fondamentalement, le principal aboutissement de cette étude est une avancée dans la théorie de la décompilation : Pour l'interprétation de programmes machines nous présentons un langage assembleur générique, potentiellement capable de décrire les programmes de n'importe quel microprocesseur classique. De plus, nous avons généralisé les algorithmes d'analyse de flots de contrôle pour ne plus effectuer la structuration des graphes par des méthodes empiriques, jusque-là basées sur la recherche de formes connues. Nous avons aussi affiné les techniques d'analyse de flots de données, en adaptant des méthodes d'inférence de types afférentes au domaine de la compilation et en les exploitant dans les algorithmes de propagation des données. La théorie que nous avons développé a fait continuellement l'objet d'un déploiement sur un décompilateur prototype dédié à l'analyse de logiciels temps-réel embarqués industriels.