Combinatorial Methods in Software Testing

Combinatorial methods have attracted attention as a means of providing strong assurance at reduced cost. Combinatorial testing takes advantage of the interaction rule, which is based on analysis of thousands of software failures. The rule states that most failures are induced by single factor faults or by the joint combinatorial effect (interaction) of two factors, with progressively fewer failures induced by interactions between three or more factors. Therefore if all faults in a system can be induced by a combination of t or fewer parameters, then testing all t-way combinations of parameter values is pseudo-exhaustive and provides a high rate of fault detection. The talk explains background, method, and tools available for combinatorial testing. Brief reviews of several case studies will also be included, to illustrate the methods and results that can be obtained. New work on applications to autonomous systems will be introduced as well, including an approach to using combinatorial methods for explainable AI.

Richard Kuhn is a computer scientist in the Computer Security Division at NIST, and is a Fellow of the Institute of Electrical and Electronics Engineers (IEEE). He co-developed the role based access control (RBAC) model that is the dominant form of access control today. His current research focuses on combinatorial methods for assured autonomy. He has authored three books and more than 200 conference or journal publications on cybersecurity, software failure, and software verification and testing. He received an MS in computer science from the University of Maryland College Park and an MBA (finance) from William & Mary. Before joining NIST, he worked as a software developer with NCR Corporation and the Johns Hopkins University Applied Physics Laboratory.