Articles > Memory bounds-checking for GCC
Brian Gough (Network Theory Ltd)This article is a supplement to the book "An Introduction to GCC" (ISBN: 0-9541617-9-3), published by Network Theory Ltd.
Bounds checking: an introduction
The commonest and most dangerous error in C programming is reading or writing to incorrect memory locations using pointers. The bounds checking extension to GCC provides a way of detecting invalid memory accesses, by producing additional checking instructions for each read or write in the executable file. This slows down the program but can prevent serious errors, particularly for software which needs to be secure.
The bounds-checking extension to GCC keeps track of pointers and memory allocations, to ensure that invalid locations are never accessed. The extension is not supplied with GCC by default, but can easily be applied to the source as a patch.
History
The initial bounds checking patch for gcc was developed by Richard Jones and Paul Kelly of the Department of Computer Science, Imperial College (London) in 1995. Their approach was to keep track of valid pointer ranges on the stack and heap at run-time, and instrument the code with inline checks of each pointer before use. The representation of pointers was unchanged, allowing binary compatibility with existing libraries from bounds-checked code. Since the approach was based on pointer arithmetic, it was architecture independent, and it was possible to prove the bounds-checking properties formally.
Their work was later improved by Olatunji Ruwase and Monica S. Lam of Stanford University, by using a new algorithm (called "CRED" -- C Range Error Detector) which closed some loopholes in the original Jones & Kelly algorithm, and eliminated possible false positive errors in the handling out-of-bound pointers. The CRED algorithm has been tested on 1.2 million lines of code from various free software packages, and used to discover a number of known and previously unknown security vulnerabilities. The CRED algorithm is probably the state of the art in this area.
Alternative approaches included checkergcc, an early
bounds-checking version of GCC, and the program valgrind which
checks executables at runtime. Checkergcc uses the memory
protection features of the x86 processors to detect invalid accesses, while valgrind is based on a memory-usage tracking emulation of the x86 instruction set.
Example
To demonstrate the use of bound-checking, here is a program which writes to a memory location beyond the end of an array:
int
main (void)
{
int i;
double x[10];
for (i = 0; i <= 10; i++)
x[i] = 1;
return 0;
}
Writing to an out-of-bounds memory location causes unpredictable results
in a running program, but is difficult to detect. Note that the problem
will not reported by warning option -Wall with
gcc.
To compile the program with memory-access checking we use the command
gcc -fbounds-checking in place of gcc:
$ gcc -Wall -g -fbounds-checking check.c
The bounds-checking version of gcc accepts all the same options
as gcc, it only differs from gcc in the executable file it
produces.
On running the executable, an error message is generated by the bounds-checking extensions:
$ ./a.out Bounds Checking GCC v gcc-3.3.3-3.2 Copyright (C) 1995 Richard W.M. Jones Bounds Checking comes with ABSOLUTELY NO WARRANTY. For details see file `COPYING' that should have come with the source to this program. Bounds Checking is free software, and you are welcome to redistribute it under certain conditions. See the file `COPYING' for details. For more information, set GCC_BOUNDS_OPTS to `-help' check.c:8:Bounds error: array reference (10) outside bounds of the array. check.c:8: Pointer value: 0xbffffa24 check.c:8: Object `x': check.c:8: Address in memory: 0xbffff9d4 .. 0xbffffa23 check.c:8: Size: 80 bytes check.c:8: Element size: 8 bytes check.c:8: Number of elements: 10 check.c:8: Created at: check.c, line 5 check.c:8: Storage class: stack Aborted
The executable created with the bounds-checking extensions correctly
detects that an out-of-bounds memory location was read at line 8 in the
main of the file 'check.c'. The output also shows that the
overflowed array was created at line 5.
Obtaining and Installing the patch
The bounds-checking patches can be obtained from Hermann ten Brugge at:
- http://sourceforge.net/projects/boundschecking/ under the [Files] section (direct link)
The typical compilation steps look like this:
$ cd gcc-3.3.3 $ patch -p1 -s < bounds-checking-patch $ cd .. ; mkdir build ; $ cd build $ ../gcc-3.3.3/configure --prefix=/opt/gcc-3.3.3-bc $ make bootstrap $ make install
After installation, the new compiler can be selected with the CC and CFLAGS variables when compiling applications.
References and Further Reading
A Practical Dynamic Buffer Overflow Detector, O. Ruwase, M. Lam, Proceedings of the 11th Annual Network and Distributed System Security Symposium, February 2004. http://suif.stanford.edu/research/analysis.html
Backwards-compatible bounds checking for arrays and pointers in C programs, R.W.M. Jones, P. Kelly, Third International Workshop on Automated Debugging, M. Kamkar and D. Byers, eds (Linkoping University Electronic Press), 1997 http://www.doc.ic.ac.uk/~phjk/BoundsChecking.html
Dynamic Buffer Overflow Detection Michael Zhivich, Tim Leek, Richard Lippmann (MIT Lincoln Laboratory). Workshop on the Evaluation of Software Defect Detection Tools, June 2005 (homepage). http://www.cs.umd.edu/~pugh/BugWorkshop05/papers/61-zhivich.pdf
Related Titles
Title: "An Introduction to GCC"Author: Brian J. Gough
Published by Network Theory Ltd, May 2004
Paperback (6"x9"), 124 pages
Retail Price: $19.95 (£12.95 in UK)
ISBN: 0-9541617-9-3
Webpage: http://www.network-theory.co.uk/gcc/intro/