"Of course, buffer overflows are fashionable this year. Perhaps
next year it'll be something else."
- Kragen ([email protected])0
A buffer overflow: it's an easy enough mistake to make. And as the Jargon File puts it, buffer overflows are the source of "some of the most insidious data-dependent bugs known to mankind"1 Yet buffer overflows are more than just a source of frustration for programmers. Indeed, they can create serious security holes, introducing vulnerabilities which can be exploited to achieve a denial of service or in some cases, to gain access and/or increased privileges on a system.
Buffer overflows attacks are nothing new. The Internet Worm, written and released by Robert T. Morris in 1988, employed the first well-known buffer overflow attack. The Worm, which infected thousands of systems on the Internet, exploited a buffer overflow in the finger daemon to gain access to VAX machines running BSD Unix.2 Even before the Worm's release, buffer overflow attacks may have known in some circles - there is anecdotal evidence of buffer overflow attacks dating back to the 1960's.3
Even so, prior to 1997, buffer overflow vulnerabilities were only periodically discovered and never in such numbers as to attract too much attention. In recent years, however, buffer overflows have become the most commonly discovered class of vulnerability, and unfortunately, the most widely exploited. In fact, 24 of the 44 CERT advisories issued since January 1, 1997, have involved some type of buffer overflow attack.4 Buffer overflow vulnerabilities therefore represent a class of security problem of great importance to computer users, whether they be programmers, system administrators or users.
The aim of this paper is to provide a limited technical introduction to buffer overflows and how they are exploited. The focus will be on the "classic" stack-based buffer overflow attacks in Unix-like operating systems, as these are relatively straightforward to understand and regrettably, quite common. Some attention will also be given to heap-based buffer overflow attacks and buffer overflow attacks in the Windows family of operating systems. Finally, certain countermeasures for protecting systems and code from buffer overflow attacks will be examined, and some guidelines for writing more secure code will be discussed.
In the most common usage, a buffer is an array - a collection of identically typed data items stored in contiguous memory locations.5 Most C programmers associate buffers with arrays of characters (i.e. a string). To overflow a buffer is simply to place more data in the buffer than it can contain. In the absence of bounds checking (which is the case with most C compilers) the extra data will "overflow" into memory locations above the end of the buffer and consequently, will overwrite any variables which are stored there.
The stack is a concept with which most computer science students should be familiar. Objects are placed (pushed) on to the stack and retrieved (popped) in a last-in-first-out (LIFO) fashion. In a process, a stack is used to store automatic variables; that is, variables which are allocated only for the duration of the subroutine in which they are declared. More importantly for the attack we will describe here, the stack is also used during subroutine linkage. When a subroutine is called, it pushes the return address (the address to which it must return when it is finished) on to the stack. When it returns, it retrieves this saved value from the stack and jumps to that address. On most common architectures (x86/Pentium, SPARC, MIPS, Alpha) the stack grows down; that is, variables pushed on to the stack are stored in memory locations lower than those of older values.
Having defined our terms, we turn to a discussion of the "classic" stack-based buffer overflow. Consider the following program:6
/* stack-overflow.c - Stack-based buffer overflow example */
#include <stdlib.h>
#define BUFSIZE 100
void foo(char *bar) {
/* allocate an automatic buffer */
char BUF[BUFSIZE];
/* copy bar into BUF */
strcpy(BUF, bar);
/* print it */
printf("%s\n", BUF);
}
int main() {
char *baz;
/* retrieve a pointer to the contents of the HOME environment variable */
baz = getenv("HOME");
foo(baz);
exit(0);
}
At first glance, this program, while exceedingly boring and not particularly efficient, seems innocent enough - it simply retrieves and prints the HOME environment variable. Yet it illustrates a number of important points quite well:
When foo() is called, it must first place the return address (the address of the instruction which follows the call to foo()) on the stack. Otherwise, the return address, which is normally stored in a register, will be overwritten when strcpy() is called and foo() will be unable to return program control to where it left off in main().
Next, 100 bytes of memory are allocated on the stack to store the contents of BUF. Since we assume the stack grows down, these memory locations are lower than the memory location which stores the saved return address.
The third step is to call the strcpy() function, which copies bytes into BUF. The strcpy() function pays no attention to the size of the source or destination buffers - it simply continues copying until it reaches an ASCII 0 value in the source buffer.
As the printf() call is just there for illustration, we'll ignore it.
Finally, foo() exits. At this point, the contents of BUF are discarded,7 the saved return address is popped off of the stack and the program jumps back into main(). Since there's nothing left to do, we call exit() and the program terminates.
Under normal circumstances, the above program should run quite happily. But now consider what happens if we run this program under abnormal circumstances. Assume, for example, that the HOME environment variable, which is normally no more than 20 or 30 characters, contains 500 characters. In this case, things will not run so smoothly - in fact, if one attempts to run this program under these conditions, the most likely result will be a segmentation violation and the program will be terminated by the operating system.
The explanation for this should be intuitively obvious - trying to jam 500 characters into a buffer that can hold only 100 is certain to cause some problems. Specifically, the strcpy() function, which neither knows nor cares how big BUF is, will simply copy bytes into BUF until it reaches the ASCII 0 character in the source buffer. As the saved return address is located on the stack at a higher memory address than BUF, its value will be overwritten by something from the HOME environment variable. Thus, when the function pops the return address off of the stack prior to returning, this value will be garbage. The function then tries to jump to this garbage address, which is most likely outside the process' address space, resulting in a segmentation violation.
Now, consider what would happen if we could set this value so that it was somewhere within the process' address space. In this case, program flow would continue, though it might not get too far before other problems occur.8 This is the security problem which buffer overflows create, since if an attacker can alter the flow of control within a program, she can redirect it to her own code, which can then do something to compromise the system.
In the classic stack-based buffer overflow attack, the attacker must accomplish a number of things:
Firstly, she must insert the code that she wishes to execute (in the vernacular, the "egg") into the process' address space. Usually, this code is something very simple, often no more than one or two lines of C code which exec()'s a shell or alters a sensitive file. The most common techniques are to place this code in the buffer that is being overflowed or if that buffer is too small, to place it in an environment variable stored higher up (in terms of memory addresses) on the stack.
Next, in order for this code to be executed, the attacker must overwrite the saved return address with the address of her "egg." Since guessing the exact address of the egg is subject to some uncertainty, an attacker can improve her odds by inserting a number of NOP (no operation - i.e. do nothing) instructions before the actual egg. Thus, the saved return address doesn't have to be overwritten with the exact address of the egg - provided control jumps to an address below that of the egg, the egg will be executed.9
To illustrate this, consider our example. In order to exploit the buffer overflow condition, we construct a special HOME environment variable which consists of three parts. The first part contains a number of NOP instructions, the purpose of which is simply to increase the chance that control will jump to a valid instruction. The second part consists of the egg - the code we wish to execute.10 Finally, we make an educated guess about the address of the egg in memory and put that in the third part of the HOME environment variable. The total size of our constructed HOME environment variable must be greater than 100 bytes, since that is the size of the buffer we are trying to overflow.
When the program is executed, the address of the HOME environment variable is passed to the function foo(). The strcpy() function then copies the contents of HOME into BUF. In doing so, strcpy() overwrites the saved return address on the stack with an address that is hopefully just less than the address of the egg. Then, when foo() returns, the overwritten return address is popped off the stack and control jumps to that address. If our guestimate of the egg's address was close, control jumps to an address on the stack immediately before our egg and control continues from there. Unless we jumped too far, our egg will be executed.
So far, we have only seen how buffer overflows can be exploited to redirect the flow of control within a process. Some readers may therefore be wondering how this can accomplish anything for a would-be attacker. Thus, we turn now to a discussion of the implications of buffer overflows in suid programs, Unix daemons and client applications.
All Unix-like operating systems have the concept of set-user-id (or suid). Normally, regular users are restricted in what they can do. For instance,the average user can't write to the password file, open a raw socket or bind to a TCP/IP port numbered less than 1024. These are actions that are restricted to the superuser.11 Sometimes, however, regular users require privileges above and beyond what they normally have; for instance, in order to change one's password, one must be able to write to the password file. Hence the concept of set-user-id. When a program designated set-user-id is executed, the operating system sets the effective user id of that process to the user id of the owner of the program. For example, when a normal user runs /usr/bin/passwd, which is (normally) owned by root, the user's passwd process runs with full root privileges. Obviously, then, set-user-id programs must carefully restrict what the user can do. Yet a buffer overflow in a suid program can allow an attacker to bypass these restrictions. If she can redirect the flow of control within the suid process to her own code, she can execute commands with elevated privileges. Hopefully, the implications of this should be obvious.
Buffer overflows in suid programs are generally classed as local vulnerabilities - that is, in order to exploit them, an attacker must have interactive login access to the target machine. Remote vulnerabilities, which can allow an attacker unauthorized access to the machine, are an order of magnitude more serious. Generally, remote vulnerabilities are found in Unix daemons - long-lived process which perform system administration tasks and provide services to other users and computers. Moreover, since many daemons run as root,12 a successful attack can not only permit an intruder access to the system, but elevated privileges as well. Unfortunately, buffer overflows can and do exist in daemons and since these daemons often interact with data from foreign (and hence untrusted) sources, these overflows can be exploited to allow an intruder to break into a machine. Examples of overflows in daemons abound; in the past year, serious buffer overflow vulnerabilities have been found in imapd (the IMAP mail server); qpopper (a popular POP3 mail server); named (the standard Unix DNS server); and wu-ftpd (a popular FTP server).
Finally, buffer overflows in client programs have recently received increased attention. Although clients such as mail readers or web browsers generally don't run with elevated privileges,13 they often contain buffer overflow conditions and interact with foreign, untrusted data. Buffer overflows in client programs can thus be exploited to compromise user accounts, thus providing an attacker entry into the system. Once inside, this access can often be leveraged into higher privileges. Buffer overflows have been found in numerous clients - from lynx and pine on Unix-based systems to Internet Explorer and Eudora in the Windows world.
A programmer, then, must always be aware of the security risks of buffer overflows, whether she is writing system software such as a suid utility or a system daemon, or a client, such as an FTP or e-mail program. In general, any program which interacts with untrusted systems or data can create a security risk.
So far, we have concentrated on stack-based buffer overflows, which are the arguably the most commonly understood and most widely exploited class of buffer overflows. Recently, however, a related class of vulnerability, known as heap-based buffer overflows, have received increased attention.14
Dynamically allocated variables (those allocated by malloc() and friends) are created on the heap.15 Unlike the stack, the heap grows upwards on most systems; that is, new variables created on the heap are located at higher memory addresses than older ones. In a simple heap-based buffer overflow attack, an attacker overflows a buffer that is lower on the heap, overwriting other dynamic variables, which can have unexpected and (from the programmer's or administrator's view) unwanted effects.
Consider the following (utterly contrived) code example:
/* heap-overflow.c - Heap-based buffer overflow example */
#include <pwd.h>
#include <sys/types.h>
#define BUFSIZE 25
int main(int argc, char* argv) {
struct passwd *pwd;
char *foo;
/* allocate some space on the heap */
foo = (char *)malloc(BUFSIZE);
pwd = (struct passwd *)malloc(sizeof(struct passwd));
/* retrieve current user's password file entry and put it in pwd*/
pwd = memcpy(pwd, getpwuid(getuid()), sizeof(struct passwd));
printf("original uid : %d\n", pwd->pw_uid);
printf("address of foo : %u\n", (unsigned long)foo);
printf("address of pwd : %u\n", (unsigned long)pwd);
/* copy argv[1] into *foo with no bounds checking */
if (argc > 1) {
strcpy(foo, argv[1]);
}
/* oops, we just clobbered our password file information */
printf("foo : %s\n", foo);
printf("new uid : %d\n", pwd->pw_uid);
/* Uh-oh */
setuid(pwd->pw_uid);
system("/bin/sh -i");
exit(0);
}
Without going into too much detail, when the contents of argv[1] are copied into foo, it overflows the buffer, overwriting the pwd structure with arbitrary values. Assuming this program was suid root, when setuid() is called, it would set the process' user id to whatever value overwrote the pw_uid member of the pwd structure. An attacker could thus exploit this overflow to obtain elevated privileges.16
It should be noted that manipulating nearby values is a technique which can be employed in stack-based buffer overflow attacks as well, though often it's much easier to overwrite the return address and redirect the flow of control.
Buffer Overflows in Windows Operating Systems
Although this paper focuses on buffer overflow attacks involving Unix-like operating systems, this by no means implies that Unix-based systems have a monopoly on this class of attack or even that they are more susceptible. Rather, due to the relative complexity of the Win32 API vis-�-vis Unix system calls,17 relatively few people have a sufficient understanding of the intricacies of the Windows API at an assembly level to exploit a buffer overflow in a controlled fashion.18 Thus, while it is trivial to exploit a buffer overflow so as to make a Windows program or service crash (which in some cases would accomplish a denial of service), it is not so trivial to exploit a buffer overflow in order to attain access and/or increased privileges on a Windows system. Thus, few examples exist of buffer overflows in Windows software that have been exploited in the most common sense of the term 19
That said, it is a simply a matter of time before buffer overflows are widely exploited on Windows systems. After all, buffer overflows existed in Unix-like operating systems for many years before they were well understood and exploited. Already, an attempt at creating a generalized framework for identifying and exploiting buffer overflows in Windows operating systems exists.20 For now, many buffer overflow vulnerabilities in Windows are "purely theoretical" - in time, however, more and more people will be making the theoretical practical.21
Since the primary objective of this paper is to raise awareness of the serious security implications of buffer overflows, we turn now to some of the countermeasures available to programmers and system administrators.
Non-executable stacks
In most operating systems, the stack region is marked as executable, which means code located in stack memory can be executed. This is a key fact for "classic" stack-based buffer overflow attacks - if the stack is marked non-executable, then any attempt to redirect program control to code located on the stack, which as mentioned earlier, is the most common way by which attackers insert their code into a process' address space, will result in a segmentation violation. Marking the stack as non-executable is thus one commonly proposed method for stopping stack-based buffer overflow attacks, and indeed, this method can be employed on some operating systems.22
This method is far from perfect, however. Marking the stack non-executable can break a number of programs, notably some Lisp interpreters, anything which uses "trampoline functions" and Objective C.23 Furthermore, an attacker doesn't necessarily have to redirect program control to a location on the stack. A alternative technique, known as return-into-libc, is to redirect program control into code located in shared libraries, which a non-executable stack can do nothing to prevent.24
Compilers
A number of compiler technologies have been proposed for preventing buffer overflow attacks. One approach has been to patch existing C compilers to perform bounds checking on arrays.25 While this would prevent buffer overflow attacks, the additional overhead of bounds checking could impose an unacceptable performance penalty in some applications. Moreover, so far, such patches remain within the realm of the theoretical - although one implementation exists for the GNU C compiler, some doubts have been expressed about its ability to compile complex (read: real-world) code.26
Another option is to use the StackGuard compiler, which is specifically designed to detect, stop and report stack-based buffer overflow attacks.27 The StackGuard mechanism adds extra code on entry to and exit from a subroutine. When a subroutine is called, StackGuard places a "canary" value immediately before the saved return address on the stack. On the subroutine's return, the extra StackGuard code checks this value to make sure it has not been altered (i.e. by a buffer overflow). If it has, the program halts and the attack is logged. StackGuard cannot prevent heap or BSS-based buffer overflows, however.
Despite their limitations, the two countermeasures described here can prevent most stack-based buffer overflow attacks and are certainly worth investigating by any individual or organization seeking to secure their systems or code.
Better tools and technology will only prevent so many security problems, however. Really, the only way to truly eliminate security problems in software is to write better software. This, of course, means finding better programmers, or failing that, educating the ones already out there.28
This principle is simple - only give a program the privileges it needs to do its job. Thus, if a program does contain a vulnerability, the impact may be lessened. Unfortunately, the history of computer security is littered with examples of buggy programs endowed with far more privileges than they required; it is no small coincidence that many of these programs have been the source of numerous security holes.
In some cases, however, programs do require elevated privileges, though often the privileges are needed only for one particular operation. Generally, this operation, whether it be to open a raw socket or bind to a privileged port, can be done immediately after the program starts, after which point the elevated privileges can be dropped. Thus, a buffer overflow (or any other bug), which is likely to occur later in the program, cannot be exploited to obtain higher privileges.
Numerous functions in the standard C libraries perform string operations without checking the length of their arguments. The functions strcpy(), gets(), sprintf() and strcat() are commonly cited as the worst offenders, though it is always possible to introduce buffer overflow conditions by other means. Even so, using functions such as strncpy(), strncat() and snprintf(), which only manipulate a programmer-specified number of bytes, can eliminate the most egregious buffer overflows.
Large, monolithic programs (i.e. sendmail) are persistent sources of security holes, including buffer overflows. Secure programs should be small bits of tight code which do one or two things. This reduces the chance of introducing any security holes, and makes the code easier to maintain and audit.
Any data which comes from untrusted sources, whether it be from command-line arguments, the environment, the DNS or user-supplied input, should be treated with a healthy suspicion. Securely written programs always carefully examine such data before manipulating it in a way that could create a security risk.
Any code which is expected to be secure (eg. anything running suid or as a daemon, but this can easily apply to client applications as well) should be periodically audited for security problems. It should also be extensively tested before release. That your program runs properly under normal conditions proves nothing about its security; a secure program must be able to run properly under abnormal conditions as well.
Some have claimed that C is an inherently dangerous programming language, specifically because the lack of bounds checking allows buffer overflow attacks to succeed, and that therefore the use of C in secure software should be seriously re-evaluated.29 Yet buffer overflows are only one class of vulnerability (hence the quote which begins this paper). While a compiler which enforces bounds checking may eliminate buffer overflows, it may do nothing to protect against other vulnerabilities, and in fact, it may introduce other, as yet undiscovered attack classes.30
Furthermore, when one considers the investment the computing world has made in C and C++, switching to other, "safer" languages becomes an extremely expensive proposition. Most programmers have been trained in C/C++; most operating systems in use today are written mostly in these languages; and other languages lack the rich set of libraries which exist for C and C++. And as this paper has attempted to illustrate, the security implications of buffer overflows go far beyond a limited number of system utilities and daemons. It's not just a matter of rewriting a few critical bits of software in Ada or Modula-2; if we are to choose this route, we must consider rewriting numerous client applications as well.
So, the question becomes an economic one: is the security gained through the use of "safer" languages worth the expense that would be incurred in switching?31 Although this question has not been studied in any formal sense, the general feeling is that it is not. Really, the only sure solution is for programmers to produce more robust and secure code. This is the goal this paper has attempted to further; it remains to be seen whether this goal can be achieved.
This paper owes much to Aleph One's Smashing the Stack for Fun and Profit, as is no doubt obvious to anyone who has read that particular paper. The portion on heap-based buffer overflows was heavily influenced by Matt Conover's w00w00 on Buffer Overflows. Lots of material is based on postings to the Bugtraq mailing list. That said, I have attempted to express myself in my own words - any technical errors are due to my confusion.
I am also indebted to a number of individuals who reviewed this paper for technical errors and downright mistruths. If any such problems are still present, it is my fault, not theirs.
0 Kragen, Posting to Bugtraq mailing list, http://geek-girl.com/bugtraq/1998_3/0213.html
1 Taken from the Jargon File - http://www.tuxedo.org/~esr/jargon/
2 Don Seeley, A Tour of the Worm, http://www.alw.nih.gov/Security/FIRST/papers/virus/tour.ps
3 Crispin Cowan, Posting to Bugtraq Mailing List, http://geek-girl.com/bugtraq/1999_1/0481.html
4 This assertion is based on a quick review of http://www.cert.org/advisories. Although the auther has his own opinions as to how and why this situation has come about, they are far too likely to provoke a flame war to discuss here ;-) In itself, the evolving nature of vulnerabilities is an interesting (and so far, neglected) area of research.
5 Taken from the Jargon File - http://www.tuxedo.org/~esr/jargon/
6 Some things are just better expressed in C than in English ;-) This is a magazine for computer science students, after all.
7 Specifically, the stack pointer is incremented by 100.
8 After all, in addition to overwriting the saved return address, strcpy probably clobbered a number of other important values, the effect of which will probably felt sooner rather than later.
9 Obviously, the return address can't be too low, otherwise we'll jump into unknown territory and earn ourselves an illegal instruction or segmentation violation.
10 Most code used by authors of buffer overflow exploits is derived from examples used by Aleph One in Smashing the Stack for Fun and Profit. One doesn't have to be an assembly wizard to write a buffer overflow attack - cut and paste will generally work quite well ;-)
11 Commonly referred to as root, though technically any account with a uid of 0 has superuser privileges.
12 This is an unfortunate legacy of the Unix security model. Some interesting work has been done to give some Unix-like OS's a more fine-grained privilege systems - see http://www.enteract.com/~tqbf/harden.html for details.
13 This presumes that most admins are sensible enough not to run irc or lynx as root. I am fully willing to admit that this presumption may be misguided...
14 This is the terminology used by Matt Conover in w00w00 on Buffer Overflows. It makes sense, so I'll use it too.
15 Readers confused about this whole stack/heap thing should consult a text on process memory organization.
16 Due to the way this example is constructed, it is not possible to exploit it in such a way as to directly obtain root privileges. It is left as an exercise to the reader to figure out why ;-)
17 I'll probably get some flames from both sides for this one. Even among Unix-like operating systems, the system call interface can affect how easily a buffer overflow can be exploited. The BSD's, for example, use far calls for system calls, which makes coding the egg somewhat more difficult. Linux, on the other hand, uses interrupt 80h (echoes of DOS?). This doesn't mean the BSD's (or Windows) are any safer; just that exploiting them requires more effort.
18 I sure don't ;-)
19 The l0pht has issued a number of advisories about buffer overflows in Windows software and has in some cases provided exploit code. One interesting example is a buffer overflow in Internet Explorer 4.02, which can be exploited to download an executable from a remote location and execute it (http://www.l0pht.com/advisories/ie4_x2.txt).
20 DilDog, The Tao of Windows Buffer Overflows, http://www.newhackcity.net/win_buff_overflow/
21 This is a reference to a claim Microsoft made about a vulnerability in some of its software The l0pht then went and produced working exploit code.
22 Solar Designer's secure-linux patch for the Linux kernel can accomplish this (http://www.false.com/security/). Solaris 2.6 and 7 can also be configured to mark the stack as non-executable by adding the line set noexec_user_stack = 1 to /etc/system and rebooting. Apparently, there's a stack integrity patch for FreeBSD floating around out there as well...
23 Nate.Posting to Bugtraq mailing list, http://geek-girl.com/bugtraq/1997_2/0125.html
24 See: John McDonald (aka Horizon), Posting to Bugtraq mailing list, http://geek-girl.com/bugtraq/1999_1/0926.html and Solar Designer, Posting to Bugtraq mailing list, http://www.geek-girl.com/bugtraq/1997_3/0281.html
25 Patches for gcc and egcs are available from http://web.inter.NL.net/hcc/Haj.Ten.Brugge/
26 Crispin Cowan, Posting to Bugtraq mailing list, http://geek-girl.com/bugtraq/1999_1/0393.html
27 StackGuard is part of the Immunix project at the Oregon Graduate Institute's Department of Computer Science and Engineering. More information is available from http://www.cse.ogi.edu/DISC/projects/immunix/StackGuard/
28 Writing secure and robust code goes far beyond the scope of this paper, however. An excellent summary of secure programming resources is available at http://geek-girl.com/bugtraq/1998_3/0215.html.
29 Craig Spanning, Posting to Bugtraq mailing list, http://geek-girl.com/bugtraq/1998_3/0171.html
30 Admittedly, buffer overflows are the single largest class of vulnerability discovered today, so trying to eliminate this attack class would be a good place to start. This counter-argument is thus perhaps not so compelling.
31 The economics of (in)nsecurity are sometimes lost in the technical intricacies and frenzied clash of egos which mark the field. Indeed, insecurity may be rational economic behaviour, but that's fodder for another paper.
Aleph One, Smashing the Stack for Fun and Profit. Originally published in Phrack 49-14.
Crispin Cowan, et al., StackGuard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks, http://www.cse.ogi.edu/DISC/projects/immunix/StackGuard/usenixsc98_html/
DilDog, The Tao of Windows Buffer Overflows, http://www.newhackcity.net/win_buff_overflow/
Matt Conover (aka Shok), w00w00 on Buffer Overflows. Posted to Bugtraq mailing list, http://geek-girl.com/bugtraq/1999_1/0377.html
Mudge, How to Write Buffer Overflows. http://www.insecure.org/stf/mudge_buffer_overflow_tutorial.html
Don Seeley, A Tour of the Worm, http://www.alw.nih.gov/Security/FIRST/papers/virus/tour.ps
Various Authors, Postings to Bugtraq Mailing List ([email protected]). Archived at http://www.geek-girl.com/bugtraq