Michael G. Epitropakis
Shin Yoo
ABSTRACT
The aim of test case prioritisation is to determine an ordering of test cases that maximises the likelihood of early fault revelation. Previous prioritisation techniques have tended to be single objective, for which the additional greedy algorithm is the current state-of-the-art. Unlike test suite minimisation, multi objective test case prioritisation has not been thoroughly evaluated. This paper presents an extensive empirical study of the effectiveness of multi objective test case prioritisation, evaluating it on multiple versions of five widely-used benchmark programs and a much larger real world system of over 1 million lines of code. The paper also presents a lossless coverage compaction algorithm that dramatically scales the performance of all algorithms studied by between 2 and 4 orders of magnitude, making prioritisation practical for even very demanding problems.
- CLOC: count lines of code. http://cloc.sourceforge.net.Google Scholar
- MySQL, Online Bug Repository. http://bugs.mysql.com/.Google Scholar
- SIR: Software-artifact Infrastructure Repository. http://sir.unl.edu/.Google Scholar
- The MySQL Test Framework, Version 2.0. http://bugs.mysql.com/.Google Scholar
- A. Arcuri and L. Briand. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Proceedings of the 33rd International Conference on Software Engineering, ICSE ’11, pages 1–10, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- R. Assi and W. Masri. Lossless reduction of execution profiles using a genetic algorithm. In Proceedings of the 7th IEEE International Conference on Software Testing, Verification and Validation Workshops, ICSTW 2014, pages 294–297, March 2014. Google ScholarDigital Library
- R. C. Bryce and C. J. Colbourn. Prioritized interaction testing for pair-wise coverage with seeding and constraints. Journal of Information and Software Technology, 48(10):960–970, 2006.Google ScholarCross Ref
- J. T. de Souza, C. L. Maia, F. G. de Freitas, and D. P. Coutinho. The human competitiveness of search based software engineering. In Proceedings of 2nd International Symposium on Search based Software Engineering (SSBSE 2010), pages 143–152, Benevento, Italy, 2010. IEEE Computer Society Press. Google ScholarDigital Library
- K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan. A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. In Proceedings of the Parallel Problem Solving from Nature Conference, pages 849–858. Springer, 2000. Google ScholarDigital Library
- H. Do, S. G. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering, 10(4):405–435, 2005. Google ScholarDigital Library
- H. Do, G. Rothermel, and A. Kinneer. Prioritizing junit test cases: An empirical assessment and cost-benefits analysis. Empirical Software Engineering, 11(1):33–70, 2006. Google ScholarDigital Library
- S. Elbaum, A. Malishevsky, and G. Rothermel. Test case prioritization: a family of empirical studies. IEEE Transactions on Software Engineering, 28(2):159–182, Feb 2002. Google ScholarDigital Library
- S. G. Elbaum, A. G. Malishevsky, and G. Rothermel. Prioritizing test cases for regression testing. In Proceedings of International Symposium on Software Testing and Analysis, pages 102–112, August 2000. Google ScholarDigital Library
- S. G. Elbaum, A. G. Malishevsky, and G. Rothermel. Incorporating varying test costs and fault severities into test case prioritization. In Proceedings of the International Conference on Software Engineering (ICSE 2001), pages 329–338. ACM Press, May 2001. Google ScholarDigital Library
- A. Finkelstein, M. Harman, S. A. Mansouri, J. Ren, and Y. Zhang. ”fairness analysis” in requirements assignments. In Proceedings of the 16th IEEE International Requirements Engineering Conference (RE ’08), Barcelona, Catalunya, Spain, September 2008. Google ScholarDigital Library
- D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989. Google ScholarDigital Library
- D. E. Goldberg and R. Lingle, Jr. Alleles loci and the traveling salesman problem. In Proceedings of the 1st International Conference on Genetic Algorithms, pages 154–159, Hillsdale, NJ, USA, 1985. L. Erlbaum Associates Inc. Google ScholarDigital Library
- R. Grissom and J. Kim. Effect Sizes for Research: A Broad Practical Approach. Lawrence Erlbaum Associates, Inc., Publishers., 2005.Google Scholar
- Q. Gu, B. Tang, and D. Chen. Optimal regression testing based on selective coverage of test requirements. In International Symposium on Parallel and Distributed Processing with Applications (ISPA 10), pages 419 – 426, Sept. 2010. Google ScholarDigital Library
- M. Harman. Making the case for MORTO: Multi Objective Regression Test Optimization. In Proceedings of the 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops, ICSTW ’11, pages 111–114, Washington, DC, USA, 2011. IEEE Computer Society. Google ScholarDigital Library
- D. Jeffrey and N. Gupta. Test suite reduction with selective redundancy. In Proceedings of the 21st IEEE International Conference on Software Maintenance 2005 (ICSM’05), pages 549–558. IEEE Computer Society Press, September 2005. Google ScholarDigital Library
- J.-M. Kim and A. Porter. A history-based test prioritization technique for regression testing in resource constrained environments. In Proceedings of the 24th International Conference on Software Engineering, pages 119–129. ACM Press, May 2002. Google ScholarDigital Library
- J. Knowles, L. Thiele, and E. Zitzler. A tutorial on the performance assessment of stochastic multiobjective optimizers. 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland, Feb. 2006. revised version.Google Scholar
- Z. Li, Y. Bian, R. Zhao, and J. Cheng. A fine-grained parallel multi-objective test case prioritization on gpu. In G. Ruhe and Y. Zhang, editors, Search Based Software Engineering, volume 8084 of Lecture Notes in Computer Science, pages 111–125. Springer Berlin Heidelberg, 2013.Google Scholar
- Z. Li, M. Harman, and R. M. Hierons. Search Algorithms for Regression Test Case Prioritization. IEEE Transactions on Software Engineering, 33(4):225–237, 2007. Google ScholarDigital Library
- 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.Google Scholar
- N. Nethercote and J. Seward. Valgrind: A program supervision framework. In Proceedings of ACM Conference on Programming Language Design and Implementation, pages 89–100. ACM Press, June 2007.Google Scholar
- Oracle Corporation. http://www.mysql.com.Google Scholar
- K. Praditwong and X. Yao. A new multi-objective evolutionary optimisation algorithm: The two-archive algorithm. In Proceedings of Computational Intelligence and Security, International Conference, volume 4456 of Lecture Notes in Computer Science, pages 95–104, November 2006.Google ScholarCross Ref
- G. Rothermel, S. Elbaum, A. Malishevsky, P. Kallakuri, and B. Davia. The impact of test suite granularity on the cost-effectiveness of regression testing. In Proceedings of the 24th International Conference on Software Engineering (ICSE 2002), pages 130–140. ACM Press, May 2002. Google ScholarDigital Library
- G. Rothermel, R. H. Untch, C. Chu, and M. J. Harrold. Test case prioritization: An empirical study. In Proceedings of International Conference on Software Maintenance (ICSM 1999), pages 179–188. IEEE Computer Society Press, August 1999. Google ScholarDigital Library
- G. Rothermel, R. J. Untch, and C. Chu. Prioritizing test cases for regression testing. IEEE Transactions on Software Engineering, 27(10):929–948, October 2001. Google ScholarDigital Library
- J. P. Royston. An extension of shapiro and wilk’s w test for normality to large samples. Journal of the Royal Statistical Society. Series C (Applied Statistics), 31(2):115–124, 1982.Google Scholar
- P. G. Sapna and M. Hrushikesha. Automated test scenario selection based on levenshtein distance. In T. Janowski and H. Mohanty, editors, 6th Distributed Computing and Internet Technology (ICDCIT’10), volume 5966 of Lecture Notes in Computer Science (LNCS), pages 255–266. Springer-Verlag (New York), Bhubaneswar, India, Feb. 2010. Google ScholarDigital Library
- A. Vargha and H. D. Delaney. A critique and improvement of the “CL” common language effect size statistics of McGraw and Wong. Journal of Educational and Behavioral Statistics, 25(2):pp. 101–132, 2000.Google Scholar
- D. A. V. Veldhuizen and G. B. Lamont. Multiobjective evolutionary algorithm research: A history and analysis. Technical Report TR-98-03, Department of Electrical and Computer Engineering, Air Force Institute of Technology, 1998.Google Scholar
- S. Yoo and M. Harman. Pareto efficient multi-objective test case selection. In Proceedings of International Symposium on Software Testing and Analysis, pages 140–150. ACM Press, July 2007. Google ScholarDigital Library
- S. Yoo and M. Harman. Using hybrid algorithm for pareto effcient multi-objective test suite minimisation. Journal of Systems Software, 83(4):689–701, April 2010. Google ScholarDigital Library
- S. Yoo and M. Harman. Regression testing minimisation, selection and prioritisation: A survey. Software Testing, Verification, and Reliability, 22(2):67–120, March 2012. Google ScholarDigital Library
- S. Yoo, M. Harman, P. Tonella, and A. Susi. Clustering test cases to achieve effective & scalable prioritisation incorporating expert knowledge. In Proceedings of International Symposium on Software Testing and Analysis (ISSTA 2009), pages 201–211. ACM Press, July 2009. Google ScholarDigital Library
- S. Yoo, M. Harman, and S. Ur. Highly scalable multi-objective test suite minimisation using graphics card. In LNCS: Proceedings of the 3rd International Symposium on Search-Based Software Engineering, volume 6956 of SSBSE, pages 219–236, September 2011. Google ScholarDigital Library
- S. Yoo, M. Harman, and S. Ur. Gpgpu test suite minimisation: search based software engineering performance improvement using graphics cards. Empirical Software Engineering, 18(3):550–593, 2013.Google ScholarCross Ref
- S. Yoo, R. Nilsson, and M. Harman. Faster fault finding at Google using multi objective regression test optimisation. In 8th European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE ’11), Szeged, Hungary, September 5th - 9th 2011.Google Scholar
- Industry Track.Google Scholar
- L. Zhang, S.-S. Hou, C. Guo, T. Xie, and H. Mei. Time-aware test-case prioritization using Integer Linear Programming. In Proceedings of the International Conference on Software Testing and Analysis (ISSTA 2009), pages 212–222. ACM Press, July 2009. Google ScholarDigital Library
- E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257–271, Nov. 1999. Google ScholarDigital Library
Index Terms
- Empirical evaluation of pareto efficient multi-objective regression test case prioritisation
Recommendations
Pareto efficient multi-objective test case selection
ISSTA '07: Proceedings of the 2007 international symposium on Software testing and analysisPrevious work has treated test case selection as a single objective optimisation problem. This paper introduces the concept of Pareto efficiency to test case selection. The Pareto efficient approach takes multiple objectives such as code coverage, past ...
Multi-objective test case prioritization for GUI applications
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied ComputingTest case prioritization techniques are proposed to schedule execution of test cases in order to improve testing effectiveness. Various coverage criteria are used as surrogates for test case prioritization. They are expected to improve testing ...
On the Use of Mutation Faults in Empirical Assessments of Test Case Prioritization Techniques
Regression testing is an important activity in the software life cycle, but it can also be very expensive. To reduce the cost of regression testing, software testers may prioritize their test cases so that those which are more important, by some measure,...
Comments