# The Stack (theory)

(This is part of my series on program vulnerability exploitation.)

Most of the techniques we will see here manipulate the program stack in some way or other, so it is imperative to have a good understanding of it, and we will describe it in some length. Again, the book by Bryant and O’Hallaron is an excellent reference for these topics.

## 1. What is the stack?

A common feature of high-level languages such as C is that they allow the programmer to define functions, such as

int factorial(int n)
{
int res = 1;
for (int i=2; i<=n; i++) {
res *= i;
}
return res;
}


which are bits of code that may be used several times during the execution of the program. For several reasons, it is important that each function have some space for itself where it will store its own data (such as the variables i and res here), which will be allocated when the function is called, and freed when it returns. In many computer platforms, and especially in the x86/Linux combination which interests us here, this scheme is implemented using a stack (generally referred to as the stack, or sometimes the call stack or the execution stack).

Recall that a stack is a data structure which operates in a last-in-first-out manner: data enters the stack from the top (we say it is pushed on the stack) and exits it also from the top (we say it is popped from the stack). One can imagine a stack of plates: you put plates on the stack on the top, and take them from the top also, which means that when you take a plate, it will always be the one which was put most recently (hence, last-in-first-out). This makes sense for our purpose: when a function is called, we give it a chunk of memory space, called its stack frame, to store its data on, and push it on our stack. Then when the function returns, its stack frame is popped from the stack and the stack is back to how it was before the function was called. If, during the execution of the function, a new function is called, the frame for that function will be pushed (when the new function is called) and popped (when it returns) before our original function returns, and we can continue like that as long as we have memory available.

Consider this program:

#include <stdio.h>

{
return a+b;
}

int mult(int a, int b)
{
int prod = 0;
for (int i=0; i<a; i++) {
}
return prod;
}

int main(void)
{
printf("%d\n", mult(2, 3));
}


During a call to the function add(), the stack will look like this:

|                 |
+-----------------+
+-----------------+
| frame of mult() |
+-----------------+
| frame of main() |
+-----------------+
|                 |


We now turn to what's inside a stack frame.

## 2. Stack frame structure

A function normally doesn't get to do whatever it wants with its stack frame, or at least not with all of it. There are numerous conventions in place so that the function plays nicely with both the function who called it, and the functions it itself will call. This is, of course, so that functions written by different programmers/compilers will be able to interact nicely. Mostly, those conventions have to do with information that functions pass to each other.

### 2.1. Parameters

The most obvious ones are the parameters of a function call, passed by the caller to the callee. Typically, the caller will simply store the parameters in a specified location at the top of its own stack frame, and the callee will grab them from there (thus the callee will read, but normally not write, on the stack frame of the caller). In our example, when mult() calls add(), it looks like this (lines of equal signs delimit stack frames, and lines of hyphens delimit where variables are stored, typically one line will be 4 bytes):

|                | frame of add()
+================+
|                |
+----------------+
| prod           | frame of mult()
+----------------+
| b              |
+----------------+
|                |
|                |
|                |
+================+
|                | frame of main()


So mult() will store the arguments to be passed to add() near the top of its stack frame. Reading them in the order in which they are written in the code, they are stored from top to bottom. There is also a space of 4 bytes at the very top of the stack frame, it's the most important one and we turn to it now.