A gentle introduction to return-oriented programming


As I have promised in my last post I will start a series about return-oriented programming. I start with a short introduction about the topic. The introduction covers the origin of return-oriented programming, describes what return-oriented programming is and ends with a definition of return-oriented programming which I will use in the future posts. I will also take some of the recent discussions on Twitter into account which showed that even though I thought I did my history research pretty well, there were still some mailing list post missing from my time-line.

Why do we need return-oriented programming ?

Return-oriented programming is a technique which allows an attacker to execute code in the presence of the following defensive measures.

  • Non executable memory segments
  • Code signing

Where does return-oriented programming come from ?

Return-oriented programming is a recently coined term which describes a technique that has been developed in an iterative process in the security community. The terminology return-oriented programming is used for a subset of techniques which can be referred to as code reuse techniques. To understand where return-oriented programming comes from I show some of the milestones of the techniques history.

Buffer overflows were first publicly documented in the Computer Security Technology Planning Study in 1972 (Appendix 1. Incomplete Parameter Checking). To put this in perspective one must remember that even though we now know that this document was published at the time only a small circle of individuals had access to the document then.

A buffer overflow is, in the original form, a very simple error that is introduced if a function does not perform proper bounds checking for the accessed memory. Basically this means the function receives more input data than it can store. Assuming that the overflowed buffer was located on the stack, the attacker can now write a certain amount of data onto the stack where other variables and the return address might be located. Therefore the attacker can hijack the control flow of the current process and perform an arbitrary computation.

The first major attack which used a buffer overflow as the targeted vulnerability was the Morris worm in 1988. But it was not until the late 90s that major operating systems started to have any protection against buffer overflows. For Microsoft operating systems a form of protection against buffer overflows was only added after the Code-Red and Slammer worms had changed their security mindset in 2004.

One of the defensive measures which have been developed to defend against buffer overflows is the option to mark data memory segments as non-executable. This lead to the next evolutionary step towards return-oriented programming.

Return-into-library technique

The return-into-library technique is the root on which all return-oriented exploit approaches are based.

A return-into-library exploit works as follows: After the attacker has hijacked the control flow, a library function he chooses is executed. The attacker has made sure that the stack pointer points into a memory segment he controls. The attacker has set up the data in the memory segment in a way that it provides the right arguments to the library function of his choice. Through this he can execute a function with the needed arguments.

The technique of return-into-library exploits was initially presented publicly by Solar Designer in his 1997 posting to the Bugtraq mailing list. In this mail the groundwork for return-into-library exploiting was presented. The next milestone in the development of the technique was the Phrack article by Nergal which summarized the known techniques and broadened the attack vector by introducing esp shifting which allowed unlimited chaining of function calls to be used within return-into-library exploitation.

Borrowed code chunks technique

With the introduction of hardware-supported non-executable memory segments in combination with the support of 64 Bit CPUs the game changed again and traditional return-into-library exploits ceased to work. This was due to an ABI change which now required that the arguments to a function must be passed in registers rather than on the stack. Stealth developed a new approach that uses chunks of library functions instead of the call to the function itself to still be able to exploit buffer overflows on machines that employed the newly introduced defense. The approach is designed around the idea to locate instruction sequences which pop values from the stack into the right registers for function calls. By using his approach an attacker can use return-into-library exploits with the new ABI. A library which uses this technique in an automated fashion is DEPLib which has been developed by Pablo Sole. This library completely automates the return-oriented approach for Windows operating systems but it lacks support for loops and conditional branches (which is from a practical point of view negligible).

Return-oriented programming

The return-oriented programming technique broadens the attack vector even further by introducing loops and conditional branches for the return-oriented approach. The first academic work published in the field of return-oriented programming is Hovav Shacham’s ”The Geometry of Innocent Flesh on the Bone: Return-into-libc without function Calls (on the x86)” It describes the two major points which get addressed by return-oriented programming in contrast to the rest of the return-into-library techniques.

  • The return-into-library technique has no support for loops and conditional branching.
  • The removal of functions from libraries does not provide any security against return-oriented programming.

For the x86 the approach he uses to find suitable instruction sequences is based on the fact that the x86 uses a variable length instruction set. Therefore it is possible to search for single binary opcodes which alter control flow such as the return instruction (0xC3) and disassemble the binary from this position backwards. Because x86 uses a variable length instruction set the bytes before the return instruction can provide many possible instruction sequences. Shacham also defined the term gadget which describes one useful instruction sequence which performs one useful operation such as addition.

One assumption which Shacham made is that he thought a fixed length instruction set would make the application of return-oriented programming unfeasible. This was shown not to be the case by Ryan Roemers work which targeted the SPARC architecture which can be seen as the anti-thesis to the x86 architecture. One change which he needed to incorporate into his gadget set was that only memory could be used to pass information between gadgets. This is due to the way SPARC passes information in registers by shifting the register window.

The most practical work which has been published in the field of return-oriented programming is the recent work which targeted the AVC Advantage voting system. This work has provided proof that return-oriented programming is a valid tool for the offensive security researcher as no other technique would have been as useful against the Harvard-type architecture upon which the AVC Advantage is build.

What did we learn ?

Return-oriented programming is a recently coined term but the underlying technology has a long history which is based on the work of many security researchers. We have started with its roots in return-into-library attacks and showed how it evolved until today.

In the next post on return-oriented programming I will explain the first steps of my approach to make return-oriented programming platform independently.


19 Responses to “A gentle introduction to return-oriented programming”

  1. jf says:

    ty for explicitly stating (by stating explicitly what the technique does bypass) that this isnt a given ASLR bypass technique, as everyone else seems to miss.

  2. […] for platform independent return-oriented programming (I of III) By Tim Kornau In my last post about the history of return-oriented programming I showed that we are not dealing with a completely […]

  3. Anon says:

    Can anyone write a brief guide illustrating the use of rop in an exploit? Like say our codebase is in file.dll, we have control of some return address and want to use rop to copy shellcode from the buffer on the stack, to an rwx memory area and then pass program flow to it.

    How would the ‘gadgets’ from the codebase be generated? Basically I’m just looking for help on how to convert a regular sequence of assembly instructions into its equivalent rop code. Thinking of it as the roles of eip/esp being switched is also kind of confusing and not intuitive.

  4. Anon says:

    Oh! I just noticed there’s a second post. Reading that now and hopefully it will answer some questions.

  5. […] list of addresses that point into code of an Adobe Reader DLL called BIB.DLL. We were dealing with return-oriented shellcode […]

  6. i was just thinking about this similar thing before haha, excellent article

  7. […] ROP return-oriented programming Zynamics introduction to ROP is a popular technique used to bypass DEP and jump to alternate memory locations by using code that […]

  8. […] iterative development in the security community for more than a decade, ROP allows an attacker to sidestep more modern operating system defenses, such as non-executable memory — also known as data execution prevention — and code […]

  9. […] iterative development in the security community for more than a decade, ROP allows an attacker to sidestep more modern operating system defenses, such as non-executable memory — also known as data execution prevention — and code […]

  10. […] the PC to a ROP (return oriented programming) gadget (both defined) and employs a stack pivoting technique. This ROP chain changes the memory space (mentioned above) […]

  11. […] Since Flash Player incorporates commonly used defences such as DEP and ASLR (references discussing DEP are provided here (see “References” at the end of the post), while ASLR is discussed here and here (see “References” at the end of the post)) attackers generally seek to bypass these mitigations using a technique known as Return Oriented Programming (ROP)(defined). […]