In September 2017, this (legacy) site will be replaced with the new site you can see at beta.csrc.nist.rip. At that time, links to this legacy site will be automatically redirected to apporpriate links on the new site.

View the beta site
NIST Logo and ITL Banner Link to the NIST Homepage Link to the ITL Homepage Link to the NIST Homepage

Automated Combinatorial Testing for Software (ACTS)

t-way faultsCombinatorial testing is a proven method for more effective software testing at lower cost. The key insight underlying combinatorial testing’s effectiveness resulted from a series of studies by NIST from 1999 to 2004. NIST research showed that most software bugs and failures are caused by one or two parameters, with progressively fewer by three or more. This finding, referred to as the interaction rule, has important implications for software testing because it means that testing parameter combinations can provide more efficient fault detection than conventional methods. New algorithms compressing combinations into a small number of tests have made this method practical for industrial use, making it possible to do better testing at lower cost.

Read more


Our focus is on empirical results and real-world testing.

Quick Start - It's easy to learn the basics of this advanced method!

  1. 3-page summary
  2. Combinatorial and pairwise testing tutorial (81 pgs.)
  3. Briefing slides (approx. 60 min).

 

FREELY AVAILABLE SOFTWARE: Software on this site is free of charge and will remain free in the future. It is public domain; no license is required and there are no restrictions on use. NIST is an agency of the United States Government.


NEW - Introducing Combinatorial Testing in a Large Organization:  Experience Report, (poster); full paper in IEEE Computer, April 2015.
J. Hagar. D.R. Kuhn, R.N. Kacker, T. Wissink.
An extensive evaluation of combinatorial testing by one of the world's largest aerospace firms.  Describes the experience of Lockheed Martin applying combinatorial methods in eight pilot projects, with roughly 20% cost savings and 20% to 50% better coverage. Extended abstract. Presented at 3rd International Workshop on Combinatorial Testing, Cleveland, Mar. 31, 2014.


NEW - Oracle-free Testing - software testing normally requires that for each test, there is an expected output, known as a test oracle.  Combinatorial methods make it possible to detect a significant number of faults without a conventional test oracle.  This seemingly impossible task is achieved using two layers of covering arrays with equivalence classes derived from specifications. Source code is not required.  Essentially, we are able to take advantage of the information latent in equivalence classes to do extensive consistency checking, revealing errors.
  • Presentation on this method from the NSF Research Experience for Undergraduates
  • Paper - Intl. Workshop on Combinatorial Testing, 2015 - introduces this method; with illustrative examples
  • Paper - Intl. Workshop on Combinatorial Testing, 2016 (submitted) - related method applied to access control rules

Book - We have published the first textbook on combinatorial methods in software testing, Introduction to Combinatorial Testing, Rick Kuhn, Raghu Kacker, Yu "Jeff" Lei, with chapter contributions from Renee Bryce, Eduardo Miranda, Sreedevi Sampath, and George Sherwood. (CRC Press, ISBN 1466552298, June 2013; 319 pgs). The book provides software testers, developers, and students with a self-contained tutorial on how to use these methods for real-world software.
"I thoroughly recommend it to anyone involved in the practice of software testing." - ACM Computing Reviews


Recent Talks (Kuhn):

Video of 2013 NASA IV&V conference briefing on application of combinatorial coverage measurement. (Charley Price and Rick Kuhn)


Tool releases, August 2015:  Version 2.93 of ACTS testing tool and Version 0.8 of CCM combinatorial coverage measurement tool now available


Combinatorial Coverage Measurement - NIST IR 7878 (released Sept. 2012)
Tools provided freely on this site are used by hundreds of organizations around the world for software and hardware testing of reliability, safety, and security. Our research collaborations include the U. of Texas Arlington, US Air Force, Carnegie Mellon, U. of North Texas, Johns Hopkins University Applied Physics Lab, U. of Maryland Baltimore County, Centro Nacional de Metrologia of Mexico, NASA, and the U. of Maryland University College. This article explains how the approach is related to statistical Design of Experiments.

Combinatorial testing poster summarizes the methodology.

Our research program includes:

  • advanced covering array algorithms;
  • combinatorial coverage measurement;
  • cybersecurity testing;
  • fault localization;
  • distribution of interaction faults;
  • testing web apps;
  • application to modeling and simulation.

