Towards Sound Reassembly of Modern x86-64 Binaries

To secure a program you only have as a compiled binary, one clean approach is reassembly — turn the machine code back into editable assembly, add your protections, and reassemble — but it has never been fully reliable, because the tool must correctly decide which of the countless numbers in the code are actually memory addresses that need relabeling, and guessing wrong silently breaks the program; this work from KAIST notices that a modern CPU security feature, now on by default in Linux, conveniently marks every valid jump target in the binary, and pairs that with a deliberately over-inclusive control-flow map, to reassemble all 9,600 test binaries correctly with almost no slowdown.

The argument in one glance

Problem

Reassembly must correctly tell addresses from numbers, or it breaks the program

To harden a binary with no source, reassembly turns machine code into editable assembly, adds instrumentation, and assembles it back. But it must decide which numbers in the code are memory addresses needing symbolic labels versus plain literals — and one wrong guess silently corrupts the rewritten program.
What people did

Use relocation info and heuristics to symbolize

For position-independent executables, use the relocation metadata to distinguish addresses from numbers, and apply heuristics to recover the rest, such as guessing the boundaries of jump tables behind switch statements.
Why it fell short

Dynamic pointers and jump tables defeat the heuristics

Compilers collapse address expressions into single ambiguous numbers, so dynamically computed pointers are hard to identify, and jump-table boundaries are nearly impossible to pin down because adjacent data looks like valid entries. Heuristics get these wrong, so no tool is actually sound.
This paper's idea

Exploit CET markers and an over-inclusive CFG (SURI)

SURI leverages two insights: modern binaries with Control-flow Enforcement Technology (CET), now default in Linux, mark every valid indirect-branch target with a special instruction, which precisely identifies dynamically computed pointers; and a deliberately over-inclusive superset control-flow graph captures all possible branch targets, whose harmless bogus entries never execute. SURI soundly reassembled all 9,600 test binaries at about 0.2 percent overhead.

Why this problem is worth solving

A great deal of security work has to be done on programs whose source code is simply not available.

When you need to secure or modify a program you did not build — a commercial off-the-shelf application shipped only as a compiled binary — you have to work at the level of machine code, and binary rewriting is the technique for doing so. Static binary rewriting modifies the code before it runs, which makes it far faster than dynamic instrumentation that intercepts the program as it executes; this speed matters for defenses like control-flow integrity that must be always-on. Among static approaches, reassembly is especially clean: the tool disassembles the binary into relocatable assembly code — assembly where addresses are symbolic labels rather than fixed numbers — so that a user can effortlessly insert instrumentation or patches, and then assembles it back into a working binary. Because the result is an ordinary binary with no runtime support machinery (no table lookups, no detours to trampolines), reassembly achieves much better performance than other rewriting techniques. The catch is that turning fixed machine code back into relocatable assembly requires knowing, for every number in the code, whether it is an address that must become a movable label.

That one requirement — correctly identifying every address — is where reassembly has quietly remained unsolved, even on modern binaries.

Symbolization is the process of deciding which numeric values in a binary are memory references and turning them into symbolic labels. Given an instruction that pushes the value 0x12345678, a reassembler must decide whether that immediate is an address — in which case it must become a label so the code still works after instrumentation shifts things around — or just a literal number to leave alone. Get it wrong in either direction and the rewritten binary silently misbehaves. Position-independent executables help somewhat, because every absolute address carries relocation information the loader uses, which distinguishes addresses from plain numbers. But sound symbolization is still far from solved, for two reasons the paper highlights. First, compilers represent addresses with complex expressions — a program-counter-relative operand might conceptually be a label plus an offset — that collapse into a single opaque number after compilation, which could be misread as pointing to some entirely different code or data. Second, two categories are especially hard: pointers the program computes dynamically at runtime, and the complete set of indirect branch targets. The hardest of these are jump tables, the arrays of offsets that compilers emit for switch statements, whose exact boundaries are nearly impossible to determine because adjacent data often looks exactly like more valid table entries. Existing tools rely on heuristics for these and get them wrong, so despite claims of soundness, none is truly sound.

