Test case filtering and prioritization based on coverage of combinations of program elements

ABSTRACT

Test case filtering is concerned with selecting from a test suite T a subset T' that is capable of revealing most of the defects revealed by T. A smaller T' is desirable since it translates to fewer test runs to be audited manually. Test case prioritization, a related technique, aims at scheduling the tests in T so that the defects are revealed as early as possible when T gets executed. We propose techniques that are based on coverage of combinations of program elements of different types. Clearly, exploring all possible combinations induced at runtime is infeasible, which calls for the use of an approximation algorithm. In this paper we investigate the use of a genetic algorithm to select a number of suitable combinations of program elements to be covered. We compared our technique to other coverage-based techniques that consider program elements of the same type and that do not take into account their combinations; our preliminary results were promising. For example, after filtering the original test suite T for JTidy, the resulting T' revealed all the defects in T and was only 14.1% its size.

References

1. P. Ammann and J. Offutt, Introduction to Software Testing, Cambridge University Press, 2008.
2. S. Butenko and W. E. Wilhelm, "Clique-detection models in computational biochemistry and genomics", European Journal of Operational Research, 173(1), pp. 1--17, 2006.
3. Elbaum S., Malishevsky A. and Rothermel G. Test Case Prioritization: A Family of Empirical Studies. IEEE Transactions on Software Engineering, vol. 26, no. 2, February 2002.
4. T.L. Graves, M. J. Harrold, J. M. Kim, A. Porter, and G. Rothermel, "An empirical study of regression test selection techniques," ACM Transactions on Software Engineering and Methodology, vol. 10, no. 2, April 2001, pp. 184--208.
5. Q. Guo, R. M. Hierons, M. Harman, K. Derderian, "Computing Unique Input/Output Sequences using Genetic Algorithms", Proceedings of the 3 ^rd International Workshop on Formal Approaches to Software Testing (FATES '03), Montreal, Canada, October 2003, pp. 1098--1100.
6. Hyunsook Do, Sebastian Elbaum, and Gregg Rothermel. Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact. Empirical Software Engineering: An International Journal, Volume 10, No. 4, pages 405--435, 2005.
7. Jeffrey D. and Gupta N. Test Case Prioritization Using Relevant Slices.
8. M. J. Harrold, R. Gupta, and M. L. Soffa. A methodology for controlling the size of a test suite. ACM Transactions on Software Engineering and Methodology 2, 3 (July 1993), 270--285.
9. D.S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing, Boston, MA, 1997.
10. M. Hifi, "A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems", The Journal of the Operational Research Society, 48(6), pp.612--622, 1997.
11. Kim, J. M. and Porter, A. A history-based test prioritization technique for regression testing in resource constrained environments. 2002 International Conference on Software Engineering (Orlando, FL, May 2002).
12. Leon D. and Podgurski A. A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases. ISSRE 2003.
13. Z. Li, M. Harman, R. M. Hierons, "Search Algorithms for Regression Test Case Prioritization", IEEE Transactions on Software Engineering, 33(4), pp. 225--237, 2007.
14. W. Masri, A. Podgurski and D. Leon. "An Empirical Study of Test Case Filtering Techniques Based On Exercising Information Flows". IEEE Transactions on Software Engineering, July, 2007, vol. 33, number 7, page 454.
15. S. McMaster, A. M. Memon: Call-Stack Coverage for GUI Test Suite Reduction. IEEE Trans. Software Eng. 34(1): 99--115 (2008)
16. X. Qu, M. B. Cohen, G. Rothermel: Configuration-aware regression testing: an empirical study of sampling and prioritization. ISSTA 2008: 75--86
17. X. Qu, M. B. Cohen, K. M. Woolf: Combinatorial Interaction Regression Testing: A Study of Test Case Generation and Prioritization. ICSM 2007: 255--264
18. G. Rothermel, M. J. Harrold, J. Ostrin, and C. Hong, "An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites," Proc. Int'l Conf. Software Maintenance, Nov. 1998, pp. 34--43.
19. Rothermel G., Untch R. and Harrold M. J. Prioritizing Test Cases for Regression Testing. IEEE Transactions on Software Engineering, vol. 27. no. 10, October 2001.
20. S. Sampath, R. C. Bryce, G. Viswanath, V. Kandimalla, A. Gunes Koru: Prioritizing User-Session-Based Test Cases for Web Applications Testing. ICST 2008: 141--150.
21. A. Singh and A. K. Gupta, "A hybrid heuristic for the maximum clique problem", Journal of Heuristics, 12(1-2), pp. 5--22, 2006.
22. Walcott K. R., Soffa M. L., Kapfhammer G. M., and Roos R. S. TimeAware Test Suite Prioritization. ISSTA 2006, Portland, Main.
23. Wong, W. E., Horgan, J. R., London, S., and Mathur, A. P. Effect of test set size minimization and fault detection effectiveness. Software Practice and Experience 28, 4 (April 1998), 347--369.
24. Wong, W. E., Horgan, J. R., Mathur, A. P., and Pasquini, A. Test set size minimization and fault detection effectiveness: a case study in a space application. 21st Annual International Computer Software and Applications Conference (Washington, D. C., August 1997), 522--528.
25. A. X. Zheng, I. Rish, A. Beygelzimer: Efficient Test Selection in Active Diagnosis via Entropy Approximation. UAI 2005, Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, July 26--29 2005, Edinburgh, Scotland.
26. Zhu, H., Hall, P. and May, J. Software Unit Test Coverage and Adequacy. ACM Computing Surveys 29, 4. (December 1997). 366--426.

Index Terms

• Information systems

  • Data management systems

    • Middleware for databases

      • Distributed transaction monitors

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Monitors