ropbot: Reimaging Code Reuse Attack Synthesis

ropbot: Reimaging Code Reuse Attack Synthesis

Speakers: Kyle Zeng

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=Pat-kFn3_pk

Overview

ropbot is a next-generation code reuse payload generation engine that fundamentally reimagines how ROP chains are constructed. By introducing the concept of a "rop block" -- a self-contained sequence of gadgets with guaranteed chainability -- ropbot replaces the traditional generate-and-test algorithm (O(n^n) worst case) with a graph-search approach that runs in effectively linear time. The result is a tool that outperforms all state-of-the-art ROP chain generators, achieves 100% success rate on full chain generation (dup2/execve payloads), works across multiple architectures (x86, ARM, and more), and has been adopted by Google as part of its kernel exploit development (XDK) framework for the kernel CTF vulnerability research program.

ropbot is the only tool that succeeded on all 10 security-sensitive binaries tested (Linux kernel, Firefox, Chromium, dnsmasq, etc.), achieved 2x better success rate and 6x speedup over the second-best tool on 200 binaries, and is open-sourced with all artifacts.

Background

▶ Watch: The real-world challenge of ROP chain generation beyond CTFs (0:00)

Return-oriented programming (ROP) and code reuse attacks are well-known exploitation techniques that chain together short code sequences ("gadgets") ending in control-flow transfer instructions to achieve arbitrary computation. While simple in CTF challenges (e.g., invoking execve("/bin/sh")), real-world exploitation requires complex payloads: connecting back to a server, downloading a second stage, mapping it into memory, and executing it -- across different program versions, builds, and architectures.

The field of automated ROP chain generation began in 2011 with the Q project and has seen numerous tools since. However, none have achieved practical adoption because they all rely on the generate-and-test algorithm: enumerate all combinations of gadgets up to a bound n, then use SMT solvers or symbolic execution to verify which combinations produce valid chains. This approach faces a fundamental dilemma: small n produces nothing useful, large n causes state explosion with O(n^n) worst-case complexity.

The core technical challenge is chainability: after one gadget finishes execution, it must correctly pass control flow to the next gadget. Traditional gadget finding algorithms scan backwards from ret/jmp/call instructions, but this approach provides no guarantee that any two gadgets can be chained together without additional intermediate gadgets. This uncertainty forces the generate-and-test approach, as there is no a priori way to know which gadget sequences will work.

Key Findings

▶ Watch: Key insight: guaranteed chainability eliminates generate-and-test (4:00)

Rop blocks guarantee chainability, eliminating generate-and-test. A self-contained gadget is defined as one with positive stack pointer change, taking its next PC from within that stack change, with no conditional branches. A rop block is a sequence of gadgets that is eventually self-contained. The key theorem: chaining two rop blocks always produces another rop block, meaning chainability is guaranteed at the rop block level.

Linear-time ROP chain generation via graph search. Register-to-register movement is solved by building a graph where nodes are registers and edges are rop blocks. Setting multiple registers becomes a graph search problem where the graph has O(2^k) nodes (k = number of registers, which is constant per architecture), making the search constant-time per query.

Architecture-agnostic gadget finding. Instead of scanning for architecture-specific instruction patterns, ropbot finds gadgets by looking for code sequences that move a symbolic value into PC from a fully symbolic state. This approach works on x86, ARM, and other architectures without modification, and finds gadgets that span multiple basic blocks or use conditional branches.

100% success rate on full chain generation. For dup2/execve payloads (common server exploitation payload), ropbot achieved 100% success rate with less time than competitors.

Adopted by Google for kernel CTF. ropbot is integrated into Google's kernel XDK framework -- anyone submitting an exploit to Google's kernel CTF vulnerability research program uses ropbot for ROP chain generation.

ARM works exceptionally well. Investigation revealed that ARM compilers inject special code sequences into every executable that can be abused for chain generation, giving ropbot abundant material on ARM binaries.

Technical Deep Dive

▶ Watch: Rop block chaining theorem: two rop blocks chain to another rop block (8:00)

Gadget finding operates at the semantic level rather than the syntactic level. In a fully symbolic state (all registers symbolic, stack content symbolic, memory regions symbolic), ropbot identifies code sequences that can potentially move a symbolic value into the program counter. This approach naturally handles ret (stack-to-PC), jmp reg (register-to-PC), conditional branches (by considering both paths), and sequences spanning multiple basic blocks. On ARM, it discovered that ldm PC (load-multiple including PC) gadgets should be considered valid gadgets but are not recognized by existing tools like ROPgadget or Ropper.

Self-contained gadgets are formally defined with three properties: (1) positive stack pointer change, (2) next PC sourced from within the stack pointer change range, (3) no conditional branches. Pop-register-ret sequences are self-contained by definition.

Normalization converts non-self-contained gadgets into rop blocks by prepending the necessary setup: conditional branch gadgets are normalized by first setting the branch guard to prevent unintended paths; call-memory gadgets (like ret2csu style) are normalized by first writing the target address to the memory location; jump/call-register gadgets are normalized by first setting the register.

Rop block chaining is performed statically (no symbolic execution needed): concatenate the two blocks' stack layouts, fix the stack offsets, and replace the first block's next-PC slot with the second block's address. The result is guaranteed to be another rop block.

Graph-based chain generation for register setting: build a graph where state (b1, b2, ..., bk) represents which of k target registers are controlled (0 or 1). An edge from state S1 to S2 exists if a rop block can set one additional register without clobbering already-set registers. Finding a path from all-zeros to all-ones gives a rop chain that sets all target registers.

Demo / Proof of Concept

▶ Watch: Graph-search for register setting: linear time chain generation (10:00)

10 security-sensitive binaries: ropbot was the only tool to succeed on all 10, including Linux kernel, Firefox, Chromium, and dnsmasq. All other tools failed on at least some binaries.

200 binaries with execve payload: ropbot achieved more than 2x better success rate than the second-best tool and 6x speedup.

Full chain generation (dup2/execve): 100% success rate with less time than all competitors -- this is the realistic server exploitation payload that represents real-world utility.

Cross-architecture: Validated on x86 and ARM, with ARM showing particularly strong results due to compiler-inserted code sequences.

Google adoption: Integrated into Google's kernel XDK framework for the kernel CTF program, representing real-world industry validation.

Stack pivoting: Confirmed in Q&A as supported, with post-paper improvements enabling push/pop style stack pivoting that performs "slightly better than humans" on some targets like the Linux kernel.

Defensive Implications

▶ Watch: Q&A: stack pivoting support and pwntools integration discussion (14:00)

ropbot's capabilities have significant implications for both offense and defense:

Exploit development automation advances. ropbot makes ROP chain generation practical, reliable, and fast across architectures. This lowers the barrier for exploit development, meaning defenders should assume that any memory corruption vulnerability with sufficient gadget availability is exploitable.

Security auditing and verification. ropbot can be used defensively to verify whether a given binary is exploitable via code reuse -- if ropbot can generate a chain, the binary needs additional hardening (CFI, shadow stacks, etc.).

Mitigation evaluation. The effectiveness of defenses like Control Flow Integrity (CFI), ASLR, and stack canaries can be evaluated against ropbot's chain generation capabilities to identify residual exploitability.

ARM deserves more attention. The finding that ARM compiler-inserted sequences provide abundant gadget material suggests that ARM-based systems may be more exploitable via ROP than previously appreciated, relevant for mobile and IoT security assessments.

Key Takeaways

• ropbot replaces generate-and-test (O(n^n)) with graph-search-based ROP chain generation in effectively linear time
• The "rop block" abstraction guarantees chainability between gadgets, enabling static chaining without symbolic execution
• Only tool to succeed on all 10 security-sensitive binaries (kernel, Firefox, Chromium); 100% success on full chain generation
• 2x better success rate and 6x speedup over the second-best tool across 200 binaries
• Architecture-agnostic: works on x86, ARM, and finds new gadget types missed by existing tools
• Adopted by Google as part of the kernel XDK framework for the kernel CTF program
• Open-sourced with all artifacts; supports stack pivoting and complex payloads

About the Speaker(s)

Kyle Zeng recently graduated from Arizona State University. His research focuses on automated exploitation, code reuse attacks, and binary analysis. The work was conducted in collaboration with multiple research institutes and has achieved industry adoption through Google's kernel exploit development framework.