Return-oriented programming

Return-oriented Programming (ROP) is a naturally occurring esoteric language that arose in the exploitation of W^X programs which means that data in the programs' memory is writable or executable but not both. Programs with W^X cannot be exploited in the usual way of supplying compiled code to be directly executed as data to the program, instead a technique was devised in [1] to piece together a Forth-like programming language out of small segments of already existing "innocent" code that ends in RET.

Programming is done by putting pointers to these gadgets as well as constant data for them to reference on the stack. Hovav describes building a trie of gadgets by searching backwards from RET instructions in libc, after finding enough of these he shows how to piece them together to perform various boolean operations, arithmetic and then unconditional and conditional jumps as well as system calls - it is noted that the "instruction set" of gadgets form a Turing-complete set. The Weird Machines paper [2] discusses the more general phenomenon of higher complexity languages showing up unwanted in programming.

Example

A simple example of loading a constant into a register:

          |    ...     |
          +------------+
          | 0xdeadbeef |
          +------------+
          |      -----------> pop edx
  esp --> +------------+      ret
          |    ...     |

The constant is stored on the stack and then the gadget to load it is pointed to. When the program execution loads its return address off the stack by popping esp it will execute that gadget.

References

• [1] The Geometry of Innocent Flesh on the Bone - Return-into-libc without Function Calls (on the x86) - Hovav Shacham (2007)
• [2] Exploit programming - Weird Machines From Buffer Overflows to "Weird Machines" and Theory of Computation - Bratus et al. (2011)