SigmaDiff: Semantics-Aware Deep Graph Matching for Pseudocode Diffing

SigmaDiff: Semantics-Aware Deep Graph Matching for Pseudocode Diffing

Speakers: Lian Gao

Conference: NDSS Symposium

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

Overview

In the realm of binary security analysis, precisely identifying code similarities and differences between compiled programs is a foundational yet challenging task. This talk introduces SIGMADIFF, a novel system designed to perform semantics-aware deep graph matching for pseudocode diffing. Presented by Lian Gao at the NDSS Symposium, SIGMADIFF addresses critical limitations in existing binary and pseudocode diffing tools, which often struggle with compiler optimizations, decompiler noise, and scalability. By operating at a fine-grained, token-level, SIGMADIFF offers a significant leap forward in understanding code changes.

The talk highlights pseudocode diffing as a superior alternative to traditional binary diffing, primarily because pseudocode retains more semantic information, is human-readable, and naturally supports cross-architecture comparisons. SIGMADIFF's innovation lies in its unique combination of Intermediate Representation (IR)-level program dependency graph (PDG) construction, lightweight symbolic analysis for semantic feature extraction, and an enhanced Deep Graph Matching Consensus (DGMC) model. This integrated approach allows SIGMADIFF to overcome the brittleness of heuristic-based methods and the scalability issues of some learning-based techniques, providing robust and accurate results across diverse diffing scenarios crucial for security analysis.

The importance of SIGMADIFF cannot be overstated for security professionals. Tasks such as vulnerability lineage analysis, patch detection, code plagiarism identification, and auditing third-party libraries in complex software systems heavily rely on accurate code diffing. SIGMADIFF's ability to precisely locate changes at the pseudocode token level, even in the presence of aggressive compiler optimizations or cross-compiler/cross-architecture variations, empowers analysts to more efficiently identify and understand security-relevant code modifications, thereby strengthening software supply chain security and vulnerability response.

Background

▶ Watch: Introduction: Pseudocode Diffing Challenges and SIGMADIFF's Goal (0:00)

The landscape of code diffing has long been segmented, with distinct approaches for source code, binary code, and the less-explored domain of pseudocode. Source code diffing tools like GumTree and ClDiff typically build Abstract Syntax Trees (ASTs) and match them. However, these techniques are ill-suited for pseudocode, as decompiler and compiler transformations can drastically alter pseudocode ASTs, making direct comparison unreliable.

Binary diffing has seen more extensive research, but existing methods present significant drawbacks. Traditional approaches, such such as BinDiff, rely heavily on syntax-based heuristics. While effective in simple cases, these heuristics prove brittle and inaccurate when faced with common compiler optimizations (e.g., O0-O3), which can dramatically change the syntactic structure of code without altering its core semantics. Dynamic analysis-based methods, including Blanket Execution and BinSim, excel at capturing runtime semantics but are inherently limited by code coverage, making them impractical for large binaries where achieving comprehensive execution paths is infeasible.

More recently, learning-based approaches have emerged in binary diffing, with tools like Asm2Vec, PalmTree, InnerEye, and DeepBinDiff. Many of these operate at a coarse-grained function level, limiting their precision for fine-grained analysis. DeepBinDiff, a notable state-of-the-art tool, works at the basic block level using the TADW algorithm. While an improvement, it suffers from severe scalability issues on large binaries, often taking days to process, and its iterative nature hinders GPU acceleration. Furthermore, its reliance on basic block embeddings can still struggle without strong semantic cues like strings or library calls, and it cannot easily translate its results to the human-readable pseudocode level.

Pseudocode diffing, despite its potential advantages, has remained largely unaddressed. Diaphora is presented as the only known tool in this space, relying on simple string-based matching. This approach is inherently conservative, leading to high precision but often very low recall, as even minor syntactic variations (e.g., variable renaming, minor structural changes) can cause it to miss semantically equivalent code. The "noise" introduced by decompilers in inferring high-level features further exacerbates the problem for such simple methods.