What people did before, and where it broke

Rewrite dynamically at runtime. Instrument the program as it executes, resolving addresses on the fly. Where it broke. Dynamic approaches carry significant runtime overhead, which is unacceptable for always-on defenses like control-flow integrity.
Reassemble using relocation info on position-independent executables. Use the relocation metadata to tell addresses from numbers and produce relocatable assembly. Where it broke. Relocation info does not resolve the compiler’s collapsed address expressions, dynamically computed pointers, or indirect branch targets, so symbolization is still incomplete.
Recover jump tables with heuristics. Guess the start and end of each jump table to symbolize its entries. Where it broke. Compilers often omit bounds checks, and data right after a table looks like valid entries, so heuristics misjudge the boundaries and introduce symbolization errors that corrupt the binary.
Claim soundness without achieving it. Prior reassemblers presented their tools as sound. Where it broke. As later work showed, they were not — the hard cases of dynamic pointers and indirect branches were handled by heuristics that fail on real binaries.
The gap. No reassembler reliably symbolized dynamically computed pointers and completely recovered indirect branches, so none was actually sound on modern binaries. Providing that, using CET and a superset control-flow graph, is what SURI does.

How SURI works

From heuristic symbolization to sound reassembly

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Let a security feature already in the binary reveal where the pointers go. SURI’s first insight turns a hardware defense into an analysis aid. Intel’s Control-flow Enforcement Technology, now enabled by default in major Linux distributions, includes indirect branch tracking: every legal target of an indirect jump or call must begin with a special marker instruction, endbr64, so the CPU can reject any indirect branch that lands elsewhere. That marker is exactly the signal a reassembler needs — it means a pointer that references an endbr64 is a genuine code target, while one that does not is something else — which lets SURI precisely symbolize the dynamically computed pointers that defeated prior heuristics. Recovering precise structure from a stripped binary by reading a reliable signal the toolchain left behind, rather than guessing, is the same move the accurate-disassembly work covered elsewhere on this site makes, extracting the true layout of complex machine code by leaning on dependable evidence in the binary instead of fragile pattern-matching that misfires on real programs.

Include every possibility, and make the extras harmless. SURI’s second insight sidesteps the impossible task of pinning down jump-table boundaries. Instead of guessing exactly which entries are real, it over-approximates: it builds a superset control-flow graph that includes all possible indirect branch targets, accepting that some are bogus. The trick is that these bogus targets do no harm — they only add unreachable code to the rewritten binary, code that will never execute, so the program’s behavior is unchanged even though the analysis was deliberately imprecise. Achieving soundness by over-approximating and then proving the over-approximation cannot change the program’s meaning is the same discipline the formally-verified rewriting work covered elsewhere on this site is built on, transforming low-level code in a way that is provably behavior-preserving rather than merely tested, so correctness comes from the structure of the method rather than from getting every guess exactly right.

Preserve the original so nothing computed at runtime can be misdirected. SURI reassembles by copying the code section for instrumentation while keeping the original sections at their original addresses, and it points every pointer in the copy back to those originals — relabeling only the pointers that reference an endbr64 target. This means a pointer the program computes at runtime, or a temporary composite address, still resolves to the value it always had, so instrumentation can be added to the copy without disturbing the delicate pointer arithmetic the original code depends on. Applying transformations on a working copy while leaving the source of truth untouched, so that all the original relationships remain valid, is the same design the runtime enforcement work covered elsewhere on this site follows, layering new checks onto a program’s execution without altering the underlying data and control relationships the program was built to rely on.

Following a binary through SURI

Reassembling a CET-enabled x86-64 binary soundly

A trace of SURI reassembling a modern binary, following the paper's CET and superset-CFG design.

Step 1 of 5

Start from a stripped, CET-enabled binary

The input is a modern x86-64 position-independent executable with Control-flow Enforcement Technology enabled — the default on major Linux distributions — but no source code and no reliable markings for which numbers are addresses.

