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

[Oliver Xymoron <oxymoron at waste dot org>]

On Mon, 3 Jan 2000, Martin Dalecki wrote:

[I wrote:]
> > 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
> 
> Goedel tells you about axiomatic systems which encompass both ARITHMETIC
> and RECURSION.

Actually, recursion is sufficient to model arithmetic. There's a nice set
theory representation of integers that looks something like this: {} {{}}
{{{}}{}} {{{{}}{}}{}}. As for needing infinite space or storage to be
theoretically intractible, there are far more possible machine states in
even the most modest computer than you can ever hope to build a state
transition table for.

> And in practical cases in CAN BE PROVEN THAT PROGRAMMS DON'T CONTAIN 
> POSSIBLE OVERFLOWS. Like in the following example:
> 
> int main(int argc, char *argv[] )
> {
> 	return 0;
> }

Yes, but that is clearly in the set of uninteresting programs. Programs
that are interesting do things like parse email addresses or HTML. They
tend not to be very simple (or correct).

Consider the difficulty a C compiler has dealing with detecting pointer
possible aliasing and you'll see that static analysis of code paths is a
pain at best.

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