Buffer overflow

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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 or the compiler can prevent buffer overflows.



[edit] 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.

[edit] 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.

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:

'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.

[edit] Stack-based overflows

Besides changing values of unrelated variables, buffer overflows can often be used (exploited) by attackers to cause a running program to execute arbitrary supplied code. The techniques available to an attacker to seek control over a process depend on the memory region where the buffer resides, for example the stack memory region, where data can be temporarily "pushed" onto the "top" of the stack, and later "popped" to read the value of the variable. Typically, when a function begins executing, temporary data items (local variables) are pushed, which remain accessible only during the execution of that function.

In the following example, "X" is data that was on the stack when the program began executing; the program then called a function "Y", which required a small amount of storage of its own; and "Y" then called "Z", which required a large buffer:

             : / / /

If the function Z caused a buffer overflow, it could overwrite data that belonged to function Y or to the main program:

. . . . . . . . / /

This is particularly serious because on most systems, the stack also holds the return address, that is, the location of the part of the program that was executing before the current function was called. When the function ends, the temporary storage is removed from the stack, and execution is transferred back to the return address. If, however, the return address has been overwritten by a buffer overflow, it will now point to some other location. In the case of an accidental buffer overflow as in the first example, this will almost certainly be an invalid location, not containing any program instructions, and the process will crash. However, a malicious attacker could tailor the return address to point to an arbitrary location such that it could compromise system security.

[edit] Example source code

The following is C source code exhibiting a common programming mistake. Once compiled, the program will generate a buffer overflow error if run with a command-line argument string that is too long, because this argument is used to fill a buffer without checking its length. [1]

/* overflow.c - demonstrates a buffer overflow */

#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: this is always incorrect but may not always result in a program error or segmentation fault. strncpy can be used to limit the number of characters copied to the buffer, but will fail to write a string terminator if the source string does not contain a string terminator within the specified number of bytes. In this case, an out-of-bounds access may occur when the buffer is later used. It is common to see calls to strncpy followed by an explicit assignment of a string terminator to prevent this.

This program could be safely rewritten using strncpy as follows: [1]

/* better.c - demonstrates one method of fixing 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';  /* explicitly write a string terminator */
  return 0;

[edit] 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.

[edit] 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,[2] 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.[3]

Stack-based buffer overflows are not to be confused with stack overflows.

[edit] Heap-based exploitation

Main article: Heap overflow

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.[4]

[edit] 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,[5] 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.

[edit] 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.

[edit] 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 through invalid pointers; 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.

[edit] 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 [6] and Erwin.[7] 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.[citation needed]

[edit] 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,[8] and the StackGuard[9] and ProPolice[10] gcc patches.

Microsoft's Data Execution Prevention mode explicitly protects the pointer to the SEH Exception Handler from being overwritten.[11]

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.

[edit] 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:

Newer variants of Microsoft Windows also support executable space protection, called Data Execution Prevention.[15] Proprietary add-ons include:

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.

[edit] 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.[18] A similar but less effective method is to rebase processes and libraries in the virtual address space.

[edit] 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.

[edit] 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.[19] Later, in 1995, Thomas Lopatic independently rediscovered the buffer overflow and published his findings on the Bugtraq security mailing list.[20] A year later, in 1996, Elias Levy (aka Aleph One) published in Phrack magazine the paper "Smashing the Stack for Fun and Profit",[21] 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[22] and in 2003 the SQL Slammer worm compromised machines running Microsoft SQL Server 2000. [23]

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.[24] The PS2 Independence Exploit also used a buffer overflow to achieve the same for the PlayStation 2.

[edit] See also

[edit] Notes

  1. ^ a b Safer C: Developing Software for High-integrity and Safety-critical Systems (ISBN 0-07-707640-0)
  2. ^ CORE-2007-0219: OpenBSD's IPv6 mbufs remote kernel buffer overflow. Retrieved on 2007-05-15.
  3. ^ The Metasploit Opcode Database. Retrieved on 2007-05-15.
  4. ^ Microsoft Technet Security Bulletin MS04-028. Retrieved on 2007-05-15.
  5. ^ Creating Arbitrary Shellcode In Unicode Expanded Strings. Retrieved on 2007-05-15.
  6. ^ The Vstr Homepage. Retrieved on 2007-05-15.
  7. ^ The Erwin Homepage. Retrieved on 2007-05-15.
  8. ^ Libsafe at FSF.org. Retrieved on 2007-05-20.
  9. ^ StackGuard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks by Cowan et al.. Retrieved on 2007-05-20.
  10. ^ ProPolice at X.ORG. Retrieved on 2007-05-20.
  11. ^ Bypassing Windows Hardware-enforced Data Execution Prevention. Retrieved on 2007-05-20.
  12. ^ PaX: Homepage of the PaX team. Retrieved on 2007-06-03.
  13. ^ KernelTrap.Org. Retrieved on 2007-06-03.
  14. ^ Openwall Linux kernel patch 2.4.34-ow1. Retrieved on 2007-06-03.
  15. ^ Microsoft Technet: Data Execution Prevention.
  16. ^ BufferShield: Prevention of Buffer Overflow Exploitation for Windows. Retrieved on 2007-06-03.
  17. ^ NGSec Stack Defender. Retrieved on 2007-06-03.
  18. ^ PaX at GRSecurity.net. Retrieved on 2007-06-03.
  19. ^ "A Tour of The Worm" by Donn Seeley, University of Utah. Retrieved on 2007-06-03.
  20. ^ Bugtraq security mailing list archive. Retrieved on 2007-06-03.
  21. ^ "Smashing the Stack for Fun and Profit" by Aleph One. Retrieved on 2007-06-03.
  22. ^ eEye Digital Security. Retrieved on 2007-06-03.
  23. ^ Microsoft Technet Security Bulletin MS02-039. Retrieved on 2007-06-03.
  24. ^ Hacker breaks Xbox protection without mod-chip. Retrieved on 2007-06-03.

[edit] External links

Personal tools