OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
 
Subject: Re: Buffer Overflows and DoS
From: Crispin Cowan (crispinwirex.com)
Date: Thu Apr 27 2000 - 11:28:41 CDT

Horst von Brand wrote:

> [Some paragraphs reindented for readablility]
> Crispin Cowan <crispinwirex.com> said:
> > Horst von Brand wrote:
> > > Crispin Cowan <crispinwirex.com> said:
> > > > Buffer overflows are largely a result of:
> > > > * the C idiom of null-terminated strings
> > > I got the same results in FORTRAN and Pascal just by wandering off the end
> > > of arrays...
> > Sure, but you have to work harder to get those kinds of bugs in
> > FORTRASH^H^H N and Pascal. To be really safe, you need a type-safe
> > language that does bounds checking. The C null-termination idiom just
> > aggrevates the problem.
> Harder? No... to exploit them is just as hard with Pascal's "packed array
> of char" and C's "char[]" as they are exactly the same thing under the hood.

Yes, it's harder, because string termination errors occur less frequently.

> > Note that Bernstein has also implemented a strings library that dumps the
> > C null-termination idiom in favor of a base+bounds idiom. He (correctly)
> > feels that this idiom is less vulnerable to potential buffer overflow
> > attacks.
>
> For better or worse, C is here to stay. And C doesn't use this natively, so
> it is of no much use in the end.

C has no native notion of strings at all. C has character pointers and pointer
arithmetic, but no strings at all. The entire string notion in C comes from an
idiom embodied in the C standard library. Bernstein has provided an alternative
string library.

What is true is that most existant C programs will not be able to use Bernstein's
library, because the API is different from the standard API.

> Besides, how you keep track of the length
> of your strings is irrelevant, you have to check bounds.

It's not irrellevant. If you use a base+bounds notation, then it is easy to
create library functions that CORRECTLY do bounds checking on the size of the
destination buffer, because the size of the buffer is encoded in the string
object. With the null terminated idiom, the code has no easy way to determine the
size of the receiving buffer, which is what makes doing correct bounds checking in
C programs hard.

> And that would
> mean an extra two words for each and every string (one the length of the
> array, another the current length). 8 bytes extra for "foo".

That was no doubt what Kernighan & Ritchie were thinking in the late 1960s when
they were designing this stuff for PDP 8 machines, with 8 KB of RAM. Palm pilots
now commonly have megabytes of RAM and workstations can have gigabytes of RAM.
Fussing over an extra word is penny wise and pound foolish.

The major barrier to using Bernstein's library is that you end up re-writing
software to do it. But new code would well benefit from using DJB's string
library instead of the standard string library.

> No. Functions that are called with a buffer elsewhere as arguments abound.
> That such attacks aren't widespread is just result of the fact that
> machines with stacks that grow upward aren't that common.

But it's still harder to do. Attackers started with the easy stuff, and move on
to the harder stuff when the easy stuff is mined out.

> Just like attacks
> that work even when the stack is not executable aren't common today, but as
> such patches for the linux kernel (and similar mechanisms for other OSes)
> have been discussed at length, crackers are starting to write them. Just as
> Linus predicted...

True: when you raise the bar, people work harder to jump over it.

Note that there is no way to jump over the StackGuard defense: you have to go
find a different bug to exploit.

> > > Array bounds checking is quite costly (some 3 or 4 extra instructions
> > > for the 1 instruction doing the access on the fast path). Most Pascal
> > > compilers (the language specifies array bounds checking for each
> > > access!) I know had a flag to turn it off, just because of this.
> > I agree. That's why we feel that StackGuard has long-term viability.
> > Function call returns are far less frequent than array references, so
> > StackGuard's overhead will always be lower than bounds checking.
>
> But it only notices that the cage is open when the bird is long gone, so it
> isn't a solution for everything.

I'm not sure what you mean by the above analogy. StackGuard halts the attack in
progress. The attacker never gains any privilege.

> Ideal would be for the compiler (or a
> lint-like tool) check array bounds at compile time, and warn each time it
> can't prove bounds won't be overrun. But to get the noise level down to
> bearable seems to need much more work still. And C's convoluted semantics
> and laisez-faire with types certainly doesn't help a bit here.

Check out this excellent paper by Wagner
http://www.cs.berkeley.edu/~daw/papers/overruns-ndss00.ps from his impressive page
of publications http://www.cs.berkeley.edu/~daw/papers/ . It describes work on a
tool to analyze C programs looking for buffer overflows. This is some of the most
advanced work available on automatic detection of buffer overflow vulnerability in
C code, and still it has a high rate of fales positives, and does not catch all
potential buffer overflows. That's because static analysis of C code for buffer
overflows is undecidable: no amount of work will ever get this perfect.

Crispin
-----
Crispin Cowan, CTO, WireX Communications, Inc. http://wirex.com
Free Hardened Linux Distribution: http://immunix.org
                  JOBS! http://immunix.org/jobs.html