TMCnet News

Unnatural selection
[July 21, 2006]

Unnatural selection


(New Scientist Via Thomson Dialog NewsEdge) WHEN the Code Red computer worm made its debut on 12 July 2001, it seemed harmless enough. A week later, it transformed into one of the worst attacks the internet has ever known. In the intervening days, someone had fixed a bug in the worm. This allowed it to spread like wildfire, striking computers at random by infiltrating a program called Microsoft Internet Information Services. Once lodged inside, Code Red sent copies of itself to other machines worldwide it is this ability to replicate that distinguishes worms from ordinary computer viruses. Within 24 hours it had infected over 350,000 machines .



The flood of online traffic was so intense it blacked out internet access to thousands of people in many parts of the US, and knocked out servers in scores of companies, including Associated Press and Fedex. What's more, Code Red carried a nasty surprise: each copy of the worm was designed to bombard the White House website with data in an attempt to crash it. To stay online, White House techies had to change the way data was routed to their site. Globally, damage from Code Red and its variants was estimated to have cost $2.6 billion.

Code Red was able to travel so far and so fast because it had an enormous pool of potential carriers. It exploited a vulnerability common to all computers running Microsoft's NT and Windows 2000 operating systems, and since variants of these account for over 90 per cent of all desktop computers, plus a third of all servers, there were an awful lot of suitable targets. The worm used a trick known to all worm-writers: identify a single flaw in the code for Microsoft's operating systems, and exploit it to quickly conquer the world.


For some insight into the problem, think of computers and the global network they form in biological terms. It is as if the internet were a planet inhabited almost exclusively by one species. Without any biodiversity, a single virulent flu virus could kill off all life. It's a well-known risk for "monocultures". This biological metaphor cuts both ways. It explains why our computers are frail, but it also suggests a potential solution. If our computers aren't "biodiverse" enough, why not add some diversity to the mix?

A vanguard of computer scientists is now trying to do precisely that: to take the computer monoculture and imbue it with "software diversity". The goal is to scramble our computers' software such that no two machines are completely alike. Many conventional computer viruses or worms would then find it much harder to spread.

How can you create this diversity? The same way that biology protects life on Earth: with mutations. Diversity within and among species has been driven by genetic mutations, which make it difficult for viruses to jump between species. The bugs that plague dogs and cats, say, don't often hurt humans, and vice versa. If the operating system software in computers also had mutations, the theory goes, our problems with computer viruses would fade away. "Every computer should have its own unique properties," says Stephanie Forrest, a computer scientist at the University of New Mexico in Albuquerque, who pioneered the idea.

Hack-proof machinesThe US military research organisation DARPA is pouring millions of dollars into software-diversity experiments in the hope of creating hack-proof computers that terrorists and criminals cannot penetrate. Early incarnations of the idea are about to make their way out of the lab: Microsoft itself is adding code-scrambling diversity to Vista, its long-awaited upgrade of Windows, which is due for release later this year.

To understand how software diversity works, you have to look at the way that worms, viruses and other intruders take control of computers. The Code Red worm, for instance, invades a computer using a trick known as a "buffer overflow". During an attack, the worm targets software on a computer that accepts data from a network it is connected to, such as a financial database that receives regular updates of share prices via the internet. The software expects incoming data to be in a standard format eight digits used to describe an account number, for example. Instead, the worm sends the computer an enormous string of gibberish with some malicious computer commands tacked on to the end.

Since the program has only allocated space in the computer's memory for an eight-digit number, the long string of gibberish data fills this space and then overflows into adjoining spaces, leaving the malicious commands stored in the computer's memory. Once inside, the operating system assumes it's a legitimate part of the program and innocently runs the malicious code.

This might sound sophisticated, but buffer-overflow attacks and "code injection" attacks that similarly sneak malicious coding into a running application are very easy to mount. About three-quarters of all computer viruses and worms use these techniques. "They are a very large source of the attacks we deal with," says Chad Dougherty, a security analyst with the Computer Emergency Response Team at Carnegie Mellon University in Pittsburgh, Pennsylvania.

Fortunately, buffer-overflow attacks have a weakness: the intruder must know precisely what part of the computer's memory to target. In 1996, Forrest realised that these attacks could be foiled by scrambling the way a program uses a computer's memory. When you launch a program, the operating system normally allocates the same locations in a computer's random access memory (RAM) each time. Forrest wondered whether she could rewrite the operating system to force the program to use different memory locations that are picked randomly every time, thus flummoxing buffer-overflow attacks.

To test her concept, Forrest experimented with a version of the open-source operating system Linux. She altered the system to force programs to assign data to memory locations at random. Then she subjected the computer to several well-known attacks that used the buffer-overflow technique. None could get through. Instead, they targeted the wrong area of memory. Although part of the software would often crash, Linux would quickly restart it, and get rid of the virus in the process. In rare situations it would crash the entire operating system, a short-lived annoyance, certainly, but not bad considering the intruder had failed to take control of the machine.

Linux computer-security experts quickly picked up on Forrest's idea. In 2003 Red Hat, the maker of a popular version of Linux, began including memory-space randomisation in its products. "We had several vulnerabilities which we could downgrade in severity," says Marc J. Cox, a Red Hat security expert.

Still, Linux is used on a small minority of computers worldwide , and most viruses and attacks are aimed at computers using Windows operating systems. That means the true test of memory randomisation will come next year when Microsoft releases Vista. The latest version of this next-generation operating system uses memory randomisation for several key components. "We'd been talking about it for a while, and finally said, 'Let's bite the bullet,'" says Michael Howard, a senior security program manager for Microsoft. He says the fact that the company's top executives approved the step, which has required a significant overhaul of Windows' code, indicates how seriously they are taking security threats. "This isn't just like changing a couple of things. This is moving everything around," Henderson says.

Memory scrambling isn't the only way to add diversity to operating systems. Even more sophisticated techniques are in the works. Forrest has tried altering "instruction sets", commands that programs use to communicate with a computer's hardware, such as its processor chip or memory.

Her trick was to replace the "translator" program that interprets these instruction sets with a specially modified one. Every time the computer boots up, Forrest's software loads into memory and encrypts the instruction sets in the hardware using a randomised encoding key. When a program wants to send a command to the computer, Forrest's translator decrypts the command on the fly so the computer can understand it.

This produces an elegant form of protection. If an attacker manages to insert malicious code into a running program, that code will also be decrypted by the translator when it is passed to the hardware. However, since the attacker's code is not encrypted in the first place, the decryption process turns it into digital gibberish so the computer hardware cannot understand it. Since it exists only in the computer's memory and has not been written to the computer's hard disc, it will vanish upon reboot.

Forrest has tested the process on several versions of Linux while launching buffer-overflow attacks. None were able to penetrate. As with memory randomisation, the failed attacks would, at worst, temporarily crash part of Linux a small price to pay. Her translator program was a success. "It seemed like a crazy idea at first," says Gabriel Barrantes, who worked with Forrest on the project. "But it turned out to be sound."

Persistent attackersIt is still possible for a hacker to subvert these techniques. The weakness in any form of randomised encryption is that it is vulnerable to a "brute force" attack. Just as few mutations in the natural world will confer any advantage, so in the computing world, virus writers can create a code that mounts repeated attacks, changing the approach each time until it hits on the form of randomisation being used.

In 2004, a group of researchers led by Hovav Shacham at Stanford University in California tried this trick against a copy of the popular web-server application Apache that was running on Linux, protected with memory randomisation. It took them 216 seconds per attack to break into it. They concluded that this protection is not sufficient to stop the most persistent viruses or a single, dedicated attacker.

Last year, a group of researchers at the University of Virginia, Charlottesville, performed a similar attack on a copy of Linux whose instruction set was protected by randomised encryption. They used a slightly more complex approach, making a series of guesses about different parts of the randomisation key. This time it took over 6 minutes to force a way in: the system was tougher, but hardly invulnerable.