SIGMADIFF builds upon two key areas: symbolic analysis and deep graph matching. Traditional value-set analysis (VSA) approximates numeric values, which can be insufficient for detailed semantic understanding. SIGMADIFF's lightweight symbolic analysis aims to capture how a value is calculated, providing richer semantic context. For graph matching, the system leverages the Deep Graph Matching Consensus (DGMC) model. DGMC is an end-to-end deep graph matching architecture that first generates initial matches based on local feature similarities using a Graph Neural Network (GNN), then iteratively refines these matches by ensuring neighborhood consensus. This iterative refinement makes DGMC robust to structural noise, providing a strong foundation for SIGMADIFF's semantics-aware approach to pseudocode diffing.

Key Findings

▶ Watch: Related Work: Limitations of Existing Diffing Tools (2:00)

SIGMADIFF introduces a robust and highly effective solution for pseudocode diffing, achieving significant advancements over existing methodologies. The core findings and contributions can be summarized as follows:

1. Novel Graph Neural Network-based Approach: SIGMADIFF proposes the first GNN-based approach specifically designed to generate token-level matching results for pseudocode. This addresses the critical gap in fine-grained, semantics-aware pseudocode diffing.
2. Semantics-Aware Feature Extraction: The system incorporates a flow-sensitive, call-site sensitive lightweight symbolic analysis. This innovative analysis extracts rich semantic information from a program's high-level Intermediate Representation (IRs), capturing not just values but how those values are computed, which is crucial for robustness against syntactic variations.
3. Enhanced Deep Graph Matching Consensus (DGMC) Model: SIGMADIFF significantly improves the design and training of the state-of-the-art DGMC model for the specific challenges of pseudocode diffing. Key enhancements include:

• A novel loss function that integrates data type and opcode type constraints, penalizing incompatible matches and boosting accuracy.
• A pre-training and fine-tuning schema that improves efficiency, generalizability, and reduces per-analysis runtime.
• Relaxed type compatibility rules to account for decompiler inference imperfections and control-flow changes.
• Increased GNN hops to capture broader neighborhood context in sparse IR graphs.
• An iterative algorithm to handle binaries too large for GPU memory.

1. Superior Performance and Efficiency: Extensive evaluations demonstrate that SIGMADIFF consistently and significantly outperforms state-of-the-art heuristic-based (Diaphora) and deep learning-based (DeepBinDiff) binary diffing techniques across multiple dimensions.

• Cross-version, Cross-optimization-level, Cross-compiler, and Cross-architecture Diffing: SIGMADIFF achieves substantially higher F1-scores, particularly excelling when optimization levels differ (e.g., 308% higher F1-score than Diaphora for O0 vs. O3). It shows strong generalization to unseen compilers.
• Efficiency: Despite leveraging GPU acceleration, SIGMADIFF's fine-tuning process takes an average of 203 seconds per binary pair on a GPU, making it practically applicable and significantly faster than DeepBinDiff for large binaries.

1. Robustness to Code Transformations: The model proves highly resilient to various code changes introduced by compiler optimizations, variable renaming, and minor structural alterations, maintaining accuracy where other tools fail.
2. Practical Value in Security Scenarios: Case studies on real-world software, including patch detection on open-source libraries (FFmpeg, libjpeg-turbo, OpenSSL) and vulnerability analysis on a closed-source application (Zoom), confirm SIGMADIFF's ability to precisely pinpoint vulnerabilities and critical code changes at the token level, easing manual investigation. For Zoom, it successfully identified 13 vulnerabilities, precisely pinpointing 8 at the token level.
3. Open-Source Availability: The source code of SIGMADIFF has been made publicly available, fostering further research and adoption.

Technical Deep Dive

▶ Watch: SIGMADIFF's Core Technical Approach: IR-Level Deep Graph Matching (4:00)

SIGMADIFF’s robust performance stems from its multi-stage, semantics-aware architecture, which processes binaries to generate precise pseudocode token matching. The system operates in three main stages: pre-processing, pseudocode diffing, and post-processing.

Pre-processing Stage

The goal of pre-processing is to extract semantic information from two given binaries and prepare the input for the diffing stage.

1. Graph Construction:

