Investigations
Discuss This Article

Getting the Bugs Out

A Smarter Way to Test Software

On June 30, 1956, two planes collided over the Grand Canyon, killing 128 people. It was the worst civil air accident in America to date and it led to the creation of the Federal Aviation Administration. Airborne collisions are rare today because of the Traffic Alert and Collision Avoidance System (TCAS), hardware and software that act as electronic eyes to help pilots visualize air traffic nearby.

Like all software systems, TCAS is constantly being improved, and each new version must be tested. Software companies spend millions of dollars to develop their core applications--from collision avoidance systems to telephone communication services--before bringing them to market. Part of this money pays for testing to debug code.

Despite the costly testing, some features still won't work right in the real world. For example, air-collision detection software might be designed to sound an alarm when another plane approaches to within 1,000 feet. Testing might miss a particular case in which the software fails. Such bugs need to be eliminated before the software can be released. Yet how can a programmer be sure that the code is error-free, especially when lives hang in the balance?

Kathi Fisler, assistant professor of computer science, along with a research colleague at Brown University, is working to guarantee that critical software systems are free of such behavioral errors. They are developing computer-aided verification techniques that will complement current testing procedures and help programmers locate more design errors in the early stages of development.

The complexity of today's computing systems makes thorough testing almost impossible. "The number of possible test cases is vastly larger than the number of atoms in the universe. It's literally impossible to run them all in a human lifetime," says Fisler. "And, unfortunately, a successful test indicates only that no major bugs were uncovered. It doesn't mean that the design is error-free."

"The number of possible test cases is vastly larger than the number of atoms in the universe. It's literally impossible to run them all in a human lifetime."

The sheer size and complexity of modern systems pose the biggest obstacle to verification. To be feasible, a verification tool ideally should analyze only the fraction of code that pertains to a given requirement. Unfortunately, such code is typically scattered throughout an application, making it difficult to isolate.

The solution to this problem, Fisler believes, ultimately lies in creating different software architectures. Research has shown that feature-oriented software simplifies other key engineering problems, such as system evolution and maintenance; it also helps create families of related products that share similar sets of features, like telephony systems with different combinations of features, such as call waiting and caller ID.

Fisler is developing techniques that utilize feature orientation--both to make verification easier and to amortize high testing costs across designs in the same product line. "Society's reliance on software infrastructure makes its reliability increasingly important," she says. In other words, she who gets the most bugs out, wins--and makes life run more smoothly for all of us in the process.

--CC


Programmers write large programs as a series of smaller modules and create whole programs by combining modules. In Fig. 1, the circles represent different steps in the program. The shaded boxes represent modules, the X's denote combining them into a program. Assume this is an e-mail system and the red circles represent the code for the e-mail forwarding feature. "A verification tool must isolate the red circles to efficiently check the feature. The challenges are identifying the red circles, then verifying them alone while determining how their behavior affects the behavior of the whole program," says Kathi Fisler.
"If programmers create modules around individual features to begin with [as in Fig. 2], isolating the red circles becomes easier. We simply capture and then exploit the programmers's knowledge of which code implements which feature."

Related Links