These attacks set off a vibrant debate in security communities about precisely how secure operating system diversity needs to be. Some shrug off the brute-force experiments. If randomisation can buy even a few extra minutes, that's enough, they say. A computer could be programmed to detect a brute-force attack by noticing, for example, that certain parts of an operating system are repeatedly crashing, and automatically closing off internet access to the attacker while leaving other network connections intact.

As in nature, a computer system might not need perfect immunity to survive. Dan Geer, an epidemiologist who studies computer security, says that even if only a fraction of computers using the internet were made diverse, it could break up the monoculture sufficiently to halt many digital attacks. The internet would have what epidemiologists call "herd immunity". "Maybe you are not immune to a disease, but if enough animals in your herd are, you won't get sick because the disease can't travel," Geer says. DARPA has embraced this idea, and the goal of its project is to develop systems in which no more than 33 per cent of the computers are susceptible to any one vulnerability.

"It's a cat-and-mouse game," says R. Sekar, a computer scientist at the State University of New York at Stony Brook. "You develop a defence, and the attackers try to work around it." Memory randomisation, he thinks, will eliminate the vast majority of viruses and worms that use buffer-overflow attacks simply because they are not very sophisticated. They cannot mount brute-force attacks, and if their first assault doesn't work, they expire. Only a more determined hacker would get past.

There are still fundamental limitations hampering the use of memory randomisation, according to John Knight of the University of Virginia. Make the randomisation too complex and it could cause conflicts between programs. Indeed, many real-world examples of memory randomisation, such as the protections in Microsoft's Vista, set a maximum of 256 possible ways to scramble the memory to avoid such conflicts. "That is not enough to be really robust," Knight says. Proponents of the system, however, respond that their techniques raise the bar high enough to defeat all but the most talented attackers.

Knight says that randomising the encryption on the instruction set is a more powerful technique because it can use larger and more complex forms of encryption. The only limitation is that as the encryption becomes more complicated, it takes the computer longer to decrypt each instruction, and this can slow the machine down. Barrantes found that instruction-set randomisation more than doubled the length of time an instruction took to execute. Make the encryption too robust, and computer users could find themselves drumming their fingers as they wait for a web page to load.

So he thinks the best approach is to combine different types of randomisation. Where one fails, another picks up. Last year, he took a variant of Linux and randomised both its memory-space allocation and its instruction sets. In December, he put 100 copies of the software online and hired a computer-security firm to try and penetrate them. The attacks failed. In May, he repeated the experiment but this time he provided the attackers with extra information about the randomised software. Their assault still failed.

The idea was to simulate what would happen if an adversary had a phenomenal amount of money, and secret information from an inside collaborator, says Knight. The results pleased him and, he hopes, will also please DARPA when he presents them to the agency. "We aren't claiming we can do everything, but for broad classes of attack, these techniques appear to work very well. We have no reason to believe that there would be any change if we were to try to apply this to the real world."

Yet the quest for even more secure forms of diversity is continuing. Knight is developing a new concept that promises to be even tougher to crack. Each computer will use two processor chips running separate copies of a program that are randomised in different ways. The two copies work in parallel, so that each time the user enters data, both copies receive the input and respond in the same way. The user, in effect, experiences one seamless application and doesn't know that two copies of the same software are running in parallel.

The advantage of doubling up? It would be hair-pullingly hard for an intruder to break in unnoticed. If a hacker tried a brute-force attack, each attempt would be copied and sent to both processors. Since each processor is randomised in a different way, no single attack could work on both processors at once. Even if an intruder managed to gain control of one processor and forced it to do something illicit, the system would notice that its two processors were out of step, and shut down.

There is a downside: crafting such a system is the hardest thing Knight has ever tried. "I gave it to one of our researchers, and he came back a couple of days later saying, 'Do you have any idea how difficult this is?'" he laughs.

No one ever said that spicing up the monoculture would be easy. When it comes to defeating digital disease, the battle is likely to rage for years, but at least our virtual immune system is starting to look a little healthier.

Clive Thompson is a writer based in New York

[ Back To TMCnet.com's Homepage ]