On Sat, 26 May 2007 Valdis.Kletnieks@vt.edu wrote:
On Sat, 26 May 2007 11:42:46 +0200, Pavel Kankovsky said:
From a theoretical POV, it might be possible do it with a program
requiring all memory of the tested system [...] to compute a correct
result. Several difficult conditions would have to be satisfied:
I'm not sure that's sufficient - [...]
If we are going to get a correct result (and those extra conditions are
satisfied) then we know that, at some point during the execution of our
program, the tested system has to pass through a certain well-defined
state and that state determines all its future states like a Cauchy
surface in physics (as long as the system stays isolated).
Well, we cannot really tell whether there was anything wrong with the
system before it reached the "Cauchy surface-like state" but we know
nothing undesired can survive when the system passes through it.
Any malware trying to cheat and hide itself will make the test fail
because there will not be enough memory to complete the computation--the
C. s.-like state is uncompressible and needs every bit of memory installed
on the tested system. The only way to avoid detection is to self-destruct.
I admit this kind of proof of integrity bears some similarity to proving
the window is broken by throwing a rock through it. :)
So you have to deal with all sorts of Turing/Godel issues.
Indeed. Kolmogorov complexity is this kind of issue.
(To be absolutely precise, it is not the true K. c. based on a universal
Turing machine but a computational K.-like c. based on the system being
investigated. This complexity is decidable (in theory) as long as the
system is deterministic and its memory finite.)
One important aspect that the system isn't just memory, it's the
combination of memory and architecture, which often means microcode.
So you also need to prove the microcode isn't tweaked [...]
"All memory" involves any aspect of the system mutable by the software. If
the microcode is mutable than the memory used to store it is a part of
"all memory".
I don't think you'll get any well-defined state other than "an extremely
expensive piece of dead silicon" from any real CPU when you fill its
microcode PROM with a string of uncompressible data but I said it was a
theoretical approach... :)
--Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."
_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/