• For each binary, SIGMADIFF constructs an IR-level Interprocedural Program Dependency Graph (IPDG). Each node in the IPDG represents an IR statement, and edges denote control or data dependency relationships.
• The choice of Ghidra's high-level IR is crucial as it retains significant semantic information.
• To handle inter-procedural dependencies, special nodes are introduced for function calls: entry, argument, and return nodes for functions, and CALLSITE_RET and CALLSITE_ARG_n nodes at call sites. These summarize complex inter-procedural data and control flows.
• For simplicity in graph matching, control and data dependencies are treated equally as directed edges.

1. Semantic Features Extraction (Lightweight Symbolic Analysis):

• This is a cornerstone for generating robust node features. SIGMADIFF performs a lightweight inter-procedural symbolic analysis. Unlike traditional value-set analysis (VSA), this approach records how a value is calculated using symbolic expressions, offering richer semantic context.
• The IR syntax interpreted includes statements like STORE, BRANCH, RETURN, CALL, LOAD, and MULTIEQUAL (phi-nodes).
• Symbolic expressions can be simple formulas or sets of sources, capturing constants, strings, symbols, and arguments. Key symbolic operations include binop, sources, and merge. The merge operation is vital for handling multiple control flows and loop variants, iteratively reaching a fixed point for soundness.
• The inter-procedural analysis algorithm visits functions in post-order, collecting return values and updating expressions at call sites, making it call-site sensitive.

1. Node Feature Extraction:

• The output of the symbolic analysis—the symbolic expression and opcode—forms the initial node features.
• Constants, strings, and addresses are normalized to reduce noise.
• For conditional jump IRs (e.g., CBRANCH), the system backtracks to append input variables of status flags, reflecting the jump condition.
• A corpus of all IR expressions is built, and doc2vec is used to learn initial node embeddings. To improve efficiency and generalizability, the doc2vec model is pre-trained on a separate, unrelated binary (e.g., LLVM not binary v3.7.0 and v3.8.1) before being applied to the binaries under analysis. The dimension of these initial node embeddings is 128.

1. Function Feature Extraction and Call Graph Generation:

• Function-level features are extracted, including return values, side effects, loads, strings, library calls, and function parameter types. These are used for an initial function-level matching, which aids in selecting high-quality training nodes.
• A binary's call graph is constructed, initially ignoring indirect calls, to support this training node selection process.

Pseudocode Diffing Stage

This stage leverages the enhanced DGMC model in a semi-supervised fashion to generate IR-level matching results.

1. Training Node Selection:

• High-quality training nodes are crucial for semi-supervised learning. A two-step strategy is employed:
• Function-level Matching: A conservative function-level matching narrows the search space. Similarity scores are calculated between functions using extracted function features (e.g., Jaccard similarity for feature sets, combined by a multi-layer perceptron (MLP)). A 2-hop greedy matching algorithm, similar to DeepBinDiff's k-hop approach, identifies matched function pairs.
• Training Node Selection (IR pairs): Within these matched function pairs, IRs with unique symbolic expressions are identified. The intersection of these unique IR sets from both functions forms the set of training nodes.

1. Whole Binary Matching with Enhanced DGMC:

• The source and target IPDGs, along with the identified training nodes, are fed into the DGMC model. This matching is performed across the whole binary, not function-by-function, to account for changes like function inlining.
• The DGMC model uses a shared Graph Neural Network (GNN), Ψθ₁, to generate latent node embeddings. An initial soft correspondence matrix, S(0), is then calculated using the Sinkhorn algorithm.
• A second GNN, Ψθ₂, iteratively refines these matchings to achieve neighborhood consensus, eliminating incorrect matches.
• Key improvements to DGMC for pseudocode diffing:
• Enhanced Loss Function: The original DGMC loss is augmented with two new terms: L(data_type) and L(op_type). These terms penalize incompatible data types and opcode types between matched IRs using an exponential function, significantly boosting matching accuracy. The coefficients α and β for these custom loss terms are set to 0.1.
• Relaxed Type Constraints: To account for decompiler imperfections in type inference, type compatibility is relaxed. For instance, signed/unsigned integers, char/byte, and all pointer types are considered compatible. Comparison-related IR operations are also deemed compatible to tolerate control-flow changes.
• Increased Hops: The number of hops in the first GNN, Ψθ₁, is increased to 3 (from a default of 1 for Ψθ₂) to capture a larger neighborhood context, which is beneficial for sparse graphs like IPDGs. The hidden states for Ψθ₁ are 128, and for Ψθ₂ are 32. Both GNNs have 3 layers.
• Pre-training and Fine-tuning Schema: To improve efficiency and generalizability, the DGMC model is pre-trained offline on a large, unrelated binary for 800 epochs. For a specific binary pair, the pre-trained model is then fine-tuned for fewer epochs (200 epochs) with early-stopping (patience of 30 epochs). This significantly reduces the actual inference time.
• Iterative Algorithm for Large Binaries: For binaries exceeding GPU memory capacity, an iterative algorithm is implemented. This involves matching function pairs, reducing them to single nodes in their respective IPDGs, and repeating until the reduced graphs fit into GPU memory.

