Re: Most common keystroke loggers?

[Nick FitzGerald <nick () virus-l demon co uk>]

foofus () foofus net to me to Jan:

> > Basically (and simplifying a lot), the Halting Problem means that you 
> > cannot write a computer program to determine if some other program 
> > exhibits "function X", _in finite time_.  
>
> I don't think this is what the Halting Problem means.  My understanding
> is that it means you can't write a program to determine if *any* other
> program exhibits "function X", in finite time.  For a particular
> program, however, this may be quite feasible.

But we were not talking about a "particular program" (other than in the 
bizarre sense that you consider the whole set of programs that makes up 
an entire OS and its application suite "a program").  Jan was 
suggesting "compromise detection" in lieu of an approach that could 
overcome the problems presented by a compromised system.  Thus, Jan's 
suggestion was for a _general_ compromise detection system (and that 
would effectively be so even if the solution space were to be limited 
to one contemporary OS as all such systems are so large and complex).

> > Thus, you cannot write a 
> > program to detect all viruses, you cannot write a program to detect key 
> > loggers, you cannot write a prorgram to detect all spyware, etc, etc.
>
> How do you know that the problem of detecting all keystroke loggers is 
> equivalent to the Halting Program?  Is there a proof somewhere that
> keystroke loggers do not share some characteristic that makes them
> detectable?  <-- I am not being sarcastic; this is an earnest question.

"Proof" -- no, but it seems it should follow from the general proof.  
My maths is not up to proving that though, but by analogy, it seems to 
me to be quite the same issue as Cohen's Ph.D. thesis proof that virus 
detection in general reduces to the Halting Problem (that is NOT the 
same thinkg as "known virus detection", which is what current AV 
products provide and why they need incessant updating to remain barely 
marginally useful).

> My formal CS background is weak, but I don't think the problem of
> programmatically detecting compromised machines of a given OS (not
> the general case of "compromised machines of any sort) ...

Actually, I don't think that helps you -- read the parts of the 
Wikipedia entry that talk about partial solutions...  The Halting 
Problem is a very powerful result in computability theory.

> ... has been proven 
> to be undecidable in the strong way that the Halting Problem has.  I may 
> be wrong, though, which is why I ask.

Likewise, I do not have the formal background to make that proof, but 
I'd be very surprised if that were not the case...


Regards,

Nick FitzGerald

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