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.
(updated 4 Sept 08)
Accomplishments
- Beta release of combinatorial testing tool
available to testers. The tool, named FireEye, can
compute tests for 2-way through 6-way interactions. An
easy-to-use GUI is included. More here.
To request a copy, send email
to Rick Kuhn - kuhn@nist.gov. (This software is provided free
of charge. NIST is an agency of the US Government.)
- Empirical data
showing all faults triggered by relatively low level of interactions
between variables (less than 6-way) across a variety of application
domains.
- New algorithms to generate covering arrays
that can produce optimal arrays for many applications and near optimal
arrays for very large applications (several hundred variables).
- Proof-of-concept
demonstration of integrating combinatorial testing with
automated generation of test oracles using model checking.
This web site provides research, empirical data, and tools for
pseudo-exhaustive and combinatorial testing. Contact: Rick Kuhn,
kuhn@nist.gov or Raghu
Kacker, raghu.kacker@nist.gov (please include "testing" in
subject line to help avoid spam filter).
News
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 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.
Briefings
- 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.
Publications on Combinatorial
Testing
- 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.
- 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, 2007.
(Published Online: Nov 29 2007, 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.
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.