There are two techniques that AV products use to try to spot viruses. I have dealt extensively with one of these—the use of signatures—in articles I’ve posted as part of the AVID (Anti-Virus Is Dead) campaign. Signatures are like fingerprints and can be used to spot known malware.

You can be slightly cleverer with signatures than to just take a signature of a whole executable, you can also keep signatures of code (just a part of the executable) that tends to be repeated by virus writers. This is a sensible idea because virus writers share libraries of code that they use to build a new virus. Taking a signature in this way makes their life a little harder. Unfortunately the signature-only approach suffers from the fact that it is really unlikely to stop a new virus.

So most AV companies add routines that try to spot virus behaviour. Behaviour spotting techniques are sometimes referred to as heuristic techniques, although if we were to be pedantic we might object to the word “heuristic”. In Computer Science the term “heuristic” usually means the use of automated iterative approximation-based feedback, aimed at getting increasingly close to a target. AV behaviour spotting techniques may get updated to include new behaviours but that is manual rather than automatic.

So what is wrong with spotting viruses by profiling? Let’s consider a mathematical theorem (are you kidding? yes, I’m sorry, it’s all dreadfully academic isn’t it). I quote from the Wikipedia: “Leonard Adleman (the A in RSA) presented a rigorous proof that, in the general case, algorithmically determining whether a virus is or is not present is Turing undecidable”. This means that you cannot know for sure whether an executable is a virus by its behaviour. (This is also a proof that current AV technology can never work perfectly).

What it means in practice is that with heuristics you risk getting too many false positives, because what viruses do, other software also does (like store files, access the network, and even log the stream of characters from the keyboard). You are also beset with the difficulty that the virus has to run for you to spot it’s behaviour. (You cannot know its behaviour from looking at its code because the code can be disguised).

Now, if you combine heuristics with whitelisting and greylisting you have something valuable. If an executable is new and you run it in a sandbox it (i.e. put it on the grey-list) and stop any virus behaviours (like accessing any other computer or saving or updating any executables) then you have something workable. (Which is what the products from SecureWave, AppSense, Bit9 and Savant Protection do).

Odd though it may seem, the real problem with heuristics and with signatures are exactly the same—the virus writer can buy the software and test his viruses against the products to see if they get through. The virus writer can also test his work against the whitelisting products. For over two years now, SecureWave has run a computer on the Internet with all its ports open, offering a challenge to any hacker to try and break in—with a virus or with anything else. It has never been hacked. Here’s the URL if you want to try to break it.