Re: Most common keystroke loggers?

[foofus () foofus net]

On Sat, Dec 03, 2005 at 12:22:17PM +1300, Nick FitzGerald wrote:
> Ahh, no...
>
>    http://en.wikipedia.org/wiki/Halting_problem
>
> 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.

> 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.

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) 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.

--Foofus.


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