Some of our accomplishments to date include:

  • empirical finding that software failures triggered by interactions of few variables (1 to 6);
  • IPOG covering array algorithm and its variants, more efficient than other known algorithms;
  • demonstrating effectiveness of test prioritization;
  • demonstrating improved efficiency for modeling and simulation;
  • access control testing automation;
  • measurement science and tools for combinatorial coverage.

Rick Kuhn or Raghu Kacker
kuhn@nist.gov, raghu.kacker@nist.gov    


Back to Top


We have 2,300 users as of June 2015, in nearly all major industries. Here is a breakdown of our user base.


1) Combinatorial testing tool, for generating test suites. Advanced Combinatorial Testing System (ACTS) can compute tests for 2-way through 6-way interactions. An easy-to-use GUI is included. A comparison of ACTS with similar tools shows that ACTS produces smaller test sets (with the same degree of coverage) and is faster than others. ACTS was developed by NIST and the University of Texas at Arlington. To request a copy, send email to Rick Kuhn. Please include your first and last name, and company or university name (this helps us with management support for the project!) ACTS won the 2009 Excellence in Technology Transfer Award from the Federal Laboratory Consortium Mid-Atlantic Region.


2) Combinatorial coverage measurement tool, for evaluating quality of test suites. Useful for gaining the advantages of combinatorial testing without disrupting existing test practice. The CCM measurement tool can analyze existing tests for 2-way through 6-way interactions they already have. An easy-to-use GUI is included. CCM was developed by NIST and the Centro Nacional de Metrologia of Mexico. To request a copy, send email to Rick Kuhn. Please include your first and last name, and company or university name (this helps us with management support for the project!)


3) Testing tutorial, Practical Combinatorial Testing, NIST SP 800-142
(81 pages). This publication provides a self-contained tutorial on using combinatorial testing for real-world software. It introduces the key concepts and methods, explains use of software tools for generating combinatorial tests, and discusses advanced topics. The material is accessible to an undergraduate student of computer science or engineering, and includes an extensive set of references to papers that provide more depth on each topic. Oct. 2010. Public domain, distribution unlimited; 81 pages.


4) Security policy testing tool. The Access Control Policy Test (ACPT) tool allows policy authors to conveniently specify access control models (such as RBAC and Multi-Level models) and rules as well as access control properties. From the specified models and rules, the ACPT tool automatically synthesizes deployable policies in XACML and generates combinatorial tests to verify security policy implementations. Complete test cases are generated, consisting of test inputs and expected output for each set of inputs. ACPT uses ACTS to provide 2-way to 4-way combinatorial testing of policies. To request a copy, send email to Vincent Hu


5) Web app testing tool. CPUT (Combinatorial-based Prioritization of User-session-based Testsuites) applies combinatorial methods to testing web applications. Test prioritization is used to make web app testing much more manageable. The tool allows testers to easily collect, prioritize, and reduce user-session-based test cases. CPUT provides (1) guidance to users on how to configure their web server to log important usage information, (2) automated parsing of web logs into XML formatted test cases that can be used by test replay tools, (3) automated prioritization of test cases by length-based and combinatorial-based criteria, and (4) automated reduction of testcases by combinatorial coverage.

Back to Top


