|
Predictive Analysis: Catching the Near Misses Gul Agha
Computer science professor Gul Agha, whose Open Systems Laboratory developed the Actor model for developing and reasoning about distributed applications, continues to come up with novel ways to deal with all kinds of issues in parallel and distributed programs. They are often based on the Actor model. Actors are autonomous objects or software agents that move things from one computer to another while a program is running. (On the Internet, actors are known as softbots.) Software bugs cost the U.S. economy about $60 billion a year, according to a 2002 study conducted by the National Institute of Standards and Technologies. That's about 0.6 percent of the gross domestic product. The manufacturing and financial service industries are two major groups that suffer tremendously from buggy code. To put a dent in that figure, Agha is helping produce higher quality software by improved software testing. In a new research thrust, Agha is combining formal techniques and theory of concurrency to monitor systems and test programs. Often such programs are tested, and they seem to run correctly, but once they are deployed they eventually crash. "This is because it is difficult to test for all cases," Agha explained. "We could dramatically improve the robustness of such programs by catching 'near misses' in the testing process." Agha used the analogy of a pedestrian crossing an intersection of a busy street. The action of the pedestrian, the traffic light, and an oncoming truck is like the execution of a program. If the pedestrian gets hit by the truck, then we know there is something wrong with the program. Suppose, for example, that the traffic light is broken. The pedestrian crosses the street, and here comes the truck. Most of the time, the pedestrian will not get hit, and in usual testing, if the truck didn't hit the pedestrian, the program is considered to be working correctly. After testing a hundred runs, the pedestrian may have crossed the street a hundred times and never have been struck. But the program may not be as correct as it seems-the pedestrian may simply have been lucky. When a program is not trustworthy, there is no causal connection-no synchronization-between the motion of the truck and the pedestrian crossing the street. Each is unaware of the other. The fact that the pedestrian made it to the other side does not prove that the system is not violating any safety rules (in this case, the traffic light is malfunctioning). For the system to be correct, certain things have to happen in a certain sequence to guarantee safety: the walk light has to be on when the pedestrian crosses the street, the traffic light has to be green when the truck passes through the intersection, the pedestrian and truck obey the traffic laws. If all of this happens, then the program will execute correctly, every time. Something is wrong, however, if the system allows the pedestrian and truck to arrive at the same point at the same time. Maybe one time, during the hundred crossings, the truck missed the pedestrian by inches. The fact that near misses occur indicates that something could be awry, and traditional testing does not have the notion of a near miss. However, the more time elapsed between when the pedestrian starts to cross the street and when the truck approaches, the less probable it is that the pedestrian will be hit. What if you could detect these near misses and use that information to predict the probability of the pedestrian getting hit? Agha and graduate student Koushik Sen, in collaboration with Professor Grigore Rosu, have developed a method to find causality in a program and to detect near misses called Predictive Analysis. This method allows a very rapid look at hundreds of cases related to a particular run without having to rerun the program. "By tracking the causal structure of events in a program, you can use one run to extract a lot of information. This allows you to see alternative scenarios-some of them potentially disastrous-that might have occurred even though they haven't yet," said Agha. Written by Judy Tolliver, July 28, 2006
|
|