Life of a Computer Scientist

Background:

Shadow Stack protects against Return Oriented Programming by maintaining a separate return addresses stack from the usual call stack. Traditionally, the compiler puts both the return addresses and local variables on the same commingled stack, including array sized variables. When the code suffers buffer overflow, the return address of a function call gets overwritten by arbitrary user-provided data, which converts a function return to a "goto" leading to Remote Code Execution.

Although most OSes now map the stack memory to prohibit code execution, Return Oriented Programming is an exploit technique that structures the arbitrary code as a series of function returns similar to Continuation Passing Style, except the gotos are stitched together from cherry-picked valid code sections. It does not "goto" to the stack, and it can recover the stack address to fetch the payload once arbitrary code execution starts.

Function pointers in stack-allocated objects can be another attack vector for remote code execution. In C++, objects with virtual methods have a pointer to a Virtual Method Table that allows runtime dynamic dispatching. The virtual table pointer could be overwritten by buffer overflow and exploited. However, this attack vector is harder to exploit compared to Return Oriented Programming. Successful exploit would require predicting the stack address and some coincidence in the vulnerable code to pass arbitrary data to a valid function or method.

This is not related to the PHP critical remote code execution discovered earlier this week, which exploits the use-after-free vulnerability when parsing HTTP POST request uploads. PHP has also suffered heap buffer overflows in the past, but it is not a stack buffer overflow. Heap buffer overflows are even more difficult to exploit because it does not directly alter the code execution path like stack overflow does.

History of Intel Instruction Set Stacks

The decision to put the return address and variables on the same stack is historical. The 16-bit Intel 8086 instruction set has two registers for stack operations: SP (stack pointer) and BP (base pointer), both operating on a SS (stack segment) which commingles return address and data. The SP is operated on by:

CALL and RET instructions for function call and return.
PUSH and POP instructions to save and restore the values of general and special purpose registers.

The BP is operated on by ENTER and LEAVE which reserves and releases stack space for local variables and for the code to address the local variables, but in practice compilers never use ENTER and LEAVE and just precompute the local variable SP offsets at compile time, which frees BP for an additional general purpose register.

Besides SS (stack segment), the Intel 8086 instruction set also has CS (code segment), DS (data segment), and ES (extra segment). It allowed these microprocessors to behave like a Harvard architecture separating code and data, even though the processor allows their memory to overlap. The 16-bit architecture has a hard limit of 64KB addressing, so in theory, code could enforce separation by programming the segments to non-overlapping 64KB blocks.

Modern operating systems running on Intel 32-bit and 64-bit instruction sets mostly eschewed separate segments by programming them to the same flat address space. However, the instruction sets still provide separate ESP/EBP (32-bit) and RSP/RBP (64-bit) registers, and they still technically operate on SS (stack segment).

The 32-bit and 64-bit instructions also added FS and GS segments for the OS to address thread local storage. The 64-bit instruction set now ignores CS, DS, ES and SS but still honors FS and GS.

Separate SS?

Without changes to the 32-bit instruction set, the OS could designate SS to a non-overlapping return address stack, with SS:ESP is still operated on by CALL/RET and PUSH/POP instructions. The compiler would be modified for this alternative ABI to:

Leave SP to be managed by the CPU alone.
Use BP to track the data stack pointer.

However, it must never address memory through BP since the instruction set will operate on the SS (stack segment) instead of the intended DS/ES (data segment).

On the 64-bit instruction set, it would require modifying the CPU to honor SS again.

Although virtual table pointers for objects on the data stack could still be overwritten by buffer overflow, CS/DS and SS have separate address spaces, so virtual method call to SS or using SS as regular data would not be possible.

Intel Shadow Stack

Without changes to the compiler, the Intel Shadow Stack is a CPU based security feature that maintains a separate CALL/RET memory page mirroring what return addresses should be expected from the commingled stack. It is programmed by the OS kernel, and the user-space code has no access or knowledge of it. On RET, if the return address on the commingled stack differs from that in the shadow stack, the CPU raises a General Protection Fault. The OS would handle this and kill the process with Segmentation Fault.

Theoretically, the Intel Shadow Stack can also be made to work in the OS kernel, but having the OS kernel handle General Protection Fault for its own code is tricky. This is why Intel Shadow Stack works in user-space first while the kernel-space protection lags behind.

The Intel Shadow Stack also does NOT prevent the virtual table pointers for objects on the commingled stack to be overwritten by buffer overflow, as virtual table function calls could be redirected to malicious addresses while following the usual CALL/RET.

Arena Allocation

A compiler-only implementation of the Shadow Stack does not require support from the CPU hardware or the instruction set. Indeed, the rest of the CPU instruction set architectures like MIPS, RISC, and ARM assume a flat address space and do not have separate segments, so a compiler-only approach is both more portable and retroactively effective on older CPUs.

Although we can say that buffer overflow vulnerability is a result of the decision to commingle return address and data on the same stack, local variables for primitive type are not the problem because primitive types are fixed sized. The problem is storing array sized variables on the stack that requires careful bounds checking.

We can continue to store primitive types on the return address stack, including register spills, but move array allocations to a heap-allocated arena that still has a stack-like LIFO semantics. When buffer overflow happens, it will only spill to other arrays in the arena. Since the arena is heap-allocated to only store data, it mitigates remote code execution the same way heap buffer overflow does.

Instead of:

void foo(...) {
    char buf[32];
}

The compiler would transform the code into something like this:

void foo(void *arena, ...) {
    // * The outermost caller would pre-allocate arena with mmap(),
    //   plus protected pages at the end.
    // * The arena is already a local variable, so it is automatically
    //   saved and restored in function calls.
    // * Users managing arenas manually must make sure the arena is
    //   naturally aligned to 16 bytes.
    char *buf = (char *) arena; arena += sizeof(char[32]);
}

If a function wishes to initialize an object from the arena and return it back to the caller, it would accept arena as a mutable reference instead:

struct bar *new_bar(void **arena, ...) {
    struct bar *p = (struct bar *) *arena; *arena += sizeof(struct bar);
    *p = (struct bar){ ... };
    return p;
}

When objects are stored on the arena, virtual table pointer could still be overwritten by buffer overflow, but this is also just a heap buffer overflow, not a stack buffer overflow. The compiler could also enforce this at compile time. Same for C function pointers.

As a programming style, since arena allocation can be done at the code level with very minimal modification, we can already minimize the damage of stack buffer overflow by rewriting local array allocations to use a heap-allocated arena.

Conclusion

Shadow Stack is not a panacea for preventing buffer overflow problems. It is also not a panacea to prevent remote code execution. It only prevents a very specific scenario where the buffer overflow allows remote code execution via Return Oriented Programming.

We can achieve most benefits of Shadow Stack with Arena Allocation, by moving array allocations to a separate heap-allocated arena. This mitigates Return Oriented Programming by converting stack buffer overflow to a heap buffer overflow, which is harder to exploit. Of course, we would like the compiler to do more array bounds checking as well, but that is a harder problem for the compiler. Arena Allocation is fairly easy to achieve both by the compiler or as a minor modification in programming style, even without hardware or instruction set support.