Menu Home

How to overflow a stack

Let’s get the obvious out of the way: You don’t actually want to overflow a stack. But if, like me, you get most of your knowledge these days from stackoverflow.com, you may have wondered about the provenance of that website’s name. While I can’t tell you why they called it Stack Overflow per se, I can tell you what I know about stacks and how to royally screw up your day through a few lines of terrible code.

Stack versus heap

Before we get to the issue of overflow, we need to nail down the concept of a stack. I currently teach Python for my day job, so we’re blessed by having memory management hidden from us. And that means no stack (and only a private heap, at least in the CPython implementation). So beware: The concept of stack and heap may not exist or may be implemented differently in your favorite programming language!

Warnings aside, we can get a pretty good general idea of stack and heap anyway. Both the stack and the heap are constructs in computer memory (RAM specifically). We can use their respective names to get some intuition for how they function.

The stack: imagine a pile of plates

A stack is orderly; it’s LIFO, to be exact. That is, last in, first out. Imagine stacking a pile of dishes for Thanksgiving dinner: unless you’re really gutsy, if you want a plate for a slice of grandma’s apple pie, you’re going to grab the one from the top of the stack. That is, the last plate that was put on the stack is the first one to be taken out to be used. A stack is a type of data structure that has push (add to the stack) and pop (remove from the top of the stack) methods.

Every thread that you’re running makes its own stack. As a function creates new variables, for example, it adds them to the stack. The stack is used for local variables because things don’t live very long here: They’re used, and then popped off the stack. Once a variable goes out of scope, it’s popped off the stack and that memory can now be used by something else.

The size of the stack is preallocated and you can’t put any old sized thing on the stack: variables are restricted in how big they can be. Remembering that a stack has a pre-determined size that doesn’t grow during execution is very important for when we get to overflowing the stack! But first, let’s define the heap.

The heap: imagine the pile of clothes currently littering your bedroom floor

The heap is also a place in RAM memory. But whereas the stack had a preallocated size that can’t get bigger, the heap can get bigger during runtime. If you need more space for execution, whatever does your memory management can make the heap bigger (up to the physical limitations of your RAM; the heap is flexible, but it’s not magic). And whereas the stack was per thread, the heap is per process.

If you’ve made the poor life decision to program in C or C++, you have to do your own memory management and garbage collection, so remember to clean up after yourself (de-allocate those pointers)!

The heap doesn’t have a push/pop structure, and you can add to the heap in a somewhat haphazard way. Global variables live here. You shouldn’t go too crazy in fragmenting memory allocation to the heap though as that’ll make it take longer to find the things you’re looking for when you need them. While the heap does have some benefits over the stack (for one, you can add dynamically sized variables to it), that doesn’t come for free. The heap is slower to allocate and it’ll take you longer to get your stuff from the heap because memory doesn’t have to be contiguous.

How to ruin your day, via the stack and via the heap

Don’t worry, you can eff up both a stack and a heap! While you may be familiar with the term stack overflow, there’s also a related heap concept: memory leakage.

You’ll get a stack overflow if you try adding more to the stack than it has room for. Remember, you’ll preallocate space to your stack before your program runs. If you then call a recursive function, every recursive call will add the function call and local variables to the stack. Try to make too many such recursive calls and you’ll run out of stack space: then, a stack overflow!

You can also ruin your day via a memory leak in your heap. If you do a bad job managing your memory, you may forgot to deallocate some pointers to objects that you’re no longer using. If you keep this up, you’ll have a lot of memory that the garbage collector can’t reclaim for other uses (because your pointers are still pointing to it), but that you’re not actually using. Do this enough, and you’ll run out of heap space!

Summary

So there you have it, there are multiple ways to ruin your day, especially if you’re using a programming language that requires you to do your own memory management.

  • A stack and a heap are both places in RAM memory
  • A stack is a LIFO structure (last in, first out)
  • A heap can be allocated/deallocated at whim from anywhere
  • Add too much to a stack and you have a stack overflow
  • Forget to deallocate from the heap and add too much to it and you’ve got yourself a memory leak

Categories: Uncategorized

Lara K

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: