Binary Diffing as a Network Alignment Problem
Différentiation Binaire en tant que Problème d’Alignement de Réseaux
Résumé
In this thesis, we address the problem of binary diffing, i.e. the problem of finding the best possible one-to-one correspondence between the functions of two programs in binary form. This problem is a major challenge in several fields of computer security since it automatically designates to an analyst the pieces of code that might have been previously analyzed among other programs. We propose a quite natural formulation of the binary diffing problem as a particular instance of a graph edit problem over the call graphs of the programs. Through this formulation, the quality of the function mapping is evaluated simultaneously with respect to both the function content similarity and the function calls consistency. We prove that this versatile formulation is in fact equivalent to the well studied network alignment problem, which enables us to leverage common optimization techniques. Following previous works, we propose a solving strategy based on max-product belief propagation, and introduce QBinDiff, a network alignment solver that outperforms other state-of-the-art methods in almost all instances. We finally show that our approach outperforms existing diffing tools, and that the matching strategy has more influence on the quality the solution than the measure of function similarity.
L'analyse statique de programme désigne la discipline consistant à analyser et prédire les différents comportements d’exécution possibles d'un programme sans même pouvoir observer son exécution. Elle représente un enjeu majeur en sécurité informatique, et comporte une grande variété d’applications telles que la détection de vulnérabilité, l'analyse de correctifs de code, la détection de logiciels malveillants, etc.
L'analyse statique d'un programme est la plupart du temps effectuée directement sur le code source du programme, car ce dernier inclue généralement une variété d'informations lisibles par l'homme, telles que des commentaires ou des noms de variables, ainsi que des concepts d'un haut niveau d'abstraction, tels que des structures de contrôle (control flow statements), ainsi que des définitions de fonctions ou de classes qui induisent une partition explicite du programme en unités fonctionnellement liées.
Cependant, il arrive que le programme ne soit disponible que sous la forme d'un exécutable binaire. Dans ce cas, l'analyse doit être conduite directement sur le code machine, ce qui est souvent considérée comme beaucoup plus difficile car ce dernier ne comprend pas le même niveau d'abstraction que les langages de programmation. En pratique, de nombreuses informations précieuses, telles que le type des variables, les adresses de destinations des sauts ou encore la délimitation des fonctions sont perdues lors de la compilation.
La conception de méthodes automatisées pour traiter complètement ou partiellement l'analyse d'un code binaire est une problème complexe. En fait, d'après le théorème de Rice, le problème consistant à extraire n'importe quelle propriété (non-triviale) d'un programme arbitraire est mathématiquement indécidable. Par conséquent, il est impossible de concevoir un algorithme unique capable d'effectuer une analyse parfaite de tous les programmes possibles. En pratique, de nombreux outils basés sur des approximations ont été proposés. Cependant, après plusieurs décennies de recherche, de nombreux problèmes nécessitent toujours une expertise humaine.
Les programmes informatiques non-triviaux sont rarement conçus de bout en bout en une seule fois. La plupart du temps, ils résultent d'un processus incrémental où des parties sont ajoutées, supprimées ou modifiées afin d'inclure de nouvelles fonctionnalités ou bien de corriger des comportements indésirables. Ainsi, un même programme existe souvent dans différentes versions, correspondant à ces modifications successives. En outre, la plupart des logiciels incluent généralement des bibliothèques externes afin de gérer les tâches auxiliaires du programme, telles que l'interface système, le formatage des données ou encore la gestion de la sécurité. Lorsqu’elles sont liées statiquement, le code de ces bibliothèques est directement inséré au sein du programme. Par conséquent, différents programmes peuvent contenir des parties similaires, consistant en du code dupliqué ou bien corrigé, ou en des dépendances de logiciels tierces.
Cette relation entre les programmes peut être habilement exploitée afin de faciliter leur analyse. Par exemple, une fonctionnalité particulièrement utile pour un analyste consisterait à retrouver les différences entre un programme précédemment analysé et celui en cours d'investigation. Lorsque ces deux programmes sont des exécutables binaires, ce problème est connu sous le nom de problème de différentiation binaire (binary diffing problem).
En pratique, ce problème est généralement abordé à travers son corollaire qui consiste cette fois à trouver la meilleures correspondance possibles entre les différentes parties des deux binaires. La correspondance obtenue permet alors simplement d'identifier les différences entre les deux programmes.
Il existe de nombreuses approches possibles pour rechercher des morceaux de code similaires dans deux binaires. À titre d'illustration, considérons l'analogie suivante : supposons que nous voulions retrouver les parties similaires au sein de deux textes arbitraires. L'approche naïve consistant à trouver une correspondance entre des chaînes de caractères semblerait inutile à l'analyste car il serait en fait incapable d'en déduire un sens. De même, aligner les mots entre eux fournirait peut-être un peu d'informations sur certaines occurrences rares, mais ne contiendrait aucune information contextuelle commune. À l'inverse, l'alignement d'entités significatives de plus haut niveau, comme des phrases ou des paragraphes, pourrait mettre en évidence des relations précieuses pour le lecteur et révéler la signification commune des deux textes.
Afin de fournir des informations utiles à un analyste, le problème de la différenciation binaire doit donc se concentrer sur la mise en relation de morceaux de code ayant une fonctionnalité unifiée. Différents niveaux de granularité ont ainsi été proposés, principalement en fonction du cas d'utilisation sous-jacent, mais aussi implicitement induits par l'approche utilisée pour calculer l’alignement. Par exemple, certains travaux visent à retrouver les différences au niveau des bloc de base (basic blocks). A l'inverse, d'autres méthodes recherchent des bibliothèques communes ou des dépendances logiciels, et considèrent le problème à une échelle plus élevée. Dans cette thèse, nous abordons le problème de la recherche de la meilleure correspondance une-à-une possible entre les fonctions respectives des deux programmes.
L'approche directe pour obtenir une telle correspondance consiste à mesurer la similarité entre chaque paire de fonctions prises dans les deux binaires, et à calculer l'appariement (assignment) ayant le score de similarité global maximal. Si l'on considère que le score de similarité entre deux fonctions représente la probabilité que la première ait été modifiée en la seconde, l'alignement de fonctions qui en résulte peut être considérée comme la plus probable.
En analyse statique, on distingue généralement la représentation disponible du programme, appelée syntaxe, et son comportement d'exécution attendu, ou sémantique. Un problème fondamental à la comparaison statique de morceaux de code est que le seul recensement de leurs différences syntaxiques ne suffit pas à évaluer la similarité de leur comportement lors de l’exécution. En outre, bien que mesurer la similarité syntaxique puisse être relativement facile, la caractérisation complète de la sémantique d'une fonction est un problème complexe, et les heuristiques existantes ont tendance à être très coûteuses en termes de calcul. Par conséquent, toute mesure de similarité de fonctions comprend nécessairement un certain degré d'approximation et ne peut donc être considérée que comme partiellement fiable.
Afin de surmonter cette difficulté, la plupart des approches actuelles proposent d'améliorer la pertinence de la correspondance de fonctions en exploitant également leur contexte au sein du programme, et en particulier la façon dont les fonctions s'appellent entre elles. Ces méthodes ne considèrent donc pas seulement la similarité des fonctions lors de leur association, mais aussi la cohérence de leur structure d'appel. Pour ce faire, elles se représente généralement le programme sous la forme d'un graphe, appelé graphe d'appel (call graph), où les nœuds correspondent aux fonctions tandis les arêtes désignent les différents appels entre elles. Par conséquent, le problème originel d'appariement de fonctions devient un problème d'alignement de graphes, ou l'on recherche une correspondance entre les nœuds basée à la fois sur la similarité des nœuds (contenu des fonctions) et la similarité des arêtes (cohérence des appels de fonctions).
Dans cette thèse, nous proposons une formulation générale du problème de différentiation binaire, sous la forme d'un problème d'édition de graphe : étant donné un ensemble d'opérations d'édition possibles ainsi que leur coût respectif sur les nœuds et les arêtes, nous nous proposons de trouver une transformation (presque) optimale du graphe d'appel du programme $A$ en graphe d'appel du programme $B$.
Cette formulation correspond à une généralisation du problème de la distance d'édition de graphes (graph edit distance problem), où au lieu de calculer directement le score de dissimilarité (distance) entre les deux graphes, on recherche le chemin d'édition qui induit ce score. Il s'agit sans doute de la formulation la plus naturelle du problème de différentiation binaire puisqu'elle décrit précisément les différentes modifications ayant eu lieu entre les deux programmes. De plus, le problème de la distance d'édition de graphes est connu pour être très polyvalent, car il dépend principalement de la définition donnée des coûts des différentes opérations d'édition. Cela offre une certaine souplesse à l'analyste qui peut ainsi configurer le problème en fonction de considérations sous-jacentes particulières.
Malheureusement, la résolution du problème de la distance d'édition des graphes, c'est-à-dire la recherche de la séquence optimale d'opérations d'édition qui transforme le graphe $A$ en $B$, est connue pour être NP-difficile (NP-hard). En pratique, il n'existe actuellement aucune méthode capable de calculer en un temps raisonnable un chemin d'édition optimal pour des graphes composés de plus d'une centaine de nœuds. Par conséquent, notre approche repose nécessairement sur des solutions approximatives.
Alors que la plupart des solveurs traditionnels de distance d'édition de graphes sont basés sur des algorithmes combinatoires et énumèrent l'espace des solutions, plusieurs méthodes approximatives récentes proposent plutôt de reformuler le problème en un programme d'optimisation sous contraintes afin de bénéficier des techniques d'optimisation usuelles. Suivant cette idée, nous reformulons le problème de différentiation binaire en un problème d'alignement de réseaux (network alignment problem). En fait, nous prouvons que, moyennant de faibles hypothèses, les deux problèmes sont équivalents. Bien que le problème d'alignement de réseaux appartienne à la même classe de complexité que le problème de distance d'édition de graphes, ce problème d'optimisation quadratique en nombres entiers a été largement étudié depuis des décennies, et plusieurs méthodes d'approximation efficaces ont été proposées.
Parmi les meilleures approches existantes, se trouve NetAlign, un modèle de transmission de messages basé sur l'algorithme du max-produit (max-product algorithm). Dans cette thèse, nous reprenons ce modèle et proposons quelques modifications pour améliorer ses performances ainsi que pour considérablement réduire son temps de calcul et sa consommation de la mémoire. Nous avons dénommé notre algorithme QBinDiff.
Afin d'évaluer correctement l'approche que nous proposons, nous devons réaliser plusieurs séries d'expériences successives.
Nous devons d'abord comparer notre algorithme d'alignement de réseaux aux autres méthodes de l'état de l'art. Cela peut être fait en soumettant exactement les mêmes instances de problème à tous les solveurs et en comparant les scores d'alignement obtenus. Nous effectuons de telles comparaisons sur trois ensembles de problèmes étalons, composés de nombreuses instances d'alignement de graphes différents, partageant des propriétés similaires à celles que l'on retrouve habituellement dans les problèmes de différentiation. Nos expériences montrent que QBinDiff surpasse les autres méthodes existantes dans presque toutes les configurations et, par conséquent, apparaît comme l'un des meilleurs algorithmes connus pour aligner ce genre de graphes.
Cependant, le calcul de bonnes solutions d'alignement ne fournit aucune garantie sur la pertinence de ces correspondances de fonctions qu regard du problème de différentiation binaire. En effet, les solutions optimales au problème de différentiation pourraient en fait s'avérer très éloignées des solutions optimales de notre formulation d'édition de graphes.
Nous devons donc conduire une autre série d'expériences afin, cette fois, d'évaluer notre approche en tant que méthode de différenciation binaire et de la comparer aux outils existants au regard de scores de précision. Pour réaliser de telles expériences, il faut disposer d'une collection de problème pour lesquelles les appariements optimaux des fonctions sont connus. La disponibilité de ces collections d'instances étalons fait cruellement défaut au sein de la littérature. Nous avons donc conçu notre propre jeu de problèmes, composé de plus de 50 binaires et de plus de 800 instances de différentiation, et l'avons mis à la disposition de la communauté des chercheurs. Les résultats globaux montrent que notre stratégie d'alignement de réseau surpasse les autres approches existantes et suggèrent que notre formulation est très adaptée au problème du différentiation.
Enfin, on peut toujours affirmer que nos résultats dépendent des scores de similarité des nœuds et des arrêtes. En effet, en prenant une médiocre mesure de similarité des fonctions, il ne serait pas surprenant que notre stratégie d'appariement équilibré fournisse de meilleures solutions que celle basée uniquement sur les scores de similarité des nœuds.
Par conséquent, nous avons reproduit nos expériences avec différentes mesures de similarité de fonction à l'état de l'art. Nos résultats suggèrent que la stratégie d'appariement a plus d'influence que les mesures de similarité choisies sur la qualité des solutions. Plus intéressant encore, il apparaît que l'utilisation de mesures de similarité sémantique sophistiquées n'améliore généralement pas la précision de l'assignation et tend même à la détériorer dans certains cas.
Outre le fait que notre formulation du problème de différentiation binaires à travers un problème de la distance d'édition des graphes est naturelle et qu'elle donne lieu à des appariements plus précis, elle fournit également une métrique appropriée pour mesurer la similarité à l'échelle du programme. En effet, toute correspondance de fonctions induit une distance d'édition (approximée) entre les deux programmes. Par conséquent, notre approche pourrait également être utilisée dans une variété d'analyses basées sur des métriques au niveau des programmes, comme la recherche de bibliothèques, du lignage de programmes, etc.
Origine : Fichiers produits par l'(les) auteur(s)