Re: Super Lint (was: Unexecutable Stack / Buffer Overflow Exploits...)

[Eric W. Biederman]

Theodore Tso I'm Cc'ing you as you are an active kernel developer
who is very interested in (at least some parts) of this thread.

I've added the gcc development list to the CC list as I believe
this conversation should move there.

Everyone please watch your CC & replies.

Oliver Xymoron <[e-mail]> writes:

> On Sat, 1 Jan 2000, Kai Henningsen wrote:
> 
> > [e-mail] (Magnus Danielson) wrote on 01.01.00 in
> <[e-mail]>:
> 
> > 
> > > Oh yes... like those that those who avoid strcpy by doing
> > >
> > >    memcpy(t, s, strlen(s)+1)
> > >
> > > I mean, memcpy is supposed to be safe, ain't it ;)
> > 
> > I guess what we _really_ need is some sort of super lint. That is, a
> > program that can analyze C code (others are fine, but C is the most
> > important by far) and highlights problematic points in the code.
> > 
> > This would not mean that your program actually does anything useful, only
> > that it's safe against some kinds of attack.
> > 
> > And it would have zero runtime overhead.
> 
> Unfortunately, your approach was proved impossible well before the
> transistor was invented. See "halting problem".

The halting problem is only true for the set of all programs.
There should be well defined sets for which halting can be proved.

A simpler solution (in concepts at least) is to do runtime checking of
buffers.  The C standard explictly allows this with it's statements
about what is defined for pointers.  In particular: (Quote from memory)
- Read/Writing from a pointer past the end of an array is undefined.
- The pointers (that do not point into an array) one past the end
  of that array are defined.

This plus some mucking around with the implementation defined rules
for how dynamic memory allocators (so you can get the size of the byte
array).  Should result in a C that doesn't allow array overflows.

This would naively at least be done with fat pointers that point at
their location, and the start & end of the array they are currently
pointed at.  Breaking the present ABI but not source code.

Integrating this into GCC, and recompiling applications
would certainly be a chore, but there is nothing really hard in
the design.  Of course there would be a set of programs (which
reimplement malloc or malloc like functions that would need to be
touched.

And doing limited proofs in the compiler to prove common cases
don't need the checking (optimizing the bounds checking), 
should result in programs that run only a few percent 5-10%
slower then their unchecked variants.

This would totally close the array overflow security hole, (except
for denial of service attacks), and be a handy debugging tool.

Any Volunteers?
Eric