Buffer Overflow Part 1: Introduction to Stack

I’ve been learning about Buffer Overflow for quite some time and I thought it’d be nice to share my learnings with others and this is the reason for this Tutorial.

Who is this Tutorial for?
This tutorial is for beginners who have little programming experience and wants to know what BOF is and how exactly does it work.

What will we learn?

We’ll look at a very simple demonstration of how we can alter the flow of a program with correct knowledge of the alignment of a stack and a precisely formed malicious input for a vulnerable function with a program.

Prerequisite:
Let’s prepare our guns before we dive into a battle.

Stack
A nerdy definition of a stack from Wikipedia says,

“In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out).”

Too Bookish

Basically, all stack does is to store elements and retrieve them in a very certain order. Only the most recent element inserted (or pushed) on to a stack can be retrieved (or popped). The position of this most recently pushed element is also called the “top” of the stack. The working of a simple stack is shown in the diagram below.

LIFO Stack
LIFO Stack

Consider we’re working in a 64-bit environment i.e. each of our address is an 8-byte address. Also, consider that the stack starts at a memory address of 0x1000(“0x” means hexadecimal). The image shows how 64-bit integer would be pushed on to the stack and how the location of “top” changes as the stack grows. The memory address painted in red represents the “top” of the stack before the push operation is carried out. Figure 1 shows only one element (integer value 1) resides at the top of the stack at memory address 0x1000. Since it is the only element in the stack, it is also the top of the stack. As we’re using 64-bit integers, it’d take 64 bits or 8 bytes to store it. So we have memory locations 0x1000 to 0x1007 holding our first integer. In figure 2, the second element (integer value 2) has been pushed to stack at memory location 0x1008, also making it the top of the stack. This continues until figure 5 when we have memory location 0x1020 as the top of the stack holding an integer value of 5.

Note: As I’ve already mentioned, the state of “top” in these figures is marked before the push operation is conducted. So, in figure 1 0x1000 is the top before the second element is pushed.

The counterpart of push operation can be seen in the image below. It’s called the “Pop” operation. It deletes the last top element from the stack and decreased the value of “top” to point to the next element in the stack.

LIFO Stack HighlightedLIFO Stack Highlighted
LIFO Stack Highlighted

A program always maintains a stack for its functioning. If you’re a coder, you’d have heard at least once that a stack is needed for making function calls and that’s exactly what we’re going to see in the coming part of this tutorial.

I’ll continue to write this tutorial on Buffer Overflow as soon as I get time. If you have any questions so far, please leave them below in the comments and I’ll try to answer them all, as quickly as possible. I encourage you to put some comments, either good or bad. Let me know if you liked the way I write, it’ll encourage me to write further. If you didn’t like the way I write, let me know about it too. One learns the best from his own mistakes. Your valuable comments are heartily welcome.

Leave a Reply