56

Every once in a while (when I think out loud and people overhear me) I am forced to explain what a buffer overflow is. Because I can't really think of a good metaphor, I end up spending about 10 minutes explaining how (vulnerable) programs work and memory allocation, and then have about 2 sentences on the actual exploit ("so a buffer overflow fills the buffer up with nonsense and overwrites the pointer to point to whatever I want it to point to"). By this time, most people have become suicidal... What is a good way to explain a buffer overflow to laymen? If possible, please include an "overflow" component, but also at least a lead-in to why this means the attacker can get what he wants. Remember, people of average (and below average) intelligence should be able to get an idea of what I am talking about, so while you should absolutely feel free (encouraged, actually) to explain what each part of your metaphor (analogy?) represents, don't rely on any super-technical descriptions...

PS, a related question explaining in technical terms what the buffer overflow does: What is a buffer overflow?

KnightOfNi
  • 2,247
  • 3
  • 18
  • 23
  • 2
    10 pounds of sugar in a 5 pound bag. – Elsporko Mar 24 '14 at 21:16
  • 1
    @Elsporko See my discussion with tylerl, I'm looking for something that at least provides an idea of why on earth the overflow component allows the attacker to get what they want. Since I didn't make this very clear, I have gotten several people who provided similar examples, so I will edit my question accordingly. Thanks for your contribution though! – KnightOfNi Mar 25 '14 at 21:27

7 Answers7

124

Imagine you have a list of people you owe money to.

Name | Amount owing

