The source code for the CFG SigMaker is available on GitHub. Only IDA Pro 9 is currently supported.

Introduction

Pattern matching is commonly used in reverse engineering to locate known instruction sequences inside compiled binaries. Traditional scanners usually rely on byte signatures built from a function’s machine code, with wildcard bytes used for values such as addresses, displacements, and relative branch offsets.

This approach works well when the generated code remains mostly unchanged. However, its reliability decreases once the same source code is rebuilt with a different compiler version, optimization level, or build configuration. Compilers may reorder instructions, replace operations with equivalent alternatives, merge or remove branches, unroll loops, inline functions, or eliminate code that is no longer required. These transformations can significantly change the final byte sequence without changing the behavior of the function.

Because traditional signatures describe instructions in a fixed linear order, even a small change may be enough to invalidate the entire pattern. This becomes especially problematic in functions containing several conditional branches, loops, early returns, or other complex control-flow structures. Two implementations may perform the same operation while sharing very few contiguous bytes.

A more resilient approach is to include structural information about the function in the signature. Instead of looking only at raw instruction bytes, the analyzer can examine properties such as the function prototype, its basic blocks, and the relationships between those blocks. These characteristics are generally less dependent on exact instruction encoding and can remain useful even when the compiler changes the layout of the generated code.

This article presents an IDA Pro plugin that generates and compares function signatures using recovered type information and control-flow graph characteristics. The goal is not to replace byte signatures entirely, but to provide an additional matching method for cases where traditional linear patterns are too fragile.

Why Simple Pattern Matching Can Break

Consider the following C function:

int process(int x)
{
    if (x < 0)
    {
        return -1;
    }

    if ((x & 1) == 0)
    {
        return x * 2;
    }

    return x + 1;
}

A possible x86_64 assembly implementation might look like this:

85 C9           test    ecx, ecx
78 0B           js      negative
F6 C1 01        test    cl, 1
75 05           jne     odd
8D 04 09        lea     eax, [rcx+rcx]
C3              ret

odd:
8D 41 01        lea     eax, [rcx+1]
C3              ret

negative:
B8 FF FF FF FF  mov     eax, -1
C3              ret

A pattern scanner may generate the following byte signature:

85 C9 78 ?? F6 C1 01 75 ?? 8D 04 09 C3

where ?? represents wildcard bytes for relative jump offsets.

This signature works only as long as the compiler emits the same sequence of instructions. After recompilation with a different optimization level, however, the compiler may generate a different implementation:

85 C9           test    ecx, ecx
78 09           js      negative
8D 04 09        lea     eax, [rcx+rcx]
F6 C1 01        test    cl, 1
75 01           jne     odd
C3              ret

odd:
FF C0           inc     eax
C3              ret

negative:
B8 FF FF FF FF  mov     eax, -1
C3              ret

Although both versions implement the same logic, the generated machine code differs:

  • Instruction ordering has changed.
  • Relative jump offsets are different.
  • lea eax, [rcx+1] has been replaced by inc eax.
  • The overall control flow is equivalent, but the byte layout is no longer identical.

As a result, the original signature fails to match the optimized binary despite the function behaving exactly the same.

This demonstrates one of the major weaknesses of simple pattern scanning quite well. Because it relies on contiguous byte sequences, even small compiler optimizations can invalidate an otherwise correct signature.

This article explores more robust techniques for pattern matching functions across compiled binaries. These approaches improve resilience against compiler optimizations and binary changes, making them valuable for tasks such as identifying malware families, tracking code reuse, and reverse engineering new software releases where traditional byte-pattern signatures may no longer be reliable.

Analyzing a function

Consider the following C function, which evaluates a transaction request based on the account balance, requested amount, user privileges, and the number of verification attempts. The function performs several validation checks, handles administrator overrides, calculates a checksum value through iterative processing, and returns a final transaction result based on the generated checksum.

#include <stdbool.h>

int32_t evaluate_transaction(
    int32_t balance,
    int32_t amount,
    bool is_admin,
    int32_t attempts)
{
    // request is invalid
    if (amount <= 0)
    {
        return -1;
    }

    // account overdrawn
    if (balance < amount)
    {
        if (!is_admin)
        {
            return -2;
        }

        // admin can override it
        balance = amount;
    }

    int32_t checksum = 0;

    for (int32_t i = 0; i < attempts; ++i)
    {
        checksum += (amount ^ i) & 0xF;

        if (checksum > 50)
        {
            break;
        }
    }

    if ((checksum & 1) == 0)
    {
        return balance - amount;
    }

    return balance - amount + checksum;
}

The function’s control-flow graph (CFG) can be represented as follows:

flowchart TD
    A([Start]) --> B{"amount <= 0?"}

    B -->|Yes| C([return -1])
    B -->|No| D{"balance < amount?"}

    D -->|Yes| E{"is_admin?"}
    D -->|No| F["checksum = 0"]

    E -->|No| G([return -2])
    E -->|Yes| H["balance = amount"]

    H --> F

    F --> I["i = 0"]

    I --> J{"i < attempts?"}
    J -->|No| K{"checksum even?"}
    J -->|Yes| L["checksum += (amount ^ i) & 0xF"]

    L --> M{"checksum > 50?"}
    M -->|Yes| K
    M -->|No| N["++i"]

    N --> J

    K -->|Yes| O([return balance - amount])
    K -->|No| P([return balance - amount + checksum])

Information That Can Be Extracted

Analyzing the function’s structure allows various characteristics to be extracted and used for pattern matching across different compiled binaries. Unlike raw byte signatures, these features capture higher-level information about the function’s behavior, structure, and control-flow organization.

The following information can be extracted:

  • Function arity (number of arguments)
  • Data type of each function argument
  • Function return type
  • Number of basic blocks within the function
  • Number of successors and predecessors for each basic block
  • Control-flow relationships between basic blocks

Extracting Function Information

IDA Pro’s Hex-Rays decompiler can be used to recover a function’s prototype and extract metadata such as its name, return type, argument count, and argument types.

The first step is to decompile the function and obtain a cfunc_t representation. The recovered function type can then be converted into a tinfo_t, from which detailed prototype information is extracted using func_type_data_t.

hexrays_failure_t failure;

const cfuncptr_t cfunc = decompile(ida_func, &failure);

if (!cfunc)
{
    logger::error("{:#018x}: decompilation failed - {} (errea={:#018x})",
        ida_func->start_ea,
        failure.desc().c_str(),
        failure.errea
    );

    return false;
}

qstring function_name;
get_func_name(&function_name, ida_func->start_ea);

tinfo_t function_type;

if (!cfunc->get_func_type(&function_type))
{
    logger::error("{:#018x}: failed to recover function type", ida_func->start_ea);

    return false;
}

func_type_data_t function_details;

if (!function_type.get_func_details(&function_details))
{
    logger::error("{:#018x}: failed to extract function type details", ida_func->start_ea);

    return false;
}

qstring prototype;

if (!function_type.print(&prototype))
{
    logger::error("{:#018x}: failed to format function prototype", ida_func->start_ea);

    return false;
}

this->m_name = function_name.c_str();
this->m_type_def = prototype.c_str();
this->m_num_args = function_details.size();

The resulting func_type_data_t object contains the recovered return type, calling convention, and information about each function argument. This information can be normalized and incorporated into the function’s structural signature.

Decompiler-generated types should not be treated as definitive. Their accuracy depends on the available symbols, type libraries, calling-convention analysis, and the quality of the decompilation. For reliable cross-binary matching, recovered types should therefore be normalized before comparison.

Building the Control-Flow Signature

The function prototype provides a useful first filter, but it is not enough to identify a function by itself. Many unrelated functions have the same return type and number of arguments. The main part of the signature therefore comes from the function’s control-flow graph.

The implementation is split into three main structures:

  • basic_block_t represents one basic block.
  • cfg_t represents the collection of blocks belonging to a function.
  • sig_t combines the CFG with the recovered function type information.

This keeps the IDA-specific extraction logic separate from the code used to serialize and compare signatures.

Extracting Basic Blocks from IDA

IDA exposes a function’s control-flow graph through qflow_chart_t. A flow chart is created for the address range occupied by the function:

qflow_chart_t flow_chart;

flow_chart.create(
    "",
    ida_func,
    ida_func->start_ea,
    ida_func->start_ea + ida_func->size(),
    FC_NOEXT
);

if (flow_chart.empty())
{
    return false;
}

The FC_NOEXT flag prevents external blocks from being included in the graph. This is useful because the signature is intended to describe the function itself rather than code outside its boundaries.

Once the flow chart has been created, each qbasic_block_t can be inspected. IDA provides the number of successor and predecessor blocks through nsucc() and npred(). The instructions inside the block are then decoded one at a time using decode_insn().

