- publishing free software manuals

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:

There are patches available from gcc-3.3.2 upwards. You also need the complete source code for the GCC, which you can get from the GNU Project (order 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/