Past Events

  • C. Price, R. Kuhn, R. Forquer, A. Lagoy, R. Kacker, Evaluating the t-way Combinatorial Technique for Determining the Thoroughness of a Test Suite, NASA IV&V Workshop, 2013.
  • 2nd International Workshop on Combinatorial Testing association with 5th IEEE International Conference on Software Testing, Verification and Validation (ICST 2013, March 18-22) Luxembourg.
  • 1st Asian Workshop on Combinatorial Testing (PPT in zip file)
  • 1st International Workshop on Combinatorial Testing In association with 5th IEEE International Conference on Software Testing, Verification and Validation April 17-21, 2012, Montreal, Canada - The workshop was a great success, with 10 presented, lots of lively discussion. Presentations here.
  • NIST/Carnegie Mellon University workshop, June 7, 2011, on software verification was a great success, with more than 150 participants locally and via webcast.
  • A survey by Gary Gack found that nearly everyone who tried combinatorial testing has found it useful!
  • Combinatorial coverage measurement was presented to NASA developers and researchers at the NASA IV&V Workshop , September 11-13, 2012.
  • We gave talks at East Carolina University and Carnegie Mellon University earlier this year.
  • ACTS team members presented three papers at the First Intl Workshop on Combinatorial Testing, April, 2012.
  • 1,000th organization acquired ACTS tool in March 2012.
  • We did a half-day tutorial on combinatorial methods at ICSM 2011 and lecture at Verify/ATI in September.
  • Rick Kuhn and Raghu Kacker are presenting a half-day tutorial on combinatorial methods at the IEEE International Conference on Software Maintenance, ICSM 2011, September 26 in Williamsburg, Virginia.
  • Rick Kuhn and Sreedevi Sampath are speaking at the Verify/ATI conference on September 27, in Arlington, Virginia.
  • Raghu Kacker presented seminars on combinatorial testing and ACTS at Fraunhofer Institute for Open Communication Systems (FOKUS) and Technical University of Berlin June 27 and 28, 2011.
  • Advanced test methods seminar in Pittsburgh at Carnegie Mellon University with Prof. Eduardo Miranda in June, drew over 150 attendees in person and via internet.
  • ACTS profiled in IEEE Computer, February 2011, News Briefs.
  • Seminars and talks: NASA IV&V, August 31; Fraunhofer Center - UMD, August 15; NASA IV&V, July 14; Carnegie Mellon Univ., June 7, Johns Hopkins University Applied Physics Lab, April 27; Institute for Defense Analyses, April 6; Army Test and Evaluation Command, March 30;  Institute for Defense Analyses February 25;Carnegie-Mellon University February 9.
  • Raghu Kacker gave invited talks at Indian Institute of Technology, Madras, and Infosys Corp., January 2011.
  • November issue of Logigear magazine features an interview (Rick Kuhn) and an article on combinatorial testing.
  • ACTS featured in SIGNAL, the flagship publication of the Armed Forces Communications and Electronics Association.
  • Rick Kuhn speaking on combinatorial testing at Dept of Energy modeling and simulation workshop December 1, 2010.
  • New Help on Testing for Common Cause of Software Bugs, Government Computer News, November 1, 2010. ACTS also featured in The EngineerInformation Week and TMC.net.
  • ACTS project featured in October issue of Logigear Magazine.
  • NIST initiated a Cooperative Research and Development Agreement with Lockheed Martin Corp. in August 2010.
  • 500th organization acquired ACTS tool in November 2010
  • Rick Kuhn, Raghu Kacker, and Sreedevi Sampath conducted a workshop on combinatorial testing for the US Army Test and Evaluation Command in May.
  • 300th organization acquired ACTS tool in February 2010
  • Rick Kuhn gave an invited talk on combinatorial testing at Carnegie Mellon University in January.
  • ACTS received 2009 Excellence in Technology Transfer Award from the Federal Laboratory Consortium Mid-Atlantic Region.
  • Our new introductory article on combinatorial testing was featured as one of the Highlights for the August 2009 issue of IEEE Computer, the flagship publication of the IEEE Computer Society.

Back to Top


Seminars and Talks


Quick introductions to Combinatorial Testing


Conference Presentations

Back to Top


Tutorial

  • Combinatoral and pairwise testing tutorial Practical Combinatorial Testing, NIST SP 800-142, (October 2010) - a concise, easy to read tutorial, for individual study or classroom use. Public domain, distribution unlimited; 81 pages.

