TL;DR

ROP attacks have a simple premise: find gadgets, chain gadgets, get shell. But what if we don’t have any gadgets? Well, then we can’t do ROP. G-Free is a tool and technique that removes all the gadgets from a binary, and thus, makes it impossible to do ROP attacks. The authors show that binaries compiled with G-Free are comparable in size and performance to the original binaries, and that G-Free is effective at defeating ROP attacks while maintaining the functionality of the original binaries.

What is the problem?

Return Oriented Programming (ROP) is a technique used to perform arbitrary code execution whenever a program returns to a user-controlled address. ROP is mostly used to bypass security mechanism that don’t permit the attacker to inject their own code into the program’s memory (NX and DEP). ROP achieves this by chaining snippets of code (gadgets) that are already present in the program’s memory, in order to create a payload that will perform the desired action. The paper G-Free: Defeating Return-Oriented Programming through Gadget-less Binaries by Onarlioglu et al. presents a new technique to defeat ROP attacks.

Why is this worth our time?

There have been numerous attempts to defeat ROP attacks, here are the most prominent ones:

1. Firstly, we have ASLR, which randomly shifts the location of the program’s memory at each execution. This makes it harder for the attacker to find the gadgets they need to create their payload, but one can still find gadgets by brute force or via memory leaks.
2. Secondly, we have stack canaries, which are located just before the return address on the stack, and checked to make sure they haven’t been tampered with. If they have, the program will crash. This makes it harder for the attacker to find the gadgets they need to create their payload, but one can still find gadgets by brute force (on 32-bit) or via memory leaks.
3. Thirdly, we have PIE, which I like to call “hardcore ASLR”. PIE is similar to ASLR, but it shuffles the program’s code and data at each execution. This is one of the hardest techniques to defeat, but again, it can be defeated via memory leaks.
4. Finally, we have CFI, which is a technique that makes sure that the execution flow of the program is always valid. In layman’s terms, a function may only return to a specific set of places, and nowhere else. There have been papers that have tried to defeat ROP by using CFI, but they all have their own limitations.

All of these techniques are cool, BUT THEY DON’T REALIZE WHAT’S OBVIOUS!!! How can you do ROP if you don’t have any gadgets? It’s so simple, yet so effective. The paper presents a new technique to defeat ROP attacks, by just… making sure that there are no gadgets.

The work’s contributions

The paper’s main contribution is the detailed breakdown of how to remove most of the useful gadgets from an x86 binary. The paper is also the first to show that it is possible to defeat all forms of ROP attacks, obviously, since there are no gadgets to chain. Then, they publish a tool, which anyone can use to remove all the gadgets from their binary. Finally, they show that their technique is effective, by removing all the gadgets from glibc, while still being able to run programs that use glibc.

How did they do it?

The authors built an assembly transpiler which would, among other things, convert instructions that encoded free-branch instruction into semantically equivalent instructions that did not. They also used techniques which wouldn’t directly remove these instructions from the binary, but would protect those instructions from being used in ROP attacks. The authors show the (negligible, ~25%) size difference between the original binaries and the G-Free binaries by compiling a suite of popular programs, and then comparing the size of the binaries. I don’t understand the concern of size, since x86 is an architecture that isn’t used in embedded systems, and the size of the binaries is not a concern for most people. Then, the authors also the performance difference between the original binaries and the G-Free binaries by running a suite of benchmarks, which is about 5% slower. For this, it would be a concern for x86, but I think that there is room for optimization. I would have liked to see a table of the reduction in the number of gadgets in each binary, and a proof that a gadget cannot be created for that particular binary. However, at the time, automated gadget finding and automated gadget chaining were not a thing, so obviously, the authors couldn’t do that in one paper.

What does this mean for the community?

The authors show that it is possible to defeat all forms of ROP attacks. This is very useful for the scientific community in order to successfully support their arguments, which may depend on the fact that ROP attacks are possible. For the security community, this is a very useful tool to use in order to secure a program that is written in a low-level language, interacts with user input, was written by incompetent developers, and sits in a critical part of an organization’s infrastructure.

What are the limitations of this work?

Now we can use G-Free’d binaries to defeat ROP attacks, hurray! Problem solved, right? Well, that was 13 years ago, and G-Free isn’t used by virtually anyone. This is all my opinion, but I think that there are two major issues with why G-Free as a tool isn’t and wasn’t used really used:

1. Who would want to use G-Free? Probably someone who is writing a compiler, and wants to implement safety features. However, as we have discussed, G-Free’d binaries are 5% slower, which isn’t much, but it’s a ton for compiler engineers, which work day and night to squeeze every last bit of performance out of their compiler. So, the first issue is very pretentious people representing the demand side of the market /s.
2. There is a reliability issue. G-Free does some weird stuff to binaries, which may cause programs that also do weird stuff to break. For example, a program that accesses the return address on the stack may break, since it is being encrypted by the ret protector. The authors do mention this and explain how they circumvented this issue, but this seems like a kick-the-can-down-the-road type of solution, as compiled programs rely on so many assumptions that we can’t possibly cover all of them.

How could other researchers build on this? What are future work directions?

There are four major avenues of future work:

1. Make G-Free faster. There are several optimization techniques that can be applied to G-Free. For example, statically determining the right size of the nop sled, instead of always emitting 9 instructions.
2. Make G-Free more reliable. As mentioned above, this would be possible, but it would require a lot of work, and it would be hard to maintain as compilers change.
3. Update G-Free to modern architectures. G-Free was written for x86 (32-bit), and it would be a good idea to update it to x86-64, and maybe even ARM. Me and a couple of other undergrads are working on this, and we have already made some progress. We are building SafeLLVM which is an x86-64 implementation of G-Free in LLVM. We are also working on a paper that will be submitted to some conference in the near future.
4. Add new protections to G-Free. There are new ROP attacks that have been discovered since G-Free was written, and it would be a good idea to add protections against them. On the top of my head, I can think of longjmp-based Jump Oriented Programming (LJOP), and Sigreturn Oriented Programming (SROP).