CET means every valid indirect target starts with an endbr64.

Why it works

CET markers are a ground-truth signal for code targets. Because every valid indirect-branch target in a CET binary begins with an endbr64 → a pointer referencing one is definitely a code target and others are not → so dynamically computed pointers are symbolized precisely instead of heuristically.
Over-approximation cannot miss a real target. Because the superset control-flow graph includes all possible indirect targets → no genuine branch destination is ever left unsymbolized → so the reassembled binary preserves every real control-flow edge.
Bogus targets are provably harmless. Because the extra targets only introduce unreachable code that never executes → the over-approximation cannot change the program’s behavior → so soundness holds despite the analysis being deliberately imprecise.
Preserving originals protects runtime-computed pointers. Because the original sections stay at their original addresses and copy pointers reference them → a pointer the program computes at runtime still resolves correctly → so instrumentation on the copy never corrupts the original pointer arithmetic.
CET being default makes the approach broadly usable. Because major Linux distributions now ship CET-enabled binaries by default → the endbr64 signal is present in the binaries people actually need to rewrite → so the technique applies to real-world software, not a niche.

What it costs (trade-offs and scope)

It depends on CET being enabled. SURI’s precise pointer symbolization relies on the endbr64 markers that Control-flow Enforcement Technology inserts. Binaries compiled without CET lack this signal, so the key insight does not apply to them, even though CET is increasingly the default.
It targets x86-64 position-independent executables. The study focuses on modern x86-64 PIE binaries on Linux. Other architectures, non-PIE binaries, or platforms without the same relocation and CET conventions would need different treatment.
The superset adds unreachable code. Over-approximating indirect targets grows the rewritten binary with code that never runs. This is harmless to correctness and the reported runtime overhead is tiny (about 0.2 percent on average), but the binary is somewhat larger than a perfectly-precise rewrite would be.
Soundness is engineered, not a universal proof. SURI is designed and demonstrated to be sound on the largest benchmark to date (9,600 binaries), and its arguments for why bogus targets are harmless are principled, but this is systems-level soundness on real binaries rather than a machine-checked formal proof of the whole pipeline.
It is about enabling instrumentation, not the instrumentation itself. SURI produces sound, relocatable, instrumentable assembly; the actual security benefit depends on what defense the user adds. It is the reliable foundation, not a specific hardening policy.
Corner cases of real toolchains remain demanding. Sound reassembly requires handling the many ways compilers encode addresses; SURI categorizes and addresses these systematically, but the approach is tied to the behaviors of current compilers, and unusual code generation could still pose challenges.

The evaluation

Approaches to rewriting a binary you have no source for

Property	Dynamic instrumentation	Heuristic reassembly
When it modifies the code		Before execution (static)
Runtime overhead
Symbolizes dynamic pointers
Recovers indirect branches / jump tables	At runtime
Soundness on real binaries	Correct but slow

Approaches to rewriting a binary without source, as compared in the paper. Dynamic instrumentation resolves everything at runtime and is correct but carries significant overhead, unacceptable for always-on defenses. Static reassembly is fast because the result needs no runtime support, but it hinges on symbolization — correctly turning address-valued numbers into relocatable labels — and prior reassemblers rely on heuristics that fail on the hard cases: dynamically computed pointers and the exact boundaries of jump tables, where adjacent data mimics valid entries. Despite claims of soundness, those tools are not actually sound. SURI achieves sound reassembly of modern CET-enabled x86-64 position-independent executables with two insights: it uses the endbr64 markers that Control-flow Enforcement Technology (now default on major Linux distributions) places at every valid indirect-branch target to precisely identify dynamically computed pointers, symbolizing a pointer as a code reference exactly when it targets such a marker while keeping the original sections in place for everything else; and it builds a superset control-flow graph that over-approximates indirect branch targets so no real target is missed, with the extra bogus targets only introducing unreachable code that never executes and so cannot affect correctness. Evaluated on the largest reassembly benchmark to date, 9,600 real-world binaries, SURI soundly reassembles all of them, and the rewritten binaries run at about 0.2 percent overhead versus the originals; the framework is open-sourced.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

SURI is a sharp, practical advance on a problem that had resisted a clean solution for years. The setting is important: securing software you have only as a binary — commercial applications without source — requires rewriting machine code, and the fast, always-on way to do that is static reassembly, which turns the binary into relocatable assembly you can instrument and reassemble. The perennial obstacle is symbolization: deciding which of the countless numbers in the code are actually memory addresses that must become movable labels, where a single wrong decision silently breaks the program. Even on position-independent executables, where relocation info helps, two things stayed hard — pointers the program computes at runtime, and the full set of indirect branch targets, especially jump tables whose boundaries blur into adjacent data — and prior tools papered over these with heuristics while claiming a soundness they did not have. SURI’s two insights are elegant and complementary. First, it repurposes a hardware security feature, Intel’s Control-flow Enforcement Technology, now default in Linux, whose endbr64 markers reliably flag every valid indirect-branch target, giving a ground-truth signal that precisely symbolizes dynamically computed pointers. Second, it embraces over-approximation, building a superset control-flow graph that includes all possible targets, and shows the extra bogus ones are harmless because they only add code that never runs. Together, and combined with the trick of keeping the original sections in place so runtime-computed pointers stay valid, this let SURI soundly reassemble all 9,600 binaries in the largest benchmark to date, at about 0.2 percent overhead, with the tool open-sourced. Read the scope carefully. The precision insight depends on CET being enabled, which is increasingly but not universally true; the work targets x86-64 PIE binaries on Linux; the superset makes the binary somewhat larger with unreachable code; and this is engineered, benchmark-demonstrated soundness on real binaries rather than a machine-checked formal proof. The durable idea is that a problem that looks like it demands perfect precision can sometimes be solved instead by finding a reliable external signal to anchor the hard decisions and by over-approximating the rest in a way that provably cannot cause harm.

Background

Why rewriting binaries without source keeps mattering

It helps to see SURI within the long-running effort to analyze and secure software that exists only as compiled binaries, a need that never goes away because so much deployed code — commercial, legacy, embedded, or third-party — ships without source. Every technique in this space wrestles with the same fundamental loss: compilation discards the structure that made the program intelligible, and tools must painstakingly recover enough of it to reason about or transform the code safely. The binary security-hardening work covered elsewhere on this site reflects the same mission from the deployment side, retrofitting protections onto binaries whose authors are unavailable, which is exactly the situation reassembly is meant to serve. The common thread is that the security and reliability of a vast installed base depends on being able to inspect and modify machine code faithfully, and the persistent difficulty is doing so soundly — without silently altering behavior — when the original intent has been compiled away. SURI advances this by showing that modern binaries are not just harder targets but also richer ones: the very hardware defenses being added to them, like Control-flow Enforcement Technology, leave behind structure that a rewriter can exploit. As such features become universal, the pattern SURI exemplifies — turning the artifacts of new security mechanisms into leverage for sound binary analysis — is likely to make faithful rewriting of stripped binaries steadily more tractable.

If you remember only three things

