Enabling more comprehensive tests on high-risk software

The research includes collaborators from the University of Texas at Arlington, Adobe Systems Inc. and Austria’s SBA Research.

NIST mathematician Raghu Kacker said that CCM represents a substantial improvement to the ACTS toolkit since its last major addition in 2015.

“Before we revised CCM, it was difficult to test software that handled thousands of variables thoroughly,” Kacker said. “That limitation is a problem for complex modern software of the sort that is used in passenger airliners and nuclear power plants, because it’s not just highly configurable, it’s also life critical. People’s lives and health are depending on it.”

Software developers have contended with bugs that stem from unexpected input combinations for decades, so NIST started looking at the causes of software failures in the 1990s to help the industry. It turned out that most failures involved a single factor or a combination of two input variables—a medical device’s temperature and pressure, for example—causing a system reset at the wrong moment. Some involved up to six input variables.

Because a single input variable can have a range of potential values and a program can have many such variables, it can be a practical impossibility to test every conceivable combination, so testers rely on mathematical strategy to eliminate large swaths of possibilities. By the mid-2000s, the NIST toolkit could check inputs in up to six-way combinations, eliminating many risks of error.

“Our tools caught on, but in the end, you still ask yourself how well you have done, how thorough your testing was,” said NIST computer scientist Richard Kuhn, who worked with Kacker on the project. “We updated CCM so it could answer those questions.”

NIST’s own tools were able to handle software that had a few hundred input variables, but SBA Research developed another new tool that can examine software that has up to 2,000, generating a test suite for up to five-way combinations of input variables. The two tools can be used in a complementary fashion: While the NIST software can measure the coverage of input combinations, the SBA algorithm can extend coverage to thousands of variables.

Recently, Adobe Systems Inc. contacted NIST and requested help with five-way testing of one of its software packages. NIST provided the company with the CCM and SBA-developed algorithms, which together allowed Adobe to run reliability tests on its code that were demonstrably both successful and thorough.

While the SBA Research algorithm is not an official part of the ACTS test suite, the team has plans to include it in the future. In the meantime, Kuhn said that NIST will make the algorithm available to any developer who requests it.

“The collaboration has shown that we can handle larger classes of problems now,” Kuhn said. “We can apply this method to more applications and systems that previously were too hard to handle. We’d invite any company that is interested in expanding its software to contact us, and we’ll share any information they might need.”