From the computer virology fudments toward a formal immunology

Cette thèse aborde trois thèmes : la formalisation de la virologie informatique, l'élaboration de protections contre l'auto-reproduction et le problème de la détection des programmes malicieux. Nous proposons une formalisation s'appuyant sur les fondements de l'informatique théorique et sur les travaux fondateurs de la discipline. Nous obtenons un formalisme souple où le théorème de récursion prend le rôle d'un compilateur de virus informatiques. Ce théorème trouve alors la place qui lui manquait encore dans la théorie de la programmation. Ce formalisme nous fournit des bases suffisamment solides pour étudier de nouvelles stratégies de protection. Dans un premier temps nous nous intéressons aux relations qu'entretiennent auto-reproduction et capacités de calcul afin d'identifier un modèle raisonnable où l'auto-reproduction est impossible. Ensuite nous exposons deux stratégies construite sur la complexité de Kolmogorov, un outil de l'informatique théorique reliant la sémantique et la syntaxe concrète d'un langage de programmation. Le thème de la détection comporte deux parties. La première traite de la difficulté de la détection des virus informatiques : nous identifions les classes de la hiérarchie arithmétique correspondant à différents scénarios d'infections informatiques. La seconde partie aborde des aspects plus pratiques en décrivant l'architecture d'un détecteur de programmes malicieux conçu durant cette thèse. Ce prototype utilise une détection morphologique, l'idée est de reconnaître la forme des programmes malicieux en utilisant des critères syntaxiques et sémantiquesThis dissertation tackles three topics: the formalization of the computer virology, the construction of protections against self-reproduction and the issue of malware detection. We propose a formalization that is based over computer science foundations and over the founder works of the discipline. We obtain a generic framework where the recursion theorem takes a key role. This theorem is seen as computer virus compiler, this approach provides a new programming perspective. The sound basis of this framework allows to study new protection strategies. First, we analyze the relations between the notion of self-reproduction and the computation capabilities. We aims at identifying a reasonable model of computation where self-reproduction is impossible. Then we propose two defense strategies based on the Kolmogorov complexity, a tool which relates the semantics to the concrete syntax of programming languages. We treat the issue of malware detection in two steps. First, we study the difficulty related to the detection of several scenarios of computer infection. Second, we present a malware detector that was designed during the thesis. It is based on a morphological detection which allies syntaxical and semantical criteria to identify the shapes of malwar