Foundations: What Are Buffer Overflows?
by Rik Farrow, Internet Security Consultant
It seems like every week, sometimes a couple of times a week, LiveSecurity advisories warn you of new vulnerabilities that involve buffer overflows.
Buffer overflows are painfully common, even in code where some vendor claims to have searched and destroyed all potential occurrences. You might also have heard of variants to buffer overflows, like format string and heap attacks. In this article, using analogies from everyday life, I'll explain how these attacks work. I borrow an idea I got from reading Bruce Schneier's Secrets and Lies, although, like any true hacker, I will modify and expand on his idea.
The dimwitted clerk
Schneier explains buffer overflows by comparing computer memory to a loose leaf binder containing instructions for a convenience store clerk. Each page has one instruction; for example, "Greet customer", "Ring up item", "Accept Payment", etc. Suppose the clerk at the convenience store is dimwitted and follows the instruction booklet exactly.
That opens the convenience store to a simple attack. The attacker walks up to the counter, and while the clerk pages through the instructions, the attacker slips in a page that reads, "Take all the money out of the register and give it to the customer." One would hope that as the clerk follows the instructions in the book, he would notice that something is amiss at this point, right?
Memories, in the pages of my mind...
Unlike most store clerks, computers both follow instructions exactly and have no common sense at all. If an attacker can slip in additional instructions, the computer will execute those instructions to the letter. That is the essence of a buffer overflow attack.
There are three common varieties of buffer overflow attacks: stack attacks, format string attacks, and heap attacks. Each attack is similar but affects a different part of a computer's memory. So that you might understand the distinctions among these attacks, let me provide a little background about how computer memory works.
When a program begins to execute, the operating system hands it a huge chunk of virtual memory. Think of this as resembling a blank book that the program gets written into, starting on page one with the program's instructions and ending with the program's data. When that is done, there are lots of blank pages left over in this book. The blank pages just after the program's data are called the "heap", and the blank pages at the very end of the book are called the "stack". Just as if you were using a notebook from both ends, the heap grows toward the back of the book and the stack grows toward the front. And the "book", the virtual memory, is so large that the heap never reaches the stack, and vice versa.
Locations within this virtual memory (the notebook's "pages"), whether in the program, the stack, the heap, or in between, are referenced by an address expressed in hexadecimal characters; for example, the highest address in two gigabytes of memory would be 8FFFFFFF. Small regions of this address space are reserved for input to the program. These regions, which can have addresses in the stack or the heap, are called buffers. Aha! We've encountered our first clue on why these attacks are called "buffer overflows." If you've heard someone say, "this is a buffer overflow in the stack," or "this is a stack-smashing attack," or "this is a heap buffer overflow," they're specifying where the problem occurs within the memory allotted to a specific program.
The stack stores temporary information. Again, we can illustrate this by borrowing from Schneier's book. Imagine you are writing notes about some project you're working on, when the phone rings. The caller is providing information you requested, so you grab another piece of paper, place it over the first one, and take notes. Before you get off the phone, your boss walks in, gets your attention, and asks you to do something when you get off the phone. You get another piece of paper and add the boss's request to it. By now, you have a short stack of paper, each with instructions and data on it. As you complete each task, you crumple up the sheet of paper and toss it into the recycling bin. You have been using a stack very much like the one talked about in buffer overflow attacks.
In the computer, there are, of course, no pieces of paper, but just memory (RAM). Data really does get added to the top of the stack, and later removed. In a stack-based buffer overflow attack, the perpetrator adds more data than expected to the stack, overwriting data that the programmer thought would never be in any danger of being replaced. For example, let's say that a program is executing and reaches the stage where it expects to use a postal code or zip code, which it gets from a Web-based form that customers filled out. Even the longest postal code requires fewer than twelve characters. But in this example, an attacker filled out the Web-based form. Instead of typing a postal code, he typed the letter "A" 256 times, followed by some commands. When the program receives this over-long string, the nonsensical data overflows the buffer allotted for the zip code (remember, buffers are regions of memory reserved to accept input), and the attacker's commands fall into the stack. Just like the convenience store robber slipping in the "Give me the money" page, a buffer overflow attack slips in instructions the program would not ordinarily do. Of course, this being a very literal computer, if the instructions are not perfect, the program crashes. If the instructions are perfect, the program blindly carries out the attacker's instructions.
In an ideal world, programmers guard against buffer overflow attacks by measuring all the data passed to the program, and assuring that it will always fit into the memory set aside for the purpose. (In the postal code example above, the program could be written to discard any input after the twelfth character.) In the real world, programmers often forget that there are lots of attackers, or sometimes, are not fully aware that the data the program expects comes from an untrusted source. The larger and more complex a program becomes, the more frequently the unexpected happens.
Format string attacks
The format string attack also affects the stack, but involves a much smaller change than the stack buffer overflow we already discussed. Formatting means to take some data and prepare it for display or printing, but the formatting instructions are so flexible that some attackers have found ways of using formatting to write to memory. Format string attacks usually add a single address in memory that points to another address in memory where the attacker has added new instructions to execute. To use our "dimwitted clerk" analogy again, suppose the clerk's instruction book contained 25 pages of instructions, but right after the page that reads, "Take the customer's money and open the cash register," the robber inserted the instruction, "Turn directly to page 26." The robber might have prepared a few pages of instructions and placed them in the back of the book, such as "Give all the cash to the customer" and "Let the customer leave, undisturbed." If the stupid clerk followed these directives, that would be similar to what happens when an attacker causes a program to skip to a specified address in memory and execute whatever instructions it finds there.
Heaps of trouble
The heap attack does not involve the stack at all. Remember the "discarded notes" analogy: stack uses temporary memory. In contrast, "heap" is the programming name for memory that is not temporary, but expected to remain in use while a program continues. Pages in the heap can be read from and written to, and attackers take advantage of this by writing attack instructions into the pages in the heap, then tricking the computer into following these instructions. Conceptually, this is not different from the stack attack, except that it occurs in the heap instead of the stack.
Defenses: Of bugs and canaries
We already know what the best defense against any of these attacks is: perfect programs. Ideally, every field in every program would allow only a given number of characters (a concept known as bounds checking) and would only allow expected characters (why should a program accept letters, or metacharacters like %, in a phone number?). We also know that programs are not perfect, they have bugs, and some of those bugs permit attacks. Because programs are not perfect, programmers have come up with schemes to defend against buffer overflow attacks.
The simplest scheme involves telling the computer to use the stack and the heap for data only, and never to execute any instructions found in the stack and the heap. While this approach works very well for many UNIX systems, it can't be used on Windows systems. Moreover, it involves the UNIX system administrator changing configuration settings on each individual server, and is easier on non-Intel processors (like Sun Microsystem's Sparc processors).
Another popular defense scheme protects against buffer overflows, but only the kind that overwrite the stack. This defense involves the use of a canary. Remember the stories about miners carrying canaries into coal mines with them? Coal mines often release methane gas, which has no odor but causes the miners to pass out, and eventually to suffocate. If miners expanded the mine into a new area containing methane, the canary would pass out first, giving the coal miners sufficient warning to leave that part of the mine.
The stack canary protects the stack by being inserted in sensitive locations in memory (near return addresses, which are sensitive locations in the stack telling the computer where to find the next commands to execute after it completes its current function). Before return addresses get used, the program checks to see if the canary is okay. If the canary has been clobbered, the program then quits, knowing that something has gone wrong.
The whole idea of using canaries was developed by a group of Linux developers, who produce a version of Linux (Immunix.com) that uses Stackguard to add canaries throughout the operating system and the programs that come with it. Microsoft's new compiler for Visual C has the option of adding canaries to the stack, too.
Canaries do help, but cannot protect against heap attacks. Heap attacks do not affect the stack at all, avoiding the canary completely. Programmers must write code that will only copy as much data into a buffer as it was designed to hold (or, in other words, write perfect programs). That is the most effective defense.
What you can do about buffer overflows
WatchGuard Firebox users do have an additional line of defense. When you configure your Firebox to use application gateways (which WatchGuard jargon calls proxies), this software watches for the use of overly long input to services protected: e-mail, HTTP, FTP, and DNS. While not a perfect defense, proxies can stop many buffer overflow attacks. If you use packet filtering instead of proxies, even stateful packet filtering, you lose this advantage.
Hopefully, this little discussion helps you to understand buffer overflow attacks, the different types of attacks, some of the countermeasures, and why even these countermeasures don't always work. But you aren't defenseless. If your firewall has application gateways or proxies, use them. When LiveSecurity Information Alerts warn you of major known buffer overflow vulnerabilities, patch your applications. Using these measures, and your new understanding of buffer overflows, you should be OK.