Re: Gödel and kernel backdoors

[Valdis.Kletnieks () vt edu]

On Mon, 20 Sep 2010 01:03:21 PDT, Hurgel Bumpf said:
> The solution could be a virtualized operating system, which has a control 
> layer between the operating system and the hardware abstraction layer. Changes
> to data could be non-persistent in the first step, and only written to
> the hdd after a heuristic check of the changes and a interaction with the user.

Actually, that's a very useful tool that you can even deploy today: Just use
the 'checkpoint' feature of a VMWare or similar tool, and keep around some
checkpoints that you're reasonably sure contain no malware.

Unfortunately, it suffers from the same exact Godel issue as any other system -
you simply *cannot* make that "heuristic check" 100% guaranteed correct and
accurate. (In fact, by definition a heuristic check *can't* be 100% accurate -
if a heuristic was perfect, it would be called an algorithm).

The point that everybody seems to be missing is this:

Godel, Turing, and all proved that you can't make that check 100% correct. They
said *nothing* about the possibility of building a checker that's 99.99998%
accurate (and in fact, that's totally within the realm of mathematical
possibility).  There are *real* problems that Godel says *nothing* about but
the real world does:

1) Making that mathematically possible 99.99998% accurate checker may require
so much simulation and state tracking that launch times for programs will be
measured in years or decades - as a practical matter, users may not want more
than 2 or 3 nines.  Heck, they whinge about the overhead of *current*
anti-malware.

2) With the plethora of complicated objects on the average computer system,
raising the "is javascript/vi modelines/whatever  data or executable code"
issues, we don't even have a clue how to do better than 95% or so.  So as an
industry, let's not bother worring about that Godel issue until we know how to
get to 99% and still have users happy with the overhead involved.

Attachment: _bin
Description:

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/