The increasing number of cybersecurity regulations highlights the growing importance of scrutinizing firmware in smart devices to ensure compliance and security. However, such scrutiny often involves reverse engineering-a process that is time-consuming, costly, and reliant on highly specialized skills that are in short supply. Consequently, there is a rising demand from the industrial sector for innovative tools and solutions to streamline and accelerate firmware analysis, making it more eficient and accessible. In this paper, we introduce BinSAFE, an integrated system for comparing binaries within a firmware against a knowledge base. BinSAFE supports adding new firmware, extracting its binaries, and matching them against the knowledge base for comparison. The core of BinSAFE is a graph-matching algorithm that leverages embedding-based solutions to identify similar functions across binaries and compute binary-level similarity. This consists of a greedy strategy to match the call graphs of two binaries, considering both library and user-defined functions. We evaluated BinSAFE on a multi-architecture dataset comprising binaries compiled with diferent compilers and optimization levels. The results demonstrate that BinSAFE outperforms a simple baseline, highlighting that combining intra-procedural information from functions with inter-procedural one from call graphs enhances the understanding of binaries' semantics.
Existing solutions for FS can be broadly divided into two categories: those that employ DNNs [
Binary Code Similarity. Despite these advancements, almost all existing works focus on computing similarity between individual functions. In practice, it is essential to develop solutions that operate at the level of entire binaries (e.g. programs or libraries), thus enabling Binary Code Similarity (BCS) Detection. A Binary Code Similarity Detection algorithm would take as input two entire binaries, e.g. two ELF files, and give as output a similarity score between 0 and 1.
Such an algorithm would allow an analyst to build a knowledge base of interesting binaries (such as common libraries or known malicious code) and, when presented with a new firmware image, quickly identify matches of interest between the binaries it contains and those already known. BinSAFE System. In this paper, we propose an integrated system named BinSAFE, which enables the creation of a knowledge base of binaries. New firmware can then be fed into the system, which automatically extracts the binaries within the firmware and matches them against the knowledge base using the BCS algorithm.
The core of BinSAFE is a general methodology that extends embedding-based FS solutions to BCS. Our BinSAFE BCS Algorithm approach achieves this by matching the call graphs of the target binaries using a greedy strategy that operates in two main phases. First, the system identifies “hotspots” by selecting pairs of similar functions across the two binaries based on a predetermined similarity threshold. Next, it attempts to match the neighbors of these hotspots in the binaries’ call graphs, continuing this process until no more viable pairs remain or all neighbors have been examined.
Throughout this process, special care is given to known library functions, incorporating their rarity as a weighting factor. While the use of a common libc function (e.g., printf) provides limited insight, the presence of an extremely uncommon function could strongly suggest a deeper similarity between the binaries.
In this paper, we propose the following contributions:
• We introduce the architecture of BinSAFE, a system that adapts FS solutions for BCS. BinSAFE
provides all the functionalities required to build a knowledge base of binaries and test new binaries
against it.
• We present the BinSAFE BCS algorithm, a novel approach that calculates a similarity score
between 0 and 1 for two entire binaries, using any embedding-based technique as its building
block.
• We provide an experimental evaluation of BinSAFE on a dataset of 2118 amd64 binaries and 1568
aarch64 binaries, showing that in terms of nDCG it outperforms a naive baseline by 67.56% in
the case of amd64 and 66.03% in the case of aarch64. Our evaluation employs SAFE [
We represent a binary through its call graph, a pair ( , ), where is the set of functions in the binary, and is the set of edges denoting calls between them. The algorithm follows an iterative process to match similar functions across call graphs of diferent binaries. Specifically, given two call graphs, 1 = (1, 1) and 2 = (2, 2), the procedure begins by identifying the pair of functions with the highest similarity score, computed using the FS system. To identify this pair, we generate embeddings for each ∈ 1 ∪ 2 using the FS system and then calculate the similarity between the embeddings of 1 and 2. In our case, this boils down to multiplying the vectors to compute the cosine similarity.
During each iteration, the algorithm examines the neighbors of the current hotspot in the corresponding call graphs. Each pair of neighbors from 1 and 2 is matched, with the pair showing the highest similarity becoming the hotspot for the next iteration. The algorithm then recursively examines and matches the neighbors of the newly matched pairs, extending this process to subsequent neighbors along the two call graphs. This continues until no more matchable pairs remain. At that point, the process is repeated for the next iteration considering the new hotspot.
The procedure terminates when no more functions in 1 and 2 can be matched or there are no more hotspot candidates. This process is controlled by a threshold . If the maximum similarity falls below this threshold, the process stops, even if unmatched functions remain in the two binaries. The rationale is to avoid matching functions with very low similarity scores. In Appendix B, we discuss the experimental approach used to determine a viable value of . The similarity between the two binaries is finally calculated as:
(1) + (2) (1, 2) = () * (1) 2 where: () is the average similarity between the matched functions; () calculates the percentage of matched functions across the binary .
The solution described in the previous section does not explicitly account for library functions, i.e., functions that are imported and linked at runtime. For dynamic linking to work correctly, the symbols of such functions cannot be stripped from the binary. Practically speaking, if an ELF file imports libc to use printf, the ELF file, even after stripping, retains a symbolic call to printf. This allows us to retrieve the name of each imported function and use this information in our matching algorithm. In this approach, imported functions are represented as nodes in the call graphs and are matched when their symbols are identical.
It is widely recognized that common library functions provide limited semantic insight, as they are generic and reused across many programs. In contrast, rare library functions can ofer valuable clues about whether binaries implement similar functionalities. To address this, we introduce a mechanism that prioritizes rare library functions over common ones during the initial phase of the algorithm. This mechanism scales the similarity score of library functions using two approaches: Additive Frequency (AF), where the similarity of two library functions with the same name is computed as = 1 + (1 − )2 and Multiplicative Frequency (MF), where the similarity is computed as = 1 · (1 − )2. Here, is a weight assigned to each function based on its popularity. Additional details on how the factor is determined can be found in Section 4.2.
A detailed description of the algorithm together with the pseudocode can be found in Appendix A.
In this section, we describe the evaluation dataset and explain the process for identifying library functions of interest, as well as how to assign them weights based on their popularity.
We evaluated our approaches on a dataset of roughly 2800 binaries generated from 16 open-source C programs and libraries: busybox, coreutils, dnsmasq, dropbear, libboost, libcurl, libgcrypt, liblzma, libpng, libtif, libzip, lighttpd, nettle, readline, wolfssl, and zlib. These projects were compiled for amd64 and aarch64 architectures using four compilers (clang 11, clang 13, gcc 8.3, and gcc 10.2) and four optimization levels (O0, O1, O2, O3).
We use ghidra [18] to disassemble binaries and extract their call graphs. After filtering duplicates and handling disassembler errors, the dataset includes 2118 amd64 binaries and 1568 aarch64 binaries. Each amd64 binary has an average of 12 similar binaries (ranging from 1 to 25), while aarch64 binaries have an average of 12 similar binaries, ranging from 1 to 27.
The procedure described in Section 3 involves matching library functions based on their names and requires a frequency measure for each name to adjust the similarity score. Therefore, it is necessary to create a list of symbols extracted from libraries referenced by common binaries. To do so, we analyzed 70,961 amd64 POSIX-based binaries, focusing on their import tables. Libraries referenced by more than 3% of the analyzed binaries were considered relevant. Through this process, we identified 29 relevant libraries and extracted their symbols. For each identified library, we extracted the function names, resulting in a set of 25,713 functions of interest. We then measured the frequency of each function considering an additional dataset of 4,168 amd64 POSIX-based binaries. Specifically, for each function name, we counted whether it was called within an analyzed binary. If a function was called multiple times within the same binary, its frequency was still counted as one.
In our evaluation, we answer the following research questions:
RQ1: What is the impact of including libraries on the overall performance of the matching algorithm? RQ2: How does the neighbor-based matching strategy afect the overall performance? In the following, we refer to the basic matching strategy described in Section 3.0.1 as BS-LF. The main matching strategy based on library names is denoted as BS-LF-A when using the AF scaling strategy and as BS-LF-M when using the MF scaling strategy. We test these algorithms against two baselines: BS-UO, which runs the algorithm described in Section 3 exclusively on the user-defined functions without considering imported libraries (so that we can measure the impact of considering libraries); BS-AVG where the similarity between two binaries is simply computed as the average similarity of the pairwise similarities between all functions in their respective call graphs (in this way we measure the impact of considering topology information).
We test our system in a retrieval scenario. We sample a query binary from the dataset described in Section 4.1 and compute the similarity between the query and all binaries in the dataset. The results are ordered by their similarity scores, and we compute the performance metrics on the top- results. As performance metrics, we use standard measures for information retrieval systems: nDCG [19], precision, and recall.
In our experiments, for each architecture, we randomly sampled 160 binaries from the dataset described in Section 4.1 to serve as queries (10 for each compiler-optimizer pair) and used the entire set of binaries as the knowledge base.
Here, we evaluate the impact of library functions on the overall performance of our matching algorithm. In particular, we compare BS-UO, where library functions are excluded from matching candidates, with BS-LF, BS-LF-A, and BS-LF-M. 5.1.1. Results on amd64.
Looking at the results in Figure 2(a) and Table 1, including library functions in the matching strategy produces a noticeable increase in algorithm performance. In particular, when considering the results in average for the search depth value ∈ {1, 200}, BS-LF demonstrates a noticeable advantage over BS-UO, as it shows a 1.90% higher nDCG, 2.53% higher precision, and a 2.43% higher recall. These gaps slightly increase when considering frequency information of library functions, with BS-LF-A outperforming BS-LF by 0.47% in nDCG, and 0.43% in recall, while achieving comparable precision. Interestingly, the performance of the matching algorithm varies based on how the similarity of library functions is scaled. Specifically, using frequency as an additive factor leads to better results than applying it as a multiplicative factor, with BS-LF-A outperforming BS-LF-M by 0.63% in nDCG, 0.63% in precision, and 0.57% in recall on average.
50 50
Precision nDCG
The results in Figure 2(a) and Table 1 reveal an interesting trend. For low search depth values, BS-UO outperforms all other matching algorithms that include library functions across all evaluated metrics. Specifically, when considering the @1 results for the three metrics, while BS-UO, BS-LF, and BS-LF-M perform almost similarly (with BS-UO improving by 0.32% BS-LF-M nDCG), BS-UO demonstrates a clear advantage over BS-LF-A, as it achieves a 2.67% higher nDCG, a 2.74% higher precision, and 2.78% higher recall.
This indicates that for low search depth values, considering library functions introduces noise into the matching process. The previous trend is subverted when increasing the search depth, with BS-LF-A being the most efective technique, as confirmed by the @10 and @100 results reported in Table 1.
nDCG 4 6 d m a precision recall nDCG 4 6 h c r aa precision recall 0.068 0.080 0.223 0.206 0.069 0.082 0.057 0.062 0.004 0.054 0.383 0.350
In this section, we examine how inter-procedural information derived from call graph topology contributes to identifying similar binaries. Based on the results of the previous section, we focus exclusively on BS-LF-A and its performance against the BS-AVG baseline.
Results in Table 1 demonstrate that call-graph information is fundamental in determining whether two binaries are similar. When considering amd64 binaries, BS-LF-A consistently outperforms BS-AVG, with an average improvement of 67.56% in nDCG, 60.76% in precision, and 50.14% in recall. Moving to aarch64, we observe similar results, with BS-LF-A improving BS-AVG by 66.03% in nDCG, 60.25% in precision, and 53.35% in recall.
Existing works on Binary Code Similarity detection can be divided into traditional and learning-based solutions.
Traditional BCS detection methods leverage manually crafted features derived from static or dynamic
analysis, combining them using various approaches to compute similarity. Solutions like BinDif [
Learning-based approaches harness recent advancements in NLP and Graph Neural Networks to
generate low-dimensional representations (i.e., embeddings) of the input that capture the semantics
of code snippets. Similarity is then measured by calculating the distance between these vectors.
During training, the parameters of the DNN model are adjusted so that embeddings of semantically
similar snippets are positioned close in the vector space. SAFE [
In this paper, we have demonstrated how combining function embedding techniques, particularly SAFE, with information from the call graph can yield valuable results in measuring program-level similarity.
Our BinSAFE system is designed for use in security-sensitive scenarios. In this context, it is crucial to understand its behavior when analyzing obfuscated code or when facing adversaries capable of crafting binaries specifically to mislead the BinSAFE system (i.e., adversarial examples). The robustness of our system is closely tied to the underlying FS system, which is responsible for modeling the semantics of binary functions within the analyzed binary. Since SAFE was not trained to handle obfuscated code, this presents a clear limitation for the entire BinSAFE system, as well as its vulnerability to adversarial examples, as demonstrated in [22, 23].
In this paper, we presented our BinSAFE system. Our main contribution is a technique to extend FS
similarity systems to BCS. In this paper, we tested our system using SAFE [
During the preparation of this work, the author(s) used ChatGPT, Grammarly in order to: Grammar and spelling check, Paraphrase and reword. After using this tool/service, the author(s) reviewed and edited the content as needed and take(s) full responsibility for the publication’s content. [17] ReFirmLabs, Binwalk, https://github.com/ReFirmLabs/binwalk, 2024. [18] National Security Agency (NSA), Ghidra Software Reverse Engineering Framework, https: //ghidra-sre.org, 2024. Last Accessed: 2024-11-29. [19] Y. Wang, L. Wang, Y. Li, D. He, T. Liu, A theoretical analysis of NDCG type ranking measures, in: Proceedings of the 26th Annual Conference on Learning Theory (COLT ’13), volume 30, 2013, pp. 25–54. [20] Q. Feng, R. Zhou, C. Xu, Y. Cheng, B. Testa, H. Yin, Scalable graph-based bug search for firmware images, in: Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security (CCS ’16), ACM, 2016, pp. 480–491. [21] Y. David, E. Yahav, Tracelet-based code search in executables, in: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14), 2014, pp. 349–360. [22] G. Capozzi, D. C. D’Elia, G. A. D. Luna, L. Querzoni, Adversarial attacks against binary similarity systems, IEEE Access 12 (2024) 161247–161269. [23] G. Capozzi, T. Tang, J. Wan, Z. Yang, D. C. D’Elia, G. A. D. Luna, L. Cavallaro, L. Querzoni, On the lack of robustness of binary function similarity systems, CoRR abs/2412.04163 (2024). arXiv:2412.04163.
We present our matching procedure in Algorithm 1. Here, we begin by computing the similarity matrix (line 2), calculating the pairwise similarity between the functions in 1 and 2 using SAFE. Then, we match by name library functions, setting their similarity to 1 or 0 and scaling it by frequency. At this point, every pair of matched library functions is considered a hotspot, so the procedure tries to recursively match all the matchable neighbors of the pairs identified before (lines 3-8). After this first phase, we now start matching the user-defined functions (line 9) by iteratively determining the next hotspot pair and matching the subsequent pairs along the two graphs (lines 11-16). Finally, we identify the percentage of matched functions in 1 and 2 (line 17) and calculate the similarity (line 18) using Equation 1.
An important aspect of our approach is deciding which function pairs from the two call graphs to match. The strategies introduced in Section 3 pair only those functions from the two binaries with a similarity score above a specified threshold , which is determined through experimental evaluation.
In these experiments, we perform 181 queries on a knowledge base containing 5,256 binaries and libraries. Specifically, the knowledge base includes binaries from the following projects: busybox, coreutils, dnsmasq, dropbear, libBoost, lighttpd, libzip, readline, and zlib. These binaries were compiled for the amd64 architecture using gcc 8.3, gcc 10.2, clang 11, and clang 13.
The results of these experiments are presented in Figure 3, where we evaluate the performance of BS-LF using three threshold values for : 0, 0.50, and 0.75. All metrics indicate a significant diference between = 0 and ∈ {0, 50, 0.75}. Specifically, considering nDCG, there is an average increase of 1.49% from 0 to 0.50 and 1.78% from 0 to 0.75, with a smaller improvement of 0.3% between 0.50 and 0.75. A similar trend is observed for precision and recall: precision improves by 1.61% from 0 to 0.50 and 2.24% from 0 to 0.75, while recall increases by 2.3% from 0 to 0.50 and 3.41% from 0 to 0.75.
For our experiments, we choose the value = 0.75.
Algorithm 1 Matching algorithm for computing similarity at the binary level • Call graphs: 1 = (1, 1) and 2 = (2, 2). • getSimilarities(1, 1, 2, 2): Compute the pairwise similarity between functions in 1 and 2 using SAFE.
Match library functions by name in 1 and 2, setting similarity to 1 or 0, then scale by frequency. Set similarity between library and user-defined functions to 0. Return matched library function pairs and the similarity matrix. • getNeighbors(, ): Get neighbors of in the call graph . • matchNeighbors(1, 2, m, sim_matrix): Match recursively functions in 1 and 2 if their similarity is above and if they have not already been matched in m. • getUnmatched( , m): Get the functions in that are not part of any match in m. • getCoverage(1, 2, matches): Get the percentage of functions across 1 and 2 that are in m.
• computeSim(sim_matrix, 1, 2): Compute the similarity according to Equation 1. 1: matches ← () 2: match_libs, sim_matrix ← 3: for ⟨, ⟩ ∈ match_libs do 4: sim_score ← sim_matrix[ ][] 5: matches.add( , , sim_score) 6: 1, 2 ← getNeighbors(1, ), getNeighbors(2, ) 7: if sim_score ≥ AND ⟨, ⟩ ∈/ matches then 8: matches ← matchNeighbors(1, 2, matches)
getSimilarities(1, 1, 2, 2) 9: 1, 2 ← getUnmatched(1, matches), getUnmatched(2, matches) 10: while 1 ̸= ∅ AND 2 ̸= ∅ AND ∃ ⟨, ⟩ ∈ 1 × 2 s.t. sim_matrix[ ][] ≥ do 11: , , sim_score ← getHotspot(1, 2, sim_matrix, matches) 12: matches.add( , , sim_score) 13: 1, 2 ← getNeighbors(1, 1), getNeighbors(2, 2) 14: matches ← matchNeighbors(1, 2, matches) 15: 1.remove(1) 16: 2.remove(2) 17: 1, 2 ← getCoverage(1, 2, matches) 18: return computeSim(sim_matrix, 1, 2) 0.05 0.50 0.45 0.40 G CD0.35 n 0.30 0.25 0.20 0.25 0.20 10
Top K 1 5 15 20 1 5 10 Top K 15 20