U.Va. Computer Scientists Look to Biological Evolution to Strengthen Computer Software

January 04, 2011

Listen to the UVA Today Radio Show report on this story by Marian Anderfuren:

January 4, 2011 — University of Virginia computer scientist Westley Weimer is following cues from biology to help create computer software that can teach itself how to thwart cyber-attacks and heal itself.

Weimer, along with computer science Ph.D. candidate Claire Le Goues, is working on the research as part of a team led by Stephanie Forrest at the University of New Mexico. The group recently secured a $3.2 million grant from the Defense Advanced Research Projects Agency, or DARPA, to develop more resilient software systems modeled after the biological concepts of immunity and evolution.

The research could be applied to an array of consumer computer-operated products and devices, from laptops and cell phones to anti-lock brakes and artificial-heart pumps. The U.S. Department of Defense, which funds the work through DARPA, is particularly interested for cybersecurity purposes.

"In biological systems, the skin and the immune system work together to fight off threats, and diverse populations mean that not every individual is vulnerable to the same disease," said Weimer, an assistant professor in the U.Va. School of Engineering and Applied Science's Department of Computer Science.

"Computer systems are not designed like this and they suffer. The question is: Can we gain insights from biological evolution and apply that knowledge to software systems?"

The researchers are using genetic programming techniques – the computational analogs of the evolutionary principles of random variation, selection and inheritance. The techniques can create more resilient software as desirable traits, in this case the ability to fend off attacks and self-repair, are passed on to successive generations of software.

The researcher's systems won't be designed to guard against a specific virus or type of attack, but instead could fix problems they encounter by working from a fundamental set of evolution-inspired programming instructions.

A key concept for the researchers will be to make sure software can automatically diversify programs to improve resiliency. Today millions of computers use the same operating systems, Internet browsers and e-mail clients, so cyber-attackers can exploit a single weak point in a system and cause wide-scale disruption.

"Economies of scale make software programs more affordable and it's easier to support and maintain them," Weimer said. "But with millions of people using the same programs, it's also easier for a single virus or invader to find just one attack surface and destroy everything – as in the unfortunate case of Dutch elm disease in botany."

Development of software that can automatically create different versions of programs means that cyber-attacks would affect a smaller fraction of users. This would lead to an evolution of more-resilient software as the system carries on successful traits and abandons less-successful ones.

The research hypothesizes that widely used programs "contain the seeds of their own repair," Weimer said.

That is, a program that accesses information incorrectly from one of its parts, leading to a security vulnerability, probably handles the information correctly in at least one of its other parts. The genetic algorithm takes pieces of code from one part of the program and transplants and adapts them to other parts. By trying and evaluating many such transplants, the technique can operate on a wide variety of programs and defects without having prior knowledge of a given program's structure.

The researchers have already successfully used genetic programming to de-bug more than 20 programs. For example, Microsoft's Zune 30 music player had a bug that created an infinite loop on Dec. 31, 2008, the last day of a leap year. The group's evolvable software was able to automatically work through 28 lines of code and fix the error in only 42 seconds.

Another important aspect of the group's research is the creation of adaptable software. Traditionally, software has been developed with "clean-slate" design methods to ensure that everything works correctly from the onset of use. While still working from the standard clean-slate platform, the group aims to create software that can also adapt over time to fend off threats that come with the addition of new programs.

Taking another cue from biology, the software system will use a distributed, decentralized search technique based on the behavior of ant colonies. Just as ant colonies can find food and make tunnels without an explicit, recognized leader, the search technique would allow multiple computers or mobile devices to work together to find the correct software fix. Melanie Moses, a professor in the UNM computer science department, will lead this aspect of the project.

The genetic programming approach means the researchers will also contend with the problem of introducing unwanted mutations into the software. To protect against destructive programs entering existing computer networks, the researchers run trials in a virtual machine. The programs are evaluated in simulations and unwanted traits are removed from subsequent generations of the software. 

"We essentially make a bunch of 'children' of a given programs and change the lines of codes in each one," Weimer said. "Most are well-behaved, except for the occasional problem child who self-programs infinite replicating loops that exhaust a machine's resources."

The group's software systems also will undergo what is known as "fuzz testing," where the researchers will attack their own systems to find weak points, develop patches for the weaknesses and then move onto the next logical weak points and develop additional solutions. Jed Crandall, professor in the UNM computer science department, is leading the testing.

While the research is now funded for defense purposes, it could also benefit the general public, which relies on computer systems for a variety of critical daily activities – "everything from cars' anti-lock brake systems to artificial-heart pumps relies on computer systems," Weimer said. "If Windows crashes, that's unfortunate. If your heart crashes, that's devastating."

Media Contact

Zak Richards

Senior Writer/SEAS