DOCSEARCHbyAlgolia
Submit Docs

QBinDiff Binary Diffing Tool

repository·main·Indexed 42 days ago

https://github.com/quarkslab/qbindiff

An experimental binary diffing tool that treats diffing as a Network Alignment Quadratic Problem. It uses an optimization-based machine learning approach (Belief Propagation) to match binaries, supporting backends like BinExport and Quokka. QBinDiff allows for programmatic tuning of features, enforcement of specific matches, and a configurable balance between function similarity and callgraph emphasis.

Tokens
22.8K
Snippets
53
Records
132
Agent score
50%

What's inside QBinDiff

  1. Overview of QBinDiff

    main

    QBinDiff is an experimental binary-diffing tool that treats diffing as a Network Alignment Quadratic Problem. Unlike traditional tools like Bindiff, QBinDiff is designed for high flexibility, allowing users to programmatically tune the diffing process.

    Key capabilities include:

    • Custom Features: Define your own criteria for matching (e.g., data-oriented instead of just control-flow).
    • Enforced Matches: Manually enforce specific matches between nodes.
    • Tunable Emphasis: Choose to emphasize either function content (similarity) or the callgraph (topology).

    Important Considerations:

    • Experimental Status: It is a tool for power-users. Obtaining high-quality results typically requires tuning various parameters, features, thresholds, and weights.
    • Memory Constraints: There is a limit on binary size. Attempting to diff binaries with more than 10,000 functions may result in Out of Memory (OOM) errors.
    • Performance: QBinDiff prioritizes flexibility over execution speed.

  2. What is QBinDiff

    main

    QBinDiff is an experimental binary diffing tool that treats diffing as a Network Alignment Quadratic Problem. Unlike traditional tools like Bindiff, QBinDiff allows for programmatic tuning of the diffing process.

    Key capabilities include:

    • Defining custom features for diffing (e.g., data-oriented instead of just control-flow/instructions).
    • Enforcing specific matches.
    • Emphasizing function content (similarity) or callgraph links.

    It uses an optimization-based machine learning approach to approximate the best match for the APX-hard graph alignment problem. It supports backends like BinExport and Quokka for exported IDA disassemblies.

  3. Use the qbindiff Binary Loader API

    main
    The qbindiff.loader module provides a high-level interface for interacting with loaded binary programs. It exposes a hierarchical model of a binary, starting from the Program level down to individual Instruction operands and Data elements. This interface allows developers to programmatically traverse functions, basic blocks, and instructions within a loaded binary.

  4. How QBinDiff's graph alignment works

    main

    QBinDiff solves the graph matching problem by finding the best mapping between nodes of a primary graph and a secondary graph. It uses a machine learning approach (specifically optimization via belief propagation) to approximate the solution to this APX-hard problem.

    The algorithm combines two distinct information sources:

    1. Similarity Matrix: Domain-specific information representing the similarity between individual nodes (e.g., how similar two functions are).
    2. Topology Similarity: Information regarding the structure/edges of the graphs (the callgraph).

    Users can control the balance between these two sources using a tradeoff parameter α (alpha), which weights the importance of topology versus node similarity.

  5. Configure the tradeoff between similarity and structure

    main

    QBinDiff balances two aspects of a binary: similarity (based on function attributes/features) and structure (the Call Graph topology). The tradeoff parameter controls this balance:

    • Tradeoff = 0: The algorithm relies exclusively on the topology (structure) to diff the binaries.
    • Tradeoff = 1: The algorithm relies solely on similarity.

    Warning: Some features (such as ChildNb or GraphCommunities) inherently consider the call graph topology. Therefore, even with a tradeoff of 1, topology may still influence the results.

  6. Use Quokka backends for program analysis

    main
    The Quokka backend provides a set of specialized classes for interacting with program data extracted via Quokka. These backends allow for granular access to different levels of program structure, including the overall program, individual functions, basic blocks, instructions, and operands. Use these classes when building custom loaders or analysis tools that require deep integration with Quokka's data representation.

  7. Choose a distance metric for feature similarity

    main

    The qbindiff.QBinDiff object uses distance metrics to measure the similarity between feature vectors. Most available distances are derived from Scipy and operate on 1-D arrays.

    Important Note: Certain features perform better with specific metrics. For example, the WeisfeilerLehman graph kernel works best with the cosine similarity metric.

    Available Scipy-based distances:

    • braycurtis
    • canberra
    • chebyshev
    • cityblock
    • correlation
    • cosine
    • euclidean
    • mahalanobis
    • minkowski
    • seuclidean
    • sqeuclidean

  8. How the QBinDiff algorithm works

    main

    QBinDiff computes a 1-to-1 mapping between matched components. By default, it performs diffing at the function level, though the API allows for diffing at the basic block level.

    Conceptually, QBinDiff treats binaries and generic graphs interchangeably (referring to the process as binary diffing for binaries and graph matching for graphs). The high-level workflow is:

    1. Attributed graph loading: Loading primary and secondary graphs (via a Backend loader for binaries).
    2. Differ instantiation: Initializing the differ with specific parameters.
    3. Similarity computation:
      • Anchoring: Identifying certain matches (e.g., imported functions) to serve as anchors.
      • Feature extraction: Extracting artifacts from functions.
      • Similarity matrix computation: Calculating similarity scores between all functions using a distance function.
      • Refinement: (Optional) Applying user-defined similarity matrix refinements.
    4. Belief propagation: Using the similarity matrix and the Call Graph (CG) topology with a machine learning algorithm to produce the final function mapping.
    5. Export: Outputting the results in various formats.

  9. Understand the GenericGraph and GenericNode abstractions

    main

    QBinDiff uses GenericGraph and GenericNode to provide a common interface for different types of graph representations.

    • GenericGraph: Represents a graph structure that can be processed by the differ.
    • GenericNode: Represents an individual node within a GenericGraph.

    By using these generic abstractions, the diffing engine can operate on various underlying graph implementations without needing to know their specific internal details.

  10. Supported disassembly backends

    main

    QBinDiff requires an exported disassembly of the programs being compared. It supports the following backends:

    • Quokka: The preferred backend. It produces extracted files that are more exhaustive and more compact on disk, making it suitable for large binary datasets.
    • BinExport: Supported for compatibility with Google's BinExport format.

  11. What are features and feature vectors?

    main

    In QBinDiff, features are heuristics used to populate the similarity matrix. They operate at various granularities (operand, instruction, basic block, or function level) to extract information and compute a feature vector.

    A feature vector acts as a mathematical embedding that characterizes a function. For example, counting the number of basic blocks in a function's Control Flow Graph (CFG) is a feature; similar functions are expected to have similar block counts.

    Important Note: Features rely on underlying assumptions (e.g., that similar functions have similar control flow). If these assumptions are violated—such as when functions are heavily obfuscated or compiled with different optimization levels—the features may produce irrelevant or misleading results.

  12. How similarity computation works in QBinDiff

    main

    QBinDiff computes similarity between nodes (functions or nodes in an attributed graph) of two input graphs: a primary graph and a secondary graph.

    Similarity is represented as a normalized value between [0, 1] and is stored in a similarity matrix $S$ of shape $(n_1, n_2)$, where $n_1$ and $n_2$ are the number of nodes in the primary and secondary graphs respectively. The value at position $[i_1, i_2]$ represents the similarity between the $i_1$-th node of the primary graph and the $i_2$-th node of the secondary graph.

    Users can refine these similarity values using the pass refinement system, which allows registering callbacks to adjust matrix values based on custom properties. This is useful for non-binary-diffing tasks involving attributed graphs.