[SOUND] Before we can talk about how buffer overflows work, we need to review some details about how you run a program on a modern computer. For understanding buffer overflows, we're particularly interested in how programs are laid out in memory. We will consider where the program code and it's data are located in memory. We will look at the call stack and how it stores arguments and local variables of functions when they are called. We will look at some of the metadata that is stored amongst this program data. To make it easier for the compiler to generate code that can be used in different circumstances. For example, no matter which function calls which other function. In our discussion, we focus on the Linux operating system process model running on an Intel x86, 32, or 64 bit processor. While the details differ for different operating systems and architectures, the concepts that we will consider are very similar. All programs are stored in memory. A program, when it begins running is called a process. And that process is given memory by the operating system in order to run. Here we depict the processes adverse space. At the bottom is address zero, the lowest address. And at the top is the address at four gigabytes, which is the highest address on a 32-bit system. The process's view of memory is that it owns all of it. As far as it can tell, it's the only programming running on a system. In reality, these are virtual addresses. That the operating system and processor map to actual physical addresses for the memory on the machine. At the bottom of the address space is the Text segment or code. Here we see some x86 instructions that might make up the code of our program. Just above the text segment is the data segment and it has two parts. The first is the initialized data area. So here we see variable y that's initialized to ten. Above that is the uninitialized data area. Here, the variable x is not initialized at all. However, note that global variables not initialized by the program are assured by the process model to be zero. This is not true of uninitialized local variables, as we'll see later. All of this data is known at compile time. So the compiler can determine where it goes and can specify as much in the executable. At the top of the address space comes the command line arguments and the environment variables. And these are set when the process starts. Just below them, is the stack. The stack is what holds local variables, along with metadata that the program uses to call and return from functions. Above the data segment is the heap. This is the area that malloc manages. All of this data is organized and managed at runtime. That is, how it behaves depends on what the program does. What it interacts with, what input files it reads or writes and so on. Now we've turned the picture on its side so the lowest address is to the left and the highest address is to the right. And we'll use this orientation for most of the rest of the slides. Here again, we see the stack and the heap depicted and we also show the direction that they grow. As more memory is needed in the heap, it grows towards the higher addresses. Where as more memory is needed for the stack, is grows downward toward the lower address. While the program is running, it maintains a stack pointer which indicates the top of the stack. When the program issues a push instruction it will move the stack pointer after pushing the value. [SOUND] Now, suppose that after running for a while, the function that had pushed these values returns. In that case we expect that the function will pop a large portion of the stack off removing all of its local variables and arguments. We'll see how this works exactly in a minute. The compiler emits the instructions that adjusts the stack at run-time. Likewise code, that is the implementation of malloc, keeps track of the heap. The memory that the heap uses is apportioned by the OS, but the individual data that's stored inside of the heap is managed by malloc. For now we're going to focus on the stack because that's our target of the first attack that we'll consider. The next question is, how does a program use the stack while it is running? As mentioned earlier, the stack is used to support calling and returning from functions. We'll now look at the details. In particular, we'll look at what data we need to store and where we'll put it when calling a function. We'll also look at what has to happen when a function returns. That is, what data needs to be restored and where to get it from. Now let's consider the basic stack layout. Here we see a simple function func, that takes three arguments, arg1, arg2, and arg3, and has two local variables, loc1 and loc2. Below we see the depiction of the memory of the process. The highest addresses are to the right as usual. And we see a depiction of the callers data, that is the caller of this function. When the caller goes to call this function it's going to push the arguments in reverse order of the code. So remember, the stack grows from the right to the left that is, the top addresses to the bottom addresses. So we see then that arg3 comes first, then arg2, then arg1, that is, the opposite order of the program. Now, the local variables of the function are accessed, on the stack as well. And they are stored in the order that they appear in the program text. That is, first loc1, and then loc2. There are a couple bits of information that are stored in between, and we'll see what these are in a moment. Now suppose the compiler is generating code to access these variables. So here we show that within the function it wants to increase the value of loc2 by one. How will it do this? Well, in order to do it, it needs to know where loc2 is stored on the stack. Suppose, for argument's sake, that it's stored at this particular address. How will the program know that? Well if we think about it, if this function could be called from many different places in the program. The actual address of loc2 could differ depending on who called the function. Therefore, the compiler cannot know this address at compile time, and it's going to need to do something else. Fortunately, the compiler always know the relative address of this variable. That is, it's always eight bytes before the question marks here on the stack. Stepping back, we can think of all of this stuff that's highlighted in blue as the stack frame for the function. The arguments and the local variables plus these extra question marks that we'll get to in a minute. Now because we want to know how to locate local variables and for that matter how to locate arguments. We need a reference point within the stack frame. We'll call that the frame pointer. Typically compilers store the frame pointer in the EBP register. Therefore, the compiler knows that no matter where this function is called from. It will always be eight bytes distant from the current value of the frame pointer. Now let's see how we implement returning from functions. Here we see main which is called the function func we were just looking at. And we see the stack frame for func, here at the bottom of the slide. Here's the caller's data for main that we've saved. Now, when we called func, main was using the frame pointer just as func is to access its own local variables. When we return from func, main is going to want to use the same frame pointer that it had before. So that when it goes to access its variables, it's going to the right addresses. So the question is, how do we save and restore the frame pointer so that this works properly? Well let's think about how main is going to call func in the first place. What it will do is it will push it's three arguments, arg3, arg2, arg1, here hey 10 minus 3. It'll push some other data that we'll see in a minute. At this point, the stack frame pointer is right here. Now what we can do is we can save main's frame pointer right on the stack. At this point, we can update the frame pointer to be the current stack pointer. And now when the func function starts to run, it will push its local variables after the current stack pointer. And here we are from where we started. The next question is, how do we resume at the same place that we were in, in main when we called func. Here's what's going on. As main is running the instruction pointer, eip, is moving through the different instructions that implement main. Now it goes to call func. When it goes to call it. The fr, the instruction pointer is going to move up and start executing these different instructions. So what we want is to resume back to where we were when we called the function. Well, we can play the same trick that we did with the frame pointer. We can store the instruction pointer just before calling the function on the stack. Now, when we go to return. We just have to set the instruction pointer to four off of the current frame pointer in the call E. In summary, when calling a function, we push arguments onto the stack in reverse order. Then we push the return address, and then we jump to the functions address. Within the called function, we pushed the old frame pointer onto the stack. We set the new frame pointer value to be were the stack is right now. And then push the local variables in order. Finally, to return, we set the previous stack frame by restoring the frame pointer. And then we simply jump back to the instruction pointer that we saved on the stack. Which is four more than the reset stack pointer which was set to be the previous frame pointer.
