Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

Automated Combinatorial Testing for Software

Industrial Case Studies - Combinatorial and Pairwise Testing

Combinatorial testing is an extension of the established field of statistical Design of Experiments (DoE), used by commercial firms with demonstrated success. Combinatorial testing is being applied successfully in nearly every industry, and is especially valuable for assurance of high-risk software with safety or security concerns.

Combinatorial testing is effectively exhaustive, or pseudo-exhaustive, in that it can be as effective as fully exhaustive testing, while reducing test set size by 20X to more than 100X.

Application

 

Reference

Notes/Abstract

Industrial controls, operating system - various companies  

Li, X., Gao, R., Wong, W.E., Yang, C. and Li, D.,  Applying combinatorial testing in industrial settings. In 2016 IEEE Intl Conf on Software Quality, Reliability and Security (QRS) (pp. 53-60).

From January 2016 to February 2016, authors tested three real-life software systems using CT, and compared the results to errors that had been discovered using conventional methods, finding roughly 3X as many bugs in one-fourth of the time, for a 12X increase in test efficiency. 

Loyola Univ, NIST -

Cryptography - multiple companies

 

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.

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. 

Lockheed Martin -

Aerospace

  J. Hagar, D.R. Kuhn, R.N. Kacker, Introducing Combinatorial Testing to a Large System-Software Organization, IEEE Computer, 48(4), pp.64-72. CT applied to 8 Lockheed Martin pilot projects in aerospace software. Results: “Our initial estimate is that this method supported by the technology can save up to 20% of test planning/design costs if done early on a program while increasing test coverage by 20% to 50%."

Siemens -

Industrial controls

 

Ozcan, M., 2017, March. Applications of Practical Combinatorial Testing Methods at Siemens Industry Inc., Building Technologies Division. In 2017 IEEE Intl Conf on Software Testing, Verification and Validation Workshops (ICSTW) (pp. 208-215). IEEE.

Applied combinatorial testing to industrial control systems, using mixed-strength covering arrays, “resulting in requiring fewer tests for higher strength coverage”. 

Adobe - 

Data analytics

 

  Smith, Riley, et al., "Measuring Combinatorial Coverage at Adobe", 2019 IEEE Intl Conf on Software Testing, Verification and Validation Workshops (ICSTW) (pp. 208-215).  "In this paper, we therefore report the practical application of combinatorial coverage measurements to evaluate the effectiveness of the validation framework for the Adobe Analytics reporting engine. The results of this evaluation show that combinatorial coverage measurements are an effective way to supplement existing validation for several purposes. In addition, we report details of the approach used to parse moderately nested data for use with the combinatorial coverage measurement tools."

Adobe - 

Data analytics

 

Smith, Riley, et al., "Applying Combinatorial Testing to Large-scale Data Processing at Adobe", 2019 IEEE Intl Conf on Software Testing, Verification and Validation Workshops (ICSTW) (pp. 208-215). 

"In this paper, we report the practical application of combinatorial testing to the data collection, compression and processing components of the Adobe analytics product. Consequently, the effectiveness of combinatorial testing for this application is measured in terms of new defects found rather than detecting known defects from previous versions. The results of the application show that combinatorial testing is an effective way to improve validation for these components of Adobe Analytics."

US Marine Corps - computer security penetration testing  

T. McLean, Cyber Penetration Testing and Statistical Analysis in DT&E  Dataworks 2018, Defense and Aerospace Test and Analysis Wkshp

"CYBERSTAT is applying Scientific Test and Analysis Techniques (STAT) to offensive cyber penetration testing tools.  By applying STAT to the tool, the tool’s scope is expanded beyond “one at a time” uses as combinations of options are explored with a combinatorial test. "
US Marine Corps - protocol testing   T. McLean, Combinatorial Testing Applied to Link 16 Standards Conformance Testing, Dataworks 2017, Defense and Aerospace Test and Analysis Wkshp

The project successfully implemented an unbiased and statistically based test methodology for Link 16 standards conformance that can ensure repeatability with a quantifiable increase in test space coverage. 

Hexawise - lessons learned, various projects  
   
