Cette thèse porte en premier lieu sur l'analyse et le désassemblage de programmes malveillants utilisant certaines techniques d'obscurcissement telles que l'auto-modification et le chevauchement de code. Les programmes malveillants trouvés dans la pratique utilisent massivement l'auto-modification pour cacher leur code utile à un analyste. Nous proposons une technique d'analyse hybride qui utilise une trace d'exécution déterminée par analyse dynamique. Cette analyse découpe le programme auto-modifiant en plusieurs sous-parties non auto-modifiantes que nous pouvons alors étudier par analyse statique en utilisant la trace comme guide. Cette seconde analyse contourne d'autres techniques de protection comme le chevauchement de code afin de reconstruire le graphe de flot de contrôle du binaire analysé. Nous étudions également un détecteur de programmes malveillants, fonctionnant par analyse morphologique : il compare les graphes de flot de contrôle d'un programme à analyser à ceux de programmes connus comme malveillants. Nous proposons une formalisation de ce problème de comparaison de graphes, des algorithmes permettant de le résoudre efficacement et détaillons des cas concrets d'application à la détection de similarités logicielles / This dissertation explores tactics for analysis and disassembly of malwares using some obfuscation techniques such as self-modification and code overlapping. Most malwares found in the wild use self-modification in order to hide their payload from an analyst. We propose an hybrid analysis which uses an execution trace derived from a dynamic analysis. This analysis cuts the self-modifying binary into several non self-modifying parts that we can examine through a static analysis using the trace as a guide. This second analysis circumvents more protection techniques such as code overlapping in order to recover the control flow graph of the studied binary. Moreover we review a morphological malware detector which compares the control flow graph of the studied binary against those of known malwares. We provide a formalization of this graph comparison problem along with efficient algorithms that solve it and a use case in the software similarity field

Cette thèse s'inscrit dans la problématique de la comparaison de graphes. Nous proposons dans la première partie de ce manuscrit plusieurs algorithmes de recherche de motifs similaires dans de grands graphes. La seconde partie de cette thèse traite de l'étude des arborescences de fichiers, structure de données pour laquelle la méthode initiale de reconnaissance de motifs a été développée. Nous présentons un modèle stochastique pour la génération aléatoire de structure arborescentes, basé sur les observations de l'étude statistique des données réelles. Enfin, nous détaillons deux adaptations de l'algorithme de reconnaissance de motifs similaires à des applications particulières. La première concerne la reconnaissance d'objets extraits de la video basse résolution pour l'indexation grossière. La deuxième application a été développée pour la visualisation de l'évolution de projets logiciels.

Je présente dans ce mémoire de HDR le travail pionnier de la bio-informatique pour les peptides non-ribosomiques (PNR). Ces recherches ont été initiées sur Lille en 2006 et ont abouti à l'unique plate-forme d'analyse bio-informatique des PNR appelée Norine, dont je suis un des membres fondateurs. Les peptides non-ribosomiques font partie des petites molécules produites par les micro-organismes, bactéries et fungi, pour coloniser leur milieu. Ces peptides particuliers ont l'avantage d'avoir une grande variété de structures. En effet, ils peuvent être linéaires, mais aussi contenir des cycles et/ou des branchements et sont composés de plus de 500 briques de base différentes. Cette variété provient de leur synthèse réalisée par de gros complexes enzymatiques, les synthétases peptidiques non-ribosomiques (PNRS). Ceux-ci sélectionnent les acides aminés et d'autres composés, appelés monomères, puis les assemblent en formant des liaisons peptidiques et d'autres liaisons. Ainsi, les peptides non-ribosomiques présentent une grande diversité d'activités telles que antibiotique, anti-cancéreux ou immuno-suppresseur. Certains, comme la pénicilline, sont des médicaments employés fréquemment. Dans une première partie, je propose un regard différent sur les synthétases en associant les particularités des peptides aux fonctions enzymatiques nécessaires à les réaliser. Puis, je décris les principales étapes nécessaires à la conception d'un outil d'analyse des séquences protéiques de PNRS en précisant les particularités des outils existants. Ensuite, je présente ma contribution à l'exploration du potentiel de synthèse de PNR à partir de séquences génomiques ou protéiques à travers ma participation à la mise au point d'un protocole d'analyses bio-informatiques et à l'annotation de plusieurs génomes. Dans une seconde partie, je commence par préciser les apports de la plate-forme Norine sur la compréhension de la diversité des peptides non-ribosomiques, complétés par une étude de la chimie de ces molécules. Ensuite, je présente les quelques bases de données et outils en relation avec ces peptides, qui sont développés par ailleurs. Puis, je présente la plate-forme Norine en exposant mes contributions et en proposant la modernisation du processus de collecte des données et l'évolution des fonctionnalités d'interrogation via les structures peptidiques. Je termine par la présentation d'une nouvelle perspective : la chémo-informatique dédiée aux peptides non-ribosomiques avec pour objectif la prédiction d'une ou plusieurs synthétases capables de produire un peptide ayant une activité cible.

Cette thèse s'organise en deux parties : une première partie s'intéresse aux mesures de similarité entre sommets d'un graphe, une seconde aux méthodes de clustering de graphe biparti. Une nouvelle mesure de similarité entre sommets basée sur des marches aléatoires en temps courts est introduite. Cette méthode a l'avantage, en particulier, d'être insensible à la densité du graphe. Il est ensuite proposé un large état de l'art des similarités entre sommets, ainsi qu'une comparaison expérimentale de ces différentes mesures. Cette première partie se poursuit par la proposition d'une méthode robuste de comparaison de graphes partageant le même ensemble de sommets. Cette mesure est mise en application pour comparer et fusionner des graphes de synonymie. Enfin une application d'aide à la construction de ressources lexicales est présentée. Elle consiste à proposer de nouvelles relations de synonymie à partir de l'ensemble des relations de synonymie déjà existantes. Dans une seconde partie, un parallèle entre l'analyse formelle de concepts et le clustering de graphe biparti est établi. Ce parallèle conduit à l'étude d'un cas particulier pour lequel une partition d’un des groupes de sommets d’un graphe biparti peut-être déterminée alors qu'il n'existe pas de partitionnement correspondant sur l’autre type de sommets. Une méthode simple qui répond à ce problème est proposée et évaluée. Enfin Kodex, un système de classification automatique des résultats d'une recherche d'information est présenté. Ce système est une application en RI des méthodes de clustering vues précédemment. Une évaluation sur une collection de deux millions de pages web montre les avantages de l'approche et permet en outre de mieux comprendre certaines différences entre méthodes de clustering. / This thesis is organized in two parts : the first part focuses on measures of similarity (or proximity) between vertices of a graph, the second part on clustering methods for bipartite graph. A new measure of similarity between vertices, based on short time random walks, is introduced. The main advantage of the method is that it is insensitive to the density of the graph. A broad state of the art of similarities between vertices is then proposed, as well as experimental comparisons of these measures. This is followed by the proposal of a robust method for comparing graphs sharing the same set of vertices. This measure is shown to be applicable to the comparison and merging of synonymy networks. Finally an application for the enrichment of lexical resources is presented. It consists in providing candidate synonyms on the basis of already existing links. In the second part, a parallel between formal concept analysis and clustering of bipartite graph is established. This parallel leads to the particular case where a partition of one of the vertex groups can be determined whereas there is no corresponding partition on the other group of vertices. A simple method that addresses this problem is proposed and evaluated. Finally, a system of automatic classification of search results (Kodex) is presented. This system is an application of previously seen clustering methods. An evaluation on a collection of two million web pages shows the benefits of the approach and also helps to understand some differences between clustering methods.

Cette thèse s'organise en deux parties : une première partie s'intéresse aux mesures de similarité (ou de proximité) définies entre les sommets d'un graphe, une seconde aux méthodes de clustering de graphe biparti. Une nouvelle mesure de similarité entre sommets basée sur des marches aléatoires en temps courts est introduite. Cette méthode a l'avantage, en particulier, d'être insensible à la densité du graphe. Il est ensuite proposé un large état de l'art des similarités entre sommets, ainsi qu'une comparaison expérimentale de ces différentes mesures. Cette première partie se poursuit par la proposition d'une méthode robuste de comparaison de graphes partageant le même ensemble de sommets. Cette méthode est mise en application pour comparer et fusionner des graphes de synonymie. Enfin une application d'aide à la construction de ressources lexicales est présentée. Elle consiste à proposer de nouvelles relations de synonymie à partir de l'ensemble des relations de synonymie déjà existantes. Dans une seconde partie, un parallèle entre l'analyse formelle de concepts et le clustering de graphe biparti est établi. Ce parallèle conduit à l'étude d'un cas particulier pour lequel une partition d'un des groupes de sommets d'un graphe biparti peut-être déterminée alors qu'il n'existe pas de partitionnement correspondant sur l'autre type de sommets. Une méthode simple qui répond à ce problème est proposée et évaluée. Enfin Kodex, un système de classification automatique des résultats d'une recherche d'information est présenté. Ce système est une application en RI des méthodes de clustering vues précédemment. Une évaluation sur une collection de deux millions de pages web montre les avantages de l'approche et permet en outre de mieux comprendre certaines différences entre méthodes de clustering.