Ruling Over Unruly Programs

And why theoretical security is theoretically impossible, and how to tell good programs from bad ones

By Simson Garfinkel

September 01, 2003 — CSO — Trojan horses. Keyboard loggers. Viruses. Bad insiders. Bad outsiders. Evil-doers. Perforated firewalls. Corrupt backups. Spam. A few years ago, many security professionals I knew looked forward to the day when the majority of the world's computer security problems were worked out. Back then, we thought that improving security was just a question of deploying technology, providing training and getting people to follow the appropriate procedure. But a look at computer science theory proves otherwise.

A fundamental goal of computer security has been to put some sort of restrictions on program execution. For example, worms and viruses wouldn't be a problem if they didn't damage our files, reformat our hard drives and e-mail themselves to everybody in our address books. If there were just some way we could stop the bad programs from doing what we don't want, without affecting the execution of the good programs, our problem would be solved.

But to stop the bad programs, we're going to need some way of distinguishing the bad from the good. That is, we're going to need a pro-gram-analyzing program that can look at any given suspect program and determine if it has any hostile code. If it doesn't, then the suspect application is safe to run. Security is simple.

But, as it turns out, writing such a program-analyzing program is theoretically impossible.

The impossibility stems not from legal issues, such as determining whether a programmer had "criminal intent", but from a technical conundrum. The mathematics of computing make it impossible to write software that can figure out what other programs can do, prior to execution.

To be sure, it is possible to write programs that can examine simple programs and determine what they do. But there's the problem: In principle, there is no way to examine a program's instructions and figure out precisely what it does. That's because it is too complicated. In principle, running the software is the only way to discover what it does. And once a hostile program is run, it's too late: The damage has been done.

That's why today's antivirus systems don't try to predict what an infected program will do. Instead, these systems have a list of "signatures," or sequences of bytes, that have been observed in existing viruses. If the copy of Microsoft Word that's about to be run contains the same copy of bytes that were discovered years ago in the Michelangelo virus, for example, then that copy of Word is deemed infected and is not permitted to run.

• Print