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

[Oliver Xymoron]

On Mon, 3 Jan 2000, Eric W. Biederman wrote:

> 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.

Yes, but most of the well defined sets aren't interesting. Godel's theorem
tells us this. The sets are all too simple to encompass the rules of
arithmetic or recursion. See also the busy beaver problem for examples of
how hard even the smallest programs can be to analyze.
 
> A simpler solution (in concepts at least) is to do runtime checking of
> buffers.

Yes, I mentioned a method that I'd tried for this in an earlier part of
the thread. To elaborate, I put together a preloadable library that hooks
into getenv, f?{open,close,read,write}, v?s?{print,scan}f, exec, most of
the string functions, etc. On load, it locates __ARGV and __ARGC and the
file handles for stdin and marks their "addresses" (file handles are
treated as negative addresses)  as tainted in an internal data structure.

Then for each call to a hooked function, the wrappers propagate the taint
information to any output buffers the function has. Data read from tainted
file handles is marked tainted. Files opened from tainted strings are as
well. If the inputs are tainted, it then checks for security problems.
First, it unwinds the stack and checks if the output buffer is in danger
of being overrun (including potential unchecked overruns) and logs a
potentially exploitable problem including the source of the taint
(environment variable, argument, file data, etc) along with the stack
offset. It does similar things for exec and the like.

The original idea was to use it to discover holes in existing application
binaries, but because most have inline string functions, taint data
doesn't get propagated - the hooks aren't called. But for stuff you build
yourself could be instrumented this way fairly easily.

As for fortifying GCC, there already exists a bounds-checking version I
believe. I suppose it could be extended to keep track of taint data in a
manner similar to how it tracks array sizes (which I assume is a hidden
size element).

If someone's interested in the (embarrassingly crufty) code I have now, I
might be persuaded to dig it out of my archives. Some assembly required.

--
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."