Combinatorial Mathematics May Help Pinpoint Software Bugs Quickly

January 9, 2008

Mathematicians and computer scientists from the National Institute of Standards and Technology and the University of Texas, Arlington are developing an open-source tool that would identify programming errors quickly through "combinatorial testing."

By evaluating software crashes in applications ranging from medical devices to Web browsers, the researchers obtained evidence that backs conventional wisdom: Most software failures result from simple events. In the case of Web browsers, for example, the majority of failures resulted from interactions between just two variables. In other applications, however, sometimes as many as six interacting variables were involved in failures.

The research team, therefore, designed an efficient method to test combinations of settings with up to six interacting variables at a time.

For example, in the case of a word-processing program that features ten text formats, certain combinations of settings (such as turning on superscript, subscript, and italics at the same time) might cause a software crash. Instead of trying all possible combinations of the ten effects together, which would require 1,024 tests, evaluating all possible combinations of any three effects requires merely 13 tests. That's because, by choosing the tests carefully, testers can evaluate 120 combinations of "triples" simultaneously.

This approach to finding software bugs may help to increase the reliability of e-commerce websites, which often contain many interacting variables, as well as industrial process controls, such as for robotic assembly lines of high-definition televisions, which contain many interacting software-controlled elements that regularly turn on and off.

The researchers have invited developers to take part in beta testing of the tool before its slated release later in 2008.

Source: National Institute of Standards and Technology, Dec. 13, 2007.