Karl (supersat) wrote in supersat_tech,

Stack layout and buffer overflows

Who decided the x86 should grow down and what was the rationale behind it? Efficiency? Unless I'm mistaken, if the stack grew up, buffer overflows would be less dangerous than they are today.

Most computers use stacks to keep track of variables and function calls. For example, function A might call function B, and function B might call function C. When function C is done, control goes back to function B. When function B is done, control goes back to function A. It's called a stack because the first item in the stack is the last item out of the stack. You can imagine a set of plates labeled A, B, and C. A is placed down first, then B on top of it, and C on top of B. You take C off first, then B, then A.

Stacks are also used to keep track of local variables only used inside a function and variables passed to that function. They're essentially plopped on each plate in the stack so when the plate is removed, the variables no longer exist in memory. This is much more efficient than trying to deal with those variables separately.

Stacks can be organized in two ways: they can grow up, or they can grow down. In stacks that grow up, each successive "plate" on the stack is stored at the next highest memory location. For example if a stack contained A, B, and C, A would be at location 0, B would be at location 1, and C would be at location 2. In a stack that grows down, each successive item is places just below the last item on the stack. In our example, C would be at location 5, B would be at location 6, and A would be at location 7. (By the way, when the location reaches 0 and another item is attempted to be put on the stack, a stack overflow error occurs.) The x86 stack grows down.

Here's why that's a problem. The stack is laid out as such:
[ Local Variables ] [ Previous stack pointer ] [ Return address ] [ Variables passed to the function ]

Local variables can include buffers, which are sets of bytes set aside to store things in. Usually, text is stored in buffers. The problem is that there's no indication of where the buffer ends. It's possible to write to the beginning of the buffer and extend past the end. If you go to far, you'll write over the return address. This is where stuff gets tricky.

It's possible to write instruction code to a buffer by passing nonsense text to a program. If the program is careless, it can allow you to write over the return address in such a way that it points to the code in the buffer. When the function exits, control will jump back to code inside the buffer, causing all sorts of nasty things to happen. You now know the basis of many exploits out there.

If the stack grew up, it'd be laid out as such:
[ Variables passed to the function ] [ Return Address ] [ Previous stack pointer ] [ Local variables ]

Local variables wouldn't be able to corrupt the return address for two reasons:

1. In practice, buffers are never sent to functions. Instead, pointers to where the buffers are in memory are passed to the function.
2. The compiler would only put the proper amount of bytes on the stack. Even if it put more than the proper number of bytes on the stack, the return address would go right on top of it. It doesn't matter where the return address is in memory as long as the called function knows how far away from the current stack position it is.
  • Post a new comment


    default userpic