PHALANX: a graph-theoretic framework for test case prioritization

ABSTRACT

Test case prioritization for regression testing can be performed using different metrics (e.g., statement coverage, path coverage) depending on the application context. Employing different metrics requires different prioritization schemes (e.g., maximum coverage, dissimilar paths covered). This results in significant algorithmic and implementation complexity in the testing process associated with various metrics and prioritization schemes. In this paper, we present a novel approach to the test case prioritization problem that addresses this limitation. We devise a framework, Phalanx, that identifies two distinct aspects of the problem. The first relates to metrics that define ordering relations among test cases; the second defines mechanisms that implement these metrics on test suites. We abstract the information into a test-case dissimilarity graph -- a weighted graph in which nodes specify test cases and weighted edges specify user-defined proximity measures between test cases. We argue that a declustered linearization of nodes in the graph results in a desirable prioritization of test cases, since it ensures that dissimilar test cases are applied first. We explore two mechanisms for declustering the test case dissimilarity graph -- Fiedler (spectral) ordering and a greedy approach. We implement these orderings in Phalanx, a highly flexible and customizable testbed, and demonstrate excellent performance for test-case prioritization. Our experiments on test suites available from the Subject Infrastructure Repository (SIR) show that a variety of user-defined metrics can be easily incorporated in Phalanx.

REFERENCES

• 1: Taweesup Apiwattanapong , Alessandro Orso , Mary Jean Harrold, Efficient and precise dynamic impact analysis using execute-after sequences, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062534]
• 2: Renée C. Bryce , Charles J. Colbourn, Test prioritization for pairwise interaction coverage, Proceedings of the 1st international workshop on Advances in model-based testing, p.1-7, May 15-21, 2005, St. Louis, Missouri
• 3: Renée C. Bryce , Charles J. Colbourn , Myra B. Cohen, A framework of greedy methods for constructing interaction test suites, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062495]
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: Christoph Csallner , Yannis Smaragdakis, DSD-Crasher: a hybrid analysis tool for bug finding, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146267]
• 6: William Dickinson , David Leon , Andy Podgurski, Finding failures by cluster analysis of execution profiles, Proceedings of the 23rd International Conference on Software Engineering, p.339-348, May 12-19, 2001, Toronto, Ontario, Canada
• 7: 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]
• 8: 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]
• 9: Gregg Rothermel , Mary Jean Harrold , Jeffery Ostrin , Christie Hong, An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites, Proceedings of the International Conference on Software Maintenance, p.34, March 16-19, 1998
• 10: Alan George , Alex Pothen, An Analysis of Spectral Envelope Reduction via Quadratic Assignment Problems, SIAM Journal on Matrix Analysis and Applications, v.18 n.3, p.706-732, July 1997 [doi>10.1137/S089547989427470X]
• 11: Patrice Godefroid, Compositional dynamic test generation, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 12: Patrice Godefroid , Nils Klarlund , Koushik Sen, DART: directed automated random testing, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 13: M. Jean Harrold , Rajiv Gupta , Mary Lou Soffa, A methodology for controlling the size of a test suite, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.3, p.270-285, July 1993 [doi>10.1145/152388.152391]
• 14: Mary Jean Harrold , David Rosenblum , Gregg Rothermel , Elaine Weyuker, Empirical Studies of a Prediction Model for Regression Test Selection, IEEE Transactions on Software Engineering, v.27 n.3, p.248-263, March 2001 [doi>10.1109/32.910860]
• 15: Bruce Hendrickson , Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, v.16 n.2, p.452-469, March 1995 [doi>10.1137/0916028]
• 16: Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977 [doi>10.1145/322033.322044]
• 17: Steven Bradish Horton , R. Gary Parker, The optimal linear arrangement problem: algorithms and approximation, Georgia Institute of Technology, Atlanta, GA, 1997
• 18: Monica Hutchins , Herb Foster , Tarak Goradia , Thomas Ostrand, Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria, Proceedings of the 16th international conference on Software engineering, p.191-200, May 16-21, 1994, Sorrento, Italy
• 19: Dennis Jeffrey , Neelam Gupta, Test Suite Reduction with Selective Redundancy, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.549-558, September 25-30, 2005 [doi>10.1109/ICSM.2005.88]
• 20: James Law , Gregg Rothermel, Whole program Path-Based dynamic impact analysis, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 21: Ben Liblit , Mayur Naik , Alice X. Zheng , Alex Aiken , Michael I. Jordan, Scalable statistical bug isolation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 22: Benjamin Livshits , Thomas Zimmermann, DynaMine: finding common error patterns by mining software revision histories, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 23: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 24: http://www.matlab.com.
• 25: Bojan Mohar, Laplace eigenvalues of graphs—a survey, Discrete Mathematics, v.109 n.1-3, p.171-183, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90288-Q]
• 26: Alessandro Orso , Taweesup Apiwattanapong , Mary Jean Harrold, Leveraging field data for impact analysis and regression testing, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 27: Alessandro Orso , Nanjuan Shi , Mary Jean Harrold, Scaling regression testing to large software systems, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 28: Michael Rabin. Fingerprinting by Random Polynomials. Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981.
• 29: http://www.cs.cmu.edu/hakim/software/.
• 30: Murali Krishna Ramanathan , Ananth Grama , Suresh Jagannathan, Sieve: A Tool for Automatically Detecting Variations Across Program Versions, Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering, p.241-252, September 18-22, 2006 [doi>10.1109/ASE.2006.61]
• 31: Xiaoxia Ren , Fenil Shah , Frank Tip , Barbara G. Ryder , Ophelia Chesley, Chianti: a tool for change impact analysis of java programs, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 32: 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]
• 33: Amitabh Srivastava , Jay Thiagarajan, Effectively prioritizing tests in development environment, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 34: W. Eric Wong , Joseph R. Horgan , Saul London , Aditya P. Mathur, Effect of test set minimization on fault detection effectiveness, Proceedings of the 17th international conference on Software engineering, p.41-50, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225018]

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)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing
      D.2.9 Management
          Subjects: Software quality assurance (SQA)

Keywords:
program analysis, regression testing, test prioritization