REVDECODE: Enhancing Binary Function Matching with Context-Aware Graph Representations and Relevance Decoding

REVDECODE: Enhancing Binary Function Matching with Context-Aware Graph Representations and Relevance Decoding

Speakers: Tongwei Ren

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=Hgt0_b9VUDo

Overview

Binary function matching is a foundational problem in reverse engineering, critical for tasks such as identifying known libraries in embedded firmware, isolating vulnerable functions, and understanding code reuse. However, this seemingly straightforward task is complicated by the myriad of variations introduced during compilation, including different settings, optimization levels, and compiler versions. Existing function matchers often struggle to provide truly relevant matches, prioritizing structural similarity over the insights a reverse engineer actually needs. This talk introduces RevDECODE, a novel framework that addresses these limitations by shifting the focus from mere similarity to relevance decoding through the intelligent use of contextual information.

RevDECODE, presented by Tongwei Ren, is not a new function matching technique in itself, but rather an enhancement framework designed to significantly improve the accuracy and utility of existing matchers. It achieves this by building context-aware graph representations of binary functions and their interdependencies, then employing a relevance decoding process to rank matches more effectively. This approach promises to bridge the critical gap between structural similarity and practical relevance, offering reverse engineers a more powerful and nuanced tool for analyzing complex binary code.

The significance of RevDECODE lies in its ability to provide more meaningful insights in scenarios where traditional matchers fall short. By leveraging surrounding binary context, it can recover relevant matches that appear structurally dissimilar due to version differences or compilation variations, and resolve ambiguities among functions that lack distinctive features. This has profound implications for vulnerability research, intellectual property protection, and overall binary analysis, making it easier to pinpoint specific software components and their origins within opaque binaries.

Background

▶ Watch: Introduction to binary function matching problem (0:00)

The problem of binary function matching is a long-standing challenge in the field of reverse engineering. At its core, it involves taking an "unknown" function from a binary and finding its most similar (or identical) counterpart within a pre-compiled and labeled "corpus" of known functions. The utility of this process is vast, ranging from quickly identifying standard library functions in proprietary firmware to pinpointing specific vulnerable code segments in closed-source applications. For instance, a reverse engineer might use function matching to determine if a specific version of a cryptographic library, known to contain a vulnerability, is present in an embedded device.

Despite its importance, binary function matching is inherently complex due to the transformations binaries undergo during compilation. Different compilers, optimization levels (e.g., -O0, -O1, -O2, -O3), target architectures, and even minor version changes in libraries can drastically alter the compiled machine code, control flow graphs, and instruction sequences. These variations often lead to structural dissimilarities even when the underlying source code logic remains identical.

Traditional research approaches to function matching employ a variety of techniques, including analyzing control flow structures, generating function embeddings using machine learning, or creating signature matching heuristics. While these methods generate abstract representations of functions and rely on similarity scores to quantify how alike an unknown function is to those in the corpus, they suffer from several key limitations:

1. Focus on Similarity over Relevance: Existing matchers predominantly focus on structural similarity. However, as highlighted by the speaker, reverse engineers often prioritize relevance – whether a match provides meaningful insights – over mere structural resemblance. For example, a function custom_X_copy from libSSL 3.5.0 might be structurally less similar to libSSL 3.0.2 (an older, more relevant version in the corpus) than to alpha_arm_size_stops from libBFD 2.30. Even if alpha_arm_size_stops yields a higher similarity score (e.g., 0.68 by Diaphora), the libSSL 3.0.2 match (e.g., 0.44 similarity score) is far more meaningful for identifying potential vulnerabilities or understanding the library's evolution. This discrepancy between similarity and relevance is a critical hurdle.

1. Impracticality of Exhaustive Corpora: It is practically impossible to build an exhaustive corpus that includes every possible version and compilation variant of every function. A corpus might contain libBFD versions 1.0 to 3.0, but the target binary might use libBFD 3.5.0. In such cases, existing matchers might fail to find a direct match or provide a suboptimal one.

1. Ambiguous Matches: Common or highly similar functions, especially across different versions of the same library, are difficult to distinguish. This can lead to ambiguous matches where a matcher cannot confidently differentiate between several plausible candidates, leaving the reverse engineer with an inconclusive result. These limitations underscore the need for a more context-aware and relevance-driven approach, which RevDECODE aims to provide.

