Immunix StackGuard: Automatic Detection and Prevention of Stack Smashing Attacks

StackGuard provides a systematic solution to the persistent problem of buffer overflow attacks.  Buffer overflow attacks gained notoriety in 1988 as  art of the Morris Worm incident on the Internet.  While it is fairly simple to fix individual buffer overflow vulnerabilities, buffer overflow attacks  continue to this day.  Hundreds of attacks have been discovered, and while most of the obvious vulnerabilities have now been patched, more sophisticated buffer overflow attacks continue to emerge.

StackGuard is a simple compiler technique that virtually eliminates buffer overflow vulnerabilities with only modest performance penalties.  Privileged programs that are recompiled with the StackGuard compiler extension no longer yield control to the attacker, but rather enter fail-safe state.  These programs require no source code changes at all, and are binary-compatible with existing operating systems and libraries.

Distribution

StackGuard's implementation is a small-scale modification of gcc 2.7.2.2.  The distribution is comprised of the compiler, and a library.  Both are available in source form.  To get StackGuard, you need:

Mechanism

Stack smashing attacks exploit a lack of bounds checking on the size of input being stored in a buffer array.  By writing data past the end of an allocated array, the attacker can make arbitrary changes to program state stored adjacent to the array.  The common data structure to attack is the current function's return address stored on the stack.  The full details of how stack smashing attacks function have been documented by many authors: StackGuard detects and defeats stack smashing attacks by protecting the return address on the stack from being altered.  StackGuard has two mechanisms to protect the return address:  one provides greater assurance, and the other provides greater performance.

The higher performance StackGuard mechanism is to instrument the stack frame with a "canary" word laid right next to the return address on the stack.  If an attacker attempts to smash the stack and change the return address, the attacker will necessarily overwrite the canary word as well.  The code emitted by the compiler to do function returns is enhanced to check the integrity of the stack by looking for the canary word:  if the canary word has been changed, the program aborts instead of yielding control to the attacker.  The canary word is selected at random when the process starts, to make it difficult for the attacker to guess the canary value.

The higher assurance StackGuard mechanism utilizes a tool from the  Synthetix  project called  MemGuard.  MemGuard provides fine-grained memory protection, down to the size of a single word.  The MemGuard variant of StackGuard applies MemGuard's protect() to the return address when a function starts, and releases the protection of the return address when the function finishes.  If any part of the program ever tries to alter the return address (which is not normal behavior) then the MemGuard memory protection mechanism detects the write to protected data, and aborts the program.

MemGuard is implemented using a combination of virtual memory protection, and the  Pentium's debugging registers.  MemGuard imposes a substantial performance penalty, but it may be acceptable to sites that do not have large computing needs, and do want greater assurance.  MemGuard offers this greater assurance, because it detects the attempt to change the return address immediately, rather than when the function exits.

Penetration Data

The following table shows the results of applying stack smashing exploits to various programs that are known to be vulnerable.
 
Vulnerable Program Result Without StackGuard Result with Canary StackGuard Result with MemGuard StackGuard
dip 3.3.7n root shell program halts program halts
elm 2.4 PL25 root shell program halts program halts
Perl 5.003 root shell program halts irregularly root shell
Samba root shell program halts program halts
SuperProbe root shell program halts irregularly program halts
umount 2.5k/libc 5.3.12 root shell program halts program halts
wwwcount v2.3 httpd shell program halts program halts
zgv 2.7 root shell program halts program halts
 
The notation "program halts" indicates that StackGuard detected and arrested the attack.  The notation "program halts irregularly" indicates that the changes in the program's data layout induced by using StackGuard (principally, changing the size of crt0's data space, and the size of a stack frame) caused the attack to fail, but StackGuard did not actually detect the attack.  In all cases, "program halts irregularly" results because the stack smashing attack is not actually attempting to alter the return address, but is actually aiming at some other variable in the program, usually a function pointer.

Performance Data

We claim that modest performance penalties for privileged setuid root daemons do not actually matter very much, because such programs are not often compute-bound.  However, some daemons do consume substantial compute time (e.g. sendmail on a large mail server) so we have performed some performance tests that we feel are representative.

The first test is in executing the program ctags, which builds indices of variables from C source programs.  This table shows the run-time of ctags under various circumstances:
  

Input Version User Time System Time Real Time
37,000 lines Generic 0.41 0.14 0.55
Canary 0.68 0.13 0.99
MemGuard 1.30 5.45 6.84
586,000 lines Generic 7.74 2.08 10.2
Canary 11.9 2.07 14.5
MemGuard 21.1 238.0 255.1
      The second test is in executing a StackGuard-protected version of gcc, compiling the ctags program.  The following table shows the time to compile ctags using the original gcc, and the two StackGuard variants.
 
Version User Time System Time Real Time
Generic 1.70 0.12 1.83
Canary 1.79 0.16 1.96
MemGuard 2.22 3.35 5.76
 Web page by crispin@cse.ogi.edu and  Netscape Navigator Gold