Exploit Programming: From Buffer Overflows to “Weird Machines” and Theory of Computation
Reference: Bratus, Locasto, Patterson, Sassaman, Shubina (2011). ;login: The USENIX Magazine, Vol. 36, No. 6 (December 2011). Source file: Bratus.pdf. URL
Summary
This influential ;login: article reframes exploitation research as a discipline of computation theory. The authors trace the evolution from simple stack-smashing (Aleph One) through return-to-libc, return-oriented programming, heap feng shui, and format string exploits, and argue that every such technique amounts to identifying and programming a “weird machine” latent inside a target: an unintended computational model realized by crafted inputs that drive the target’s own code into performing computations its designers never intended.
The essay is dedicated to Len Sassaman and is both a memorial and a manifesto. It argues that “attack papers,” often dismissed as intellectually marginal, are in fact constructive proofs that a target contains a stronger automaton than its designers believed, and thereby exposes incorrect assumptions about the computational nature of the system. Exploitation, in this view, comes full circle to the foundational questions of Church and Turing (“what can a given machine compute?”) and deserves treatment as a rigorous subdiscipline unifying hacker practice with language-theoretic and computation-theoretic analysis.
Key Ideas
- Exploits are programs for weird machines instantiated inside a target.
- Evolution: stack smashing -> return-to-libc -> ROP -> heap feng shui -> format strings.
- “Weird instructions” as attacker-programmable primitives borrowed from target code (strcpy+RET, malloc bookkeeping, printf %n).
- Attack papers as constructive proofs of unintended computational power.
- Exploitation research as empirical computability theory: “what can this machine actually compute?”
- Language- and computation-theoretic methods can redefine weaknesses previously overlooked.
- Call to unify hacker craft with academic theory of computation.
Connections
Conceptual Contribution
- Claim: Exploitation is the empirical study of unintended computational models (“weird machines”) inside real systems, and brings security research back to the Church-Turing questions of what a given machine can compute.
- Mechanism: Reconstructs the history of memory-corruption exploitation as a progression of increasingly general ways to program target-internal weird machines using crafted input data as instructions borrowed from the target’s own code and data-interpretation loops; reinterprets attack papers as constructive proofs presenting a computationally stronger automaton than expected.
- Concepts introduced/used: Weird Machine, Exploit Programming, Return-Oriented Programming, Computability, LangSec, Attack Papers
- Stance: foundational
- Relates to: Companion essay to Security Applications Of Formal Language Theory by the same authors; provides the conceptual vocabulary (Weird Machine) invoked throughout LangSec and pertinent to Agent Security and LLM Agents where crafted prompts or tool inputs similarly instantiate unintended computation (Prompt Injection, Tool Use).
Tags