Combinatorial Testing

Combinatorial Methods in Cybersecurity Testing

Combinatorial methods improve security assurance in two ways:

• Reducing vulnerabilities - Multiple studies show that about two-thirds of security vulnerabilities result from ordinary coding errors that can be exploited (for example, lack of input validation).  By identifying errors more efficiently, combinatorial testing can reduce vulnerabilities as well. 
• Specialized security testing - We have been able to achieve huge improvements in fault detection for cryptographic software, hardware Trojan horse and malware, web server security, access control systems, and others.  

Below are some of the recent projects and research areas we're working on now. 

• Cryptographic software - Detected flaws in cryptographic software code, reducing the test set size by 700X as compared with exhaustive testing, while retaining the same fault-detection capability.   Mouha, N., Raunak, M.S., Kuhn, D.R. and Kacker, R., 2018. Finding bugs in cryptographic hash function  implementations. IEEE Trans Reliability, 67(3), pp.870-884.
• Web security - SBA Research demonstrated automated Web penetration testing using ACTS and combinatorial methods, detecting dozens of vulnerabilities in an industrial web application. B. Garn et al., “On the Applicability of Combinatorial Testing to Web Application Security Testing: A Case Study,” Proc. Workshop Joining AcadeMiA and Industry Contributions to Test Automation and Model-Based Testing (JAMAICA 14), 2014, pp. 16–21.
• System call vulnerabilities -  Automated detection of system call parameter errors.  B. Garn and D.E. Simos, “Eris: A Tool for Combinatorial Testing of the Linux System Call Interface,” Proc. IEEE 7th Int’l Conf. Software Testing, Verification, and Validation Workshops (ICSTW 14), 2014, pp. 58–67.
• Access control policy testing - tools to specify security policies, then automatically generate tests for conformance to the policies. Full tests are generated, with both input values and expected results, not just test data. More details here: Access Control Policy Test (ACPT) tool.
• Buffer overflow detection - our research, and others, shows that a small number of parameters are involved in software failures. For buffer overflows, more than 90% of vulnerabilities appear to be caused by a single parameter, and the rest by two or three parameters interacting (based on review of more than 3,000 reports in the National Vulnerability Database).
• Network security - we have demonstrated the effectiveness of combinatorial methods with a network simulator to detect configurations that produce deadlock, useful for defending a network against attacks that attempt to force the network into a deadlock configuration that results in denial of service.

If you'd like to find out more on any of these topics, please email Rick Kuhn: kuhn@nist.gov. 

People

Rick Kuhn - NIST
Raghu Kacker - NIST
Dimitris Simos - SBA Research
Bernhard Garn - SBA Research
Mohammad Raunak - Loyola University Maryland
Vincent Hu - NIST
Nicky Mouha - NIST