Wikipedia

Buffer overflow

This is an old revision of this page, as edited by 80.221.26.157 (talk) at 15:12, 24 February 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer programming, a buffer overflow is an anomalous condition where a program somehow writes data beyond the allocated end of a buffer in memory. Buffer overflows usually arise as a consequence of a bug and the use of c or c++. One ramification of the overflow is that valid data can be overwritten as a result. Buffer overflows are also a commonly exploited computer security risk—since program control data often sits in the memory areas adjacent to data buffers, by means of a buffer overflow condition the computer can be made to execute arbitrary (and potentially malicious) code that is fed to the buggy program as data.

Security ramifications

A program which takes advantage of a vulnerability to subvert another program's security is called an exploit and is usually intended to gain access to superuser or otherwise escalated privileges. A buffer overflow exploit works by feeding the program specially crafted input content which is designed to overflow the allocated data storage buffer and change the data that follows the buffer in memory.

For example, imagine a hypothetical program that executes with superuser privileges in order to perform some system administrative function such as changing a user password. If the program fails to ensure that the length of the new password entered is equal to or smaller than the data buffer allocated for its storage, then any overflow data will simply be written over whatever happens to be after the data buffer. If this post-buffer area is executable code, a malicious user can insert machine language instructions that can perform any function normally requiring root privileges — add users, delete users, change passwords, alter or delete any file, etc.

Properly written programs ought to check the length of input data, to ensure that it is not larger than the allocated data buffer, but this is frequently overlooked, especially by novice programmers. Buffer overflows are most easily exploited when the data buffer is in the program stack, since this can lead directly to an alteration of the program's execution path.

Determining the exploitability of a buffer overflow vulnerability can be difficult even for experienced programmers, since it involves a lot of high and low level knowledge of the architecture internals and the target program. Overflows of as little as a single byte beyond the end of a buffer have proved to be exploitable.

Generally, the buffer overflow problem is caused by careless programming. Avoiding them is still a manual process as most formal verification systems have yet proven unattainable in modern programming languages. Buffer overflows are common only in programs written in relatively low-level programming languages, such as assembly language, C, and C++ which require the programmer to manually manage the size of allocated memory. Many programming languages such as Java and Lisp manage memory allocation automatically, and use a combination of run time checking and static analysis to make it difficult or impossible to code a buffer overflow bug. Perl provides for automatic resizing of the arrays to avoid buffer overflows. However, runtime systems and libraries for such languages may still occasionally have buffer overflows due to internal implementation errors in these checking systems.

Technical rundown

Description

A more technical view of this would be best explained by using C or C++ as an example. This is based around x86 architectures, but works for many others.

Basically, when a dynamic buffer or automatic array is allocated in a function, it is allocated at function call time on the stack. Writing data to the buffer can write beyond it on the stack. Also, the stack grows from bottom up (or from right to left, depending on perspective). Here, (DATA) (DATA) (...) represents the existing stack, and (NEWDATA) is some new value the CPU has pushed onto the stack: 

(NEWDATA)(DATA)(DATA)(...)

When a C program executes a subroutine, it pushes the return address onto the stack, so the subroutine knows where to return control to when it has finished: 

(ADDR)(DATA)(DATA)(...)

When a dynamic buffer is allocated, the stack grows left by however big the buffer is. So, if a function starts with a 'char a[10]' declaration, the result is: 

(a.........)(ADDR)(DATA)(DATA)(...)

At the end of the function, the buffers are deallocated, everything pushed is popped, and a RET operation is called. This pops the return address off the stack and jumps there, shifting program control back to wherever the subroutine was called from.

Suppose that 10 byte buffer is intended to hold user input (a new password, for example.) If the program fails to specifically check the number of characters the user has entered, and writes 14 bytes to the buffer, the extra data will clobber the return address, overwriting part of it with the extra data. This changes where program control will go to continue execution when the subroutine has finished.

If the user is not malicious and enters more than 10 characters, the extra data will effectively be random, and will probably end up making the return address point to an area in memory which is not under the control of the currently executing program, causing a segmentation fault on Unix architectures (or an analogous error on other operating systems) when the RET instruction attempts to jump control there.

If a technically inclined user is malicious, they can ensure that the extra data does indeed point to a valid memory address, causing program control to be shifted to this ___location of their choosing, and potentially executing whatever arbitrary code the user has caused to be in that ___location with whatever privileges the currently executing program has.

Example

A practical example of a buffer overflow written in C is: 

#-------overflow.c
# Reads data from the command line and stores
# them in buffer
#
#include <stdio.h>

int main(int argc, char **argv)
{
   char buffer[10];
   if(argc<2)
   {
      printf("Usage: %s <characters>.\n", argv[0]);
      exit(1);
   }
   strcpy(buffer,argv[1]);
   printf("Characters typed: %s", buffer);
   return(0);
}

By executing that example in a Unix-compatible system, with an argument of 10 or less bytes, we have the following result: 

poli@etacarinae:/tmp$ ./overflow Hello_World!
Characters typed: Hello_World!

Now if the line contained more than 10 characters as the first argument, the following would result: 

poli@etacarinae:/tmp$ ./overflow 12345678910111213141516171819
Characters typed: 12345678910111213141516171819
Segmentation fault

The correction for the overflow in the previous example could be achieved by not using the strcpy function, but strncpy instead. The latter copies a fixed number of characters (in this example), avoiding the extra characters typed.

Prevention

Various techniques have been used to make buffer overflows less likely.

Intrusion-detection software

The use of Intrusion Detection Software can detect remote attempts to use buffer overflows. Since most buffer overflows contain a long array of instructions that have No OPeration (NOP's) or (NOOP's), the IDS just has to block all incoming packets containing a large number of consecutive NOP's. Recently, crackers have begun to use alphanumeric, polymorphic, and self-modifying shellcodes to slip through these IDS systems.

Stack-smashing protection

Stack-smashing protection is used to detect the most common buffer overflows by checking that the stack has not been altered when a function returns. If it has been altered, the program exits with a segmentation fault.

Two such systems are StackGuard and ProPolice, both of which are extensions to gcc. As of gcc-3.3.3, neither patch seems to have been incorporated into the mainline distribution. Gentoo Linux and OpenBSD supply ProPolice by default with gcc.

Putting the return address on the data stack makes it easy for a buffer overflow to lead to executing arbitrary code. In theory, gcc could be patched to place the return address on a return stack completely separate from the data stack, reminiscent of the Forth programming language.

See:

Executable space protection

Protecting the executable space may soften the blow of buffer overflow exploits by making most of their operations impossible. This is done by randomizing the address space (ASLR) and making sure memory is not writable and executable. A non-executable stack will stave off most shellcode exploits.

Two patches for the Linux kernel that accomplish this are PaX and exec-shield. Neither of these are yet included in the mainstream kernel. OpenBSD since 3.3 has included a system called W^X, which provides executable space control as well.

Note that this manner of protection will not prevent stack smashing; however, it will often prevent the payload from being successfully delivered. The program will not be able to inject shellcode into non-writable memory, such as the existing code segments. It also will not be able to execute non-executable memory, such as the stack or the heap.

ASLR will make ret2libc type attacks a very difficult guessing game. They are still possible in a controlled environment, or if the attacker guesses correctly.

Some CPUs such as Sun's Sparc, Transmeta's Efficeon, and newer 64-bit Intel and AMD x86 processors prevent code from being executed on areas of memory flagged with a special NX bit.

Choice of programming language

The choice of programming language can have a profound effect on the existence of buffer overflows. As of 2004, the most popular languages generally are C and its derivative, C++. Languages such as these do not check that data, when written to an array (the implementation of a buffer), is within the assumed boundaries of the array. Other programming languages differ in this regard, sending a warning or raising an exception when such a data assignment is made. Examples of such languages are Java and Pascal and its descendants such as Modula-2, Oberon, and Ada; there are many other such languages. Part of the original rationale for choosing C is that it is "fast," in part because it does not take processor time to do such boundary checking; however, tests have shown that the amount of time added in checking array boundaries does not usually represent a burdensome overhead. In an era of fast processors (relative to the most common tasks, c. 2004), that original tradeoff of speed versus safety might be reconsidered. Such language features remain an ongoing debate among some within the software design community.

History

In 1988, the Morris worm used a buffer overflow in a Unix program called finger to propagate itself over the Internet. Even after this incident, buffer overflows were virtually ignored as security issue. Later, in 1995, Thomas Lopatic independently reinvented the buffer overflow and published his findings on the Bugtraq security mailing list, which caused a wave of new security relevant buffer overflows to be found. In 1996, Elias Levy (aka Aleph One) published in Phrack magazine the paper "Smashing the Stack for Fun and Profit", a step-by-step introduction to exploiting stack-based buffer overflow vulnerabilities, which caused a wave of new buffer overflow exploits to be written.

See also

Retrieved from "https://en.wikipedia.org/w/index.php?title=Buffer_overflow&oldid=10610841"