Post-processing Stage

In the final stage, SIGMADIFF refines the IR matching results and translates them to pseudocode token-level matches.

1. Pruning and Top-1 Selection: IR matching results are pruned using the type constraints discussed earlier. From the pruned candidates, the top-1 match is selected by referring to the soft correspondence matrix S.
2. Token-level Pseudocode Matching: Since each IR statement typically maps to a group of tokens in pseudocode, token-level pseudocode matching results are generated directly from the IR matching.
3. Refinement: Token matching can be further refined by utilizing IR variables and their corresponding tokens. Purely formatting tokens (indents, brackets, parentheses, commas) are ignored as they carry no semantic meaning.

Implementation Details and Hyperparameters

SIGMADIFF's lightweight symbolic analysis and IPDG generation are implemented based on Ghidra v9.2.2's APIs. The DGMC model implementation is based on the package released by its authors.

Key hyperparameters:

• Doc2vec initial node embedding dimension: 128.
• GNN hidden states: Ψθ₁: 128, Ψθ₂: 32.
• GNN layers: 3 for both.
• GNN hops: Ψθ₁: 3, Ψθ₂: 1.
• Training epochs: Pre-training: 800, Fine-tuning: 200 (with early-stopping patience of 30 epochs).
• Optimizer: Adam with a learning rate of 0.001.
• Loss function coefficients: α and β for custom loss terms: 0.1.

Experiments were conducted on a server with a Ryzen 3900X CPU, an RTX 2080Ti GPU (at least 11GB memory), 64GB RAM, and a 500GB SSD.

Demo / Proof of Concept

▶ Watch: System Design: Pre-processing and Graph Construction (6:00)

SIGMADIFF's practical utility was demonstrated through two compelling case studies in real-world security scenarios, showcasing its ability to provide precise and actionable insights.

1. Patch Detection on Open-source Libraries

This case study focused on the critical task of identifying security patches in widely used open-source libraries. SIGMADIFF was used to analyze eleven CVEs across three prominent libraries: FFmpeg, libjpeg-turbo, and OpenSSL. The process involved comparing older, vulnerable versions (compiled with GCC) against patched versions (compiled with both GCC and Clang).

The results indicated that SIGMADIFF accurately located most patches, performing substantially better than baseline tools, especially when compiler-introduced changes (e.g., cross-compiler comparisons) were present. This highlights SIGMADIFF's robustness in scenarios where replicating identical build environments is challenging, a common real-world impediment to effective patch analysis. By precisely pinpointing changes at the pseudocode token level, SIGMADIFF significantly streamlines the process of verifying patch application and understanding the security implications of updates.

2. Vulnerability Analysis on a Closed-source Application (Zoom)

The second case study involved a more complex scenario: investigating a closed-source application, Zoom, for embedded vulnerabilities. Windows and Linux versions of Zoom were analyzed to identify five embedded open-source libraries. Subsequently, known CVEs within these identified libraries were located using SIGMADIFF.

SIGMADIFF successfully identified thirteen vulnerabilities within Zoom's embedded libraries. Crucially, it precisely pinpointed eight of these vulnerabilities at the token level, marking them as insertions, deletions, or updates in the pseudocode. For the remaining five, SIGMADIFF accurately located the vulnerable functions. This level of granularity is invaluable for security analysts, as it drastically reduces the manual effort required to investigate and confirm vulnerabilities.

In contrast, traditional tools showed significant limitations:

• BinDiff precisely spotted only three vulnerabilities at the basic block level and located two functions. Its disassembly output, however, is notoriously harder for human analysts to interpret.
• Diaphora pinpointed two vulnerabilities at the token level and eight functions, but its results were less precise, particularly for large functions where its string-based diffing approach failed due to extensive syntactic changes unrelated to the vulnerability.

SIGMADIFF's ability to find exact changes regardless of variable renaming or code structure modifications proved invaluable in this real-world application. The analysis also confirmed that the latest Zoom version had fixed all listed CVEs except one, demonstrating the tool's efficacy in auditing third-party libraries and identifying lingering risks in complex software. This case study underscores SIGMADIFF's necessity for thorough security audits and its ability to uncover more vulnerabilities with higher precision.

Defensive Implications

▶ Watch: Detailed Semantic Feature Extraction via Symbolic Analysis (7:00)

SIGMADIFF offers several significant defensive implications for security professionals, enabling more proactive and precise security measures:

1. Accelerated Patch Analysis and Verification: Defenders can leverage SIGMADIFF to quickly and accurately identify differences between vulnerable and patched versions of software, even when binaries are compiled with different compilers or optimization levels. This is crucial for verifying that a patch has been correctly applied and understanding its exact security impact, especially in scenarios where source code is unavailable or build environments are inconsistent.
2. Enhanced Vulnerability Discovery in Third-Party Libraries: In modern software, third-party libraries constitute a significant attack surface. SIGMADIFF allows security teams to efficiently audit these components within closed-source or complex applications, precisely pinpointing known CVEs or identifying suspicious changes that might introduce new vulnerabilities. Its token-level precision helps in focusing manual review on critical code segments.
3. Improved Software Supply Chain Security: By enabling fine-grained diffing of binary components, SIGMADIFF can help identify unauthorized modifications or supply chain attacks. Any unexpected changes in embedded libraries or proprietary code can be quickly flagged, contributing to a more secure software development and deployment pipeline.
4. Understanding Compiler Optimization Effects: SIGMADIFF's resilience to compiler optimizations means defenders can analyze software variations without being misled by purely syntactic changes. This allows for a deeper understanding of how different compilation settings affect code behavior and security, which is vital for hardening and auditing.
5. Forensic Analysis and Incident Response: In post-incident scenarios, SIGMADIFF can aid in forensic analysis by identifying subtle changes in deployed binaries, potentially revealing backdoors, malware injections, or unauthorized updates that might be difficult to spot with traditional tools.
6. Code Plagiarism and IP Protection: While primarily a security tool, SIGMADIFF's ability to detect code similarity at a semantic level can also be applied to detect code plagiarism, helping organizations protect their intellectual property or identify unauthorized use of proprietary code.

Key Takeaways

• SIGMADIFF introduces a novel, semantics-aware approach for pseudocode diffing, addressing a critical gap in binary analysis tools.
• It leverages IR-level IPDGs, lightweight symbolic analysis, and an enhanced Deep Graph Matching Consensus (DGMC) model for robust and precise token-level matching.
• The system significantly outperforms state-of-the-art baselines like Diaphora and DeepBinDiff across cross-version, cross-optimization, cross-compiler, and cross-architecture diffing tasks, demonstrating superior accuracy and resilience.
• SIGMADIFF is practically efficient, with fine-tuning (inference) taking an average of 203 seconds on a GPU, making it suitable for real-world security analysis.
• Case studies on OpenSSL, FFmpeg, libjpeg-turbo, and Zoom highlight its effectiveness in patch detection and vulnerability analysis, precisely pinpointing critical code changes and known CVEs at the pseudocode token level.
• The source code for SIGMADIFF is publicly available, encouraging further research and adoption in the security community.

About the Speaker(s)

The talk "SigmaDiff: Semantics-Aware Deep Graph Matching for Pseudocode Diffing" was presented by Lian Gao. Based on the provided information, further specific details regarding their title or company are not available in the transcript or metadata.