for (int i = 0; i < flow_chart.size(); ++i)
{
    const qbasic_block_t& ida_block = flow_chart.blocks[i];

    const std::size_t num_successors = flow_chart.nsucc(i);
    const std::size_t num_predecessors = flow_chart.npred(i);

    insn_t instruction = {};

    ea_t address = ida_block.start_ea;

    std::size_t first_type = 0;
    std::size_t last_type = 0;
    std::size_t num_instructions = 0;

    bool first_instruction = true;

    while (address < ida_block.end_ea)
    {
        const std::size_t length = decode_insn(&instruction, address);

        if (length == 0)
        {
            break;
        }

        if (first_instruction)
        {
            first_type = instruction.itype;
            first_instruction = false;
        }

        last_type = instruction.itype;
        ++num_instructions;

        address += length;
    }

    this->add_basic_block(
        num_instructions,
        num_successors,
        num_predecessors,
        first_type,
        last_type
    );
}

For every block, the analyzer currently records five values:

class basic_block_t
{
    std::size_t m_num_instr;
    std::size_t m_num_succ;
    std::size_t m_num_pred;
    std::size_t m_first;
    std::size_t m_last;
};

These values describe:

  • The number of instructions in the block.
  • The number of outgoing control-flow edges.
  • The number of incoming control-flow edges.
  • The IDA instruction type of the first instruction.
  • The IDA instruction type of the last instruction.

The first and last instruction types give a small amount of information about the block’s purpose without storing its complete instruction sequence. For example, a block ending in a conditional jump has a different shape from one ending in a return or an unconditional branch.

The implementation stores instruction.itype, which is IDA’s internal instruction identifier, rather than the encoded instruction bytes. This makes the descriptor independent of register allocation, immediate values, and relative branch offsets. However, these identifiers are processor-module-specific, so signatures should normally be compared only between binaries using the same architecture and IDA processor module.

After decoding a block, its descriptor is added to the CFG. The analyzer also keeps a count of the total number of decoded instructions in the function.

It is worth noting that the current implementation does not store the complete edge list of the graph. It records the number of predecessors and successors for each block, but not exactly which block connects to which. The signature is therefore a compact structural summary of the CFG rather than a complete graph representation.

Comparing Basic Blocks

Two basic blocks are compared by calculating a similarity value for each stored property. Numeric values are compared using the following formula:

\[ S(x,y) = \begin{cases} 1, & \text{if } x = 0 \text{ and } y = 0 \\[6pt] 1 - \dfrac{|x-y|}{\max(x,y)}, & \text{otherwise.} \end{cases} \]

This produces a result between zero and one. Equal values produce a similarity of 1.0, while increasingly different values move closer to zero.

For example, blocks containing ten and eight instructions have the following instruction-count similarity:

\[ 1 - \frac{|10-8|}{10} = 0.8 \]

Each block property is given a different weight:

constexpr double instruction_weight = 0.05;
constexpr double successor_weight   = 0.40;
constexpr double predecessor_weight = 0.40;
constexpr double first_type_weight  = 0.075;
constexpr double last_type_weight   = 0.075;

The predecessor and successor counts together account for 80 percent of the final block score. This makes the position and branching role of the block more important than its exact instruction count. The first and last instruction types each contribute 7.5 percent, while the instruction count contributes the remaining 5 percent.

The final score is calculated as a weighted sum:

return
    instruction_similarity * instruction_weight +
    successor_similarity   * successor_weight +
    predecessor_similarity * predecessor_weight +
    first_type_similarity  * first_type_weight +
    last_type_similarity   * last_type_weight;

These weights are heuristic rather than absolute. They were chosen to favor control-flow structure, since instruction counts tend to change more often as a result of compiler optimizations.

One limitation is that the first and last instruction types are treated as numeric values by the same distance formula. IDA instruction identifiers are categories, not measurements, so the numeric distance between two identifiers does not necessarily have semantic meaning. A stricter alternative would assign 1.0 when the instruction types are equal and 0.0 otherwise. They could also be grouped into broader categories such as conditional branch, unconditional branch, call, return, arithmetic, and data movement.

Comparing Control-Flow Graphs

After individual blocks can be compared, the next step is to compare two complete CFG signatures.

The implementation uses greedy one-to-one block matching. For every block in the first CFG, it searches for the most similar unmatched block in the second CFG:

std::vector<bool> matched(other_blocks.size(), false);

double total_similarity = 0.0;

for (const basic_block_t& source_block : source_blocks)
{
    double best_similarity = 0.0;
    std::size_t best_index = invalid_index;

    for (std::size_t i = 0; i < other_blocks.size(); ++i)
    {
        if (matched[i])
        {
            continue;
        }

        const double similarity = source_block.similarity(other_blocks[i]);

        if (similarity > best_similarity)
        {
            best_similarity = similarity;
            best_index = i;
        }
    }

    if (best_index != invalid_index)
    {
        matched[best_index] = true;
        total_similarity += best_similarity;
    }
}