J. Hunter, Adopting Optimized Software Test Design Methods at Scale, Dataworks 2017, Defense and Aerospace Test and Analysis Wkshp

Using Combinatorial Test Design methods to select software test scenarios has repeatedly delivered large efficiency and thoroughness gains – which begs the questions: 

• Why are these proven methods not used everywhere?• Why do some efforts to promote adoption of new approaches stagnate?• What steps can leaders take to introduce successfully introduce and spread new test design methods?

US Air Force - autonomous systems   D. Ahner, Testing Autonomous Systems, Defense and Aerospace Test and Analysis Workshop, 2018 Autonomous systems pose new challenges in conducting test and evaluation that assures adequate performance, safety, and cybersecurity outcomes. We propose an autonomous systems architecture concept and map the elements of a decision theoretic view of a generic decision problem to the components of this architecture. These models offer a foundation for developing a decision-based, common framework for autonomous systems. We also identify some of the various challenges faced by the Department of Defense (DoD) test and evaluation community in assuring the behavior of autonomous systems as well as test and evaluation requirements, processes, and methods needed to address these challenges.
IBM - autonomous vehicles  

Masuda, S., Nakamura, H. and Kajitani, K., 2018. Rule-based searching for collision test cases of autonomous vehicles simulation. IET Intelligent Transport Systems, 12(9), pp.1088-1095.

Abstract.  A combination of parameters is called a test case; hence, the challenge is to search collision test cases from the extremely large number of combinations. A rule-based method is the main focus because an explicit method of searching test cases is required in certain industries in the real world. In this study, a method of rule-based searching for collision test cases of autonomous vehicles simulations is proposed. Simulation models that have rules between an AD car and other cars are defined. Experiments on AD simulations involving the simulation models of a three-lane highway and a signalised intersection were conducted. The results indicate the efficiency of the method.
NASA JPL/Caltech - autonomous spacecraft  

Smith, B., Feather, M. and Huntsberger, T., A Hybrid Method of Assurance Cases and Testing for Improved Confidence in Autonomous Space Systems. In 2018 AIAA Information Systems-AIAA Infotech@ Aerospace(p. 1981).

Abstract. We are investigating a new test development method that aims to maximize the confidence to be achieved by combining Assurance Cases with High Throughput Testing (HTT). Assurance Cases, developed for safety-critical systems, are a rigorous argument that the system satisfies a property (e.g., the Mars rover will not tip over during a traverse). They integrate testing, analysis, and environmental and operational assumptions, from which the set of conditions that testing must cover is determined. In our method, information from the Assurance Case is used to determine the test coverage needed, and then input to HTT to generate the minimal test suites needed to provide that coverage.

SBA Research - computer security penetration testing  

Garn, B., Kapsalis, I., Simos, D.E. and Winkler, S., On the applicability of combinatorial testing to web application security testing: a case study. Proc 2014 Wkshp Joining AcadeMiA and Industry Contributions to Test Automation and Model-Based Testing. ACM.

This paper reports on a case study done for evaluating and revisiting a recently introduced combinatorial testing methodology used for web application security purposes. It further reports on undertaken practical experiments thus strengthening the applicability of combinatorial testing to web application security testing.

Video games - Workinman Games  

Sagi, Bhargava Rohit. "Experimental Design in Game Testing." Rochester Institute of Technology (2016).

Combinatorial testing is a method of experimental design that is used to generate test cases and is primarily used for commercial software testing. In addition to the discussion of the implementation of combinatorial testing techniques in video game testing, we present a method for finding combinations resulting in video game bugs.

Jaguar Land Rover - 

Automotive

 

Dhadyalla, Gunwant, Neelu Kumari, and Timothy Snell. "Combinatorial testing for an automotive hybrid electric vehicle control system: a case study." 2014 IEEE Seventh International Conference on Software Testing, Verification and Validation Workshops. IEEE, 2014.

