A concept analysis inspired greedy algorithm for test suite minimization

ABSTRACT

Software testing and retesting occurs continuously during the software development lifecycle to detect errors as early as possible and to ensure that changes to existing software do not break the software. Test suites once developed are reused and updated frequently as the software evolves. As a result, some test cases in the test suite may become redundant as the software is modified over time since the requirements covered by them are also covered by other test cases. Due to the resource and time constraints for re-executing large test suites, it is important to develop techniques to minimize available test suites by removing redundant test cases. In general, the test suite minimization problem is NP complete. In this paper, we present a new greedy heuristic algorithm for selecting a minimal subset of a test suite T that covers all the requirements covered by T. We show how our algorithm was inspired by the concept analysis framework. We conducted experiments to measure the extent of test suite reduction obtained by our algorithm and prior heuristics for test suite minimization. In our experiments, our algorithm always selected same size or smaller size test suite than that selected by prior heuristics and had comparable time performance.

References

1. H. Agrawal, "Dominators, super blocks, and program coverage," 21st ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, Portland, Oregon, 1994.
2. H. Agrawal, "Efficient Coverage Testing Using Global Dominator Graphs," 1999 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, Toulouse, France, 1999.
3. G. Birkhoff Lattice Theory, volume 5, American Mathematical Soc. Colloquium Publications, 1940.
4. J. Black, E. Melachrinoudis and D. Kaeli, "Bi-Criteria Models for All-Uses Test Suite Reduction," 26th International Conference on Software Engineering, Edinburgh, Scotland, UK, 2004
5. V. Chvatal. "A Greedy Heuristic for the Set-Covering Problem." Mathematics of Operations Research. 4(3), August 1979.
6. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein "Introduction to Algorithms", MIT Press, Second Edition, September 2001.
7. M. R. Garey and D. S. Johnson, "Computers and Intractability-A Guide to the Theory of NP-Completeness," V Klee, Ed. Freeman, New York, 1979.
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):270--285, July 1993.
9. J. R. Horgan and S. A. London, "ATAC: A data flow coverage testing tool for C," in Proceedings of Symposium on Assessment of Quality Software Development Tools, pages 2--10, May 1992.
10. M. Hutchins, H. Foster, T. Goradia, and T. Ostrand, "Experiments on the Effectiveness of Dataflow- and Controlflow-based Test Adequacy Criteria," 16th International Conference on Software Engineering, May 1994.
11. http://www.cse.unl.edu/~galileo/sir
12. J. A. Jones and M. J. Harrold, "Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage," IEEE Transactions on Software Engineering, 29(3):195--209, March 2003.
13. M. Marre and A. Bertolino, "Using Spanning Sets for Coverage Testing," IEEE Transactions on Software Engineering, 29(11):974--984, Nov. 2003.
14. 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," International Conference on Software Maintenance, November 1998.
15. S. Sampath, V. Mihaylov, A. Souter and L. Pollock "A Scalable Approach to User-Session based Testing of Web Applications through Concept Analysis," in proceedings of Automated Software Engineering, 19th International Conference on (ASE'04) Linz, Austria, September 2004,
16. S. Sprenkle, S. Sampath, E. Gibson, A. Souter, L. Pollock, "An Empirical Comparison of Test Suite Reduction Techniques for User-session-based Testing of Web Applications," Technical Report 2005--009, Computer and Information Sciences, University of Delaware, November 2004
17. "The LLVM Compiler Infrastructure Project," http://llvm.cs.uiuc.edu/
18. W. E. Wong, J. R. Horgan, S. London, and A. P. Mathur. "Effect of Test Set Minimization on Fault Detection Effectiveness." Software Practice and Experience. 28(4):347--369, April 1998.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging