Keywords: Binary Diffing, Binary Code Analysis, Graph Edit Distance, Network Alignment, Belief Propagation

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.

Résumé

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, viii 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 ix 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 noeuds 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 noeuds basée à la fois sur la similarité des noeuds (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 noeuds 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 noeuds. 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 x 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 noeuds 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 noeuds.

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 xi 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.

1

Introduction

Static program analysis is the process of analyzing and predicting the possible execution behaviors and outcomes of a program without actually executing it [START_REF] Nielson | Principles of Program Analysis[END_REF]. It is a cornerstone of computer security, and has a wide variety of applications such as vulnerability detection, patch analysis, malware detection, software clone detection, etc. [START_REF] Haq | A Survey of Binary Code Similarity[END_REF] Static program analysis is most of the time performed on the source code of the program since it usually includes human-readable information such as comments or variable names, but also high-level concepts such as control-flow statements as well as function or class definitions which induce an explicit partition of the program into functionally related units [START_REF] Balakrishnan | WYSINWYX: What you see is not what you eXecute[END_REF].

Sometimes, however, the program is only available as a binary executable. In this case, the analysis must be conducted directly on the machine code, and is often considered much more difficult since it does not include the same level of abstraction as programming languages. In practice, many useful information such as variable types, branching target addresses or function boundaries have been lost during the compilation [START_REF] Kinder | Static Analysis of x86 Executables[END_REF].

The design of automated methods to completely or partially process binary code analysis is a difficult task. In fact, it is known from Rice's theorem that any interesting property about the execution behavior of an arbitrary program is undecidable [START_REF] Rogers | Theory of recursive functions and effective computability[END_REF]. As a consequence, there can not be any general algorithm that performs an analysis task exactly on every possible program. In practice, multiple approximate tools have been proposed [START_REF] Chess | Static Analysis for Security[END_REF][START_REF] Chess | Secure programming with static analysis[END_REF]. However, after decades of research, many problems still require human expertise.

Non-trivial computer programs are rarely implemented all at once. Most of the time, they result from an incremental process where parts are added, removed or modified in order to include new features or fix undesired behaviors. Consequently, a same program often exists under different versions corresponding to these successive modifications. Furthermore, most software usually include external libraries in order to handle auxiliary tasks of the program such as system interface, data formatting or security management. When they are statically linked, the code of these modules is directly inserted into the program. As a consequence, different programs may contain similar parts, consisting in duplicated or patched code, or in third-party modular dependencies. This relationship between programs can be leveraged in order to ease their analysis. For instance, a particularly useful feature for an analyst would consist in retrieving the differences between a previously analyzed program and the one currently under investigation. When the two programs are binary executables, this problem is known as the binary diffing problem [START_REF] Baker | Compressing differences of executable code[END_REF].

In practice, the binary diffing problem is usually addressed through its corollary formulation which consists in matching the similar parts in both binaries. Given the resulting correspondence, it is then straightforward to identify the differences between the two programs.

There may be many approaches to search for similar pieces of code in two binaries. As an illustration, consider the following analogy: suppose we are willing to retrieve the similar and different parts in two arbitrary texts. The naive approach consisting in finding a correspondence between chains of characters in both texts would appear useless to the analyst, as he would actually be unable to read it. Similarly, mapping words together would perhaps provide few information about some rare occurrences, but would not enclose any common contextual information. Conversely, the alignment of higher level, meaningful entities, such as phrases or paragraphs, could highlight precious relationships to the reader and reveal the common significations of both texts.

In order to provide useful information to an analyst, the binary diffing problem should thus focus on mapping pieces of code with unified functionality. Different levels of granularity have been proposed mostly depending on the underlying use case but also implicitly induced by the solving approach [START_REF] Haq | A Survey of Binary Code Similarity[END_REF]. For instance, some works aim at retrieving fine-grained differences at a basic-block level [START_REF] Zuo | Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs[END_REF]. Conversely, other researches are looking for common libraries or dependencies, and consider the problem at a higher scale [START_REF] Backes | Reliable Third-Party Library Detection in Android and its Security Applications[END_REF]. In this work, we address the problem of finding the best possible one-to-one correspondence between the respective functions of the two programs.

The straightforward approach to obtain such mapping consists in measuring the similarity between every pair of functions taken from both binaries, and to compute the one-to-one assignment with maximum overall similarity score [START_REF] Liu | $\alpha$ Diff: cross-version binary code similarity detection with DNN[END_REF]. If we consider that the similarity score between two functions represents the probability that the first one has been modified into the second one, the resulting function correspondence can be viewed as the most likely one.

In static program analysis, we usually distinguish the available code representation of a program, known as syntax, and its expected execution behavior, or semantic [START_REF] Nielson | Principles of Program Analysis[END_REF]. A fundamental problem in statically comparing pieces of code is that the retrieval of their syntactic differences may be insufficient to assess the similarity of their respective behavior when executed [START_REF] Haq | A Survey of Binary Code Similarity[END_REF]. Furthermore, though measuring syntactic similarity can be relatively easy, performing a complete characterization of the semantic of a function is a complex problem, and practical heuristics tend to be computationally expensive. As a consequence, any measure of function similarity necessarily includes some levels of approximation and can thus only be considered as partially reliable.

In order to overcome this limitation, most current binary diffing approaches propose to improve the assignment accuracy by also leveraging the context of the function within the program, and in particular, the way the functions call each others [START_REF] Dullien | Graph-based comparison of executable Objects[END_REF][START_REF] Kostakis | Improved call graph comparison using simulated annealing[END_REF]. These methods thus not only consider the function similarity during the mapping but also the consistency of their call structure. To do so, they usually refer to a graph representation of the program, known as call graph [START_REF] Callahan | Constructing the Procedure Call Multigraph[END_REF], where the nodes correspond to the functions and the edges encode the different calls among them. As a result, the naive function assignment problem becomes a graph matching problem that searches for a node correspondence based on both the similarity of nodes (function content) and the similarity of edges (function calls consistency).

In this work, we propose a general graph edit formulation of the binary diffing problem: given a set of possible edit operations and respective costs on both the nodes and edges, we find an (almost) optimal transformation of the call graph of program A into the call graph of program B [START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications[END_REF].

Such formulation corresponds to a generalization of the graph edit distance problem, where instead of directly computing the score of dissimilarity (distance) between both graphs, we search for the actual edit path that induces this score. It is arguably the most natural formulation of the binary diffing problem since it precisely describes the different modifications that occur between the two programs. Moreover, the graph edit distance problem is known to be very versatile, as it mostly depends on the given definition of the edit operation costs. This provides flexibility to the analyst in order to setup the problem according to particular underlying considerations.

Unfortunately, solving the graph edit distance problem, i.e. finding the optimal sequence of edit operations that transforms graph A into B, is known to be NP-hard [START_REF] Lin | Hardness of Approximating Graph Transformation Problem[END_REF]. In practice, no existing method can compute in reasonable time an optimal edit path for graphs made of more than a hundred nodes. Therefore, our approach would necessarily rely on approximate solutions.

While most traditional exact graph edit distance solvers are based on combinatorial algorithms and enumerate the solution space [START_REF] Fankhauser | Speeding up graph edit distance computation through fast bipartite matching[END_REF], several recent approximate methods propose instead to reformulate the problem into constraint optimization programs in order to leverage common optimization techniques [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Bougleux | Graph edit distance as a quadratic assignment problem[END_REF]. Following these insights, we reformulate the binary diffing problem into a network alignment problem. In fact, we prove that under minor conditions both problems are equivalent. Though the network alignment problem belongs to the same complexity class as the graph edit distance problem, this quadratic integer program has been extensively studied for decades, and several efficient approximate methods have been proposed [START_REF] Burkard | Quadratic assignment problems[END_REF].

Amongst the current best existing approaches is NetAlign, a message passing framework introduced by [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF] based on the max-product algorithm [START_REF] Loeliger | An introduction to factor graphs[END_REF]. In our work, we leverage this model and propose some modifications to improve its performances as well as to reduce its required computational time and memory usage. We named our algorithm QBinDiff.

In order to properly evaluate our proposed approach, we must perform several successive sets of experiments.

We must first compare our proposed network alignment algorithm to other state-of-the-art methods. This may be done by submitting the exact same problem instances to all solvers and by comparing the resulting alignment scores. We perform such comparisons on three different benchmarks, made of many different graph matching instances, sharing similar properties with the ones usually found in diffing problems. Our experiments show that QBinDiff outperforms other existing methods in almost all configurations and, as such, is one of the best-known algorithms to align such graphs.

Unfortunately, computing high-quality alignment solutions does not provide any guaranty about the relevance of these function correspondences in terms of binary diffing. Indeed, optimal solutions to the binary diffing problem could turn out to be far from optimal solutions of our graph edit formulation.

We must thus conduct another series of experiments in order to evaluate our approach as a binary diffing method and compare to existing tools with respect to accuracy metrics. Performing such experiments requires a collection of binary diffing instances for which the actual optimal function mappings are known. As readily available diffing benchmarks are crucially missing in the literature, we designed our own, made of more than 50 binaries and over 800 diffing instances, and released it to the research community. Overall results point out that our network alignment matching strategy outperforms other existing approaches and suggest that our formulation is very well suited to address the diffing problem.

Finally, one may still argue that our results depend on the given node and edge similarity scores. Indeed, given a poor function similarity measure, it would not be surprising that our balanced matching strategy provides better assignments than the one solely based on the node similarity scores.

Therefore, we reproduce our experiments with different state-of-the-art function similarity measures. Our results highlight that the matching strategy has more influence than the chosen similarity measures on the quality of the solutions. More interestingly, it appears that using sophisticated semantic similarity measures does not generally improve the assignment accuracy and tends to even worsen it in some cases.

Contributions

In summary, the contributions of this thesis are:

We introduce a new formulation of the binary diffing problem as a graph edit distance problem and show that this formulation is equivalent to the network alignment problem.

We present an efficient network alignment algorithm, named QBinDiff, based on max-product belief propagation, and show that it outperforms other state-of-the-art solvers.

We release a new binary diffing benchmark data set consisting in more than 60 binaries and over 800 manually extracted ground truth correspondences.

We propose an extensive evaluation of our approach by comparing to other common matching methods, as well as other state-of-the-art function similarity measures.

The rest of this thesis is organized as follows. In Chapter 2, we introduce in more details the context of static binary analysis and the common formulations of the binary diffing problem. We then review some existing solutions. We properly formalize the problem in Chapter 3 and prove that it actually consists in an integer quadratic optimization problem. In Chapter 4, we present a maximization algorithm able to efficiently find an approximate solution to the problem. We evaluate our model as a network alignment solver in Chapter 5 and compare its performances to some of the best existing approaches. In Chapter 6, we provide an evaluation of our proposed solution as a binary diffing tool.

We also analyze its relevance using different measures of function similarity. We discuss our method and findings in Chapter 7, in order to finally conclude.

Chapter 2

Background

In this chapter, we first present the overall context of static binary analysis and introduce several notions as well as common program representations. We then discuss in more details the problem of binary diffing and review some of the existing work.

Static binary analysis

The static analysis of programs in binary form, or static binary analysis, consists in analyzing and predicting the possible behaviors of a binary program without executing it [START_REF] Nielson | Principles of Program Analysis[END_REF]. It thus requires to retrieve most of the program properties and functionalities solely based on its available binary representation. In this section, we give a short introduction of what is a binary executable and then present some common analytical representations.

Binary executable

A binary executable is a file designed to order a machine to perform desired tasks. It basically consists in a very long sequence of zeros and ones that corresponds to machine code and provides to the computer information regarding the program as well as the instructions that must be read and executed.

Though it may be directly implemented by hands, a binary executable typically results from an automated translation process that converts humanreadable source code into low-level machine code (see Figure 2.1). This process usually involves several successive transformation steps such as compilation, assembling and linking [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF].

Compilation

The compilation provides a formal translation of a source code into a semantically equivalent assembly code. A common compilation process first converts the source code into a low-level intermediate representation, then performs multiple optimization passes that reformulate portions of the current representation into equivalent but more efficient implementations. Finally, it translates the resulting code into the assembly language of the desired computer architecture.

Assembling

The assembly code is then assembled in order to produce object code i.e. machine code that is not directly executable by a computer but is designed to be reusable. The assembler converts assembly mnemonics into binary instructions and resolves the symbols i.e. turns human-readable names such as function denomination or labels into their corresponding relative addresses. Moreover, it partitions the code into different segments in order to distinguish the portions of code that consist in executable code, constants and variables data, header, etc. It finally includes several metadata sections that will be used during the linking step.

Linking

Modern computer programs are typically composed of several pieces of code called modules. These modules may arise from an efficient partitioning from the developer, as well as from the usage of third-party implementations such as libraries or APIs. During the compilation, each module is processed separately and results in a single object file. The linking step aggregates these object files in order to produce a unified binary executable. It properly relocates the memory addresses of the different modules in order to prevent overlaps and resolves the function calls among them.

Information loss

Unfortunately, this automated translation process from source to machine code induces some information loss that may harden the program analysis (see Figure 2.1).

In practice, most of the interesting features of the program are lost during the compilation step, i.e. during the conversion of the source code into assembly code [START_REF] Nielson | Principles of Program Analysis[END_REF]. In particular, the high-level concepts provided by the programming language, such as variable declaration, type specification or function and class implementation are diluted. Moreover, compiler optimizations may consist in complex patterns that very efficiently exploit processor features such as the number of cycles per instruction or register state side effects. Therefore, these optimizations may produce an assembly code syntactically quite different from the one that would have resulted from a non-optimized compilation. Finally, since they are of no interest to the computer during the execution, almost all human-readable symbols such as function or variable names, developer comments or debugging information are often removed, or stripped. Stripping an executable reduces its size and provides some limited protection against reverse engineering in hiding implementation details.

Furthermore, the translation of assembly code into machine code also causes information loss. Indeed, machine code only targets computer comprehension, and is designed to be read during an execution process, where instructions are fetched one after the other through their address locations. Therefore, it does not require a proper layout and usually consists in a simple concatenation of all its binary content, code and data, resulting in a long sequence of bytes. As a consequence, the actual delimitation of instructions, as well as the boundaries of basic blocks or functions are not available. The retrieval of these information is a challenging problem that enables one to leverage a program rendering close to its original assembly representation [START_REF] Kinder | Static Analysis of x86 Executables[END_REF].

Program disassembly

To be readable by a human expert, even at a low level of abstraction, a binary executable must be disassembled, i.e. translated from machine code into assembly code. Each binary instruction is thus decoded and expressed as a mnemonic specifying the nature of the machine operation, followed by zero or more operands which may refer to registers, memory addresses or literal data [START_REF] Eagle | The IDA Pro Book: The Unofficial Guide to the World's Most Popular Disassembler[END_REF]. Therefore, the resulting assembly code is expected to be quite close to the one produced by the compilation of the original source code, though all variable and function names, as well as all comments would still be missing (see Figure 2.1). Note that different computer processors might have different machine languages (instruction set architectures) and thus different assembly languages. In this work, we only consider programs designed to run on x86-64 processors, though similar methods should provide comparable results on different architectures. The process of disassembly is a challenging problem that requires to deduce from the raw binary code the correct delimitation of each machine code instruction. In fact, this problem consists in retrieving the starting bit of each instruction, or, in other words, to resolve the potential target addresses of each branching instruction [START_REF] Meng | Binary code is not easy[END_REF].

In practice, we usually distinguish two disassembly strategies [START_REF] Wartell | Shingled Graph Disassembly: Finding the Undecideable Path[END_REF]. The first one, called linear-sweep, basically starts at the program entry point and translates each instruction one after the other until it reaches the end. The major drawback of such approach is that the sliding window of byte pattern to decode is likely to misalign after few instructions. This happens, for instance, when data lies between pieces of code and is interpreted as such, in the presence of padding bytes (nop) or of optimized patterns of overlapping instructions. In order to overcome this issue, another disassembly method, called recursive traversal, consists in decoding the instructions in the order they are expected to be executed, i.e. following the potential jump target addresses [START_REF] Schwarz | Disassembly of Executable Code Revisited[END_REF]. Such a strategy prevents linear-sweep misalignments and thus only translates patterns of bytes that actually correspond to machine code instructions. However, it does not guarantee to process all program bytes since some parts may never be reached during the traversal. Though several disassemblers are currently available (e.g. Radare21 , Binary Ninja2 , Ghidra3 ) our work only uses the most popular one, IDA Pro4 , which uses a recursive traversal strategy [START_REF] Eagle | The IDA Pro Book: The Unofficial Guide to the World's Most Popular Disassembler[END_REF].

Program representations

Once disassembled, a binary executable can be represented as a series of assembly instructions. However, one can leverage other graphical representations of the program in order to best exhibit its potential behavior when executed (see Figure 2.2).

Control-flow graph

During its execution, most of the program instructions are executed sequentially, following the order they were arranged in. However, programs typically include branching instructions that order the computer to jump at a particular position of the program and to carry on the execution from there [START_REF] Knuth | The Art of Computer Programming: Fascicles 0-4. 1st[END_REF].

We usually distinguish two types of branching instructions: conditional or unconditional branches, and direct or indirect branches. Unconditional branches always order the computer to jump at the specified address whereas conditional jumps may simply proceed to the next instruction if the condition is not fulfilled. For instance, a function call in a source code will result in an unconditional jump instruction which target address corresponds to the entry point of the function in the binary executable. On the contrary, any if-else or loop statement would probably induce a pattern of conditional branch instructions in the program. Direct branches admit a unique target address whereas indirect branch destinations can be specified at run-time.

In general, both the condition status of conditional jumps and the actual target addresses of indirect branches can only be assessed on the fly during the program execution. Moreover, they may be subject to arbitrary input parameters or even randomness. Therefore, the control flow of a program, i.e. the sequence of instructions that will actually be executed at run-time, remains mostly unknown during a static analysis [START_REF] Liu | Binary Code Analysis[END_REF].

In order to consider its different possible execution behaviors, a program can be represented as a set of all its possible execution paths, i.e. all its possible control flows. Such representation consists in a directed graph of instructions where every non-branching instruction simply points at its successor, whereas every jump instruction points at all its potential targeted instructions (in addition to its successor in the case of a conditional jump). The graph can then be simplified by gathering the consecutive instructions into so-called basic blocks. This program representation is usually called a control flow graph (CFG) [START_REF] Allen | Control flow analysis[END_REF].

The partition of a program into related basic blocks is semantically relevant since all constitutive instructions of a basic block will necessarily be executed in their exact order. Moreover, unlike a sequential representation, this graph structure is particularly convenient to deal with compilation-based instruction reordering, as well as with address relocation resulting from linking step, since the different blocks of instructions become position-independent along the program and are then only related by the jumps among them [START_REF] Khedker | Data Flow Analysis: Theory and Practice[END_REF].

Unfortunately, the retrieval of such a graph often results in an approximation of the set of all possible execution paths of the program [START_REF] Meng | Binary code is not easy[END_REF]. First, some of the walks in the graph might be subject to a combination of branching conditions that are actually impossible to fulfill, though most modern compiler optimizations aim at removing unreachable (dead) code. Moreover, the retrieval of all possible target addresses of each indirect branching statement is a complex problem, known to be undecidable. In some cases, some addresses might be determined using heuristics such as alias analysis, or obtained from additional information such as jump tables (records of common target addresses). The rest of the time, the jump statement is simply ignored [START_REF] Kinder | Static Analysis of x86 Executables[END_REF].

Note that both the disassembly and the control flow construction address the same problem that consists in statically resolving the target addresses of the branch statements. In fact, both processes are performed at the same time, successively decoding machine code instruction and, when this later is a jump, inferring its target location.

Call graph

The representation of a binary executable as a graph not only deals with uncertainties about its execution behavior. It may also be arguably thought as an algorithmic view of the program. Indeed, any possible walk in this graph can be considered a possible execution path specially designed by the developer to perform a particular task. Following this insight, the structure of the control flow graph could be leveraged in order to retrieve higher-level program abstractions and hence highlight the potential intent of the developer. In particular, an instructive representation consists in a partition of the controlflow graph according to the program subroutines only. The resulting directed attributed graph is composed of nodes denoting the different functions and edges registering the calls among them. Such representation is known as call graph (CG) [START_REF] Callahan | Constructing the Procedure Call Multigraph[END_REF]. Notice that in a CG, each node can be itself represented as an independent graph of basic blocks, and each basic block consists in a sequence of assembly instructions (see Figure 2.2).

Usually, the retrieval of the function boundaries immediately follows the call procedure layout, i.e. the conventional instruction patterns that enclose the core of each function. However, such partitioning may produce an inexact call graph in some more complex cases such as non-returning functions or tails calls, as well as non-contiguous or code sharing functions [START_REF] Ryder | Constructing the Call Graph of a Program[END_REF]. Here again, heuristics can be used to provide the best possible call graph, though no guarantee can be given on its reliability. In particular, some languages, such as object-oriented languages, may have an extended use of polymorphism. In this case, the actual function to be executed is often resolved at run-time, through a dynamic dispatch. As for the jump tables in CFG construction, such calls would probably result in an over-approximation of the CG and all the homonymous functions would be considered potential candidates [START_REF] Grove | Call graph construction in object-oriented languages[END_REF].

Binary Diffing

The idea of binary diffing, is to provide an automatic comparison of two programs based on their available machine code representation. It is a precious feature for analysts and reverse engineers since it quickly enables one to leverage knowledge gained during the investigation of previous binaries (see Figure 2.3).

The binary diffing problem consists in retrieving and aligning the pieces of code common to two binary executables. It generally results in a one-to-one correspondence, or mapping, between the aligned parts and a set of unmatched elements for each program.

Such formulation requires the formal specification of the code granularity (what should be compared), the comparison criteria (how it should be compared) and the mapping criteria (how it should be aligned). The different proposed definitions mostly depend on the underlying use-case of the analysis. In the rest of this chapter, we review some of the most common approaches.

Binary code granularity

As it ultimately targets human comprehension, the binary diffing problem should result in mappings that provide valuable information to the analyst. Therefore, it should be performed on a code representation with a level of abstraction close to the analysis. Usual comparisons focus on functionally related pieces of code such as functions, traces, basic blocks or instructions. For more details about the different code granularity used in the literature, we refer the reader to [START_REF] Haq | A Survey of Binary Code Similarity[END_REF].

Function

Most approaches focus on mapping functions [START_REF] Bourquin | BinSlayer: accurate comparison of binary executables[END_REF][START_REF] Lee | Function matching-based binary-level software similarity calculation[END_REF][START_REF] Liu | $\alpha$ Diff: cross-version binary code similarity detection with DNN[END_REF][START_REF] Flake | Structural comparison of executable objects[END_REF][START_REF] Xu | SPAIN: security patch analysis for binaries towards understanding the pain and pills[END_REF]. Figure 2.3: Illustration of the binary diffing problem. Given any two binaries A and B and their call graph representation G A and G B , the binary diffing problem consists in finding the best correspondence between the functions i of A and those i of B (black arrows). Such mapping provides useful information to an analyst. In this figure, green dots and lines represent functions and calls that remained identical from a program to the other, and thus correspond to duplicated code. Blue (resp. red) elements represent inserted (resp. deleted) items, and may be considered as added (resp. removed) functionalities. Yellow dots record matched functions which content has been modified (substituted). They may thus indicate the functions that have been patched during the release. Furthermore, any alignment characterizes an edit-path between both binaries, and therefore induces a score of similarity.

The partition of a program through its call graph is a natural granularity for an analyst and is relatively robust to different compilation schemes. Moreover, this granularity enables one to efficiently leverage the program dependency on external functions such as those imported from libraries. These functions are easy to match, and provide interesting information to carry on the rest of the diffing. However, functions often consist in complex pieces of code, and their comparison may require quite sophisticated (and approximate) measures of similarity [START_REF] Liu | $\alpha$ Diff: cross-version binary code similarity detection with DNN[END_REF].

Basic block

Some methods propose to align the basic blocks [START_REF] Duan | DeepBinDiff: Learning Program-Wide Code Representations for Binary Diffing[END_REF][START_REF] Luo | Semantics-based obfuscation-resilient binary code similarity comparison with applications to software plagiarism detection[END_REF][START_REF] Zuo | Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs[END_REF][START_REF] Ming | iBinHunt: binary hunting with inter-procedural control flow[END_REF]. The main interest of such granularity is that it enables one to use very precise measures of code similarity. However, it requires the comparison of a much larger number of elements especially if the matching approach requires to compute all the pairwise similarity scores. Moreover, the structure of code is quite sensitive to compilation optimizations and can thus be leveraged with less confidence [START_REF] Ng | Expose: Discovering Potential Binary Code Re-use[END_REF].

Trace

Between functions and basic blocks, lies the trace granularity [START_REF] Kargén | Towards robust instruction-level trace alignment of binary code[END_REF][START_REF] Ming | BinSim: trace-based semantic binary diffing via system call sliced segment equivalence checking[END_REF]. The idea consists in comparing sequences of basic blocks that are likely to be executed in a row. A typical application is to represent a function through one or several traces of its constitutive basic blocks. Such an approach allows to use the basic block measure of similarity while limiting the number of elements to be compared. However, the enumeration of all possible traces of a piece of code rises exponentially with its complexity. Therefore, this granularity requires to compare code with a possibly very limited subset of its possible behaviors. In the literature, other names have been given to traces, such as tracelets [START_REF] David | Tracelet-based code search in executables[END_REF], strands [START_REF] David | Statistical similarity of binaries[END_REF] or juices [START_REF] Lakhotia | Fast location of similar code fragments using semantic 'juice[END_REF].

Instruction

Finally, binary diffing can be performed at an instruction level of granularity [START_REF] Baker | Compressing differences of executable code[END_REF][START_REF] Saebjørnsen | Detecting code clones in binary executables[END_REF]. Such granularity is arguably the most convenient for an analyst since it corresponds to the granularity at which code is usually read. Yet, it is rarely used as such. Indeed, the purpose of an instruction within a program usually depends on its surrounding context, and in particular on the instructions that have just been previously executed. Moreover, several syntactically quite different instructions can have the exact same semantic depending on the status of their operands. Therefore, usual binary diffing formulations favor to retrieve meaningful patterns of consecutive instructions, over a one-to-one correspondence disseminated all along both programs. However, in order to handle instruction reordering, binary diffing should not restrict to aligning programs as immutable sequences of instructions, and thus usually leverage a graph representation such as the CFG.

Hierarchical diffing

For the sake of readability, common binary diffing tools display the resulting diffing correspondence at a fine-grained level of granularity, typically instructions.

In practice, most of them actually perform a hierarchical diffing [START_REF] Flake | Structural comparison of executable objects[END_REF]. They first compute a mapping of pieces of code at a higher level, such as function or basic block, and then proceed a second diffing among each pair of matched elements. In this case, the resulting fine-grained alignment largely depends on the quality of the prior mapping, since any mismatch in this later would induce a completely erroneous alignment of its constitutive elements.

Notice that the chosen level of granularity to perform binary diffing may differ from the one chosen to measure the code similarity. For instance, an approach may seek at aligning the functions of the program, while measuring function similarity by comparing their constitutive basic blocks.

Binary code similarity

The key interest of binary diffing is to retrieve common features from a program into another. Therefore, a robust problem formulation should not restrict to mapping identical patterns, but should be able to match different pieces of code that have a similar functionality. Consequently, an ideal code comparison criteria for addressing the binary diffing problem would measure the semantic similarity of the two pieces of code.

Code characterization

The comparison of two pieces of code requires a prior proper definition of the properties that must be considered. Usually, we distinguish a syntactic depiction of the binary, that only considers the available code representation, from a semantic characterization that focuses on the intrinsic code functionality, or meaning, no matter its practical implementation [START_REF] Nielson | Principles of Program Analysis[END_REF].

A fundamental problem of static program analysis is that there is no immediate relationship between the syntax of a piece of code and its expected execution behavior [START_REF] Haq | A Survey of Binary Code Similarity[END_REF]. For instance, as there might be multiple ways to implement a complex process, there may be several syntactic representations of a same program semantic. In addition, it is well known that the compilation of the same source code can result in very different binary executables, though they share the exact same functionalities [START_REF] Liu | Binary Code Analysis[END_REF]). These differences may be due to different compiler heuristics, or optimization levels, but also to the targeted architecture or operating system for which the program is built. Furthermore, though the exact same syntax necessarily induces the same semantic, slight syntactic program divergences, such as a single target address modification, may result in completely different run-time behaviors. Consequently, the retrieval of the syntactic differences between two pieces of code may be insufficient to assess the similarity of their respective behavior when executed. Notice however that in practice, it still provides valuable information in many cases.

Unfortunately, the complete semantic characterization of a program is also a very challenging problem. In fact, from a simple reduction to the Halting problem, it is known to be mathematically undecidable [START_REF] Rogers | Theory of recursive functions and effective computability[END_REF]. Therefore, semantic characterizations are most of the time approximated on much smaller pieces of code such as instructions or basic blocks, in order to be then compared with each other. The resulting comparison can then be aggregated to evaluate the similarity of larger elements such as functions.

Semantic measures

A convenient format to describe the semantic of a piece code is to record the different memory modifications that result from its execution [START_REF] Cadar | Symbolic execution for software testing: three decades later[END_REF]. Such representation ignores the intermediate operations and is independent of the code syntax. In static analysis, such semantic characterization can be computed using symbolic execution [START_REF] King | Symbolic execution and program testing[END_REF]. However, the computational cost of symbolic execution of a piece of code rises exponentially with its complexity. Therefore, though it can characterize arbitrarily complex pieces of code, symbolic execution is mostly performed on a consecutive sequence of instructions, such as basic blocks or traces, in order to limit the code complexity and thus the required computation time.

Several methods propose to evaluate the semantic similarity of two pieces of code by comparing their symbolic execution. To this end, some of them introduce satisfiability modulo theories (SMT) solvers to check if the resulting symbolic formulas are equivalent [START_REF] Gao | BinHunt: Automatically Finding Semantic Differences in Binary Programs[END_REF][START_REF] Ming | iBinHunt: binary hunting with inter-procedural control flow[END_REF][START_REF] Lakhotia | Fast location of similar code fragments using semantic 'juice[END_REF][START_REF] Luo | Semantics-based obfuscation-resilient binary code similarity comparison with applications to software plagiarism detection[END_REF][START_REF] David | Statistical similarity of binaries[END_REF]. However, in addition to being very computationally expensive, such approaches can only assess the equivalence of the code, and not measure its similarity.

To overcome this issue, some methods propose to compute edit distances on the set of symbolic formulas [START_REF] David | Tracelet-based code search in executables[END_REF][START_REF] Pewny | Leveraging semantic signatures for bug search in binary programs[END_REF]. Other works refer instead to a statistical measure of semantic similarity by comparing the ratio of identical outputs, given the same input [START_REF] Kruegel | Polymorphic worm detection using structural information of executables[END_REF][START_REF] Jin | Binary Function Clustering Using Semantic Hashes[END_REF][START_REF] Chandramohan | BinGo: cross-architecture cross-OS binary search[END_REF][START_REF] Pewny | Cross-Architecture Bug Search in Binary Executables[END_REF]. Such an approach is very convenient since each piece of code can be fully encoded through a vector of output values, and therefore enables one to quickly compute the similarity scores using common metrics. However, the number of evaluated inputs is often insignificant with regards to the set of every possible arguments, and consequently provides low confidence on the resulting similarity scores.

More recently, several methods introduced supervised learning models designed to measure the semantic similarity of codes. The idea is to feed the models with pairs of semantically equivalent pieces of code in order to learn their common syntactic properties [START_REF] Xu | Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection[END_REF][START_REF] Massarelli | SAFE: Self-Attentive Function Embeddings for Binary Similarity[END_REF][START_REF] Li | Graph Matching Networks for Learning the Similarity of Graph Structured Objects[END_REF][START_REF] Liu | $\alpha$ Diff: cross-version binary code similarity detection with DNN[END_REF][START_REF] Zuo | Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs[END_REF]. The major interest of these approaches is that the similarity score is directly computed on the code representation and therefore is much faster than common semantic measures. However, they require the collection of a large quantity of statistically significant pairs of semantically equivalent pieces of code. Such training data set is not immediately available. Current techniques restrict to samples taken from slight mutations of a same program, resulting for instance from different compilation processes, or from minor source code modifications. However, there is no guarantee that the collected pairs are semantically equivalent or, more importantly, statistically significant. In fact, following this design, all training samples come from the same source code, and therefore, enclose syntactic differences necessarily resulting from the compilation process, and never from different implementations.

To some extend, unsupervised models designed to learn instruction embeddings based on their closest neighbors could be also considered as semantic similarity measures, though they can actually only consider the syntax of the code [START_REF] Ding | Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization[END_REF][START_REF] Zuo | Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs[END_REF][START_REF] Duan | DeepBinDiff: Learning Program-Wide Code Representations for Binary Diffing[END_REF][START_REF] Chua | Neural nets can learn function type signatures from binaries[END_REF].

Syntactic measures

Another category of code similarity measure focuses on the code syntax. These measures mostly compare arbitrary features extracted from the code representation. Common features describe the code instructions (count of different mnemonics or operands, occurrences of particular operations, etc.) or their normalized representation (classification, intermediate representation, etc.), the code structure (instruction number, basic blocks layout, callers and callees, addresses, etc.) or the presence of characteristic elements (function names, function imports, strings, system calls, immediate values, etc.) [START_REF] Dullien | Graph-based comparison of executable Objects[END_REF][START_REF] Bourquin | BinSlayer: accurate comparison of binary executables[END_REF]Alrabaee et al., 2018;[START_REF] Kinable | Malware classification based on call graph clustering[END_REF]. Such approaches have the major advantage of being very fast to both extract and compute, and enable the pairwise comparison of a large number of pieces of code in a limited amount of time. Few other approaches introduce more complex measure derived from graph matching problems such as string or graph edit distance [START_REF] Hu | Large-scale malware indexing using function-call graphs[END_REF][START_REF] Huang | BinSequence: Fast, Accurate and Scalable Binary Code Reuse Detection[END_REF][START_REF] Alrabaee | SIGMA[END_REF], maximum weight matching [START_REF] Feng | Scalable Graph-based Bug Search for Firmware Images[END_REF], maximum common edge subgraph [START_REF] Eschweiler | discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code[END_REF]. These methods are more precise and tend to better enclose the semantic similarity of the code. However, solving a large number of matching problems can be very expensive and therefore scales less easily to larger programs.

Binary code matching

Once a proper measure of code similarity has been defined, the pieces of code that are considered similar must be aligned to provide to the analyst a precise mapping of the common and different parts in each program. To the best of our knowledge, all proposed approaches are designed to produce an injective alignment, i.e. to match each piece of code to at most one counterpart. Such mappings are sometimes abusively referred to as one-to-one correspondences, though they do not actually consists in bijections. Notice that more complex many-to-many mappings could be used to retrieve common code patterns such as basic blocks or functions split or merge, or code duplication [START_REF] Bernat | Structured Binary Editing with a CFG Transformation Algebra[END_REF].

Maximum weight matching

The straightforward approach to compute a one-to-one mapping given a measure of code similarity consists in computing all pairwise similarity scores and to find the one-to-one mapping that maximizes the overall sum of similarity. This is the natural matching strategy of methods using complex code similarity measures, such as those originally designed to perform near-duplicate retrieval [START_REF] Feng | Scalable Graph-based Bug Search for Firmware Images[END_REF][START_REF] Xu | Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection[END_REF][START_REF] Li | Graph Matching Networks for Learning the Similarity of Graph Structured Objects[END_REF]. This assignment problem is known as the maximum weight matching (MWM) problem and its optimal solutions can be found exactly in polynomial time, using e.g. the Hungarian algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF]. The major drawback of this approach is that the resulting mapping might be highly inconsistent with regards to the code structure of the two programs, which may indicate that it failed to leverage part of the program semantics.

Maximum common edge subgraph

To overcome this issue, other formulations favor mappings that are locally consistent with regard to the graph structure of the programs. For instance, [START_REF] David | Tracelet-based code search in executables[END_REF] looks for the Longuest Common Sequence of basic blocks. The most common approach addresses the binary diffing problem as a maximum common edge subgraph problem (MCS). The idea consists in finding the node correspondence that maximizes the number of induced common edges in both graphs [START_REF] Bahiense | The maximum common edge subgraph problem: A polyhedral investigation[END_REF]. Such edge overlaps are also known as squares [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF].

Unfortunately, the MCS problem is known to be NP-complete and even APX-hard [START_REF] Kann | On the Approximability of the Maximum Common Subgraph Problem[END_REF]. Since modern programs typically consist in much more than a hundred functions and thousands of basic blocks, solutions to the MCS must be approximated. The most common approximate method is based on the VF algorithm of P. [START_REF] Cordella | A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs[END_REF]. The idea is to iteratively expand a partial node correspondence while preserving its topological consistency. At each iteration, a set of candidate nodes from each program is thus collected in the neighborhood of the current mapping. A pair of nodes is matched and included in the solution if they share a similar content as well as a similar neighborhood. In practice, the error tolerance on both the node and edge similarity increases with the number of iterations [START_REF] Dullien | Graph-based comparison of executable Objects[END_REF].

Though this strategy proved to provide satisfying results, it suffers from several important limitations. Indeed, at each iteration, the candidate nodes are retrieved from the neighborhood of the current solution. Therefore, any error in the partial assignment intrinsically misleads the candidate selection and may propagate erroneous correspondences as the matching process goes on. In particular, the algorithm is very sensitive to the mapping initialization, which is often performed based on the node content only. More importantly, another drawback of this approach is that by restricting new matches to belong to the respective neighbors of the current partial mapping, it prevents the assignment of potentially better non-local correspondences. Therefore, this strategy mostly consists in finding a locally-consistent mapping whereas a globally better assignment potentially exists.

Graph edit distance

To our knowledge, the only global formulation of the binary diffing problem refers to a graph edit distance problem (GED) [START_REF] Hu | Large-scale malware indexing using function-call graphs[END_REF][START_REF] Kostakis | Improved call graph comparison using simulated annealing[END_REF][START_REF] Bourquin | BinSlayer: accurate comparison of binary executables[END_REF]. The idea consists in considering a set of possible graph edit operations on both the nodes and edges of the graphs, and in assigning to them a cost. Intuitively, the cost of substituting a piece of code with another one would be inversely proportional to their measured similarity score. A series of edit operations is called an edit path, and its cost is simply the sum of the costs of its constitutive operations. Then, an edit path that transforms graph A into B at the minimum cost is called an optimal edit path and the resulting edit cost is known as the graph edit distance [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF].

Such formulation is particularly convenient to an analyst since it provides an explicit description of the different modifications that transform a first binary into another one.

There is a close relationship between an edit path and a mapping. Indeed, under mild conditions on the possible edit operations and their respective costs, both solutions are equivalent (see Chapter 3 for more details). In this case, substituted nodes correspond to matched elements, whereas inserted and deleted nodes correspond to the pieces of code that do not belong to the mapping. Therefore, the optimal graph edit path between two programs can be used as a solution to the binary diffing problem.

Unfortunately, the graph edit distance problem is of the same complexity as the MCS problem [START_REF] Lin | Hardness of Approximating Graph Transformation Problem[END_REF]. Though exact algorithms exist, they rapidly become intractable as the number of vertices rises [START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications[END_REF]. In practice, the computation of the GED of graphs of more than a hundred nodes must be approximated.

Several approaches have been previously proposed to compare programs in binary form through a GED formulation [START_REF] Hu | Large-scale malware indexing using function-call graphs[END_REF][START_REF] Kostakis | Improved call graph comparison using simulated annealing[END_REF][START_REF] Kinable | Malware classification based on call graph clustering[END_REF][START_REF] Bourquin | BinSlayer: accurate comparison of binary executables[END_REF]. However, in order to compute an approximated solution, all of them refer to the linear programming relaxation of [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], which reduces to the above-mentioned MWM formulation of the binary diffing problem where the similarity score of each pair of nodes is computed with respect to their respective number of incident edges.

In our work, we propose to address the binary diffing problem as a GED problem. In Chapter 3 we introduce a proper formulation of the problem and prove that it is equivalent to a constraint integer quadratic program known as the network alignment problem [START_REF] Burkard | Quadratic assignment problems[END_REF]. In this form, the globally optimal edit-path can be efficiently approximated by means of a message passing framework presented in Chapter 4.

Chapter 3

Problem Statement

In this chapter, we formalize our definition of the binary diffing problem as a graph edit distance problem. We then introduce another seemingly different formulation of the problem through an integer quadratic program, known as the network alignment problem (NAP) [START_REF] Klau | A new graph-based method for pairwise global network alignment[END_REF], for which efficient approximate solutions have been proposed. We finally prove that under mild restrictions over the set of possible edit-operations, both formulations are actually equivalent. We conclude this chapter by discussing the determination of the edit-operation costs, as well as the different assumptions induced by the restrictions.

Binary diffing as a graph edit distance problem

In our work, we define the binary diffing problem as the problem of aligning call graphs. We want to map functions from a program into functions of another such that they share similar functionalities (node content similarity) and they call other functions in a similar way (induced edge similarity). As a result, when a matching is satisfactory, the remaining differences between the call graphs can be interpreted as meaningful modifications from a program to the other. A natural representation of such correspondence implies an edit path and the binary diffing can thus be formulated as an instance of a call graph edit distance problem [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF].

Let us consider two binary executables A and B. We assume that adapted disassembly tools are used to represent them by their respective call graphs

G A = (V A , E A ) and G B = (V B , E B ). The vertices V A = {1, . . . , n} and V B = {1 , . . . , m } represent the functions of A and B. The edges E A ⊂ {(i, j)|i, j ∈ V 2 A , i = j} and E B ⊂ {(i , j )|i , j ∈ V 2 B , i = j } represent the function calls.
For instance, the edge (i, j) ∈ E A encodes the fact that function i calls function j in program A. Without loss of generality, we assume that both call graphs do not include self-loops, i.e. recursive calls. We discuss in Section 3.4.1 how they can be accounted for at the level of the function similarity calculation.

We assume given a measure σ V that evaluates the similarity between two functions i ∈ V A and i ∈ V B such that σ V (i, i ) = s i,i . Similarly, the measure σ E computes the similarity between the function calls (i, j) ∈ E A and (i , j ) ∈ E B in A such that σ E ((i, j), (i , j )) = s ij ,i j . We also assume that the two similarity measures give values in [0, 1]. As a result, we can easily convert similarity scores into dissimilarity scores, or costs, using Finally, we assume that each node i ∈ V A and edge (i, j) ∈ E A is given a nonnegative value d i, and d ij, corresponding to the cost of removing the function i or the call (i, j) in the graph A. Similarly, the values d ,i and d ,i j characterize the cost of insertion of each function i and call (i , j ) in graph B. Let us finally consider six possible program edit operations and their respective costs given in Table 3.1. We denote any series of graph edit operations (op 1 , . . . , op k ) an edit path, and define P(A, B) as the set of all possible edit paths that transform

d i,i = 1 -s i,i and d ij,i j = 1 -s ij,i j . Operation Cost substitute function c(i → i ) = d i,i delete function c(i → ) = d i, insert function c( → i ) = d ,i substitute call c((i, j) → (i , j )) = d ij,i j delete call c((i, j) → ) = d ij, insert call c( → (i , j )) = d ,i j
G A into G B . Formally, if (op 1 , . . . , op k ) ∈ P(A, B), then op k (op k-1 (. . . op 1 (G A ) . . .)) = G B (see Figure 3.1).
The definition of an edit path is quite permissive. In order to control its versatility, we must attach few constraints on P(A, B): every node and edge in both graphs A and B must be subject to one and only one edit operation. In other words, every element of A must be either deleted or substituted once, and every element of B must be either inserted or substituted once every edge incident to a deleted node must be deleted and every edge incident to an inserted node must be inserted an edge (i, j) ∈ E A is substituted by (i , j ) ∈ E B if and only if i is substituted by i and j is substituted by j . Furthermore, since they consist in an ordered sequence of operations, multiple edit paths may encode the exact same graph transformation. For instance, a path may remove node i before node j while another path can do the opposite scheme. In our work, we are only interested in the resulting overall graph transformation, no matter the order in which the operations are performed. Therefore, we introduce an arbitrary order on both the nodes and edges such that no two edit path can consist in the same collection of edit operations.

In the rest of this thesis, we abusively refer to this set of slightly restricted edit-paths as P(A, B). Notice that, though these constraints might appear to be quite restrictive, they are actually mechanically satisfied for most edit cost definitions. We provide more details in the Section 3.4.

Following these notations, our formulation of the binary diffing problem consists in finding the minimal-cost edit path P * that transforms A into B. Formally:

P * = arg min P ∈P(A,B) C(P ) = arg min (op 1 ,...,op k )∈P(A,B) k i=1 c(op i ) (GED)

Binary diffing as a network alignment problem

We now reformulate our definition of the binary diffing problem as an equivalent instance of a network alignment problem. To begin with, we must introduce the following notations.

We first describe the function mapping via a binary vector x ∈ {0, 1} |V A |×|V B | (where |U | denotes the cardinality of the set U ) such that x ii = 1 if and only if function i in A is matched with function i in B. In order to ensure that each function in A is matched to at most one function in B and vice versa, x must fulfill the following constraints:

∀i ∈ V A , j ∈V B x ij ≤ 1, ∀i ∈ V B , j∈V A x ji ≤ 1 (3.1)
A good matching should associate similar functions that have also similar calling patterns. This can be captured in a large cost matrix W ∈ R |V A | 2 ×|V B | 2 defined as follows:

W ii jj =      w ii if ii = jj , w ii jj if (i, j) ∈ E A and (i , j ) ∈ E B , 0 otherwise. (3.2)
with:

w ii = -d i,i + d i, + d ,i , w ii jj = -d ij,i j + d ij, + d ,i j
Using these definitions, it can be shown that computing the optimal edit path of (GED) is equivalent to solving the following network alignment problem:

x * =arg max x x T W x subject to ∀i ∈ V A , j ∈V B x ij ≤ 1 ∀i ∈ V B , j∈V A x ji ≤ 1 x ∈ {0, 1} |V A |×|V B | (NAP)
We provide a proof in the next section.

Equivalence between graph edit distance and network alignment problem

In the rest of this document, we denote X the solution set of (NAP), i.e. the set of all binary vectors x ∈ {0, 1} |V A |×|V B | satisfying the constraints (3.1).

Formal proof

In the following proof, we first show that there is a one-to-one correspondence between P(A, B), the solution set of (GED), and X , the one of (NAP). Then we show that both objective functions are equivalent up to a sign and a constant term. As a consequence, since both problems optimize an equivalent objective function on an equivalent solution set, they can be considered equivalent.

Lemma 1. The function φ :

P(A, B) → X , φ(P ) = x such that i → i ∈ P ⇔ x ii = 1 is bijective.
Proof. We first show that φ is surjective, i.e. that any binary vector x ∈ X may result from a valid edit path P ∈ P(A, B). Consider any vector x ∈ X , and let us design an edit path P as follows: First substitute both nodes and edges of graph A by those of graph B according to vector x such that:

i → i ∈ P, ∀(i, i ) ∈ V A × V B such that x ii = 1 (i, j) → (i , j ) ∈ P, ∀((i, j), (i , j )) ∈ E A × E B such that x ii x jj = 1
Then remove all remaining nodes and edges in graph A:

i → ∈ P, ∀i ∈ V A such that ∀i ∈ V B , i → i / ∈ P (i, j) → ∈ P, ∀(i, j) ∈ E A such that ∀(i , j ) ∈ E B , (i, j) → (i , j ) / ∈ P
And finally insert all missing nodes and edges in graph B:

→ i ∈ P, ∀i ∈ V B such that ∀i ∈ V A , i → i / ∈ P → (i , j ) ∈ P, ∀(i , j ) ∈ E B such that ∀(i, j) ∈ E A , (i, j) → (i , j ) / ∈ P
From the first substitution step, it is clear that φ(P ) = x. Moreover, P effectively transforms graph A into B since after substituting a set of nodes and edges from A to B, it removes all remaining elements of A and inserts all missing elements in B. Finally, as x satisfies the constraints (3.1), every node and thus edge in both graph is subject to one and only one edit operation. Since, by design, P fulfills the other conditions, it consists in a valid edit path. Consequently, φ is surjective.

We now show that φ is injective, i.e. that any two edit paths P, P ∈ P(A, B) such that P = P necessarily characterize two different binary vectors x = x with x = φ(P ) and x = φ(P ).

It is clear that if the set of substituted nodes in P and P differs, then x = x . Moreover, as any node must be subject to a single operation, any difference in the set of inserted nodes in P and P necessarily implies a difference in their node substitution operations. Therefore, either both P and P proceed to the same node insertions, or x = x . This property holds true for the set of deleted nodes. Furthermore, if P and P share the same set of edit operations on the nodes, they must also have the same set of operations on the edges incident to both inserted and deleted nodes, since these operations are constraint by our definition of valid edit path. Finally, the remaining differences may come from the edition of edges incident to two substituted nodes. However, here again our definition of a valid edit path is unambiguous: if both graphs include an edge between two substituted nodes, the edge must be substituted from A to B, otherwise, the edge is either removed or inserted. Therefore, any difference in the constitutive edit operation of both P and P implies a difference in their respective image x and x according to φ. As a consequence, function φ is injective, surjective, and thus bijective.

Lemma 2. Let P ∈ P(A, B) be an arbitrary edit path and let x = φ(P ) ∈ X be its equivalent representation according to Lemma 1, then C(P ) = -x T W x+C(P 0 ) where C(P 0 ) is a constant term.

Proof. For the sakes of clarity, we represent the cost of the edit path P as the sum of its node and edge operation costs, i.e. C(P ) = C V (P ) + C E (P ). Moreover, we introduce the following notations to represent the cost of inserting or removing all nodes and all edges in each graph:

V A 0 = i∈V A d i, , V B 0 = i ∈V B d ,i , E A 0 = (i,j)∈E A d ij, , E B 0 = (i ,j )∈E B d ,i j
Let us first describe C V (P ), the cost of the node operations in P . We distinguish the different possible operations such that:

C V (P ) = i→i ∈P c(i → i ) + i→ ∈P c(i → ) + →i ∈P c( → i ) = i→i ∈P d i,i + i→ ∈P d i, + →i ∈P d ,i = i→i ∈P d i,i -d i, -d ,i + i→i ∈P d i, + d ,i + i→ ∈P d i, + →i ∈P d ,i = i→i ∈P d i,i -d i, -d ,i + i∈V A d i, + i ∈V B d ,i = i→i ∈P d i,i -d i, -d ,i + V A 0 + V B 0
where we used the fact that i→i ∈P x i + i→ ∈P x i = i∈V A x i .

In order to evaluate the cost of all the edges operations, we must consider the different possible configurations for pairs of nodes. But first, we must introduce the following notations:

δ A ij = = 1, if (i, j) ∈ E A , = 0, otherwise. δ B i j = = 1, if (i , j ) ∈ E B , = 0, otherwise.
We also notice that the edition cost of edges incident to two substituted nodes is:

i→i ∈P j→j ∈P d ij,i j δ A ij δ B i j + d ij, δ A ij (1 -δ B i j ) + d ,i j (1 -δ A ij )δ B i j = i→i ∈P j→j ∈P (d ij,i j -d ij, -d ,i j )δ A ij δ B i j + i→i ∈P j→j ∈P d ij, δ A ij + i→i ∈P j→j ∈P d ,i j δ B i j
3.3. Equivalence between graph edit distance and network alignment problem 27

We may now evaluate C E (P ) such that:

C E (P ) = i→i ∈P j→j ∈P d ij,i j δ A ij δ B i j + d ij, δ A ij (1 -δ B i j ) + d ,i j (1 -δ A ij )δ B i j + i→i ∈P j→ ∈P d ij, δ A ij + i→i ∈P →j ∈P d ,i j δ B i j + i→ ∈P j→j ∈P d ij, δ A ij + →i ∈P j→j ∈P d ,i j δ B i j + i→ ∈P j→ ∈P d ij, δ A ij + →i ∈P →j ∈P d ,i j δ B i j = i→i ∈P j→j ∈P (d ij,i j -d ij, -d ,i j )δ A ij δ B i j + i∈V A j∈V A d ij, δ A ij + i ∈V B j ∈V B d ,i j δ B i j = i→i ∈P j→j ∈P (d ij,i j -d ij, -d ,i j )δ A ij δ B i j + E A 0 + E B 0
Putting all together, and denoting

C(P 0 ) = V A 0 + V B 0 + E A 0 + E B 0
, the cost of any edit path P is:

C(P ) = C V (P ) + C E (P ) = C(P 0 ) + i→i ∈P d i,i -d i, -d ,i + i→i ∈P j→j ∈P (d ij,i j -d ij, -d ,i j )δ A ij δ B i j = C(P 0 ) - i→i ∈P w ii - i→i ∈P j→j ∈P w ii jj δ A ij δ B i j = C(P 0 ) - ii ∈V A ×V B x ii w ii - ii ∈V A ×V B jj ∈V A ×V B x ii x jj w ii jj δ A ij δ B i j = C(P 0 ) - ii ∈V A ×V B jj ∈V A ×V B x ii w ii jj x jj = C(P 0 ) -x T W x
where we simply use the fact that d i,i -d i, -d ,i = -w ii and similarly for w ii jj .

Proposition 1. The formulation of the graph edit distance problem GED is equivalent to the network alignment problem NAP.

Proof. The proof immediately results from Lemmas 1 and 2.

Related work

Other works previously attempt to formalize relationships between the graph edit distance problem and other graph matching problems. For instance, it has been shown that the maximum common edge subgraph problem is equivalent to a special case of the graph edit distance under particular edit operation costs (Bunke, 1999;[START_REF] Bunke | On a relation between graph edit distance and maximum common subgraph[END_REF][START_REF] Brun | Relationships between graph edit distance and maximal common structural subgraph[END_REF]. Moreover, [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF] proposed to compute a sub-optimal solution to the GED problem by solving a maximum weight matching problem instance. In order to enable node insertion and deletion, their model expands the pairwise node substitution cost matrix of size [START_REF] Bougleux | Graph edit distance as a quadratic assignment problem[END_REF] then extended this approach and introduced a network alignment formulation of the GED. However, this model requires a cost matrix of size

|V A | × |V B | to a larger matrix of size |V A | + |V B | × |V A | + |V B |.
(|V A | + |V B |) 2 × (|V A | + |V B |)
|V A | + |V B |.
Recently, independently of our work, [START_REF] Raveaux | On the unification of the graph edit distance and graph matching problems[END_REF] proved that the formulation of [START_REF] Lerouge | New binary linear programming formulation to compute the graph edit distance[END_REF] could be further simplified and actually correspond to our quadratic integer formulation. However, it requires stronger constraints on the set of possible edit paths.

Graph edit operation costs

In the previous sections of this chapter, we introduced a quite natural definition of the binary diffing problem and propose an equivalent reformulation into a network alignment problem. In this section, we discuss the definition of the edit operation costs and propose two simple measures of function and call similarity.

Edit operation relationships Local vs global similarity trade-off

The definition of the edit operation costs of any GED formulation usually relies on carefully chosen data-based considerations (see e.g. [START_REF] Bourquin | BinSlayer: accurate comparison of binary executables[END_REF]). Costs have obviously an effect on the quality of the matching but also on the ability of a solver to find an approximately optimal solution. In particular, the local similarity scores between functions might be inconsistent with the global edge structure of both call graphs, and therefore, there may be no solution that is both locally and globally optimal. As a consequence, a matching results from an inherent trade-off between local node similarity and global graph topology.

In order to control this trade-off, we may decompose the matrix W into two terms and weight them accordingly. We define W 1 as the diagonal matrix in R |V A | 2 ×|V B | 2 with diagonal terms W 1ii ii = w ii and W 2 as W 2 = W -W 1 . Thus, matrix W 1 gathers the node similarity scores while W 2 contains all the potential induced overlapping edges, or "squares".

Given a trade-off parameter α ∈ [0, 1], the objective function of (NAP) can thus be modified into: In terms of graph edit operations, this reformulation simply consists in appropriately weighting the original edit operation costs.

αx T W 1 x + (1 -α)x T W 2 x
Notice that extreme values for α correspond to some interesting particular cases. Indeed, when α = 1, our problem reduces to a maximum weight matching (MWM) strategy which disregards the function calls and produces a mapping solely based on the function similarity. Furthermore, the case α = 0 corresponds to an instance of the maximum common edge subgraph (MCS) problem where function similarities are not used. Therefore, our formulation can be seen as a balanced strategy between the two most common binary code matching methods.

Substitution vs deletion -insertion trade-off

The versatility of the graph edit distance problem offers multiple possible paths to transform an element in graph A into one in B. In particular, any edit path results from an inherent choice between substituting two elements or removing the element in A and then insert the one in B. In our problem definition, we introduce a restriction on the edge edit operations such that this choice does not apply: any edge incident to two substituted nodes must be substituted, and can not be removed and then inserted. However, this ambiguity remains for the node operations: any two nodes in both graphs can always result from a substitution, or a deletion followed by an insertion (see Figure 3.2). Notice that both edit schemes provide a completely different interpretation in the context of binary diffing. For instance, an analyst would pay different attention to a patched function than to a newly inserted one.

The choice of favoring a substitution over a deletion -insertion scheme depends on the cost of both patterns. From the previous proof, we may express the relative cost of substituting two nodes i ∈ V A and i ∈ V B within an edit path P such that:

d i,i -d i, -d ,i + j→j ∈P (d ij,i j -d ij, -d ,i j )δ A ij δ B i j
This relative cost perfectly highlights the trade-off between substituting both nodes or deleting node i in order to later insert node i . On one hand, the substitution of both nodes has a cost d i,i . On the other hand, since each node must be subject to an edit operation, performing a substitution implicitly prevents to pay the cost of both an insertion and a deletion d i, + d ,i . Such balance is summed up in the first part of the above equation. Furthermore, the substitution of two nodes immediately implies the substitution of their respective edges that are both incident to other substituted nodes, again, the cost of these operations can be view as the cost of substitution to which is subtracted the avoided cost of insertion and deletion.

As a consequence, an edit path would prefer substituting both nodes instead of performing a delete then insert scheme only if:

d i,i -d i, -d ,i + j→j ∈P (d ij,i j -d ij, -d ,i j )δ A ij δ B i j ≤ 0
which, following the notation of the proof, corresponds to the cases where:

w ii + jj ∈V A ×V B
x jj w ii jj ≥ 0

In other words, in our graph edit formulation, the choice of substituting two functions is not only based on their content similarity, but also considers the one of their induced common edges.

Therefore, by leveraging the trade-off parameter α introduced above, we may weight the node and edge similarity scores in order to precisely control to what extent two functions that have a quite different content similarity but induce many similar edges should be matched.

Edit path assumptions

We finally discuss the different restrictions introduced all along our problem definition.

To begin with, we assumed that both graph A and B do not include self-loops, i.e. recursive functions. This assumption may be very restrictive since modern programs often require such implementation patterns. In fact, self-loops can be easily handled. Indeed, in terms of edit operations, the cost of substituting two recursive functions i ∈ V A and i ∈ V B is simply its original node substitution cost to which we add the cost of substituting both function self-loops. Therefore, this cost can be fully characterized by a slightly modified node similarity score d i,i such that d i,i = d i,i + d ii,i i . In other words, any self-loop can be considered as an attribute of the function, if it is properly taken into account by the node similarity measure. Similarly, the cost of removing the recursive function i becomes di, = d i, + d ii, .

We also proposed a constrained definition of the possible edit path. First, we restrict valid edit paths to perform respectively a delete or insert operation on edges incident to deleted or inserted nodes. Such definition is quite common in other works [START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications[END_REF], though it could be formulated otherwise. It mostly aims at properly distinguishing a node substitution from a deletion -insertion scheme.

Moreover, we restrict a valid edit path to perform one and only one operation per constitutive elements of both graphs. Here again, similar restrictions are commonly introduced in other works [START_REF] Bougleux | Graph edit distance as a quadratic assignment problem[END_REF][START_REF] Raveaux | On the unification of the graph edit distance and graph matching problems[END_REF]. Therefore, no function nor call could be, for instance, inserted then substituted, inserted then removed or substituted multiple times. It is clear that all of these edit patterns are redundant, since an equivalent edition could be obtained from a single (or even no) edit operation. As a consequence, they would still be optimal only if the unnecessary operations have zero cost (negative costs are forbidden by definition). Notice that zero cost operations may be encountered in several configurations, in order to address special cases of the GED (see e.g. [START_REF] Bunke | On a relation between graph edit distance and maximum common subgraph[END_REF]). In such a case, an optimal edit path could include an infinite number of free operations if it was not forbidden by our definition. On the contrary, in the case of non-metric similarity measure, when the cost of substituting two identical elements is strictly positive, our definition guaranties that this cost is taken into account, since it can not be replaced by the equivalent but completely free edition scheme that consists in performing no operation.

Finally, we constraint any solution edit path to favor edge substitution over edge deletion then insertion whenever it is possible. Such a condition is truly restrictive, since it may result in a sub-optimal edit-path when the cost of substitution exceeds the one of both deletion and insertion. However, in practice, edit costs often satisfy d ij,i j ≤ d ij, + d ,i j , in which case the restriction does not apply [START_REF] Blumenthal | Quasimetric Graph Edit Distance as a Compact Quadratic Assignment Problem[END_REF].

Similarity measures

Function content similarity

As mentioned in the previous chapter, many different methods have been proposed to measure the similarity of two binary functions. Arguably, the quality of this measure may significantly affect the performance of the diffing process. However, the purpose of our work is to identify and evaluate the benefit of the proposed matching strategy only. Therefore, we propose to use a simple syntactic-based function similarity metric σ V as a baseline.

Our measure consists in a weighted Canberra distance [START_REF] Lance | Computer Programs for Hierarchical Polythetic Classification ("Similarity Analyses[END_REF] over the set of features given in Table 3.2. During the computation, each feature is properly weighted according to its type. We distinguish content-based (instructions), topological-based (CFG layout), and neighborhood-based features (CG callers and callees). Notice that one of our features refers to an instruction classification. This classification encodes each instruction using the class of its mnemonic and the ones of its potential operands. Our taxonomy consists in respectively 34 and 13 different mnemonic and operand classes.

Since most matching algorithms are sensitive to ties between function distances, we introduce a small perturbation to the resulting similarity scores. Assuming that the denomination of the functions is consistent with their order in terms of entry address, the similarity between function i in A and i in B is being increased by the value 1 -

|i-i | max(|V A |,|V B |) .

Function call similarity

In order to measure the similarity of two function calls, we simply use a 0/1 indicator, i.e. σ E ((i, j), (i , j )) = 1 if and only if (i, j) ∈ E A and (i , j ) ∈ E B . Therefore, the matrix W 2 can be computed through the Kronecker product of the affinity matrix of graphs A and B.

Insertion and deletion costs

Finally, in order to compare with other state of the art methods, and because, in general, binary diffing favors recall over precision, we set all the insertion and deletion operation costs to

d i, = d ,i = d ij, = d ,i j = 1 2 .
As a result, the constitutive weights of matrix W (3.2) simply become:

w ii = -d i,i + d i, + d ,i = 1 -d i,i + d i, + d ,i -1 = s i,i + 1 2 + 1 2 -1 = s i,i
Similarity, we have w ii jj = s ij,i j . This configuration forces the algorithm to produce a complete mapping even when some assignments are of poor relevance, since the cost of deleting then inserting a node is equal to 1, which is always more expensive than the cost of substituting both nodes.

In this Chapter, we proposed a formal definition of the binary diffing problem as a graph edit distance problem, and proved that it actually reduces to an instance of the network alignment problem. In this form, the optimal edit-path can be efficiently approximated by means of a message passing framework. We provide a complete presentation to this framework in Chapter 4.

Chapter 4

Message-passing framework for the network alignment problem

In this chapter, we present a novel algorithm to address the network alignment problem. It is inspired from a previous model, named NetAlign, proposed by [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF] and designed to efficiently approximate a solution via the max-product algorithm. We first give a short introduction to the max-product algorithm, and then present in more details the original model of NetAlign. We finally propose several modifications to this model, designed to significantly speed up the message updates as well as to enforce their convergence. We conclude the chapter by reviewing different other approaches proposed to address the network alignment problem.

Max-product algorithm

A graphical model is a way to represent a class of probability distributions over some random variables [START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques -Adaptive Computation and Machine Learning[END_REF]. The main interest of graphical model is to efficiently encode the local interactions between the variables in order to leverage potential conditional independence, and thus to reduce the overall combinatorial complexity of the distribution. There is a strong link between inference in graphical models and optimization problems, especially when we consider maximum a posteriori (MAP) inference. MAP inference is the problem of finding the most probable value of some of the random variables given the value of the rest of the variables. A particular case of MAP inference reduces to finding the mode of the probability distribution, i.e. the most probable value of all its variables. Therefore, if a graphical model encodes both the objective function and the constraints of an optimization program into a probability distribution such that it assigns maximum probability to the optimal solution of the problem, then there is an equivalence between finding the mode of the distribution and solving the program.

The max-product (or min-sum) algorithm is one of the most efficient algorithm for performing MAP inference [START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques -Adaptive Computation and Machine Learning[END_REF]. The idea of maxproduct algorithm is to estimate the max-marginals of each variable in the model, i.e. the marginal distribution of a single variable, given the optimal assignment of all the others. At first sight, the benefit of maximizing multiple times the joint distribution over all the variables but one, instead of directly computing its mode is not clear. Indeed, both problems could be considered of the same complexity for sufficiently large graphical models or small variable support. In fact, by means of an adapted message passing implementation, the max-marginals can be estimated all at the same time, by recycling redundant intermediate local maximizations [START_REF] Loeliger | An introduction to factor graphs[END_REF].

The max-product algorithm has originally been designed to perform MAP inference on tree-like graphical models. In this case, it was proven that the messages converge to the true max-marginals in a finite number of iteration, enabling to exactly determine the mode of the joint distribution (Pearl, 1988). The algorithm was later extended to more complex graphical models containing cycles, providing excellent empirical results in many models, though no theoretical guarantees are available in the general case (see e.g. [START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1[END_REF], [START_REF] Malioutov | Walk-Sums and Belief Propagation in Gaussian Graphical Models[END_REF], [START_REF] Allahverdyan | On maximum a posteriori estimation of hidden Markov processes[END_REF], [START_REF] Meltzer | Globally Optimal Solutions for Energy Minimization in Stereo Vision Using Reweighted Belief Propagation[END_REF], Bayati, Shah, and Sharma (2008), [START_REF] Huang | Loopy Belief Propagation for Bipartite Maximum Weight b-Matching[END_REF], and [START_REF] Sanghavi | Linear programming analysis of Loopy belief propagation for weighted matching[END_REF]). In the rest of this section, we propose a short introduction to the max-product algorithm. We first introduce a particular representation of a graphical model distribution via a factor graph. Then we present the maxproduct algorithm in the case of tree-like graphical models. Finally, we show how the algorithm applies to models with cycles.

Factor-graph

A factor graph is a graphical representation of the factorization of a function. It consists in a bipartite graph, where the first part of the nodes, referred to as variable nodes, represent the global variables of the function, whereas the second part, called factor nodes, correspond to the different factors of the function. Edges in this graph connect factors with their corresponding arguments.

As an example, let us consider the following probability distribution p X : x = {x 1 , . . . , x 7 } ∈ A 7 → [0, 1] for any finite alphabet A, such that:

P X (x 1 , . . . , x 7 ) = f a (x 1 )f b (x 1 , x 2 )f c (x 2 , x 3 , x 4 )f d (x 4 , x 5 , x 6 , x 7 )f e (x 5 ) = k f k (x ∂f k )
where we denote x ∂f k ⊂ x as the subset of variable in x that are arguments of factor f k .

According to the above definition, such distribution is compatible with the factor graph introduced in Figure 4.1. Indeed, the variables {X 1 , . . . , X 7 } correspond to the variable nodes whereas the factors {f a , . . . , f e } are encoded via the factor nodes. Notice that this bipartite graph may also be represented through a tree-like graphical model as pictured in Figure 4.2, in order to best highlight the conditional dependencies of each variables.

A factor graph is a very useful representation of a model distribution that enables the design of a powerful message passing algorithm in order to efficiently estimate each of its max-marginal distributions. Furthermore, it is very convenient to encode constrained optimization program since it may easily simultaneously handle both the objective function and the hard constraints on the function domain. Indeed, the objective function can be be represented by a multiplication of energy potentials, while the hard constraints may be managed by indicator factors which output is null if the constraints are not satisfied. As a result, we may ensure that the distribution function maxima is reached for valid value of the variables only.

Estimation of the max-marginals

The max-product algorithm is designed to efficiently compute the max-marginal distribution of all variables. Following the graphical model introduced above, the max-marginal of variable X 1 corresponds to the distribution:

PX 1 (x) = max x∈A 7 x 1 =x P X (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 )
In order to evaluate PX 1 , we may notice that the overall maximization may be divided into several partial maximization such that:

PX 1 (x) = f a (x) max x 2 f b (x, x 2 ) max x 3 ,x 4 f c (x 2 , x 3 , x 4 ) max x 5 ,x 6 ,x 7 f d (x 4 , x 5 , x 6 , x 7 ) f e (x 5 ) λ fe→X 5 (x 5 ) λ f d →X 4 (x 4 ) λ fc→X 2 (x 2 ) λ f b →X 1 (x)
Consequently, we may compute the max-marginal PX 1 (x), by first finding the optimal values of variables x 5 , x 6 and x 7 given each possible value of x 4 (λ f d →X 4 (x 4 )). The resulting local optimum can then be exploited to compute the best combination of x 3 and x 4 given a value of x 2 , i.e. by solving λ fc→X 2 (x 2 ) = max

x 3 ,x 4 f c (x 2 , x 3 , x 4 )λ f d →X 4 (x 4 ).
Similarly, the distribution of PX 1 (x) can be finally retrieved by maximizing x 2 based on the later intermediate results (λ f b →X 1 (x)). These partial optimizations λ f k →X i enclose all the information of its constitutive variables regarding their contribution to the joint distribution. Therefore, they could be seen as "messages", describing the optimal configuration of locally interacting variables.

In fact, computing PX 1 (x) by performing multiple successive smaller maximizations is often much less expensive than directly optimizing the joint distribution. As an illustration, in our example, assuming that all variables are A tree-like representation of our example graphical model. this representation best highlights the trajectory of the messages during the computation. For instance, in order to estimate the max-marginal of variable X 1 , the updates propagate from factor node e to factor node b in order to transmit to variable node X 1 the locally optimal configuration, as described in our equations.

binary valued, i.e. |A| = 2, the brute-force approach consists in comparing 2 6 = 64 possible variable combinations twice (one for x 1 = 0, and another for x 1 = 1). Meanwhile, the "divide and conquer" approach above requires only 2 × 2 3 + 2 × 2 2 + 2 × 2 = 28 comparisons. Notice that the computational benefit of such approach rises exponentially with the size of the support of each variables. Furthermore, we may notice that some of the messages are also encountered in the computation of the other max-marginals. For instance, we have:

PX 2 (x) = max x 1 f a (x 1 )f b (x 1 , x)max x 3 ,x 4 f c (x, x 3 , x 4 ) max x 5 ,x 6 ,x 7 f d (x 4 , x 5 , x 6 , x 7 )f e (x 5 ) = max x 1 f a (x 1 )f b (x 1 , x)λ fc→X 2 (x) = λ f b →X 2 (x)λ fc→X 2 (x)
Therefore, an optimized implementation could store the intermediate results of the partial maximization in order to avoid redundant computations and to estimate all max-marginals at the same time.

Following this insight, [START_REF] Pearl | Reverend bayes on inference engines: a distributed hierarchical approach[END_REF] proposed a message passing framework to efficiently compute the max-marginals all at once. Messages are transmitted from node to node along the factor graph following the edges. Therefore, messages flow either from a variable node to a factor node, or conversely, from a factor node to a variable node.

We denote µ X i →f k the message from the variable node X i to the factor node f k . The message is defined for all possible values x i of variable X i , and gathers the information coming from all other neighboring factors f k ∈ ∂X i \ f k such as:

µ X i →f k (x) = f k ∈∂X i \f k λ f k →X i (x ∂f k )
In the case where f k is the only neighbor to X i , i.e. ∂X i \ f k = ∅, then µ X i →f k is considered uniformly distributed.

Similarly, the message λ f k →X i represents the message from the factor node f k to the variable node X i . It encloses the optimal configuration of all the neighboring variables of factor f k , given each value of x i . Formally we have:

λ f k →X i (x) = max x ∂f k x i =x f k (x ∂f k ) X j ∈∂f k \X i µ X j →f k (x j ) Here again, if ∂f k \ X i = ∅, the message λ f k →X i (x) is simply equal to f k (x).
Following this message passing scheme, the estimated max-marginal of variable X i can thus be computed such as:

PX i (x) ∝ f k ∈∂X i λ f k →X i (x ∂f k )
And the optimal marginal assignment can thus be deduced such as:

x * i = arg max x∈A PX i (x)
It can be proven that, in the case of acyclic graphical models, all the estimated max-marginals converge to the true max-marginals in a finite number of iteration [START_REF] Pearl | Reverend bayes on inference engines: a distributed hierarchical approach[END_REF]. Furthermore, the resulting distributions can be used to compute the exact mode of P X . In fact, if each max-marginal PX i has a unique optimum x * i , then the mode of the joint distribution corresponds to the combination x = {x * 1 , . . . , x * 7 } [START_REF] Wainwright | Graphical Models, Exponential Families, and Variational Inference[END_REF]. In the case where the optimal marginal assignment is not unique, i.e. if at least one max-marginal admits several maximizers, a back-tracking procedure based on dynamic programming may be leveraged to retrieve the exact MAP of P X [START_REF] Wainwright | Tree consistency and bounds on the performance of the max-product algorithm and its generalizations[END_REF].

Simplifications

Numerical instability is an inherent problem of message passing frameworks on limited precision machines. In particular, when factors represents conditional probabilities (as it is the case for tree-like models), the max-product algorithm may perform many multiplications on values in [0, 1], and consequently may result in messages extremely close to zero, below machine precision. To overcome this issue, we usually reformulate the max-product updates into the log domain such that:

log µ X i →f k (x) = f k ∈∂X i \f k log λ f k →X i (x ∂f k ) log λ f k →X i (x) = max x ∂f k x i =x log f k (x ∂f k ) + X j ∈∂f k \X i log µ X j →f k (x j ) PX i (x) ∝ f k ∈∂X i log λ f k →X i (x ∂f k )
Notice that another reformulation also introduces a negation of the factors, giving rise to the min-sum algorithm.

When the variable are binary valued, i.e. A = {0, 1}, computing the messages for x = 0 and x = 1 is redundant. Therefore, another common simplification consists in only considering the log-ratios m X i →f k = log 0) , which enables to halve the computation cost without loss of information. The estimated max-marginal can then be retrieved such as:

µ X i →f k (1) µ X i →f k (0) , and similarly m f k →X i = log λ f k →X i (1) λ f k →X i (
x * i = arg max x∈{0,1} PX i (x) = H(log PX i (1) PX i (0) ) = H( f k ∈∂X i m f k →X i )
where H(x) = 1 x≥0 is the Heaviside function.

Extension to the "loopy" case

Though it has been originally designed to perform exact MAP inference on acyclic factor graphs, the max-product algorithm has been later extended to 'loopy' graphical models, i.e. models containing cycles. Surprisingly, the algorithm showed to provide excellent results on many complex models, such as turbo codes [START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1[END_REF], Markov random fields [START_REF] Tappen | Comparison of Graph Cuts with Belief Propagation for Stereo, using Identical MRF Parameters[END_REF], clustering [START_REF] Frey | Clustering by Passing Messages Between Data Points[END_REF] or several optimization problems [START_REF] Gamarnik | Belief Propagation for Min-Cost Network Flow: Convergence and Correctness[END_REF][START_REF] Bayati | Maximum weight matching via max-product belief propagation[END_REF][START_REF] Sanghavi | Message passing for maximum weight independent set[END_REF]. However, though particular model have been extensively analyzed [START_REF] Weiss | Correctness of Local Probability Propagation in Graphical Models with Loops[END_REF][START_REF] Weiss | On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs[END_REF][START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1[END_REF][START_REF] Meltzer | Globally Optimal Solutions for Energy Minimization in Stereo Vision Using Reweighted Belief Propagation[END_REF]Bayati, Shah, and Sharma, 2008;[START_REF] Zhang | Convergence of minsum-min message-passing for quadratic optimization[END_REF], the theoretical guarantees on the messages convergence, the exactness of the resulting maxmarginals as well as the optimality of the induced MAP are still missing for the general case. In particular, it is known that for some of these loopy graphs, the messages may never converge, or oscillate between multiple states over repeated iterations. Furthermore, excepted for few models, the messages may converge into local optima that does not actually correspond to the distribution of the max-marginals.

Network alignment via max-product belief propagation

This section is dedicated to the presentation of the original model of [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF], named NetAlign, designed to efficiently compute an approximate solution to the network alignment problem (NAP). We first introduce the factor graph corresponding to the constraint program NAP and show that finding the MAP of the model is equivalent to solving the alignment problem. We then introduce the update scheme that immediately follows from the message passing framework of [START_REF] Pearl | Reverend bayes on inference engines: a distributed hierarchical approach[END_REF] presented above.

Factor-graph

We first define the set of variable nodes in the factor graph:

X = {X ii ∈ {0, 1}, ii ∈ V A × V B }
These variables correspond to the matching vector x in NAP, that indicates if

function i ∈ V A matches function i ∈ V B .
We then introduce the different factor nodes. We distinguish the factors encoding the program constraints from the factors providing the energy to the objective function.

On one hand, the hard-constraints 3.1 of NAP are encoded through Dirac measures

f i : {0, 1} |∂f i | → {0, 1} and g i : {0, 1} |∂g i | → {0, 1} such that: ∀i ∈ V A , f i (x ∂f i ) = 1 if j ∈V B x ij ≤ 1, 0, otherwise. ∀i ∈ V B , g i (x ∂g i ) = 1 if j∈V A x ji ≤ 1, 0 otherwise.
where

x ∂f i = {x ij ∈ x, j ∈ V B }, and similarly, x ∂g i = {x ji ∈ x, j ∈ V A }.
On the other hand, the objective function of 3.2 is encoded via two sets of factor nodes h ii : {0, 1} → R + and h ii jj : {0, 1} 2 → R + , such that:

∀ii ∈ V A × V B , h ii (x ii ) = e x ii w ii ∀ii , jj ∈ (V A × V B ) 2 , h ii jj (x ii , x jj ) = e x ii w ii jj x jj
Clearly we have:

ii h ii (x ii ) ii jj h ii jj (x ii , x jj ) = e x T W x
By multiplying all the factors, we obtain the joint probability distribution of our graphical model:

p X (x) = 1 Z n i=1 f i (x ∂f i ) m i =1 g i (x ∂g i ) ii h ii (x ii ) ii jj h ii jj (x ii , x jj ) = 1 Z n i=1 f i (x ∂f i ) m i =1 g i (x ∂g i ) e x T W x (4.1)
where the normalization constant Z denotes the partition function of the model. It is clear that the support of the distribution 4.1 is equivalent to the set of feasible solutions in NAP. Furthermore, the mode of p X (x) corresponds to the optimal solution of the NAP.

We provide a representation of our graphical model in Figure 4.3. Notice that it slightly diverges from the one proposed by [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF] since our model does not include the variable nodes X ii ,jj , though it is provably equivalent. Notice that some possible assignments (for instance 1 → 3 ) may be arbitrarily excluded, if considered too unlikely. Each pair of correspondences with consistent topology (for instance 1 → 2 and 2 → 3 ) forms a potential square (shaded). It is thus provided with an additional factor node h ii jj that favors their simultaneous assignment (right).

Message updates

Given the factor graph introduced above, we may apply the message passing scheme of [START_REF] Pearl | Reverend bayes on inference engines: a distributed hierarchical approach[END_REF]. Denoting by m (t) the value of the message m after t iterations, we have the following updates: First, the messages from the factor nodes to the variable nodes:

λ (t) f i →X ii (x ii ) = max x ∂f i \{ii } f i (x ∂f i ) j =i µ (t) X ij →f i (x ij ) λ (t) g i →X ii (x ii ) = max x ∂g i \{ii } g i (x ∂g i ) j =i µ (t) X ji →g i (x ji ) λ (t) h ii →X ii (x ii ) = h ii (x ii ) λ (t) h ii jj →X ii (x ii ) = max x jj h ii jj (x ii , x jj )µ (t) X jj →h ii jj (x jj )
Then, the messages from the variable nodes to the factor nodes:

µ (t+1) X ii →f i (x ii ) = λ (t) g i →X ii (x ii )λ (t) h ii →X ii (x ii ) jj λ (t) h ii jj →X ii (x ii ) µ (t+1) X ii →g i (x ii ) = λ (t) f i →X ii (x ii )λ (t) h ii →X ii (x ii ) jj λ (t) h ii jj →X ii (x ii ) µ (t+1) X ii →h ii jj (x ii , x jj ) = λ (t) f i →X ii (x ii )λ (t) g i →X ii (x ii ) λ (t) h ii →X ii (x ii ) kk =jj λ (t) h ii kk →X ii (x ii )
Since x ii are binary valued, we may apply the log-ratio simplification introduced above. Then, it can be shown [START_REF] Bayati | Message-Passing Algorithms for Sparse Network Alignment[END_REF] that the messages from the factor nodes to the variable nodes simplify to:

m (t) f i →X ii = -max k =i m (t) X ik →f i + m (t) g i →X ii = -max k =i m (t) X ki →g i + m (t) h ii →X ii = w ii m (t) h ii jj →X ii = w ii jj + m (t) X jj →h ii jj + -m (t) X jj →h ii jj +
where we use the notations: x + = max(0, x).

Consequently, the message-passing framework reduces to the following updates:

m (t+1) X ii →f i = w ii + m (t) g i →X ii + jj m (t) h ii jj →X ii (4.2) m (t+1) X ii →g i = w ii + m (t) f i →X ii + jj m (t) h ii jj →X ii (4.3) m (t+1) X ii →h ii jj = w ii + m (t) f i →X ii + m (t) g i →X ii + kk =jj m (t) h ii kk →X ii (4.4)

Damping strategy

Since the graphical model of our framework contain cycles (see Figure 4.3), the theoretical properties applying to the acyclic case do not hold. In particular, the messages are not guaranteed to converge, and may instead fall into infinite loops and oscillate between few states [START_REF] Murphy | Loopy belief propagation for approximate inference: an empirical study[END_REF]. To overcome this issue, most practical implementations include a mechanism that enforces convergence [START_REF] Braunstein | Learning by Message Passing in Networks of Discrete Synapses[END_REF][START_REF] Frey | Clustering by Passing Messages Between Data Points[END_REF]. In their work, [START_REF] Bayati | Message-Passing Algorithms for Sparse Network Alignment[END_REF] propose a damping factor to mitigate the updates over iterations. The idea is to progressively reduce the contribution of the most recent updates to the messages values. Once this damping is sufficiently low, the message updates become insignificant, and the algorithm converges. Different damping strategies have been proposed. For instance, the default implementation of Netalign uses the following scheme:

m (t+1) X ii →f i ← γm (t+1) X ii →f i + (1 -γ)m (t) X ii →f i m (t+1) X ii →g i ← γm (t+1) X ii →g i + (1 -γ)m (t) X ii →g i m (t+1) X ii →h ii jj ← γm (t+1) X ii →h ii jj + (1 -γ)m (t) X ii →h ii jj
where decreasing parameter γ ∈ [0, 1] controls the influence of the computed updates on the current messages.

Rounding strategy

After each message-passing iteration, the algorithm must compute the current best solution based on the lastly transmitted messages, in order to evaluate the progress made by the updates, and decide to proceed or not the iterations. In other words, it must deduce a binary vector x based on the fractional values of the current messages (4.2)-(4.4). As explained in Section 4.1.2, such solution could be directly deduced from the current estimated the max-marginal distributions PX i . However, since our factor graph is loopy, the resulting assignment vector could not correspond to the actual MAP of the model. More specifically, it could violate the matching constraint and thus not belong to the solution set.

In their work, [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF] proposed several other binarization mechanisms, called "rounding strategies". The general idea is based on the concept of auction: it considers the messages m X ii →f i as the auctioning bid of graph A, i.e. as the current assignment preferences of graph A to map its nodes with those of graph B. Similarly, the messages m X ii →g i are assumed to be the best choice of graph B, given the one of graph A. Following this insight, the best current mapping according to graph A corresponds to the one-to-one assignment x which maximizes its preference scores or, in other words, to the solution of the following instance of the maximum weight matching instance (MWM):

x * =arg max x ii x ii m X ii →f i subject to x ∈ X
Similarly, the optimal choice of graph B may be computed by solving the same linear program with weights m X ii →g i . The proposed rounding strategy thus consists is retrieving the best assignment according to both messages m X ii →f i and m X ii →g i , and to compare their corresponding overall network alignment score. The assignment with the higher score is considered to be the current best solution.

As a result, this rounding strategy requires to solve two MWM problems after each iteration. Though it can be done in reasonable time, proceeding to this computational step after each iteration seriously slows down the algorithm. Aware of this limitation, the authors suggested to instead compute approximate solutions by running sub-optimal greedy matching algorithms such as the 1 2approximate matching of [START_REF] Preis | Linear time 1/2 -approximation algorithm for maximum weighted matching in general graphs[END_REF]. However, later works reported that these approximations actually harm the resulting network alignment score [START_REF] Khan | A multithreaded algorithm for network alignment via approximate matching[END_REF].

We must notice that this rounding strategy is immediately inspired from a previous model proposed by Bayati, Shah, and Sharma (2008). In fact, it has been shown that the MWM version of the graphical model, i.e. when α = 1 (or all m h ii jj →X ii = 0), the message passing scheme is equivalent to the auction algorithm of [START_REF] Bertsekas | The auction algorithm: a distributed relaxation method for the assignment problem[END_REF]. This algorithm is known to efficiently find the exact solution of the MWM problem when this later is unique. Though our model is quite different in the general network alignment case, this relationship may help to understand the messages mechanism and to propose some potential improvements. We discuss these in more details in Section 4.3.

Complexity

A key property of this graphical model is the local interactions of the message passing scheme. Indeed, the underlying structure of the factor-graph limits the propagation of updates to the connected components only, and therefore does not require a dense similarity matrix W . As a consequence, it enables to discard a priori some potential correspondences in W 1 that are considered too unlikely to be matched, and thus to arbitrarily reduce the size of the problem solution set. Furthermore, the model is particularly well fitted to leverage the potential sparseness of matrix W 2 , since only the messages m h ii jj →X ii with non-zero weight w ii jj must be updated. The quadratic summations in the above equations can thus be reduced to the only potential edge overlaps, which are of limited number for sparse graphs (see Figure 4.3).

This property is very useful to control the required computation cost and memory usage of large problem instances. Indeed, the computational cost of performing a single iteration of the message passing scheme (4.2)-(4.4) is in O(nnz(W 1 ) + nnz(W 2 )) where nnz(x) denotes the number of non-zero entries in x [START_REF] Khan | A multithreaded algorithm for network alignment via approximate matching[END_REF]. Moreover, due to the rounding strategy, each iteration terminates by solving two instances of the MWM problem, which can be done in O(nnz(W 1 )N + N 2 log N ) operations, where

N = |V A | + |V B |.

Proposed improvements

In this section, we introduce three different modifications of the original model of [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF], designed to respectively speed up the computation, halve the memory consumption and enforce the messages convergence. We summarize the proposed modifications by providing a pseudo-code of our algorithm named QBinDiff in Algorithm 1.

Solution assignment

We first propose to limit the heavy computational cost of the rounding strategy of NetAlign by introducing another simple assignment procedure. Our scheme is based on the current estimated max-marginals. In fact, as presented in Section 4.1, we propose to directly retrieve the most probable value of each variable X ii from the log-ratio of its max-marginal distribution PX i , such that:

xii = arg max x∈{0,1} PX ii (x) = H log PX ii (1) PX ii (0) = H w ii + m (t) f i →X ii + m (t) g i →X ii + jj m (t) h ii jj →X ii
Notice that, since our graphical model is loopy, there is no guarantee that the vector x = {x 11 , . . . , xnm } corresponds to the MAP of the joint distribution, even if the max-marginal PX ii were exact. In particular, the vector x may violate the assignment constraint, and thus not even belong to the solution space X . To overcome this issue, we ensure that the resulting solution determines a valid matching by removing the correspondences that map a node more than

W = αW 1 + (1 -α)W 2 /* initialize all messages to zero */ f ii ← 0 // m X ii →f i g ii ← 0 // m X ii →g i h ii jj ← 0 // m X ii →h ii jj x ii ← 0 // log PX i (1) -log PX i (0) while obj did not converge and n > 0 do /* compute the updates */ f ii ← w ii -max k =i g ki + -ζii + jj (w jj ii + h jj ii ) + -(h jj ii ) + g ii ← w ii -max k =i f ik + -ξ ii + jj (w jj ii + h jj ii ) + -(h jj ii ) + x ii ← f ii + g ii -w ii -jj (w jj ii + h jj ii ) + -(h jj ii ) + h ii jj ← x ii -h jj ii /* compute the current solution */ x * ii ← H(x ii ) /* compute current objective score */ obj ← ii jj x * ii (w ii + w ii jj ) x * jj n ← n -1 /* compute a complete solution */ x * ← MWM(x) return x *
once. This results in a partial mapping that provides a lower bound of the current objective score. After the last iteration, ie. when the objective score converges or the algorithm reaches the maximum number of iterations, the resulting assignment is augmented with less confident matches computed by solving a maximum weight matching instance on the max-marginal log-ratios of unmatched nodes (see Algorithm 1).

Such assignment procedure proved to provide comparable solutions, while greatly reducing the computational cost of NetAlign (see Figure 5.1 in Chapter 5).

Updates schedule

In addition to significantly reduce the computational cost of the original model, we propose to halve the memory consumption by introducing a simple update scheduling.

Though it was originally designed to compute and transmit the messages all at the same time, ie. in parallel (Pearl, 1988), the Max-Product algorithm has shown to perform very well on frameworks that use sequential (or asynchronous) updates [START_REF] Tappen | Comparison of Graph Cuts with Belief Propagation for Stereo, using Identical MRF Parameters[END_REF][START_REF] Wainwright | MAP estimation via agreement on trees: message-passing and linear programming[END_REF][START_REF] Elidan | Residual belief Propagation: informed scheduling for asynchronous message passing[END_REF][START_REF] Globerson | Fixing max-product: convergent message passing algorithms for MAP LP-relaxations[END_REF]. Meanwhile, different updating schemes inspired from auction processes were analyzed by [START_REF] Bertsekas | Parallel synchronous and asynchronous implementations of the auction algorithm[END_REF] and applied to its algorithm.

Following this idea, our scheduling tends to reproduce the bidding mechanism of an auction process. Usually, the different actors wait to see the preferences of their contenders, and update their prices accordingly. As suggested by [START_REF] Bertsekas | Parallel synchronous and asynchronous implementations of the auction algorithm[END_REF], this can be seen as a message passing mechanism. In our work, we propose to consider the different factor nodes as different bidding actors, and to compute the messages one after the other, such that every updates is based on the most recent available information. Formally, the messages (4.2)-(4.4) become:

m (t+1) X ii →f i = w ii + m (t) g i →X ii + jj m (t) h ii jj →X ii m (t+1) X ii →g i = w ii + m (t+1) f i →X ii + jj m (t) h ii jj →X ii m (t+1) X ii →h ii jj = w ii + m (t+1) f i →X ii + m (t) g i →X ii + kk =jj m (t) h ii kk →X ii
Experimental results show that our sequential update scheme slightly speedup the update computation and ultimately results in more accurate assignments. More importantly, since it overwrites the messages at each iteration, this update scheme halves the memory consumption required by the original framework.

Unfortunately, it appears that the order of updates depends on the sizes of both graphs. When the graphs to align are of different sizes, following the idea of auctioning, we suggest to first compute the messages from the smallest graph to the largest. For instance, the scheme given above assumes that n < m. On the contrary, if n > m, we suggest to first update the messages m

Auction based -complementary slackness

Last but not least, we propose a novel mechanism to enforce message convergence. Instead of the original damping scheme of Netalign, we introduce a slight perturbation on the local maximization of the factors based on the concept of -complementary slackness proposed by [START_REF] Bertsekas | The auction algorithm: a distributed relaxation method for the assignment problem[END_REF]. This relaxation has been originally proposed to run the auction algorithm on MWM instances that admit multiple optimal solutions. The idea is to prevent the saturation of the complementary slackness with a small constant margin. This scheme not only breaks ties and ensures the convergence but also provably converges to the optimal solution for a small enough [START_REF] Bertsekas | Auction algorithms for network flow problems: A tutorial introduction[END_REF]. Furthermore, for larger values, it shows to generally provide near-optimal assignments in much less computation time.

As previously mentioned, our model is quite different to a MWM instance in the general case. In order to adapt the idea of -complementary slackness to our message-passing scheme, we propose the following modifications:

m (t) f i →X ii = -max k =i m (t) X ik →f i + -ξ (t) ii m (t) g i →X ii = -max k =i m (t) X ki →g i + -ζ (t) ii
where:

ξ (t) ii = if m (t) X ii →f i = max k m (t) X ik →f i , 0 otherwise. ζ (t) ii = if m (t) X ii →g i = max k m (t) X ki →g i , 0 otherwise.
Unfortunately, this relaxation suffers from an important drawback: the value of the introduced must be chosen carefully. If set too small, the mechanism cannot fully play its part and the algorithm may reach a maximum number of iterations before converging. On the contrary, if too high, it could break ties too coarsely and strongly favor local optima that might appear to be poor global solutions. In this case, the algorithm could shortly converge to an unsatisfying assignment. In their work, [START_REF] Bertsekas | Auction algorithms for network flow problems: A tutorial introduction[END_REF] propose an iterative method, called -scaling, to properly setup the relaxation. It consists in repeatedly decreasing after the messages converged, until it reaches a small enough value, known to provide an optimal solution. In our work, we suggest the opposite scheme. The model starts with a rather small that helps to softly break local ties. Then, as the algorithm iterates, we propose to raise the relaxation value each time the messages have not improved the current objective function for few iterations. As rises, the messages are more and more likely to escape their local optimum and to fall into another better one. As soon as the current assignment improves, is set back to its original value, such that the new local solutions can be carefully explored. Note that a similar approach has been briefly discussed in [START_REF] Bertsekas | Auction algorithms for network flow problems: A tutorial introduction[END_REF].

In our experiments, this mechanism shows to significantly reduce the number of required running iterations as well as to significantly improve the overall final assignment score (see Figure 5.2 in Chapter 5).

Related work

Due to its high complexity, the different methods proposed to address the Network Alignment Problem largely depend on the problem instance, especially the size and the sparseness of the matrix W . According to our use cases, we only review in this section methods that apply to graphs of more than several hundred nodes in reasonable time. Therefore, the literature regarding exact solution of the NAP is omitted. More details about these methods can be found in [START_REF] Burkard | Quadratic assignment problems[END_REF].

Spectral methods

Amongst the first approaches to approximate the NAP are the spectral methods that can be distinguished into two main categories. On one hand, spectral matching approaches are based on the idea that similar graphs share a similar spectrum [START_REF] Umeyama | An Eigendecomposition Approach to Weighted Graph Matching Problems[END_REF]. Thus, they aim at best aligning the (leading) eigenvectors of the two affinity matrices (or Laplacians) [START_REF] Horaud | Rigid and Articulated Point Registration with Expectation Conditional Maximization[END_REF][START_REF] Patro | Global network alignment using multiscale spectral signatures[END_REF]. On the other hand, PageRank methods approximates the NAP through an eigenvalue problem over the matrix W [START_REF] Singh | Global alignment of multiple protein interaction networks with application to functional orthology detection[END_REF]. The idea consists in computing the principal eigenvectors of W , and to use it as a similarity score of every possible correspondence. The resulting assignment can then be computed using conventional MWM solvers. Over the years, several improvements have been proposed to enhance the procedure [START_REF] Kollias | Network Similarity Decomposition (NSD): A Fast and Scalable Approach to Network Alignment[END_REF][START_REF] Nassar | Low Rank Spectral Network Alignment[END_REF][START_REF] Feizi | Spectral Alignment of Graphs[END_REF][START_REF] Zhang | FINAL: Fast Attributed Network Alignment[END_REF].

Quadratic programming approaches

Other common approaches propose to directly address the quadratic program by means of relaxations. The most common convex relaxation consists in extending the solution set to the set of doubly stochastic matrices. The relaxed problem can then be exactly solved using convex-optimization solvers, and is finally projected into the set of permutation matrices to provide an integral assignment. However, when the solution of the convex program is far from the optimal permutation matrix, the final projection may result in an incorrect mapping [START_REF] Lyzinski | Graph Matching: Relax at Your Own Risk[END_REF]. Other approaches make use of a concave [START_REF] Zaslavskiy | A Path Following Algorithm for the Graph Matching Problem[END_REF] or indefinite [START_REF] Vogelstein | Fast Approximate Quadratic Programming for Graph Matching[END_REF] relaxations. The induced programs are generally much harder to solve but yield better results when properly initialized. Note that most methods use a combination of both relaxations [START_REF] Zhou | Factorized graph matching[END_REF][START_REF] Zhang | KerGM: kernelized graph matching[END_REF].

Linear programming approaches

Several other methods are based on a linearization of the NAP objective function. The idea is to reformulate the quadratic program into an equivalent linear program, and to solve it using conventional (mixed-integer) linear programming solvers. However, this reformulation usually requires the introduction of many new variables and constraints, and computing the exact solutions of the linear program may become prohibitively expensive. In most cases, relaxations must also be introduced. A successful method, based on the linearization of [START_REF] Adams | Improved linear programming based lower bounds for the quadratic assignment problem[END_REF] and using a Lagrangian dual relaxation have been proposed by [START_REF] Klau | A new graph-based method for pairwise global network alignment[END_REF] and later improved by [START_REF] El-Kebir | Lagrangian relaxation applied to sparse global network alignment[END_REF].

Message passing models

Finally, [START_REF] Bradde | Aligning graphs and finding substructures by a cavity approach[END_REF] introduced a belief propagation algorithm based on Bethe free energy approximation. Meanwhile, [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF] proposed a message passing framework that has shown promising results. This later is directly derived from a previous model that provided important results on solving the MWM using max-product belief propagation [START_REF] Bayati | Maximum weight matching via max-product belief propagation[END_REF]. In our work, we chose to apply this model to our use case..

Sparse models

Note that an important limitation to the NAP is the size of the matrix W that grows quartically with the size of the graphs. This memory requirement may become prohibitive for relatively large graphs encountered in many real-world problems. It is mainly due to the intrinsic nature of the problem which requires that every potential correspondence is evaluated with regards to other candidates, in order to take into account its topological consistency. In practice, most methods are designed to efficiently exploit the potential sparseness of the matrix W . Therefore, they generally apply to sparse graphs only. Moreover, several approaches propose to also restrain the number of potential candidates [START_REF] El-Kebir | Lagrangian relaxation applied to sparse global network alignment[END_REF][START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF] and thus the problem complexity. This pre-selection may rely on prior knowledge or on arbitrary decision rules. It mostly aims at preventing the algorithm to compute the assignment score of highly improbable correspondences. The framework we introduce in the next section makes use of this interesting feature.

In this Chapter, we provided a complete presentation of our proposed network alignment solver. In the following Chapters, we perform a series of experiment to assess the quality of our approach. In Chapter 5, we evaluate our method as a network alignment solver, and thus compare with other state-of-the-art methods with regards to the resulting objective scores. Then, in Chapter 6, we assess the relevance of our overall problem formulation to address the binary diffing problem by comparing the resulting matchings to true assignments. As a baseline, we compare to the two most common binary diffing tools, but also to different other matching approaches, as well as to other state-of-the-art function similarity measures.

Chapter 5

Network Alignment Experiments

In this chapter, we provide an evaluation of our proposed method as a network alignment solver. Therefore, we compare with other state-of-the-art approaches only with regards to the objective score of the resulting assignment. Our evaluation is twofold: we first perform a series of experiments on a set of randomly generated problem instances and compare the results according to the different problem configurations. Then we submit to all solvers a set of real-world problems commonly found in the literature. Our overall results show that QBinDiff outperforms state-of-the-art methods, and is much faster than its best competitors. As a consequence, it appears to be the best candidate to approximate the solution of our diffing instances.

Baseline

In this set of experiments, we compare our method to other state-of-the-art NAP solvers. We selected four competitors: Final, Natalie, NetAlign and Path, often considered as the reference method in their respective solving approach (see Section 4.4). All these solvers have been launched using the original source code implementation, and configured with their default parameters.

All the experiments have been conducted on an identical hardware1 .

QBinDiff

We provided a complete presentation of QBinDiff in the previous Chapter (see Section 4.3, or Algorithm 1). Recall that our solver is designed to approximate the following constrained integer quadratic program NAP:

x * =arg max x x T W x =arg max x αx T W 1 x + (1 -α)x T W 2 x subject to x ∈ X
In all our experiments, unless precisely mentioned, we run our method with default parameters: = 0.5, and within a maximum of 1000 iterations. Moreover, though we test different configurations, the default trade-off between node and edge similarity is set to α = 0.75. Notice that in order to ensure that every solver address the exact same alignment problem, we may adapt their respective trade-off parameter in order to meet the desired balance.

In this chapter, we refer to QBinDiff as the network alignment solver only, whereas, in the next chapter, it will designate the whole binary diffing framework, including the setup of call graph alignment problem, as well as the computation of all nodes and edges similarity scores.

Final

Following the idea of IsoRank [START_REF] Singh | Global alignment of multiple protein interaction networks with application to functional orthology detection[END_REF], [START_REF] Zhang | FINAL: Fast Attributed Network Alignment[END_REF] introduced an algorithm named Final which instantiates the network alignment problem as an eigenvalue problem and aims at finding the leading eigenvector of the association matrix W2 (normalized matrix W 2 ) in order to use it as a node similarity scores that includes topological information. They thus aim at maximizing the following penalized objective function:

J(x) = -α||x -diag(W 1 )|| 2 + (1 -α)x T ( W2 -I)x = -α(||x|| 2 + ||diag(W 1 )|| 2 -2x T W 1 x) + (1 -α)(x T W2 x -||x|| 2 ) =2αx T W 1 x + (1 -α)x T W2 x -||x|| 2 -cste
which lead to the relaxed and penalized formulation of NAP:

x =arg max

x x T W x -||x|| 2 subject to x ∈ [0, 1] |V A |×|V B |
where we set α = α 2-α such that the ratio between node and edge similarity remains the same as in our definition.

It can be shown that this problem reduces to an eigenvalue (PageRank) problem [START_REF] Feizi | Spectral Alignment of Graphs[END_REF]. As a consequence, it may be efficiently approximated by the iterative power method [START_REF] Nassar | Low Rank Spectral Network Alignment[END_REF]. However, the resulting vector x, corresponding to the leading eigenvector of W , consists in values in [0, 1], and as such, does not characterize a proper one-to-one assignment. In order to retrieve such correspondence x * , the authors suggest to finally solve the following MWM instance:

x * =arg max x x T x subject to x ∈ X
Notice that an interesting property of Final is the ability to leverage both nodes and edges contents in order to introduce additional constraints on the solution set and to ensure that matched elements share common features. In our experiments, in order to provide to all solvers the exact same problem instance, we did not use this property.

Natalie

Natalie is a linear programming approach proposed by El-Kebir, Heringa, and Klau (2015) that refers to the linearization of [START_REF] Adams | Improved linear programming based lower bounds for the quadratic assignment problem[END_REF].

The idea is to replace each quadratic combinations x ii x jj by a new variable y ii jj such that y ii jj ≤ x ii and y ii jj = y jj ii . In order to efficiently handle the resulting larger problem instance, the authors propose to relax these later symmetry constraints by introducing Lagrangian multipliers λ ii jj . As a result, the relaxed linear program becomes:

x * =arg max x min Λ max x,Y αx T W 1 x + (1 -α)W 2 • Y + Λ • (Y -Y T ) subject to ∀ii , jj , y ii jj ≤ x ii ∀i , jj j y ii jj ≤ 1 ∀i, jj j y ii jj ≤ 1 Y ∈ {0, 1} |V A | 2 ×|V B | 2 x ∈ X
where α is the exact same trade-off ratio than the one in our definition.

The interest of this rather heavy reformulation is that it can be noticed that both x and Y can be optimized successively by solving multiple smaller MWM instances.

NetAlign

Netalign is an alignment algorithm proposed by [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF]. It has been introduced in the previous Chapter (see Section 4.2).

Path

Zaslavskiy, Bach, and Vert (2009) proposed a path-following algorithm, named Path, that leverages a linear combination between two relaxations of the original problem NAP. The first relaxation simply expands the solution set of NAP to the set of doubly stochastic matrices, and thus consists in a convex quadratic program for which an optimal solution can be found efficiently. However, the resulting floating-point solution does not usually define a proper mapping. The second relaxation is based on a concave reformulation of the problem NAP. Though it is not easier to solve than the original problem, this reformulation ensures that any local solution would consist in a proper one-to-one correspondence.

The idea of Path is to iteratively track the local optima of NAP through a path of linear combinations of both problems, starting with the simply convex relaxation and ending with the strictly concave reformulation.

Notice that, in practice, Path refers to a slightly different formulation of the graph matching problem. Indeed, it aims at maximizing the following objective function:

J(X) =αx T W 1 x -(1 -α)||M A X -XM B || 2 =αx T W 1 x -(1 -α)(||M A || 2 + ||M B || 2 -2vec(X)(M A ⊗ M B )vec(X)) =αx T W 1 x -(1 -α)(||M A || 2 + ||M B || 2 -2x T (M A ⊗ M B )x) =αx T W 1 x + 2(1 -α)x T (M A ⊗ M B )x + cste
where we respectively denote M A and M B as the (potentially weighted) affinity matrices of graphs A and B, and X as the matrix form of x, i.e vec(X) = x.

As a consequence, this formulation is equivalent to ours only if matrix W 2 = M A ⊗ M B , which is the case in all the remaining experiments. Moreover, we here again set the parameter α = 2α 1+α in order to fit the desired trade-off between node and edge similarity.

Synthetic problems

Benchmark

We first evaluate the relative performances of our proposed algorithm on a set of synthetic network alignment problems. Though the generated graph samples appear to be unrealistic compared to actual call graphs, these instances enable us to closely analyze the behavior of the different solvers according to different graph properties. We chose to investigate four different parameters: the structural properties of the graphs, depending on the generative model the edge density of both graphs, controlled by parameter d the size of the subgraph common to both graphs, set by parameter n * the ratio of noise on both the nodes and edges of the graphs, ruled by parameters σ N and σ E . Moreover, we also analyze degenerate instances, where the best possible edge alignment does not fit with the best node content mapping.

In order to create these NAP instances, we follow a simple graph generation procedure. We first generate two attributed graphs A and B with an arbitrary number of nodes n A and n B , and an expected edge density d. We then replace an entire subgraph of n * nodes in B with another one, randomly selected in A. This subgraph includes both the nodes and their respective edges, and corresponds to the conserved interactions between the two graphs. Notice that, at this point, this later subgraph aligns perfectly: both its node contents and edges are exactly the same in both A and B. Therefore, we finally randomly regenerate a portion σ N of nodes and σ E of edges in B using the same generative model. This perturbation adds noise to the conserved interactions.

In order to properly analyze their effect on the resulting assignments, we modify the parameters of our generative model one after the other. Default parameters are n A = 500, n B = 650, d = 0.01, n * = 400, σ N = 0.15, σ E = 0.15. For each different configurations, we generate five problem instances and average the resulting scores.

In our experiments, we generate our samples using three different random graph generation models. The model proposed by [START_REF] Erdös | On the evolution of random graphs[END_REF] generates edges with equal probability and thus usually results in rather homogeneous graphs with binomial degree distribution. On the contrary, the generative model of [START_REF] Albert | Statistical mechanics of complex networks[END_REF], also known as Powerlaw model, generates scale-free networks, where few nodes are likely to have much more edges than the average. These graph structures are closer to observed call graphs. Finally, we introduce a custom graph generation model named Motifs. This model concatenates a set of small subgraphs sampled from a collection of randomly generated Erdős-Rényi graphs. Therefore, it results in graphs with multiple recurrent substructures (motifs) connected with each others by few edges. Though the resulting graphs are not realistic, the induced alignment problem is more likely to include several common subgraphs and therefore several local optima.

Results

An overview of our experimental results is provided in Figure 5.1. It shows that in almost every configuration, QBinDiff outperforms or nearly ties the best state-of-the-art approaches. Moreover, it appears to perform well on all three graph generation models whereas other approaches seem to be best suited for particular graph layouts. For instance, Path generally provides the secondbest solution on Erdos-Renyi graphs, while NetAlign is the best competitor on scale-free networks. This result is consistent with the solving strategy of both approaches, since Path seeks a global solution to the (relaxed) NAP problem and therefore performs well on balanced graphs, whereas NetAlign propagates local optima information and thus matches well highly connected nodes.

Our experiments also show that our method is more robust to perturbation on both node contents and edges than its competitor (see Figure 5.1a). In fact, it seems to be less likely to fall into poor local optima induced by the noise. In particular, QBinDiff proves to provide much better solutions on very noisy instances, where the node similarity scores can only be misleading. This result holds when comparing the solvers' solutions according to the structural consistency of the two graphs to be aligned (see Figure 5.1b). However, it appears that QBinDiff performs similarly to its competitor when the graphs are structurally very similar. Regarding the density of the graphs, QBinDiff appears to be slightly better on very sparse graphs in comparison to other methods (see Figure 5.1c). More importantly, it scales much better than NetAlign, which computation time quickly becomes prohibitive, even on these rather small problem instances. Finally, it appears that QBinDiff performs well for every trade-off parameter α, which means that it relies on a balanced strategy between matching similar nodes and aligning edges (see Figure 5.1d). Surprisingly, this observation does not hold for NetAlign that seems to mostly maximize the node similarity scores, neglecting the induced edge consistency. This result holds when comparing the results on the degenerate instances, where QBinDiff provides much better assignments for all three graph generative models.

Real world problems

Benchmark

In a second set of experiments, we evaluate the performances of QBinDiff on five real-world network alignment problems commonly found in the literature (see Table 5.1). In fact, all these instances have been introduced along with one of the competitor solvers in our evaluation. In order to analyze the ability of each solver to provide proper solutions both in terms of node content and number of overlapping edges, each problem was submitted multiple times, with different trade-off parameters.

We must notice that some problems include a similarity score matrix with several zero entries. In some models (QBinDiff, NetAlign, Natalie), those entries are considered as unfeasible matches whereas they are legal correspondences in others. Therefore, these models would optimize the problem on a subset of all possible one-to-one mappings.

Finally, in order to ensure that every solver were submitted the same problem, we did not take into account edge features when available. As a result, each problem instance consists in a pairwise node similarity matrix X such that vec(X) = diag(W 1 ) as well as two unweighted affinity matrices M A and M B .

Results

Our results show that our approach outperforms or nearly ties the other existing methods on every problem (see Table 5.2). It appears to provide better results on sparse graphs, while it may compute slightly suboptimal assignments on densest ones (1EWK-1U19). As observed in the synthetic experiments, it is also the best fitted to perform diffing at different arbitrary settings of the trade-off parameter α, even in the degenerated MCS case α = 0, where it provides significantly better assignments than the other approaches.

We then compared the different proposed modifications of NetAlign according to the quality of the current solution over iterations (see Figure 5.2). This analysis shows that the -relaxation continuously looks for better local optima whereas the common max-product updates do not significantly improve the current solution over time. Moreover, it seems to best enforce convergence than the original damping strategy. Finally, it appears that our proposed assignment strategy does not harm the final assignment score while it seriously reduces the required computation time.

In terms of computing time, as expected, QBinDiff takes much less time to approximate the NAP than NetAlign. This is mostly due to the different assignment strategies. Regarding other solvers, Final performs faster, but ends up with less valuable assignments, while the computation time of Natalie greatly depends on its convergence, but seems to scale reasonably to large graphs. Conversely, Path tends to be very expensive, and may become prohibitive for larger problem Matcher α = 0 α = 0.25 α = 0.5 α = 0.75 α = 0.9 instances. Note that it was not able to provide a solution to the Flickr-Lastm problem when α = 0.25 within 8 days, and was thus considered timed-out. Of course, these timings depend on the quality of the implementation and should only be considered with respect to their order of magnitude.

In this Chapter, we evaluated our framework as a network alignment solver and showed that it outperforms other state-of-the-art method both in terms of alignment scores and required computation time. However, such evaluation does not provide any guarantee on the relevance of our approach to address the binary diffing problem. In the next Chapter, we assess the quality of the resulting assignment as approximate solutions of the binary diffing problem by comparing to actual true solutions.

Chapter 6

Binary Diffing Experiments

In the previous set of experiments, we showed that our proposed solver is very well suited to address network alignment problems on graphs of several thousand nodes. In this chapter, we assess the relevance of formulating the binary diffing problem as a network alignment problem. Therefore, we no longer focus on objective scores, but now evaluate the ability of different methods to provide relevant correspondences to diffing instances. We thus compare the resulting assignment with the expected true assignment known as "ground truth", and consider accuracy metrics.

Baseline

As mentioned in Section 2.2, any diffing process requires a formal measure of code similarity, as well as a proper matching criterion. Both play an important role in the quality of the resulting alignment. On one hand, a perfect measure of function semantic similarity would produce univocal scores that immediately induce the pair of functions to be matched, whatever the matching criteria.

Unfortunately, determining the semantic similarity of two pieces of code is a complex problem and, to our knowledge, no such perfect measure has been proposed yet. On the other hand, even though we could efficiently compute the exact solution of the GED problem, its relevance would still heavily depends on the quality of the chosen function and edge similarity measure, as well as on the chosen trade-off parameter α. As a consequence, a careful evaluation of a binary diffing method should be able to distinguish the benefit induced by the similarity measure as well as the matching criteria.

In our experiments, we compare the resulting assignments of the different function matching strategies outlined in Chapter 2.2.3, as well as the two most common binary diffing tools. In order to evaluate the incidence of the similarity scores on the resulting mapping, we also leverage three state-of-the-art function similarity measures and combine them to the different matching approaches to generate synthetic differs.

Function similarity

We first present the different measures of function similarity that we refer to in our experiments.

QBinDiff

We presented our measure of function similarity in Section 3.4.2. It consists in a quite simple metric based on syntactic features. Recall that, in order to properly compare different methods, we use a 0 and 1 edge similarity measure and set the cost of node and edge insertion and deletion to 1 2 , which is sufficiently high to produce complete mapping. [START_REF] Xu | Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection[END_REF] introduced Gemini, a Siamese graph neural network to learn the common features of two semantically similar functions. It consists in an embedding model, trained to transform a very simple syntactic representation of the function instructions as well as the basic block layout of the CFG into a metric space where semantically similar functions are likely to have close coordinates. Once every function representation is projected into this metric space, pairwise similarity scores can be computed very efficiently using common vector-based distance computation routines.

Gemini

GraphMatching

Following the idea of Gemini, [START_REF] Li | Graph Matching Networks for Learning the Similarity of Graph Structured Objects[END_REF] proposed GraphMatching, designed to enhance the model with an attention mechanism based on the structure of both function CFGs. However since it actively uses the topology of both graphs during the similarity score computation itself, GraphMatching can not benefit from fast vector-based distance computation as Gemini does. In fact, the computational cost induced by the proposed attention mechanism rises quadratically with the number of basic blocks in both functions. Therefore, the computation of the similarity score between two large functions may easily take several seconds. As a consequence, the time required to compute all pairwise similarity scores may rise significantly with the number of functions in both binaries but also with the number of basic blocks in each function. [START_REF] Duan | DeepBinDiff: Learning Program-Wide Code Representations for Binary Diffing[END_REF] introduced DeepBinDiff, an unsupervised learning model that embeds each basic block based on its content but also on the one of its closest neighbors. In order to encode the content of a basic block, its constitutive instructions are embedded and averaged into a vector representation using an unsupervised model similar to Asm2Vec [START_REF] Ding | Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization[END_REF]. Then, the authors propose to complete this embedding with topological information, by leveraging the text-associated DeepWalk algorithm (TADW) [START_REF] Yang | Network representation learning with rich text information[END_REF] on the inter-procedural control-flow graphs (ICFG). However, the TADW algorithm is originally designed to perform network representation learning, i.e. to provide a vector representation of each node in a single network, whereas the diffing problem includes two binaries and thus two ICFGs. To overcome this issue, DeepBinDiff first merges the ICFG of both programs based on the available binary symbols.

DeepBinDiff

Notice that this approach is designed to proceed the diffing at a basic block granularity, whereas ours seeks a mapping between the functions of each binary. Therefore, we produce function embeddings by averaging the vector representation of its constitutive basic blocks. Notice that other embedding aggregation functions could also have been used, such as a min, max, etc.

Function matching

Then, we introduce the different matching strategies that will be compared.

Network alignment

In order to address the network alignment problem (NAP), we use QBinDiff, the approximate solver presented in the next chapter, with default parameters: α = 0.75, = 0.5, and within a maximum of 1000 iterations.

Maximum weight matching

Both Gemini and GraphMatching are originally designed to produce efficient semantic similarity scores in order to perform near-duplicate retrieval of functions. Therefore, a natural approach to use them to address a diffing problem would arguably leverage a maximum weight matching (MWM) matching strategy. Such a problem can be solved exactly by conventional optimization solvers. In our experiments, we use a standard implementation of the Hungarian algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF].

Maximum common edge subgraph

DeepBinDiff suggests to use a matching strategy that reduces to an instance of the maximum common edge subgraph problem (MCS). In fact, it proposes an iterative matching algorithm very similar to the VF2 algorithm of P. [START_REF] Cordella | A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs[END_REF], known to efficiently provide approximate solutions to the MCS problem. In our experiments, we based our implementation on the one of DeepBinDiff (see Algorithm 2). However, since a CG is usually much more dense than a ICFG, we limited the neighbor parameter k to 2. Note that, to output a complete mapping, the algorithm terminates by applying a MWM solver to the set of unmatched correspondences.

Notice that VF2 is a linear-time approximate algorithm and may actually result in assignment quite far from the optimal solution. In particular, it is highly sensitive to the provided initial mapping, which is usually based on arbitrary considerations. In our experiments, this initialization matches functions with the same name (such as imported functions), or functions with the exact same content.

Integrated differs

We finally compare to what we call integrated differs, i.e. state of the art diffing tools for which the matching strategy is closely related to the function similarity

/ X * ← X * ∪ {(j, j )} X ← X ∪ {(j, j )}
/* get all remaining unmatched candidates */ (J, J ) ← GetUnmatched() /* complete mapping with a maximum weight matching */ X * ← X * ∪ MWM(W 1 [J, J ]) return X * measure based on expert heuristics. In these cases, it does not seem relevant to distinguish both steps as we propose to do for the rest of the differs.

BinDiff

BinDiff [START_REF] Dullien | Graph-based comparison of executable Objects[END_REF] is a closed source state-of-the-art binary diffing tool that uses a MCS matching strategy based on different, non-public, function similarity heuristics.

Diaphora

Diaphora1 is an open-source differ, which initially attempted to reproduce BinDiff features and recently proposed new ones. In order to compute an assignment, it uses a greedy matching approach close to the 1 2 -approximate matching algorithm of [START_REF] Preis | Linear time 1/2 -approximation algorithm for maximum weighted matching in general graphs[END_REF], known to provide suboptimal solutions to the MWM problem.

Training

Gemini and GraphMatching are supervised learning models that require to be trained on multiple pairs of functions labeled as similar or different. As the manual construction of such a dataset is tedious, existing methods usually use a collection of functions extracted from slightly mutated programs, such as different versions of an executable. Then, a pair of functions is labeled as similar if they share the same (or very similar) name, and dissimilar otherwise.

We applied this training protocol to our dataset. Notice that this should give a small competitive advantage to the differs based on Gemini and GraphMatching as their similarity measures will be optimized on the specific type of functions found in the binaries under study (described in Section 6.2).

During the training process, we collected 85680 samples of 7276 different functions from the unstripped binaries. 80% of them were used as training examples, 10% as a validation set, and the remaining 10% were used to assess the final accuracy of the trained models. Both models were trained using their recommended hyper-parameters. To compute the similarity score of two embedded vectors, Gemini uses a cosine similarity measure, whereas GraphMatching refers to a normalized euclidean metric. After the training, the models respectively provided an estimated AUC2 of 0.968 and 0.939.

We also trained DeepBinDiff instruction embedding model on each binary of our dataset, following the protocol and the recommendations of the corresponding article [START_REF] Duan | DeepBinDiff: Learning Program-Wide Code Representations for Binary Diffing[END_REF]. As DeepBinDiff provides embeddings of basic blocks, we represent each function by the average of all its basic block embeddings.

Benchmark

A diffing approach can be evaluated by comparing the mapping results with "true" assignments, known as the ground truth. Unfortunately, such assignments are not readily available and may be in fact very difficult to determine in an objective way. As part of this thesis, we have built a new benchmark that will be released to the research community.

Preliminary

The determination of the ground truth correspondences between two binary executables is a very challenging problem. In fact, whereas we could arguably map all semantically equivalent pieces of code with each others (although assessing their equivalence is theoretically infeasible [START_REF] Haq | A Survey of Binary Code Similarity[END_REF]), determining the alignment of the remaining functionally divergent parts necessarily refers to subjective considerations.

First, to the best of our knowledge, there is no universal criterion that determines if a function is more likely to result from the modification of one or another pieces of code. Therefore, any correspondence between two semantically different functions is based on a arbitrary definition of semantic similarity.

Moreover, the ground truth mapping between the functions of two programs is not necessarily complete. Indeed, some functions in binary A could have been removed whereas some in program B could have been added. Therefore, each unmatched function induces an ambiguous assignment choice that also requires an arbitrary rule. It must assess to what extent this function is not sufficiently similar to its best candidate to be considered the consequence of a modification. Notice that this ambiguity is closely related to the redundancy of the substitute operation with the delete then insert scheme in the graph edit distance problem.

Although in many cases, it is impossible to determine a unanimous best assignment among the functions of two arbitrary binaries, one may significantly reduce the subjective bias by considering other sources of information.

Indeed, during its implementation, a source code is often enriched by humanreadable symbols such as function names, argument types, strings, comments, etc. These textual information can be seen as a rather reliable description of the actual intents of the program creator and may provide useful indications concerning the purpose of each function. For instance, we may argue that in general, even if they might be semantically distant, two functions that share the same name, should encode the same functional utility, at least from the developer's point of view. In other words, instead of a custom interpretation of the semantic similarity of two programs, we may extract the actual function mapping by considering the potential motives of the developer following these textual information. Notice however that such consistent denomination may be only available in closely related programs, either in different versions of a same executable or, more rarely, in different programs implemented by the same developers. Notice that these information may not be found in binaries including some sort of protection against reverse engineering, such as stripped or obfuscated programs.

In addition to the source code documentation and symbols, some repositories include detailed commit descriptions that precisely record the different modifications from a version to another. These information may also give major insights on the function semantic relations along different program versions. However, they almost always refer to the modifications occurring during a release, and are thus available for successive versions only.

Therefore, in order to design an experimental dataset made of multiple pairs of executables from which the ground truth functional correspondence is available, we restrict to the diffing of different versions of a same program. We then determine the ground truth assignment by hand, with the help of the available human-readable information.

Notice that another possible approach to design such a benchmark would have been to compare the same program in two different syntactic representations. Such samples could be obtained, for instance, in compiling the same source code with different optimizations or target architectures, but also in performing code modifications such as obfuscation. The interest of this approach is that the ground truth assignment is relatively easy to determine. However, it only enables to compare semantically equivalent programs, and hence mostly relies on the quality of the measure of function similarity.

Benchmark design

According to the previously exposed considerations, we selected programs to include in our benchmark, based on several requirements. First, the source of the programs should be made readily available, within several different versions. This enables us to compile the program with symbols and thus to ease the determination of the ground truth. Second, well-maintained source repositories with explicit commit descriptions, detailed changelogs, as well as a relatively consistent function denomination over time are also very important features for the ground truth extraction. Third, since our evaluation method requires a timeconsuming manual extraction, we must restrict our experiments to programs of "reasonable" size.

We thus chose three well-known open source projects to compose our experimental dataset, namely Zlib3 , Libsodium4 and OpenSSL5 . Note that some of these programs are amongst the most frequently used for evaluation in the literature [START_REF] Haq | A Survey of Binary Code Similarity[END_REF].

For each of these projects, we first downloaded the official repository, then we compiled the different available versions using GCC v7.5 for x86-64 target architecture with -O3 optimization level and keeping the symbols. Once extracted, each binary was stripped to remove all symbols, then disassembled using IDA Pro v7.2, and finally exported into a readable file with the help of BinExport This extraction protocol provided us with respectively 18, 33 and 17 different binary versions. For each project, given n different versions of the program, we propose to evaluate our method in diffing all the n(n-1) 2 possible pairs of different executables. Statistics describing our evaluation benchmark are given in Table 6.1.

Few remarks can be made regarding our resulting dataset. First, the average graph size of the project programs varies with around 150 functions in Zlib, 600 in Libsodium and over 4000 in OpenSSL. Moreover, the sparseness of the call graphs also depends on the project. For instance, both Zlib and Libsodium are extremely sparse with a mean degree of around 1.5 whereas OpenSSL counts on average a bit more than 5 edges per node. This variety will provide insights on the scalability of the diffing methods under study as well as the effect of sparsity on our solver. Last but not least, one may notice an important gap in the number of both nodes and edges following the release of OpenSSL 1 1 0. This difference is explained by the removal of several deprecated functions, as it is usual for major releases, but mostly by the migration of many cryptographic primitives into the related library LibSSL. In our experiments, we chose to preserve our dataset unchanged in order to evaluate the different approach behaviors in these particular cases.

Ground Truth

Our ground truth extraction protocol has two steps. We first manually determine what we think to be the function mapping that best describes the modifications between two successive binary versions. This process is done with regards to the Changelogs files, the source code and the unstripped binaries. Excepted for few major project modifications, almost all the functions are mapped from a version to its successor (see Table 6.1).

Once all the contiguous version ground truth mappings are extracted, we deduce all the pairwise diffing correspondences by extrapolating the mappings from version to versions. Formally, if we denote X A 1 →A 2 the mapping between program versions A 1 and A 2 into a boolean matrix such that vec(X A 1 →A 2 ) = x A 1 →A 2 , then, our extrapolating scheme simply consists in computing the diffing correspondence between A k and A n as follows:

X A k →An = n-1 i=k X A i →A i+1 .

Results

The quality of a diffing result is measured using its precision and recall with respect to the ground truth. We refer to the standard definitions of precision and recall i.e. p = |M ∩G| |G| and r = |M ∩G| |M | where M and G respectively correspond to the set of matched function pairs in the computed and ground truth assignments. Note that, except for BinDiff, all the evaluated methods are designed to produce a complete mapping. In fact, none of them includes a mechanism to limit the mapping of the most unlikely correspondences during computation. Therefore, these matching strategies do not consider precision but only focuses on recall. In future work, we will investigate the effect of rising the node insertion/deletion operation costs d i, and d ,i in order to favor the solution's precision score.

Overall results

In a first set of experiments, we instantiate all diffing instances with our proposed similarity measures. We thus evaluate the resulting accuracy scores for the three matching approaches, given the exact same information. We also compare the relevance of the resulting mappings to the two most common integrated differs, as well as to the state-of-the-art network alignment solvers introduced in the previous chapter.

Performance of the matching strategy

Our experiments show that QBinDiff generally outperforms other matching approaches in both precision and recall (see Table 6.2). In fact, our method appears to perform clearly better at diffing more different programs, whereas it provides comparable solutions on similar binaries (see Figure 6.1). This highlights that the local greedy matching strategy of both MWM and MCS is able to provide good solutions on simple cases but generalizes poorly on more difficult problem instances. This result should be view as promising in the perspective of diffing much more different binaries.

Performance of the integrated differs

Regarding the common diffing tools, it appears that they provide partial assignments with slightly better precision scores but lower recall. In fact, as they do not match functions with low content similarity, they only provide likely correspondences and miss more tricky ones, resulting in another trade-off between precision and recall.

Performances of other network alignment solvers

We also submitted the diffing instances to other network alignment solvers. In order to compare the resulting assignments of each solver for all instances at once, we normalized the node similarity score as well as the number of edge overlaps by the ones of the solution of QBinDiff (see Table 6 all problem instances. In fact, it appears that QBinDiff efficiently leverages a balanced matching strategy whereas other methods seem to mostly optimize either only node or edge similarity scores, resulting in lower overall alignment score. Regarding the accuracy of the resulting mappings, it seems that solutions with higher network alignment scores are also the ones with higher sensitivity (or recall), whereas only maximizing node or edge similarity scores appears to provide less accurate assignments. As a consequence, our proposed alignment solver clearly appears to be the best suited to compute diffing correspondences.

Parameter selection

We also performed a series of experiments in order to find the parameter setup that provides the best results. We evaluate both the trade-off parameter α and the complementary slackness relaxation at different levels and reproduce the resulting accuracy scores in Figure 6.3. Notice that we did not evaluate the parameter in charge of controlling the size of the solution set by removing the less probable correspondences since this later mostly depends on the memory limitation and is set to 0 for the smaller programs ZLib and Libsodium. Experiments show that our network alignment formulation provides better results with a relatively high parameter α, between 0.75 and 0.9 (see Figure 6.3a). This means that the matching strategy should mostly rely on the function similarity score and not overestimate the influence of the consistency of the calls. Meanwhile, a strategy only based on the function content (α = 1), equivalent to the MWM approach, clearly results in suboptimal assignments (see also Table 6.2). These experiments highlight the benefit of our balanced matching strategy over common MCS or MWM ones. We may also notice that programs with a higher edge density require a higher trade-off parameter. This is consistent with the fact that densest graphs mechanically include more potential edge overlaps and thus the relative weight of node similarity decreases. As a consequence, it In almost all problem instances, QBinDiff provides better assignments than its competitors. In particular, most other methods appear to compute solutions with a high node similarity score but much less induced edges. On the contrary, Natalie seems to retrieve a high number of edge overlaps with a low overall node similarity score.

appears that, to some extent, the optimal trade-off parameter α depends on the density of the call graph. We discuss this property in the next chapter. Interestingly, different configurations of the relaxation parameter appears to result in quite similar accuracy scores (see Figure 6.3b). In fact, it seems that the relaxation is mostly managed by the -scaling scheme introduced in the previous chapter and thus simply requires a certain number of iterations to reach the critical level that enables the current messages to switch from one local optimum to another. Notice that, although the results are quite similar, the required computational time may strongly vary with the parameter and that a high value of will significantly accelerate the messages convergence.

Accuracy of the optimal solutions

An interesting analysis consists in comparing the different matching method assignments to the ground truth correspondences in terms of function similarity score and call graph alignment. Once again, we may display the relative performances of the different strategies on every instances by normalizing the resulting scores by ones of the ground truth assignments (see Figure 6.4). It appears that both Zlib and OpenSSL ground truth assignments are near-optimal in both maximum weight matching and maximum common edge subgraph scores. This observation is consistent with our experimental results that show that a balanced network alignment matching strategy provides better accuracy results than other approaches. More importantly, it justifies our intuition that the proposed problem formulation as a network alignment problem is very well suited to address the binary diffing problem. However, in some cases, Libsodium's For Zlib and OpenSSL binaries, the ground truth seems to be a near optimal NAP assignment in almost all cases. This result does not hold for Libsodium, as in some cases, assignments computed by QBinDiff are better in both function similarity and number of induced squares.

correct assignments show to be sub-optimal in both function similarity and graph topology. In these cases, the ground truth mappings are inconsistent in both function content syntax and invoked call procedures. We investigated these cases, and noticed that over the versions, several functions were split in two such that a first trivial function is solely designed to access a second core function actually containing the whole function semantic. As we largely determined our ground truth based on function names, we mapped full functions into their newly created accessors. We discuss these specific cases in the next chapter.

Results with different similarity measures

In order to evaluate the actual benefit of our matching approach on binary diffing problems, we reproduced our experiments with different function similarity measures. We thus generated several synthetic differs, each of which uses a particular measure of similarity to setup the problem, as well as a particular matching strategy to find a solution.

Predominance of the matching strategy

As observed with our custom metric, our network alignment strategy (NAP) provides better assignments than other matching approaches. Furthermore, it appears that in almost all cases, the chosen matching method has more influence than the similarity metric, i.e. that it is more beneficial to switch the matching strategy to NAP than to change the measures of similarity (see

Misleading similarity measures

Surprisingly, it appears that the use of these complex models does not actually improve the accuracy of the resulting mapping, and might even worsen it in some cases. Since the topology of the graphs does not change, this means that the computed similarity scores are not consistent with the actual ground truth assignment. By comparing the similarity scores of the pairs of functions in the ground truth with all other scores, it appears that both Gemini and GraphMatching models very accurately retrieve similar functions, but strongly deteriorate the similarity scores of more diverging ones (see Figure 6.5). This is consistent with the original purpose of both models and with the training dataset which labels as completely different two similar functions with different names. In the case of DeepBinDiff, it seems that the scores of ground truth correspondences are distributed relatively uniformly over the cumulative distribution function, which means that the model itself does not provide sufficiently discriminative scores, and thus leads to erroneous assignments. As previously mentioned, our experiments also suggest that our rather basic function similarity metric provides scores that are consistent with the actual ground truth assignment (see Figure 6.4). Moreover, on the contrary to supervised learning models Gemini and GraphMatching, it produces less discriminative scores. Though it might be view as a less informative metric, it appears that this keeps the ground truth correspondences similarity scores at a satisfying level and ultimately results in better solutions (see Figure 6.5).

Runtime comparisons

Finally, we recorded the computing time of each method. As could be expected, it takes much more time to approximate the NAP of two graphs than to compute the MWM or the MCS (see Table 6.2). However, this can be controlled by raising the sparsity ratio parameter ξ, at the cost of limiting the problem solution set and potentially resulting in sub-optimal assignments. Furthermore, QBinDiff shows to run much faster than its best alignment solver competitors. In fact, it appears to be the only one able to provide satisfying results in reasonable time for large problem instances.

Regarding the processing times, it appears that, whereas the use of Gemini model does not harm the required time, both GraphMatching and DeepBinDiff take very long time to compute the pairwise similarity scores, which might be prohibitive for larger programs (see Table 6.4). Moreover, it seems that better similarity scores speed up the computation. This is due to the fact that the algorithm finds more easily a satisfying local optima (see Table 6.3). Notice that we were not able to compute DeepBinDiff embeddings on OpenSSL binaries in reasonable time. Indeed, these problem instances involve the factorization of the adjacency matrices of graphs of over 100 000 nodes which is a very computationally intensive task.

In this Chapter, we evaluated our proposed approach to address the binary diffing problem. Experimental results showed that our method outperforms other state-of-the-art methods in almost all diffing instances. Therefore, it suggested that our problem formulation is well fitted to address our problem. Furthermore, it also highlighted that the matching strategy has more influence on the quality of the resulting assignment than the choice of the function similarity measure. Finally, it appeared that using similarity metrics originally designed to retrieve near-duplicate functions might actually harm the quality of the resulting mapping. In the next Chapter, we discuss some limitations of our method as well as some threats to the validity of our evaluation. We finally mention some possible enhancements.

Chapter 7 Discussions

Limitations

While it improves the state-of-the-art, our method still includes some limitations and could be further enhanced.

One-to-many correspondences

A first limitation is that our approach is designed to find a one-to-one correspondence between the functions of both programs. Thus, it can not properly handle cases where a function in a binary is split into several ones in the other program, or similarly, multiple functions are merged into a single one. In such cases, the information of both the function syntax and its call graph relations is diluted into multiple chunks and may be harder to retrieve. Notice that, to our knowledge, this problem is common to all other diffing methods, and that in practice, many function splits result in a core function containing most of the semantic information, and few trivial functions that are immediately called before or after it (as in the Libsodium programs). Such schemes could be handled by a pre-processing step.

Edit operation costs determination

The other key property of our approach is that it is based on the assumption that the true expected mapping is the optimal solution to the graph edit distance problem. Although it is partially validated by our limited-sized experiments, there is no general available result that proves that this intuition is verified in practice, especially for more complex cross-compiler or cross-architecture diffing instances. One may argue that, due to the versatility of the graphedit distance problem, one may always define the graph edit operation costs such that the optimal edit path meets the actual ground truth assignment. However, in practice, there is no known function similarity metric that correctly encodes function semantic, and therefore, the actual benefit of our approach is to efficiently leverage the call graph structure of both programs. As a consequence, our method mostly relies on programs with rather similar call graphs.

Furthermore, our method enables to balance the relative influence of both node and edge similarity scores on the resulting solution. As highlighted in our experiments, this trade-off actually depends on the density of the graphs, since denser graphs mechanically induce more potential edge overlaps. As a result, the choice of the trade-off parameter α requires human expertise and prior knowledge about the binaries under analysis. In future work, we plan to introduce a normalization process in matrix Q 2 to ease the parameter selection.

Finally, in this work, we presented our method with deletion and insertion operation costs d i, = d i, = 1 2 . In fact, setting these costs this high enforces our network alignment solver to produce a complete mapping from the smallest graph into the largest, since any node substitution would be always provide more benefit than a node deletion followed by a node insertion. An immediate consequence of this property is that QBinDiff does not include any mechanism to improve the assignment precision score. This issue could be overcame by lowering the costs of both deletion and insertion operations

d i, = d i, = 1 2 -ξ 2
, or in terms of network alignment problem, by penalizing the node similarity scores w ii = -d i,i + d i, + d ,i = s i,i -ξ. As a result, correspondences with negative similarity scores would belong to the final mapping only if they induce enough induced edge similarity.

Memory usage limitation

An important drawback of our problem formulation is that it requires a matrix W ∈ R |V A | 2 ×|V B | 2 which memory requirements grow quartically with the size of the graphs. Though we proposed to significantly reduce the problem size by limiting the solution set to the most probable correspondences, this heuristic inevitably induces some information loss, especially for large graphs where the relaxation must rise consequently. In practice, binaries of several thousand functions can be handled efficiently. For larger programs, it might be better to first partition the call graphs into smaller consistent subgraphs, and then proceed the matching among them. Although this partition is not trivial and might result in important diffing errors, it can be quite natural in modern programs for example following its modules.

Threats to validity

Internal validity

Our evaluation relies on a collection of diffing instances for which the ground truth assignment has been manually determined. Though we performed this extraction with regards to multiple sources of information such as source code, commit descriptions and unstripped symbols, we can not guarantee that our judgment is not biased, nor that it meets other experts' opinions. Furthermore, any error or absence in our extracted mappings is later propagated in our extrapolation step. This may lower the confidence in the ground truth assignment between two distant versions. This threat is inherent to any manually determined assignments and can only be mitigated by releasing the dataset for the community to review.

External validity

Despite the relatively large number of proposed diffing instances, several factors still threaten the generalizability of our experiments. First, our benchmark only includes C programs taken from three open-source projects. This is not representative of the variety of existing binaries. Moreover, all the executables were compiled with the same compiler, optimization level and targeted architecture.

In future works, we will investigate the performance of our approach on programs built under different settings. Notice that it would probably require more sophisticated measures of similarity able to handle greater syntactic differences. Last but not least, all of our diffing instances compare different versions of a same program. Though the manual determination of a unanimous ground truth assignment between two different binaries appears to be quite challenging, the evaluation of our method on such instances could be very instructive in the perspective of many applications such as the detection of duplicate code or vulnerability.

Construct validity

The proposed comparison of our approach with other state-of-the-art methods could also include threats to construct validity. First, all these methods are based on machine learning models that require a prior training step. We trained the models on the same dataset as the one we ran our experiments on. This could bias the resulting similarity scores, especially in the case of overfitting. Moreover, we configured all models with their default parameters (recommended by the authors), though different settings could have provided better results. Finally, we must recall that none of the competitor methods were originally designed to address the exact same problem as ours. Indeed, both Gemini and GraphMatching have been initially proposed to retrieve near-duplicate functions whereas DeepBinDiff addresses the binary diffing at a basic block granularity.

Future works

In addition to the aforementioned extended analysis we plan to investigate in the short run to improve our current solution, deeper researches will also be conducted to enhance our method in the long run. Most of them focus on the blind spot of our work: the measure of binary code similarity.

Hierarchical diffing

As introduced in Chapter 2 any function in our program representation actually consists in a graph of basic blocks. Therefore, we believe that our proposed network alignment framework could be leveraged in order to find a relevant basic block correspondence between the content of any two matched functions in a post-processing step. Such hierarchical diffing strategy consisting in first aligning higher-level elements and then to perform finer-grained matching between them is commonly found in the literature. To some extend, once the basic blocks of each function have been aligned, we could also run an instruction matching procedure inspired from sequence alignment methods. According to our graph matching formulation, introducing a post-processing step that performs basic block alignment inside any two matched functions requires a proper measure of basic block similarity. Moreover, a careful analysis of common control flow graph layout could provide insight about the desired trade-off between block content and branches similarity. Notice however that the graph structure of a function (control flow graph) might be quite different from the one of a program (call graph). As a consequence, leveraging the CFG during function mapping could provide not as much benefit as it does while mapping CG.

Function similarity measure

As previously mentioned in this chapter, our framework crucially lacks of more sophisticated measure of function semantic similarity. A substantial effort in our future works will be directed to the elaboration of a finer measure, able to leverage functions implemented via different programming languages, or compiled under different optimization levels or targeted architecture. Moreover, our measure should be sufficiently fast to compute several millions of similarity scores in reasonable time.

Many researches have been conducted in this direction. In particular, machine learning models are known to compute similarity scores relatively fast, based on sophisticated measures enclosing knowledge gained on a great amount of previously analyzed samples. Unfortunately, our experiments highlighted that some of the best-known models could provide misleading measures in order to perform binary diffing, though we believe that part of this issue might come from a bias in the training step that only considers identically named functions. In future work, we plan to investigate unsupervised learning models such as asm2vec [START_REF] Ding | Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization[END_REF]. However, we may want to process to a prior lifting of the assembly code into an intermediate representation, as well as to apply a code normalization close to the one used in our proposed similarity measure to limit unnecessary complex consideration of very similar instructions of operands.

To some extent, we could also work on improving our measure of call similarity, for instance by considering the type of function call (call to imported functions, method, private function, etc.) or distinguishing direct and indirect calls.

Program similarity measure

An interesting property of our approach is that it ultimately computes an approximation of the graph edit distance between both programs and thus provides a proper metric for measuring program similarity. Indeed, given the resulting assignment as well as the similarity scores, we may compute the overall cost of the corresponding edit path as chosen in Chapter 3. As a result, our framework could be leveraged in a variety of program-wide analyses requiring proper metrics such as malware detection, program lineage or library retrieval. We plan to investigate some of these applications in future works.

Diffing instance generative model

Finally, we believe that the current binary diffing community lacks of extended benchmark instances with ground truth solutions to perform experiments and compare approaches. In particular, in most existing available problem instances, the ground truth assignment is either extracted manually which is very timeconsuming, or computed automatically based on the unstripped function names, which usually results in partial mappings of the most similar functions. Both methods are not able to provide reliable problems with solutions at large scale.

In future work, we will attempt to design generative models able to introduce perturbation to a program while keeping the function correspondence. The idea is to modify the syntax of each function individually while keeping its semantic unchanged. To do so, we plan to review existing techniques in the field of binary code obfuscation.

Chapter 8

Conclusion

In this thesis, we introduced a new approach to address the binary diffing problem through its natural graph edit distance formulation: we aim at finding the minimal cost sequence of edit operations that transforms the call graph of a first binary A into the call graph of the second program B. In order to efficiently find an approximate solution, we reformulated the problem as a constrained integer quadratic program and proved that under mild conditions, the graph edit distance problem is equivalent to the network alignment problem. This reformulation enabled us to leverage efficient optimization techniques, such as the max-product algorithm.

We thus encoded the resulting maximization problem into a factor-graph graphical model such that the support of its distribution is equivalent to the set of feasible solutions in the constraint program, as well as the mode of the joint distribution corresponds to the optimal solution of the alignment problem. As a result, finding the assignment with maximum probability in the graphical model is equivalent to solving the network alignment problem, and therefore, to finding the optimal edit path between program A and B.

In order to efficiently approximate the mode of our graphical model, we leveraged the max-product algorithm, following the approach of NetAlign. As shown by [START_REF] Bayati | Algorithms for Large, Sparse Network Alignment Problems[END_REF], the algorithm actually reduces to a quite simple message-passing framework, which can compute updates very efficiently. However, both the control of the convergence of the messages, as well as the deduction of the current assignment after each iteration require computational expensive schemes in the original framework. We thus introduced several modifications to NetAlign and showed that they significantly speed up the computation, improve the control of the updates convergence, and halve the memory usage.

The evaluation of our proposed approach was twofold. We first compared our proposed model as a network alignment solver against some of the best-known methods. Based on a collection of synthetic alignment instances, as well as several famous real-world problems, we showed that QBinDiff outperforms its competitors in almost all instances and, as such, is one of the best-known solvers to align these types of graphs.

We then evaluated QBinDiff as a binary diffing tool, and thus compared the resulting assignments with ground truth solutions. Such experiments require a collection of binary diffing instances for which the actual function correspondences are known. Since no such benchmarks were readily available, we designed our own, consisting in over 60 programs as well as hundreds of ground truth solutions, and released it to the research community.

As a baseline, we referred to the two most common binary diffing tools that are BinDiff and Diaphora. Moreover, in order to properly assess the interest of our matching approach, we reproduced our experiments with other state-ofthe-art measures of function similarity, namely Gemini, GraphMatching and DeepBinDiff.

Our experiments showed that our algorithm outperforms other existing approaches in almost every problem instance. It also highlighted that the matching strategy is a crucial part of the diffing process and has more influence than the choice of the function similarity measure. Moreover, it appeared that using similarity metrics originally designed to retrieve near-duplicate functions might actually harm the quality of the resulting mapping. Finally, our results suggest that our problem formulation is a very adapted way to address the binary diffing problem.

Besides our formulation is quite natural and showed to result in more accurate mappings, it also provides a proper metric for measuring program-wide similarity. Indeed, any diffing assignment induces the (approximated) graph edit distance between the two programs. Therefore, our approach could also be used in a variety of metric-based analysis at a program level, such as library retrieval, program lineage, etc.

Finally, we believe that our graph matching algorithm could also be leveraged to perform diffing between matched functions in a post-processing step. This would result in a fined-grained alignment between constitutive basic blocks of both functions and could provide to an analyst precious information about their exact differences.

Figure 3 . 1 :

 31 Figure 3.1: Decomposition of an edit path P transforming graph G A into G B . The sequence of operations of an edit path can be dissociated into three different steps. All unnecessary nodes and edges are first removed from G A . Then, the contents of the all remaining elements are substituted into the one of their corresponding item in G B . Finally, extra nodes and edges are inserted in order to exactly recover G B . Each of these edit operations has a particular cost, and the graph edit distance problem consists in finding the edit path P * whose constitutive operations have the overall minimum cost.

Figure 3 . 2 :

 32 Figure3.2: Ambiguity between substitution and deletioninsertion edit schemes. The substitution of the node 2 in G A by node 3 in G B , as well as the one of their corresponding edges can always can be alternatively obtained by first removing 2 and all its incident edges and then inserting the desired 3 along with its adjacent edges in G B .

Figure 4 . 1 :

 41 Figure 4.1: The factor graph representation of the distribution function P X in our example

Figure

  Figure 4.2:A tree-like representation of our example graphical model. this representation best highlights the trajectory of the messages during the computation. For instance, in order to estimate the max-marginal of variable X 1 , the updates propagate from factor node e to factor node b in order to transmit to variable node X 1 the locally optimal configuration, as described in our equations.

Figure 4 . 3 :

 43 Figure 4.3: Our proposed model (right) induced by the two directed graphs G A and G B (left).Notice that some possible assignments (for instance 1 → 3 ) may be arbitrarily excluded, if considered too unlikely. Each pair of correspondences with consistent topology (for instance 1 → 2 and 2 → 3 ) forms a potential square (shaded). It is thus provided with an additional factor node h ii jj that favors their simultaneous assignment (right).

Algorithm 1 :

 1 QBinDiff message passing framework Input: Node and edge similarity matrices W 1 and W 2 , trade-off parameter α, relaxation parameter , maximum number of updates n. Output: Assignment vector x * begin /* balance the node and edge similarity */

  X→g , then, considering its new value, update m (t) X→f and finally m (t) X→h .

  (a) Average objective scores according to different ratios of noise. (b) Average objective scores according to different ratios of conserved elements. (c) Average objective scores according to different levels of graph density. (d) Average objective scores according to different trade-offs parameter α.

Figure 5 . 1 :

 51 Figure 5.1: Average network alignment scores for each solver according different graph generation parameters (rows) and different graph generation model (columns). For each experiments, the average computing time of each solver is given in second (right most column). Recall that the default trade-off parameter is α = 0.75.

Figure 5 . 2 :

 52 Figure 5.2: Evolution of the alignment score of the current solution over the iterations for different versions of NetAlign (lcshwiki problem). A marker + indicates the algorithm convergence or the 1000th iteration, and the corresponding objective score is prolonged by a dotted line for readability. QBinDiff corresponds to NetAlign + assignment strategy + epsilon relaxation. Both methods using the max-marginal assignment strategy provide a partial (thus suboptimal) mapping all along the algorithm and finally perform a MWM assignment after convergence.

Figure 6 . 1 :

 61 Figure 6.1: Average recall scores according to the program versions distance.Every matching method provides comparable near-optimal results while diffing very similar programs. As the distance increases, the performances of local matching strategies decline faster than our global approach.

Figure 6 . 2 :

 62 Figure 6.2: Relative similarity scores and square numbers of different network alignment solvers compared to QBinDiff. The grey lines record the normalized scores of the solution computed by QBinDiff. The blue area represents solutions with a higher overall network alignment score (α = 0.75).In almost all problem instances, QBinDiff provides better assignments than its competitors. In particular, most other methods appear to compute solutions with a high node similarity score but much less induced edges. On the contrary, Natalie seems to retrieve a high number of edge overlaps with a low overall node similarity score.

  (a) Average accuracy scores according to different trade-off parameters α. (b) Average accuracy scores according to different relaxation parameters .

Figure 6 . 3 :

 63 Figure 6.3: Average accuracy scores for different configurations of QBinDiff. Notice that the extreme parameters α = 0 and α = 1 in (A) respectively correspond to the resulting scores of the MCS and MWM solvers.

Figure 6 . 4 :

 64 Figure 6.4: Relative similarity scores and square numbers of different matching methods compared to the optimal assignment. The grey lines record the normalized scores of the ground truth.For Zlib and OpenSSL binaries, the ground truth seems to be a near optimal NAP assignment in almost all cases. This result does not hold for Libsodium, as in some cases, assignments computed by QBinDiff are better in both function similarity and number of induced squares.

Figure 6 . 5 :

 65 Figure 6.5: Cumulative distribution function of all non-zero pairwise similarity scores (a) and of the ground truth pairs only (b) (libsodium-0.4.2 vs libsodium-1.0.3). The similarity scores in (a) that correspond to a ground truth correspondence are marked by a cross. GraphMatching appears to be well fitted to retrieve a large part of the correct matches but strongly deteriorates the score of some. QBinDiff provides a more balanced score but keeps almost all ground truth correspondence to a satisfying level.

  Binary Diffing . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graph edit operation costs . . . . . . . . . . . . . . . . . . . . . 3.4.1 Edit operation relationships . . . . . . . . . . . . . . . . 3.4.2 Similarity measures . . . . . . . . . . . . . . . . . . . . . Max-product algorithm . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Factor-graph . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Estimation of the max-marginals . . . . . . . . . . . . . 4.1.3 Simplifications . . . . . . . . . . . . . . . . . . . . . . . . 4.1.4 Extension to the "loopy" case . . . . . . . . . . . . . . . 4.2 Network alignment via max-product belief propagation . . . . . Rounding strategy . . . . . . . . . . . . . . . . . . . . . 4.2.5 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Proposed improvements . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Solution assignment . . . . . . . . . . . . . . . . . . . . . 4.3.2 Updates schedule . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Auction based -complementary slackness . . . . . . . . 4.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Synthetic problems . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Real world problems . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . Translation of a simple program source code into assembly code and machine code. . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Different representations of a binary . . . . . . . . . . . . . . . . 2.3 Illustration of the binary diffing problem . . . . . . . . . . . . . 3.1 Decomposition of an edit path. . . . . . . . . . . . . . . . . . . Average accuracy scores for different configurations of QBinDiff 6.4 Relative similarity scores and square numbers of different matching methods compared to the optimal assignment . . . . . . . . 6.5 Relative similarity scores of the ground truth correspondences .

	4 Message-passing framework for the network alignment prob-lem 4.1 xvi 4.2.4 5 Network Alignment Experiments 5.1 Chapter 1

Introduction 2 Background 2.1 Static binary analysis . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Binary executable . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Program disassembly . . . . . . . . . . . . . . . . . . . . 2.1.3 Program representations . . . . . . . . . . . . . . . . . . 2.2 2.2.1 Binary code granularity . . . . . . . . . . . . . . . . . . 2.2.2 Binary code similarity . . . . . . . . . . . . . . . . . . . 2.2.3 Binary code matching . . . . . . . . . . . . . . . . . . . 3 Problem Statement 3.1 Binary diffing as a graph edit distance problem . . . . . . . . . 3.2 Binary diffing as a network alignment problem . . . . . . . . . . 3.3 Equivalence between graph edit distance and network alignment problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Formal proof . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . 3.4 4.2.1 Factor-graph . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Message updates . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Damping strategy . . . . . . . . . . . . . . . . . . . . . . 6 Binary Diffing Experiments 6.1 Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Function similarity . . . . . . . . . . . . . . . . . . . . . 6.1.2 Function matching . . . . . . . . . . . . . . . . . . . . . 6.1.3 Integrated differs . . . . . . . . . . . . . . . . . . . . . . 6.1.4 Training . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Benchmark design . . . . . . . . . . . . . . . . . . . . . 6.2.3 Ground Truth . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Overall results . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Results with different similarity measures . . . . . . . . . 7 Discussions 7.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Threats to validity . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii List of Figures 2.1 3.2 Ambiguity between substitution and deletion -insertion edit schemes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 An example factor graph representation . . . . . . . . . . . . . . 4.2 An example factor graph tree-like representation . . . . . . . . . 4.3 A factor graph representation of our model . . . . . . . . . . . . 5.1 Average network alignment scores on our synthetic benchmark . 5.2 Evolution of the alignment score of the current solution over the iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Average recall scores according to the program versions distance 6.2 Relative similarity scores and square numbers of different network alignment solvers compared to QBinDiff . . . . . . . . . . . . . 6.3

// Collatz sequence int collatz(int n) { // If n is even if(n % 2 == 0){ n = n / 2; } // If odd else{ n = n * 3 + 1; } return n; } int main() { int n = 100; /* Repeat until reaching 1*/ while(n != 1){ n = collatz(n); } } Source code [...] sub_1129: test dil, 1 jnz short loc_113D mov eax, edi shr eax, 1Fh add eax, edi sar eax, 1 retn loc_113D: lea eax, [rdi+rdi*2+1] retn main: mov edi, 64h loc_114B: call sub_1129 mov edi, eax cmp eax, 1 jnz short loc_114B mov eax, 0 retn [...] Assembly code return 0 while(n != 1) n = collatz(n) int n = 100 n = n / 2 return n if(n % 2 == 0) n = n * 3 + 1 return n 40F6 C701 F8D1 F8C3 750A 89F8 C1E8 1F01 F8D1 F8C3 8D44 7F01 C3BF 6400 0000 E8D9 FFFF FF89 C783 F801 75F4 B800 0000 00C3 F30F 1EFA E977 FFFF FFF3 0F1E FA40 F6C7 0175 0A89 F8C1 E81F 01F8 D1F8 C38D 447F 01C3 F30F 1EFA BF64 0000 00E8 D9FF FFFF 89C7 83F8 0175 F4B8 0000 0000 C30F 1F00 F30F 1EFA 4157 4C8D 3D83 2C00 0041 5649 89D6 4155 4989 F541 5441 89FC 5548 8D2D 742C 0000 534C 29FD 4883 EC08 E86F FEFF 48C1 FD03 741F 31DB 0F1F 8000 0000 004C Machine code

	Figure 2.1: Translation of a simple program source code into
	assembly code and machine code. While the machine code repre-
	sentation of a program can not be analyzed directly, the assembly
	representation lacks high-level concepts such as function names or
	variable types, as well as human-readable comments. Moreover,
	compiler optimizations introduce complex patterns to process
	simple operations. As a result, assembly code is much more
	difficult to analyze than source code.

40F6 C701 F8D1 F8C3 750A 89F8 C1E8 1F01 F8D1 F8C3 8D44 7F01 C3BF 6400 0000 E8D9 FFFF FF89 C783 F801 75F4 B800 0000 00C3 F30F 1EFA E977 FFFF FFF3 0F1E FA40 F6C7 0175 0A89 F8C1 E81F 01F8 D1F8 C38D 447F 01C3 F30F 1EFA BF64 0000 00E8 D9FF FFFF 89C7 83F8 0175 F4B8 0000 0039 D00F 1F00 F30F 1EFA 4157 4C8D 3D83 2C00 0041 5649 89D6 4155 4989 F541 5441 89FC 5548 8D2D 742C 0000 534C 29FD 4883 EC08 E86F FEFF 48C1 FD03 741F 31DB 0F1F 8000 0000 004C 0E4A 4118 200E 0E53 0008 0000 0060 0000 0748 0000 D93C FFFE 02AA 0000 6300 100E 028D 0E42 8C18 4603 200E 0486 0E41 8328 4405 300E 0A53 280E 0E41 4120 180E 0E42 Binary Instructions test r14d, r14d jnz loc_4B14 mov esi, [rbx+172Ch] add ebp, r14d mov [rbx+0B4h], ebp lea eax, [rbp+rsi+0] cmp eax, 2 ja loc_4688 cmp ebp, 105h ja loc_4730 mov rax, [rbx] mov r12d, [rax+8] test r12d, r12d jz loc_4830 mov r14d, [rbx+68h] add eax, [rsp+48h+var_44] sub r14d, ebp sub r14d, edx cmp eax, edx jbe short loc_4508 mov r15, [rbx] mov r12d, [r15+8] test r12d, r12d jz r15 cmp r12d, r14d ja short loc_4448 add rbp, [rbx+60h] mov r14d, r12d mov [r15+8], eax mov rdx, r14 mov rdi, rbp call _memcpy mov rax, [r15+38h] mov eax, [rax+30h] cmp eax, 1 jz loc_47F8 push rbx sub rsp, 8 call get_pc add rbx, 0x1217 add rsp, 8 pop rbx retn push rbx sub rsp, 8 call get_pc add rbx, 0x1217 add rsp, 8 pop rbx retn

	Control Flow Graph	Call Graph
	...
	...
	...
	...
	...
	...
	...
	...
	Figure 2.2: Different representations of a binary. The analysis
	of a program through its binary form (left-most) is quite tedious
	and usually requires a prior disassembling. The disassembly
	process first delimits the constitutive bytes of each instruction
	(red) and lift them into their corresponding assembly representa-
	tion (center left). Then, the potential targets of the branching
	instructions are analyzed (orange), and the program sequence
	of instructions is partitioned into basic blocks according to the
	different possible execution paths (center right). Finally, the
	CFG is itself divided into independent subgraphs according to
	the call procedures only (yellow). Each created node thus con-
	sists in a whole graph, and represents a function in the program
	(right-most).

40F6 C701 F8D1 F8C3 750A 89F8 C1E8 1F01 F8D1 F8C3 8D44 7F01 C3BF 6400 0000 E8D9 FFFF FF89 C783 F801 75F4 B800 0000 00C3 F30F 1EFA E977 FFFF FFF3

	Binary A
		080E 0B46 0000 0000
		0010 0000 08A4 0000
		0290 FFFF 00DE 0000
		0000 0000 0010 0000
		08B8 0000 035C FFFF
		005E 0000 0000 0000
		0054 0000 08CC 0000
	0F1E FA40 F6C7	03A8 FFFF 00E0 0000
	0175 0A89 F8C1 E81F	4B00 100E 028D 0E42
	01F8 D1F8 C38D 447F	8C18 4103 200E 0486
	01C3 F30F 1EFA BF64	0E41 8328 4705 300E
	0000 00E8 D9FF FFFF	0A70 280E 0E41 4120
	89C7 83F8 0175 F4B8	180E 0E42 4210 080E
	0000 0039 D00F 1F00	0B44 6602 0E0A 4128
	F30F 1EFA 4157 4C8D	0EC3 4420 0EC6 4218
	3D83 2C00 0041 5649	0ECC 4210 0ECD 4908
	89D6 4155 4989 F541	520B 080E C6C3
	5441 89FC 5548 8D2D
	742C 0000 534C 29FD
	4883 EC08 E86F FEFF
	48C1 FD03 741F 31DB
	0F1F 8000 0000 004C
	0E4A 4118 200E 0E53
	0008 0000 0060 0000
	0748 0000 D93C FFFE
	02AA 0000 6300 100E
	028D 0E42 8C18 4603
	200E 0486 0E41 8328
	4405 300E 0A53 280E
	0E41 4120 180E 0E42

CDCC 002C 0000 0924 0000 0430 FFFF 00F0 0000 4500 100E 028C 0E41 8618 4103 200E 0483 9902 0E0A 4118 100E 0E42 4508 000B 0000 0010 0000 0954 0000 04F0 FFFF 000F 0000 0000 0000 0010 0000 Binary B

Table 3

 3

.1: Program edit operations and respective costs.

  2 which is much larger than our |V A | 2 × |V B | 2 formulation. Finally, Lerouge et al. (2017) proposed another network alignment framework with the same cost matrix as ours, but requiring |V A ||V B | + |E A ||E B | variables and |V A | + |V B | + 2|V B ||E A | constraints whereas ours only requires respectively |V A ||V B | and

Table 3 . 2 :

 32 Function features and respective weights used in our proposed similarity measure. The final similarity score is computed using the Canberra distance.

Table 5 .

 5 1: Description of our benchmark dataset. The last column records the number of non-zero entries in the similarity matrix W 1 .

  Table 5.2: Resulting network alignment scores of each solver on different benchmark problems. The last column records the average computing time in seconds.

								Timing
	flickr-lastfm	QBinDiff 6144 6955.02 7775.69 8594.41 9118.51 Final 1980 3890.41 5800.81 7711.22 8857.46 Natalie 6012 5164.40 4282.43 3417.64 2896.06 NetAlign 5830 6742.41 7567.50 8427.41 9025.68 434531.5 419.6 156.8 94.1 Path 10 -4316.11 7403.84 8845.28 387114.1
	offline-online	QBinDiff 2608 2138.21 1678.45 1103.16 Final 40 222.35 404.70 587.06 Natalie 198 315.16 327.39 392.08 NetAlign 1772 1507.91 1352.68 1002.28 Path 244 789.61 725.42 690.01	812.04 696.47 446.39 756.60 27971.6 98.1 22.7 1553.8 742.72 13881.3
	dmela-scere	QBinDiff Final Natalie NetAlign Path	255 112 174 224 47	347.94 250.95 163.11 332.40 230.81	441.55 389.91 142.56 431.73 376.12	543.83 528.86 126.84 543.44 522.18	616.47 612.23 119.16 615.56 609.81 17951.0 36.1 45.9 8.7 115.4
	lcsh-wiki	QBinDiff Final Natalie NetAlign	632 574 584 506	614.87 585.22 496.47 547.40	612.69 596.43 419.76 552.33	605.06 607.65 337.64 584.12	614.09 614.38 287.93 610.77	39.3 20.3 2.9 52.3
		Path	238	385.09	462.93	539.48	594.96	4332.6
	1EWK-1U19	QBinDiff 2890 2183.37 1473.61 Final 2874 2169.75 1465.50 Natalie 2896 2172.50 1448.99 NetAlign 2896 2185.75 1474.02 Path 2896 2169.75 1465.50	764.76 761.25 725.49 765.02 761.25	339.63 338.70 291.39 338.70 338.70	23.8 17.9 852.9 1620.4 0.7

Algorithm 2 :

 2 Maximum common subgraph approximate algorithmInput: G A , G B , pairwise node similarity scores W 1 , max-hop parameter k, similarity threshold t, initial mapping pairs X

	Output: Complete mapping pairs X *
	begin
	/* initialize mapping	*/
	X * ← X
	while X = ∅ do
	/* pick a currently matched pair of functions	*/
	(i, i ) ← X.pop()
	/* get respective unmatched candidates	*/
	J ← GetUnmatchedKHopNeighbors(i)
	J ← GetUnmatchedKHopNeighbors(i )
	/* retrieve the most similar candidate pair	*/
	(j, j ) ← GetBestCandidate(J, J )
	if W 1 [j, j ] ≥ t then
	/* if the similarity score is high enough	*

  6 . During the problem statement, only plain text functions determined during the disassembly process are considered. Imported functions are hence discarded.

	Program	Vers. Diff. Nodes Edges GT GT
	Zlib	18 153	153	235 0.99 0.96
	Libsodium	33 528	589	701 0.98 0.79
	OpenSSL	17 136	3473 18563 0.94 0.72
	Table 6.1: Description of our binary diffing dataset. The last
	six columns respectively record the number of different binary
	versions, the number of resulting diffing instances, the average
	number of functions and function calls and the average ratio of
	conserved functions in our manually extracted and extrapolated
		ground truth.

  .2). As observed in our alignment benchmarks, our solver outperforms other methods in almost

		Matcher Similarity Squares Score Precision Recall Timing
		QBinDiff	0.929	0.807 0.888	0.955 0.995	0.2
		MWM	0.930	0.789 0.883	0.953 0.992	0.0
		MCS	0.924	0.781 0.876	0.946 0.985	0.0
	Zlib	BinDiff Diaphora	0.921 0.863	0.765 0.869 0.655 0.792	0.943 0.975 0.978 0.940	0.9 1.4
		Final	0.929	0.784 0.881	0.948 0.986	18.5
		Natalie	0.587	0.812 0.663	0.901 0.603	0.4
		NetAlign	0.929	0.807 0.888	0.955 0.995	21.9
		Path	0.930	0.789 0.883	0.953 0.992	0.6
		QBinDiff	0.706	0.604 0.677	0.722 0.880	6.6
		MWM	0.712	0.483 0.647	0.699 0.847	0.2
	Libsodium	MCS BinDiff Diaphora Final	0.708 0.662 0.605 0.710	0.494 0.647 0.544 0.628 0.470 0.567 0.455 0.636	0.704 0.854 0.752 0.869 0.783 0.831 0.686 0.829	0.3 0.9 8.6 30.3
		Natalie	0.424	0.565 0.462	0.596 0.438	37.0
		NetAlign	0.703	0.597 0.673	0.722 0.879	283.1
		Path	0.700	0.519 0.648	0.696 0.836	61.8
		QBinDiff	0.720	0.595 0.643	0.605 0.783	213.3
		MWM	0.738	0.506 0.592	0.522 0.670	25.5
	OpenSSL	MCS BinDiff Diaphora Final	0.738 0.643 0.543 0.719	0.506 0.592 0.501 0.553 0.332 0.408 0.355 0.487	0.522 0.670 0.572 0.681 0.577 0.565 0.476 0.627	24.4 3.2 60.6 264.4
		Natalie	0.620	0.589 0.601	0.599 0.668	733.8
		NetAlign	0.682	0.587 0.623	0.625 0.755 15193.9
		Path	0.722	0.521 0.596	0.556 0.715 7667.8
		Table 6.2: Average objective and accuracy scores of each state-
		of-the-art solver on binary diffing instances. Columns 2-4 respec-
		tively represent the normalized overall node similarity scores,
		normalized number of induced overlapping edges and normalized
		resulting alignment scores. The last column provide the average
		computation times for the matching step only, given in seconds.

  Table 6.3).

		Similarity	Matcher Precision Recall Timing
			NAP	0.955 0.995	3.2
		QBinDiff	MWM	0.953 0.992	3.0
			MCS	0.946 0.985	3.0
			NAP	0.953 0.992	6.2
	Zlib	Gemini	MWM MCS	0.936 0.974 0.942 0.981	5.9 5.9
			NAP	0.938 0.977	77.9
		GraphMatching MWM	0.901 0.937	77.1
			MCS	0.927 0.964	77.1
			NAP	0.909 0.946	494.0
		DeepBinDiff	MWM	0.820 0.853	489.4
			MCS	0.834 0.868	489.5
			NAP	0.722 0.880	19.9
		QBinDiff	MWM	0.699 0.847	13.5
			MCS	0.704 0.854	13.5
	Libsodium	Gemini	NAP MWM MCS NAP	0.714 0.863 0.668 0.802 0.686 0.823 0.693 0.837	31.7 24.4 24.4 315.6
		GraphMatching MWM	0.643 0.776	294.0
			MCS	0.670 0.806	294.2
			NAP	0.664 0.796	194.5
		DeepBinDiff	MWM	0.585 0.702	157.9
			MCS	0.599 0.718	157.6
			NAP	0.605 0.783	301.8
		QBinDiff	MWM	0.522 0.670	114.0
			MCS	0.522 0.670	113.0
	OpenSSL	Gemini	NAP MWM MCS	0.577 0.685 0.400 0.467 0.401 0.467	613.9 189.7 189.1
			NAP	0.548 0.686 39186.8
		GraphMatching MWM	0.316 0.408 37054.0
			MCS	0.317 0.409 37054.3
		DeepBinDiff	-	-	-	-

Table 6 .

 6

3: Average precision and recall scores for each combination of similarity measure (Similarity) and matching method (Matcher), for our three benchmark projects. The provided timings include both the computation of the similarity scores and the solution assignment, and are given in seconds.

  Table 6.4: Average computation time of the similarity scores only for each similarity measure, given in seconds. Notice that we were not able to compute DeepBinDiff pairwise similarity scores of OpenSSL programs in reasonable time.

	Similarity		Timing
		Zlib Libsodium OpenSSL
	QBinDiff	3.0	13.3	88.6
	Gemini	6.0	24.2	164.8
	GraphMatching 77.1	293.9	36999.2
	DeepBinDiff	489.3	156.0	-

https://www.radare.org/n/

https://binary.ninja/

https://ghidra-sre.org/

https://www.hex-rays.com/products/ida

Intel Xeon E5-2630 v4 @2.20GHz

https://github.com/joxeankoret/diaphora

Area Under the ROC Curve

https://github.com/madler/zlib

https://github.com/jedisct1/libsodium

https://github.com/openssl/openssl

https://github.com/google/binexport

Remerciements

List of Tables