Papers

  • Kuhn, D.R., Hu, V., Ferraiolo, D., Kacker, R., Lei, Y., Pseudo-exhaustive Testing of Attribute Based Access Control Rules, (Aug. 2015) Preprint, to be submitted Intl Workshop on Combinatorial Testing.
  • Hagar, J. D., Wissink, T. L., Kuhn, D. R., & Kacker, R. N. (2015). Introducing Combinatorial Testing in a Large Organization. IEEE Computer, (4), 64-72.
  • DR Kuhn, R Bryce, F Duan, L Sh. Ghandehari, Yu Lei, RN Kacker, Combinatorial Testing, Theory and Practice, Advances in Computers, vol. 99 (to appear, 2015).
  • Kuhn, D. R., Kacker, R. N., Lei, Y., & Torres-Jimenez, J. (2015, April). Equivalence class verification and oracle-free testing using two-layer covering arrays. In Software Testing, Verification and Validation Workshops (ICSTW), 2015 IEEE Eighth International Conference on (pp. 1-4). IEEE.
  • Duan, F., Lei, Y., Yu, L., Kacker, R. N., & Kuhn, D. R. (2015, April). Improving IPOG's vertical growth based on a graph coloring scheme. In Software Testing, Verification and Validation Workshops (ICSTW), 2015 IEEE Eighth International Conference on (pp. 1-8). IEEE.
  • Yu, L., Duan, F., Lei, Y., Kacker, R. N., & Kuhn, D. R. (2015, April). Constraint handling in combinatorial test generation using forbidden tuples. In Software Testing, Verification and Validation Workshops (ICSTW), 2015 IEEE Eighth International Conference on (pp. 1-9). IEEE.
  • Ghandehari, L. S., Chandrasekaran, J., Lei, Y., Kacker, R., & Kuhn, D. R. (2015, April). BEN: A combinatorial testing-based fault localization tool. In Software Testing, Verification and Validation Workshops (ICSTW), 2015 IEEE Eighth International Conference on (pp. 1-4). IEEE.
  • D.R. Kuhn, R.N. Kacker and Y. Lei, Combinatorial Coverage as an Aspect of Test Quality, Mar/Apr 2015 CrossTalk: Journal of Defense Software EngineeringArticle (pdf)
    Preprint
  • D.R. Kuhn, R.N. Kacker and Y. Lei, Measuring and Specifying Combinatorial Coverage of Test Input Configurations, submitted to Innovations in Systems and Software Engineering: a NASA journal, [2015].
    Preprint
  • L. S. Ghandehari, J. Czerwonka, Y. Lei, S. Shafiee, R. Kacker and R. Kuhn, An Empirical Comparison of Combinatorial and Random Testing, Third International Workshop on Combinatorial Testing (IWCT 2014), in Proceedings of the Seventh IEEE International Conference on Software, Testing, Verification and Validation (ICST 2014), Cleveland, Ohio, March 31-April 4, 2014, pp. 68-77.
    Abstract; DOI: 10.1109/ICSTW.2014.8; Preprint
  • J. Hagar, R. Kuhn, R. Kacker, and T. Wissink, Introducing Combinatorial Testing in a Large Organization: Pilot Project Experience Report [poster], Third International Workshop on Combinatorial Testing (IWCT 2014), in Proceedings of the Seventh IEEE International Conference on Software, Testing, Verification and Validation (ICST 2014), Cleveland, Ohio, March 31-April 4, 2014, p. 153.
    Abstract; DOI: 10.1109/ICSTW.2014.70; Preprint
  • R. Kuhn, R Kacker and Y. Lei, Estimating Fault Detection Effectiveness [poster], Third International Workshop on Combinatorial Testing (IWCT 2014), in Proceedings of the Seventh IEEE International Conference on Software, Testing, Verification and Validation (ICST 2014), Cleveland, Ohio, March 31-April 4, 2014, p. 154.
    Abstract; DOI: 10.1109/ICSTW.2014.69; Preprint
  • J. Torres-Jimenez, I. Izquierdo-Marquez, Survey of Covering Arrays, 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2013), Timisoara, Romania, September 23-26, 2013, pp. 20-27.
    DOI: 10.1109/SYNASC.2013.10
  • R.N. Kacker, D.R. Kuhn, Y. Lei, and J.F. Lawrence, Combinatorial Testing for Software: an Adaptation of Design of Experiments, Measurement, vol. 46, no. 9, November 2013, pp. 3745-3752.
    DOI: 10.1016/j.measurement.2013.02.021
  • X. Niu, C. Nie, Y. Lei, A.T.S. Chan, Identifying Failure-Inducing Combinations Using Tuple Relationships, 2nd International Workshop on Combinatorial Testing (IWCT 2013), in Proceedings of the Sixth IEEE International Conference on Software, Testing, Verification and Validation (ICST 2013), Luxembourg, March 18-22, 2013, pp. 271-280.
    DOI: 10.1109/ICSTW.2013.38; Preprint
  • D.R. Kuhn, I. Dominguez Mendoza, R.N. Kacker and Y. Lei. Combinatorial Coverage Measurement Concepts and Applications, 2nd International Workshop on Combinatorial Testing (IWCT 2013), in Proceedings of the Sixth IEEE International Conference on Software, Testing, Verification and Validation (ICST 2013), Luxembourg, March 18-22, 2013, pp. 352-361.
    Abstract; DOI: 10.1109/ICSTW.2013.77; Preprint
  • L.S.G. Ghandehari, M.N. Borazjany, Y. Lei, R.N. Kacker and D.R. Kuhn, Applying Combinatorial Testing to the Siemens Suite, 2nd International Workshop on Combinatorial Testing (IWCT 2013), in Proceedings of the Sixth IEEE International Conference on Software, Testing, Verification and Validation (ICST 2013), Luxembourg, March 18-22, 2013, pp. 362-371.
    Abstract; DOI: 10.1109/ICSTW.2013.47; Preprint
  • M.N. Borazjany, L.S.G. Ghandehari, Y. Lei, R.N. Kacker and D.R. Kuhn, An Input Space Modeling Methodology for Combinatorial Testing, 2nd International Workshop on Combinatorial Testing (IWCT 2013), in Proceedings of the Sixth IEEE International Conference on Software, Testing, Verification and Validation (ICST 2013), Luxembourg, March 18-22, 2013, pp. 372-381.
    Abstract; DOI: 10.1109/ICSTW.2013.48; Preprint
  • D.R. Kuhn and R.N. Kacker, Measuring Combinatorial Coverage of System State-space for IV&V [extended abstract], NASA IV&V Workshop, Morgantown, West Virginia, September 11-13, 2012.
    Abstract; Presentation
  • S. Manchester, R. Bryce, S. Sampath, N. Samant, D. R. Kuhn and R. Kacker, Applying Higher Strength Combinatorial Criteria to Test Prioritization: a Case Study, to appear in: Journal of Combinatorial Mathematics and Combinatorial Computing.
    Preprint
  • D.R. Kuhn, R.N. Kacker and Y. Lei. Combinatorial Testing, Encyclopedia of Software Engineering, edited by Phillip A. Laplante. Taylor & Francis, 2012.
    Abstract; DOI: 10.1081/E-ESE-120048153; Preprint
  • D.R. Kuhn, J.M. Higdon, J.F. Lawrence, R.N. Kacker and Y. Lei, Efficient Methods for Interoperability Testing Using Event Sequences, CrossTalk (Hill AFB): the Journal of Defense Software Engineering, vol. 25, no. 4, July/August 2012, pp. 15-18.
    Abstract; Article
  • C. Montanez-Rivera, D.R. Kuhn, M. Brady, R.M. Rivello, J. Reyes and M.K. Powers, Evaluation of Fault Detection Effectiveness for Combinatorial and Exhaustive Selection of Discretized Test Inputs, Software Quality Professional, vol. 14, no. 3, June 2012.
    Abstract; Article; Preprint
  • M.N. Borazjany, L. Yu, Y. Lei, R. Kacker and R. Kuhn, Combinatorial Testing of ACTS: A Case Study, First International Workshop on Combinatorial Testing, in Proceedings of the IEEE Fifth International Conference on Software, Testing, Verification and Validation (ICST 2012), Montreal, Quebec, Canada, April 17-21, 2012, pp. 591-600.
    Abstract; DOI: 10.1109/ICST.2012.146
  • K. Shakya, T. Xie, N. Li, Y. Lei, R. Kacker and R. Kuhn, Isolating Failure-Inducing Combinations in Combinatorial Testing using Test Augmentation and Classification, First International Workshop on Combinatorial Testing, in Proceedings of the IEEE Fifth International Conference on Software, Testing, Verification and Validation (ICST 2012), Montreal, Quebec, Canada, April 17-21, 2012, pp. 620-623.
    Abstract; DOI: 10.1109/ICST.2012.149; Preprint
  • D.R. Kuhn, J.M. Higdon, J.F. Lawrence, R.N. Kacker and Y. Lei, Combinatorial Methods for Event Sequence Testing, First International Workshop on Combinatorial Testing, in Proceedings of the IEEE Fifth International Conference on Software, Testing, Verification and Validation (ICST 2012), Montreal, Quebec, Canada, April 17-21, 2012, pp. 601-609.
    Abstract; DOI: 10.1109/ICST.2012.147; Preprint
  • V.C. Hu, D.R. Kuhn, T. Xie and J. Hwang, Model Checking for Verification of Mandatory Access Control Models and Properties, International Journal of Software Engineering and Knowledge Engineering, vol. 21, no. 1, February 2011, pp. 103-127.
    Abstract; DOI: 10.1142/S021819401100513X; Preprint
  • J. Lawrence, R.N. Kacker, Y. Lei, D.R. Kuhn, and M. Forbes, A Survey of Binary Covering Arrays, Electronic Journal of Combinatorics, vol. 18, no. 1, art. P84, April 7, 2011.
    Abstract; Article
  • D.R. Kuhn, R.N. Kacker and Y. Lei, Advanced Combinatorial Test Methods for System Reliability, 2010 Annual Technical Report of the IEEE Reliability Society, January 2011.
    Article
  • C. Montanez, D.R. Kuhn, M. Brady, R. Rivello, J. Reyes, M.K. Powers, An Application of Combinatorial Methods to Conformance Testing for Document Object Model Events, NIST Internal Report (NISTIR) 7773, November 2010, 9 pp.
    Abstract; NISTIR 7773
  • R.C. Bryce, C.J. Colbourn and D.R. Kuhn, Finding Interaction Faults Adaptively using Distance-Based Strategies, 18th IEEE International Conference and Workshops on Engineering of Computer Based Systems (ECBS), Las Vegas, Nevada, April 27-29, 2011, pp.4-13.
    DOI: 10.1109/ECBS.2011.9
  • J.R. Maximoff, M.D. Trela, D.R. Kuhn and R. Kacker, A Method for Analyzing System State-space Coverage within a t-Wise Testing Framework, 4th Annual IEEE International Systems Conference, April 5-8, 2010, San Diego, California, pp. 598-603.
    DOI: 10.1109/SYSTEMS.2010.5482481
  • D.R. Kuhn, R. Kacker and Y.Lei, Random vs. Combinatorial Methods for Discrete Event Simulation of a Grid Computer Network, MODSIM World 2009, Virginia Beach, Virginia, October 14-16, 2009. In Selected Papers Presented at MODSIM World 2009 Conference and Expo, edited by T.E. Pinelli, NASA/CP-2010-216205, National Aeronautics and Space Administration, pp. 83-88.
    Abstract; Paper
  • D.R. Kuhn,R. Kacker, Y. Lei, Combinatorial and Random Testing Effectiveness for a Grid Computer Simulator
  • R. Kuhn, R. Kacker, Y. Lei and J. Hunter, Combinatorial Software Testing, IEEE Computer, vol. 42, no. 8, August 2009, pp. 94-96.
    Abstract; DOI: 10.1109/MC.2009.253; Preprint
  • R.C. Bryce, Y. Lei, D.R. Kuhn and R. Kacker, Combinatorial Testing, Ch. 14 in Handbook of Research on Software Engineering and Productivity Technologies: Implications of Globalization, edited by M. Ramachandran and R. Atem de Carvalho, IGI Global, 2010, pp.196-208.
    DOI: 10.4018/978-1-60566-731-7.ch014
  • V.C. Hu, D.R. Kuhn and T. Xie, Property Verification for Generic Access Control Models, 2008 IEEE/IFIP International Symposium on Trust, Security, and Privacy for Pervasive Applications (TSP-08) in Volume 2 of Proceedings of the 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC-08), Shanghai, China, December 17-20, 2008, pp. 234-250.
    Abstract; DOI: 10.1109/EUC.2008.22; Preprint
  • M. Ellims, D. Ince and M. Petre, The Effectiveness of T-Way Test Data Generation, 27th International Conference on Computer Safety, Reliability, and Security (SAFECOMP 2008), Newcastle upon Tyne, U.K., September 22-25, 2008. In Computer Safety, Reliability, and Security, Lecture Notes in Computer Science 5219, pp.16–29.
    DOI: 10.1007/978-3-540-87698-4_5
  • M. Forbes, J. Lawrence, Y. Lei, R.N. Kacker, and D.R. Kuhn, Refining the In-Parameter-Order Strategy for Constructing Covering Arrays, Journal of Research of the National Institute of Standards and Technology, vol. 113, no. 5, September-October 2008, pp. 287-297.
    Abstract; DOI: 10.6028/jres.113.022
  • D.R. Kuhn, R. Kacker and Y. Lei, Automated Combinatorial Test Methods: Beyond Pairwise Testing, CrossTalk (Hill AFB): the Journal of Defense Software Engineering, vol. 21, no. 6, June 2008, pp.22-26.
    Abstract; Article
    Comment: A fairly comprehensive tutorial on combinatorial testing and automated test generation, with a worked example.
  • R. Kessel and R. Kacker, A Test of Linearity Using Covering Arrays for Evaluating Uncertainty in Measurement, Advanced Mathematical and Computational Tools in Metrology and Testing (AMCTM VIII), Paris, France, June 23-25, 2008, Series on Advances in Mathematics for Applied Sciences vol. 78, pp.195-203.
    Abstract; DOI: 10.1142/7212; Preprint
  • R. Kuhn, Y. Lei and R. Kacker, Practical Combinatorial Testing: Beyond Pairwise Testing, IT Professional, vol. 10, no. 3, May-June 2008, pp.19-23.
    Abstract; DOI: 10.1109/MITP.2008.54
    Comment: Quick introduction to combinatorial testing.
  • Y. Lei, R. Kacker, D. Kuhn, V. Okun and J. Lawrence, IPOG/IPOD: Efficient Test Generation for Multi-Way Combinatorial Testing, Software Testing, Verification, and Reliability, vol. 18, no. 3, September 2008, pp. 125-148.
    Abstract; DOI: 10.1002/stvr.381
  • Y. Lei, R.H. Carver, R. Kacker and D. Kung, A Combinatorial Testing Strategy for Concurrent Programs, Software Testing, Verification, and Reliability, vol. 17, no. 4, December 2007, pp. 207-225.
    Abstract; DOI: 10.1002/stvr.369
  • 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’07), Tucson, Arizona, March 26-29 2007, pp. 549-556.
    Abstract; DOI: 10.1109/ECBS.2007.47; Preprint
  • R. Bryce and C.J. Colbourn, Prioritized Interaction Testing for Pair-wise Coverage with Seeding and Constraints, Information and Software Technology, vol. 48, no. 10, October 2006, pp. 960-970.
    DOI: 10.1016/j.infsof.2006.03.004
  • R. Bryce, A. Rajan and M.P.E. Heimdahl, Interaction Testing in Model-Based Development: Effect on Model-Coverage, 13th Asia-Pacific Software Engineering Conference (APSEC 2006), Kanpur, India, December 6-8, 2006, pp. 259-268.
    DOI: 10.1109/APSEC.2006.42
  • D. R. Kuhn, V. Okun, Pseudo-exhaustive Testing for Software, 30th Annual IEEE/NASA Software Engineering Workshop (SEW-30), Columbia, Maryland, April 24-28, 2006, pp. 153-158.
    Abstract; DOI: 10.1109/SEW.2006.26; Preprint
    Comment: Proof-of-concept experiment on pseudo-exhaustive testing, integrating automated test generation with combinatorial testing.
  • R.C. Bryce, C.J. Colbourn and M.B. Cohen, A Framework of Greedy Methods for Constructing Interaction Test Suites, 27th International Conference on Software Engineering (ICSE 2005), St. Louis, Missouri, May 15-21, 2005, pp. 146-155.
    DOI: 10.1109/ICSE.2005.1553557
  • M. Grindal, J. Offutt and S.F. Andler, Combination Testing Strategies: a Survey, Software Testing, Verification and Reliability, vol. 15, no. 3, March 2005, pp. 167-199.
    DOI: 10.1002/stvr.319; Preprint
    Comment: A survey of combinatorial testing methods and results.
  • D.R. Kuhn, D.R. Wallace, A.M. Gallo, Jr., Software Fault Interactions and Implications for Software Testing, IEEE Transactions on Software Engineering, vol. 30, no. 6, June 2004, pp. 418-421.
    Abstract; DOI: 10.1109/TSE.2004.24
    Comment: Investigates interaction level required to trigger faults in a large distributed database system.
  • D.R. Kuhn and M.J. Reilly, An Investigation of the Applicability of Design of Experiments to Software Testing, 27th Annual NASA Goddard/IEEE Software Engineering Workshop (SEW ’02), Greenbelt, Maryland, December 5-6, 2002, pp. 91-95.
    Abstract; DOI: 10.1109/SEW.2002.1199454; Preprint
    Comment: Investigates interaction level required to trigger faults in open source browser and server.
  • D.R. Wallace and D.R. Kuhn, Failure Modes in Medical Device Software: an Analysis of 15 Years of Recall Data, International Journal of Reliability, Quality and Safety Engineering, vol. 8, no. 4, December 2001, pp.351-371.
    Abstract; DOI: 10.1142/S021853930100058X; Preprint
    Comment: Categorizes failures by their symptoms and faults, including interaction level required to trigger faults in medical device software.

