Renée C. Bryce
ABSTRACT
Greedy algorithms for the construction of software interaction test suites are studied. A framework is developed to evaluate a large class of greedy methods that build suites one test at a time. Within this framework are many instantiations of greedy methods generalizing those in the literature. Greedy algorithms are popular when the time for test suite construction is of paramount concern. We focus on the size of the test suite produced by each instantiation. Experiments are analyzed using statistical techniques to determine the importance of the implementation decisions within the framework. This framework provides a platform for optimizing the accuracy and speed of "one-test-at-a-time" greedy methods.
- K. Burr and W. Young. Combinatorial test techniques: Table-based automation, test generation, and code coverage. Proceedings of the Intl. Conf. on Software Testing Analysis and Review, pages 503--513, October 1998.Google Scholar
- J. N. Cawse. Experimental design for combinatorial and high throughput materials development. GE Global Research Technical Report, 29(9):769--781, November 2002.Google Scholar
- C. Cheng, A. Dumitrescu, and P. Schroeder. Generating small combinatorial test suites to cover input-output relationships. Proceedings of the Third International Conference on Quality Software (QSIC '03), pages 76--82, 2003. Google ScholarDigital Library
- 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, October 1997. Google ScholarDigital Library
- D. M. Cohen, S. R. Dalal, M.L.Fredman, and G. 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):82--88, October 1996. Google ScholarDigital Library
- M. B. Cohen. Designing test suites for software interaction testing. Ph.D. Thesis, The University of Auckland, Department of Computer Science, 2004.Google Scholar
- M. B. Cohen, C. J. Colbourn, P. B. Gibbons, and W. B. Mugridge. Constructing test suites for interaction testing. Proc. Intl. Conf. on Software Engineering (ICSE 2003), pages 38--48, 2003. Google ScholarDigital Library
- M. B. Cohen, C. J. Colbourn, and A. C. H. Ling. Constructing strength three covering arrays with augmented annealing. Discrete Mathematics, to appear.Google Scholar
- C. J. Colbourn. Combinatorial aspects of covering arrays. Le Matematiche (Catania), to appear.Google Scholar
- C. J. Colbourn, M. B. Cohen, and R. C. Turban. A deterministic density algorithm for pairwise interaction coverage. Proc. of the IASTED Intl. Conference on Software Engineering, pages 242--252, February 2004.Google Scholar
- J. H. Conway and N. J. A. Sloane. Lexicographic codes: error correcting codes from game theory. IEEE Trans. Inform. Theory, 32:337--348, 1986. Google ScholarDigital Library
- P. C. Denny and P. B. Gibbons. Case studies and new results in combinatorial enumeration. J. Combin. Des., 8:239--260, 2000.Google ScholarCross Ref
- A. Dumitrescu. Efficient algorithms for generation of combinatorial covering suites. Proc. 14-th Annual Intl. Symp. Algorithms and Computation (ISAAC '03), Lecture Notes in Computer Science, pages 300--308, 2003.Google ScholarCross Ref
- S. Dunietz, W. K. Ehrlich, B. D. Szablak, C. L. Mallows, and A. Iannino. Applying design of experiments to software testing. Proc. Intl. Conf. on Software Engineering (ICSE '97), pages 205--215, October 1997. Google ScholarDigital Library
- R. A. Fisher. The arrangement of field experiments. Journal of Ministry of Agriculture of Great Britain, 33(9):503--513, November 1926.Google Scholar
- P. B. Gibbons, R. A. Mathon, and D. G. Corneil. Computing techniques for the construction and analysis of block designs. Utilitas Math., 11:161--192, 1977.Google Scholar
- A. Hartman. Software and hardware testing using combinatorial covering suites. Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms, June 2002.Google Scholar
- A. Hartman and L. Raskin. Problems and algorithms for covering arrays. Discrete Math., 284:149--156, 2004.Google ScholarDigital Library
- A. Hartman and Z. Yehudai. Greedesigns. Ars Combin., 29C:69--76, 1990.Google Scholar
- N. Kobayashi, T. Tsuchiya, and T. Kikuno. A new method for constructing pair-wise covering designs for software testing. Information Processing Letters, 81:85--91, 2002. Google ScholarDigital Library
- D. Kuhn and M. Reilly. An investigation of the applicability of design of experiments to software testing. Proc. 27th Annual NASA Goddard/IEEE Software Engineering Workshop, pages 91--95, October 2002. Google ScholarDigital Library
- D. R. Kuhn, D. R. Wallace, and A. M. Gallo. Software fault interactions and implications for software testing. IEEE Trans. Software Engineering, 30(6):418--421, October 2004. Google ScholarDigital Library
- D. Montgomery. Design and Analysis of Experiments 5th edition. John Wiley and Sons, New York NY, 2001. Google ScholarDigital Library
- K. Nurmela. Upper bounds for covering arrays by tabu search. Discrete Applied Math., 138(9):143--152, March 2004. Google ScholarDigital Library
- D. Shasha, A. Kouranov, L. Lejay, M. Chou, and G. Coruzzi. Using combinatorial design to study regulation by multiple input signals. a tool for parsimony in the post-genomics era. Plant Physiology, 27:1590--1594, 2001.Google ScholarCross Ref
- K. Tai and L.Yu. A test generation strategy for pairwise testing. IEEE Transactions on Software Engineering, 28:109--111, 2002. Google ScholarDigital Library
- Y. Tung and W. Aldiwan. Automating test case generation for the new generation mission software system. IEEE Aerospace Conf., pages 431--37, 2000.Google Scholar
- M. B. Wells. Elements of Combinatorial Computing. Pergamon Press, Oxford-New York-Toronto, 1971.Google Scholar
- A. W. Williams. Determination of test configurations for pair-wise interaction coverage. Testing of communicating systems: Tools and techniques. 13th International Conference on Testing Communicating Systems, pages 59--74, October 2000. Google ScholarDigital Library
- A. W. Williams and R. L. Probert. A practical strategy for testing pair-wise coverage of network interfaces. Seventh Intl. Symp. on Software Reliability Engineering, pages 246--254, 1996. Google ScholarDigital Library
- A. W. Williams and R. L. Probert. A measure for component interaction test coverage. Proc. ACS/IEEE Intl. Conf. on Computer Systems and Applications, pages 301--311, October 2001. Google ScholarDigital Library
- C. Yilmaz, M. B. Cohen, and A. Porter. Covering arrays for efficient fault characterization in complex configuration spaces. Intl. Symp. on Software Testing and Analysis, pages 45--54, July 2004. Google ScholarDigital Library
Index Terms
- A framework of greedy methods for constructing interaction test suites
Recommendations
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 ...
Test prioritization for pairwise interaction coverage
A-MOST '05: Proceedings of the 1st international workshop on Advances in model-based testingInteraction testing is widely used in screening for faults. In software testing, it provides a natural mechanism for testing systems to be deployed on a variety of hardware and software configurations. Several algorithms published in the literature are ...
Test prioritization for pairwise interaction coverage
Interaction testing is widely used in screening for faults. In software testing, it provides a natural mechanism for testing systems to be deployed on a variety of hardware and software configurations. Several algorithms published in the literature are ...
Comments