PK Wiki

source · sources/Control-Flow Integrity — Abadi et al.md

Control-Flow Integrity — Abadi et al.

status: active · created 2026-06-20 · 1 source · #security #software-security #control-flow #exploitation #paper

The foundational paper that named and formalized Control-Flow Integrity. Journal version (ACM TISSEC, 2009) of work first presented at ACM CCS 2005 (and ICFEM 2005). Auto-grounded 2026-06-20 to back the Control-Flow Integrity concept page (fetched from the author's faculty page).

Summary

The paper introduces CFI as a basic safety property: software execution must follow a path of a Control-Flow Graph (CFG) determined ahead of time. The CFG can be derived by source-code analysis, binary analysis, or execution profiling; the authors' implementation uses static binary analysis and targets Windows on x86. The motivation: after mitigations like stack canaries and non-executable data (NXD/DEP) were deployed, attackers still subverted execution — "abnormal control-flow modification is an essential step in many exploits," independent of the specific vulnerability. The authors show a vulnerable median() function exploitable even on Windows XP SP2 with hardware NXD and a StackGuard analogue, via stack overflow and C++ vtables.

Enforcement (inlined, via machine-code rewriting). CFI is enforced as an Inlined Reference Monitor: the binary is rewritten to insert a bit-pattern ID at each legal destination of a computed/indirect transfer, and an ID-check before each indirect call, jump, or return that verifies the destination carries the expected ID. Transfers the CFG doesn't sanction are blocked at runtime. The instrumentation is simple to verify after the fact.

Threat model. Protection holds even against a powerful adversary with full control over the entire data memory of the running program — ID-checks and IDs live in code and don't rely on data-memory integrity. The authors prove correctness of inlined CFI for an abstract machine with a simplified instruction set.

Three required assumptions (CFI's guarantee rests on these):

  • UNQ — Unique IDs: ID bit patterns must appear nowhere in code except in IDs and ID-checks (easily met with large, e.g. 32-bit, IDs that avoid opcode bytes).
  • NWC — Non-Writable Code: the program must not be able to modify code memory at runtime (else an attacker overwrites an ID-check). True on most systems except during dynamic-library loading and runtime code generation.
  • NXD — Non-Executable Data: the program must not execute data as code (else an attacker runs data labeled with the expected ID). Hardware-supported on recent x86; Windows XP SP2 used it. NXD alone (without CFI) stops some attacks but not those that reuse pre-existing code.

Key claims

  • Performance is practical. On SPEC benchmarks, CFI-instrumented binaries ran on average 16% slower, range 0%–45% (45% on crafty, the highest measured). Binary size grew ~8% on average; instrumenting a binary took ~10 seconds.
  • Much cheaper than comparable techniques. Program Shepherding's overhead is

    100% on crafty (CFI: 45%) and >660% on gcc (CFI: under 10%).

  • CFI is a foundation for stronger policies. The authors build on it for a protected user-level shadow call stack (claimed ~order-of-magnitude faster than prior software implementations) and Software Memory Access Control (SMAC) / an efficient variant of SFI.
  • Guarantees are formal and adversary-robust — a deliberate contrast with earlier mitigations that relied on "informal reasoning and hidden assumptions."

Connections

  • Control-Flow Integrity — this source grounds and upgrades that concept page from #unsourced draft to active.
  • Match Process Weight to Stage and Stakes — see also (cross-domain): CFI is an instance of the ⚖️ "justified heaviness" quadrant — security rigor whose ~16% overhead is worth paying when exploitation stakes are high.

Source

The wiki is the source. This door reads it at build time and never writes to it.