A multidisciplinary team led by Carnegie Mellon University computer scientist Edmund M. Clarke has received a five-year, $10 million grant from the National Science Foundation's Expeditions in Computing program to create revolutionary computational tools that will advance science on a broad array of fronts, from discovering new cancer treatments to designing safer aircraft. The researchers will combine Model Checking and Abstract Interpretation, two methods that have been successful in finding errors in computer circuitry and software, and extend them so they can provide insights into models of complex systems, whether electronic or biological.
In addition to Clarke, who is one of the coinventors of Model Checking, the research team includes project Deputy Director Amir Pnueli, a New York University computer scientist and a Turing Award winner for his work on systems verification. Among the other notables on the team are Patrick Cousot, an NYU computer scientist and coinventor of Abstract Interpretation, and James Glimm, a National Medal of Science winner who heads the Department of Applied Mathematics and Statistics at the State University of New York at Stony Brook.
Specifically, computer scientists, biomedical researchers and engineers from eight leading research institutions will use Model Checking and Abstract Interpretation to better understand what causes deadly pancreatic cancer and the common heart rhythm problem known as atrial fibrillation. At the same time, they will use the techniques to study the embedded computer systems that are increasingly critical to the safe operation of aircraft and automobiles.
"Biological and embedded computer systems may be on opposite ends of the research spectrum, but they pose similar challenges for creating and analyzing computational models of their behavior," said Clarke, the Carnegie Mellon FORE Systems University Professor of Computer Science and the 2007 winner of the Association for Computing Machinery's Turing Award. "Solutions to these problems at either end will enable new approaches to modeling across the spectrum that ultimately will improve health and safety. With this new initiative, I think we finally have achieved the critical mass of expertise and effort needed to crack these puzzles."
Model Checking and Abstract Interpretation are the result of more than 30 years of research. Model Checking is the most widely used technique for detecting and diagnosing errors in complex hardware and software designs. It considers every possible state of a hardware or software design and determines if it is consistent with the designer's specifications; it produces counterexamples when it uncovers inconsistencies. It is limited, however, by the size of the systems it can analyze.
Abstract Interpretation, by contrast, doesn't attempt to look at every possible state of a system, but to develop a simplified approximation of a system that preserves the particular properties that need to be assessed. This makes it possible to analyze very large, complex systems, such as the one million lines of code in the Airbus A380's primary flight control system, but with less precision than is possible with Model Checking.
In this new project, the researchers plan to take advantage of the strengths of both methods by tightly integrating the two into what they call MCAI 2.0.
One of the challenge problems driving this development involves modeling of pancreatic cancer, the fourth-leading cause of cancer deaths in the United States and Europe. Computer modeling is particularly important for discovering how this cancer develops and how it might be detected at an early, treatable stage because researchers have had trouble developing an animal model. Christopher Langmead, a Carnegie Mellon computer scientist, and James Faeder, a computational biologist at the University of Pittsburgh School of Medicine, will lead this effort, working with researchers at the Translational Genomics Research Institute.
"The death last year of our computer science colleague Randy Pausch, who had pancreatic cancer, made all of us at Carnegie Mellon appreciate the importance of improved models for this disease," Clarke said.
Atrial fibrillation, the most common form of heart rhythm disturbance, contributes to congestive heart disease and is responsible for 15 to 20 percent of strokes. Its incidence increases with age, so the aging demographics of America mean that this condition afflicting 2 to 3 million people today could be a problem for 10 million by 2050. A team led by Flavio Fenton, a biomedical researcher at Cornell University, and Radu Grosu, a computer scientist at SUNY at Stony Brook, will explore how modeling can enable physicians to predict the onset of atrial fibrillation.
A growing number of embedded systems are being integrated into cars — electronic stability control, anti-skid systems, hybrid powertrains, collision-avoidance systems — though the ability to develop models of how these systems interact with each other is severely limited. Rance Cleaveland, a computer scientist at the University of Maryland, and Bruce Krogh, a Carnegie Mellon electrical and computer engineer, will focus on distributed automotive control and electronic stability control as they lead the development of models that can help manufacturers integrate these systems into automobiles.
The aerospace industry has been a key driver of embedded software technology since the earliest weather-satellite launches of the 1960s, but it is now faced with exponential growth in the size and complexity of these systems in both spacecraft and commercial aircraft. With aircraft manufacturers seeking to better utilize microprocessors, NYU's Cousot and Gerard Holzmann, a computer scientist at NASA's Jet Propulsion Laboratory, will develop models that identify potential conflicts that can occur as microprocessors are shared between systems.
Research will be coordinated through a new Institute for Model Discovery and Exploration of Complex Systems, which will be headquartered in Carnegie Mellon's newly constructed Gates Center for Computer Science.
Clarke emphasized that Carnegie Mellon will funnel the bulk of its project money to support graduate students, rather than faculty salaries. In addition to the NSF grant, the School of Computer Science and the Ray and Stephanie Lane Center for Computational Biology at Carnegie Mellon are providing supplemental support for the project.