Cohen's problem

Fred Cohen determined theoritically that viral detetction is an undecidable problem. Can anyone provide an intuitive reasoning for that?

Background

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

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

• Excellent answer, with a great example too. I hadn't heard of this problem. I guess Turing-completeness factors into this too? Commented Sep 4, 2012 at 5:57
• @Polynomial: Turing-completeness comes into the picture the following way: the halting problem is about deciding whether a program which runs on a Turing machine will halt. Turing-completeness implies undecidability of the halting problem (a "Turing-complete" programming language is one which allows to implement a Turing machine, and thus anything that a Turing machine can compute). Commented Sep 4, 2012 at 17:27

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: