Gadget Chains as a Programming Language, and What CFI Restricts

Return-oriented programming begins from an observation about instruction decoding on a variable-length instruction set. x86 instructions range from one byte to fifteen, and the decoder has no alignment requirement, so any byte offset in an executable page is a valid place to begin decoding. A sequence of bytes that a compiler emitted as one instruction can be decoded as several different instructions starting mid-instruction, and some of those decodings end in a ret. The executable’s text is therefore not a collection of functions but a dense space of short programs, most of which no compiler intended.

Finding and classifying sequences

A gadget is a short instruction sequence ending in ret, an indirect jmp, or an indirect call. The distinction matters because ret consumes a stack slot and indirect branches consume a register or memory operand, so chains built from each require different setup. ret-terminated gadgets are the standard because the stack is already the thing the attacker controls.

A gadget that performs a useful operation usually has a side effect. pop rdi; ret is clean; mov [rdi], rsi; ret is a write primitive but clobbers nothing else; add rsp, 8; ret adjusts the chain’s own cursor; xchg eax, esp; ret pivots the stack. The classifier that matters for chain construction is not what the gadget does but what it requires and what it destroys. A gadget that dereferences rcx is only usable if the chain can set rcx first, and a gadget that leaves a register in an unknown state forces the chain to restore it before the next gadget depends on it.

Discovery is mechanical: scan the executable sections for the byte 0xc3 (ret on x86), decode backwards to find instruction boundaries that end there, and filter for sequences without privileged instructions, memory accesses that would fault, or calls into the PLT. The search is quadratic in the size of the text if done naively and linear with a decoder that walks every offset once. Real binaries of a few hundred kilobytes yield thousands of gadgets; a full libc yields tens of thousands.

Why the set is computationally complete

The completeness argument does not require that any single gadget be expressive. It requires a small set of primitives that can be composed. Loading a constant into a register, moving a value between registers, loading from and storing to an address held in a register, arithmetic, and a conditional branch are enough to implement a universal machine, and each of those exists in a large library.

Memory access is the usual obstacle, because most gadgets that load or store do so through a register that also has to be loaded, and the loading gadget may be different from the storing one. The pop gadgets solve this for the argument registers; a gadget like mov rax, [rax]; ret gives a load through a chosen pointer, and a matching store gives the write. Once a chain can read and write arbitrary memory, it can implement a loop by keeping a counter in memory and comparing it, and the loop makes the chain a general interpreter for a bytecode encoded in the stack.

The practical form is not a Turing machine but a staged loader. A short chain calls read or mprotect to make a region writable and executable, or writes a small interpreter into a known buffer and jumps to it. That returns the attacker to the shellcode model that NX was designed to prevent, with the chain as the bootstrap. The defence that removes the bootstrap therefore has more value than the defence that removes any individual gadget.

The stack as program counter

A chain’s control flow is the sequence of stack slots. Each ret advances the cursor by eight bytes, so the stack pointer is the program counter and the stack contents are the instruction stream. This is why pivoting is the natural companion technique: a pivot sets rsp to a buffer the attacker filled, and the chain runs from there regardless of how small the original overflow was.

The pivot needs one gadget that loads rsp from a controlled register or memory location. xchg rsp, rax; ret, mov rsp, rbp; pop rbp; ret, and leave; ret all serve, and which is available depends on the binary. A pivot into the heap is common because the overflow may be a heap overflow and the heap buffer is large enough to hold the chain.

Once pivoted, the chain’s length is bounded by the buffer it lives in, not by the original overflow. A 200-byte overflow can start a chain that runs for kilobytes if the pivot lands in a larger region. That asymmetry — a small write gaining a large execution budget — is what makes pivoting worth the extra gadget.

rsp -> [pop rdi; ret]        ; gadget 1: load the first argument
       [address of string]   ; consumed by gadget 1
       [pop rsi; ret]        ; gadget 2
       [length]              ; consumed by gadget 2
       [mov [rdi], rsi; ret] ; gadget 3: the write itself
       [pop rdi; ret]        ; gadget 4: next operation begins
       ...

Reading the listing as data rather than as code is the point: every line is eight bytes on the stack, and the alternation between gadget addresses and argument values is determined entirely by how many slots each gadget consumes.

What control-flow integrity actually constrains

CFI is a family of mechanisms that check indirect branches against a computed set of legitimate targets. The granularity of that set determines both the strength and the cost.

Coarse-grained CFI groups targets by function signature or by instruction type. Every address that could legitimately be the target of an indirect call is placed in a set, and the check verifies that the actual target is in the set. Because many functions share a signature, the set is large, and an attacker who can redirect a call to any function with the same argument types passes the check. Coarse CFI removes the ability to jump into the middle of a function, which kills most ret-into-gadget chains, but it does not remove the ability to call the wrong function.

Fine-grained CFI computes a per-callsite target set, so a specific indirect call may only reach the functions that the program’s own analysis showed it could reach. The set is usually a single target for a devirtualised call, which makes the check close to a comparison. The cost is the analysis: computing the sets requires whole-program points-to analysis, which is imprecise for C and C++ and produces larger sets than the source suggests. Virtual dispatch, function pointers in structures, and callbacks through libraries all widen the set.

Shadow stacks are the back-edge half of the problem. A ret is an indirect branch, and the legitimate target set for it is exactly one address: the instruction after the matching call. Rather than compute that set statically, a shadow stack records it at runtime in a second stack that ordinary writes cannot reach. The check on ret compares the two, and a mismatch faults. This is a stronger guarantee than any static analysis for returns, and it costs one extra memory write per call and one extra read per return.

The forward edge — indirect calls and jumps — has no equivalent runtime record, because the target is not determined until the instruction executes. It has to be checked statically or with a label-based scheme where each function’s entry carries a type identifier and the call site checks it. The two halves are usually deployed together, and the hardware support for each is a different mechanism.

The cost of checking, and the gap it leaves

Every check is a branch on a path that executes constantly. A shadow stack check on every ret adds a load, a compare, and a conditional branch to every function return, and returns are among the most frequent instructions in real programs. The instruction cost is small in isolation and significant in aggregate, which is why the mechanism is implemented in hardware rather than as a compiler transformation: the silicon can do the compare in parallel with the return address fetch and fault only on mismatch.

Static CFI has a different cost profile. The label checks add instructions at indirect call sites only, which are far rarer than returns, so the runtime overhead is low. The build-time cost is the analysis, and the compatibility cost is that hand-written assembly, JIT output, and code loaded at runtime must cooperate with the labelling scheme or be excluded from it.

The gap that remains is data. CFI constrains control flow, and an attack that does not need to redirect control flow is unaffected. A format string that writes a length field, a heap overflow that corrupts a pointer used as a destination, or a logic bug that grants access without any corrupted address all proceed. CFI raises the cost of the control-flow step and leaves the data-only step untouched, which is why the techniques in the format string and heap articles remain relevant against a target with full control-flow protection.

There is also the question of what “legitimate target set” means for a program that loads code at runtime. A JIT compiler’s output has no static call graph, so a CFI scheme that relies on one must either exclude the JIT region or instrument the compiler to emit labels. Both are compromises, and both have been used as the entry point for attacks that a purely static scheme would have blocked.