"Embedded electrical systems for passenger vehicles are highly complex distributed systems with varying system boundaries. The surge towards further electrification of vehicles demands the deployment of high voltage systems that provide propulsion through an electric motor as part of a hybrid electric or pure electric drivetrain. This demands additional care and robust deployment to ensure the safety of the end user and the environment around them. Exhaustive testing is not feasible for large systems and the use of formal approaches can be restrictive. In the presented work a combinatorial test approach is applied to a real Hybrid Electric Vehicle control system as part of a hardware-in-the-loop test system."
SBA Research - web application penetration testing  

Bozic, J., Garn, B., Kapsalis, I., Simos, D., Winkler, S. and Wotawa, F., 2015, August. Attack pattern-based combinatorial testing with constraints for web security testing. 2015 IEEE Intl Conf Software Quality, Reliability and Security 

The evaluated results indicate that both techniques succeed in detecting security leaks in web applications with different results, depending on the background logic of the testing approach. Last but not least, we claim that attack pattern-based combinatorial testing with constraints can be an alternative method for web application security testing, especially when we compare our method to other test generation techniques like fuzz testing.

Rockwell Collins -

Avionics

 

R. Bartholomew, An Industry Proof-of-Concept Demonstration of Automated Combinatorial Test,25th Annual IEEE Software Technology Conf., April 8-10, 2013, Salt Lake City, Utah.

“Industry proof-of-concept demonstration that used this approach to automate parts of the unit and integration testing of a 196 KSLOC avionics system. The goal was to see if it might cost-effectively reduce rework by reducing the number of software defects escaping into system test – if it was adequately accurate, rigorous, thorough, scalable, mature, easy to learn, easy to use, etc. Overcoming scalability issues required moderate effort, but in general it was effective – e.g., generating 47,040 test cases (input vectors, expected outputs) in 75 seconds, executing and analyzing them in 2.6 hours. It subsequently detected all seeded defects, and achieved nearly 100% structural coverage.”

Bosch AG - automotive  

Dominka S, Mandl M, Dübner M, Ertl D. Using combinatorial testing for distributed automotive features: Applying combinatorial testing for automated feature-interaction-testing. 2018 IEEE 8th Ann. Computing and Communication Wkshp and Conf (CCWC) Jan 8 (pp. 490-495)

Abstract—Modern passenger cars have a comprehensive embedded distributed system with a huge number of bus devices interlinked in several communication networks. The number of (distributed) features and hence the risk of undesired feature interaction within this distributed system rises significantly. Such distributed automotive features pose a huge challenge in terms of efficient testing. Bringing together Combinatorial Testing with Automated Feature-Interaction Testing reduces the testing effort for such features significantly.

Avaya Corp. - 

Telecommunications

 

Sherif, Anwar. "Combinatorial testing: Implementations in solutions testing." 2016 IEEE Ninth International Conference on Software Testing, Verification and Validation Workshops (ICSTW). IEEE, 2016.

"This paper focuses the technical challenges and how they were addressed in implementing CT for solutions testing. "
Malardalen Univ & Bombardier Transportation AB - safety-critical industrial controls  

Ericsson S, Enoiu E. Combinatorial Modeling and Test Case Generation for Industrial Control Software using ACTS. 2018 IEEE Intl Conf Software Quality, Reliability and Security (QRS) 2018 Jul 16 (pp. 414-425)

"Our results show that not all combinations of algorithms and interaction strengths could generate a test suite within a realistic cut-off time. The results of the modeling process and the efficiency evaluation of ACTS are useful for practitioners considering to use combinatorial testing for industrial control software as well as for researchers trying to improve the use of such combinatorial testing techniques."

Daimler-Benz - 

Automotive

 

Züfle, Siegmar, and Venkataraman Krishnamoorthy. "A process for nonfunctional combinatorial testing: Selection of parameter values from a nondiscrete domain space." 2015 IEEE Eighth International Conference on Software Testing, Verification and Validation Workshops 

"This paper describes the preliminary and subsequent work before and after a combinatorial test set generation for non-functional full-automatic testing of a car infotainment system."
Red Hat - 
Operating system
 

Ahmed BS, Pahim A, Junior CR, Kuhn DR, Bures M. Towards an Automated Unified Framework to Run Applications for Combinatorial Interaction Testing. arXiv preprint arXiv:1903.05387. 2019 Mar 13.

