Hardness of detecting computer virii

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 S_A = \{\phi_i(x) | \phi_i(x) \textnormal{ is vurnable code}\} be the infinite set of all possible harmful programs. Further on, let S_B be the set of programs that terminates. Now, let \psi_i(x) be any program code. Choose any \phi_k(x) \in S_A (assume that we know of one, or can reproduce one). Now, modify \psi_i(x) such that \psi_i(x) calls \phi_k(x) before halting. We now use the oracle for deciding S_A to see if \psi_i(x) is a harmful program if \psi_i(x) 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 S_B \cup S_B^C. This will give us a false positive for Q_B, an infinitely large subset of S_B^C. 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 Q_B = \emptyset, 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s