Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

Automated Combinatorial Testing for Software

Security testing

The tools distributed here are used extensively in testing for security vulnerabilities.  A short survey article and some examples:

Simos, D. E., Kuhn, R., Voyiatzis, A. G., & Kacker, R. (2016). Combinatorial Methods in Security Testing. IEEE Computer, 49(10), 80-83.

Introduces CT-based approaches for security testing and presents our case studies and experiences so far. The success of the presented research program motivates further intensive research on the field of combinatorial security testing. In particular, security testing for the Internet of Things (IoT) is an area where these approaches may prove particularly useful. IoT systems send and receive data from a large (often continually changing) set of interacting devices and the number of potential communicating pairs increases with the square of the number of devices. Combinatorial methods are ideally suited for the IoT environment, where testing can involve a very large number of nodes and combinations.

 

Bozic, J., Simos, D. E., & Wotawa, F. (2014, May). Attack pattern-based combinatorial testing. In Proceedings of the 9th international workshop on automation of software test (pp. 1-7). ACM.

We extend previous work in combining the attack pattern models with combinatorial testing in order to provide concrete test input, which is submitted to the system under test.  With combinatorial testing we capture different combinations of inputs and thus increasing the likelihood to find weaknesses in the implementation under test that can be exploited. Besides the foundations of our approach we further report on first experiments that indicate its practical use.

 

Wang, W., Lei, Y., Liu, D., Kung, D., Csallner, C., Zhang, D.,& Kuhn, R. (2011, June). A combinatorial approach to detecting buffer overflow vulnerabilities. In 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN)(pp. 269-278). IEEE.

Buffer overflow vulnerabilities are program defects that can cause a buffer to overflow at runtime. Many security attacks exploit buffer overflow vulnerabilities to compromise critical data structures. In this paper, we present a black-box testing approach to detecting buffer overflow vulnerabilities.  Our approach is motivated by a reflection on how buffer overflow vulnerabilities are exploited in practice.

 

Nelson, C., Kantor, P., Nakamura, B., Ricks, B., Whytlaw, R., Egan, D., ... & Young, M. (2015, April). Experimental designs for testing metal detectors at a large sports stadium. In 2015 IEEE International Symposium on Technologies for Homeland Security (HST)(pp. 1-7). IEEE.

This experiment was created to understand the walk-through performance at each setting in the outdoor environment; e.g., does a walk-through catch each of the pre-specified prohibited items, and is this consistent across machines on the same setting? Because of the number of factors to be considered (type of item, location, orientation, walk-through setting, etc.), designing the experiment required a sophisticated approach called Combinatorial Experimental Design. The experiment was part of two DHS-supported projects on best practices for stadium security.

 

Bozic, J., Garn, B., Kapsalis, I., Simos, D., Winkler, S., & Wotawa, F. (2015, August). Attack pattern-based combinatorial testing with constraints for web security testing. In 2015 IEEE International Conference on Software Quality, Reliability and Security (pp. 207-212). IEEE.

Security testing of web applications remains a major problem of software engineering. In order to reveal vulnerabilities, manual and automatic testing approaches use different strategies for detection of certain kinds of inputs that might lead to a security breach. In this paper we compared a state-of-the-art manual testing tool with an automated one that is based on model-based testing.

 

Kitsos, P., Simos, D. E., Torres-Jimenez, J., & Voyiatzis, A. G. (2015, November). Exciting FPGA cryptographic Trojans using combinatorial testing. In 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE)(pp. 69-76). IEEE.

In this paper, we explore the applicability of a prominent combinatorial strategy, namely combinatorial testing, for FPGA Trojan detection. We demonstrate that combinatorial testing provides the theoretical guarantees for exciting a Trojan of specific lengths by covering all input combinations. Our findings indicate that combinatorial testing constructs can improve the existing FPGA Trojan detection capabilities by reducing significantly the number of tests needed. Besides the foundations of our approach, we also report on first experiments that indicate its practical use.

 

Dalal, S. R., Jain, A., & Kantor, P. B. (2015, April). Creating configurations for testing radiation portal algorithms using factor covering combinatorial designs. In 2015 IEEE International Symposium on Technologies for Homeland Security (HST)(pp. 1-6). IEEE.

We present a systematic approach for testing the efficacy of different algorithms used in portals to identify Special Nuclear Materials (SNM) in presence of a number of other confounding factors including background radiation and naturally occurring radiation material (NORM). Algorithms are sensitive to several factors, and for realistic situations, the number of factors is large and exhaustive testing using full factorial designs is impractical. Our method, instead, extends factor covering combinatorial design to create a smaller number of configurations to cover all pairwise or 3-way factor combinations.

 

Simos, D. E., Kleine, K., Voyiatzis, A. G., Kuhn, R., & Kacker, R. (2016, August). Tls cipher suites recommendations: A combinatorial coverage measurement approach. In 2016 IEEE International Conference on Software Quality, Reliability and Security (QRS)(pp. 69-73). IEEE.

We present a coverage measurement for TLS cipher suites recommendations provided by various organizations. These cipher suites are measured and analyzed using a combinatorial approach, which was made feasible via developing the necessary input models. Besides shedding light on the coverage achieved by the proposed recommendations, we discuss implications towards aspects of test quality.

 

Bozic, J., Kleine, K., Simos, D. E., & Wotawa, F. (2017, March). Planning-based security testing of the ssl/tls protocol. In 2017 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)(pp. 347-355). IEEE.

In this paper a novel testing approach is presented, which adapts planning for security testing of cryptographic protocols.  The whole approach is implemented in one testing framework. Its purpose is to automatically test for known vulnerabilities in protocol implementations but to trigger other unintended behavior as well so eventually new security flaws can be identified.  Additionally, the planning specification can be extended further so new testing possibilities can be generated. New test cases can be generated dynamically according to changing conditions.

 

Garn, B., Simos, D. E., Duan, F., Lei, Y., Bozic, J., & Wotawa, F. (2019, April). Weighted Combinatorial Sequence Testing for the TLS Protocol. In 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)(pp. 46-51). IEEE.

In this paper, we apply the notion of weighted tway sequences to derive sequence test cases for testing implementations of the TLS protocol version 1.2. The used weights have been derived from an analysis of a security bug database of GnuTLS and we tested four implementations of the TLS protocol against them comparing their behavior. Our results indicate discrepancies in the behavior of different TLS implementations.

 

 

Created May 24, 2016, Updated October 07, 2019