Re: Ants, trees, etc.

[Jonatan B <onatan () gmail com>]

On 6/22/05, David Klotz <bucky () speakeasy org> wrote:
> The halting problem essentially says you can't write a general program which
> will verify whether ALL programs will halt or not (when using a computer with
> infinite memory by the way).  While not an expert on this,
> I suspect you could also use it to formally prove you can't write a general
> algorithm that determines if ANY two programs behave the same on ALL input.
>
> However, I don't believe it prohibits you from writing an algorithm which takes
> two simple pieces of code, some static set of input, and seeing if the code
> behaves the same on that input.  If it did, I don't think we could do any
> automated code analysis, no?
<snip>
> > First of all i might be talking out of my uhm bottom, but i never understand
> > the references to the halting problem that are throw around very often.
> > As i understand the halting problem basicly states:

[From Wikipedia]:
In computability theory the halting problem is a decision problem
which can be informally stated as follows:

"Given a description of an algorithm and its initial input, determine
whether the algorithm, when executed on this input, ever halts
(completes). The alternative is that it runs forever without halting."

Alan Turing proved in 1936 that a general algorithm to solve the
halting problem for all possible inputs cannot exist. We say that the
halting problem is undecidable.
[End Wikipedia]

In-fact, we bump our collective heads against the halting problem
whenever we have to
write a program (or an algorithm) that analyzes all the possible code
paths of a program
(or an algorithm). Solving it means walking all the code paths means that
for every possible input,
   running on every possible environment
   (OS, CPU, ENV vars, Endianess, yadda yadda),
   we store the output
   (and registers and ENV, yadda yadda),
and compare the outputs to each-other.
Iff all the outputs are equal, then the blocks do exactly the same thing.
While the problem is stated as the issue of finding if a program (or
an algorithm) ever halts,
I personally (read: I could be wrong but it feels like) it would have
been undecidable if we
tested for any other case. For example, "will a user controllable
buffer overflow?", or in this
case "will the reordered block of code will do exactly the same thing
as the original, given
the same input".

Maybe it will never overflow unless very specific requirements are met:
http://www.guninski.com/where_do_you_want_billg_to_go_today_4.html

I might be wrong. Specifically, because it might be very feasible to test that 
> register contents and the state of the stack
are equal in the new block.
_______________________________________________
Dailydave mailing list
Dailydave () lists immunitysec com
https://lists.immunitysec.com/mailman/listinfo/dailydave