PaperlayerView exact revision on arXiv

Source-linked AI summary

Block Oriented Programming: Automating Data-Only Attacks

Kyriakos Ispoglou, Bader AlBassam, Trent Jaeger, Mathias Payer

arXiv:1805.04767v2cs.CR

TL;DR

CFI and shadow stacks make control-flow hijacking harder, but assessing the remaining attack surface, including data-only attacks, remains an open problem. BOPC compiles SPL payloads into CFG-compliant traces using basic blocks and search heuristics. It mapped payloads across 10 programs successfully in 81% of cases, with limitations including basic-block granularity.

  • Problem

    Assessing whether attackers can execute useful behavior under CFI and shadow stacks remains open, while CFI cannot stop attacks that manipulate program data.

    Source: §1 · p. 1, §2.3 · p. 3

  • Method

    BOPC maps high-level SPL payloads to functional basic blocks and connects them with dispatcher blocks along valid program paths, using pruning and heuristics to search.

    Source: §1 · p. 2, §4 · p. 3, §9 · p. 12

  • Results

    81% of the time across 10 programs, BOPC successfully mapped the majority of 13 payloads, including loops and conditionals.

    Source: §9 · p. 12

  • Takeaways & Limitations

    BOPC offers defenders a way to assess a program’s residual attack surface and test whether a bug can enable a practical code-reuse attack.

    Source: §1 · p. 2

    BOPC’s basic-block granularity can miss desired SPL behavior that would arise only from combining multiple blocks.

    Source: §8 · p. 12

Abstract

from arXiv · show

With the widespread deployment of Control-Flow Integrity (CFI), control-flow hijacking attacks, and consequently code reuse attacks, are significantly more difficult. CFI limits control flow to well-known locations, severely restricting arbitrary code execution. Assessing the remaining attack surface of an application under advanced control-flow hijack defenses such as CFI and shadow stacks remains an open problem. We introduce BOPC, a mechanism to automatically assess whether an attacker can execute arbitrary code on a binary hardened with CFI/shadow stack defenses. BOPC computes exploits for a target program from payload specifications written in a Turing-complete, high-level language called SPL that abstracts away architecture and program-specific details. SPL payloads are compiled into a program trace that executes the desired behavior on top of the target binary. The input for BOPC is an SPL payload, a starting point (e.g., from a fuzzer crash) and an arbitrary memory write primitive that allows application state corruption. To map SPL payloads to a program trace, BOPC introduces Block Oriented Programming (BOP), a new code reuse technique that utilizes entire basic blocks as gadgets along valid execution paths in the program, i.e., without violating CFI or shadow stack policies. We find that the problem of mapping payloads to program traces is NP-hard, so BOPC first reduces the search space by pruning infeasible paths and then uses heuristics to guide the search to probable paths. BOPC encodes the BOP payload as a set of memory writes. We execute 13 SPL payloads applied to 10 popular applications. BOPC successfully finds payloads and complex execution traces -- which would likely not have been found through manual analysis -- while following the target's Control-Flow Graph under an ideal CFI policy in 81% of the cases.

1 INTRODUCTION

CFI and shadow stacks constrain control-flow hijacking, but attackers retain choices among permitted targets and can manipulate conditional branches. BOPC automates assessment by compiling high-level SPL payloads into execution traces through the target program.

1 INTRODUCTION

  • CFI derives allowed indirect-control targets from an over-approximated CFG, and runtime checks reject targets outside each dispatch location’s allowed set.Modern CFI mechanisms are deployed in Google Chrome, Windows 10, and Edge.Source: §1 · p. 1
  • CFI leaves attackers choices among permitted indirect-call targets and conditional branches, making CFG-valid exploit construction highly program-dependent and predominantly manual.Finding a path that achieves exploit goals is more complex than locating gadgets.Source: §1 · p. 1
  • BOPC uses Turing-complete SPL to specify attacker behavior and returns a trace encoded as memory writes from a supplied starting point.The starting point may come from fuzzing or manual analysis; BOPC is also envisioned as a tool for defenders assessing residual attack surface.Source: §1 · pp. 1–2
  • BOP maps SPL statements to functional basic blocks and connects them through dispatcher blocks, using pruning and proximity-based ranking to guide its NP-hard search.The proximity ranking prioritizes likely dispatcher gadgets after pruning the candidate functional blocks.Source: §1 · p. 2
  • 81% of the cases across 10 target programs produced traces for 13 SPL exploit payloads, including code-reuse attacks.The payloads included both practical exploit behavior and SPL loops and conditionals.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

