Smashing the heap by overflowing the stack
I ran across something strange while learning about Rust's stack overflow and segmentation fault handling.
First, some backstory: in the past, Rust (and Go) used segmented stacks, also known as split stacks. This is a scheme that allows you to start each thread with a small amount of stack space, and dynamically allocate a new, discontiguous chunk of stack space when you run out. Each function starts with a call to __morestack to see if it has enough stack space for that function's variables. If not, __morestack is supposed to allocate more space, quietly switch out the stack pointer, and call the function. When the function returns, __morestack frees the additional space and restores the original stack pointer. For a system like pre-1.0 Rust's tasks or Go's goroutines, allocating lots of tiny, growable stacks makes sense.
However, Rust's __morestack function currently only serves to trigger stack-overflow handling: the only thing that it does, besides aligning the stack properly, is call the rust_stack_exhausted function, which prints an error message and exits. Rust gives each thread plenty of stack space, so if it overflows, it probably means there's unbounded recursion and the thread should be terminated.
I thought this was a little odd. When you overflow the stack in C, or in any other language without __morestack, the next instruction tries to access unallocated memory. This causes a standard segmentation fault, which terminates the program. What's the need for Rust to catch this and terminate the program on its own?
Part of the answer is to provide a better error message. A straightforward stack overflow is not a memory safety violation in the same way an access to out-of-bounds memory is, so a segmentation fault is the wrong way to report a stack overflow. But the real answer turns out to be subtler than that. While accessing an invalid page of memory cannot cause data corruption, it's not guaranteed that the page is in fact invalid! With enough luck, you can overflow the stack far enough and reach into a completely unrelated memory region.
It turns out that this is possible in well-defined C, in a worrisomely straightforward way. The following program generates no warnings:
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
void clobber(uintptr_t target_address) {
int dummy;
uintptr_t dummy_address = (uintptr_t)&dummy;
char array[dummy_address - target_address];
array[50] = 'x';
(void)array; // suppress warning about unused variable
}
int main(void)
{
int i;
int *x = malloc(20 * sizeof(int));
for (i = 0; i < 20; i++)
x[i] = 3;
clobber((uintptr_t)x);
for (i = 0; i < 20; i++)
printf("%d ", x[i]);
printf("\n");
return 0;
}
and produces this output on my computer (an x86-64 machine running Debian GNU/Linux 8):
geofft@titan:/tmp$ gcc -Wall -Wextra -Wpedantic --std=c99 -o lol-stacks lol-stacks.c
geofft@titan:/tmp$ ./lol-stacks
3 3 3 3 7864323 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
What's going on? We create a variable on the stack called dummy, to figure out where our stack is. Then we figure out how far we are from the target address and create a giant array of exactly that size. Now the end of the stack lines up, more or less, with the target address. The process of "creating an array" doesn't involve any actual changes to memory, just changes to the interpretation of memory (and usually updating the stack pointer register), so while there's a wide swath of invalid memory between &dummy and target, none of it is accessed. Therefore, because the only access is to a valid memory location, there's no segmentation fault generated, and the change to memory goes through. When the program writes to array, it finds valid, writable memory at that location—namely, one of the elements in the target array x. (Remember that on x86 machines, the stack grows downwards, towards lower-valued addresses, so array[0] is the end of the stack. On other architectures, if the stack grows upwards, we'd need to write to the other end of array.)
As you might expect with memory corruption, this is exploitable. In 2010, Rafal Wojtczuk, a researcher at Invisible Things Lab, discovered that this sort of confusion could be used in a privilege-escalation exploit against the X server (PDF). A client can cause the X server to exhaust most of its memory, request a shared-memory region that gets mapped right past the stack, and then trigger a recursive function in the X server. As the associated blog post puts it, it "exploits a bug in... well, actually it doesn't exploit any concrete bug, which makes it so much more interesting."
How can we defend against this? The X server vulnerability (CVE-2010-2240) relied on the stack running right up against mapped pages, so the straightforward solution was to ensure that an unmapped guard page is always just past the end of the stack. But this doesn't help for more complicated cases that span more than a single page—like my example above, or even a less-contrived function with a 5000-byte string buffer.
It turns out that GCC has an option, -fstack-check, that inserts code to check for this problem. If I recompile my program with -fstack-check, I get a segmentation fault. It appears that gcc has inserted code to step the stack down one page at a time, running a logical-OR with zero at each point, which doesn't affect any value on the stack but forces a memory access. Here's the disassembly of that section of code, from GDB:
0x0000000000400621 <+139>: mov %rsp,%rcx
0x0000000000400624 <+142>: sub %rdx,%rcx
0x0000000000400627 <+145>: cmp %rcx,%rsp
0x000000000040062a <+148>: je 0x40063a <clobber+164>
0x000000000040062c <+150>: sub $0x1000,%rsp
=> 0x0000000000400633 <+157>: orq $0x0,(%rsp)
0x0000000000400638 <+162>: jmp 0x400627 <clobber+145>
The size of my variable-length array has already been computed in %rdx. GCC has inserted code to step through the stack one page ($0x1000 bytes) at a time, in a loop. At each step, it ORs the value at the stack pointer with zero, which doesn't change any data but forces a read and write of memory.
Why isn't this the default, like other safety mechanisms like -fstack-protector? I don't know for sure. Part of the answer could be performance, since each somewhat large stack allocation will result in this code being run—with overhead linear in the size of the allocation, instead of just a single change to the stack pointer—but I'm not sure if anyone expects large stack allocations to be performant. Another answer could be lack of interest, since GCC doesn't even enable it by default when compiling Ada code, even though the Ada language requires that stack overflows and segmentation faults be distinct errors.
This technique is common on Windows. Microsoft's rationale for stack checking is less about preventing unexpected changes to memory and more about making sure the stack is actually in place. Windows places a single guard page past the end of the stack, which is reserved in the memory map, but causes a fault when accessed. The kernel takes this as an indication that the process needs more stack space, and will allocate more physical pages, provided that resource limits allow it and there's enough free RAM. Then it moves the guard page past the new end of the stack. So, if your program has an object that is even slightly more than the page size (e.g., a char buffer[5000]), it's important that the guard page get touched, instead of skipped over. (Linux also uses a similar mechanism, but as far as I can tell, the entire possible stack region is treated as guard pages, so the problem of skipping over a single guard page doesn't arise.)
Rust is looking at moving away from the __morestack approach to this approach, under the name of stack probes (the term "probe" is also used in GCC documentation). Apparently the right name for this technique is a bit of a question. "Stack checking," as Microsoft and GCC call it, is a somewhat generic name, and I imagine many developers would interpret it as referring to the more typical direction of stack protection. Indeed, I was very surprised to see that the first C program above "worked", clobbering memory, even with -fstack-protector. It's common to see stack-smashing attacks, where an out-of-bounds pointer overwrites something valuable on the stack, and that's what -fstack-protector (StackGuard, which uses stack canaries) protects against. But it's not as common to see the inverse problem, where an out-of-bounds stack pointer overwrite something elsewhere in memory, which can be just as unsafe and just as much of a security risk.
Thanks to Nelson Elhage, Liz Denys, Alex Dehnert, and Asheesh Laroia for feedback on drafts of this post.
