TODO: have to update design flowcharts, will do as soon as possible today

GSoC 2026: Function Prologues Generation Plugin for Rizin

In context of Rizin, Prelude and Prologue are used interchangeably. Although Prologue is the more widely used term generally. Hence I have used Prologues terminology for the Plugin and the legacy naming of analysis system (analyze preludes) is kept as it is.

The Problem

A common problem in binary analysis is function detection. One method is searching for function prologues. Prologues are a sequence of instructions commonly found at the beginning of a function. These prologues perform tasks like setting up the stack, or initializing registers to values as defined in the architecture’s ABI. It is very common to hard-code these prologues patterns and match instructions against them. These patterns get outdated, are tedious to update, and have to be written for each architecture. Also because these signatures are generic, they are highly prone to false positives especially on x86/x86_64 binaries.

This project augments static signature based approach with a dynamic, multi-stage statistical heuristic pipeline. So that reverse engineers and researchers can extract function prologues signatures from a binary having symbol information and use them to analyse another stripped binary (does not have symbol information). This provides a good enough baseline for function detections particularly detecting functions not in normal control flow like an orphaned function

Solution: Design, Algorithm and Code

We weren’t going to the Machine Learning approach to this. Instead we want a fast statistics based approach to this.

This can be split into 2 categories:

1. The mathematical solution and algorithm
2. The system design of the plugin and utility

Mathematical formulation and solution Algorithm

Let, $S_{true}$ = Set of true, infinite distribution of all possible function prologues. Where each prelude is a sequence of bytes values (not using assembly instructions and instead using bytes as we need to support most architectures and can’t rely on disassembling). L is the length of the sequence.

Good Binaries = Binaries having symbol information

$S$ = A sample of the true distribution (the input we give to the algorithm; the good binaries giving the function prologues)

The structure of these prologues is such that many prologues share a common prefix or some portion while branching at some points (operand bits or register bits). So they represent a branching data structure (prefix tree).

The language we want in output: Signatures having two fundamental elements:

1. Exact bytes
2. Mask defining the wildcard bits

mask[i]=0 means dont care bit, which means the the ith bit in the bytes signatures is wildcard (accept 0 or 1 both)

Why generate masks? Why not just save every raw extracted prelude in the database as a static signature? Because $S$ is not the true population distribution; it is only a sample drawn from the population. It does not reflect the population (eg. operands and varying registers bits). We have to maximise our chance of finding unseen preludes too in the test binary.

On analysing a binary with prologues signatures we need:

• Recall ($R$) = Generalization. We want to be able to finding maximum number of function preludes that are not in $S$ but are in $S_{true}$. Which translates to wildcard at relevant and correct positions.
• FP = False positives (We want minimum false positives).

Wildcarding reduces improves Recall but penalizes on False Positives.

Inspired from the 2012 ML research paper ByteWeight, we are using weighted prefix tree (Trie) data structure to store raw prologues buffer as its the best possible data structure to store them for furthur generalization. As bits like register bits are never byte alligned, we cant use byte prefix tree, and have to use bit prefix tree.

Build raw Weighted Prefix Tree (Trie)

We take a fixed prologue length for all prologues = Number of bytes to extract from a function start. Let it be $L$.

Hence each function prologue is a bit sequence $S = (b_0, b_1, \dots, b_{m-1})$ of length $m = 8 \times L$,

We first feed all extracted raw prologues buffers from the binary into the bit prefix tree (each node is single bit). Essentially it becomes binary prefix tree. Each node keeps track of how many times the bit (at that specific prefix state) is hit for all prologues inserted in the trie. The root node of trie is empty/dummy.

If user just wanna use raw prologues extracted (without mask , essentially mask = 0xff…) we stop here and extract the prologues list. Else after all prologues are fed into the trie, we run the generalization algorithm over the trie.

Generalization

Generalization means to “generalise” the prelude pattern which both reduces the prelude database size and also captures the unseen by setting wildcards at correct and most appropriate positions in the prelude sequence.

We traverse the trie and use the hit_cnt of each node and child nodes to come to a conclusion whether to declare the node as wildcard OR exact bit. Wildcarding has an inherent problem of giving false positives if done incorrectly as it will allow any byte at that position. Thus we need a correct signal to decide whether the node is actually a wildcard or better to keep 2 distinct signatures (as the maximum childs of a node is 2). That decision is however to be made on the sample (good binaries in hand) instead of population. So we have to make the best decision with the data in hand. And hence it’s always better to have a larger number of functions (large binaries) for better results.

Do DFS traversal and at each node, if the node has 2 childrens, we calculate Shanon Entropy of the Split (EoS) for that node.

Let say we are at node $n$. It has two child nodes $c_1$ and $c_2$. The shanon entropy of split of node $n$:

where $p(c_i)$ is the probability of node $c_i$ occuring after node $n$.

where $F_i$ is the frequency (hit count) of the node $i$.

Shanon Entropy is good metric for uncertainity, high uncertainty means the bit is highly variable and can be wildcarded.

Let entropy Threshold be $E_c$. If the $EOS(node) > E_c$, we declare the bit at next depth (d+1) as wildcard (mask[d+1]=0) for the current branch of prologue, where d is the depth of node $n$.

Wildcarding the bit implictly means that we now need to merge the subtrees (merging same nodes recursively) at that node merge(src,dst). Because without merging the Entropy calculation for the node in levels below the current one will be wrong due to seperate hit_cnt. Hence after wildcarding decision we need to merge the the subtrees (adding the hit_cnt of the nodes being merged).

During the DFS traversal, upon reaching a terminal node (is_end), the active bit and mask buffers are exported as an RzPrologue pair.

The system design of the plugin and utility

This plugin is a core (RzCore) plugin as we need to have command suite in a normal interactive rizin session too. There are two modes for using the plugin:

1. Using commands in interactive rizin session
2. Using rz-prologues command line utility (binrz)

The cmdline utility is just a wrapper around the APIs provided by our RzCore plugin. The plugin code is coded as modular as possible with a relevant API surface for any power user needing fine grained control over the whole pipeline.

There are 3 modes of extracting prologues in rizin session.

• pg : generate prologues from current open binary in session.
• pga : generate prologoues from all the open binaries in the session.
• pgd : generate prologues using all the binaries from a directory (batch processing). Opens and closes one file at a time.

Earlier in the coding period I had designed the plugin with a Persistent state design where the prologue trie, prologues list, architecture info persisted in the rizin session using Plugin context. But this design made the plugin complex to use for a normal user. Because it required the user to run different commands to finally get the generalized prolouges. Starting from extracting and populating the prologues trie to running generalization command (pgg) and then running print command to print the generated prologues or export it (pgp). My initial thought for having this design was to give the user most fine grained control over whole pipeline. Like user could populate the trie by running pg on binaries one by one on which he wants to and at last run generalization or extract raw prologues without generalization from trie. This is actually complex for normal user (on top of that given the number of commands already in rizin). On top of that the user would need to keep two store design in mind at everytime (which actually should be internal implementation detail not to be bothered by end user).

However as suggested by mentors and discussion to make user facing part simple and follow KISS design philosophy (Keep it simple stupid), I shifted to a Ephemeral Design (one shot and few commands) by automating whole pipeline and removing persistency (for rizin session cmds).

Another friction currently is that in interactive rizin session, all the commands follow single word command structure. No command uses a flag like system which you can use for lets say a mode (commands do accept arguments but they are not for passing flags). So by rizin’s cmd design pattern, we need to have seperate command for a different mode, like for printing system we do not pass -j flag to command, we add j suffix to the parent command to indicate json mode printing instead of yaml. So having pgp -t for printing the trie would not be according to existing command design. I needed to have pgpt command for trie mode. So adding new feature unnecssarily increase the number of individual commands.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// old plugin context struct (that persist in rizin session until plugin is unloaded)
typedef struct core_prologues_generator_context_t {
    RzCmdDesc *cmd_desc;

	// generation workspace (reset by pgt-)
	RzTrie *pg_trie;
	RzSetS *fpaths; // names of files already processed to build the curr trie
	ut64 trie_prologue_len; // cfg: prologue length used for generation, may differ from the length of prologues in the store
	double entropy_threshold; // cfg: threshold for node split entropy used for generalization

	// prologues store (reset by pgp-)
	RzVector /*<RzPrologue>*/ *prologues; // has independent lifecycle then pg_trie
	ut64 store_prologue_len; // length of prologues in store

	RzProloguesArchInfo arch_info; // session metadata (set by first pg[a|d]/pgL and reset only by pg-)
} CorePGContext;

So I shifted to Ephemeral (short lived) design by removing all the persistant stores in the plugin context struct and then refactoring the command handlers to reflect the change. Now the lifetime of the trie, prologues vector, processed file store; is only till the runtime of the specific command. You run the command, plugin will extract, populate trie, generalise, and output the prolgoues list and everything is cleared after that. Nothing lives in memory after the command execution completes. You run the command and you get prologues, that’s it. I you want more control you use the binrz cmd line tool rz-prologues which supports passing flags for different modes and outputs; see: rz-prologues.

1
2
3
4
5
6

// new stripped down plugin context struct
typedef struct core_prologues_generator_context_t {
	RzCmdDesc *cmd_desc;
	ut64 prologue_len; // cfg: prologue length used for generation
	double entropy_threshold; // cfg: threshold for node split entropy used for generalization
} CorePGContext;

Now the rizin session provides only 3 commands for proglogues generation (though I have added additional commands in core analysis engine to support the use of generated prologues using this plugin; see below Prolougues Analysis).

The prologues are outputed in hex string format (byte hex string, mask hex string). In the mask 0 bit means wildcard (accept 0 or 1 both in the target position).

Some examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

❯ rizin test/bins/elf/riscv_crypto_64
[0x000104f0]> pg
arch: "riscv"
bits: 64
endian: "little"
prologue_length: 16
count: 5
prologues:
  - bytes: "4d65cd6713050502938707026386a700"
    mask: "f38b347cce1afaf5a91deb7811c08308"
  - bytes: "75bf797106f422f00018233ca4fc2338"
    mask: "ffffffffffffffffffffffffffffffff"
  - bytes: "797106f422f00018233ca4fc2338b4fc"
    mask: "ffffffffffffffffffffffff5ff0cffe"
  - bytes: "011106ec22e80010b7e7096a93877766"
    mask: "c79fffefffef7fef8d7f75226bb8abad"
  - bytes: "cd6703c7870201ef411106e4eff07ffb"
    mask: "9018b018901ae915baec6a1c150c0200"

rz-prologues

As you see there is more control over what you want to do and how in the cmd line tool compared to rizin session.

The tool is coded using the API surface made available by this plugin. The API functions are used by both rizin session cmds and Tool. The API is made avaible by rz_prologues.h and can be used by anyone who wants to make their own wrapper or if they want to have more fine grained control over the pipeline. The functions are defined in the same file as the rizin session plugin code.

The API surface:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// librz/core/p/prologues_generator.c

RZ_API void rz_prologues_arch_info_init(...<args>...);
RZ_API void rz_prologues_arch_info_fini(...<args>...);
RZ_API bool rz_prologues_arch_check(...<args>...);
RZ_API RZ_OWN RzTrie *rz_prologues_trie_new(void);
RZ_API bool rz_prologues_trie_feed_binfile(...<args>...);
RZ_API st64 rz_prologues_trie_feed_all_binfiles(...<args>...);
RZ_API st64 rz_prologues_trie_feed_directory(...<args>...);
RZ_API RZ_OWN RzVector /*<RzPrologue>*/ *rz_prologues_generalize_and_extract(...<args>...);
RZ_API RZ_OWN RzVector /*<RzPrologue>*/ *rz_prologues_extract_raw_from_trie(...<args>...);
RZ_API RZ_OWN RzStructuredData *rz_prologues_trie_to_structured_data(...<args>...);
RZ_API RZ_OWN RzStructuredData *rz_prologues_to_structured_data(...<args>...);

Somethings about code

• the code is written as modular as possible which also follows DRY (dont repeat yourself) only where neccessarry.
• its highly readable
• functions are grouped logically and easy to follow along

Prologues Analysis

As we have new way to generate the prologues dynamically, we need a supported core analysis command for that. Rizin had aap (analyze prelude) core analysis command for searching for prologues signatures in target binary, where the prologues were fetched from the architecture specific analysis plugin’s defined callback (kinda static database, directly written in code). Also we had a analysis.prelude config available to input a specific prologues byte pattern to search for instead of using the database.

The aap used rz_core_search_preludes API which searches for the patterns in the binary and makes a function on match. This API in turn used another API rz_core_search_prelude (note the singular name). The _preludes API called this _prelude API repeatedly over the mapped boundaries and inside the search range search.from - search.to. The _preludes API accepted only core object and a unused boolean flag bool log (may be was leftover trace while removing the old logging system earlier).

Using analysis.prelude config for searching for custom prelude is kinda unusual and only supports providing a fixed byte string to search for and no mask. Given that now we have new RzSearchBytesPattern having a structured way of representing search bytes pattern, and relevant robust APIs from librz/search/byte_search.c which supports parsing "bytes:mask" from input, it was better to use it and provide support for something like <prelude_search_cmd> "bytes:mask" for user instead of managing it via a config which is awkward.

So I removed the config and its fetching logic from rz_core_search_preludes API and changed its signature to accept a list of RzSearchKeywords (i.e, prologues).

1
2
3
4
5
6

// librz/core/cmd/cmd_search.c

// old
RZ_API int rz_core_search_preludes(RzCore *core, bool log) // log was unused
// new 
RZ_API int rz_core_search_preludes(RzCore *core, RZ_NULLABLE RzList /*<RzSearchKeyword *>*/ *prologues)

• If the prologues list is not passed -> use preludes defined in architecture’s analysis plugin
• If its passed use the list to search for patterns one-by-one (This I think can be optimised by batch processing instead of one-by-one)

With these I introduced 2 more prologues analysis command aapk <"bytes:mask"> and aapf <json file> that will use the updated _preludes API (aap remains the same).

