Buffer Overflow Attacks and Their Countermeasures
Buffer overflow problems always have been associated with security vulnerabilities. In the past, lots of security breaches have occurred due to buffer overflow. This article attempts to explain what buffer overflow is, how it can be exploited and what countermeasures can be taken to avoid it.
Knowledge of C or any other high level language is essential to this discussion. Basic knowledge of process memory layout is useful, but not necessary. Also, all the discussions are based on Linux running on x86 platform. The basic concepts of buffer overflow, however, are the same no matter what platform and operating system is used.
A buffer is a contiguous allocated chunk of memory, such as an array or a pointer in C. In C and C++, there are no automatic bounds checking on the buffer, which means a user can write past a buffer. For example:
int main () {
int buffer[10];
buffer[20] = 10;
}
The above C program is a valid program, and every compiler can compile it without any errors. However, the program attempts to write beyond the allocated memory for the buffer, which might result in unexpected behavior. Over the years, some bright people have used only this concept to create havoc in the computer industry. Before we understand how they did it, let's first see what a process looks like in memory.
A process is a program in execution. An executable program on a disk contains a set of binary instructions to be executed by the processor; some read-only data, such as printf format strings; global and static data that lasts throughout the program execution; and a brk pointer that keeps track of the malloced memory. Function local variables are automatic variables created on the stack whenever functions execute, and they are cleaned up as the function terminates.
The figure above shows the memory layout of a Linux process. A process image starts with the program's code and data. Code and data consists of the program's instructions and the initialized and uninitialized static and global data, respectively. After that is the run-time heap (created using malloc/calloc), and then at the top is the users stack. This stack is used whenever a function call is made.
A stack is a contiguous block of memory containing data. A stack pointer (SP) points to the top of the stack. Whenever a function call is made, the function parameters are pushed onto the stack from right to left. Then the return address (address to be executed after the function returns), followed by a frame pointer (FP), is pushed on the stack. A frame pointer is used to reference the local variables and the function parameters, because they are at a constant distance from the FP. Local automatic variables are pushed after the FP. In most implementations, stacks grow from higher memory addresses to the lower ones.
This figure depicts a typical stack region as it looks when a function call is being executed. Notice the FP between the local and the return addresses. For this C example,
void function (int a, int b, int c) {
char buffer1[5];
char buffer2[10];
}
int main() {
function(1,2,3);
}
the function stack looks like:
As you can see, buffer1 takes eight bytes and buffer2 takes 12 bytes, as memory can be addressed only in multiples of word size (four bytes). In addition, an FP is needed to access a, b, c, buffer1 and buffer2 variables. All these variables are cleaned up from the stack as the function terminates. These variables take no space in the executable disk copy.
Consider another C example:
void function (char *str) {
char buffer[16];
strcpy (buffer, str);
}
int main () {
char *str = "I am greater than 16 bytes"; // length of str = 27 bytes
function (str);
}
This program is guaranteed to cause unexpected behavior, because a string (str) of 27 bytes has been copied to a location (buffer) that has been allocated for only 16 bytes. The extra bytes run past the buffer and overwrites the space allocated for the FP, return address and so on. This, in turn, corrupts the process stack. The function used to copy the string is strcpy, which completes no checking of bounds. Using strncpy would have prevented this corruption of the stack. However, this classic example shows that a buffer overflow can overwrite a function's return address, which in turn can alter the program's execution path. Recall that a function's return address is the address of the next instruction in memory, which is executed immediately after the function returns.
Because we know it is easy to overwrite a function's return address, an intelligent hacker might want to spawn a shell (with root permissions) by jumping the execution path to such code. But, what if there is no such code in the program to be exploited? The answer is to place the code we are trying to execute in the buffer's overflowing area. We then overwrite the return address so it points back to the buffer and executes the intended code. Such code can be inserted into the program using environment variables or program input parameters. An example code that spawns a root shell can be found in a classic paper written by Aleph One for Phrack Magazine (see Resources).
The solutions proposed for buffer overflow problems mainly target the prevention of large-scale system attacks through the loopholes described above. None of the methods described below can claim to prevent all possible attacks. These methods, however, can make it more difficult to access buffer overflows and, hence, destroy the consistency of stacks.
Write secure code: Buffer overflows are the result of stuffing more code into a buffer than it is meant to hold. C library functions such as strcpy (), strcat (), sprintf () and vsprintf () operate on null terminated strings and perform no bounds checking. gets () is another function that reads user input (into a buffer) from stdin until a terminating newline or EOF is found. The scanf () family of functions also may result in buffer overflows. Hence, the best way to deal with buffer overflow problems is to not allow them to occur in the first place. Developers should be educated about how to minimize the use of these vulnerable functions.
Stack execute invalidation: Because malicious code (for example, assembly instructions to spawn a root shell) is an input argument to the program, it resides in the stack and not in the code segment. Therefore, the simplest solution is to invalidate the stack to execute any instructions. Any code that attempts to execute any other code residing in the stack will cause a segmentation violation. However, the solution is not easy to implement. Although possible in Linux, some compilers (including GCC) use trampoline functions (see Resources) to implement taking the address of a nested function that works on the system stack being executable. A trampoline is a small piece of code created at run-time when the address of a nested function is taken. It normally resides in the stack, in the stack frame of the containing function and thus requires the stack to be executable. However, a version of the Linux kernel that enforces the non executable stack is freely available (see Resources).
Compiler tools: Over the years, compilers have become more and more aggressive in optimizations and the checks they perform. Various compiler tools already offer warnings on the use of unsafe constructs such as gets (), strcpy () and the like. For example, this code
int main () { char *str = (char *)malloc(10);// allocate 10 bytes for str gets (str); // reads input from stdin and store into str }when compiled with GCC, returns the following warning:/tmp/cc203ViF.o: In function "main": /tmp/cc203ViF.o(.text+0x1f): the "gets" function is dangerous and should not be used.
Apart from offering warnings, modern compiler tools change the way a program is compiled, allowing bounds checking to go into compiled code automatically, without changing the source code. These compilers generate the code with built-in safeguards that try to prevent the use of illegal addresses. Any code that tries to access an illegal address is not allowed to execute.
These kind of tools, however, require the source code to be recompiled with a newer compiler. This requirement may be a problem if the application is not open source. Furthermore, it may affect the application's performance to a great extent. In some case, executable size and execution time may increase two-fold.
A patch for GCC that does bounds checking can be found here. Recently, however, most of the tools have concentrated on preventing the return address from being overwritten, as most attacks occur this way. StackShield is a freely available tool that copies the return address of a function to a safe place (usually to the start of the data segment) at the start of the function. When the function terminates, it compares the two function return address, the one in the stack and the one stored in data segment. In the case of a mismatch, the function aborts immediately.
Because a function also can call another function, it needs to maintain a stack kind of structure for storing return addresses. Another tool available is StackGuard, which detects and defeats smash stacking attacks by protecting the return address on the stack from being altered. It places a canary word next to the return address whenever a function is called. If the canary word has been altered when the function returns, then some attempt has been made on the overflow buffers. It responds by emitting an alert and halting.
Dynamic run-time checks: In this scheme, an application has restricted access in order to prevent attacks. This method primarily relies on the safety code being preloaded before an application is executed. This preloaded component can either provide safer versions of the standard unsafe functions, or it can ensure that return addresses are not overwritten. One example of such a tool is libsafe. The libsafe library provides a way to secure calls to these functions, even if the function is not available. It makes use of the fact that stack frames are linked together by frame pointers. When a buffer is passed as an argument to any of the unsafe functions, libsafe follows the frame pointers to the correct stack frame. It then checks the distance to the nearest return address, and when the function executes, it makes sure that address is not overwritten.
All the methods/tools described above are limited in one manner or another. No tool can solve completely the problem of buffer overflow, but they surely can decrease the probability of stack smashing attacks. However, code scrutiny (writing secure code) is still the best possible solution to these attacks. Programmers should be educated to prevent/minimize the use of standard unsafe functions. In addition, no warning given by the compiler should be taken lightly. With time and increasing awareness among developers, buffer overflow problems are predicted to decrease in importance and frequency. Security-related issues are still expected to be around, though, by various other means.
"Smashing the Stack for Fun and Profit", by Aleph One.
Openwall Project, Linux patch with non-executable stack version.
libsafe Project from Avaya Labs
Sandeep Grover works as a Software Engineer with Quicklogic, India. He holds a Bachelor's Degree in Computer Science from the Institute of Technology, BHU, India. His research interests lie in compilers, EDA and computer architecture.
email: sgrover@quicklogic.com
