Combinatorial Testing

Security testing

The tools distributed here are used extensively in testing for security vulnerabilities.  
Survey article:

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.

------------
Examples:

Marksteiner, S., Marko, N., Smulders, A., Karagiannis, S., Stahl, F., Hamazaryan, H., Schlick, R., Kraxberger, S. and Vasenev, A., 2021. A Process to Facilitate Automated Automotive Cybersecurity Testing. arXiv preprint arXiv:2101.10048.

This paper outlined a process for testing the cyber­ security of (particularly automotive) systems to fill the gap between existing standards for automotive security engineering and their hands-on, actual-system testing. The process provides a comprehensive, automatable ap­ proach for system testing based on ISO/SAE DIS 21343.

Tran-Jørgensen, P. W., Kulik, T., Boudjadar, J., & Larsen, P. G. (2019, October). Security analysis of cloud-connected industrial control systems using combinatorial testing. In Proceedings of the 17th ACM-IEEE International Conference on Formal Methods and Models for System Design (pp. 1-11).

When exhaustive verification accounts for this complexity the state space being sought grows drastically as the system model evolves and more details are considered. Eventually this may lead to state space explosion, which makes exhaustive verification infeasible. To address this, we use VDM-SL’s combinatorial testing feature to generate security attacks that are executed against the model to verify whether the system has the desired security properties.

Simos, D. E., Zivanovic, J., & Leithner, M. (2019, May). Automated combinatorial testing for detecting SQL vulnerabilities in web applications. In 2019 IEEE/ACM 14th International Workshop on Automation of Software Test (AST) (pp. 55-61). IEEE.

In this paper, we present a combinatorial testing methodology for testing web applications in regards to SQL injection vulnerabilities. We describe three attack grammars that were developed and used to generate concrete attack vectors. Furthermore, we present and evaluate two different oracles used to observe the application’s behavior when subjected to such attack vectors. We also present a prototype tool called SQLINJECTOR capable of automated SQL injection vulnerability testing for web applications. The developed methodology can be applied to any web application that uses server side scripting and HTML for handling user input and has a SQL database backend.

Elks, D. C., Deloglos, C., Jayakumar, A., Tantawy, D. A., Hite, R., & Gautham, S. (2019). REALIZATION OF A AUTOMATED T-WAY COMBINATORIAL TESTING APPROACH FOR A SOFTWARE BASED EMBEDDED DIGITAL DEVICE (No. INL/EXT-19-54096-Rev000). Idaho National Lab.(INL), Idaho Falls, ID (United States).

This report describes the detailed workflow for conducting testing and the testbed to support Bounded Exhaustive Testing with respect to Combinatorial Test (CT) methods. The report primarily describes the description of the process workflow, testbed architecture, tools, resources, and computing needed to conduct an automated testing process. This information will be used to fully realize the testbed and conduct the experimental study – which is to demonstrate the efficacy of digital qualification via Bounded Exhaustive Testing with respect to Common Cause Failure assessment.

Ma, L., Zhang, F., Xue, M., Li, B., Liu, Y., Zhao, J., & Wang, Y. (2018). Combinatorial testing for deep learning systems. arXiv preprint arXiv:1806.07723.

Adopting testing techniques could help to evaluate the robustness of a DL system and therefore detect vulnerabilities at an early stage. The main challenge of testing such systems is that its runtime state space is too large: if we view each neuron as a runtime state for DL, then a DL system often contains massive states, rendering testing each state almost impossible. For traditional software, combinatorial testing (CT) is an effective testing technique to reduce the testing space while obtaining relatively high defect detection abilities. In this paper, we perform an exploratory study of CT on DL systems. We adapt the concept in CT and propose a set of coverage criteria for DL systems, as well as a CT coverage guided test generation technique. Our evaluation demonstrates that CT provides a promising avenue for testing DL systems.

Ratliff, Z. B. (2018). Black-box Testing Mobile Applications Using Sequence Covering Arrays.  Texas A&M University. 

This research examines the effectiveness of using sequence covering arrays to discover software bugs in mobile phone applications. Analysis of the distribution of t-way interactions between events in event sequence bugs provides insight into the practicality and usefulness of this combinatorial testing method. From a developer’s perspective, these methods can contribute to finding this particular class of bugs early in the software development process, saving the developers time and money without sacrificing effectiveness. However, an attacker may also leverage these techniques to discover previously undetected bugs as a means to exploit the system. This method can be particularly useful for attackers in that it is often simple to determine events in interactive software, even in black-box environments where internal knowledge about the source code is absent. Mobile applications running on popular operating systems such as Android and iOS are generally very interactive and therefore susceptible to these types of bugs. This project involved analyzing hundreds of software vulnerabilities in Android software, developing a new research tool for measuring sequence coverage in existing test suites, and using these combinatorial methods on various Android mobile applications. 

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.