RE: New Binary Bruteforcing Method Discovered
From: Michael Wojcik (Michael.Wojcik@microfocus.com)Date: 03/28/02
 Previous message: auto12012 auto12012: "Re: Behavior analysis vs. Integrity analysis [was: Binary Bruteforcing]"
 Maybe in reply to: pr0ix@hushmail.com: "New Binary Bruteforcing Method Discovered"
 Next in thread: Michal Zalewski: "RE: New Binary Bruteforcing Method Discovered"
 Reply: Michal Zalewski: "RE: New Binary Bruteforcing Method Discovered"
 Reply: Blue Boar: "Re: New Binary Bruteforcing Method Discovered"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
From: Michael Wojcik <Michael.Wojcik@microfocus.com> To: vulndev@securityfocus.com Date: Thu, 28 Mar 2002 06:56:51 0800
> From: mixter@2xs.co.il [mailto:mixter@2xs.co.il]
> Sent: Wednesday, March 27, 2002 4:06 PM
>
> On Wed, 27 Mar 2002, Michal Zalewski wrote:
>
> > Knowing the way to solve the halting problem for infinite
> > Turing machines in finite time would very likely enable us to
> > perform this analysis for finite machines in no time (and have
> > dramatic implications not only for computer security).
The Halting Problem isn't an unsolved conjecture (like P!=NP), it's a proven
theorem. Turing's proof shows that no Universal Turing Machine can solve
the HP (in finite time, which is the whole point of the HP). By extension,
no machine less powerful than a UTM can solve it. That includes digital
computers, which are just resourceconstrained Turing Machines. There's no
"knowing the way to solve" it to be had.
Quantum "computers" (which aren't precisely digital) *might* be a different
story, but I've never seen a QC algorithm that gets around Turing's proof.
It would have to be a QC algorithm that for some reason can't be simulated
on a digital computer, which seems very unlikely to me, but I'm not a QC
expert by any means. (Ditto any other sort of nondigital computing device
 for it to be able to avoid Turing's proof, it has to be more powerful than
a UTM, and hence couldn't be simulated by a UTM.)
The proof's very simple  it's just a matter of selfreferential proof by
negation, where you assume a machine that solves the HP exists, then you
tinker with it a bit and feed it to itself. It's similar to Godel's
Incompleteness proof. Any decent intro to computer science covers it.
> Would you say that human beings can theoretically solve this
> problem
If the human mind is a Turing Machine, then no. That the human mind is a
Turing Machine is an unproven conjecture. Some people (Roger Penrose, for
example) believe it to be false.
> If so, do you think AI could eventually solve the problem...?
No AI algorithm executing on a digital computer can solve the Halting
Problem. Ever. End of story.
Now, the HP is a strong problem: solving it means being able to take *any*
program and tell whether it will eventually halt. Turing's proof shows that
there's a class of programs which can never be analyzed for "haltingness" by
a UTM (and since it's possible to turn any binary program characteristic
into a haltorloop situation, that covers any other aspect of program
analysis), but that doesn't mean that some UTM algorithm couldn't be devised
that analyzed "most" of the "interesting" programs that would likely be fed
to it. What the HP proof does  as Michal originally pointed out  is
strike down absolute claims like "this analysis program can find any bug".
Michael Wojcik
Principal Software Systems Developer, Micro Focus
Department of English, Miami University
 Previous message: auto12012 auto12012: "Re: Behavior analysis vs. Integrity analysis [was: Binary Bruteforcing]"
 Maybe in reply to: pr0ix@hushmail.com: "New Binary Bruteforcing Method Discovered"
 Next in thread: Michal Zalewski: "RE: New Binary Bruteforcing Method Discovered"
 Reply: Michal Zalewski: "RE: New Binary Bruteforcing Method Discovered"
 Reply: Blue Boar: "Re: New Binary Bruteforcing Method Discovered"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
