Inversed Data Direction on the Stack

Question

As I remember from my micro controller course, the stack is at the end of the memory, while at the begin are some interrupt pointers, program code and later data. Since the stack is at the end of the memory it grows in the direction to smaller addresses. And at every function call a new stack frame is pushed onto it. Which contains the following items, among others, in the following direction (from small address to high address)

local variables
return pointer
parameters

And as far as I know most buffer overflows, try to overflow the available space in a local variable to overwrite for example the return pointer.

So one thought of mine was, that one fundamental problem is, that data on the stack is addressed the same way, then else where in the memory. If a pointer to a buffer points to the highest address of the buffer, and the buffer's last element has the smallest address (hence in reverse order), wouldn't that help?

So my questions are:

• Is this a valid thought?
• Has there been similar thoughts?
• What are the drawbacks thereof?

Answer 1

There are some architectures which use a "growing up" stack. Generally speaking, this makes porting of operating systems a bit harder; it does not seem to be that much of a gain security-wise. The convention of making stacks grow down comes from the era before the advent of MMU (without MMU, RAM is a block; the stack grows down from the end of the block, the data elements are allocated upwards, and memory is exhausted when heap and stack meet).

In the case of buffer overflows, it so happens, empirically, that most occur "on high addresses": the buffer has size 1000 but the buggy code tries to write into the 1001th, 1002nd... slots. This is related to how most programmer implement a loop: when they want to loop over the 1000 elements of an array, they loop up, with index from 0 to 999, instead of looping from 999 down to 0. For the machine, both are equivalent (in fact, in some old 8-bit computers, looping down was slightly faster); but programmers are humans with human habits, and this includes counting up instead of down, when given the choice.

This matters with stack direction because with a "downward" stack, the juicy slots that the attacker wants to rewrite (in particular the return address) are in range of "high" overflows, which are more common than "low" overflows. However, "low" overflows (also called "underruns": code tries to access slots -1, -2...) are just infrequent, not unheard of. Reversing the stack direction just swaps the roles: now, low overflow become critical.

Also, as @Polynomial explains, low overflows can also be interesting. The function return address is just one among many slots that the attacker would like to overwrite.

In my opinion, the main problem with a buffer overflow is that it occurred: the code does nonsensical things, and is allowed to proceed unabated. It is like a rhinoceros evaded from a zoo and rampaging through the town centre; reversing the stack is like: "let's move the whole town, so that the rhinoceros is more likely to run toward countryside, where it will make less damage". It is hardly a "reasonable" safety mechanism. It would be a much better idea to concentrate on not letting the rhinoceros go loose.

Answer 2

The main problem with having the stack grow up is that it either has to sit at the start of memory and have a forced upper size limit, or sit at the top of memory and have a forced location. Both of these situations limit maximum memory utilisation. If both the stack and heap grow towards each other from opposite ends, you only run out of memory when there is literally none left. In other configurations you may run out of stack or heap despite having free memory.

The "backwards stack" idea has been thrown around for quite a while now, and is generally not seen as a solid solution. For a start, you're going to run into problems if you're altering stack buffers that are in previous frames. This initially doesn't seem like it would be common, but consider that you allocate buffers for many functions before you pass them:

void foo(char* src)
{
    char dest[20];     // local allocated within frame of foo
    strcpy(dest, src); // new stack frame, so return ptr AFTER dest
    // blah blah rest of code...
    if (dest[0] == 'X')
        printf("First char is X\n");
}

Notice that the stack frame for strcpy will sit numerically above the stack frame for foo. In a typical system, strcpy would write past the buffer, over the return pointer of foo, leading to control of the instruction pointer after foo returns. With a backwards stack, strcpy would write up, through the end of foo's stack frame, into the bottom of strcpy's stack frame, leading to an overwrite of the return address of strcpy, and again giving control of the instruction pointer.

A solution that is considered by many to be quite secure is to use an architecture that has one stack for locals and parameters (the data stack), and another for stack frames and return pointers (the control stack). This isolation helps ensure that return pointers cannot be casually overwritten when a local buffer is overflowed. It again has the issues with memory management, though only one stack has to have a fixed maximum size - the other can grow into the heap.

Of course, this architecture also isn't completely robust from a security standpoint. Consider the following:

int int_sorter( const void *val_a, const void *val_b )
{
    // this code isn't important here
    int first = *(int*)val_a;
    int second = *(int*)val_b;
    if ( first == second )
        return 0;
    else return (first < second) ? -1 : 1;
}

void bar(char* message, int (*sorter)(const void*,const void*))
{
    int array[10];
    char dest[32];
    // do something with array
    // ...
    strcpy(dest, message);
    qsort(array, 10, sizeof( int ), sorter);
}

In this case, assuming a pair of classic downward-growing stacks in a dual-stacked architecture, message overflows dest on the data stack, copying over the sorter function pointer that was pushed as the second parameter to bar. The call to strcpy returns as normal (the control stack is intact) but then the call to qsort contains an instruction to jump to the sorter function, again leading to control over the instruction pointer.

At the end of the day, you're not going to find a total solution to the problem. The best you can do is use good coding practices (or teach your devs to do so), and enable protections such as ASLR (a.k.a. PIE), DEP/NX, stack canaries, etc.