'Combinatorial' approach squashes software bugs faster, cheaper

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

Related stories:

Novel living system recreates predator-prey interaction
The hunter-versus-hunted phenomenon exemplified by a pack of lionesses chasing down a lonely gazelle has been recreated in a Petri dish with lowly bacteria.
First glimpse of a key DNA repair protein at work
Repairing breaks in the two strands of the DNA double helix is critical for avoiding cancer. In humans and other organisms, a molecular machine called the MRN complex is responsible for finding and signaling double-strand breaks (DSBs), then launching the error-free method of DNA repair called homologous recombination.
New formula predicts how people will migrate in coming decades
Nearly 200 million people now live outside their country of birth. But the patterns of migration that got them there have proven difficult to project. Now scientists at Rockefeller University, with assistance from the United Nations, have developed a predictive model of worldwide population shifts that they say will provide better estimates of migration across international boundaries. Because countries use population projections to estimate local needs for jobs, schools, housing and health care, a more precise formula to describe how people move could lead to better use of resources and improved economic conditions.
Biophysicists create new model for protein-cholesterol interactions in brain and muscle tissue
Biophysicists at the University of Pennsylvania have used 3,200 computer processors and long-established data on cholesterol's role in the function of proteins to clarify the mysterious interaction between cholesterol and neurotransmitter receptors. The results provide a new model of behavior for the nicotinic acetylcholine receptor, a well studied protein involved in inflammation, Alzheimer's disease, Parkinson's disease, schizophrenia, epilepsy, the effect of general anesthetics and addiction to alcohol, nicotine and cocaine.
Europe all set for lunar mission Chandrayaan-1
Europe is participating in a big way in the Indian Space Agency’s Chandrayaan-1 mission to the Moon, by contributing three instruments. All these instruments have now been delivered, tested and integrated with the spacecraft.
Real-life robots obey Asimov’s laws
(PhysOrg.com) -- European researchers have developed technology enabling robots to obey Asimov’s golden rules of robotics: to do no harm to humans and to obey them.
The ATLAS Pixel Detector
With the Large Hadron Collider start-up only weeks away, SLAC researchers working on the LHC are feeling the excitement. SLAC has been involved in designing and building the ATLAS (A Toroidal LHC ApparatuS) detector since mid-2006, when the lab officially joined the collaboration.
Stanford's 'autonomous' helicopters teach themselves to fly
Stanford computer scientists have developed an artificial intelligence system that enables robotic helicopters to teach themselves to fly difficult stunts by watching other helicopters perform the same maneuvers. The result is an autonomous helicopter than can perform a complete airshow of complex tricks on its own.

News discussion:

Technology news