NIST tool boosts chances of finding dangerous software flaws

After more than 20 years of steady improvement, the US National Institute of Standards and Technology (NIST) thinks it has reached an important milestone with something called Combinatorial Coverage Measurement (CCM).

Part of a research toolkit called Automated Combinatorial Testing for Software (ACTS), CCM is an algorithmic approach used to test software for interactions between input variables that might cause unexpected failures.

It sounds like a technical mouthful, but this is good news for software, especially when it’s inside complex systems such as aircraft, cars and power plants where these sorts of problems could be life-threatening.

Typically, this will be software taking inputs from arrays of sensors that generate unexpected conflicts the software can’t resolve, for instance between temperature, pressure or altitude.

Designers try to counteract these problems by modelling as many interactions as they can before the software is used in the real world, which is where ACTS and CCM come in.

But there’s always been a problem – modelling enough interactions from enough variables to spot all the possible combinations that might lead to an issue.

This has been improving since the late 1990s when the idea got off the ground, most recently during a revision to the ACTS toolkit in 2015.

Now, in collaboration with University of Texas, Austria’s SBA Research, and Adobe (one of several big companies using the toolkit), NIST thinks that the 2019 revision of CCM has made some kind of leap forward.

NIST mathematician Raghu Kacker said of the difficulties of testing complex software:

Before we revised CCM, it was difficult to test software that handled thousands of variables thoroughly. 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.

With the help of a new algorithm developed by SBA, NIST’s tool had gone from being able to model a few hundred variables to up to 2,000 from five-way combinations of inputs.

Although not an official part of the tool, developers could request the algorithm. NIST computer scientist Richard Kuhn said:

The collaboration has shown that we can handle larger classes of problems now. We can apply this method to more applications and systems that previously were too hard to handle.

Not far from the surface of this development is the problem of cost – how much time and effort should developers spend removing bugs from their software?

NIST’s hope must be that anything that can remove more bugs for the same effort is going to have a positive effect on security and reliability.

Unfortunately, as helpful as CCM might be, its effectiveness must now be measured against the rising complexity of software systems that are acquiring once unimagined capabilities, such as automation.

There is an expanding range of commercial products that want to help solve this problem. The investment NIST is making in ACTS and CCM suggests there is still plenty of room for a toolset that everyone can use.