1. Securing software you have only as a compiled binary — commercial code with no source — requires binary rewriting, and static reassembly is the fast, always-on approach: disassemble the binary into relocatable assembly (addresses as movable symbolic labels), let the user add instrumentation like control-flow integrity, then assemble it back, with none of the runtime overhead of dynamic instrumentation. The hard, long-unsolved problem is symbolization: deciding which numeric values in the code are memory addresses that must become labels versus plain literals, where one wrong decision silently breaks the program. Even for position-independent executables, whose relocation info distinguishes addresses from numbers, soundness stayed out of reach because compilers collapse complex address expressions into single ambiguous numbers, and because two things are especially hard to recover: dynamically computed pointers, and the complete set of indirect branch targets — above all jump tables (from switch statements), whose exact boundaries blur into adjacent data that looks like valid entries. Prior tools used heuristics that fail on these and claimed a soundness they did not have.
2. SURI achieves sound reassembly of modern CET-enabled x86-64 PIE binaries with two complementary insights. First, it exploits Intel Control-flow Enforcement Technology (now default on major Linux distributions), whose indirect branch tracking requires every valid indirect-branch target to begin with a special endbr64 marker instruction. That marker is a ground-truth signal: a pointer is a genuine code target exactly when it references an endbr64, which precisely symbolizes the dynamically computed pointers that defeated heuristics. SURI copies the code for instrumentation but keeps the original sections at their original addresses, relabeling only pointers that reference an endbr64, so runtime-computed and temporary pointers still resolve correctly. Second, instead of guessing jump-table boundaries, SURI over-approximates: it builds a superset control-flow graph including all possible indirect branch targets, so no real target is missed. The extra bogus targets only add unreachable code that never executes, so the over-approximation provably cannot change the program's behavior — soundness by construction despite deliberate imprecision.
3. Evaluated on the largest reassembly benchmark to date — 9,600 real-world binaries — SURI soundly reassembles all of them, and the rewritten binaries run at about 0.2 percent overhead versus the originals; the framework is open-sourced. Scope: the precise-symbolization insight depends on CET being enabled (increasingly but not universally the default); the work targets x86-64 PIE binaries on Linux; the superset makes the binary somewhat larger with unreachable code; and this is engineered, benchmark-demonstrated soundness on real binaries rather than a machine-checked formal proof of the whole pipeline. SURI provides the reliable relocatable-assembly foundation; the security benefit depends on the instrumentation the user adds. The durable lesson is that a problem seeming to demand perfect precision can instead be solved by anchoring the hard decisions to a reliable external signal (here, CET markers) and over-approximating the rest in a way that provably cannot cause harm.

Check yourself

Check your understanding

1. What is symbolization, and why does it make sound reassembly hard?
2. How does SURI use Control-flow Enforcement Technology (CET) to symbolize pointers precisely?
3. What is a superset control-flow graph, and why does using it keep SURI sound?
4. What did SURI achieve, and what are the limits of the result?

Sources

The paper is “Towards Sound Reassembly of Modern x86-64 Binaries” by Hyungseok Kim, Soomin Kim, and Sang Kil Cha, published at ASPLOS 2025, DOI 10.1145/3676641.3716026. The authors are affiliated with the Affiliated Institute of ETRI and KAIST, and the tool is named SURI (Superset CFG-based Reliable Instrumentation).

This explainer is based on the full text of the paper, obtained from the authors’ open-access copy (the CC-BY version) hosted on Sang Kil Cha’s KAIST page. The problem framing (binary rewriting for hardening commercial off-the-shelf software without source; static reassembly turning machine code into relocatable assembly for low-overhead instrumentation; symbolization as the core difficulty of deciding which numbers are addresses; why position-independent executables help but do not make symbolization sound; the compiler’s collapsed address expressions; and the two remaining hard challenges of dynamically computed pointers and complete indirect-branch recovery, especially jump-table boundaries that blur into adjacent data), the SURI design (the insight that Control-flow Enforcement Technology, now default on major Linux distributions, marks every valid indirect-branch target with an endbr64 instruction that precisely identifies code pointers; the pointer repairer that copies the code while preserving the original sections at their addresses and relabels only pointers referencing an endbr64; and the superset control-flow graph that over-approximates all possible indirect branch targets, whose bogus entries only add never-executed unreachable code and so preserve correctness, with a method to soundly symbolize jump-table entries), and the results (sound reassembly of all 9,600 real-world binaries in the largest reassembly benchmark to date, about 0.2 percent average runtime overhead, and an open-source release) are all drawn directly from the paper. Background explanations of binary rewriting, disassembly, symbolization, position-independent executables, jump tables, and Intel CET are standard and provided to make the paper’s contribution understandable.