-----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED] Sent: Friday, December 02, 2005 6:39 PM To: [email protected] Subject: Re: [Full-disclosure] Most common keystroke loggers?
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. You're right, the particular problem of finding if a program exhibits "function X" is Rice's Theorem, which is related to the Halting problem, but is properly a subset of the problem. http://en.wikipedia.org/wiki/Rice%27s_theorem >> 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. Quoted (with minor changes of what the function does) from the Rice's theorem page referenced above: Suppose we have an algorithm for examining a program p and determining infallibly whether p is an implementation of a keystroke logger. The claim is that we can convert our algorithm for identifying key loggers into one which identifies functions that halt. We will describe an algorithm with takes inputs a and I and determines whether program a halts when given input i. The algorithm is simple, we construct a new program t which (1) temporarily ignores its input while it tries to execute program a on input i, and then, if that halts, (2) returns whether a keylogger was detected. Clearly, t is a function for finding keyloggers if and only if step 1 halts. Since we've assumed that we can infallibly identify programs for finding keyloggers, we can determine whether t is such a program, and therefore whether program a halts on input i. Note that we needn't actually execute t, we need only decide whether it is a squaring program, and, by hypothesis, we know how to do this. >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. _______________________________________________ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