Also, when you write over something, it replaces what was there before instead of writing over the top of it. (The analogy breaks down a bit here, because you pens don't work that way in real life, but computer memory does)

You pay someone a $500 deposit on a $5000 car, so you now owe them $4500. They tell you their name is John Smith. You write the amount (4500) and the name (John Smith) in the table. Your table now looks like this:

John Smith | 4500

Later your table reminds you to pay them back. You pay the $4500 (plus interest) and erase it from the table, so now your table is blank again.

Then you get a $1000 loan from someone else. They tell you their name is "John Smithxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx9999999999". You write the amount (1000) and the name (John Smithxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx9999999999) in your table. Your table now looks like this:

John Smithxxxxxxxxxxxxxxxxxxxxxxx|x99999999990

(the last 0 from 1000 was not written over. This is unimportant.)

When writing the name, you didn't stop when you got to the end of the "name" column, and kept writing into the "amount owing" column! This is a buffer overflow.

Later, your table reminds you that you owe $99999999990 to John Smithxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx. You find him again and pay him almost 100 billion dollars.

user253751
  • 3,885
  • 3
  • 19
  • 15
  • 6
    An excellent answer; I may use this next time I have to present to non-techies. – paj28 Mar 22 '14 at 16:00
  • The one problem I have with this explanation is that most people write left-to-right; that is, the `Amount Owing` column would be written _after_ the `Name` column, so should show the expected amount (`$1000`). You'd probably be better off having the entry for `Name` write to the next row, so the current-row amount could be safely written (note that you wouldn't even need huge amounts here - the person could just be in the table twice). – Clockwork-Muse Mar 25 '14 at 03:27
  • 3
    I see. I would personally prefer to explain it as "you always write the amount you owe first (that would be the preexisting value) and only read the number most recently written into the space." Maybe it's just how my mind works, but that seems a bit clearer to me than magic correcting fluid (perhaps because the rest of the analogy is so realistic...) – KnightOfNi Mar 26 '14 at 16:23
  • If you wrote both in the same space you would get something like this: http://puu.sh/7KTwk.png . How would you know whether to read 9's or 0's? – user253751 Mar 27 '14 at 00:37
  • "You only read the number most recently written into the space." I frequently write over things I had previously written without bothering to erase them, and I am always able to clearly see which thing I wrote last (usually, I just go over new letters several times to make them the obvious choice). This is not only more realistic as regards real life, but it is also closer to what a computer actually does (it doesn't "erase" the data, it just writes right over it). – KnightOfNi Mar 27 '14 at 21:29
  • 3
    `you have a weird pen with built-in correction fluid` sort of spoils the analogy for me - I know what you're saying but as it doesn't exist in real life it would sound odd to someone I think. – SilverlightFox Mar 28 '14 at 16:36
  • @SilverlightFox you could cut off a few 9's, so you end up with $999...9991000 and no overlapping digits. – user253751 Aug 16 '14 at 13:28
  • 2
    I think @immibis is just saying that if you overwrite something with normal writing, when you go to read it, you can usually tell that new writing has corrupted earlier writing. When you overwrite something in computer memory, there typically isn't any such evidence. – arya Sep 17 '17 at 21:53
18

The idea of using up more space than you were given, and therefore spilling over into a different field is simple enough to visualize. But it probably isn't clear how this can lead to a bad guy running his own code.

This is pretty simple to explain if you understand it well enough. Just make sure you hit on the important background. More or less in this order:

  • The "stack" is a place where you can store temporary information. The "stack pointer" determines where the end of the stack is. When a function runs, it moves the stack pointer to give itself memory to work with, and when it's done, it moves the pointer back where it found it.

  • The stack grows backwards. So to give yourself 100 bytes on the stack, you subtract 100 from the stack pointer rather than adding it. If the previous function's stack started at 1000 and I want 100 bytes, then my stack starts at 900.

  • This means that if you use more space than you gave yourself, you won't just continue writing out into empty space, you'll actually start overwriting previous stack values.

  • When my function starts, the very top value left on the stack for me by the previous function is the return address where I should go when my function is done.

  • This means that if my function overruns its stack, the very first thing that it's going to overwrite is the return address. If the attacker is careful about what he fills the stack with, he can specify whatever return address he wants.

  • When my function exists, whatever code is at that return address is what will get executed next.

Simple Example

In Smashing the Stack for Fun and Profit, where this technique was originally described, the most simple and straight-forward technique was introduced. Imagine the function reads your name and then returns. So your stack looks like this:

Stack Pointer                                      Prev. Stack Ptr
+----------------------------------+--------------+................
| Your Name Here                   | Return Addr  |  Old stack ...
+----------------------------------+--------------+................

But the bad guy makes his name long enough to overflow the space. And not only that, instead of typing a real name, he types in some Evil Code, some padding, and the address of that Evil Code.

+----------------------------------+--------------+................
| [ Evil Code ]xxxxxxxxxxxxxxxxxxxxxxEvil Address |  Old stack ...
+----------------------------------+--------------+................
  ▲──────────────────────────────────┘

Now instead of returning back to the previous caller, you jump straight to the [Evil Code]. Now you're running his code instead of your program. From there it's pretty much game-over.

Mitigation and Other Techniques

Two of the techniques used to reduce the effectiveness of stack smashing are DEP and ASLR.

DEP ("Data Execution Prevention") works by marking the stack non-executable. This means that the [Evil Code] on the stack won't run, because running code on the stack is no longer allowed. To get around this, the attacker finds chunks of existing code that will do bits and pieces of what he wants. And instead of just overwriting his own return address, he creates a chain of return addresses down through the stack for all the functions he wants to run in turn. They call this "Return Oriented Programming", or ROP. The chain of returns is called a "ROP Chain". This is really hard to do. But there are tools to help.

ASLR ("Address Space Layout Randomization") works by randomizing the locations of all the interesting functions. Now creating a ROP chain isn't so easy -- every time the program runs, all the addresses are in different places. So when the attacker goes to overwrite the return address with is own Evil Address, he won't know what numbers to use because the code is always in different places.

Neither DEP nor ASLR on its own offers much protection, but both together make successful exploitation very difficult. While some circumventions sometimes exist, there isn't a workaround that works everywhere. If you can get around DEP+ASLR, it's a one-off sort of success.

tylerl
  • 82,225
  • 25
  • 148
  • 226
  • +1 for being very clear and informative, but I was hoping for a 45 second metaphor I could use to explain it to someone who doesn't really want to know all of the technical details. – KnightOfNi Mar 22 '14 at 14:45
  • 3
    Analogies for simple buffer overflows are easy enough, but that's an intuitive concept that rarely requires much explanation. Arbitrary code execution due to stack overflow is a different matter. There really isn't a real-world parallel because it depends on the interaction of rules and conventions that are peculiar to this subject. People understand easily enough that you can overflow one field into another, but that usually leaves the question, "why the hell does that mean the attacker now gets to do whatever he wants?" – tylerl Mar 23 '14 at 18:28
3

The other answers are still pretty technical, so I am offering this.

Let's imagine you have a kindergarten class. There are cubby holes for each student to put their shoes in. Each cubby hole holds one shoe. So for each student, you provide two cubby holes.

Each student is assigned two adjacent cubby holes. The teacher then calls students at random to put their shoes into the cubby holes to which they are assigned.

When the teacher calls up Bad Billy Bad Billy wants to mess with Stupid Sally. Billy's cubby holes are numbers 5 and 6 and Sally's are numbers 7 and 8. Billy puts his shows in 5 and 6 and then overflows his defined limit and puts a slimy toad in Sally's cubby number 7.

Because the teacher is not enforcing any protections on the defined limit for using cubby holes in the adjacent order, Billy is able to overflow his limit and mess with Sally's storage. Now when Sally goes to get her shoe, she will get a slimy toad instead yuck!


+-------------------+--------------------+-------------------+--------------------+
|      CUBBY 5      |       CUBBY 6      |      CUBBY 7      |       CUBBY 8      |
+-------------------+--------------------+-------------------+--------------------+
|                   |                    |                   |                    |
| Billy's Left Shoe | Billy's Right Shoe | Sally's Left Shoe | Sally's Right Shoe |
+-------------------+--------------------+-------------------+--------------------+

Billy input three items where it is defined he should only put in 2, this is how a stack overflow works at a high level, someone is messing with storage for which they are not authorized and then when that storage get's read it's not what you were expecting.

+-------------------+--------------------+------------+--------------------+
|      CUBBY 5      |       CUBBY 6      |   CUBBY 7  |       CUBBY 8      |
+-------------------+--------------------+------------+--------------------+
|                   |                    |            |                    |
| Billy's Left Shoe | Billy's Right Shoe | Slimy Toad | Sally's Right Shoe |
+-------------------+--------------------+------------+--------------------+

A buffer overflow could have been prevented if the teacher was paying more attention and ensuring that each student only used the amount of storage which was expected.

Eric G
  • 9,691
  • 4
  • 31
  • 58
  • While this has a great "overflow" component, it doesn't really show how a buffer overflow can be utilized to execute script (see the cookbook and price chart examples, which both result in the attacker getting something). – KnightOfNi Mar 22 '14 at 16:26
  • If the function is SallyPutsOnShoe(), then when Sally goes to obtain her shoe she get's a toad instead. Billy get's to laugh. Billy's goal is just to change the outcome. Would you not consider this a denial of service against Sally getting her shoes on so she can go outside and play? It is intended the frog replaces the shoe not just puts the toad in the shoe. – Eric G Mar 22 '14 at 16:29
  • Yeah, but the goal of a buffer overflow isn't just to make the vulnerable program not work, it's to make the program work for you. Billy does cause a bit of chaos, but that would be the equivalent of me smashing a stack and then overwriting the EIP with "xxxxxx." It doesn't really do anything for me. – KnightOfNi Mar 22 '14 at 16:38
  • I believe the question was asking about just a buffer overflow, not a stack overflow. You can insert an arbitrary instruction as one attack or you can put in new data. Imagine you have to adjacent spaces in memory for the amount of money you are owed by the Bank, if you overflow the first memory allocation and can write to the second one for which you don't have permission, now the Bank owes you more money. You illegally modified the input to a legit function to your advantage, why introduce new code to give you more money if you can just change the input illegally? – Eric G Mar 22 '14 at 16:43
  • Fair enough, +1 for being original! – KnightOfNi Mar 22 '14 at 16:46
3

I'll try this without using any analogies.

A computer is basically all memory, that's the important part, the contents of memory are instructions, which tell the computer what to do, and data, which the instructions make use of and can use or modify. Frequently it's necessary to store data which has a variable length. For example, if a program has to keep track of someone's email address that could be very short (a@b.com) or very long (first-name.middle-name.last-name@mycustomdomainname.co.uk). Some programs don't keep track of the maximum length of their data records very well. So if a program was designed with a maximum of, say, 100 characters for an email address and someone gave it an email address with more than 100 characters the program would just continue writing the rest of the address in memory past the end of its pre-allocated space. The important part to remember is that the memory is everything, the program itself is in memory right along side the data records.

Someone who knew exactly how this program worked could give it a very carefully crafted email address that was very long and had special characters at the end of it. The idea being that when the program stored the email address in memory it would blindly write those special characters to a part of the memory where the program thought other parts of itself were, and then when it went to run those parts it would instead run whatever program those special characters translated into, in computer code. In that way it would be possible for someone to get the computer to run anything they wanted it to, just by carefully crafting the data they gave to the program.

Wedge
  • 323
  • 1
  • 3
1

Good question. Here's an analogy that isn't the most technically accurate, but it should get the idea across.

Picture a recipe book on 3-hole punch paper in a binder (memory) and a very dumb cook (the processor, i.e. the CPU).

  • People can add or remove pages from the binder (load or unload programs and data in memory)
  • The cook just follows every instruction on the page they're on
  • The cook starts at the beginning (bootloader) and continues on until the instruction is "close book"
    • Even if the instruction is to flip to another page (Turn to page 394)

So, normally, you'd write on page one "Turn to page 200 (waffles)", open up the binder, and put in waffles at page 200. Then have the cook start - the cook should make waffles!

But wait... there's an attacker! They've written notes in the margins of your waffle recipe (outside the buffer) - and the cook executes those instructions even though they're obviously handwritten.

The cook was never told to only do what's printed on the original sheet (in the normal buffer space) - the cook will also do anything after that (in memory after the buffer).

Perhaps the cook adds vinegar to the waffles (corrupts your files). Perhaps the cook turns to page three hundred and ninety four and just leaves the raw egg sitting there, unused, until it rots and molds (turns off your antivirus). Perhaps the cook throws away everything in the kitchen (deletes all your files), or puts a lock on your kitchen door to keep you out (ransomware), or opens the window (installs a trojan/backdoor) so the attacker can climb in the window.

Anti-weakpasswords
  • 9,785
  • 2
  • 23
  • 51
  • So what is the cook? – KnightOfNi Mar 22 '14 at 02:21
  • The CPU, blindly executing instructions; I updated the answer slightly to make it more clear. – Anti-weakpasswords Mar 22 '14 at 02:22
  • 1
    Looking over this again, it looks a bit more like SQL injection than a buffer overflow. Can you add an "overflowing" component? Thanks. – KnightOfNi Mar 22 '14 at 02:25
  • Oh! Or are you saying that by adding new pages the attacker can put HIS instructions on page 200? A bit of a weak buffer, but that would make a lot of sense. – KnightOfNi Mar 22 '14 at 02:29
  • An attacker can put their own data in "memory" (the book) wherever they like. Additionally, if you consider the "buffer" to be "the line of text inside the margins", then the "overflow" is "writing in the margins". SQL Injection isn't really that different at this high a level (the 60,000 foot view) - the attacker is putting stuff where it shouldn't be executed, and it's getting executed anyway. – Anti-weakpasswords Mar 22 '14 at 02:34
  • Why the downvote? – Anti-weakpasswords Jan 23 '15 at 21:25
1

I always explain it as like bursting a bucket. The bucket is there to protect the contents from the outside and vice versa, but you're using the contents to get to the outside of the bucket, and therefore access to areas of the system that you should not otherwise have access to.

David
  • 111
  • 3
  • 1
    I considered this, but as @tylerl mentioned, there isn't a great way to explain how this leads to the attacker being able to do/get what he wants. Thoughts? – KnightOfNi Mar 25 '14 at 21:25
0

How's this?

The data in a computer is stored as a long list of numbers, like the tracks on a music cassette. Unlike music, which is played from the start to the end, computers need to jump around from one track to another, so they need a 'track listing' to tell them where each one starts.

Track lists are easy for music, since each song has a known length. With a computer, the amount of data we need to store might not be known yet, for example if it's coming in from the Internet. If the track we're using fills up, we need to switch to a different, unused one. If we don't, for example if we wrongly assume that we'll never be given more than a certain amount of data, we might use up too much tape and 'tape over' the next track. When a program tries to read that next track, it will get back part of our data instead of whatever was there before.

This can be dangerous, because the overwritten data might have been a set of instructions to carry out. If so, the computer will now be carrying out instruction downloaded straight from the Internet!

Warbo
  • 111
  • 4
  • I do like how well your metaphor blends with real life, but it's a bit confusing... would it be more accurate to say that RAM as a whole is a (really big) album, and each stack is a tape? If so, could you edit your answer to reflect that? – KnightOfNi Mar 25 '14 at 21:39
  • I don't think it's necessary to mention stacks explicitly, even if they are commonly exploited via buffer overflows. Buffer overflows themselves are a more general bug. It's like trying to explain "SQL injection", which requires explaining databases, instead of "code injection", which is more general. – Warbo Mar 26 '14 at 12:01