Return Oriented Programming without Returns

We show that on the x86 it is possible to mount a return-oriented programming attack without using any return instructions. Our new attack instead makes use of certain instruction sequences that behave like a return; we show that these sequences occur with sufficient frequency in large Linux libraries to allow creation of a Turing-complete gadget set.

Because it does not make use of return instructions, our new attack has negative implications for two recently proposed classes of defense against return-oriented programming: those that detect the too-frequent use of returns in the instruction stream, and those that detect violations of the last-in-first-out invariant that is normally maintained for the return-address stack.