Marking blocks as matched prevents one block in the target function from being reused for several source blocks. Once all possible matches have been selected, the total is divided by the larger block count:

const double normalization = static_cast<double>(
    std::max(source_blocks.size(), other_blocks.size()));

return total_similarity / normalization * 100.0;

Normalizing by the larger CFG means that unmatched blocks reduce the final score. For example, if one function has ten blocks and another has twelve, the two additional blocks cannot simply be ignored.

This method is relatively simple and fast, which makes it suitable for scanning all functions in an IDA database. It also allows blocks to appear in a different order, since matching is based on their characteristics rather than their position in the function.

Optimizing Block Matching

However, greedy matching does not always produce the globally optimal assignment. Each block from the first CFG is paired with the most similar unmatched block from the second CFG. A block selected early may therefore consume a candidate that would have been a much stronger match for another block later in the search.

Consider the following block similarity matrix:

B1 B2 B3
A1 0.90 0.80 0.10
A2 0.85 0.20 0.10
A3 0.10 0.70 0.95

A greedy algorithm processes A1 first and selects B1, since it has the highest similarity score of 0.90. Because B1 is now unavailable, A2 must be matched with B2 for only 0.20. Finally, A3 is matched with B3 for 0.95.

flowchart LR
    subgraph FA["Function A"]
        A1["A1"]
        A2["A2"]
        A3["A3"]
    end

    subgraph FB["Function B"]
        B1["B1"]
        B2["B2"]
        B3["B3"]
    end

    A1 -- "0.90" --> B1
    A2 -- "0.20" --> B2
    A3 -- "0.95" --> B3

The total score produced by the greedy assignment is:

\[ 0.90 + 0.20 + 0.95 = 2.05 \]

This is not the best possible assignment. Instead, A1 can be matched with B2, leaving B1 available for A2:

flowchart LR
    subgraph FA["Function A"]
        A1["A1"]
        A2["A2"]
        A3["A3"]
    end

    subgraph FB["Function B"]
        B1["B1"]
        B2["B2"]
        B3["B3"]
    end

    A1 -- "0.80" --> B2
    A2 -- "0.85" --> B1
    A3 -- "0.95" --> B3

The total score is now:

\[ 0.80 + 0.85 + 0.95 = 2.60 \]

Although the individual match for A1 is slightly worse, the complete assignment produces a higher score.

A more advanced implementation could use maximum-weight bipartite matching to avoid this problem. The basic blocks from the first CFG form one side of a bipartite graph, while the blocks from the second CFG form the other side. Every possible pair is connected by an edge whose weight is the calculated block similarity.

An assignment algorithm, such as the Hungarian algorithm, considers these edges together and selects the one-to-one block assignment with the highest total weight. Unlike the greedy approach, it does not commit to a match based only on the best choice available at the current step.

The current algorithm also compares block descriptors without checking the actual control-flow edges between matched blocks. Two CFGs with similar block-degree distributions may receive a high score even when their connections are arranged differently. Storing an adjacency list and checking whether edges between matched blocks are preserved would make the comparison more accurate.

Despite these limitations, the current implementation has produced reliable results during testing against several Windows kernel binaries, including ntoskrnl, hvix, and other kernel-related samples. The simpler greedy approach is still practical for real-world function matching, even though more advanced graph-matching techniques could improve its accuracy in difficult cases.

Constructing and Serializing a Signature

The sig_t class combines the structural CFG information with data recovered by Hex-Rays:

class sig_t
{
    cfg_t m_cfg;

    std::string m_name;
    std::string m_type_def;
    std::size_t m_num_args = 0;
};

When a signature is generated, the CFG is extracted first. The function name, printed prototype, and argument count are then added to it.

The signature can be serialized to JSON using nlohmann::json. The generated object contains the function prototype, argument count, total instruction count, number of blocks, and an array of block descriptors.

A generated signature has approximately the following form:

{
  "type_def": "int32_t __fastcall evaluate_transaction(int32_t, int32_t, bool, int32_t)",
  "num_args": 4,
  "num_total_instr": 31,
  "num_blocks": 12,
  "basic_blocks": [
    {
      "num_instr": 2,
      "num_succ": 2,
      "num_pred": 0,
      "first": 105,
      "last": 184
    },
    {
      "num_instr": 2,
      "num_succ": 0,
      "num_pred": 1,
      "first": 73,
      "last": 201
    }
  ]
}

The exact instruction identifiers and block counts depend on the architecture, compiler, optimization settings, and the code produced for the function.

JSON was used because it is easy to inspect, copy, store, and transfer between IDA databases. It also makes it possible to add more signature fields later without defining a custom binary format.

