Buffer overflow
In computer security and programming, a buffer overflow is an anomalous condition where a process attempts to store more data in a buffer than there is memory allocated for it, causing the extra data to overwrite adjacent memory locations. The overwritten data may include other buffers, variables and program flow data.
Buffer overflows can cause a process to crash or produce incorrect results. They can be triggered by specially crafted input which may be designed to execute arbitrary, possibly malicious, code, or to make the program operate in an unintended way. As such, buffer overflows cause many software vulnerabilities. Sufficient bounds checking — by the programmer or by the compiler can avoid the overflow problem.
High-level description
A program which takes advantage of a vulnerability to subvert another program's security is called an exploit and is usually intended to gain access to superuser (called "root" in UNIX) or otherwise escalated privileges. A buffer overflow exploit works by feeding the program specially crafted input that is designed to overflow the allocated data storage buffer and change the data that follows the buffer in memory.
For example, take a program to change a user's password. It is runnable by any user, but must run with superuser privileges in order to effect the changes. If the program fails to ensure that the length of the new password entered is equal to or smaller than the data buffer allocated for its storage, then any overflow data will simply be written over whatever happens to be after the data buffer. If this post-buffer area is executable code, a malicious user can overflow the buffer with machine language instructions to perform any function normally requiring root privileges — add users, delete users, change passwords, alter or delete any file, etc.
Properly written programs check the length of input data, to ensure that it is not larger than the allocated data buffer, but this is frequently overlooked, especially by novice programmers. Buffer overflows are most easily exploited when the data buffer is in the program's function stack, since this can lead directly to an alteration of the program's execution path.
Determining the exploitability of a buffer overflow vulnerability can be difficult, even for experienced programmers, since it involves a lot of high and low level knowledge of the architecture internals and the target program. Overflows of as little as a single byte beyond the end of a buffer have proven exploitable.
Buffer overflows are rarely a problem with the compiler or interpreter of a programming language, but rather programming errors. Buffer overflows are common only in programs written in relatively low-level programming languages, such as assembly language, C, and C++ which require the programmer to manually manage the size of allocated memory. See the Choice of programming language section below.
Technical description
When a dynamic buffer or array is allocated in a function, it is allocated at function call time on the runtime stack. A buffer overflow occurs when data is written over, spilling onto the stack. Note that a buffer overflow can occur regardless of the direction of stack growth. Typically the stack will be used for storing return address from functions, which can be overwritten as follows.
Here, (DATA) (DATA) (...) represents the existing stack, and (NEWDATA) is some new value the CPU has pushed onto the stack:
(NEWDATA)(DATA)(DATA)(...)
When a C program executes a subroutine, it pushes the return address onto the stack, so the subroutine knows where to return control to when it has finished:
(ADDR)(DATA)(DATA)(...)
When a dynamic buffer is allocated, the stack grows left by however big the buffer is. So, if a function starts with a 'char a[10]' declaration, the result is:
(.a.........)(ADDR)(DATA)(DATA)(...)
where a is the first entry of the array. At the end of the function, the buffers are deallocated, everything pushed is popped, and a RET operation is called. This pops the return address off the stack and jumps there, shifting program control back to wherever the subroutine was called from.
Suppose that 10 byte buffer is intended to hold user input (a new password, using the example from above). If the program fails to specifically check the number of characters the user has entered, and writes 14 bytes to the buffer, the extra data will clobber the return address, overwriting part of it with the extra data. This changes where program control will go to continue execution when the subroutine has finished.
If the user is not malicious and enters more than 10 characters, the extra data will most likely give an invalid address — pointing to an area in memory which is not under the control of the currently executing program. When the function attempts to return, it references this garbage address outside of its address space, causing a a segmentation fault (or an analogous error on other operating systems) .
If a technically inclined user is malicious, it may be possible to overwrite the return address to point to some user-controlled buffer (perhaps the overflown buffer itself); the attacker has then gained control of the program and its privileges.
Example
The following is C source code. Once compiled, the program can be used to generate buffer overflow errors. The first command-line argument is taken as the text with which to fill the buffer.
/* overflow.c - demonstrates the buffer overflow process */
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[])
{
char buffer[10];
if(argc < 2)
{
fprintf(stderr, "USAGE: %s string\n", argv[0]);
return 1;
}
strcpy(buffer, argv[1]);
return 0;
}
Strings of 9 or fewer characters will not cause a buffer overflow. Strings of 10 or more characters will cause an overflow; however, they may not result in a segmentation fault.
This program could be safely rewritten using strncpy as follows:
/* better.c - demonstrates how to fix the problem */
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[])
{
char buffer[10];
if(argc < 2)
{
fprintf(stderr, "USAGE: %s string\n", argv[0]);
return 1;
}
strncpy(buffer, argv[1], sizeof(buffer));
buffer[sizeof(buffer) - 1] = '\0';
return 0;
}
Protection from buffer overflows
Various techniques have been used to detect or prevent buffer overflows, with various tradeoffs. The surest way to prevent buffer overflows is to use automatic protection at the language level (see below). This sort of protection, however, cannot be applied to legacy code, and often technical, business, or cultural constraints call for a vulnerable language.
Packet scanning
Intrusion-detection systems (IDSs) and application firewalls can detect remote attempts to exploit buffer overflows. These are able to block packets which have the signature of a known attack, or if a long series of No-Operation (NOP) instructions (known as a nop-sled) is detected, these are often used when the location of the exploit's payload is slightly variable.
Packet scanning is not an effective method since it can only prevent known attacks and there are many ways that a 'nop-sled' can be encoded. Attackers have begun to use alphanumeric, polymorphic, and self-modifying shellcodes to avoid detection by heuristical packet scans.
Stack-smashing protection
Stack-smashing protection is used to detect the most common buffer overflows by checking that the stack has not been altered when a function returns. If it has been altered, the program exits with a segmentation fault.
Two such systems are StackGuard and ProPolice, both of which are patches to gcc. As of gcc-4.1-stage2 the ProPolice patch, which appears to have superceded StackGuard, was incorporated into the mainline distribution. Gentoo Linux (when "hardened") and OpenBSD supply ProPolice by default with gcc.
Stronger stack protection is possible by splitting the stack in two: one for data and one for function returns. This split is present in the Forth programming language, though it was not a security-based design decision. Regardless, this is not a complete solution to buffer overflows, as sensitive data other than the return address may still be overwritten.
Implementations
Executable space protection
Protecting the executable space may soften the blow of buffer overflow exploits by making most of their operations impossible. This is done by randomizing the address space (ASLR) and making sure that all memory is either writable or executable, but never both.
Some CPUs, such as Sun Microsystems' Sparc, Transmeta's Efficeon, and newer 64-bit Intel and AMD processors prevent code from being executed on areas of memory flagged with a special NX bit. AMD calls their solution NX, derived from No eXecute, and Intel call theirs XD, after eXecute Disabled.
However, this method of protection will not prevent corruption of the stack although it will often prevent the attacker's code from being successfully executed. This is achieved by marking the stack and heap segments as non-executable, which is where hostile code is normally inserted. This however does not stop an attacker from modifying other variables or executing existing code.
Protection in Linux, UNIX, and BSD
Two patches for the Linux kernel that protect memory in this manner this are PaX and exec-shield. Neither of these are included in the production kernel distribution. OpenBSD since 3.3 has included a system called W^X, which provides executable space control as well.
ASLR will make 'return to libc' exploits very difficult. The attacker would have to correctly guess the address range assigned.
Protection for Windows systems
Development of similar protection methods for Windows has taken longer, but Windows customers can choose from a wide variety of MS and 3rd party "Executable Space Protection" (ESP) solutions that attempt to prevent execution of malicious code.
Microsoft has recently introduced their ESP solution named Data Execution Prevention (DEP) with Service Pack 2 for XP and Service Pack 1 for Windows 2003. DEP relies on a hardware extension provided by Intel/AMD built on top of Page Addressing Extensions (PAE). PAE was initially created to overcome the 4GB limit resulting from 32-bit memory management. It effectively increases the affected data structures to cover additional bits in order to be capable of addressing beyond the 4GB boundary. Furthermore, the extended data structures contain an NX bit, that is not used otherwise during "normal" PAE mode.
Besides that, Microsoft has introduced a stack protection mechanism with Windows Server 2003 which detects overwritten stack memory by marking the stack with a random "canary" value that gets verified at a later time. If it has changed, the stack was overwritten.
There are multiple third-party solutions providing non-executable data pages and/or ASLR on the market today. It is worth noting that many such protection systems, as they are not very tightly integrated into the operating system, are circumventable and will not prevent attacks launched with knowledge of the defenses. The PAX website maintains a list of Windows-related solutions.
Use of safe libraries
The problem of buffer overflows is commonly manifest in the C and C++ languages because they expose low level representational details of buffers as containers for datatypes. Buffer overflows are thus avoided by maintaining a high degree of correctness in code which performs buffer management. Well-written and tested abstract data type libraries which centralize and automatically perform buffer management and include bounds checking can reduce the occurrence of buffer overflows. The two main building block data types in these languages in which buffer overflows commonly manifest are strings and arrays; libraries preventing buffer overflows in these data types provide the vast majority of the necessary coverage. Still, failure to use these safe libraries correctly can result in buffer overflows and other vulnerabilities; naturally, any bug in a library itself is a potential vulnerability.
Implementations
Choice of programming language
The choice of programming language can have a profound effect on the occurrence of buffer overflows. As of 2005, among the most popular languages are C and its derivative, C++, with an enormous body of software having been written in these languages. The languages do not check that data written to an array (the implementation of a buffer) is within the assumed boundaries of that array. The problem is that the effect of executing such an operation in C is not well defined, and thus may respond in any arbitrary way — usually silently overwriting data, failing later including corrupted later operations, or executing arbitrary code (as described above).
Variations on C, such as Cyclone and CCured help to prevent more buffer overflows by, for example, attaching size information to arrays. The D programming language uses a variety of techniques to prevent most uses of pointers and arrays.
Many other programming languages provide some kind of run time check which might send a warning or raise an exception when C or C++ would overwrite data. Examples of such languages range broadly from Python to Ada, from Lisp to Modula-2, and from Smalltalk to OCaml. The Java programming language, in many ways similar to C and C++, raises exceptions on buffer overflows. Nearly every strongly typed or interpreted programming language will protect against buffer overflows, signalling a well-defined error condition. Static analysis can remove many dynamic bound and type checks, but poor implementations and awkward cases can significantly decrease performance.
History
In 1988, the Morris worm used a buffer overflow in a Unix program called fingerd to propagate itself over the Internet. Even after this incident, buffer overflows were virtually ignored as a security issue. Later, in 1995, Thomas Lopatic independently rediscovered the buffer overflow and published his findings on the Bugtraq security mailing list, which caused a wave of new security relevant buffer overflows to be found. In 1996, Elias Levy (aka Aleph One) published in Phrack magazine the paper "Smashing the Stack for Fun and Profit", a step-by-step introduction to exploiting stack-based buffer overflow vulnerabilities, which caused a wave of new buffer overflow exploits to be written. Then, in 2001, the Code Red worm sent specially crafted packets to machines executing Microsoft Internet Information Services (IIS) 5.0, triggering a buffer overflow and yielding full administrative privileges to the worm. (HTTP servers typically must have administrative privileges to use the standard TCP port 80; IIS5 did not drop its administrative privileges after using them.) Following in 2003, the SQLSlammer worm compromised machines running Microsoft SQL Server 2000 by sending specially crafted packets to those machines and allowing execution of arbitrary code.
See also
- Common libc functions that can lead to buffer overflows : strcpy, strcat, sprintf
- Computer security
- Heap overflow
- Memory debugger
- Secure operating systems
- Security focused operating systems
- Self-modifying code
- shellcodes
- SPlint
- Static code analysis