Malware and viral components – why do they pose a threat to the society? Isn’t there a universal remedy? Why is it so hard to detect virii? Because the problem is in fact impossible to solve (with some restriction!). That is not very surprising maybe, but can we prove it somehow?

In complexity theory (and many other sciences as well), one of the most important tools is reduction. If one can show that solving one problem A solves another problem B, then we can conclude that A is at least as hard as B: If one can make a caffe latte, then one can make an ordinary cup of coffee by just replacing milk with nothing. This implies that making a caffee latte is at least as hard as making ordinary coffee.

Ok, let us return to the viral problematics. Can we replace A with the problem of detecting viral components and B with some impossible problem? Yes – we can. We will use the Halting problem, a problem widely known to be impossible to solve.

The ‘attempted proof ‘ is really simple and goes as follows:

Let be the infinite set of all possible harmful programs. Further on, let be the set of programs that terminates. Now, let be any program code. Choose any (assume that we know of one, or can reproduce one). Now, modify such that calls before halting. We now use the oracle for deciding to see if is a harmful program if halts.

In other words, we create a program that is harmful if and only if the program terminates. So before the program terminates, it calls the harmful code. If it doesn’t terminate, it will not be harmful.

There is one flaw with the proof: there most certainly exist harmful code that does not terminate and the are in the set of all possible programs, that is . This will give us a false positive for , an infinitely large subset of . Why? Because the modified anti-viral oracle would say: this code is vulnerable, thus it will terminate  – but that is not true. Crap.

So we have to change the claim a bit, which could seem a bit artificial. Assume that we run all code in an isolated environment (like a virtual machine) where changes to the system can only be done once the code terminates and returns control to the system. Then, program must terminate in order to pose a threat to the system and therefore , i.e. no non-terminating harmful programs.

As we can see, everything boils down to the definition of ‘harmfulness’. Also, we don’t really need look for harmful programs, we can simply look for any changes in the system in order to see that it terminates. A consequence of this, is that it is as impossible to make a construction that detects virii as it is to construct something that detects changes of the system.