Key Findings

▶ Watch: Introducing REVDECODE and its core idea (3:00)

RevDECODE introduces a paradigm shift in binary function matching by leveraging contextual information to prioritize relevance over raw similarity. The key findings from its development and evaluation demonstrate a significant improvement in the quality and utility of function match results:

1. Significant Improvement in Ranking Quality: RevDECODE consistently and substantially enhances the quality of function rankings produced by various existing matchers. Across general purpose binaries (including binutils, busybox, and openssl compiled across different versions), 56.3% to 97.3% of rankings were improved. For example, when applied to BinSim, nearly 40% of rankings achieved an ideal best score of 1.0, indicating perfect relevance. Similarly, for Franken binaries (synthetic firmware samples simulating real-world properties), 72.3% to 98.8% of rankings saw improvement. This widespread enhancement across diverse datasets and underlying matchers highlights RevDECODE's robust and generalizable nature.

1. Recovery of Relevant, Structurally Dissimilar Matches: One of RevDECODE's most crucial contributions is its ability to recover relevant matches that are structurally dissimilar due to version or compilation differences. A compelling example provided is how BinSim initially misidentified an uncompress function from libUbuntu 20.04 as get_abs_looked_express from S 2.24, ranking the correct uncompress (from libUbuntu 14.04) at a dismal 187th position. RevDECODE, by incorporating library context from surrounding matches, corrected this, promoting the relevant uncompress function to the top position. This demonstrates its power in overcoming the "similarity vs. relevance" gap.

1. Resolution of Ambiguities: RevDECODE effectively resolves ambiguities among functions that lack distinctive features, such as distinguishing the same function from different versions of the same library. In the general-purpose dataset, approximately 35% of the 200,000 improved BinSim rankings fell into this category, representing 70,000 instances where RevDECODE provided clarity where traditional matchers struggled. This capability is vital for precise version identification and vulnerability analysis.

1. Importance of Contextual Components: An application study revealed the critical role of each component in RevDECODE's weight calculation and the utility of uncertain nodes. The more components RevDECODE utilized, the better its performance. Specifically, uncertain nodes were found to be instrumental in mitigating irrelevant context chains, leading to a 7% decrease in context chain-introduced ranking errors. This underscores the thoughtful design of its graph representation and weighting scheme.

1. Scalability through GPU Acceleration: Recognizing the need for scalability when dealing with larger graphs and binaries, RevDECODE incorporates parallel graph traversal algorithms designed for GPU acceleration. Both the fine-grained traversal and segment-based estimation traversal algorithms achieved substantial speedups compared to naive traversal and CPU baselines. The segment-based traversal, in particular, offered significant performance gains with only a negligible reduction (0.003 NDC reduction) in accuracy, ensuring RevDECODE's applicability to real-world, large-scale binary analysis tasks.

Technical Deep Dive

▶ Watch: REVDECODE's three-phase graph-based architecture (4:10)

RevDECODE's core innovation lies in its concept of relevance decoding from context. It operates on the observation that existing function matchers often overlook the rich contextual information surrounding individual functions within a binary, such as preceding and succeeding code segments, and the interdependencies between functions. This contextual information provides crucial insights into function relationships that go beyond isolated structural comparisons. RevDECODE is designed as a framework to enhance the accuracy of any underlying function matcher, rather than replacing them.

The RevDECODE process is structured into three distinct phases: Graph Construction, Graph Traversal Weight Computation, and Graph Traversal Ranking.

Phase 1: Graph Construction

The initial phase transforms the raw outputs of an existing function matcher into a sophisticated directed layered graph representation. This graph is the backbone of RevDECODE's contextual analysis:

• Nodes and Columns: Each column in the graph represents an unknown function from the target binary, arranged sequentially according to their order in the binary. Within each column, individual nodes represent potential matches for that unknown function, as suggested by the underlying function matcher (e.g., func_A from the binary might have match_1, match_2, match_3 as nodes in its column).
• Uncertain Nodes: A key feature is the inclusion of uncertain nodes. These nodes are designed to manage situations where the reference corpus is incomplete or lacks a direct, high-confidence match for a given unknown function. They prevent irrelevant matches from propagating contextual errors and ensure the framework can handle real-world corpus limitations.
• Edges and Interdependencies: Connections (edges) between nodes encode function interdependencies and contextual relationships. An edge typically connects a match from one unknown function's column to a match from a subsequent unknown function's column, representing a potential call relationship or sequential execution flow.
• Weighted Edges: The edges are assigned weights, which are a carefully calculated combination of several scores, designed to capture both similarity and contextual relevance:
• Similarity Scores: These are the foundational scores provided by the underlying function matcher (e.g., BinSim, Diaphora, SAFE, Gemini). They quantify the structural resemblance between the unknown function and its potential match.
• Confidence Scores: These scores reflect the uniqueness and strength of the matched features between two functions. A higher number of unique, matched features leads to a higher confidence score, indicating a more reliable match.
• Library Scores: This component assesses the uniqueness of the matched library within the corpus. If a matched function belongs to a library that is rare or highly specific within the corpus, it receives a higher library score, indicating greater relevance.
• Adjacency Scores: This is a critical contextual signal. It quantifies the relationship between two connected matches (i.e., matches for adjacent functions in the binary). For example, if two adjacent functions in the unknown binary are matched to functions from the same library and version in the corpus, their adjacency score would be high, reinforcing the likelihood that these are indeed correct, contextually related matches.

Phase 2: Graph Traversal Weight Computation

Once the graph is constructed, RevDECODE proceeds to identify the most relevant paths through it. This phase focuses on computing the maximum weight paths:

• Viterbi-Inspired Forward Pass: To efficiently compute these paths, RevDECODE employs a Viterbi-inspired forward pass algorithm. This dynamic programming approach iteratively calculates the maximum cumulative weight to reach each node in the graph, starting from the beginning. By doing so, it identifies all nodes that lie on at least one of the maximum weight paths, effectively highlighting sequences of matches that are maximally relevant given the contextual information.

Phase 3: Graph Traversal Ranking

The final phase involves ranking the matches for each unknown function based on their proximity and contribution to the identified maximum weight paths:

• Backward Pass Ranking: RevDECODE uses a backward pass algorithm, starting from the end nodes of the graph. This pass evaluates how closely each match (node) is associated with the overall maximum weight paths. Nodes that are part of or strongly contribute to these high-relevance paths are ranked higher. This ensures that the output for each unknown function is a ranked list of potential matches, ordered by their contextual relevance, rather than just their isolated similarity score.

Parallelizing Graph Traversal

For RevDECODE to be scalable for large binaries and extensive corpora, the graph traversal process needs to be efficient. The sequential nature of traditional graph traversal algorithms presents challenges, particularly for GPU acceleration:

• Sequential Dependencies: Layer-by-layer computation in graph traversal often depends on the results from previous layers, limiting naive parallelization.
• Resource Utilization: Efficient division of workload is essential to maximize GPU resource usage.
• Memory Dependencies: Frequent accesses to cumulative weight matrices can create bottlenecks.

To address these, RevDECODE introduces three parallel traversal algorithms:

1. Naive Traversal: Serves as a baseline, a straightforward parallelization without specific optimizations.
2. Fine-Grained Traversal: Focuses on parallelizing edge computations efficiently, distributing the workload at a granular level.
3. Segment-Based Estimation Traversal: This algorithm employs a divide-and-conquer strategy. It partitions the graph into segments and processes them, trading minor accuracy losses for substantial speedups. The evaluation showed that this approach achieved greater speedups than fine-grained traversal, with a negligible reduction in accuracy (only 0.003 NDC reduction).

These parallelization efforts ensure that RevDECODE can handle large-scale binary analysis tasks, making its contextual enhancement practical for real-world scenarios.

Demo / Proof of Concept

▶ Watch: Evaluation results: significant ranking quality improvement (7:50)

While the talk did not feature a live, interactive demonstration of RevDECODE's functionality, the speaker presented a comprehensive evaluation that served as a robust proof of concept for the framework's effectiveness. This evaluation utilized two distinct datasets:

1. General Purpose Dataset: Comprising functions from widely used open-source projects such as binutils, busybox, and openssl. These projects were compiled across various versions and configurations, resulting in a dataset of 11 billion function matches used for testing.
2. Franken Binaries Dataset: A specially crafted dataset of synthetic firmware samples. These "Franken binaries" were designed to simulate key structural properties and complexities found in real-world firmware, providing a realistic testbed. This dataset generated 5.8 billion function matches for evaluation.

