Raghu Kacker Named Fellow of the Washington Academy of Sciences

Dr. Raghu Kacker was chosen as a Fellow in recognition of outstanding contributions in enabling the field of combinatorial testing to become a mainstream tool in measurement science and software engineering.

In 1997, the Mars Pathfinder began experiencing system resets at seemingly unpredictable times soon after it landed and began collecting data. Fortunately, engineers were able to deduce and correct the problem, which occurred only when (1) a particular type of data was being collected, and (2) intermediate priority tasks exceeded a certain load, resulting in a blocking condition that eventually triggered a reset. Situations of this type are known as interaction faults. Many real-time failures of software-based systems have been traced to such faults. These are often insidious in that they may remain hidden until the unfortunate combination is encountered during system operation.

Combinatorial testing (CT) is a methodology for detecting interaction faults. CT began as pairwise (2-way) testing in which all pairs of the test values for all pairs of test factors are checked. Thus, pairwise testing can detect faults involving single factors or interactions between two factors. CT is based on an empirical observation, referred to as the interaction rule, that while the behavior of a software system may be affected by many factors, only a few are involved in any given failure. NIST investigations of failures in actual systems have shown that while most faults involved a single factor or interaction between two factors, some faults involved three or more factors. (A fault involving more than six factors has not yet been reported.) Thus, pairwise testing is useful, but it may not be adequate for detecting interaction faults involving more than two test factors. And, extending pairwise (2-way) CT to higher strength t-way CT for t > 2 was thought to be computationally infeasible. As a result, CT had not been widely embraced by the software engineering community.

Some 17 years ago, Dr. Kacker and colleagues proposed that NIST take the lead in developing methods and tools based on combinatorial mathematics to test software-based systems for performance, security, and trust; and to promote their application in industry. NIST has helped make CT practical by developing research tools and techniques for efficiently generating combinatorial test suites. CT has since gained significant interest from the international software testing community. Many successful results from the use of CT in aerospace, automotive, and financial service industries, as well as defense, security, and electronic medical systems have since been reported.