Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

Automated Combinatorial Testing for Software

Industrial Case Studies - Combinatorial and Pairwise Testing

Industrial Case Studies and Practical Examples

Combinatorial testing is an extension of the established field of statistical Design of Experiments (DoE), endorsed by the Department of Defense and used by commercial firms with demonstrated success. Combinatorial testing is being applied successfully in nearly every industry.

The key advantage of combinatorial testing is 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

Lockheed Martin -

Aerospace

J. Hagar, D.R. Kuhn, R.N. Kacker, Introducing Combinatorial Testing to a Large System-Software Organization, to appear, 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%.”

Industrial controls, operating system - various companies, China

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

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. 

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."

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."

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.”

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. "

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 (ICSTW). IEEE, 2015.

"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.

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."

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 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. In2017 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C) 2017 Jul 25 (pp. 100-107). IEEE.

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.

Web applications

Maughan, C.Test Case Generation Using Combinatorial Based Coverage for Rich Web Applications. Logan, UT: Utah State University (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 Conference on(pp. 587-590). IEEE.

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. Workshop 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. Workshop on 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. In2013 IEEE Sixth International Conference on Software Testing, Verification and Validation Workshops 2013 Mar 18 (pp. 372-381). IEEE.

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. InSoftware Testing, Verification and Validation (ICST), 2012 IEEE Fifth Intl Conference on(pp. 591-600) IEEE.

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 May 16, 2019