How to explain buffer overflow to a layman
Imagine you have a list of people you owe money to.
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:
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:
(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.
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.
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.