Export or edit this event...

CS Colloquium: Repairing software automatically using evolutionary computation

Portland State University Fourth Avenue Building (FAB)
1900 SW 4th Ave.
Portland, OR 97201, US (map)



Stephanie Forrest University of New Mexico

FAB 86-01


A pressing challenge for computer science over the next decade is reducing the total cost of software. This includes the billions of dollars that are lost each year from software defects. The number of software defects far outstrips the resources available for repairing them, and most software is shipped with both known and unknown bugs. This problem arises because human programmers still develop, maintain, and repair computer programs largely by hand, despite many years of progress in machine learning and artificial intelligence. The talk will describe recent research that shows how evolutionary computation can be combined with program analysis methods to automatically repair bugs in off-the-shelf legacy C programs. Once a program fault is discovered, evolutionary algorithms are used to generate program variants until one is found that both retains required functionality and avoids the defect in question. Standard test cases are used to represent the fault and to encode program requirements. Once a successful variant is discovered, structural differencing algorithms and delta debugging methods are used to minimize its size. Initial results will be presented on a wide range of C programs, including security vulnerabilities such as integer overflow, denial of service, format string, and buffer overflow. Finally, the talk will describe how the automatic repair mechanism can be combined with anomaly intrusion detection to produce a closed-loop repair system.


Stephanie Forrest is Professor and Chairman of the Computer Science Department at the University of New Mexico in Albuquerque. She is also an External Professor and has served on the Science Board and as Vice President of the Santa Fe Institute. Professor Forrest received M.S. and Ph.D. degrees in Computer and Communication Sciences from the University of Michigan (1982,1985) and a BA from St. John's College (1977). Before joining UNM in 1990 she worked for Teknowledge Inc. and was a Director's Fellow at the Center for Nonlinear Studies, Los Alamos National Laboratory. Her research studies adaptive systems, including evolutionary computation, immunology, biological modeling, and computer security. In security, she is best known for her early work using system calls for anomaly intrusion detection and her more recent work on automated diversity. She was a recipient of the NSF Presidental Young Investigator's Award and has recently served on the NSF GENI Science Council, the NSF CISE Advisory Committee, and the UCLA CENS Advisory Board.