Last Updated: October 2003
Michael Ligh (michael.ligh@mnin.org)
Originally Published on Dr. Fred Cohen's all.net
If we are playing Jeopardy and the challenge is "a relatively easy mechanism for root access, data corruption, or denial of service," returning the question "What is an input overflow?" would be a strong decision. If we are not playing Jeopardy but still asking the same question, we are probably in trouble. The clear reasoning is that input overflows are as commonplace to computer exploits as guns are to homicide. They are easy to obtain, even easier to launch, and surrounded by potential victims. Input overflows are used to invoke a shell on the target system, plant trojans, install root kits, open sockets, or simply crash applications. In general, any code that can be executed by typing commands into a terminal can be executed by a carefully written overflow exploit. This research will present an introduction to the concept of overflowing a buffer, offer a quick demonstration, and discuss limitations and prevention techniques.
ii. Introduction to Input Buffer Overflows
For a process to accept data from external sources, it must reserve space for that data before it is received. This practice of allocating memory for general-purpose input often introduces a vulnerability when the data received exceeds the amount of space reserved. The effect is something similar to pouring a liter of liquid into a pint-sized glass - inevitably there is going to be a spill. In any case this creates a mess that must be cleaned up. When computer data spills, it lands in areas of memory reserved for some other purpose, or possibly for some other process. This too, is messy, often difficult to clean and time consuming.
A computer's memory is complex. Specific regions are used for specific tasks. The regions vary in size, location, and other attributes. Much like the ownership and permissions associated with individual files, regions of memory can belong to the system itself, a process running as root, or a process running as an unprivileged user. They may also be labeled writeable, read-only, and/or executable. Exploits commonly overwrite data on the program's data-dss region, heap, and stack, but the examples henceforth will focus on overflows that occur within the stack.
The basic idea behind overflows is to locate a bug in a program or subroutine that will allow attacker-supplied code to spill into one - or several - of these memory locations (preferably one owned by root). Depending on the nature of the code (random or meaningful), it may then redirect the CPU's instruction pointer to begin executing commands located within the exploited memory region. This is how attackers force a system to run any commands they provide. If the excess bytes are random instead, it normally results in data corruption, application crashes, or full system crashes.
iii. Stack-Based Input Buffer Overflows
Input buffers are contiguous blocks of memory located in regions such as a program's stack, [1]. In this case, they are allocated dynamically at run-time and consume predetermined, fixed amounts of space, [1] [3]. These are the pint-sized glasses, if you will. For instance, a program may declare an 8-element character array (also known as a buffer) to hold a user's login name. The program sets aside 8 bytes of memory, one for each of the 8 characters. If the user enters 15 characters and no bounds checking is employed, the excess 7 are written to an area of memory outside of the buffer (it has thus overflowed the buffer).
Where, exactly, these excess bytes end up and how the machine interprets them is our foremost concern. The diagram below, [3], shows the layout of a normal program stack. A stack is a writable area of memory that dynamically shrinks and grows as needed or determined by the program's execution, [5]. It is said to be dynamic because the data in this region is constantly changing as the process manipulates local variables, calls subroutines, and maintains flow control. The particular location in memory where the stack is working at a given instant is also dynamic, [2]. Data-integrity within the stack is vital to producing meaningful output and returning to the correct location when finished.
[bottom of memory][top of stack] .... +---------------------+ [lowest memory address] |local variables, e.g | | | | char login_name[8]; | | int overwrite_me=0; | | ..other variables.. | +---------------------+ | saved frame pointer | +---------------------| | return addr pointer | +---------------------+ | function parameters | +---------------------+ [highest memory address] .... [top of memory][bottom of stack]
Assume we wish to have some shell code executed on a system found to be vulnerable. This could be any machine running a program that accepts input and fails to verify its length before writing it to memory. The trick is to supply this program with a carefully selected (and overly long) sequence of bytes and cause them to spill out onto the stack. Data is written to the stack in the direction of higher memory addresses, or toward the top of memory, [1] [5] [6]. In this manner, the overflowed buffer will grow down - from the local variables to the function parameters (see diagram). If distances are calculated correctly, the return address field will be overwritten with a value that points back into the exploited buffer. This position indicates the place in system memory where the next instruction to execute resides. As a result, the CPU, without discretion and with the same privileges of the process that owned the original memory region, will resume execution on any instructions located therein.
This is a segment of code written in C with a typical buffer overflow coding error. It will show how excess input can be used overwrite a local variable when such errors exist.
main ()
{
char login_name[]={0,0,0,0,0,0,0,0};
int overwrite_me=0;
int ctr;
printf("\nEnter Login Name: ");
scanf("%s",&login_name);
printf("\n[variable] [address]\t\t[init]\t[now]");
for (ctr=0;ctr<8;ctr++)
printf("\nlogin_name[%i]
%i\t\t0\t%c",ctr,&login_name[ctr],login_name[ctr]);
printf("\noverwrite_me %i\t\t0\t%c",&overwrite_me,overwrite_me);
puts("");
}
The program declares an 8-element character buffer (all 0s) called login[]. It also reserves space for an integer variable named overwrite_me and initializes it to zero. Following the assignment of overwrite_me, no functions are called to manipulate its value, thus, after program execution it should still be zero. By examining the local variables segment of this program's stack (below) we can learn that the overwrite_me variable exists adjacent to, and directly below, the last space in the larger buffer.
bottom of memory / top of stack .... +---------------------+ [lowest memory address] |login_name[0] 0x12FF70| |login_name[1] 0x12FF71| |login_name[2] 0x12FF72| |login_name[3] 0x12FF73| |login_name[4] 0x12FF74| |login_name[5] 0x12FF75| |login_name[6] 0x12FF76| |login_name[7] 0x12FF77| |overwrite_me_ 0x12FF78 - 0x12FF79 |integer - ctr 0x12FF80 - 0x12FF81 +---------------------+ | saved frame pointer | - 0x12FF82 to 0x12FF85 +---------------------+ | return addr pointer | - 0x12FF86 to 0x12FF89 +---------------------+ | function parameters | +---------------------+ [highest memory address] .... top of memory / bottom of stack
The goal here is to fill the input buffer with 8 characters and use a 9th to replace the value of overwrite_me. We can supply the program with something like 123456789 when it prompts for a login name. Once entered, a function must be called from within the program to write these bytes into memory. The scanf function is a perfect choice for this purpose - it fails to do any sort of bounds checking or input validation. It simply assigns the received bytes to nine successive memory locations beginning at 0x12FF70. We can expect the first number we enter, 1, to be stored at this address. The next number, 2, is stored at 0x12FF71, the second space in the buffer. And so on. By entering 20* characters we would overwrite the return address value with bytes 17-20.
As we can see from the table below (the program's output), the 9th character falls outside of the 8-character buffer and lands in the space allocated for the least significant byte of overwrite_me, which it does indeed. The table shows the variable names and positions followed by their respective memory addresses**, initial values***, and values after the overflow.
[variable][address][init][now] login_name[0] 0x12FF70 0 1 login_name[1] 0x12FF71 0 2 login_name[2] 0x12FF72 0 3 login_name[3] 0x12FF73 0 4 login_name[4] 0x12FF74 0 5 login_name[5] 0x12FF75 0 6 login_name[6] 0x12FF76 0 7 login_name[7] 0x12FF77 0 8 overwrite_me_ 0x12FF78 0 9
*The number 20 corresponds to 8 bytes for the login[] buffer, 2 bytes for
each of the two integers (overwrite_me and ctr), and 4 bytes for each of the
pointers (frame and return address).
**Addresses were manually converted from decimal to hex for presentation.
***Initial values field is printed from numbers embedded in the source
code.
vi. Identification and Prevention of Input Overflows
Input overflows are essentially a result of sloppy programming, [2]. Programming languages such as C, which have no built-in bounds checking, allow this to happen. In particular, use of the following functions in a careless manner is commonly reponsible: fgets, gets, getws, memcpy, memmove, scanf, sprintf, strcat, strcopy, and vsprintf, [1] [2]. Inexperienced programmers can scan their source code with an automated code-checking tool before compiling and distributing it. Cigital's ITS4 and L0pht's SLINT have the capability to recognize potentially dangerous function calls, analyze the associated risks, and suggest ways to fix them, [2] [10].
A good start at defense against stack-based buffer overflows is to configure the system with a non-executable stack, [2]. This, however, does not prevent data corruption or denials of service as a result of overflowed buffers - it simply helps prevent the overflowed data from being executed, [7]. Likewise, it does not prevent execution of code from other memory regions, should it be placed somewhere other than the stack.
We can also try to defend the return pointer from being altered. When a function is called, something like StackGuard can place a "canary" word between the buffer and the return address field on the stack, [8]. Because of its location, when (if) the canary word is altered, this indicates an overflow attack is in progress. The program immediately halts execution; risking at maximum a temporary denial of service, [8].
Another defense, Shack Shield, protects the return pointer by copying its value into an un-overflowable area of memory during function prologs (or start of the procedure). On function epilogs (just before it finishes), if the two values are different, the system knows a modification took place. Similar to StackGuard, the running program is terminated to prevent rogue code from being executed.
Lastly, processes should not be run as root unless absolutely necessary. Removing root privileges from a processes will also prevent code on its exploited stack from being executing as root. It is important to realize that these defenses, even if applied together, do not guarantee immunity. For instance, an attacker could bypass StackGuard protection by altering other pointers in the program besides the return address, such as the function pointers and longjmp buffers, which need not even be on the stack, [11].
vii. Limitations and Challenges
Input overflows are operating system, application version, protocol, and encoding dependent, [6]. Accordingly, effective exploits require particularized knowledge of these features on the victim machine (else we must play the guessing game). One reason is a program's stack layout and location, as mentioned earlier, is dynamic. It will almost always differ among systems with non-identical configurations. If the code to be executed is lost in memory or we jump to an incorrect address trying to reach it, the exploitation attempt will fail.
There are at least two techniques attackers use to keep track of the code that spills. They will conduct heavy reconnaissance against the target, such as OS fingerprinting, service scans, and version mapping. Examining the source code of running applications usually follows if no exploits are already available. The attacker can use this as a reference, a blueprint, to estimate the stack and buffer positioning in memory.
The second technique involves surrounding the exploit code with NOPs. A NOP is an instruction that tells the CPU to wait a tick of its clock before proceeding. In this manner, the return pointer need not be aimed at the exact start address of the exploit code, [1] [2] [3]. It only needs to point somewhere within the string of NOPs, which are processed one by one until the exploit code is eventually reached, [1] [2] [3].
vii. Summary, Conclusions, and Futher Work
Input overflows allow attackers to manipulate the return address of a function, and thus change the flow of execution. The commands found at this new address are limited only by talented programmers' imaginations. Payload contents of an overflow may also be random. This will likely result in the vulnerable process returning incorrect output or trying to access memory locations that are invalid or do not exist. If an attacker's motive is to simply destroy data or crash applications on the vulnerable machine, this methodology is simple, quick, and effective.
There seems to be an equilibrium between the release of security patches and introduction of new exploits. In other words, with the abundance of software produced and the rate it is distributed, eliminating the world's input overflow vulnerabilities before new ones pop up is an impossibility. Unless every user verifies the source code of every program before installation (this is fiction at its best), input overflows will remain a likely source of their system's demise.
[1] Phrack Magazine Volume 7 Issue 49. Smashing The Stack For Fun and
Profit by Aleph1. Available www.phrack.org/phrack/49/P49-14
[2] Skoudis, Ed. Couter Hack A Step-by-Step Guide to Computer Attacks and
Effective Defenses. New Jersey: Prentice-Hall, Inc., 2002.
[3] Northcut, Steven, Mark Cooper, Matt Fearnow, and Karen Frederick. SANS
GIAC Intrusion Signatures and Analysis. Indiana: New Riders Publishing,
2002.
[4] Cheswick, William R., Steven M. Bellovin, and Aviel D. Ruben. Firewalls
and Internet Security, 2nd Ed: Repelling the Wily Hacker. Boston:
Addison-Wesley, 2003.
[4] Denning, Dorothy E. and Peter J. Denning. Internet Besieged: Countering
Cyberspace Scofflaws. Boston: Addison-Wesley, 1998.
[5] Litchfield, David. Exploiting Windows NT 4 Buffer Overruns, A Case Study:
RASMAN.EXE. Available: atstake.com/research/reports/wprasbuf.html
[6] Hoglund, Greg. Advanced Buffer Overflow Technique, Power Point
Presentation. Available:
www.blackhat.com/presentations/bh-asia-00/greg/greg-asia-00-stalking.ppt
[7] Solar Designer's Linux kernel patch (for a non-executable stack and other
security features). Available: www.openwall.com/linux/README.shtml
[8] StackGuard Compiler from Immunix.org - Adaptive System Viability.
Available: www.immunix.org
[9] Stack Shield - A "stack smashing" technique protection tool for Linux.
Available: www.angelfire.com/sk/stackshield/info.html
[10] Cigital's ITS4: Software Security Tool to scan source code for potential
vulnerabilites. Available: www.cigital.com/its4/
[11] Crispin Cowan, Steve Beattie, Ryan Finnin Day, Calton Pu, Perry Wagle
and Erik Walthinsen. Protecting Systems from Stack Smashing Attacks with
StackGuard. Available: www.immunix.org/StackGuard/lexpo99.pdf
[12] SQLExp SQL Server Worm Analysis by members of Symantec's DeepSight
Threat Management System. Avialable: http://securityresponse.symantec.com/avcenter/Analysis-SQLExp.pdf
[13] Internet Storm Center Analysis of OpenSSL Vulnerabilities. Available:
http://isc.incidents.org/analysis.html?id=167
[14] Perriot, Frederic, and Peter Szor. An Analysis of the Slapper Worm
Exploit, for Symantec Security Response. Available: http://securityresponse.symantec.com/avcenter/reference/analysis.slapper.worm.pdf
[15] The Computer Emergency and Reponse Team (CERT) Advisory Index.
Available: http://www.cert.org/advisories/
[16] An archive of expert white papers and publications on input overflows
offered by SecurityFocus. Available:
http://www.securityfocus.com/library/category/29