Automated Combinatorial Testing for Software - beyond
pairwise testing
Software
developers frequently encounter failures that occur only as the result
of an
interaction between two components.
Testers
often use pairwise
testing – all pairs of parameter values – to detect
such interactions. Combinatorial testing beyond pairwise is rarely
used
because good algorithms for higher strength combinations (e.g., 4-way
or more)
have not been available, but empirical
evidence shows that some errors
are
triggered only by the interaction of three, four, or more parameters
(see graph). These
results have important implications for testing. If all faults in a
system can be triggered by a combination of n or
fewer parameters, then testing all n-way
combinations of parameters can provide high confidence that nearly all
faults have been discovered. We are producing methods and tools to
generate tests for all n-way
combinations of
parameter values, using improved combinatorial testing algorithms for
constructing covering arrays, and automated generation of test oracles
using model checking. This work will have applications in high
assurance software, safety and security, and combinatorial testing. Our
focus is on empirical results and real-world problems. For an
easy to read intro to combinatorial and pairwise testing, see this article.
Our research program currently includes:
- improved covering array algorithms
- fault localization
- distribution of interaction faults
- integration into the development process
- application to modeling and simulation.
Contact: Rick Kuhn,
kuhn@nist.gov or Raghu
Kacker,
raghu.kacker@nist.gov
(updated 30 July 09)
>>> free beta release of
combinatorial testing tool available to
testers. The tool, named Advanced Combinatorial Testing Suite (ACTS), can
compute tests for 2-way through 6-way interactions. An
easy-to-use GUI is included. More here.
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.
To request a copy, send email
to Rick Kuhn - kuhn@nist.gov. This software is provided free
of charge and will remain free in the future. NIST is an agency of the US Government.
Please Note: Prior to Feb
09, the name "FireEye" was used for the ACTS tool. In the papers and
articles listed below, FireEye is discussed; this is the same tool now
called ACTS.
Who uses our combinatorial testing tool? We have approximately
200 users as of July 2009, in IT, defense, finance, telecom, and many
other industries. Here is a breakdown of our user base.
News
Rick Kuhn and Raghu Kacker will give invited
talks on combinatorial methods for cyber security testing
at the DHS Software Assurance working group forum, June 16 - 18, 2009; and the Military Test and Evaluation Summit, June 24-25, McLean, VA.
Oct. 2008: Testing expert Elfriede Dustin talked about ACTS at the Google Test Automation Conference Oct 24, 2008. Video here.
Oct. 2008: ACTS covering array tool is being
used by W3C DOM
Level 3
Events working group to test conformance. Using 4-way
covering
arrays, strong testing is being provided with 1,833 tests, as compared
with over 36,000 before.
We have established a database of covering arrays here.
Software Development Times article: Automatically
Automate your Automation, Apr. 29, 2008.
We made Network World's list of 25
Radical Network Research Projects You Should Know About.
Apr. 17, 2008.
Rick Kuhn gave an invited talk on combinatorial testing and
our project at George Washington University, Mar. 10, 2008.
Jeff Lei was interviewed in Dr. Dobb's
Journal - Conversations: Pairwise and
Combinatorial Testing. Feb. 28, 2008.
Open-source
tool 'will boost software quality' - Computerworld UK, Dec.
14, 2007.
NIST
Working on New Method for Finding Software Bugs - Government
Computer News, Dec 13, 2007.
Proof-of-concept
demonstration of integrating combinatorial testing with
automated generation of test oracles using model checking.
Tutorial on this method here.
Briefings
- Rick Kuhn, Raghu Kacker, Combinatorial Testing Tutorial, Military Test and Evaluation, McLean, VA, June 24-25, 2009.
- D.R. Kuhn, R. Kacker, "Automated Combinatorial
Testing", VERIFY 2007, Crystal City, VA, Oct. 29-30, 2007.
- P. Black, "My Life with Bugs, or Why I
Believe in Combinatorial Testing", American Society for
Quality, Gaithersburg, MD Oct. 30, 2007.
- Y.
Lei, "IPOG - A
General Strategy for t-Way Software Testing", IEEE
Engineering of Computer Based Systems conference, 2007.- describes
generalized IPO algorithm for constructing t-way covering arrays.
- D.R.
Kuhn, V. Okun, "Automated
Combinatorial Testing for Software", ISSRE 06, Raleigh, Nov.
6, 2006.
- D. R. Kuhn, V. Okun, "Pseudo-exhaustive
Testing For Software (ppt file), 30th NASA/IEEE
Software Engineering Workshop, April 25-27, 2006 - proof-of-concept
experiment on pseudo-exhaustive testing.
- J. Lei, "In Parameter Order: A Test Generation
Strategy for Pairwise Testing", 6/21/05 - explains
the IPO algorithm, one of the most widely used in combinatorial
testing.
- D. R. Kuhn, "Software Fault Interactions",
OWASP AppSec DC 2005 - reviews empirical results on fault interactions,
suggesting a need for combinatorial testing.
Combinatorial
Testing for software
- R. Kuhn, R. Kacker, Y. Lei, J. Hunter, "Combinatorial Software Testing", IEEE Computer (to appear, 2009).
- V. Hu, D.R. Kuhn, T. Xie, "Property Verification for
Generic Access Control Models", IEEE/IFIP International
Symposium
on Trust, Security, and Privacy for Pervasive Applications, Shanghai,
China, Dec. 17-20, 2008.
- M. Ellims, D. Ince, M. Petre, "The Effectiveness of T-Way Test Data Generation", SAFECOMP 2008, Springer LNCS 5219, pp.16–29.
- M. Forbes, J. Lawrence,
Y. Lei, R.N. Kacker, and D.R. Kuhn "Refining
the In-Parameter-Order Strategy for Constructing Covering Arrays",
NIST Journal of Research, Vol. 113, No. 5 (Sept/Oct 2008), pp. 287 - 297.
- D.R. Kuhn, R. Kacker, Y. Lei, "Automated
Combinatorial Test
Methods: Beyond Pairwise Testing", Crosstalk,
Journal of
Defense Software Engineering, vol. 21, no. 6, June
2008 - a fairly
comprehensive tutorial on combinatorial testing and automated test
generation, with a worked example.
- D.R. Kuhn Y. Lei, R. Kacker, "Practical
Combinatorial Testing – Beyond Pairwise Testing",
IEEE IT
Professional, vol. 10, no. 3, June 2008 - quick introduction
to
combinatorial testing.
- Y. Lei, R.
Kacker, D. Kuhn, V. Okun, J. Lawrence, ``IPOG/IPOD: Efficient Test
Generation for Multi-Way Software Testing," accepted for publication in
Journal of Software Testing, Verification, and Reliability, vol. 18, pp. 125-148, DOI: 10.1002/stvr.381)
- Y.
Lei, R.
Carver, R. Kacker, D. Kung, ``A Combinatorial Strategy for Testing
Concurrent Programs," Journal of Software Testing, Verification, and
Reliability, 17(4):207-225, 2007.
- Y.Lei, R. Kacker, D.R. Kuhn, V. Okun, J. Lawrence, "IPOG - a General Strategy for
t-way Testing", IEEE Engineering of Computer Based
Systems conference, 2007.
- R.C. Bryce, C.J. Colbourn, D.R. Kuhn, "Finding Interaction
Faults Adaptively Using Distance Based Strategies" (submitted for
publication)
- R.
Bryce, C.J. Colbourn. Prioritized Interaction Testing for Pairwise
Coverage with Seeding and Avoids, Information and Software Technology
Journal (IST, Elsevier), (October 2006), 48(10):960-970.
- R. Bryce, A. Rajan, M.P.E. Heimdahl, "Interaction Testing
in
Model-Based Development: Effect on Model Coverage, 13th
Asia-Pacific Software Engineering Conf. Bangalore, India, 2006.
- J. Lei, "In Parameter Order: A Test Generation
Strategy for Pairwise Testing", 6/21/05 -
introduces IPO and outlines extension to > pairwise test.
Performance comparison with other tools here.
- R. Bryce, C.J. Colbourn, M.B. Cohen, "A
Framework of Greedy Methods for Constructing Interaction Tests",
27th Intl. Conf. on Software Engineering, 2005.
- M. Grindal, J. Offutt, S. Andler, "Combination
Testing Strategies: a Survey", Software Testing,
Verification and Reliability, Vol. 15, No. 3, pp. 167-199, 2005 - a
survey of combinatorial testing methods and results.
Combinatorial Methods for modeling and simulation
Empirical Results
Empirical
data showing all faults triggered by relatively low level of
interactions between variables (less than 6-way) across a variety of
application domains.
- D. R. Kuhn, V. Okun, "Pseudo-exhaustive
Testing For Software (conf. paper), 30th NASA/IEEE
Software Engineering Workshop, April 25-27, 2006 - proof-of-concept
experiment on pseudo-exhaustive testing, integrating automated test
generation with combinatorial testing.
- D.R. Kuhn, D.R. Wallace, A.J. Gallo, Jr., "Software
Fault Interactions and Implications for Software Testing",
IEEE Trans. on Software Engineering, vol. 30, no. 6, June, 2004) -
investigates interaction level required to trigger faults in a large
distributed database system.
- D.R. Kuhn, M.J. Reilly, "An
Investigation of the Applicability of Design of Experiments to Software
Testing", 27th NASA/IEEE Software Engineering
Workshop, NASA Goddard Space Flight Center, 4-6 December, 2002 -
investigates interaction level required to trigger faults in open
source browser and server.
- D.R. Wallace, 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, 2001 - categorizes failures by their symptoms and
faults, including interaction level required to trigger faults in
medical device software.
Automated Test Generation Using
Model Checking
- V. Okun, P. E. Black, “Issues
in Software Testing with Model Checkers”,
Proceedings of the International Conference on Dependable Systems and
Networks (DSN-2003), June 2003 - explains effective use of model
checking to generate complete test cases.
- V. Okun, "Specification Mutation for Test
Generation and Analysis", PhD Dissertation, U of
Maryland Baltimore Co., 2004 - both theoretical and experimental
methods for selecting the most effective mutation operators for test
generation.
- P. E. Black, V. Okun, Y. Yesha, "Testing
with Model Checkers: Insuring Fault Visibility",
WSEAS Trans. Sys., 2 (1): 77-82, Jan. 2003 - describes specification
mutation methods using a model checker to guarantee propagation of
faults to visible outputs.
- P. E. Black, V. Okun, Y. Yesha, "Mutation
Operators for Specfications", Automated Software
Engineering, 2000 - sets of mutation operators that yield good test
coverage at reduced cost compared with other operators.
Disclaimer: Certain software products are identified inthis document.
Such identification does not implyrecommendation by NIST, nor does it
imply that theproducts identified are necessarily the best available
for thepurpose.