Describes a framework for generating, executing and verifying CIT test suites, based on the open-source Avocado test framework. The new framework can generate, execute, and verify effective combinatorial interaction test suites for detecting configuration failures (invalid configurations) in a virtualization system.

Sulake - video games/social network

 

Puoskari, E., Vos, T.E., Condori-Fernandez, N. and Kruse, P.M., 2013. Evaluating applicability of combinatorial testing in an industrial environment: A case study. 2013 Intl Wkshp Joining Academia and Industry Contributions to testing Automation ACM.

Abstract: This paper reports on a case study done for evaluating a combinatorial testing tool in a realistic industrial environment with real objects and subjects. The case study has been executed at Sulake, a company that develops social entertainment games and whose main product is Habbo Hotel, a social network community in the shape of an online Hotel that is visited by millions of teenagers every week all around the world. This paper describes the experimental design of the case study together with the results and decisions that Sulake has taken about the further study, adoption and implantation of these type of tools.
Scania AB - automotive  

Chunduri, Annapurna, Robert Feldt, and Mikael Adenmark. "An effective verification strategy for testing distributed automotive embedded software functions: A case study." Intl Conf Product-Focused Software Process Improvement, pp. 233-248. Springer, 2016.

The proposed verification strategy to test distributed automotive embedded software functions has given promising results by providing means to identify test gaps and test redundancies. It helps establish an effective and feasible approach to capture function test coverage information that helps enhance the effectiveness of integration testing of the distributed software functions.

Oak Ridge National Lab - scientific software  

Vilkomir, S.A., Swain, W.T., Poore, J.H. and Clarno, K.T., 2008, June. Modeling input space for testing scientific computational software: a case study. Intl Conf Computational Science Springer, Berlin

Abstract. An application of a method of test case generation for scientific computational software is presented. NEWTRNX, neutron transport software being developed at Oak Ridge National Laboratory, is treated as a case study. A model of dependencies between input parameters of NEWTRNX is created. Results of NEWTRNX model analysis and test case generation are evaluated.

Lockheed Martin -

Failure analysis

 

Cunningham, A. M., Hagar, J., & Holman, R. J.  A System Analysis Study Comparing Reverse Engineered Combinatorial Testing to Expert Judgment. InSoftware Testing, Verification and Validation (ICST), 2012 IEEE Fifth Intl Conference on(pp. 630-635) IEEE.

Lockheed Martin F-16 ventral fin redesign “The historic analysis was able to determine a set of combinations, which isolated the problem and tested a solution. However, the original effort was expensive, time consuming, and required highly specialized knowledge from the expert to be effective. In the study, a series of iterations created combinatorial test cases which could have 'replicated' the original highly optimized and successful test program, without the expert.”

Database system queries  

Tsumura, K., Washizaki, H., Fukazawa, Y., Oshima, K. and Mibe, R., 2016, April. Pairwise coverage-based testing with selected elements in a query for database applications. In 2016 IEEE Ninth International Conference on Software Testing, Verification and Validation Workshops (ICSTW) (pp. 92-101). IEEE.

Develops a method of applying combinatorial testing for use with SQL database query programs. Results showed that the pairwise tests detected “many bugs which are not detected by existing test methods based on predicates in the query”. 

NIST/US Air Force - laptop applications  

Kuhn DR, Higdon JM, Lawrence JF, Kacker RN, Lei Y. Combinatorial methods for event sequence testing. In2012 IEEE Fifth International Conference on Software Testing, Verification and Validation 2012 Apr 17 (pp. 601-609). IEEE.

"The methods described in this paper were motivated by testing needs for systems that may accept multiple communication or sensor connections and generate output to several communication links and other interfaces, where it is important to test the order in which connections occur. Although pairwise event order testing (both A followed by B and B followed by A) has been described, our algorithm ensures that any t events will be tested in every possible t-way order."

Video coding

 

Hong, D., & Chae, S. I. (2014, June). Efficient test bitstream generation method for verification of HEVC decoders. In Consumer Electronics (ISCE 2014), The 18th IEEE International Symposium on (pp. 1-2).

Combinatorial methods provided an 84X efficiency improvement for testing conformance to a new video coding standard. The original conformance testing spec included 1,000,182 coding tree units, but using a 3-way covering array plus two more tests, they provided better coverage with 13,712 units. Coverage was measured in 'syntax elements', requiring > 90% coverage of the syntax elements. The authors say, "In the proposed method the SE coverage normalized by the number of CTUs is 84 times higher compared to that in the HEVC conformance test suite. This means that we can verify the HEVC decoders 84 times faster with the test bitstream set obtained by the proposed method, compared to the HEVC conformance test suite."

Mobile app penetration testing   Ratliff, Z.B., 2018. Black-box Testing Mobile Applications Using Sequence Covering Arrays (thesis). Abstract.  This research examines the effectiveness of using sequence covering arrays to discover software bugs in mobile phone applications. 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.
Financial enterprise  

Fögen, K. and Lichter, H., 2018. A Case Study on Robustness Fault Characteristics for Combinatorial Testing-Results and Challenges. QuASoQ 2018, p.18.

Abstract.  Combinatorial strategies are extended to generate invalid test inputs but the effectiveness of negative test scenarios is yet unclear. Therefore, we conduct a case study and analyze 434 failures reported as bugs of a financial enterprise application. As a result, 51 robustness failures are identified including failures triggered by invalid value combinations and failures triggered by interactions of valid and invalid values.

Industrial controls  

Bergström, Henning, and Eduard Paul Enoiu. "Using timed base-choice coverage criterion for testing industrial control software." 2017 IEEE Intl Conf Software Testing, Verification and Validation Workshops (ICSTW). IEEE, 2017.

Applies combinatorial test methods to industrial control software.  “We found that tests generated for timed base-choice criterion show better code coverage (7% improvement) and fault detection (27% improvement) in terms of mutation score than tests satisfying base-choice coverage criterion. The results demonstrate the feasibility of applying timed base-choice criterion for testing industrial control software.”

Web content management system  

Sánchez, A.B., Segura, S., Parejo, J.A. and Ruiz-Cortés, A., 2017. Variability testing in the wild: the Drupal case study. Software & Systems Modeling16(1)"

"Among other results, we identified 3392 faults in single features and 160 faults triggered by the interaction of up to four features in Drupal v7.23. We also found positive correlations relating the number of bugs in Drupal features to their size, cyclomatic complexity, number of changes and fault history. To show the feasibility of our work, we evaluated the effectiveness of non-functional data for test case prioritization in Drupal. Results show that non-functional attributes are effective at accelerating the detection of faults, outperforming related prioritization criteria as test case similarity."

Software as a service  

Srikanth, H. and Cohen, M.B., 2011, September. Regression testing in software as a service: An industrial case study. In 2011 27th IEEE Intl Conf Software Maintenance (ICSM) IEEE.

We have applied our technique to two releases of a large industrial enterprise level SaaS application and demonstrate that using our approach (1) we could have uncovered escaped faults prior to the system release in both versions of the system; (2) using a priority order we could have improved the efficiency of testing in the first version; and (3) prioritization based on failure history from the first version increases the fault detection rate in the new version, suggesting a correlation between the important sequences in versions that can be leveraged for regression testing.

Web administration

 

N. Condori-Fernandez, T. Vos, P.M. Kruse, E. Brosse, A. Bagnato. Analyzing the Applicability of a Combinatorial Testing Tool in an Industrial Environment, Tech. Rpt. UU-CS-2014-008, May 2014, Univ. of Utrecht.

"The main outcomes of the presented study are: (1) with the test suite designed with the CTE, the testers were able to find faults that the traditional test suites did not find, one of them a severe fault; (2) the company realized that the current coverage metrics used for evaluating the quality of test suites needs to be changed to a more sophisticated one; (3) SOFTEAM’s motivation to do more case studies with the CTE is high"

Full text search on web server  

Raunak MS, Kuhn DR, Kacker R. Combinatorial testing of full text search in Web applications. 2017 IEEE Intl Conf on Software Quality, Reliability and Security Companion (QRS-C)

