Microsoft recently announced the winners of its BlueHat Prize Contest. The goal of the contest was to develop a defense against Return-Oriented Programming (ROP). Vasilis Pappas, Ivan Fratric, and Jared DeMott won a combined total of $260,000 with Vasilis Pappas winning the lion’s share ($200,000) for his kBouncer mitigation measure. Unfortunately for Microsoft, all three of these defenses are already broken.

The first place winner, kBouncer [5], leverages an Intel protected-mode instruction that allows an OS kernel to extract the last several executed branches. When a user application calls into the kernel, the kernel will check that the last set of return instructions executed actually returned to a location after a call instruction. Pappas does admit that kBouncer does not protect against return-oriented programming that doesn’t use returns—a technique pioneered by Hovav Shacham and me in 2010 [3]. However, this is not the only way to defeat kBouncer.

As Pappas writes, “[a]nother way to evade [kBouncer] is by using ROP code to overwrite the contents of the [branch trace] registers with legitimate call-return control transfers just before performing the system call.” He continues that this would be “extremely hard to realise.” In fact, this is not true. It is not the case that a return-oriented program is limited to executing only the gadgets that make up its Turing-complete functionality. Indeed, it is entirely possible to craft a separate function call stack and execute legitimate functions in the program. When these functions return, control returns to the return-oriented program. As long as the sequence of indirect branches (in particular returns) between the function’s entry point and when it first makes a system call is sufficiently long, kBouncer will not detect the return-oriented program.

This is not a theoretical vulnerability, it is precisely the tack I took when crafting a voting-stealing program in my 2009 paper with Ariel J. Feldman, Brian Kantor, J. Alex Halderman, Edward W. Felten, and Hovav Shacham [2]. In a sense, this is not surprising. It is not always the case that the attacker wishes to induce entirely new behavior when exploiting a program. Often, it is sufficient to modify the behavior of the program and this can be accomplished without the need to make new system calls. (Note that I’m not claiming to have anticipated kBouncer and written an exploit to defeat it; I’m simply noting that one natural way to write ROP code defeats it as a side effect.)

The second place prize was claimed by Ivan Fratric for his ROPGuard. I have not yet seen the details for ROPGuard, but arstechnica is reporting that it has already been defeated [4]. It’s not clear if this is a fundamental break of the technique or simply an implementation error.

The third place entry was /ROP by Jared DeMott and like kBouncer only tries to defend against the original incarnation of ROP which relied on return instructions. It is also defeated by return-oriented programming without returns.

In the winners’ defense, their techniques do raise the bar for attackers by eliminating the easiest and most natural form of ROP.

In closing, I should note that Microsoft already knows a comprehensive defense against ROP and a large class of control-flow hijacking attacks. In fact, they invented the technique (at least in part)! I am, of course, referring to Control-Flow Integrity developed by Martín Abadi, Mihai Budiu, Úlfar Erlingsson, and Jay Ligatti [1]. So with this in mind, the title of this page refers to the fact that ad hoc defenses against exploitation are still defeated and comprehensive defenses are still successful. In short, ROP’s status is unchanged.

References

  1. Martín Abadi, Mihai Budiu, Úlfar Erlingsson, and Jay Ligatti. Control-Flow Integrity: Principles, Implementations, and Applications. In Catherine Meadows and Ari Juels, editors, Proceedings of CCS 2005. ACM. November 2005.
  2. Stephen Checkoway, Ariel J. Feldman, Brian Kantor, J. Alex Halderman, Edward W. Felten, and Hovav Shacham. Can DREs Provide Long-Lasting Security? The Case of Return-Oriented Programming and the AVC Advantage. In David Jefferson, Joseph Lorenzo Hall, and Tal Moran, editors, Proceedings of EVT/WOTE 2009. USENIX/ACCURATE/IAVoSS, August 2009.
  3. Stephen Checkoway and Hovav Shacham. Escape From Return-Oriented Programming: Return-oriented Programming without Returns (on the x86). Technical Report CS2010-0954, UC San Diego, February 2010.
  4. Dan Goodin. Microsoft defense that fetched $50,000 prize bypassed in just 2 weeks. arstechnica. August 2012.
  5. Vasilis Pappas. kBouncer: Efficient and Transparent ROP Mitigation. April 2012.