Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

Automated Combinatorial Testing for Software

Case Studies - Combinatorial and Pairwise Testing

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. One of the first organizations to make extensive use of this type of testing for software and systems is the U.S. Air Force test group at Eglin Air Force Base, and a growing number of organizations have reported cost and time savings using the approach. Most of its use has been in computer software and hardware, defense/aerospace, telecommunications, and financial applications, although users can be found in nearly every industry.

The most extensive, publicly documented analysis to date of an industrial application of combinatorial testing has been an eight-project study by Lockheed Martin, a large U.S. defense contractor. Lockheed Martin has a Cooperative Research and Development Agreement (CRADA) with NIST [2]. CRADAs are one of the ways in which NIST conducts joint research with U.S. industry, allowing federal laboratories to work with U.S. industry, providing flexibility in structuring projects and protecting industry-proprietary information and research results. Lockheed Martin and NIST entered into the agreement in 2010 to better understand applicability and effectiveness of the combinatorial testing approach for software testing to improve quality, safety and reliability of U.S. products and systems. Of particular interest was understanding the challenges in introducing a new approach for software testing in a large U.S. corporation. Projects evaluated the viability of the concept for achieving the following goals:

• Test process improvement in a variety of domains: system, software, and hardware testing;

• Make tests more effective in finding problems; and

• Reduce the cost of testing, or at least reduce test life-cycle cost by finding fewer errors late in development or in the field.

The pilot projects demonstrated that it was practical to incorporate the new methods, with testing cost reduction of approximately 20 %, with 20 % to 50 % improvement in test coverage.

Recent projects reported by other organizations include:

• A team of developers in banking and financial services reported, "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 [Automated Combinatorial Testing for Software] are of great help for testing professionals to optimize effort and reduce learning curve." [5]

An application of combinatorial testing to automotive electronics by a large manufacturer found the method to be a significant advance over traditional test approaches. The authors reported that they “observed a remarkable reduction in time to identify more likely defects and increased probability in detecting of less probable defects. This is especially crucial when the market release of product approaches.”[8]

• An “industry proof-of-concept demonstration used combinatorial testing approach to automate parts of the unit and integration testing of a highly complex 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. The test would also determine if CT was adequately accurate, rigorous, thorough, and scalable. 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.”[3]

• Combinatorial methods provided an 84X efficiency improvement for testing conformance to a new video coding standard, HEVC (High Efficiency Video Coding). 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 more than 90 % coverage of the syntax elements. The authors say, "In the proposed method, the SE [syntax elements] coverage normalized by the number of CTUs [coding tree units] 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." [4]

Additional Resources

[1] D. R. Kuhn, R. N. Kacker, and Y. Lei, Practical Combinatorial Testing, National Institute of Standards and Technology (NIST) Special Publication (SP) 800-142, October 2010, 82 pp. http://dx.doi.org/10.6028/NIST.SP.800-142.

[2] J. D. Hagar, T. L. Wissink, D. R. Kuhn, and R. N. Kacker, “Introducing combinatorial testing in a large organization,” Computer (IEEE), vol. 48, no. 4 (April 2015), pp. 64-72. http://dx.doi.org/10.1109/MC.2015.114.

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

[4] D. Hong and S.-I. Chae, “Efficient test bitstream generation method for verification of HEVC decoders,” 18th IEEE International Symposium on Consumer Electronics (ISCE 2014), JeJu Island, South Korea, June 22-25, 2014, 2 pp. http://dx.doi.org/10.1109/ISCE.2014.6884404.

[5] M. Mehta and R. Philip, “Applications of Combinatorial Testing Methods for Breakthrough Results in Software Testing,” 2nd International Workshop on Combinatorial Testing (IWCT 2013), Luxembourg, March 22, 2013, in Proceedings, IEEE Sixth International Conference on Software, Testing, Verification and Validation Workshops, Piscataway, New Jersey: IEEE Computer Society, 2013, pp. 348-351.http://dx.doi.org/10.1109/ICSTW.2013.46.

[6] Y. Lei, R. Kacker, D. R. Kuhn, V. Okun, and J. Lawrence, “IPOG: a General Strategy for t-way Software Testing,” 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS 2007), Tucson, Arizona, United States, March 26-29, 2007, pp. 549–556. http://dx.doi.org/10.1109/ECBS.2007.47.

[7] D. R. Kuhn, I. Dominguez, R. N. Kacker, and Y. Lei, “Combinatorial Coverage Measurement Concepts and Applications,” 2nd International Workshop on Combinatorial Testing (IWCT 2013), Luxembourg, March 22, 2013, in Proceedings, IEEE Sixth International Conference on Software, Testing, Verification and Validation Workshops, Piscataway, New Jersey: IEEE Computer Society, 2013, pp. 352-361. http://dx.doi.org/10.1109/ICSTW.2013.77.

[8] S. Züfle and V. Krishnamoorthy, “A process for nonfunctional combinatorial testing: Selection of parameter values from a nondiscrete domain space,” 2015 IEEE 8th International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Graz, Austria, April 13-17, 2015, 4 pp. http://dx.doi.org/10.1109/ICSTW.2015.7107437.


Application

Reference

Notes

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

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"

avionic

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

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

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

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; none by 3-way not also found in 2-way.

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

aerospace

J. Hagar, D.R. Kuhn, R.N. Kacker, Introducing Combinatorial Testing to a Large System-Software Organization, to appear, TBD.

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

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

Created May 24, 2016, Updated July 26, 2018