Myra B. Cohen
ABSTRACT
Software system faults are often caused by unexpected interactions among components. Yet the size of a test suite required to test all possible combinations of interactions can be prohibitive in even a moderately sized project. Instead, we may use pairwise or t-way testing to provide a guarantee that all pairs or t-way combinations of components are tested together. This concept draws on methods used in statistical testing for manufacturing and has been extended to software system testing. A covering array, CA(N; t, k, v), is an N × k array on v symbols such that every N × t sub-array contains all ordered subsets from v symbols of size t at least once. The properties of these objects, however, do not necessarily satisfy real software testing needs. Instead we examine a less studied object, the mixed level covering array and propose a new object, the variable strength covering array, which provides a more robust environment for software interaction testing. Initial results are presented suggesting that heuristic search techniques are more effective than some of the known greedy methods for finding smaller sized test suites. We present a discussion of an integrated approach for finding covering arrays and discuss how application of these techniques can be used to construct variable strength arrays.
- I. Anderson. Combinatorial Designs and Tournaments. Oxford University Press, New York, 1997.Google Scholar
- R. Brownlie, J. Prowse, and M. S. Padke. Robust testing of AT&T PMX/StarMAIL using OATS. AT&T Technical Journal, 71(3):41--7, 1992.Google ScholarCross Ref
- K. Burr and W. Young. Combinatorial test techniques: Table-based automation, test generation and code coverage. In Proc. of the Intl. Conf. on Software Testing Analysis & Review, 1998, San Diego.Google Scholar
- M. Chateauneuf and D. Kreher. On the state of strength-three covering arrays. Journal of Combinatorial Designs, 10(4):217--238, 2002Google ScholarCross Ref
- D. M. Cohen, S. R. Dalal, M. L. Fredman, and G. C. Patton. The AETG system: an approach to testing based on combinatorial design. IEEE Transactions on Software Engineering, 23(7):437--44, 1997. Google ScholarDigital Library
- D. M. Cohen, S. R. Dalal, M. L. Fredman, and G. C. Patton. Method and system for automatically generating efficient test cases for systems having interacting elements United States Patent, Number 5,542,043, 1996.Google Scholar
- D. M. Cohen, S. R. Dalal, J. Parelius, and G. C. Patton. The combinatorial design approach to automatic test generation. IEEE Software, 13(5):83--8, 1996. Google ScholarDigital Library
- D. M. Cohen and M. L. Fredman. New techniques for designing qualitatively independent systems. Journal of Combinatorial Designs, 6(6):411--16, 1998.Google ScholarCross Ref
- C. Colbourn and J. Dinitz. Making the MOLS table. In Computational and Constructive Design Theory, 1996. (W.D.Wallis, ed.) Kluwer Academic Press, 67--134.Google Scholar
- S. R. Dalal, A. J. N. Karunanithi, J. M. L. Leaton, G. C. P. Patton, and B. M. Horowitz. Model-based testing in practice. In Proc. of the Intl. Conf. on Software Engineering,(ICSE '99), 1999, pp. 285--94, New York. Google ScholarDigital Library
- G. Dueck. New optimization heuristics - the great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104:86--92, 1993. Google ScholarDigital Library
- I. S. Dunietz, W. K. Ehrlich, B. D. Szablak, C. L. Mallows, and A. Iannino. Applying design of experiments to software testing. In Proc. of the Intl. Conf. on Software Engineering, (ICSE '97), 1997, pp. 205--215, New York. Google ScholarDigital Library
- L. Gargano, J. Körner, and U. Vaccaro. Capacities: from information theory to extremal set theory. J. Combin. Theory Ser. A, 68(2):296--316, 1994. Google ScholarDigital Library
- A. Hedayat, N. Sloane, and J. Stufken. Orthogonal Arrays. Springer-Verlag, New York, 1999.Google ScholarCross Ref
- G. Katona. Two applications (for search theory and truth functions) of Sperner type theorems. Periodica Math., 3:19--26, 1973.Google ScholarCross Ref
- D. Kleitman and J. Spencer. Families of k-independent sets. Discrete Math, 6:255--262, 1973.Google ScholarDigital Library
- R. Mandl. Orthogonal latin squares: an application of experiment design to compiler testing. Communications of the ACM, 28(10): 1054--8, 1985. Google ScholarDigital Library
- K. Nurmela and P. R. J. Östergård. Constructing covering designs by simulated annealing. Technical report, Digital Systems Laboratory, Helsinki Univ. of Technology, 1993.Google Scholar
- P. R. J. Östergård. Constructions of mixed covering codes. Technical report, Digital Systems Laboratory, Helsinki Univ. of Technology, 1991.Google Scholar
- A. Réyni. Foundations of Probability. Wiley, New York, 1971.Google Scholar
- N. Sloane. Covering arrays and intersecting codes. Journal of Combinatorial Designs, 1(1):51--63, 1993.Google ScholarCross Ref
- J. Stardom. Metaheuristics and the search for covering and packing arrays. Master's thesis, Simon Fraser University, 2001.Google Scholar
- B. Stevens and E. Mendelsohn. Efficient software testing protocols. In Proc. of Center for Advanced Studies Conf. (Cascon '98), 1998, pp. 270--293, Ontario. Google ScholarDigital Library
- B. Stevens and E. Mendelsohn. New recursive methods for transversal covers. Journal of Combinatorial Designs, 7(3): 185--203, 1999.Google ScholarCross Ref
- B. Stevens, L. Moura, and E. Mendelsohn. Lower bounds for transversal covers. Designs Codes and Cryptography, 15(3):279--299, 1998. Google ScholarDigital Library
- K. C. Tai and L. Yu. A test generation strategy for pairwise testing. IEEE Transactions on Software Engineering, 28(1): 109--111, 2002. Google ScholarDigital Library
- A.W. Williams and R. L. Probert. A practical strategy for testing pair-wise coverage of network interfaces. In Proc. Seventh Intl. Symp. on Software Reliability Engineering, 1996, pp. 246--54. Google ScholarDigital Library
- A. W. Williams and R. L. Probert. A measure for component interaction test coverage. In Proc. ACS/IEEE Intl. Conf. on Computer Systems and Applications, 2001, pp. 301--311. Google ScholarDigital Library
- L. Yu and K. C. Tai. In-parameter-order: a test generation strategy for pairwise testing. In Proc. Third IEEE Intl. High-Assurance Systems Engineering Symp., 1998, pp. 254--261. Google ScholarDigital Library
- T. Yu-Wen and W. S. Aldiwan. Automating test case generation for the new generation mission software system. In Proc. IEEE Aerospace Conf., 2000, pp. 431--437.Google ScholarCross Ref
Index Terms
- Constructing test suites for interaction testing
Recommendations
Adaptive random prioritization for interaction test suites
SAC '14: Proceedings of the 29th Annual ACM Symposium on Applied ComputingCombinatorial interaction testing (CIT), a black-box testing method, has been well studied in recent years. It aims at constructing an effective interaction test suites, so as to identify the faults that are caused by interactions among parameters. ...
Constructing interaction test suites with greedy algorithms
ASE '05: Proceedings of the 20th IEEE/ACM International Conference on Automated Software EngineeringCombinatorial approaches to testing are used in several fields, and have recently gained momentum in the field of software testing through software interaction testing. One-test-at-a-time greedy algorithms are used to automatically construct such test ...
One-test-at-a-time heuristic search for interaction test suites
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computationAlgorithms for the construction of software interaction test suites have focussed on the special case of pairwise coverage; less is known about efficiently constructing test suites for higher strength coverage. The combinatorial growth of t-tuples ...
Comments