'Combinatorial' approach squashes software bugs faster, cheaper

Dec 12, 2007

A team of computer scientists and mathematicians from the National Institute of Standards and Technology and the University of Texas, Arlington is developing an open-source tool that catches programming errors by using an emerging approach called “combinatorial testing.” The NIST-Texas tool, described at a recent conference,* could save software developers significant time and money when it is released next year.

Studying software crashes in a variety of applications from medical devices to Web browsers, NIST researchers obtained hard evidence to support long-held conventional wisdom: most software failures result from simple events rather than complex ones.** Even for Web browsers containing hundreds of different variables, most failures were caused by interactions between just two variables. Nonetheless, in the applications that the researchers studied, additional failures could result from interactions of up to six variables.

Based on that insight, the NIST-Texas team went beyond the popular practice of “pairwise testing,” or exploring interactions between only two variables at a time, and designed a method for efficiently testing different combinations of settings in up to at least six interacting variables at a time. Their technique resembles combinatorial chemistry in which scientists screen multiple chemical compounds simultaneously rather than one at a time.

For example, imagine a word-processing program that features 10 different text formats. Certain combinations of settings (such as turning on superscript, subscript and italics at the same time) could cause the software to crash. Trying all possible combinations of the 10 effects together would require 1,024 tests. However, testing all possible combinations of any three effects requires just 13 different tests, thanks in part to the fact that if the tests are selected judiciously the 10 different variables allow you to explore 120 combinations of “triples” simultaneously.

The new tool generates tests for exploring interactions among the settings of multiple variables in a given program. Compared to most earlier combinatorial testing software, which has typically focused on testing interactions between just two variables, the tool excels at quickly generating efficient tests for 6-way interactions or more.

The researchers plan to release the tool early next year as open-source code. They currently are inviting developers to participate in beta testing of the tool before release. This new approach for finding bugs to squash may be particularly useful for increasing the reliability of e-commerce Web sites, 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.

References:
* Y. Lei, R. Kacker, D. R. Kuhn, V. Okun and J. Lawrence, IPOG: A general strategy for t-way software testing. IEEE International Conference on Engineering of Computer-Based Systems March 26-29, 2007, pp 549-556, Tucson AZ, USA.

** D.R. Kuhn, D.R. Wallace and A.J. Gallo, Jr. Software fault interactions and implications for software testing. IEEE Trans. on Software Engineering, June 2004 (Vol. 30, No. 6) pp. 418-421.

Source: National Institute of Standards and Technology

Explore further: Encryption made easier: Just talk like a parent

Related Stories

The growing influence of statisticians

Jun 04, 2015

With more information than ever at our fingertips, statisticians are vital to innumerable fields and industries. Welcome to the world of the datarati, where humans and machines team up to crunch the numbers.

Shedding light on untapped information in photons

May 25, 2015

Conventional optical imaging systems today largely limit themselves to the measurement of light intensity, providing two-dimensional renderings of three-dimensional scenes and ignoring significant amounts ...

Astronomers breathe new life into venerable instrument

Feb 06, 2015

How do astronomers determine the shapes of objects that are too far away to photograph? One method is by using spectropolarimetry, an observational technique that measures the way light waves align after ...

As Austin grows, so does its traffic woes

Jan 16, 2015

Ask any Austinite what they enjoy least about the city, and many will mention the escalating traffic issues. According to Forbes, Austin is one of the fastest growing cities in the U.S., and without a tran ...

Recommended for you

Solar Impulse 2 pilot becomes aviation legend

13 hours ago

At 62 years of age, Swiss Solar Impulse 2 pilot Andre Borschberg has made aviation history with a record breaking solo flight across the Pacific that he has called "an interior journey".

Facegloria: Facebook for Brazil's Evangelicals

13 hours ago

Fluffy clouds waft across a blue sky as you log in and while you chat with friends, Gospel music rings out: welcome to Facegloria, the social network for Brazilian Evangelicals.

Mexico City proposes regulations for Uber

13 hours ago

Mexico City is proposing regulations that would allow Uber and other smartphone-based ride-sharing apps to operate, while requiring drivers and cars to be registered, the city's Office of Legal and Legislative Studies said ...

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.