Time-aware test-case prioritization using integer linear programming

ABSTRACT

Techniques for test-case prioritization re-order test cases to increase their rate of fault detection. When there is a fixed time budget that does not allow the execution of all the test cases, time-aware techniques for test-case prioritization may achieve a better rate of fault detection than traditional techniques for test-case prioritization. In this paper, we propose a novel approach to time-aware test-case prioritization using integer linear programming. To evaluate our approach, we performed experiments on two subject programs involving four techniques for our approach, two techniques for an approach to time-aware test-case prioritization based on genetic algorithms, and four traditional techniques for test-case prioritization. The empirical results indicate that two of our techniques outperform all the other techniques for the two subjects under the scenarios of both general and version-specific prioritization. The empirical results also indicate that some traditional techniques with lower analysis time cost for test-case prioritization may still perform competitively when the time budget is not quite tight.

REFERENCES

• 1: Sara Alspaugh , Kristen R. Walcott , Michael Belanich , Gregory M. Kapfhammer , Mary Lou Soffa, Efficient time-aware prioritization with knapsack solvers, Proceedings of the 1st ACM international workshop on Empirical assessment of software engineering languages and technologies: held in conjunction with the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE) 2007, p.13-18, November 05-05, 2007, Atlanta, Georgia [doi>10.1145/1353673.1353676]
• 2: J. H. Andrews , L. C. Briand , Y. Labiche, Is mutation an appropriate tool for testing experiments?, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062530]
• 3: Thomas Ball, On the limit of control flow analysis for regression test selection, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.134-142, March 02-04, 1998, Clearwater Beach, Florida, United States
• 4: David Binkley, Semantics Guided Regression Test Cost Reduction, IEEE Transactions on Software Engineering, v.23 n.8, p.498-516, August 1997 [doi>10.1109/32.624306]
• 5: Jennifer Black , Emanuel Melachrinoudis , David Kaeli, Bi-Criteria Models for All-Uses Test Suite Reduction, Proceedings of the 26th International Conference on Software Engineering, p.106-115, May 23-28, 2004
• 6: T. Y. Chen and M. F. Lau. A new heuristic for test suite reduction. IST, 40(5-6):347--354, 1998.
• 7: Yih-Farn Chen , David S. Rosenblum , Kiem-Phong Vo, TestTube: a system for selective regression testing, Proceedings of the 16th international conference on Software engineering, p.211-220, May 16-21, 1994, Sorrento, Italy
• 8: Hyunsook Do , Siavash Mirarab , Ladan Tahvildari , Gregg Rothermel, An empirical study of the effect of time constraints on the cost-benefits of regression testing, Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, November 09-14, 2008, Atlanta, Georgia [doi>10.1145/1453101.1453113]
• 9: 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]
• 10: Hyunsook Do , Gregg Rothermel , Alex Kinneer, Empirical Studies of Test Case Prioritization in a JUnit Testing Environment, Proceedings of the 15th International Symposium on Software Reliability Engineering, p.113-124, November 02-05, 2004 [doi>10.1109/ISSRE.2004.18]
• 11: 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
• 12: 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
• 13: 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]
• 14: 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]
• 15: S. Hou, L. Zhang, T. Xie, and J. Sun. Quota-constrained test-case prioritization for regression testing of service-centric systems. In Proc. ICSM, pages 257--266, 2008.
• 16: James A. Jones , Mary Jean Harrold, Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage, IEEE Transactions on Software Engineering, v.29 n.3, p.195-209, March 2003 [doi>10.1109/TSE.2003.1183927]
• 17: Jung-Min Kim , Adam Porter, A history-based test prioritization technique for regression testing in resource constrained environments, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581357]
• 18: B. Korel, G. Koutsogiannakis, and L. Tahat. Application of system models in regression test suite prioritization. In Proc. ICSM, pages 247--256, 2008.
• 19: Bogdan Korel , Luay H. Tahat , Mark Harman, Test Prioritization Using System Models, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.559-568, September 25-30, 2005 [doi>10.1109/ICSM.2005.87]
• 20: H. Leung and L. White. A study of integration testing and software regression at the integration level. In Proc. ICSM, pages 290--300, 1990.
• 21: 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]
• 22: S. Lin. Computer solutions of the travelling salesman problem. Bell System Technical Journal, 44(5):2245--2269, 1965.
• 23: A. Malishevsky, J. R. Ruthru, G. Rothermel, and S. Elbaum. Cost-cognizant test case prioritization. Technical report, Department Computer Science and Engineering of University of Nebraska, 2006.
• 24: Nashat Mansour , Khalid El-Fakih, Simulated annealing and genetic algorithms for optimal regression testing, Journal of Software Maintenance: Research and Practice, v.11 n.1, p.19-34, Jan.-Feb. 1999 [doi>10.1002/(SICI)1096-908X(199901/02)11:1<19::AID-SMR182>3.0.CO;2-M]
• 25: I. Moore. Jester-a JUnit test tester. In Proc. International Conference on Extreme Programming and Flexible Processes, pages 84--87, 2001.
• 26: A. Jefferson Offutt , Gregg Rothermel , Christian Zapf, An experimental evaluation of selective mutation, Proceedings of the 15th international conference on Software Engineering, p.100-107, May 17-21, 1993, Baltimore, Maryland, United States
• 27: Hyuncheol Park , Hoyeon Ryu , Jongmoon Baik, Historical Value-Based Approach for Cost-Cognizant Test Case Prioritization to Improve the Effectiveness of Regression Testing, Proceedings of the 2008 Second International Conference on Secure System Integration and Reliability Improvement, p.39-46, July 14-17, 2008 [doi>10.1109/SSIRI.2008.52]
• 28: Xiao Qu , Myra B. Cohen , Gregg Rothermel, Configuration-aware regression testing: an empirical study of sampling and prioritization, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA [doi>10.1145/1390630.1390641]
• 29: T. Ralphs and M. Guzelsoy. The SYMPHONY callable library for mixed integer programming. In Proc. INFORMS Computing Society Conference, pages 61--73, 2005.
• 30: Colin R. Reeves, Modern heuristic techniques for combinatorial problems, John Wiley & Sons, Inc., New York, NY, 1993
• 31: Gregg Rothermel , Mary Jean Harrold, A safe, efficient regression test selection technique, ACM Transactions on Software Engineering and Methodology (TOSEM), v.6 n.2, p.173-210, April 1997 [doi>10.1145/248233.248262]
• 32: 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
• 33: 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]
• 34: 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
• 35: 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]
• 36: H. Williams. Model Building in Mathematical Programming. John Wiley, New York, 1993.
• 37: W. Eric Wong , Joseph R. Horgan , Saul London , Hira Agrawal Bellcore, A Study of Effective Regression Testing in Practice, Proceedings of the Eighth International Symposium on Software Reliability Engineering, p.264, November 02-05, 1997
• 38: Shin Yoo , Mark Harman, Pareto efficient multi-objective test case selection, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273483]
• 39: Hao Zhong , Lu Zhang , Hong Mei, An experimental study of four typical test suite reduction techniques, Information and Software Technology, v.50 n.6, p.534-546, May, 2008 [doi>10.1016/j.infsof.2007.06.003]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Experimentation, Measurement, Performance

Keywords:
integer linear programming, test-case prioritization