Most of us probably don’t fully grasp how much of modern life (and personal privacy) relies on the stability, integrity and accuracy of software to fuel the nation’s economic engine, public services and health care. Every day we entrust our lives to software when we step aboard a high-tech aircraft or modern car. Now, a long-term research effort guided by two researchers at the National Institute of Standards and Technology with their collaborators has developed new tools to make this type of safety-critical software even safer.
The research team’s new creation can be added to the software developer’s toolkit to strengthen the safety tests that software companies conduct on the programs that help control vehicles, operate power plants and manage other critical, complex technology. While these tests are often costly and time-consuming, they reduce the likelihood that this complex code will malfunction because it received some unexpected combination of input data. This source of trouble can plague any sophisticated software package that must reliably monitor and respond to multiple streams of data flowing in from sensors and human operators at every moment, NIST said in a release.
With the research toolkit called Automated Combinatorial Testing for Software, or ACTS, software companies can make sure that there are no simultaneous input combinations that might inadvertently cause a dangerous error. To compare, think of a keyboard shortcut, such as pressing CTRL-ALT-DELETE to reset a system intentionally. The risk with safety-critical software is that combinations such as these could create unintentional consequences.
Until now, there was no way to be certain that all the significant combinations in very large systems had been tested which elevates risk. Now, with the help of advances made by the research team, even software that has thousands of input variables, each one of which can have a range of values, can be tested thoroughly, NIST explained.
NIST’s ACTS toolkit now includes an updated version of Combinatorial Coverage Measurement (CCM), a tool that should help improve safety as well as reduce software costs. The software industry often spends seven to 20 times as much money ensuring safety-critical software is reliable than it does on more conventional code, NIST estimated.
The peer-reviewed findings of the research team appear in two papers the team will presented April 23 at the 2019 IEEE International Conference on Software Testing, Verification and Validation in Xi’an, China. 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, according to NIST.
Because a single input variable can have a range of potential values—and a program can have many such variables—it is not feasible to test every plausible combination, so testers must rely on mathematical strategies to eliminate a large number of possibilities. By the mid-2000s, the NIST toolkit could check inputs in up to six-way combinations, eliminating many risks of generating errors.
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 approach: 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, NIST will make the algorithm available to any developer who requests it.
NIST encourages any company interested in expanding its software testing capability to contact it for further information.
Papers: R. Smith, D. Jarman, J. Bellows, R. Kuhn, R. Kacker and D. Simos. Measuring Combinatorial Coverage at Adobe; and R. Smith, D. Jarman, R. Kuhn, R. Kacker, D. Simos, L. Kampel, M. Leithner and G. Gosney. Applying Combinatorial Testing to Large-scale Data Processing at Adobe. Both to be presented at IEEE International Conference on Software Testing, Verification and Validation, April 23, 2019.