• silicon.com
• Technology
• Security

By Neil Barrett, 18 May 2005 13:10

COMMENT To explain why antivirus software is so limited and malicious code so hard to detect, Neil Barrett goes back to the very origins of modern computing.

Some statements are undoubtedly true; I am an adult male. Others undoubtedly false; I can breathe underwater. And some of them need more information; I live in a house with a green-tiled bathroom. You can visit my house, you can ask my family; it is decidable, provided that you can get some more information.

There are, however, some statements that are entirely un-decidable; even with extra information - or indeed, with every piece of information possible - these statements cannot be determined to be true or false. The most famous example is: 'This statement is false.' If it's true, it's false; if it's false, it's true. It is a perfectly well-formed, grammatically correct statement for which we cannot assign a true or false value.

These are the sorts of statements to confuse children but they proved to be an anathema to mathematicians, whose purpose in life is to determine whether or not well-formed mathematical expressions are true or false. If statements such as 'this statement is false' have analogues in the language of mathematics, then there are expressions that cannot be decided - and so the mathematicians have set themselves an impossible task. This became important at the start of the 20th Century, when mathematicians such as David Hilbert and Kurt Gödel tried to establish mathematics on the most rigorous possible foundations; they were trying to prove that mathematics was complete and self-consistent.

Unfortunately, they managed instead to prove that it wasn't - but on the road to that discovery, they managed to invent computers, help to win World War II and built our modern 'information age'.

The person who, more than any other, was responsible for laying the foundations of this work was the incomparable genius, Alan Turing. He produced not only an answer to the Decidability Problem but did so with an imaginative technique that showed us how to build automatic mathematicians - computers which first solved the puzzle of the Enigma cipher machines, turning the tide of the U-Boat war, and then solved everything from payroll to rocket launches. He did this by designing what has come to be known as a 'Turing Machine', an idealised version of a mathematician manipulating mathematical symbols - turning statements into alternative statements, converging on an answer to any form of calculation that can be expressed.

The machine has an infinitely long tape containing discrete cells, each of which contains a symbol. It also has a unit which can read or write those symbols, with the position and value of the written symbol determined by a small set of simple rules based on the values read. The unit moves along the tape, reading and altering the symbols so as to change the contents of the tape from the original 'problem' into the final 'answer'. When the final answer is produced, the Turing Machine halts. Any problem for which the machine halts is soluble, or 'decidable'; any for which it doesn't are 'un-decidable'. Turing proved that there were well-expressed mathematical statements for which the machine would never reach the halting state - and so there are indeed un-decidable statements.

The Turing Machine is an enormously powerful concept, providing mathematicians with a simple, mechanistic way of considering their task. But a Turing Machine that is actually constructed is an even more powerful device; it becomes an entirely automatic mathematician, a programmable computer able to perform any calculation. Perhaps the most important step in this direction was taken by Turing's former colleague at Princeton, John von Neumann, who produced the design to implement the machine physically and who gave us the modern computer.

In the language of mathematics, a computer program is a Turing Machine and a computer - a device able to run any Turing Machine - is called a 'Universal Turing Machine', a mathematical model able to interpret any mathematical model. One feature of Turing's work, though, was to show that there are programs which cannot be run to completion - programs which are the analogues of 'this statement is false' and cannot therefore be decided.

What does this mean for information security? In essence, we want to know in advance whether a given sequence of changes to data - a program - is going to be 'harmful' or not. Unfortunately, in 1986, Fred Cohen managed to prove that the problem of determining whether a piece of program was a virus was indeed an un-decidable problem. A Turing Machine to run the analysis would never halt; the only way to determine the effect of the program was actually to run it and see.

This is an enormously important result. It means the task of the antivirus program is mathematically impossible. By extension, the task of determining in advance whether any program will have a harmful effect is equally impossible. The only way of establishing what a program will in fact do is to allow it to execute and then to look at the state of the computer's memory. If the task of information security is to predict whether a given program will have a harmful effect on the data state, then this is impossible.

The implication is that the mathematical model of computation has insecurity implicit within it because we know that we cannot know ahead of time whether something will or will not be damaging. To borrow a phrase from my colleague Stephen Castell, computers are "ontologically insecure" - whether they are built on the von Neumann or any other architectural model.

Of course, this isn't the final word. Antivirus programs do exist and perform a vitally important task - as do intrusion detection systems, segregated memory models and a host of other solutions. But we should be conscious that each of these solutions can do nothing more than plug the occasional hole in the dyke. For true information security, we need to call on something that isn't bound by the Turing Machine model: we need to step outside the problem and examine it differently; we need to apply the real-world, human perspective to it - a perspective that is fascinated but not foxed by 'this statement is false'.