Improved Algorithm for the Network Alignment Problem with Application to Binary Diffing

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 [25]. Thus, they aim at best aligning the (leading) eigenvectors of the two affinity matrices (or Laplacians) [14, 21]. On the other hand, PageRank methods approximates the NAP through an eigenvalue problem over the matrix $Q$ [24]. The idea consists in computing the principal eigenvectors of $Q$, and to use it as a similarity score of every possible correspondences. The resulting assignment can then be computed using conventional MWM solvers. Over the years, several improvements have been proposed to enhance the procedure [16, 20, 12, 28].

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 [18]. Other approaches make use of a concave [27] or indefinite [26] 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 [30, 29].

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 Adams and Johnson linearization and using a Lagrangian dual relaxation have been proposed by Klau [15] and later improved by El-Kebir et al. [10].

Finally, a message passing framework has shown promising results [2]. It is directly derived from a previous model that provided important results on solving the MWM using max-product belief propagation [4]. In our work, we chose to apply this model to our use case.

Note that an important limitation to the NAP is the size of the matrix $Q$ 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 $Q$. Therefore, they generally apply to sparse graphs only. Moreover, several approaches propose to also restrain the number of potential candidates [10, 2] 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 make use of this interesting feature.

The most common reformulation of a constrained optimization program into probabilistic graphical models usually requires the introduction of a factor-graph which assigns maximum probability to the solution of the program. For more details about factor-graph graphical models, we refer the reader to Kschischang et al. [17]. In order to design such graphical model, we must encode both the objective function and the constraints of NAP into an equivalent probability distribution. This encoding is done through the factorization of several functions (function nodes) over the different variables of the program (variable nodes). In this form, the mode of the distribution, can be efficiently computed (at least approximated) using the max-product algorithm. In the following, we introduce the factor-graph designed to address NAP.

We compare our method to four state-of-the-art NAP solvers and their associated benchmarks (see Table 1): PATH [27], NetAlign [2], Natalie 2.0 [11], and Final [28]. All these solvers have been configured with their default parameters. In order to analyze the ability of each solver to provide proper solutions both in terms of node similarity and edge overlaps, we tested different values of the trade-off parameter $\alpha$. Notice that some problems include a similarity score matrix with several zero entries. In some models (ours, NetAlign, Natalie), those entries are considered as unfeasable matches whereas they are legal correspondences in others. These models would thus optimize the problem on a subset of all possible one-to-one mappings.

Our results show that our approach outperforms or nearly ties the other existing methods on every problems (see Table 2). It appears to provide better results on sparse graphs, while it may compute slightly suboptimal assignments on the densest one (1EWK-1U19). It also seems to be the best fitted to perform diffing at different arbitrary setting of the trade-off parameter $\alpha$, even in the degenerated MCS case ($\alpha=0$), unlike most other evaluated methods.

In terms of computing time, as expected, QBinDiff takes much less time to approximate the NAP than NetAlign. Regarding other solvers, both Natalie and Final run within comparable time while Path tends to be very expensive, and may become prohibitive for larger problem instances. Note that it was not able to provide a solution to the Flickr-Lastm problem when $\alpha=0.25$ within 8 days, and was considered timed-out. Of course these timings depends on the quality of the implementation and should only be considered with respect to their order of magnitude. We used the implementations provided by the authors of other methods.

In a second set of experiments, we propose to evaluate the relevance of our model in order to address the Binary Diffing problem. Given two binary executables $A$ and $B$, this problem consists in retrieving the correspondence between the functions of $A$ and those of $B$ that best describes their semantic differences. This problem can be reduced to a network alignment problem over the call graphs of $A$ and $B$.

The results of the alignment should be compared to some ground truth. We computed it as follows. We first downloaded the official repository of a program, then compiled the different available versions using GCC v7.5 for x86-64 target architecture and with -O3 optimization level. Once extracted, each binary was stripped to remove all symbols, then disassembled using IDA Pro v7.2¹¹1https://www.hex-rays.com/products/ida, and finally exported into a readable file with the help of BinExport²²2https://github.com/google/binexport. During the problem statement, only plain text functions determined during the disassembly process are considered. For each program, assuming that this extraction protocol provided us with $n$ different versions, we propose to evaluate our method in diffing all the $\frac{n(n-1)}{2}$ possible pairs of different binaries.

