Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
Fred Cohen determined theoritically that viral detetction is an undecidable problem. Can anyone provide an intuitive reasoning for that?
Fred Cohen experimented with computer viruses and confirmed Neumann's postulate and investigated other properties of malware such as detectability, self-obfuscation using rudimentary encryption, and others. His 1988 Doctoral dissertation was on the subject of computer viruses
Sure. In Cohen's famous result, he says that a perfect virus detector should emit an alarm if and only if the input program can ever act like a virus (i.e., infect your machine and do damage).
Consider the following program:
f();
infect_and_do_damage();
where f() is some harmless function, and infect_and_do_damage() is a viral payload that infects your machine and does all sorts of damage (wipes your hard disk, steals all your money, whatever).
Let's consider what a perfect virus detector should say about this program:
If f() can return, this is a virus and the virus detector should emit an alarm.
On the other hand, if f() always enters an infinite loop and never returns, then the second line is dead code, infect_and_do_damage() will never be invoked, this program will never act like a virus, and the virus detector should not set off any alarms.
So, the problem of determining whether this code is a virus is equivalent to the problem of determining whether the function f() can ever halt. That's the famous halting problem, which is known to be undecidable.
In other words, detecting whether a program is a virus is at least as hard as detecting whether a program will halt. Thus, both problems are undecidable.
Note that this is a purely theoretical result. Undecidability is a purely theoretical construct. The fact that a problem is undecidable is not the end of the conversation; it is merely the beginning of the conversation.
In practice, there are various ways to attempt to deal with undecidability: e.g., try to write a solution that is probabilistically correct, even if it is not always correct on all programs; try to find a solution that works for the set of programs you're likely to find in practice, even if it doesn't work on all programs; allow the solution to occasionally answer "I don't know" or to err on the side of declaring a program a virus (or err on the side of false negatives); and so on.
So you should not treat this as a definitive statement that virus detection is impossible -- just because the problem is undecidable doesn't mean it is necessarily impossible to find a good-enough solution in practice. But it does identify some fundamental barriers to building a perfect virus detector.
To complement @D.W.'s answer: even if the halting problem could be solved, there is also an inherent definition issue: what is a virus, anyway ?
For instance, as the joke goes, Microsoft Word is a virus:
In what ways can Word not be a virus ?
Of course, many people (including Microsoft's lawyers) would argue that Word is not a virus and that it is a ridiculous assertion. However, this shows that the not-a-virus property is macroscopic: it is not a clear-cut distinction coming from the code alone (by "macroscopic" I mean that it is an emergent property of the whole, not of any of the assembly opcodes in the executable).
Let's take a less outrageous example: the installer for a Linux operating system. Is it code ? Yes. Does it copies itself ? Yes, indeed. Does it modify the boot sector ? Absolutely. Does it alters the operating system already in place on the machine ? Oh yes. The one property which makes it a non-virus is that whenever the installer does all of the above, the human user wants it that way.
It follows that a perfect antivirus must somehow guess what the user wants. And there cannot be an absolute answer to that. In practice, most antivirus software try to make "educated guesses" and, when it comes down to it, decide what the user should want (that's how I spent one frustrating hour this morning trying to send an executable file to a customer: some antivirus have decided that I cannot possibly want to send an executable file by email).
