'Combinatorial' approach squashes software bugs faster, cheaper

December 12, 2007

A team of computer scientists and mathematicians from the National Institute of Standards and Technology (NIST) 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.
* 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.

National Institute of Standards and Technology (NIST)

Related Software Articles from Brightsurf:

Novel software assesses phonologial awareness
Understanding sounds in language is a critical building block for child literacy, yet this skill is often overlooked.

Software of autonomous driving systems
Researchers at TU Graz and AVL focus on software systems of autonomous driving systems.

New software supports decision-making for breeding
Researchers at the University of Göttingen have developed an innovative software program for the simulation of breeding programmes.

Software updates slowing you down?
We've all shared the frustration -- software updates that are intended to make our applications run faster inadvertently end up doing just the opposite.

Where is George? Ask this software to look at the crowd
Idtracker.ai is a mix of conventional algorithms and artificial intelligence developed at the Champalimaud Centre for the Unknown.

Research finds serious problems with forensic software
New research finds significant flaws in recently released forensic software designed to assess the age of individuals based on their skeletal remains.

Beta of Neurodata Without Borders software now available
Neuroscientists can now explore a beta version of the new Neurodata Without Borders: Neurophysiology (NWB:N 2.0) software and offer input to developers before it is fully released next year.

New software speeds origami structure designs
Researchers at Georgia Institute of Technology have developed a new computer-aided approach that streamlines the design process for origami-based structures, making it easier for engineers and scientists to conceptualize new ideas graphically while simultaneously generating the underlying mathematical data needed to build the structure in the real world.

International competition benchmarks metagenomics software
Communities of bacteria live everywhere: inside our bodies, on our bodies and all around us.

Preventing software from causing injury
Workplace injuries don't just come from lifting heavy things or falling off a ladder.

Read More: Software News and Software Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.