For all these diffing instances, we finally had to extract the ground truth assignments. We proceed in two steps. We first manually determine what we think to be the function mapping that best describes the modifications between two successive program versions. This is done considering the binary symbols, as well as the explicit commit descriptions. Then, we deduce all the remaining pairwise diffing assignments by extrapolating the mappings from version to versions. Formally, if we encode the mapping between $A_{1}$ and $A_{2}$ into a boolean matrix $M_{A_{1}\to A_{2}}$ such that ${M_{A_{1}\to A_{2}}}_{ii^{\prime}}=1$ if and only if function $i$ in $A_{1}$ is paired with function $i^{\prime}$ in $A_{2}$, then, our extrapolating scheme simply consists in computing the diffing correspondence between $A_{k}$ and $A_{n}$ as follows: $M_{A_{k}\to A_{n}}=\prod_{i=k}^{n-1}M_{A_{i}\to A_{i+1}}$. We applied this extraction protocol to three well known open source programs, namely Zlib ³³3https://github.com/madler/zlib, Libsodium ⁴⁴4https://github.com/jedisct1/libsodium and OpenSSL ⁵⁵5https://github.com/openssl/openssl from which we collected respectively 18, 33 and 17 different binary versions and therefore 153, 528 and 136 diffing instances. Statistics describing our evaluation dataset are given in Table 3.

As a baseline, we chose to compare to the two most common diffing tools: BinDiff and Diaphora. BinDiff uses a matching algorithm close to VF2 [8] originally introduced to approximate the MCS whereas Diaphora proposes a different greedy assignment strategy that first matches the most similar functions and then searches for potential correspondences in the remaining ones. This mapping mechanism is known to provide $\frac{1}{2}$-approximate solutions to the MWM problem [9]. Note that, in order to compare with NAP solvers, and because, in general, binary diffing favors recall over precision, QBinDiff is designed to produce a complete assignment and does not include a mechanism to limit the mapping of very unlikely correspondences during computation.

Our experiments show that QBinDiff generally outperforms other matching approaches in both alignment score and recall (see Table 4). In fact, our method appears to perform clearly better at diffing more different programs, whereas it provides comparable solutions on similar binaries. This highlights that the local greedy matching strategies of both BinDiff and Diaphora are able to provide good solutions on simple cases but generalize poorly on more difficult problem instances. This results should be view as promising in the perspective of diffing much more different binaries.

We reproduced our experiments with different trade-off parameters $\alpha$, in order to estimate which setup should be used such that the optimal assignment meets the ground truth. Our computations suggest that a trade-off around 0.75 is a fair choice though a slightly higher value could provide satisfying assignments as well, especially while diffing OpenSSL programs.

Though our method improves the state-of-the-art, some difficulties remain.

A first limitation of our approach concerns the design of the network alignment itself. Indeed, the determination of the trade-off parameter $\alpha$ is subject to arbitrary considerations and may have an important impact on the resulting solution. Moreover, this trade-off certainly depends on the density of the graphs since densest graphs mechanically include more potential edge overlaps. Finally, the proposed model is designed to compute complete assignments and therefore does not include any mechanism to optimize the precision. This later could be done in introducing a penalty term $\zeta$ to the node similarity scores such $p_{ii^{\prime}}=\sigma_{V}(i,i^{\prime})-\zeta$. Correspondences with negative similarity scores would thus belong to the final mapping if they induce enough topological similarity.

Another difficulty of our approach is the determination of the relaxation parameter $\epsilon$. As previously mentioned, its setting controls on a trade-off between the quality of the solution and the speed at which the messages converges. While the proposed solution gives very satisfactory results, other rising schemes could be used to adapt the parameter to the current solution during computation. We leave this investigations to future work.

Finally, our formulation is limited by its memory consumption associated to the use of a quartic memory matrix $Q$. Though the proposed model enables to significantly reduce the problem size by limiting the solution set to the most probable correspondences, this relaxation inevitably induces information loss, especially for large graphs where the relaxation must rise consequently. In practice, graphs of several thousands of nodes can be handled efficiently. For larger instances, a solution could consists in first partitioning the graphs into smaller consistent subgraphs, and then proceed the matching among them. However such partition is not trivial and might result in important alignment errors.