Back to Top


Combinatorial Methods for Modeling and Simulation

  • D.R. Kuhn, R. Kacker and Y.Lei, Random vs. Combinatorial Methods for Discrete Event Simulation of a Grid Computer Network, MODSIM World 2009, Virginia Beach, Virginia, October 14-16, 2009. In Selected Papers Presented at MODSIM World 2009 Conference and Expo, edited by T.E. Pinelli, NASA/CP-2010-216205, National Aeronautics and Space Administration, pp. 83-88.
    Abstract; Paper
  • R. Kessel and R. Kacker, A Test of Linearity Using Covering Arrays for Evaluating Uncertainty in Measurement, Advanced Mathematical and Computational Tools in Metrology and Testing (AMCTM VIII), Paris, France, June 23-25, 2008, Series on Advances in Mathematics for Applied Sciences vol. 78, pp.195-203.
    Abstract; DOI: 10.1142/7212; Preprint

Automated Test Generation Using Model Checking

  • V.C. Hu, D.R. Kuhn, T. Xie and J. Hwang, Model Checking for Verification of Mandatory Access Control Models and Properties, International Journal of Software Engineering and Knowledge Engineering, vol. 21, no. 1, February 2011, pp. 103-127.
    Abstract; DOI: 10.1142/S021819401100513X; Preprint
  • D.R. Kuhn, R. Kacker and Y. Lei, Automated Combinatorial Test Methods: Beyond Pairwise Testing, CrossTalk (Hill AFB): the Journal of Defense Software Engineering, vol. 21, no. 6, June 2008, pp.22-26.
    Abstract; Article
    Comment: A fairly comprehensive tutorial on combinatorial testing and automated test generation, with a worked example.
  • V. Okun and P. E. Black, Issues in Software Testing with Model Checkers, submitted to 2003 International Conference on Dependable Systems and Networks (DSN 2003), San Francisco, California, June 22-25, 2003.
    Preprint
    Comment: Explains effective use of model checking to generate complete test cases.
  • V . Okun, Specification Mutation for Test Generation and Analysis, PhD Dissertation, University of Maryland Baltimore County, 2004, 77 pp.
    Dissertation
    Comment: Both theoretical and experimental methods for selecting the most effective mutation operators for test generation.
  • V . Okun, P.E. Black and Y. Yesha, Testing with Model Checkers: Insuring Fault Visibility, WSEAS Transactions on Systems, vol. 2, no. 1, January 2003, pp. 77-82.
    Abstract; Paper
    Comment: Describes specification-based mutation methods using a model checker to guarantee propagation of faults to visible outputs. Same paper was presented at 2002 WSEAS International Conference on System Science, Applied Mathematics & Computer Science, and Power Engineering Systems, Rio de Janeiro, Brazil, October 21-23, 2002.
  • P .E. Black, V. Okun and Y. Yesha, Mutation Operators for Specifications, Fifteenth IEEE International Conference on Automated Software Engineering, Grenoble, France, September 11-15, 2000, pp. 81-88.
    Abstract; DOI: 10.1109/ASE.2000.873653; Preprint
    Comment: Sets of mutation operators that yield good test coverage at reduced cost compared with other operators.

Back to Top



Disclaimer: Certain software products are identified in this document. Such identification does not imply recommendation by NIST, nor does it imply that the products identified are necessarily the best available for the purpose.Belorussian translation of our project summary here.