RzSearchBytesPattern is actually private, so we can’t directly access the bytes and mask from the struct instance. The parsing API (which converts a string “bytes:mask” to RzSearchBytesPattern) returns RzSearchBytesPattern and not the (bytes, mask). So I added 2 getter APIs. We need the bytes and mask after parsing to form RzSearchKeyword which is used by rz_core_search_preludes(...).

1
2
3

// librz/search/bytes_search.c
RZ_API const ut8 *rz_search_bytes_pattern_get_bytes(RZ_NONNULL const RzSearchBytesPattern *bp);
RZ_API const ut8 *rz_search_bytes_pattern_get_mask(RZ_NONNULL const RzSearchBytesPattern *bp);

This completes the command handler for aapk.

For aapf <file>, the input is the path to the json file generated using the prologues generator. Only json file parsing is supported because we have a json parser in rizin and not other format. An interesting question arises, why rizin does not have the file/input to RzStructuredDatalayer, if it has the RzStructuredData to json/yaml layer (unified serialization)? Because parsing data is much harder than generating it, especially for loosely defined formats. So only json file loading is supported. You give file path to aapf and it loads prologues from it and searches for them in target binary and creates functions at hits.

Also with this we are migrating the “prelude” terminology everywhere in codebase to “prologue” terminology for consistency and removing unnecessary confusion.

RzTrie

Rizin didn’t have a prefix tree library until now. So I implemented a Generic and complete RzTrie library under rz_util as generic Utility lib, for prefix trees with all major APIs and almost 100% unit testing coverage.

The RzTrie is a non-intrusive tree data structure unlike RBTree which is intrusive. Means the tree structure wraps the data object, which is hence unaware of the tree. Whereas in an intrusive tree, the tree pointers are directly embedded inside your custom data object, forcing the object to become a part of the tree itself. The root node of the trie is empty and dummy generally but you can manipulate it for your usecase, thought generally not advised to do it if you ain’t aware if sideeffects, like empty keys and all. So it’s not advised to manipulate root node manually. The library however gives you full access to internals to code your any custom operation on the trie; like for my usecase in prologues generator, I coded the Merge subtree function (merge source tree to destination tree, and free source tree) by accessing the trie internals. Because this function is in general not needed as such and does not represent the main trie functions hence not include as part of trie library itself.

The library supports insertion of keys (automatically considered complete keys while inserting), and supports finding both partial and complete keys. Deletion is only allowed for complete keys. Several fine grained control is given using callback functions (signature defined by function pointers) like onhit cb for insertion, (pre, edge, post) cb visit in dfs.

The API surface:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// librz/include/rz_util/rz_trie.h

RZ_API RZ_OWN RzTrie *rz_trie_new(...<args>...);
RZ_API void rz_trie_clear(...<args>...);
RZ_API void rz_trie_free(...<args>...);
RZ_API RZ_BORROW RzTrieNode *rz_trie_insert(...<args>...);
RZ_API RZ_BORROW RzTrieNode *rz_trie_find_prefix(...<args>...);
RZ_API RZ_BORROW RzTrieNode *rz_trie_longest_prefix_match(...<args>...);
RZ_API bool rz_trie_contains(...<args>...);
RZ_API size_t rz_trie_size(...<args>...);
RZ_API bool rz_trie_delete(...<args>...);
RZ_API void rz_trie_dfs(...<args>...);

Now this library can be used for any prefix tree based usecase, by storing string, bit string, instructions, etc… you name it.

Future Consideration : Radix Tree would be better IMO, as it merges nodes with single children and makes trie memory optimised. This can be useful currently considering the bit trie where for some window of a branch the bit node have single children.

Code Testing

RzTrie

Plugin

Analysis

Benchmarking performance of prologues generator

[TODO]

Left to do

• Final Review process and future changes based on review.
• Set optimal default values for RZ_PROLOGUE_DEFAULT_LEN and RZ_PROLOGUE_DEFAULT_ENTROPY_THRESHOLD based on experiments.
• A testing benchmark to evaluate prologues generated

Future scope for plugin

• Based on how this plugin performs, explore other algorithms or heuristics if better than current one.
• There’s an idea of a probabilistic approach using the generated trie from good binaries, to analyse a target binary for function detection. By traversing root-to-leaf paths, the engine can compute a likelihood score or confidence metric for any memory offset, quantifying the probability that a given byte sequence represents a valid function entry point.
• Optimise code if possible
• Can add more APIs for Power users for more fine grained control over the whole pipeline and intermediate states.

Links to relevant work

• Prefix Tree (Trie) Library
• Prologues Generation Plugin
• Visualizer for exported Prefix tree # not a part of main work as such but just an extra touch from me (needs update for bit trie currently)

Challenges faced

Advice to future contributors

Thanks