The holy GCC

After running the benchmarks compiled using llvm-gcc and making sure that the technique was working, it was time to modify gcc. In order to take advantage of gcc's optimizations, I changed my strategy a little bit and modified the RTL generation phase to generate code for upward growing stack. Modifying code generation phase was still inevitable, because our target was x86 that only supported downward growing stack and some instructions should have been augmented with extra instructions to work properly when stack grew upward.

One of the instructions in x86 which is difficult to transform for upward growing stack, is RET <16-bit Integer>. This instruction pops the return address from the stack and internally increments the stack pointer (SP) by the value of its operand and then jumps to the popped return address. When stack grows upward, the stack pointer should be decremented rather than incremented. Now if we replace this instruction with an instruction that decrements the stack pointer and a normal (with no operand) RET instruction, the value that the RET reads is not the correct return address, because the stack pointer no longer points to the return address.

A solution to this problem is using a set of instructions to read the return address and store it in a temporary register, decrement the stack pointer and jump indirectly to the temporary register. We use ECX as the temporary register, because it is a volatile register that is assumed to be clobbered after a function call and it is not used to return values to the caller too.

The value that is decremented from the stack pointer should be <RET operand> minus 4. The reason is that the stack pointer is decremented by 4 after all CALL instructions (refer to this article). The SP is adjusted to compensate the amount added to it by a RET instruction. Now that we remove the RET instruction the SP should not be adjusted after CALLs to these functions. By subtracting 4 from the value, we eliminate the effect of the SP adjustment after the CALL instructions.

If you are interested in the details of instruction augmentation for reverse stack, you can take a look at this article.

Compiler and Library

I modified LLVM to generate executables that write the stack in opposite direction. It took me several weeks till I had a customized llvm-gcc which could generate reverse-stack executables that ran correctly. My approach was to modify the code generator, patch stack manipulating instructions and change stack offset computations.

To generate reverse-stack executables modifying a compiler is not enough. You also need a reverse-stack library to link against. It may seem that when we have a compiler, we can compile a library for reverse stack growth, but life is not always easy! There is good amount of assembly code in all libraries that should be modified for reverse stack. I picked dietlibc and modified assembly files manually. Since my intent was to run SPEC CPU benchmarks, I had to modify some of the C sources as well to make the library compatible with the standard libc. Without these modifications, runspec would fail during output verification.

At the end, results exceeded my expectations. Less than one percent performance reduction on average, comparing to a normal executable!

The Project

I am trying to build a multi-variant execution environment which runs multiple variants of a single program on different processors/cores and monitors their outputs. Any divergence among the outputs raises an exception and interrupts the execution. The goal of this system is to make programs resilient against malware (viruses, internet worms, etc.).

More specifically we are targeting buffer overflow and similar vulnerabilities such as boundary error, format string, ... that give the opportunity to an attacker to overwrite activation records (return address or frame pointer) on the stack. Overwriting the activation records can lead to malicious code execution.

To fight activation record overwrites, we run two variants of the same program that write the stack in different directions. For example, in x86 stack is written downward and executables generated by compilers conform to this regulation. We have modified a compiler to generate executables that write the stack upward. Running a normal executable along with a reverse-stack executable in a multi-variant environment can disrupt all known buffer overflow exploits. The reason lies behind the fact that all inputs to the program is sent identically to both variants. Therefore, an attacker cannot send different attack vectors to each variant. An attack vector that overwrites activation records on one variant, has different effects on the other one which causes the outputs to diverge. Output divergence is detected by our multi-variant environment and execution is interrupted.