When a signature is loaded, the deserializer checks for the required fields and rebuilds each basic_block_t entry. Malformed JSON, missing fields, and incorrect value types are handled as errors instead of being silently accepted.

The function name is not serialized because it is only useful when displaying search results. It should not influence matching, since stripped binaries commonly contain automatically generated names such as sub_140001000.

Searching for a Matching Function

Searching begins by deserializing the supplied JSON signature. The analyzer then iterates over every function in the current IDA database:

const std::size_t function_count = get_func_qty();

for (std::size_t i = 0; i < function_count; ++i)
{
    func_t* function = getn_func(i);

    if (!function)
    {
        continue;
    }

    if (function->flags & (FUNC_NORET | FUNC_THUNK | FUNC_OUTLINE))
    {
        continue;
    }

    // Build and compare the candidate signature.
}

Functions marked as non-returning, thunks, or outlined code are skipped. These functions often have unusual or compiler-generated layouts and are less useful as normal matching candidates.

For each remaining function, the plugin constructs a temporary signature. Before performing the CFG comparison, it applies an exact type filter:

if (!reference_signature.equal_type_def(candidate_signature))
{
    continue;
}

equal_type_def() currently requires both the argument count and the complete printed type definition to match. Only functions passing this filter have their CFG similarity calculated. The results are then sorted from highest to lowest similarity and shown in an IDA chooser.

Using the prototype as a first-stage filter greatly reduces the number of CFG comparisons. It can also reduce false positives when a binary contains many functions with similar control-flow shapes.

The disadvantage is that exact textual prototype matching is strict. The following prototypes may describe effectively compatible functions but fail the comparison:

int process(int value);
int32_t process(int32_t value);
LONG process(LONG value);

Typedef names, calling conventions, imported type libraries, and Hex-Rays type recovery can all change the printed prototype. A more tolerant implementation could compare normalized type categories instead:

return: signed integer, 32 bits
arguments: 1. signed integer, 32 bits

Pointer types could similarly be reduced to properties such as pointer depth, pointed-to size, and whether the pointee is known. This would preserve useful type information without depending on identical typedef names.

Caching Decompiled Function Information

Decompiling every function during every comparison would be expensive. To avoid repeatedly invoking Hex-Rays, the plugin contains a cache indexed by function address:

std::unordered_map<ea_t, decompiled_func_t> decompiled_functions;

Before a search begins, the plugin walks through the IDA function list and decompiles eligible functions. The recovered name, printed type definition, and argument count are stored in the map. Later, sig_t::from_ida_func() retrieves this information using the function’s start address instead of decompiling it again.

The search dialog also checks whether a cache already exists. If it does, the user can choose whether to reuse it or decompile the database again. This is useful after manually correcting function types because the old cache may no longer represent the current IDA database.

The decompilation pass also visits direct call references and attempts to decompile their target functions. This can help Hex-Rays discover type information for functions involved in the current call graph. In the current implementation, the callee metadata is not included directly in the generated signature.

Plugin

The plugin supports two main operations:

  1. Generate a signature for the function under the cursor.
  2. Search the current IDA database using an existing JSON signature.

When generating a signature, the analyzer verifies that the current address belongs to a valid function. Library functions, thunks, and functions smaller than five bytes are rejected. It then extracts the CFG, obtains the decompiler information, serializes the result, and writes the JSON signature to IDA’s output window.

During a search, the user pastes a previously generated signature. The plugin prepares the decompiler cache, scans the function database, filters candidates by prototype, computes CFG similarity, and displays the sorted results.

This produces a workflow similar to an ordinary byte-signature scanner, except that the signature describes the function’s structure rather than a continuous region of machine code.

Current Limitations

This implementation is intended as a starting point rather than a complete binary-diffing system. Its main limitations are:

  • The exact control-flow edges are not stored.
  • Blocks are matched greedily rather than globally.
  • The printed function prototype must match exactly.
  • IDA instruction identifiers are architecture-specific.
  • First and last instruction identifiers are compared as numeric values.
  • Calls made by the function are not part of the signature.
  • Constants, strings, imported functions, and instruction semantics are not considered.
  • Compiler inlining and outlining can still significantly change the function’s structure.

Despite these limitations, the signature contains considerably more structural information than a traditional byte pattern. Relative addresses, register selection, instruction encoding, and many small instruction-level changes do not directly affect it.

The design can also be extended gradually. Possible additions include explicit CFG edges, normalized instruction categories, call-graph information, referenced constants, string hashes, loop detection, dominator relationships, and optimal block matching. Each feature can be assigned its own weight so that no single unstable property completely determines the result.

Source Code

The source code for the plugin developed in this article is available here:

References