RevDECODE was evaluated on four different underlying function matchers: BinSim, Diaphora, SAFE, and Gemini. The evaluation used NDCG (Normalized Discounted Cumulative Gain), a common metric for ranking quality, to measure improvements. The consistent and significant improvements across these diverse matchers and datasets, as detailed in the "Key Findings" section, strongly validated RevDECODE's design and capabilities. The specific examples, such as the uncompress function misidentification by BinSim and its correction by RevDECODE, effectively served as illustrative proof points for the framework's ability to recover relevant matches and resolve ambiguities.

Defensive Implications

▶ Watch: Key benefits: recovering relevant matches, resolving ambiguities (8:50)

RevDECODE offers significant advantages for defenders, enhancing their capabilities in several critical areas of binary security analysis:

1. Improved Vulnerability Identification: By providing more relevant and accurate function matches, RevDECODE drastically improves the ability to identify known vulnerable functions within closed-source binaries, firmware, or proprietary software. Defenders can more reliably pinpoint if a specific version of a library containing a CVE is present, even if it's heavily optimized or custom-compiled, enabling faster patching or mitigation strategies. For instance, if a known flaw exists in libPNG 1.6.37, RevDECODE can help confirm its presence (or absence) in a target binary with higher confidence than traditional matchers.

1. Enhanced Supply Chain Security: In complex software supply chains, identifying the exact components used in a final product can be challenging. RevDECODE facilitates better Software Bill of Materials (SBOM) generation by more accurately identifying library versions and their functions. This allows organizations to understand their attack surface more thoroughly and react quickly to newly discovered vulnerabilities affecting specific dependencies.

1. Accurate Patch Analysis: When analyzing patched binaries, defenders need to understand precisely which functions have been altered. RevDECODE can help distinguish between different versions of the same function, even with minor changes, making it easier to confirm if a specific security patch has been correctly applied or if a vulnerability still persists in a slightly modified form. This is crucial for validating security updates.

1. Better Malware Analysis and Attribution: For malware analysts, understanding the functionality of unknown binaries is paramount. RevDECODE can assist in attributing malware to known families by identifying shared code or specific library usages, even when obfuscation or custom compilation settings are employed. This can accelerate reverse engineering efforts and aid in developing more effective detection signatures.

1. Robust Intellectual Property Protection: Organizations can use RevDECODE to detect unauthorized reuse of their proprietary code in third-party binaries with greater accuracy. By identifying relevant matches of their unique functions, they can uncover potential IP infringements that might otherwise be masked by compilation differences or minor code alterations.

1. Reduced False Positives and Negatives: By focusing on contextual relevance, RevDECODE helps reduce both false positives (irrelevant matches distracting analysts) and false negatives (missed relevant matches due to structural dissimilarity). This leads to more efficient and reliable security analysis workflows, saving valuable time and resources for security teams.

Key Takeaways

• Relevance over Similarity: Binary function matching needs to prioritize relevance (meaningful insights for reverse engineers) over mere structural similarity, which is often insufficient due to compilation variations.
• Context-Aware Graph Representation: RevDECODE introduces a novel framework that enhances existing function matchers by building a directed layered graph capturing function interdependencies and contextual relationships within the binary.
• Significant Accuracy Improvements: The framework demonstrably improves the ranking quality of existing matchers, with 56.3-97.3% improvement for general-purpose binaries and 72.3-98.8% for synthetic firmware (Franken binaries).
• Resolving Ambiguities and Recovering Matches: RevDECODE excels at recovering relevant matches that are structurally dissimilar (e.g., due to version differences) and resolving ambiguities among functions lacking distinctive features, offering clarity in complex scenarios.
• Scalability through GPU Acceleration: To handle large-scale binaries and corpora, RevDECODE incorporates parallel graph traversal algorithms, specifically the segment-based estimation traversal, which provides substantial speedups with minimal accuracy loss.
• Enhancement Framework: RevDECODE is designed as an enhancement framework, compatible with and improving the performance of any underlying function matcher, making it a versatile tool for binary analysis.

About the Speaker(s)

The talk was presented by Tongwei Ren. Based on the transcript, Tongwei Ren is the primary researcher behind RevDECODE, articulating the problem, the proposed solution, and the evaluation results. No further biographical details were provided in the transcript or metadata.