ReGraph: A Tool for Binary Similarity Identification Conference: 34th ACM SIGSOFT International Symposium on Software Testing and Analysis; June 25–28, 2025; Trondheim,Norway 34th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA Companion ’25), June 25–28, 2025, Trondheim,
Li Zhou, Marc Dacier, Charalambos Konstantinou · 2025
Read ReGraph: A Tool for Binary Similarity Identification Conference: 34th ACM SIGSOFT International Symposium on Software Testing and Analysis; June 25–28, 2025; Trondheim,Norway 34th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA Companion ’25), June 25–28, 2025, Trondheim, by Li Zhou, Marc Dacier, Charalambos Konstantinou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16219.txt.
Introduction
Li Zhou and co-authors present ReGraph in a 2025 paper, a fast tool to judge similarity between binary code functions. Matching binaries aids bug hunting and copy detection, but stripped files and varied build settings make it hard.
Recent methods lean on heavy neural networks that slow down on large software, even with strong graphics cards. ReGraph compares functions across architectures and build levels with a graph approach. On public data sets it ran hundreds of times faster than language-based methods. Accuracy stayed in line with top models. Security teams get a way to scan big code bases without the usual time cost, a gain for routine audits.
Catalog record
| CREATOR | Li Zhou, Marc Dacier, Charalambos Konstantinou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16219
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ReGraph: A Tool for Binary Similarity Identification Conference: 34th ACM SIGSOFT International Symposium on Software Testing and Analysis; June 25–28, 2025; Trondheim,Norway 34th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA Companion ’25), June 25–28, 2025, Trondheim, Norway DOI: 10.1145/3713081.3731728 ISBN: 979-8-4007-1474-0/2025/06 CCS: Security and privacy Malware and its mitigation CCS: Security and privacy Embedded systems security CCS: Security and privacy Software reverse engineering Li Zhou, Marc Dacier, Charalambos Konstantinou Abstract . Binary Code Similarity Detection (BCSD) is not only essential for security tasks such as vulnerability identification but also for code copying detection, yet it remains challenging due to binary stripping and diverse compilation environments. Existing methods tend to adopt increasingly complex neural networks for better accuracy performance. The computation time increases with the complexity. Even with powerful GPUs, the treatment of large-scale software becomes time-consuming. To address these issues, we present a framework called ReGraph to efficiently compare binary code functions across architectures and optimization levels. Our evaluation with public datasets highlights that ReGraph exhibits a significant speed advantage, performing 700 times faster than Natural Language Processing (NLP) -based methods while maintaining comparable accuracy results with respect to the state-of-the-art models. 1. Introduction Binary Code Similarity Detection (BCSD) plays a critical role in various downstream applications such as vulnerability identification, firmware security analysis, and software reuse detection ( Basit and Jarzabek 2005 ; Luo et al. 2014 ; Zhao et al. 2022 ; Shirani et al. 2018 ; Huang et al. 2017 ) . Despite significant progress, it remains an active research area. A key difficulty lies in that, even when compiled from the same source code, binaries can exhibit substantial differences across various compilation options in both structure and semantics. Furthermore, to minimize file size, binary stripping is commonly employed ( Marcelli et al. 2022 ) , eliminating symbol tables and debug information ( GNU [n. d.] ) , thereby exacerbating the challenge of binary-level code analysis ( Wang et al. 2024 ) . Manually reverse engineering binary code functions is a solution but a very time-consuming one, especially when analyzing millions of stripped binary functions ( Xu et al. 2021 ) . Hence, research directions focus on automatic methods. At first, methods have compared binary file elements such as operator counts, jumps, and Control Flow Graphs (CFGs) ( xorpd [n. d.] ; David and Yahav 2014 ) , but different compilation options significantly alter CFG s and other extracted features ( Mengin and Rossi 2021 ) , limiting their performance in cross-optimization and cross-architecture scenarios ( Pewny et al. 2015 ; Marcelli et al. 2022 ) . More recently, new methods have been proposed to leverage neural networks and have outperformed earlier methods ( Xu et al. 2017 ; Yu et al. 2020b ; Yu et al. 2020a ) . Despite that, the differences caused by different compilation options require an increasing amount of neural network parameters ( Chandramohan et al. 2016 ; Hu et al. 2016 ; Xu et al. 2017 ) , as well as the creation of large models ( Ding et al. 2019 ; Luo et al. 2023 ; Yu et al. 2020b ) . These models require powerful and expensive GPUs and render the computation time impractical when analyzing large amounts of functions. To address these challenges, we propose ReGraph, a function-level cross-architecture and cross-compilation binary code matching framework. ReGraph efficiently identifies known functions within a given software by leveraging code lifting, re-optimization, Code Property Graphs (CPGs), and Graph Neural Networks (GNNs) to compute function similarity. This enables analysts to further examine the most likely similar functions within a binary executable. We evaluate ReGraph on public datasets ( Marcelli et al. 2022 ) . The results demonstrate that our framework exhibits high accuracy and fast matching speed with much lower resource consumption than state-of-the-art solutions. Our contributions can be summarized as follows: • We propose mitigating binary discrepancies by offloading them to the lifter and re-optimizer. Our experiments show that these techniques improve similarity scores by an average of 72.8% with respect to those reported by BinDiff ( GmbH 2011 ) . Our results demonstrate that these techniques can serve as a generalizable meta-method for other binary code similarity detection frameworks. • We integrate CPG s and GNN s with lifting and re-optimization to develop ReGraph. ReGraph achieves a 700× speedup over NLP-based methods while maintaining comparable performance to state-of-the-art approaches. • With ReGraph, our proposed command-line tool, analysts can focus on the top-K most similar functions rather than analyzing the entire binary file, significantly reducing their workload. This paper is structured as follows: Section II presents the usage of our tool, and Section III provides a detailed explanation of each component of ReGraph. We evaluate ReGraph in Section IV. Section V concludes the paper and discusses potential directions for future research. 2. Usage In this section, we demonstrate the usage of ReGraph, A Python-based command-line tool that detects similar binary code functions. It operates in two phases: the training phase, which processes newly encountered binary files, and the inference phase, which computes similarity results based on the trained model. 2.1. Requirements ReGraph is built in Python with additional dependencies. It requires RetDec ( Křoustek et al. 2017 ) for binary lifting, LLVM ( Lattner 2002 ) for re-optimization, and Joern ( Yamaguchi 2014 ) for extracting CPGs. These dependencies should be installed before using ReGraph. 2.2. Training Preprocessing: Preprocessing includes binary lifting, re-optimization, CPG extraction, and CPG vectorization. We have integrated the first three functionalities into a Python script, allowing them to be executed with a single command. By default, we assume the directory structure follows the format project/architecture/ optimization-level . If not, users can specify custom file paths through the extra-provided Python programming interface. Once CPGs are extracted, a separate command-line script vectorize the CPGs into datasets for training and inference. Additionally, an auxiliary file, the op_file , will be generated to store statistics about operators extracted from binaries to assist in encoding the CPGs. Training: To achieve optimal performance on new binary files, we recommend training the model on these files. All hyperparameters governing the training process are defined within the configuration file called train_config.yaml . Subsequent to data preprocessing, this file requires modification to specify the dataset directory path and finalize the parameters for training execution. Then, running the model training script will initiate the training process and generate the trained model file in the specified output folder. 2.3. Inference With the trained model file and the corresponding op_file , inference can be performed. Given a target function in a binary file (target binary file), our tool identifies the top K’s most similar functions, in which the user pre-defines the K, from another binary file (candidate binary file). To minimize user interaction, our tool outputs all functions from the target binary file along with their top-K matches from the candidate binary file, including the corresponding similarity scores, rather than requiring users to select a target function manually. This functionality is encapsulated in a script, where users specify the pre-trained model path, the op_file , and the two binaries via the command line to generate the results in the Excel spreadsheet. 2.4. Illustrative Example In this