In
computer security and
programming, a 'buffer overflow', or 'buffer overrun', is a programming error which may result in a
memory access
exception and program termination, or in the event of the user being malicious, a possible breach of system security.
A buffer
overflow is an
anomalous condition where a
process attempts to store
data beyond the boundaries of a fixed-length
buffer. The result is that the extra data overwrites adjacent
memory locations. The overwritten data may include other buffers, variables and program flow data and may cause a process to
crash or produce incorrect results. They can be triggered by inputs specifically designed to execute malicious code or to make the program operate in an unintended way. As such, buffer overflows cause many
software vulnerabilities and form the basis of many
exploits. Sufficient
bounds checking by either the programmer, the
compiler or the
runtime can prevent buffer overflows.
Technical description
A buffer overflow occurs when
data written to a buffer, due to insufficient
bounds checking, corrupts data values in
memory addresses adjacent to the allocated buffer. Most commonly this occurs when copying
strings of
characters from one buffer to another.
Basic example
In the following example, a program has defined two data items which are adjacent in memory: an 8-byte-long string buffer, A, and a two-byte integer, B. Initially, A contains nothing but zero bytes, and B contains the number 3. Characters are one byte wide.
| A | A | A | A | A | A | A | A | B | B |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
Now, the program attempts to store the character string "excessive" in the A buffer, followed by a zero byte to mark the end of the string. By not checking the length of the string, it overwrites the value of B:
| A | A | A | A | A | A | A | A | B | B |
| 'e' | 'x' | 'c' | 'e' | 's' | 's' | 'i' | 'v' | 'e' | 0 |
Although the programmer did not intend to change B at all, B's value has now been replaced by a number formed from part of the character string. In this example, on a
big-endian system that uses
ASCII, "e" followed by a zero byte would become the number 25856. If B was the only other variable data item defined by the program, writing an even longer string that went past the end of B could cause an error such as a
segmentation fault, terminating the process.
Exploitation
The techniques to
exploit a buffer overflow vulnerability vary per
architecture,
operating system and memory region. For example, exploitation on the
heap (used for dynamically allocated memory) is very different from on the
call stack.
Stack-based exploitation
A technically inclined and malicious user may exploit stack-based buffer overflows to manipulate the program in one of several ways:
★ By overwriting a local variable that is near the buffer in memory on the stack to change the behaviour of the program which may benefit the attacker.
★ By overwriting the return address in a
stack frame. Once the function returns, execution will resume at the return address as specified by the attacker, usually a user input filled buffer.
★ By overwriting a function pointer,
[1] or exception handler, which is subsequently executed.
With a method called "Trampolining", if the address of the user-supplied data is unknown, but the location is stored in a register, then the return address can be overwritten with the address of an
opcode which will cause execution to jump to the user supplied data. If the location is stored in a register R, then a jump to the location containing the opcode for a jump R, call R or similar instruction, will cause execution of user supplied data. The locations of suitable opcodes, or bytes in memory, can be found in
DLLs or the executable itself. However the address of the opcode typically cannot contain any
null characters and the locations of these opcodes can vary in their location between applications and versions of the operating system. The
Metasploit Project is one such database of suitable opcodes, though only those found in the
Windows operating system are listed.
[2]
Stack-based buffer overflows are not to be confused with
stack overflows.
Heap-based exploitation
A buffer overflow occurring in the heap data area is referred to as a heap overflow and is exploitable in a different manner to that of stack-based overflows. Memory on the heap is dynamically allocated by the application at run-time and typically contains program data. Exploitation is performed by corrupting this data in specific ways to cause the application to overwrite internal structures such as linked list pointers. The canonical heap overflow technique overwrites dynamic memory allocation linkage (such as
malloc meta data) and uses the resulting pointer exchange to overwrite a program function pointer.
The
Microsoft JPEG GDI+ vulnerability is a recent example of the danger a heap overflow can represent to a computer user.
[3]
Barriers to exploitation
Manipulation of the buffer which occurs before it is read or executed may lead to the failure of an exploitation attempt. These manipulations can mitigate the threat of exploitation, but may not make it impossible. Manipulations could include conversion to upper or lower case, removal of
metacharacters and filtering out of non-
alphanumeric strings. However, techniques exist to bypass these filters and manipulations;
alphanumeric code,
polymorphic code,
Self-modifying code and
return to lib-C attacks. The same methods can be used to avoid detection by
Intrusion detection systems. In some cases, including where code is converted into unicode,
[4] the threat of the vulnerability have been misrepresented by the disclosers as only Denial of Service when in fact the remote execution of arbitrary code is possible.......
Practicalities of exploitation
In real-world exploits there are a variety of issues which need to be overcome for exploits to operate reliably. Null bytes in addresses, variability in the location of shellcode, differences between different environments and various counter-measures in operation.
Nop sled technique
Illustration of a NOP-sled payload on the stack.
A NOP-sled is oldest and the most widely known technique for successfully exploiting a stack buffer overflow.
[5] It solves the problem of finding the exact address to the buffer by effectively increasing the size of the target area. To do this much larger sections of the stack are corrupted with the
no-op machine instruction. At the end of the attacker supplied data, after the no-op instructions, is placed an instruction to perform a relative jump to the top of the buffer where the shellcode is located. This collection of no-ops is referred to as the "NOP-sled" because if the return address is overwritten with any address within the no-op region of the buffer it will "slide" down the no-op's until it is redirected to the actual malicious code by the jump at the end. This technique requires the attacker to guess where on the stack the NOP-sled is instead of the, comparatively small, shellcode.
[6]
Because of the popularity of this technique many vendors of
Intrusion prevention systems will search for this pattern of no-op machine instructions in an attempt to detect shellcode in use. Its important to note that a NOP-sleds does not necessarily contain only traditional no-op machine instructions; any instruction that does not corrupt the machine state to a point where the shellcode will not run can be used in place of the hardware assisted no-op. As a result it has become common practice for exploit writers to compose the no-op sled with randomly chosen instructions which will have no real effect on the shellcode execution.
[7]
While this method greatly improves the chances that an attack will be successful, it is not without problems. Exploits using this technique still must rely on some amount of luck that they will guess offsets on the stack that are within the NOP-sled region.
An incorrect guess will usually result in the target program crashing and could alert the
system administrator to the attacker's activities. Another problem is that the NOP-sled requires a much larger amount of memory in which to hold a NOP-sled large enough to be over any use. This can be a problem when the allocated size of the affected buffer is too small and the current depth of the stack is shallow (i.e. there is not much space from the end of the current stack frame to the start of the stack). Despite its problems, the NOP-sled is often the only method that will work for a given platform, environment, or situation; as such it is still an important technique.
The jump to register technique
The "jump to register" technique allows for reliable exploitation of stack buffer overflows without the need for extra room for a NOP-sled and without having to guess stack offsets. The strategy is to overwrite the return pointer with something that will cause the program to jump to a known pointer stored within a register which points to the controlled buffer and thus the shellcode. For example if register A contains a pointer to the start of a buffer then any jump or call taking that register as an operand can be used to gain control of the flow of execution.
[9] 
An instruction from ntdll.dll to call the
DbgPrint() routine contains the
i386 machine opcode for
jmp esp.
In practice a program may not intentionally contain instructions to jump to a particular register. The traditional solution is to find an unintentional instance of a suitable
opcode at a fixed location somewhere within the program memory. In figure
E on the left you can see an example of such an unintentional instance of the i386
jmp esp instruction. The opcode for this instruction is
FF E4.
[10] This two byte sequence can be found at a one byte offset from the start of the instruction
call DbgPrint at address
0x7C941EED. If an attacker overwrites the program return address with this address the program will first jump to
0x7C941EED, interpret the opcode
FF E4 as the
jmp esp instruction, and will then jump to the top of the stack and execute the attacker's code.
[11]
When this technique is possible the severity of the vulnerability increases considerably. This is because exploitation will work reliably enough to automate an attack with a virtual guarantee of success when it is run. For this reason, this is the technique most commonly used in
internet worms that exploit stack buffer overflow vulnerabilities.
[12]
This method also allows shellcode to be placed after the overwritten return address on the windows platform. Since executables are based at address
0x00400000 and x86 is a Little Endian architecture, the last byte of the return address must be a null, which terminates the buffer copy and nothing is written beyond that. This limits the size of the shellcode to the size of the buffer, which may be overly restrictive. DLLs are located in high memory (above
0x01000000 and so have addresses containing no null bytes, so this method can remove null bytes (or other disallowed characters) from the overwritten return address. Used in this way, the method is often referred to as "DLL Trampolining".
Protective countermeasures
Various techniques have been used to detect or prevent buffer overflows, with various tradeoffs. The most reliable way to avoid or prevent buffer overflows is to use automatic protection at the language level. This sort of protection, however, cannot be applied to
legacy code, and often technical, business, or cultural constraints call for a vulnerable language. The following sections describe the choices and implementations available.
Choice of programming language
The choice of programming language can have a profound effect on the occurrence of buffer overflows.
As of 2006, among the most popular languages are
C and its derivative,
C++, with an enormous body of software having been written in these languages. C and C++ provide no built-in protection against accessing or overwriting data in any part of memory; more specifically, they do not check that data written to an array (the implementation of a buffer) is within the boundaries of that array. However, it is worth noting that the standard C++ libraries, the
STL, provide many ways of safely buffering data, and similar facilities can also be created and used by C programmers. As with any other C or C++ feature, individual programmers are given the choice as to whether or not they wish to accept possible performance penalties in order to reap the potential benefits.
Variations on C such as
Cyclone help to prevent more buffer overflows by, for example, attaching size information to arrays. The
D programming language uses a variety of techniques to avoid most uses of pointers and user-specified bounds checking.
Many other programming languages provide runtime checking 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 and
.NET bytecode environments also require bounds checking on all arrays. Nearly every
interpreted language will protect against buffer overflows, signalling a well-defined error condition. Often where a language provides enough type information to do bounds checking an option is provided to enable or disable it.
Static code analysis can remove many dynamic bound and type checks, but poor implementations and awkward cases can significantly decrease performance. Software engineers must carefully consider the tradeoffs of safety versus performance costs when deciding which language and compiler setting to use.
Use of safe libraries
The problem of buffer overflows is common in the C and C++ languages because they expose low level representational details of buffers as containers for data types. Buffer overflows must thus be 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, including bounds checking, can reduce the occurrence and impact of buffer overflows. The two main building-block data types in these languages in which buffer overflows commonly occur are strings and arrays; thus, libraries preventing buffer overflows in these data types can provide the vast majority of the necessary coverage. Still, failure to use these safe libraries correctly can result in buffer overflows and other vulnerabilities; and naturally, any bug in the library itself is a potential vulnerability. "Safe" library implementations include Vstr
[13] and Erwin.
[14] The
OpenBSD operating system's
C library provides the
strlcpy and
strlcat functions, but these are more limited than full safe library implementations.
In September 2006, Technical Report 24731, prepared by the C standards committee, was published; it specifies a set of functions which are based on the standard C library's string and I/O functions, with additional buffer-size parameters. However, the efficacy of these functions for the purpose of reducing buffer overflows is disputable; it requires programmer intervention on a per function call basis that is equivalent to intervention that could make the analogous older standard library functions buffer overflow safe.
[15]
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. Three such systems are Libsafe,
[16] and the ''
StackGuard''
[17] and ''
ProPolice''
[18] gcc patches.
Microsoft's
Data Execution Prevention mode explicitly protects the pointer to the SEH Exception Handler from being overwritten.
[19]
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.
Executable space protection
Executable space protection is an approach to buffer overflow protection which prevents execution of code on the stack or the heap. An attacker may use buffer overflows to insert arbitrary code into the memory of a program, but with executable space protection, any attempt to execute that code will cause an exception.
Some CPUs support a feature called
NX ("No eXecute") or
XD ("eXecute Disabled") bit, which in conjunction with software, can be used to mark
pages of data (such as those containing the stack and the heap) as readable but not executable.
Some Unix operating systems (e.g.
OpenBSD,
Mac OS X) ship with executable space protection (e.g.
W^X). Some optional packages include:
★
PaX [20]
★
Exec Shield [21]
★
Openwall [22]
Newer variants of Microsoft Windows also support executable space protection, called
Data Execution Prevention.
[23] Proprietary add-ons include:
★ BufferShield
[24]
★ StackDefender
[25]
Executable space protection does not protect against
return-to-libc attacks, or any other attack which does not rely on the execution of the attackers code.
Address space layout randomization
Address space layout randomization (ASLR) is a computer security feature which involves arranging the positions of key data areas, usually including the base of the executable and position of libraries, heap, and stack, randomly in a process' address space.
Randomization of the
virtual memory addresses at which functions and variables can be found can make exploitation of a buffer overflow more difficult, but not impossible. It also forces the attacker to tailor the exploitation attempt to the individual system, which foils the attempts of
internet worms.
[26] A similar but less effective method is to
rebase processes and libraries in the virtual address space.
Deep packet inspection
The use of deep packet inspection (DPI) can detect, at the network perimeter, remote attempts to exploit buffer overflows by use of attack signatures and
heuristics. 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,
metamorphic, and
self-modifying shellcodes to evade detection by heuristic packet scanners and
Intrusion detection systems.
History of exploitation
The earliest known exploitation of a buffer overflow was in 1988. It was one of several exploits used by the
Morris worm to propagate itself over the Internet. The program exploited was a
Unix service called
fingerd.
[27] Later, in 1995, Thomas Lopatic independently rediscovered the buffer overflow and published his findings on the
Bugtraq security mailing list.
[28] A year later, in 1996,
Elias Levy (aka Aleph One) published in ''
Phrack'' magazine the paper "Smashing the Stack for Fun and Profit",
[29] a step-by-step introduction to exploiting stack-based buffer overflow vulnerabilities.
Since then, at least two major internet worms have exploited buffer overflows to compromise a large number of systems. In 2001, the
Code Red worm exploited a buffer overflow in Microsoft's
Internet Information Services (IIS) 5.0
[30] and in 2003 the
SQL Slammer worm compromised machines running
Microsoft SQL Server 2000.
[31]
In
2003, Buffer overflows present in licensed
Xbox games have been exploited to allow unlicensed software, including
homebrew games, to run on the console without the need hardware modifications, known as
modchips.
[32] The
PS2 Independence Exploit also used a buffer overflow to achieve the same for the
PlayStation 2.
See also
★
Stack buffer overflow
★
Heap overflow
★
Shellcode
★
Return-to-libc attack
★
Self-modifying code
★
Computer security
★
Computer insecurity
★
Security focused operating systems
Notes
1. CORE-2007-0219: OpenBSD's IPv6 mbufs remote kernel buffer overflow
2. The Metasploit Opcode Database
3. Microsoft Technet Security Bulletin MS04-028
4. Creating Arbitrary Shellcode In Unicode Expanded Strings
5.
6.
7.
8.
9.
10. Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2A: Instruction Set Reference, A-M, , , , Intel Corporation, ,
11.
12.
13. The Vstr Homepage
14. The Erwin Homepage
15. CERT Secure Coding Initiative
16. Libsafe at FSF.org
17. StackGuard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks by Cowan et al.
18. ProPolice at X.ORG
19. Bypassing Windows Hardware-enforced Data Execution Prevention
20. PaX: Homepage of the PaX team
21. KernelTrap.Org
22. Openwall Linux kernel patch 2.4.34-ow1
23. Microsoft Technet: Data Execution Prevention
24. BufferShield: Prevention of Buffer Overflow Exploitation for Windows
25. NGSec Stack Defender
26. PaX at GRSecurity.net
27. "A Tour of The Worm" by Donn Seeley, University of Utah
28. Bugtraq security mailing list archive
29. "Smashing the Stack for Fun and Profit" by Aleph One
30. eEye Digital Security
31. Microsoft Technet Security Bulletin MS02-039
32. Hacker breaks Xbox protection without mod-chip
External links
★
An Overview and Example of the Buffer-Overflow Exploit. pps. 16-21.
★
CERT Secure Coding Standards
★
CERT Secure Coding Initiative
★
Secure Coding in C and C++
★
SANS: inside the buffer overflow attack
★
"Smashing the Stack for Fun and Profit" by Aleph One
★
"Advances in adjacent memory overflows" by Nomenumbra
★
A Comparison of Buffer Overflow Prevention Implementations and Weaknesses
★
More Security Whitepapers about Buffer Overflows
★
Chapter 12: Writing Exploits III from ''Sockets, Shellcode, Porting & Coding: Reverse Engineering Exploits and Tool Coding for Security Professionals'' by James C. Foster (ISBN 1-59749-005-9). Detailed explanation of how to use Metasploit to develop a buffer overflow exploit from scratch.
العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
Español
