Binary Diffing as a Network Alignment Problem via Belief Propagation

• URL: http://arxiv.org/abs/2112.15337v1
• Date: Fri, 31 Dec 2021 07:54:11 GMT
• Title: Binary Diffing as a Network Alignment Problem via Belief Propagation
• Authors: Elie Mengin (SAMM), Fabrice Rossi (CEREMADE)
• Abstract summary: We introduce a new formulation of this problem as a particular instance of a graph edit problem over the call graphs of the programs. We show that this formulation is equivalent to a network alignment problem. We implement a prototype of our method, called QBinDiff, and propose an extensive evaluation which shows that our approach outperforms state of the art diffing tools.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we address the problem of finding a correspondence, or matching, between the functions of two programs in binary form, which is one of the most common task in binary diffing. We introduce a new formulation of this problem as a particular instance of a graph edit problem over the call graphs of the programs. In this formulation, the quality of a mapping is evaluated simultaneously with respect to both function content and call graph similarities. We show that this formulation is equivalent to a network alignment problem. We propose a solving strategy for this problem based on max-product belief propagation. Finally, we implement a prototype of our method, called QBinDiff, and propose an extensive evaluation which shows that our approach outperforms state of the art diffing tools.

Related papers

• The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
  The noisy version of the graph isomorphism problem aims to find a matching between the nodes of two graphs which preserves most of the edges. This thesis focuses on understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data.
  arXiv  Detail & Related papers  (2024-04-18T15:31:13Z)
• Counterfactual Intervention Feature Transfer for Visible-Infrared Person Re-identification [69.45543438974963]
  We find graph-based methods in the visible-infrared person re-identification task (VI-ReID) suffer from bad generalization because of two issues. The well-trained input features weaken the learning of graph topology, making it not generalized enough during the inference process. We propose a Counterfactual Intervention Feature Transfer (CIFT) method to tackle these problems.
  arXiv  Detail & Related papers  (2022-08-01T16:15:31Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Improved Algorithm for the Network Alignment Problem with Application to Binary Diffing [0.0]
  We present a novel algorithm to address the Network Alignment problem. Experiments show that our proposed model outperforms other state-of-the-art solvers. We also propose an application of our method in order to address the Binary Diffing problem.
  arXiv  Detail & Related papers  (2021-12-31T07:52:14Z)
• Bilateral Cross-Modality Graph Matching Attention for Feature Fusion in Visual Question Answering [71.6781118080461]
  We propose a Graph Matching Attention (GMA) network for Visual Question Answering (VQA) task. firstly, it builds graph for the image, but also constructs graph for the question in terms of both syntactic and embedding information. Next, we explore the intra-modality relationships by a dual-stage graph encoder and then present a bilateral cross-modality graph matching attention to infer the relationships between the image and the question. Experiments demonstrate that our network achieves state-of-the-art performance on the GQA dataset and the VQA 2.0 dataset.
  arXiv  Detail & Related papers  (2021-12-14T10:01:26Z)
• Deep graph matching meets mixed-integer linear programming: Relax at your own risk ? [8.05409526074409]
  We propose an approach integrating a MILP formulation of the graph matching problem. Similar approaches are derived by releasing the optimal guarantee of the graph matching solver and by introducing a quality level. Our experimental evaluation gives several theoretical insights and guides the direction of deep graph matching methods.
  arXiv  Detail & Related papers  (2021-08-01T08:29:55Z)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  We consider a problem known as multi-task learning, consisting of fitting a set of regression functions intended for solving different tasks. In our novel formulation, we couple the parameters of these functions, so that they learn in their task specific domains while staying close to each other. This facilitates cross-fertilization in which data collected across different domains help improving the learning performance at each other task.
  arXiv  Detail & Related papers  (2020-10-24T21:35:57Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the question [13.625395368083641]
  We address the common setting in which one of the graphs to match is a bipartite network and one is unipartite. We formulate the graph matching problem between a bipartite and a unipartite graph using an undirected graphical model. We show how our methods can result in a more accurate matching than the naive approach of transforming the bipartite networks into unipartite.
  arXiv  Detail & Related papers  (2020-02-05T05:24:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.