Understanding the Stack - A Precusor to exploiting Buffer Overflow

Alright,

So I was trying to exploit buffer overflow in a simple C program and it turns out that understanding of Stack is one of the most important things you should have before you are able to make any meaningful strides towards your goal.

There are a number of lecture notes out there which do a good job at explaining things, but somehow they fail to give the big picture. So here is the big picture as per my understanding, I made it myself (you are free to use it if you want to !)

In this post, I will discuss each of these three diagrams as per my understanding and hopefully someone might be able to benefit from this post!

Figure 1 (orange) on the left demonstrates how memory allocation is done for a program when it is loaded into the memory.

Let us assume that we have 4 GB of RAM in the system on a 32 bit machine. We will refer to RAM as memory hence forth. In a modern operating systems , each program that is loaded into the memory assumes that the entire memory ( 4 GB in this case) belongs to the process. This is how it appears from the point of view of the program. And this is how we will see the memory for the purpose of our discussion in this post.

Note - ( For those who are wondering how this works - In a modern OS, the address of a memory location ,which is a virtual address in the range 0x00000000 to 0xffffffff, goes through an address translation to map to a physical address. This mapping is done using Paging and Segmentation mechanisms. You can read more about this in a operating systems course or online, but for our purpose you don't need to care about this).

Now,  the components of a program that is loaded into the memory are assigned various sections in the memory. The Code (also called Text) of the program is loaded into the Text section. The size of this section is fixed and does not change during the execution of the program. 

The initialized Global variables and Static variables are placed into the Data section of the memory.

The uninitialized global variables and uninitialized static local variables are placed in the BSS section of the memory. If you are wondering why this section is called BSS, then let me tell you that the full form of BSS is Block Started by Symbol and it is called so for historical reasons, which you can ignore.

The heap is the area of the memory which is used to assign memory dynamically at run time. Functions like Malloc(), Realloc()  in C are used to allocate space in this section of the memory. Heap grows upwards, towards higher addresses as shown in the Figure 1.

The Stack section starts from the highest address in the memory and grows downwards towards lower addresses. The variables local to a function and arguments to another function are stored on the stack.

A Stack is a LIFO structure, which means - Last in First Out. The first element that is pushed on the stack is the last one to be popped off the stack.

Why are Stack and Heap placed at the opposite ends of the memory ? Well, in ancient times, when memory used to be small, then stack and heap would often run out of space and touch the other section's boundary. To avoid that situation, this placement was adopted and it is still being used.

This completes the high level view of memory. At this stage we move forward and focus on the stack alone.

Now, each function that has not yet returned, will have a stack frame on the Stack.  In the below diagram, the point at which the last() function is called and while it is being executed, at this point the Figure 2 above (green), shows the state of the stack while the function last() is being executed.

To return to the original function and continue executing normally, it is natural that the EIP (Extended Instruction pointer register, which points to the next instruction to be executed at any point of time) must point to the line next to the line in which the function (which has just returned) was called.

So, it is natural that we save the contents of EIP on the stack before calling any functions.

Also to work with a stack, we need two very important Registers 

1.  EBP ( Extended Base pointer)

2.  ESP  (Extended Stack Pointer)

Base pointer stores the address of base of the stack frame. Stack pointer always points to the top of the stack. ( Actually, this is the location with the lowest most address on the stack). 

Another important register is EIP ( Extended Instruction pointer), which always points to the next instruction to be executed. EIP is always the last thing to be saved on the stack frame of a given function, before it transfer control to another function. This is done so that the called function is later able to return the control to calling function after it is done executing. This transfer of control is done by loading the EIP with the old value (which pointed to next line of code in the calling function) and setting the ESP and EBP to the old values, so that the calling function can continue normal execution.

Thus EIP, ESP and EBP make it possible for a function to call another function and then continue normal execution after the called function has returned. All this is achieved with the help of a Stack frame.

As you can see in the above diagram, EBP and ESP point to the base and top of the stack frame of currently executing function. All other stack frames save EBP and EIP values before transferring control to another function.

Now, we move onto the figure 3 (blue).

The most important things about this diagram are the following:

1. The first item that is pushed on the stack frame of a function is EBP of the previous function's stack frame. This is always present on the stack frame.

2. Then there may or may not be some space (which is multiple of 4 bytes) to store return values.

3. The local variables are always in the order in which they are declared ( local var 1, local var 2). These variables are always present on the stack.

4. There may or may not be any saved registers and temporaries.

5.  The arguments for the next function call are saved next in the reverse order (arg 2, arg 1). These arguments are always present if the next function is expecting arguments.

6. The last thing on the stack is EIP, which is the return address ie. The address of the next line of code to be executed after the called function has returned.

The important thing here is to realized that - although, the local variable and arguments are present on the stack in the order in which they are specified in the diagram, the stack may have other temporary values (say return values or other values generated during function execution) and as such when you compare the stack frame of two programs you can expect the local variables and arguments to be floating between the EBP and ESP in the order in which they are specified in the diagram.

The purpose of buffer overflow attack, is to overwrite this value on the stack, so that when the called function returns, it loads the address of the attacker's code and executes it. For example - the local variable 1 of the next stack frame may overflow and thus overwrite the EBP and then EIP (as memory gets filled from lower to higher addresses).

I will connect this post with another posts on Basic assembly language tutorial and a Buffer Overflow tutorial.

Criticism and suggestions are welcome!

Thanks

Vinay