Buffer overflow
Encyclopedia
In computer security
and programming
, a buffer overflow, or buffer overrun, is an anomaly
where a program
, while writing data
to a buffer
, overruns the buffer's boundary and overwrites adjacent memory. This is a special case of violation of memory safety
.
Buffer overflows can be triggered by inputs that are designed to execute code, or alter the way the program operates. This may result in erratic program behavior, including memory access errors, incorrect results, a crash
, or a breach of system security. They are thus the basis of many software vulnerabilities and can be maliciously exploited
.
Programming language
s commonly associated with buffer overflows include C
and C++
, which provide no built-in protection against accessing or overwriting data in any part of memory and do not automatically check that data written to an array (the built-in buffer type) is within the boundaries of that array. Bounds checking
can prevent buffer overflows.
written to a buffer, due to insufficient bounds checking
, corrupts data values in memory address
es adjacent to the allocated buffer. Most commonly this occurs when copying strings
of characters
from one buffer to another.
Now, the program attempts to store the null-terminated string
in the A buffer. By failing to check the length of the string, it overwrites the value of B:
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.
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 exploitation on the call stack
.
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 character
s and the locations of these opcodes can vary 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.
Stack-based buffer overflows are not to be confused with stack overflow
s.
Also note that these vulnerabilities are usually discovered through the use of a fuzzer.
meta data) and uses the resulting pointer exchange to overwrite a program function pointer.
Microsoft
's GDI+
vulnerability in handling JPEG
s is an example of the danger a heap overflow can present.
s 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-libc attack
s. The same methods can be used to avoid detection by intrusion detection systems. In some cases, including where code is converted into unicode, 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.
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-ops 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.
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. It is important to note that a NOP-sled 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.
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 of 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.
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
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.
This method also allows shellcode to be placed after the overwritten return address on the Windows platform. Since executables are mostly based at address
, and often technical, business, or cultural constraints call for a vulnerable language. The following sections describe the choices and implementations available.
and its derivative, C++
, with a vast 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 a buffer is within the boundaries of that buffer. However, the standard C++ libraries provide many ways of safely buffering data, and techniques to avoid buffer overflows also exist for C.
Many other programming languages provide runtime checking and in some cases even compile-time checking which might send a warning or raise an exception
when C or C++ would overwrite data and continue to execute further instructions until erroneous results are obtained which might or might not cause the program to crash. Examples of such languages include Ada
, Eiffel
, Lisp, Modula-2
, Smalltalk
, Objective Caml
and such C-derivatives as Cyclone and D
. The Java and .NET Framework
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.
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 "The Better String Library", Vstr and Erwin. 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 2007, 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.
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, and the StackGuard and ProPolice gcc
patches.
Microsoft's Data Execution Prevention
mode explicitly protects the pointer to the SEH Exception Handler from being overwritten.
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 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.
Because XOR is linear, an attacker may be able to manipulate an encoded pointer by overwriting only the lower bytes of an address. This can allow an attack to succeed if the attacker is able to attempt the exploit multiple times and/or is able to complete an attack by causing a pointer to point to one of several locations (such as any location within a NOP sled). Microsoft added a random rotation to their encoding scheme to address this weakness to partial overwrites.
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 and writeable 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
. Proprietary
add-ons include:
Executable space protection does not generally protect against return-to-libc attack
s, or any other attack which does not rely on the execution of the attackers code. However, on 64-bit
systems using ASLR, as described below, executable space protection makes it far more difficult to execute such attacks.
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. A similar but less effective method is to rebase
processes and libraries in the virtual address space.
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. Shellcode
used by attackers can be made alphanumeric
, metamorphic
, or self-modifying
to evade detection by heuristic packet scanners and intrusion detection systems.
The earliest documented hostile 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 service on Unix
called finger
. Later, in 1995, Thomas Lopatic independently rediscovered the buffer overflow and published his findings on the Bugtraq
security mailing list. A year later, 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.
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 and in 2003 the SQL Slammer worm compromised machines running Microsoft SQL Server 2000.
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 for hardware modifications, known as modchip
s. The PS2 Independence Exploit also used a buffer overflow to achieve the same for the PlayStation 2
. The Twilight hack
accomplished the same with the Wii
, using a buffer overflow in The Legend of Zelda: Twilight Princess
.
Computer security
Computer security is a branch of computer technology known as information security as applied to computers and networks. The objective of computer security includes protection of information and property from theft, corruption, or natural disaster, while allowing the information and property to...
and programming
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, a buffer overflow, or buffer overrun, is an anomaly
Anomaly in software
In software testing, a software anomaly is anything that differs from expectation. This expectation can result from many things like from a document or from a person's view or experiences In software testing, a software anomaly is anything that differs from expectation. This expectation can...
where a program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
, while writing data
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
to a buffer
Buffer (computer science)
In computer science, a buffer is a region of a physical memory storage used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device or just before it is sent to an output device...
, overruns the buffer's boundary and overwrites adjacent memory. This is a special case of violation of memory safety
Memory safety
Memory safety is a concern in software development that aims to avoid software bugs that cause security vulnerabilities dealing with random-access memory access, such as buffer overflows and dangling pointers....
.
Buffer overflows can be triggered by inputs that are designed to execute code, or alter the way the program operates. This may result in erratic program behavior, including memory access errors, incorrect results, a crash
Crash (computing)
A crash in computing is a condition where a computer or a program, either an application or part of the operating system, ceases to function properly, often exiting after encountering errors. Often the offending program may appear to freeze or hang until a crash reporting service documents...
, or a breach of system security. They are thus the basis of many software vulnerabilities and can be maliciously exploited
Exploit (computer security)
An exploit is a piece of software, a chunk of data, or sequence of commands that takes advantage of a bug, glitch or vulnerability in order to cause unintended or unanticipated behavior to occur on computer software, hardware, or something electronic...
.
Programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s commonly associated with buffer overflows include C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, which provide no built-in protection against accessing or overwriting data in any part of memory and do not automatically check that data written to an array (the built-in buffer type) is within the boundaries of that array. Bounds checking
Bounds checking
In computer programming, bounds checking is any method of detecting whether a variable is within some bounds before its use. It is particularly relevant to a variable used as an index into an array to ensure its value lies within the bounds of the array...
can prevent buffer overflows.
Technical description
A buffer overflow occurs when dataData
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
written to a buffer, due to insufficient bounds checking
Bounds checking
In computer programming, bounds checking is any method of detecting whether a variable is within some bounds before its use. It is particularly relevant to a variable used as an index into an array to ensure its value lies within the bounds of the array...
, corrupts data values in memory address
Memory address
A digital computer's memory, more specifically main memory, consists of many memory locations, each having a memory address, a number, analogous to a street address, at which computer programs store and retrieve, machine code or data. Most application programs do not directly read and write to...
es adjacent to the allocated buffer. Most commonly this occurs when copying strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
of characters
Character (computing)
In computer and machine-based telecommunications terminology, a character is a unit of information that roughly corresponds to a grapheme, grapheme-like unit, or symbol, such as in an alphabet or syllabary in the written form of a natural language....
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 1979. Characters are one byte wide.| variable name | A | B | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| value | [ |
1979 | ||||||||
| hex value | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 07 | BB |
Now, the program attempts to store the null-terminated string
Null-terminated string
In computer programming, a null-terminated string is a character string stored as an array containing the characters and terminated with a null character...
in the A buffer. By failing to check the length of the string, it overwrites the value of B:
| variable name | A | B | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| value | 'e' | 'x' | 'c' | 'e' | 's' | 's' | 'i' | 'v' | 25856 | |
| hex | 65 | 78 | 63 | 65 | 73 | 73 | 69 | 76 | 65 | 00 |
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
Endianness
In computing, the term endian or endianness refers to the ordering of individually addressable sub-components within the representation of a larger data item as stored in external memory . Each sub-component in the representation has a unique degree of significance, like the place value of digits...
system that uses ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
, "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
Segmentation fault
A segmentation fault , bus error or access violation is generally an attempt to access memory that the CPU cannot physically address. It occurs when the hardware notifies an operating system about a memory access violation. The OS kernel then sends a signal to the process which caused the exception...
, terminating the process.
Exploitation
The techniques to exploitExploit (computer security)
An exploit is a piece of software, a chunk of data, or sequence of commands that takes advantage of a bug, glitch or vulnerability in order to cause unintended or unanticipated behavior to occur on computer software, hardware, or something electronic...
a buffer overflow vulnerability vary per architecture
Computer architecture
In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....
, operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
and memory region. For example, exploitation on the heap (used for dynamically allocated memory), is very different from exploitation on the call stack
Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the 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, 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
Opcode
In computer science engineering, an opcode is the portion of a machine language instruction that specifies the operation to be performed. Their specification and format are laid out in the instruction set architecture of the processor in question...
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
Dynamic-link library
Dynamic-link library , or DLL, is Microsoft's implementation of the shared library concept in the Microsoft Windows and OS/2 operating systems...
or the executable itself. However the address of the opcode typically cannot contain any null character
Null character
The null character , abbreviated NUL, is a control character with the value zero.It is present in many character sets, including ISO/IEC 646 , the C0 control code, the Universal Character Set , and EBCDIC...
s and the locations of these opcodes can vary between applications and versions of the operating system. The Metasploit Project
Metasploit Project
The Metasploit Project is an open-source computer security project which provides information about security vulnerabilities and aids in penetration testing and IDS signature development....
is one such database of suitable opcodes, though only those found in the Windows
Microsoft Windows
Microsoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
operating system are listed.
Stack-based buffer overflows are not to be confused with stack overflow
Stack overflow
In software, a stack overflow occurs when too much memory is used on the call stack. The call stack contains a limited amount of memory, often determined at the start of the program. The size of the call stack depends on many factors, including the programming language, machine architecture,...
s.
Also note that these vulnerabilities are usually discovered through the use of a fuzzer.
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 mallocMalloc
C dynamic memory allocation refers to performing dynamic memory allocation in the C via a group of functions in the C standard library, namely malloc, realloc, calloc and free....
meta data) and uses the resulting pointer exchange to overwrite a program function pointer.
Microsoft
Microsoft
Microsoft Corporation is an American public multinational corporation headquartered in Redmond, Washington, USA that develops, manufactures, licenses, and supports a wide range of products and services predominantly related to computing through its various product divisions...
's GDI+
Graphics Device Interface
The Graphics Device Interface is a Microsoft Windows application programming interface and core operating system component responsible for representing graphical objects and transmitting them to output devices such as monitors and printers....
vulnerability in handling JPEG
JPEG
In computing, JPEG . The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality. JPEG typically achieves 10:1 compression with little perceptible loss in image quality....
s is an example of the danger a heap overflow can present.
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 metacharacterMetacharacter
A metacharacter is a character that has a special meaning to a computer program, such as a shell interpreter or a regular expression engine.-Examples:...
s and filtering out of non-alphanumeric
Alphanumeric
Alphanumeric is a combination of alphabetic and numeric characters, and is used to describe the collection of Latin letters and Arabic digits or a text constructed from this collection. There are either 36 or 62 alphanumeric characters. The alphanumeric character set consists of the numbers 0 to...
strings. However, techniques exist to bypass these filters and manipulations; alphanumeric code
Alphanumeric code
In general, in computing, an alphanumeric code is a series of letters and numbers which are written in a form that can be processed by a computer....
, polymorphic code
Polymorphic code
In computer terminology, polymorphic code is code that uses a polymorphic engine to mutate while keeping the original algorithm intact. That is, the code changes itself each time it runs, but the function of the code will not change at all...
, self-modifying code
Self-modifying code
In computer science, self-modifying code is code that alters its own instructions while it is executing - usually to reduce the instruction path length and improve performance or simply to reduce otherwise repetitively similar code, thus simplifying maintenance...
and return-to-libc attack
Return-to-libc attack
A return-to-libc attack is a computer security attack usually starting with a buffer overflow in which the return address on the stack is replaced by the address of another instruction and an additional portion of the stack is overwritten to provide arguments to this function...
s. The same methods can be used to avoid detection by intrusion detection systems. In some cases, including where code is converted into unicode, 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 challenges which need to be overcome for exploits to operate reliably. These factors include null bytes in addresses, variability in the location of shellcode, differences between environments and various counter-measures in operation.NOP sled technique
A NOP-sled is the oldest and most widely known technique for successfully exploiting a stack buffer overflow. It solves the problem of finding the exact address of 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, an instruction to perform a relative jump to the top of the buffer where the shellcodeShellcode
In computer security, a shellcode is a small piece of code used as the payload in the exploitation of a software vulnerability. It is called "shellcode" because it typically starts a command shell from which the attacker can control the compromised machine. Shellcode is commonly written in...
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-ops 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.
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. It is important to note that a NOP-sled 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.
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
System administrator
A system administrator, IT systems administrator, systems administrator, or sysadmin is a person employed to maintain and operate a computer system and/or network...
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 of 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 address stored in a 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.Opcode
In computer science engineering, an opcode is the portion of a machine language instruction that specifies the operation to be performed. Their specification and format are laid out in the instruction set architecture of the processor in question...
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. 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.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.
This method also allows shellcode to be placed after the overwritten return address on the Windows platform. Since executables are mostly 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 codeLegacy code
Legacy code is source code that related to a no-longer supported or manufactured operating system or other computer technology. The term can also mean code inserted into modern software for the purpose of maintaining an older or previously supported feature — for example supporting a serial...
, 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. , among the most popular languages are CC (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and its derivative, C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, with a vast 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 a buffer is within the boundaries of that buffer. However, the standard C++ libraries provide many ways of safely buffering data, and techniques to avoid buffer overflows also exist for C.
Many other programming languages provide runtime checking and in some cases even compile-time checking which might send a warning or raise an exception
Exception handling
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
when C or C++ would overwrite data and continue to execute further instructions until erroneous results are obtained which might or might not cause the program to crash. Examples of such languages include Ada
Ada (programming language)
Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
, Eiffel
Eiffel (programming language)
Eiffel is an ISO-standardized, object-oriented programming language designed by Bertrand Meyer and Eiffel Software. The design of the language is closely connected with the Eiffel programming method...
, Lisp, Modula-2
Modula-2
Modula-2 is a computer programming language designed and developed between 1977 and 1980 by Niklaus Wirth at ETH Zurich as a revision of Pascal to serve as the sole programming language for the operating system and application software for the personal workstation Lilith...
, Smalltalk
Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
, Objective Caml
Objective Caml
OCaml , originally known as Objective Caml, is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996...
and such C-derivatives as Cyclone and D
D (programming language)
The D programming language is an object-oriented, imperative, multi-paradigm, system programming language created by Walter Bright of Digital Mars. It originated as a re-engineering of C++, but even though it is mainly influenced by that language, it is not a variant of C++...
. The Java and .NET Framework
.NET Framework
The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
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
Static code analysis
Static program analysis is the analysis of computer software that is performed without actually executing programs built from that software In most cases the analysis is performed on some version of the source code and in the other cases some form of the object code...
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. It has also long been recommended to avoid standard library functions which are not bounds checked, such asgets, scanfScanfScanf format string refers to a control parameter used by a class of functions typically associated with some types of programming languages. The format string specifies a method for reading a string into an arbitrary number of varied data type parameter...
and strcpy. The Morris worm exploited a gets call in fingerd.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 "The Better String Library", Vstr and Erwin. The OpenBSD
OpenBSD
OpenBSD is a Unix-like computer operating system descended from Berkeley Software Distribution , a Unix derivative developed at the University of California, Berkeley. It was forked from NetBSD by project leader Theo de Raadt in late 1995...
operating system's C library provides the strlcpy and strlcat functions, but these are more limited than full safe library implementations.
In September 2007, 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.
Buffer overflow protection
Buffer overflow protection is used to detect the most common buffer overflows by checking that the stackCall stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...
has not been altered when a function returns. If it has been altered, the program exits with a segmentation fault
Segmentation fault
A segmentation fault , bus error or access violation is generally an attempt to access memory that the CPU cannot physically address. It occurs when the hardware notifies an operating system about a memory access violation. The OS kernel then sends a signal to the process which caused the exception...
. Three such systems are Libsafe, and the StackGuard and ProPolice gcc
GNU Compiler Collection
The GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...
patches.
Microsoft's Data Execution Prevention
Data Execution Prevention
Data Execution Prevention is a security feature included in modern operating systems.It is known to be available in Linux, Mac OS X, and Microsoft Windows operating systems and is intended to prevent an application or service from executing code from a non-executable memory region. This helps...
mode explicitly protects the pointer to the SEH Exception Handler from being overwritten.
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 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.
Pointer protection
Buffer overflows work by manipulating pointers (including stored addresses). PointGuard was proposed as a compiler-extension to prevent attackers from being able to reliably manipulate pointers and addresses. The approach works by having the compiler add code to automatically XOR-encode pointers before and after they are used. Because the attacker (theoretically) does not know what value will be used to encode/decode the pointer, he cannot predict what it will point to if he overwrites it with a new value. PointGuard was never released, but Microsoft implemented a similar approach beginning in Windows XP SP2 and Windows Server 2003 SP1. Rather than implement pointer protection as an automatic feature, Microsoft added an API routine that can be called at the discretion of the programmer. This allows for better performance (because it is not used all of the time), but places the burden on the programmer to know when it is necessary.Because XOR is linear, an attacker may be able to manipulate an encoded pointer by overwriting only the lower bytes of an address. This can allow an attack to succeed if the attacker is able to attempt the exploit multiple times and/or is able to complete an attack by causing a pointer to point to one of several locations (such as any location within a NOP sled). Microsoft added a random rotation to their encoding scheme to address this weakness to partial overwrites.
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
NX bit
The NX bit, which stands for No eXecute, is a technology used in CPUs to segregate areas of memory for use by either storage of processor instructions or for storage of data, a feature normally only found in Harvard architecture processors...
("No eXecute") or XD ("eXecute Disabled") bit, which in conjunction with software, can be used to mark pages of data
Paging
In computer operating systems, paging is one of the memory-management schemes by which a computer can store and retrieve data from secondary storage for use in main memory. In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called...
(such as those containing the stack and the heap) as readable and writeable but not executable.
Some Unix operating systems (e.g. OpenBSD
OpenBSD
OpenBSD is a Unix-like computer operating system descended from Berkeley Software Distribution , a Unix derivative developed at the University of California, Berkeley. It was forked from NetBSD by project leader Theo de Raadt in late 1995...
, Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
) ship with executable space protection (e.g. W^X
W^X
W^X is the name of a security feature present in the OpenBSD operating system. It is a memory protection policy whereby every page in a process' address space is either writable or executable, but not both simultaneously...
). Some optional packages include:
- PaXPaXPaX is a patch for the Linux kernel that implements least privilege protections for memory pages. The least-privilege approach allows computer programs to do only what they have to do in order to be able to execute properly, and nothing more. PaX was first released in 2000.PaX flags data memory as...
- Exec ShieldExec ShieldExec Shield is a project started at Red Hat, Inc in late 2002 with the aim of reducing the risk of worm or other automated remote attacks on Linux systems. The first result of the project was a security patch for the Linux kernel that emulates an NX bit on x86 CPUs that lack a native NX...
- Openwall
Newer variants of Microsoft Windows also support executable space protection, called Data Execution Prevention
Data Execution Prevention
Data Execution Prevention is a security feature included in modern operating systems.It is known to be available in Linux, Mac OS X, and Microsoft Windows operating systems and is intended to prevent an application or service from executing code from a non-executable memory region. This helps...
. Proprietary
Proprietary software
Proprietary software is computer software licensed under exclusive legal right of the copyright holder. The licensee is given the right to use the software under certain conditions, while restricted from other uses, such as modification, further distribution, or reverse engineering.Complementary...
add-ons include:
- BufferShield
- StackDefender
Executable space protection does not generally protect against return-to-libc attack
Return-to-libc attack
A return-to-libc attack is a computer security attack usually starting with a buffer overflow in which the return address on the stack is replaced by the address of another instruction and an additional portion of the stack is overwritten to provide arguments to this function...
s, or any other attack which does not rely on the execution of the attackers code. However, on 64-bit
64-bit
64-bit is a word size that defines certain classes of computer architecture, buses, memory and CPUs, and by extension the software that runs on them. 64-bit CPUs have existed in supercomputers since the 1970s and in RISC-based workstations and servers since the early 1990s...
systems using ASLR, as described below, executable space protection makes it far more difficult to execute such attacks.
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
Virtual memory
In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various forms of computer data storage , allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which...
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. A similar but less effective method is to rebase
Rebasing
In computing, rebasing is one of the following:* The process of creating a shared library image in such a way that it is guaranteed to use virtual memory without conflicting with any other shared libraries loadable in the system. This technique is used extensively on Win32 platforms to avoid the...
processes and libraries in the virtual address space.
Deep packet inspection
The use of deep packet inspection (DPI) can detect, at the network perimeter, very basic 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 instructions (known as a nop-sled) is detected, these were once used when the location of the exploit's payloadPayload (software)
Payload in computing is the cargo of a data transmission. It is the part of the transmitted data which is the fundamental purpose of the transmission, to the exclusion of information sent with it solely to facilitate delivery.In computer security, payload refers to the...
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. Shellcode
Shellcode
In computer security, a shellcode is a small piece of code used as the payload in the exploitation of a software vulnerability. It is called "shellcode" because it typically starts a command shell from which the attacker can control the compromised machine. Shellcode is commonly written in...
used by attackers can be made alphanumeric
Alphanumeric code
In general, in computing, an alphanumeric code is a series of letters and numbers which are written in a form that can be processed by a computer....
, metamorphic
Metamorphic code
In computer virus terms, metamorphic code is code that can reprogram itself. Often, it does this by translating its own code into a temporary representation, editing the temporary representation of itself, and then writing itself back to normal code again. This procedure is done with the virus...
, or self-modifying
Self-modifying code
In computer science, self-modifying code is code that alters its own instructions while it is executing - usually to reduce the instruction path length and improve performance or simply to reduce otherwise repetitively similar code, thus simplifying maintenance...
to evade detection by heuristic packet scanners and intrusion detection systems.
History
Buffer overflows were understood and partially publicly documented as early as 1972, when the Computer Security Technology Planning Study laid out the technique: "The code performing this function does not check the source and destination addresses properly, permitting portions of the monitor to be overlaid by the user. This can be used to inject code into the monitor that will permit the user to seize control of the machine." (Page 61) Today, the monitor would be referred to as the kernel.The earliest documented hostile 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 service on Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
called finger
Finger protocol
In computer networking, the Name/Finger protocol and the Finger user information protocol are simple network protocols for the exchange of human-oriented status and user information.-Name/Finger protocol:...
. Later, in 1995, Thomas Lopatic independently rediscovered the buffer overflow and published his findings on the Bugtraq
Bugtraq
Bugtraq is an electronic mailing list dedicated to issues about computer security. On-topic issues are new discussions about vulnerabilities, vendor security-related announcements, methods of exploitation, and how to fix them...
security mailing list. A year later, in 1996, Elias Levy
Elias Levy
Elias Levy , was the moderator of the full disclosure vulnerability mailing list Bugtraq from May 14, 1996, until he stepped down on October 15, 2001. He was the CTO and co-founder of the computer security company SecurityFocus, which was acquired by Symantec on August 6, 2002...
(aka Aleph One) published in Phrack
Phrack
Phrack is an ezine written by and for hackers first published November 17, 1985. Described by Fyodor as "the best, and by far the longest running hacker zine," the magazine is open for contributions by anyone who desires to publish remarkable works or express original ideas on the topics of interest...
magazine the paper "Smashing the Stack for Fun and Profit", 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
Internet Information Services
Internet Information Services – formerly called Internet Information Server – is a web server application and set of feature extension modules created by Microsoft for use with Microsoft Windows. It is the most used web server after Apache HTTP Server. IIS 7.5 supports HTTP, HTTPS,...
(IIS) 5.0 and in 2003 the SQL Slammer worm compromised machines running Microsoft SQL Server 2000.
In 2003, buffer overflows present in licensed Xbox
Xbox
The Xbox is a sixth-generation video game console manufactured by Microsoft. It was released on November 15, 2001 in North America, February 22, 2002 in Japan, and March 14, 2002 in Australia and Europe and is the predecessor to the Xbox 360. It was Microsoft's first foray into the gaming console...
games have been exploited to allow unlicensed software, including homebrew games
Homebrew (video games)
Homebrew is a term frequently applied to video games or other software produced by consumers to target proprietary hardware platforms not typically user-programmable or that use proprietary storage methods...
, to run on the console without the need for hardware modifications, known as modchip
Modchip
A modchip is a small electronic device used to modify or disable built-in restrictions and limitations of computers, specifically videogame consoles...
s. The PS2 Independence Exploit also used a buffer overflow to achieve the same for the PlayStation 2
PlayStation 2
The PlayStation 2 is a sixth-generation video game console manufactured by Sony as part of the PlayStation series. Its development was announced in March 1999 and it was first released on March 4, 2000, in Japan...
. The Twilight hack
Twilight hack
The Twilight hack is the name given to the exploit found by Team Twiizers of in The Legend of Zelda: Twilight Princess that permits homebrew developers and everyday users to run unofficial homebrew software from a Secure Digital card inserted into the slot on the front of the Wii...
accomplished the same with the Wii
Wii
The Wii is a home video game console released by Nintendo on November 19, 2006. As a seventh-generation console, the Wii primarily competes with Microsoft's Xbox 360 and Sony's PlayStation 3. Nintendo states that its console targets a broader demographic than that of the two others...
, using a buffer overflow in The Legend of Zelda: Twilight Princess
The Legend of Zelda: Twilight Princess
is an action-adventure game developed by Nintendo Entertainment Analysis and Development, and published by Nintendo for the GameCube and Wii video game consoles. It is the thirteenth installment in The Legend of Zelda series...
.
External links
- "Discovering and exploiting a remote buffer overflow vulnerability in an FTP server" by Raykoid666
- "Smashing the Stack for Fun and Profit" by Aleph One
- 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
- "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.
- Computer Security Technology Planning Study, James P. Anderson, ESD-TR-73-51, ESD/AFSC, Hanscom AFB, Bedford, MA 01731 (October 1972) [NTIS AD-758 206]