Re: Re New Binary Bruteforcing Method Discovered

From: Blue Boar (BlueBoar@thievco.com)
Date: 03/27/02 

Date: Wed, 27 Mar 2002 13:48:02 -0800
From: Blue Boar <BlueBoar@thievco.com>
To: Michal Zalewski <lcamtuf@coredump.cx>

Michal Zalewski wrote:
>
> > Oh, this is a known problem as well? :) Well, pressing CTRL+C usually
> > does the trick. Then again, of course you can write a little program to
> > enumerate processes in the group of the shell process running the
> > library interception tests, then check their activity time and send them
> > appropriate signals to continue when they stall...
>
> Hello? I think you do not really understand what I was trying to say - try
> 'Turing "halting problem"' in google.com.

What he is trying to get at is that you can define a fixed amount of
time as a maximum, and simply kill the process at that point, if you
don't have an answer yet.

> Nowadays, the analysis of all
> possible execution paths for any given program (for example to find an
> answer whether certain code will be executed or not, and in what order - a
> critical issue for static, automated detection of dynamic vulnerabilities)
> is excessively time consuming and completely not feasible in most cases.

Naturally, any claim that "all vulnerabilities can be found" by a
Turing machine is incorrect. Having a fixed timer will find many
that fall into a certain class... such as simple overflows or
format strings in initialization code involving command-line
options or environment variables.

As a counter example, I believe there was a bug in Win9x that caused
it to crash after the machine had been up 90-something days straight.
Some tick counter maxed out. There's a good example of something
that running a program for 1 minute won't catch.

                                        BB