[OCLUG-devel] Anatomy of a buffer overflow

[Christopher Smith]

On Sun, 2004-07-11 at 08:07, Jack Denman wrote:
> I do not see the buffer overflow in the GNU code. Let each one that knows the 
> "C" language judge for themselves, and don't take anybody's word for it.

I have to admit, Jack's statements concerned me. For one, I was pretty
confident about the security flaw in the code and I didn't want him or
anyone else to come to the wrong conclusion about the code. I felt I've
already gone into great detail as to why there is an error, and nobody
has pointed out an error in the analysis, or some point of confusion. So
I was at a loss for what to add for further explanation. I was also
concerned that somehow perhaps I'd gotten things wrong, and if so, I
wanted to understand why.

So, I wrote out a test snippet to demonstrate a buffer overflow in the
code. I thought it might also prove to be a useful demonstration that
people could step through in their debugger.

Sure enough, I did in fact find it.

Please find attached a code snippet demonstrating how a buffer overflow
can happen with Jack's code. I took Jack's snipped, removed the DOS
stuff, and made a few corrections to that the support libraries could
compile. None of this should effect the code's behavior on a Linux or
Unix system (Jack, feel free to point out if I am wrong in this regard).
I then added a fairly simple main() function which would create a file
with a single line of size SIZE_MAX (much bigger than necessary, but
just to be safe), as well as a linebuffer just over SIZE_MAX/2, and then
invoke readline on the file. You can actually start with various sizes
of line buffers by passing in a 3rd argument. Depending on your starting
buffer size and a ton of other factors, you may run out of virtual
memory before the buffer overflow occurs. The program will attempt to
detect cases where this will happen, but really, this is in the hands of
a particular system's malloc/realloc/free implementation (my little test
loop that checks for memory seems to really fragment the heap, so you
might want to remove it). Also note that you need to have your system
setup so that it can address >2GB of virtual memory. For best results,
you want to use a so called "4+4" kernel, which allows 4GB of virtual
memory per process. Most of the distros ship with kernels configured for
at least 3GB's of virtual memory, but a lot of people who build their
own kernels trim it down to 1GB, as that is the default. Also, you might
want to make sure that you don't have any memory allocation limits from
ulimit which might get in the way. In general, YMMV as far as which
buffer sizes result in a buffer overrun, but if you support >2.5GB of
virtual memory, you shouldn't have a problem getting there with the
default config.

The code generates a test file larger than 2GB, so you need a file
system with large file support (basically all of them). The code
attempts to create a sparse file to avoid chewing up a ton of disk space
and time, so stick to filesystems which also support sparse files:
ext2/3, reiserfs, xfs, jfs, etc. It runs quite slowly (if for no other
reason that doing large reads with getc() is painfully slow), so be
patient.

I also added an assertion into the the main loop of readline which tests
for whether we have a buffer overflow. Where previously, it was just:
        *p++ = (char) c;

We now have:

//make sure that p is not pointing outside the allocated buffer
//if p is pointing outside, we have a buffer overflow
if ((p - line->buffer) > line->size) {
  fprintf(stderr, "Buffer overflow with p at\t%x\nline->buffer
at\t\t\t%x\nDifference is:\t%u\nline->size is:\t%u\n", p, line->buffer,
p - line->buffer, line->size);
  exit(10);
}
        *p++ = (char) c;

Compilation is straight forward, I've been building it with "gcc -g
readline.c -o readline". If you strip out the symbols the code will take
up less of virtual memory, but then you won't be able to look at it in
the debugger too easily. This is what happens when I run it:

$ ./readline testFile
Buffer overflow with p at       b74a900a
line->buffer at                 374a9008
Difference is:  2147483650
line->size is:  4
$ echo $?
10

The default test case seems to work consistently on the 32-bit x86 RHEL
systems I tested on, a 64-bit x86 RHEL Opteron system (running as a
32-bit binary of course), as well as a Solaris system (again running as
a 32-bit binary). While it's theoretically possible to reproduce the
error with a 64-bit executable, you'd need > 2^63 of virtual memory, and
I figure most of us can't come up with that until another 30 odd years
of Moore's law and it's variants pass us by.

-- 
Christopher Smith <x at xman.org>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: readline.c
Type: text/x-csrc
Size: 5454 bytes
Desc: not available
Url : http://localhost.localdomain/pipermail/oclug-devel/attachments/20040712/296abb22/attachment.bin