Testing full-text search in a database web application. We develop test-case selection techniques, where test strings are synthesized using characters or string fragments that may lead to system failure. Demonstrated discovery of a number of "corner-cases" that had not been identified previously. We also present simple heuristics for isolating the fault causing factors that can lead to such system failures. The test method and input model described in this paper have immediate application to other systems that provide complex full text search.

School management web application  

Manchester S, Bryce R, Sampath S, Samant N, Kuhn DR, Kacker R. Applying higher strength combinatorial criteria to test case prioritization: a case study.

Using the CPUT tool, we "conduct an empirical study where we compare 2-way and 3-way combinatorial coverage of inter-window parameter interactions in terms of the rate of fault detection for a web application called Schoolmate and a user-session-based test suite. Our results show that the rate of fault detection for 2-way and 3-way prioritization are within 1% of each other, but 2-way provides a slightly better result."

Web applications

 

Maughan, C.Test Case Generation Using Combinatorial Based Coverage for Rich Web Applications. Logan, UT: Utah State Univ (2012).

Compared exhaustive (discretized values) w/ CT. 2-way tests found all but one fault found by exhaustive using < 13% of tests required for exhaustive.

MP3 audio

 

Zhang, Z., Liu, X., & Zhang, J. (2012, April). Combinatorial Testing on ID3v2 Tags of MP3 Files. InSoftware Testing, Verification and Validation (ICST), 2012 IEEE Fifth International Conf

Most faults detected by 1-way and 2-way tests, with one caused by 4-way interaction.

iGate Corp. -

Product engineering; banking & financial services; insurance

 

M. Mehta, R. Philip, Applications of Combinatorial Testing methods for Breakthrough Results in Software Testing, 2nd Intl. Wkshp on Combinatorial Testing, Luxembourg, IEEE, Mar. 2013.

"Combinatorial Testing (CT) approach has greatly helped our projects from different domains to optimize testing effort without compromising on testing quality. We were able to achieve breakthrough business results. CT based freeware tools such as All Pairs & ACTS are of great help for testing professionals to optimize effort and reduce learning curve."

Various

 

L. Shikh Gholamhossein Ghandehari, M. N. Bourazjany, Yu Lei, R.N. Kacker and D.R. Kuhn, "Applying Combinatorial Testing to the Siemens Suite", 2nd Intl. Wkshp Combinatorial Testing, Luxembourg, IEEE, Mar. 2013.

"Modeled the seven programs in the Siemens suite and applied combinatorial testing to these programs. The results show that combinatorial testing can detect most faulty versions of the Siemens programs, and is more effective than random testing."

Linux system utilities  

Borazjany MN, Ghandehari LS, Lei Y, Kacker R, Kuhn R. An input space modeling methodology for combinatorial testing. 2013 IEEE Sixth Intl Conf on Software Testing, Verification and Validation Wkshp

This paper describes a method for modeling input structures and parameters, and compares combinatorial with random testing using the same input models.  It is shown that combinatorial testing provides better structural coverage and detects more errors than random. 

Covering array tool

 

Borazjany, M. N., Yu, L., Lei, Y., Kacker, R., & Kuhn, R. (2012, April). Combinatorial Testing of ACTS: A Case Study. Software Testing, Verification and Validation (ICST), 2012 IEEE Fifth Intl Conf(pp. 591-600)

Applied 2-way and 3-way tests; approx. 80% module and branch coverage, 88% statement coverage 15 faults found; 2-way tests found as many as 3-way.

NIST -

Web browser
DOM modules

 

C. Montanez, D.R. Kuhn, M. Brady, R. Rivello, J. Reyes, M.K. Powers,Evaluation of Fault Detection Effectiveness for Combinatorial and Exhaustive Selection of Discretized Test Inputs Software Quality Professional - June, 2012.

Compared exhaustive (discretized values) w/ CT, 2-way to 6-way. 4-way tests found all faults using < 5% of tests required for exhaustive, for a 20X reduction in test set size. 

Created May 24, 2016, Updated August 20, 2019