Clustering test cases to achieve effective and scalable prioritisation incorporating expert knowledge

ABSTRACT

Pair-wise comparison has been successfully utilised in order to prioritise test cases by exploiting the rich, valuable and unique knowledge of the tester. However, the prohibitively large cost of the pair-wise comparison method prevents it from being applied to large test suites. In this paper, we introduce a cluster-based test case prioritisation technique. By clustering test cases, based on their dynamic runtime behaviour, we can reduce the required number of pair-wise comparisons significantly. The approach is evaluated on seven test suites ranging in size from 154 to 1,061 test cases. We present an empirical study that shows that the resulting prioritisation is more effective than existing coverage-based prioritisation techniques in terms of rate of fault detection. Perhaps surprisingly, the paper also demonstrates that clustering (even without human input) can outperform unclustered coverage-based technologies, and discusses an automated process that can be used to determine whether the application of the proposed approach would yield improvement.

REFERENCES

• 1: Paolo Avesani , Cinzia Bazzanella , Anna Perini , Angelo Susi, Facing Scalability Issues in Requirements Prioritization with Machine Learning Techniques, Proceedings of the 13th IEEE International Conference on Requirements Engineering, p.297-306, August 29-September 02, 2005 [doi>10.1109/RE.2005.30]
• 2: Hyunsook Do , Sebastian Elbaum , Gregg Rothermel, Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact, Empirical Software Engineering, v.10 n.4, p.405-435, October 2005 [doi>10.1007/s10664-005-3861-2]
• 3: Hyunsook Do , Gregg Rothermel, On the Use of Mutation Faults in Empirical Assessments of Test Case Prioritization Techniques, IEEE Transactions on Software Engineering, v.32 n.9, p.733-752, September 2006 [doi>10.1109/TSE.2006.92]
• 4: C. Douligeris and I. Pereira. A telecommunications quality study using the analytic hierarchy process. IEEE Journal on Selected Areas in Communications, 12(2):241--250, Feb 1994.
• 5: Sebastian Elbaum , Alexey G. Malishevsky , Gregg Rothermel, Test Case Prioritization: A Family of Empirical Studies, IEEE Transactions on Software Engineering, v.28 n.2, p.159-182, February 2002 [doi>10.1109/32.988497]
• 6: Sebastian Elbaum , Alexey G. Malishevsky , Gregg Rothermel, Prioritizing test cases for regression testing, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.102-112, August 21-24, 2000, Portland, Oregon, United States
• 7: Sebastian Elbaum , Alexey Malishevsky , Gregg Rothermel, Incorporating varying test costs and fault severities into test case prioritization, Proceedings of the 23rd International Conference on Software Engineering, p.329-338, May 12-19, 2001, Toronto, Ontario, Canada
• 8: Gavin R. Finnie , Gerhard E. Wittig , Doncho I. Petkov, Prioritizing software development productivity factors using the analytic hierarchy process, Journal of Systems and Software, v.22 n.2, p.129-139, Aug. 1993 [doi>10.1016/0164-1212(93)90091-B]
• 9: J. Karlsson, C. Wohlin, and B. Regnell. An evaluation of methods for prioritizing software requirements. Information&Software Technology, 39(14-15):939--947, 1998.
• 10: David Leon , Andy Podgurski, A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases, Proceedings of the 14th International Symposium on Software Reliability Engineering, p.442, November 17-21, 2003
• 11: Zheng Li , Mark Harman , Robert M. Hierons, Search Algorithms for Regression Test Case Prioritization, IEEE Transactions on Software Engineering, v.33 n.4, p.225-237, April 2007 [doi>10.1109/TSE.2007.38]
• 12: Modeling the Cost-Benefits Tradeoffs for Regression Testing Techniques, Proceedings of the International Conference on Software Maintenance (ICSM'02), p.204, October 03-06, 2002
• 13: A. G. Malishevsky, J. R. Ruthruff, G. Rothermel, and S. Elbaum. Cost-cognizant test case prioritization. Technical Report TR-UNL-CSE-2006-0004, Department of Computer Science and Engineering, University of Nebraska-Lincoln, March 2006.
• 14: Gregg Rothermel , Sebastian Elbaum , Alexey Malishevsky , Praveen Kallakuri , Brian Davia, The impact of test suite granularity on the cost-effectiveness of regression testing, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581358]
• 15: Gregg Rothermel , Roland H. Untch , Chengyun Chu , Mary Jean Harrold, Test Case Prioritization: An Empirical Study, Proceedings of the IEEE International Conference on Software Maintenance, p.179, August 30-September 03, 1999
• 16: Gregg Rothermel , Roland J. Untch , Chengyun Chu, Prioritizing Test Cases For Regression Testing, IEEE Transactions on Software Engineering, v.27 n.10, p.929-948, October 2001 [doi>10.1109/32.962562]
• 17: T. Saaty. The Analytic Hierarchy Process, Planning, Piority Setting, Resource Allocation. McGraw-Hill, New York, USA, 1980.
• 18: H. Srikanth, L. Williams, and J. Osborne. System test case prioritization of new and regression test cases. In Proceedings of International Symposium on Empirical Software Engineering, pages 64--73, November 2005.
• 19: Paolo Tonella , Paolo Avesani , Angelo Susi, Using the Case-Based Ranking Methodology for Test Case Prioritization, Proceedings of the 22nd IEEE International Conference on Software Maintenance, p.123-133, September 24-27, 2006 [doi>10.1109/ICSM.2006.74]
• 20: Kristen R. Walcott , Mary Lou Soffa , Gregory M. Kapfhammer , Robert S. Roos, TimeAware test suite prioritization, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146240]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Algorithms

Keywords:
ahp, clustering, test case prioritisation