The background traces code-reuse techniques and automated exploit tools, then explains why CFI, shadow stacks, and data-only attacks shape the problem BOPC addresses.

2 BACKGROUND AND RELATED WORK

  • Code reuse progressed from return-to-libc to Turing-complete ROP and variants using arbitrary indirect transfers.ROP chains small return-terminated gadgets by arranging state on the stack.Source: §2 · p. 2
  • Automated ROP tools search for predefined gadget forms and can leave chaining to researchers, while AEG assumes no defenses and generates buffer-overflow shellcode exploits.When expected gadgets or more complex chains are missing, the tools may degenerate into gadget-dump tools.Source: §2 · p. 2

2.1 Control Flow Integrity

  • CFI checks indirect targets against an over-approximated CFG, but complex CFG-compliant code-reuse attacks remain manually constructed.Newton exposes reachable indirect pointers and their allowed targets but cannot stitch gadgets into an attack.Source: §2.1 · pp. 2–3

2.2 Shadow Stacks

  • Shadow stacks protect backward edges by comparing return addresses on regular and protected stacks, complementing CFI’s protection of forward edges.The shadow stack is assumed to reside in protected memory.Source: §2.2 · p. 3

2.3 Data-only Attacks

  • Data-only attacks manipulate program data rather than control flow, which CFI cannot stop; controlling execve() arguments can suffice for arbitrary command execution.Data Oriented Programming (DOP) generalizes data-only attacks, whose sensitive-variable selection has relied on analysts.Source: §2.3 · p. 3
  • BOPC automatically generates high-level-language payloads that follow the program CFG but not its Data Flow Graph.Practical Data Flow Integrity defenses are not known to the authors, who cite prohibitively high data-flow tracking overhead.Source: §2.3 · p. 3

3 ASSUMPTIONS AND THREAT MODEL

BOPC assumes a hardened binary with a known memory-corruption vulnerability and an attacker able to modify memory state. Its payload execution begins from a naturally reached entry point after that state modification.

3 ASSUMPTIONS AND THREAT MODEL

  • The target is a vulnerable binary hardened with CFI or a shadow stack, as well as DEP, ASLR, and stack canaries.The threat model focuses on strong control-flow-hijack mitigations.Source: §3 · p. 3
  • An Arbitrary memory Write Primitive (AWP) can write any value to any writable address; an Arbitrary memory Read Primitive (ARP) is optional and needed to bypass probabilistic defenses.The ARP models access to an information leak.Source: §3 · p. 3
  • BOPC assumes the program naturally reaches an entry point after memory operations, without requiring code-pointer corruption to reach it.Finding that entry point is considered part of vulnerability discovery and orthogonal to BOPC.Source: §3 · p. 3
  • AWP or ARP operations may modify state multiple times, after which the SPL payload executes without further use of those primitives.This separates state modification from payload execution; the paper describes the assumptions as practical and consistent with control-flow-hijack threat models.Source: §3 · p. 3

4 DESIGN

BOPC maps high-level SPL payloads onto basic blocks and connects them along valid program paths to produce a payload from an arbitrary write. Its design combines block summaries, path search, and concolic execution to handle constraints that make block selection NP-hard.

4 DESIGN

  • BOP chains use whole basic blocks along valid CFG paths, with functional blocks implementing SPL statements and dispatcher blocks connecting them without clobbering prior state.Block Constraint Summaries capture block effects and help identify when a dispatcher would clobber the SPL state.Source: §4 · pp. 3–4, Figure 2 · p. 4

4.1 Expressing Payloads

  • SPL is a Turing-complete, architecture-independent C dialect whose virtual registers and OS API express payload behavior independently of the target binary.Payloads run as side effects of the target binary’s state, rather than as code executed directly on the CPU.Source: §4.1 · p. 4

4.2 Selecting functional blocks

  • Block Constraint Summaries let BOPC match machine-code blocks to SPL statements by representing their possible effects on registers, memory, control flow, and external operations.A block matches a statement when its constraints contain the operations required by that statement.Source: §4.2 · pp. 4–5

4.3 Finding BOP gadgets

  • Selecting functional blocks and dispatcher paths is NP-hard because earlier gadget choices can make later paths infeasible.BOPC uses proximity-based heuristics and a delta graph to prioritize likely candidates and eliminate paths that cannot connect blocks.Source: §4.3 · p. 5

4.4 Searching for dispatcher blocks

  • The delta graph ranks functional-block connections by path length, while context-sensitive shortest-path search accounts for runtime call targets and avoids clobbering blocks.Shorter paths are treated as more likely to yield satisfiable constraints, and paths that cannot legally connect blocks can be eliminated early.Source: §4.4 · pp. 5–6

4.5 Stitching BOP gadgets

  • BOPC incrementally tests dispatcher paths with concolic execution, clones state at conditional statements, and turns satisfying constraints into memory writes.If a candidate chain fails, it tries another functional-block selection; the resulting memory layout is initialized through the arbitrary write primitive.Source: §4.5 · p. 6

5 IMPLEMENTATION

BOPC lifts binaries into a basic-block constraint CFG and SPL payloads into an intermediate representation, then searches for block mappings and paths that realize each statement. Its iterative pipeline selects functional blocks, finds non-clobbering dispatchers, and solves constraints to encode a trace as memory writes.

5 IMPLEMENTATION

  • BOPC takes an SPL payload, vulnerable application, and reachable entry point, then outputs memory-write tuples and optionally controlled stream inputs.The entry point is expected after arbitrary writes have been completed.Source: §5 · p. 6

5.1 Binary Frontend

  • The Binary Frontend uses symbolic execution to summarize each basic block’s register, memory, call, and branch effects, adding these abstractions to the CFG.The resulting CFG with abstractions is CFGA.Source: §5.1 · p. 6

5.2 SPL Frontend

  • Independent SPL statements can be reordered into semantically equivalent payload permutations, and BOPC searches for a solution among them.The frontend groups independent statements using a dependence graph and customized topological sorting.Source: §5.2 · pp. 6–7

5.3 Locating candidate block sets

  • BOPC matches SPL statements to basic blocks by their summarized effects, then creates register, variable, and dereferenced-address mapping structures.Assignments, unconditional jumps, and returns do not require candidate blocks; a statement with no candidates halts synthesis.Source: §5.3 · p. 7

5.4 Identifying functional block sets

  • For each candidate block, BOPC tests whether register and memory mappings satisfy its constraints, using maximum bipartite matchings to identify usable functional blocks.It enumerates alternative maximum matches when the mapping is not unique.Source: §5.4 · p. 7

5.5 Selecting functional blocks

  • BOPC selects one functional block per payload statement and searches minimum-weight induced subgraphs, trying bounded payload permutations when needed.Each permutation requires recalculating the payload adjacency matrix.Source: §5.5 · pp. 7–8

5.6 Discovering dispatcher blocks

  • The delta graph represents minimum non-clobbering paths between functional blocks; concolic execution tests the K shortest dispatcher paths in order.The implementation reports that this proximity heuristic works well in practice even for small K, such as 8.Source: §5.6 · p. 8
  • During simulation, BOPC initializes mapped variables, branches symbolic state at conditionals, and checks that constraints remain satisfiable across paths.It concretizes symbolic memory values inline before they are overwritten, adding those values to the memory-write set.Source: §5.6 · p. 8, §5.7 · p. 9

6 EVALUATION

Across 10 applications and 13 SPL payloads, BOPC finds traces for most tested cases while following the target CFG. Success depends on the tested payloads and applications, and some failures reflect search limits or the inability to establish truly infinite execution.

6 EVALUATION

  • 105 of 130 cases (approximately 81%) yielded memory-write mappings that execute the payload while following the CFG without violating strict CFI or stack integrity.The evaluation uses 13 representative SPL payloads across 10 applications.Source: §6 · p. 9
  • Large-CFG applications have higher success rates, while infinite-loop payloads may terminate through segmentation faults when modified loop conditions drive out-of-bounds accesses.BOPC verifies a truly infinite loop only in some cases where memory accesses are bounded; otherwise the loop is arbitrarily bounded by an external factor.Source: §6 · pp. 9–10
  • Results depend on the chosen payloads and vulnerable applications, with payloads selected to showcase SPL features rather than exhaust possible payloads.The authors note that other payloads and combinations are possible.Source: §6 · p. 9
  • Failure to find a trace may mean no solution exists or that algorithm imprecision prevented discovery; increasing bounds and timeouts makes search more exhaustive but slower.A failure can arise from missing candidate blocks, invalid mappings or paths, or unsatisfiable constraints and solver timeouts.Source: §6 · p. 10
  • BOPC assumes a supplied entry point, but evaluation locations were selected arbitrarily because concrete exploits or crashes were unavailable.In practice, the entry point would come from the exploit or crash context.Source: §6 · p. 10

7 CASE STUDY: NGINX

The nginx case study tests shell execution, looping, and branching from function-reachable entry points. BOPC synthesizes an execve trace in under a minute, an infinite-loop trace in under five minutes, and conditional traces by exploring alternative paths when a shortest path fails.

7.1 Spawning a shell

  • BOPC synthesizes the nginx execve payload and generates a proof-of-concept exploit in less than a minute.The payload uses an existing function that invokes execve with arguments supplied through a structure.Source: §7.1 · p. 11

7.2 Infinite loop

  • The infinite-loop trace uses a single functional block and a dispatcher path exceeding 20 basic blocks, and BOPC synthesizes it in less than five minutes.The entry point is the start of ngx_signal_handler; the dispatcher loops back to the functional block.Source: §7.2 · p. 11, Figure 6 · p. 11

7.3 Conditional statements

  • The nginx conditional case maps virtual registers __r0 and __r1 to rsi and r15 after trying four mappings, then represents the search with a delta graph.The graph identifies an induced subgraph for an if-else payload whose conditional branches into two statements.Source: §7.3 · p. 12, Figure 7 · p. 12
  • For the conditional payload, BOPC clones symbolic state at the branch and searches a second-shortest path after the shortest path raises an invalid-dereference exception.The payload implements logical NOT, setting __r1 to one when __r0 is zero and to zero otherwise.Source: §7.3 · pp. 11–12

8 DISCUSSION AND FUTURE WORK

The prototype demonstrates feasible, scalable construction of BOP chains from a high-level language, but basic-block granularity and bounded search can exclude valid solutions.

8 DISCUSSION AND FUTURE WORK

  • BOPC demonstrates the feasibility and scalability of automatically constructing BOP chains through a high-level language.The authors identify potential optimizations for future versions.Source: §8 · p. 12
  • Basic-block granularity can prevent BOPC from mapping a desired SPL statement that a combination of blocks could implement.For example, one block may set a register to 0 and the next increment it to 1; coalescing blocks could address this issue.Source: §8 · p. 12
  • User-defined bounds and symbolic-execution timeouts reduce search space but can prune potentially valid solutions.Higher bounds may allow BOPC to find alternate or additional solutions.Source: §8 · p. 12

9 CONCLUSION

Data-only attacks remain possible despite strong control-flow defenses, while configuring them under execution-path constraints has required complex manual analysis. BOPC automates payload synthesis, mapping 13 payloads across 10 programs 81% of the time.

9 CONCLUSION

  • Despite CFI or shadow stacks, data-only code-reuse attacks remain possible, and configuring them under restrictive execution-path constraints has required complex manual analysis.Source: §9 · p. 12
  • BOPC automates attack-surface analysis and exploit-payload synthesis by mapping high-level payload statements to functional blocks stitched through CFG-valid dispatcher blocks.Heuristics prune the search space and evaluate more probable paths first for this NP-hard problem.Source: §9 · p. 12

A EXTENDED BACKUS-NAUR FORM OF SPL

The SPL grammar specifies payload structure and the forms of statements, including variable declarations, register operations, memory access, calls, branches, and returns.

A EXTENDED BACKUS-NAUR FORM OF SPL

  • An SPL payload is a void function containing zero or more statements or labels, followed optionally by a return.Source: A EXTENDED BACKUS-NAUR FORM OF SPL · p. 14
  • SPL statements include variable and register assignments or modifications, calls, memory reads and writes, conditional branches, jumps, and returns.The grammar also permits integer-pointer initializer lists and string declarations.Source: A EXTENDED BACKUS-NAUR FORM OF SPL · p. 14
  • The grammar defines registers as __r followed by an identifier from 0 to 7, with variables, numbers, values, operators, and comparison operators given by productions.Source: A EXTENDED BACKUS-NAUR FORM OF SPL · p. 14

B STITCHING BOP GADGETS IS NP-HARD

Stitching BOP gadgets reduces to selecting a minimum-weight induced subgraph in a delta graph, a problem shown NP-hard and not multiplicatively approximable. The proof reduces K-Clique to this selection problem.

B STITCHING BOP GADGETS IS NP-HARD

C SPL IS TURING-COMPLETE

The paper gives a constructive proof of SPL’s Turing-completeness by implementing a Brainfuck interpreter in SPL, with a Brainfuck program supplied as the payload.

C SPL IS TURING-COMPLETE

D CFG OF NGINX AFTER PRUNING

BOPC pruning reduces the displayed nginx CFG portion to a small delta graph; the figure limits the visible function-call depth to three.

D CFG OF NGINX AFTER PRUNING

  • Pruning reduces the displayed nginx CFG portion to the small delta graph in Figure 7.The graph begins at ngx_cache_manager_process_cycle and displays functions up to three calls deep.Source: D CFG OF NGINX AFTER PRUNING · p. 15
Loading 1805.04767v2…