U.Va. Computer Scientists Look to Biological Evolution to Strengthen Computer Software
As appeared in UVA Today, January 4, 2011
By Zak Richards
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."
More news about Mary L Soffa
- Alliance for Computational Science and Engineering Helps Make Students and Faculty 'Research-Ready' (Mary L Soffa)
- UVA Today, January 6, 2011 (Local Copy)
- U.Va. Computer Scientists Look to Biological Evolution to Strengthen Computer Software (Mary L Soffa)
- UVA Today, January 4, 2011 (Local Copy)
- U.Va. Computer Scientists Join $13 Million Project to Secure Software of Unknown Origins (Mary L Soffa)
- UVA Today, November 23, 2010 (Local Copy)
- U.Va.'s Applied Research Institute Developing More Robust Communications Platform for First Responders (Mary L Soffa)
- UVA Today, November 12, 2010 (Local Copy)
- U.Va. Professor Emerita Anita Jones Wins NAE's 2010 Arthur M. Bueche Award (Mary L Soffa)
- UVA Today, October 12, 2010 (Local Copy)
- Jack Stankovic awarded 2010 Distinguished Faculty Award (Mary L Soffa)
- UVA SEAS website, October 1, 2010 (Local Copy)
- U.Va. Researchers Land $2 Million NSF Grant to Design 'Smart Building' Energy Systems (Mary L Soffa)
- UVA Today, September 23, 2010 (Local Copy)
- Kim Hazelwood one of top young innovators (Mary L Soffa)
- UVA Today, August 30, 2010 (Local Copy)
- Computer Science Legend Anita Jones Retires from the Engineering School (Mary L Soffa)
- UVA Today, August 30, 2010 (Local Copy)
- abhi shelat named Microsoft Research Fellow (Mary L Soffa)
- UVA Today, July 12, 2010 (Local Copy)
- Jason Mars receives Google Fellowship (Mary L Soffa)
- UVA Today, June 28, 2010 (Local Copy)
- Seven Young Faculty Innovators Selected for U.Va.'s FEST Awards (Mary L Soffa)
- UVA Today, June 15, 2010 (Local Copy)
- Sudhanva Gurumurthi recives $1M Google Research Award (Mary L Soffa)
- UVA Today, February 10, 2010 (Local Copy)
- U.Va. Computer Science Department Celebrates 25th Anniversary with 'Father of the Internet' (Mary L Soffa)
- UVA Today, February 1, 2010 (Local Copy)