Undetectable Computer Virus (scientific paper in 2000)

[b]Cohen's Result[/b]

In [1], Fred Cohen demonstrates that there is no algorithm that can detect the set of all possible computer viruses (returning “true” if and only if its input is an object infected with some computer virus). The proof is a simple diagonal argument, like Cantor’s proof of the uncountability [3] of the real numbers, or Turing’s proof of the undecidability of the Halting Problem [4]. For any candidate computer virus detection algorithm A, there is a program p, which reads:

if A(p), then exit; else spread

Clearly A does not return the correct result when called on p, since if it returns “true” (i.e. it says that p is infected), then p just exits (and is therefore not infected), whereas if A returns anything else (i.e. it says that p is not infected), then p spreads (and is therefore infected).[1] So there is no algorithm which detects all viruses without error; any program that attempts to detect all viruses will either miss some infected files (a false negative), accuse some non-infected files of being infected (a false positive) or fail to return anything (a bug).

See original article here: http://www.research.ibm.com/antivirus/SciPapers/VB2000DC.htm