research-article

Empirically studying the role of selection operators duringsearch-based test suite prioritization

Authors:

Alexander P. Conrad,

Robert S. Roos,

Gregory M. KapfhammerAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 1373 - 1380

https://doi.org/10.1145/1830483.1830735

Published: 07 July 2010 Publication History

Abstract

Regression test suite prioritization techniques reorder test cases so that, on average, more faults will be revealed earlier in the test suite's execution than would otherwise be possible. This paper presents a genetic algorithm-based test prioritization method that employs a wide variety of mutation, crossover, selection, and transformation operators to reorder a test suite. Leveraging statistical analysis techniques, such as tree model construction through binary recursive partitioning and kernel density estimation, the paper's empirical results highlight the unique role that the selection operators play in identifying an effective ordering of a test suite. The study also reveals that, while truncation selection consistently outperformed the tournament and roulette operators in terms of test suite effectiveness, increasing selection pressure consistently produces the best results within each class of operator. After further explicating the relationship between selection intensity, termination condition, fitness landscape, and the quality of the resulting test suite, this paper demonstrates that the genetic algorithm-based prioritizer is superior to random search and hill climbing and thus suitable for many regression testing environments.

References

[1]

T. Blickle and L. Thiele. A comparison of selection schemes used in evolutionary algorithms. Evol. Comp., 4, 1997.

Digital Library

[2]

L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Chapman and Hall/CRC, 1998.

[3]

E. Cantu-Paz. Efficient and Accurate Paral lel Genetic Algorithms. Kluwer Academic Publishers, 2000.

Digital Library

[4]

J. Clarke, J. J. Dolado, M. Harman, R. Hierons, B. Jones, M. Lumkin, B. Mitchell, K. Rees, and M. Roper. Reformulating software engineering as a search problem. Proc. Softw., 150, 2003.

[5]

M. J. Crawley. The R Book. John Wiley & Sons, Inc., 2007.

Digital Library

[6]

R. Durstenfeld. Algorithm 235: Random permutation. Commun. of the ACM, 7(7), 1964.

Digital Library

[7]

S. Elbaum, A. Malishevsky, and G. Rothermel. Test case prioritization: A family of empirical studies. Trans. on Softw. Eng., 28(2), 2002.

Digital Library

[8]

P. G. Frankl and S. N. Weiss. An experimental comparison of the effectiveness of branch testing and data flow testing. Trans. on Softw. Eng., 19(8):774--787, 1993.

Digital Library

[9]

M. Harman and J. Clark. Metrics are fitness functions too. In METRICS, 2004.

Digital Library

[10]

P. Kampstra. Beanplot: A boxplot alternative for visual comparison of distributions. Journ. of Stat. Softw., Code Snippets, 28(1), 10 2008.

[11]

G. M. Kapfhammer and M. L. Soffa. Database-aware test coverage monitoring. In ISEC, 2008.

Digital Library

[12]

P. Larranaga, C. M. H. Kuijpers, R. Murga, I. Inza, and S. Dizdarevic. Genetic algorithms for the travelling salesman problem: A review of representations and operators. Art. Intel l. Rev., 13, 1999.

Digital Library

[13]

J. Lässig, K. H. Hoffmann, and M. Enachescu. Threshold a selecting: best possible probability distribution for crossover selection in genetic algorithms. In GECCO, 2008.

Digital Library

[14]

Z. Li, M. Harman, and R. M. Hierons. Search algorithms for regression test case prioritization. Trans. on Softw. Eng., 33(4), 2007.

Digital Library

[15]

C. F. Lima, F. G. Lobo, and M. Pelikan. From mating pool distributions to model overfitting. In GECCO, 2008.

Digital Library

[16]

A. G. Malishevsky, J. Ruthruff, G. Rothermel, and S. Elbaum. Cost-cognizant test case prioritization. Technical Report TR-UNL-CSE-2006-0004, University of Nebraska - Lincoln, 2006.

[17]

S. McMaster and A. Memon. Call stack coverage for GUI test-suite reduction. In ISSRE, 2006.

Digital Library

[18]

S. McMaster and A. M. Memon. Call stack coverage for test suite reduction. In ICSM, 2005.

Digital Library

[19]

S. McMaster and A. M. Memon. Fault detection probability analysis for coverage-based test suite reduction. In ICSM, 2007.

[20]

B. L. Miller and D. E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Compl. Sys., 9, 1995.

[21]

J. Misurda, J. A. Clause, J. L. Reed, B. R. Childers, and M. L. Soffa. Demand-driven structural testing with dynamic instrumentation. In ICSE, 2005.

Digital Library

[22]

A. S. Namin and J. H. Andrews. The influence of size and coverage on test suite effectiveness. In ISSTA, 2009.

Digital Library

[23]

X. Qu, M. B. Cohen, and G. Rothermel. Configuration-aware regression testing: an empirical study of sampling and prioritization. In ISSTA, 2008.

Digital Library

[24]

D. S. Rosenblum and E. J. Weyuker. Using coverage information to predict the cost-effectiveness of regression testing strategies. Trans. on Soft. Eng., 23(3), 1997.

Digital Library

[25]

A. M. Smith and G. M. Kapfhammer. An empirical study of incorporating cost into test suite reduction and prioritization. In SAC, 2009.

Digital Library

[26]

C. Strobl, A.-L. Boulesteix, A. Zeileis, and T. Hothorn. Bias in random forest variable importance measures: Illustrations, sources and a solution. BMC Bioinf., 8, 2007.

[27]

N. J. Wahl. An overview of regression testing. SIGSOFT Softw. Eng. Notes, 24(1), 1999.

Digital Library

[28]

K. R. Walcott, M. L. Soffa, G. M. Kapfhammer, and R. S. Roos. Time-aware test suite prioritization. In ISSTA, 2006. v

Digital Library

[29]

S. Yoo, M. Harman, P. Tonella, and A. Susi. Clustering test cases to achieve effective and scalable prioritisation incorporating expert knowledge. In ISSTA, 2009.

Digital Library

[30]

S. Yoo, M. Harman, and S. Ur. Measuring and improving latency to avoid test suite wear out. In SBST, 2009.

Digital Library

[31]

J. Zhong, X. Hu, J. Zhang, and M. Gu. Comparison of performance between different selection strategies on simple genetic algorithms. In CIMCA, volume 2, 2005.

Digital Library

[32]

H. Zhu, P. A. V. Hall, and J. H. R. May. Software unit test coverage and adequacy. Comput. Surv., 29(4), 1997.

Digital Library

[33]

B. Zorman, G. M. Kapfhammer, and R. S. Roos. Creation and analysis of a JavaSpace-based genetic algorithm. In PDPTA, 2002

Digital Library

Cited By

Singh ASinghrova ABhatia RRattan D(2023)A Systematic Literature Review on Test Case Prioritization TechniquesAgile Software Development10.1002/9781119896838.ch7(101-159)Online publication date: 8-Feb-2023
https://doi.org/10.1002/9781119896838.ch7
Bajaj ASangwan O(2019)A Systematic Literature Review of Test Case Prioritization Using Genetic AlgorithmsIEEE Access10.1109/ACCESS.2019.29382607(126355-126375)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2938260
Mukherjee RPatnaik K(2019)Prioritizing JUnit Test Cases Without Coverage Information: An Optimization Heuristics Based ApproachIEEE Access10.1109/ACCESS.2019.29223877(78092-78107)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2922387
Show More Cited By

Index Terms

Empirically studying the role of selection operators duringsearch-based test suite prioritization

Recommendations

TimeAware test suite prioritization
ISSTA '06: Proceedings of the 2006 international symposium on Software testing and analysis

Regression test prioritization is often performed in a time constrained execution environment in which testing only occurs for a fixed time period. For example, many organizations rely upon nightly building and regression testing of their applications ...
Faster mutation testing inspired by test prioritization and reduction
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and Analysis

Mutation testing is a well-known but costly approach for determining test adequacy. The central idea behind the approach is to generate mutants, which are small syntactic transformations of the program under test, and then to measure for a given test ...
Experimental Comparison of Code-Based and Model-Based Test Prioritization
ICSTW '09: Proceedings of the IEEE International Conference on Software Testing, Verification, and Validation Workshops

During regression testing, a modified system needs to beretested using the existing test suite. Since test suites may be very large, developers are interested in detecting faults in the system as early as possible. Test prioritization orders test cases ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
212
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Singh ASinghrova ABhatia RRattan D(2023)A Systematic Literature Review on Test Case Prioritization TechniquesAgile Software Development10.1002/9781119896838.ch7(101-159)Online publication date: 8-Feb-2023
https://doi.org/10.1002/9781119896838.ch7
Bajaj ASangwan O(2019)A Systematic Literature Review of Test Case Prioritization Using Genetic AlgorithmsIEEE Access10.1109/ACCESS.2019.29382607(126355-126375)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2938260
Mukherjee RPatnaik K(2019)Prioritizing JUnit Test Cases Without Coverage Information: An Optimization Heuristics Based ApproachIEEE Access10.1109/ACCESS.2019.29223877(78092-78107)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2922387
Paterson DKapfhammer GFraser GMcMinn PBai XLi JUlrich A(2018)Using controlled numbers of real faults and mutants to empirically evaluate coverage-based test case prioritizationProceedings of the 13th International Workshop on Automation of Software Test10.1145/3194733.3194735(57-63)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3194733.3194735
Kanugo GKaur SKhullar V(2018)Enhanced Test Case Prioritization Technique Based on Fix-and-Reschedule Adaptive Approach and Genetic Algorithm2018 4th International Conference for Convergence in Technology (I2CT)10.1109/I2CT42659.2018.9057830(1-5)Online publication date: Oct-2018
https://doi.org/10.1109/I2CT42659.2018.9057830
Lachmann RFelderer MNieke MSchulze SSeidl CSchaefer IBosman P(2017)Multi-objective black-box test case selection for system testingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071189(1311-1318)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071189
Kamna Solanki Yudhvir Singh Sandeep Dalal Srivastava P(2016)Test Case Prioritization: An Approach Based on Modified Ant Colony OptimizationEmerging Research in Computing, Information, Communication and Applications10.1007/978-981-10-0287-8_19(213-223)Online publication date: 10-May-2016
https://doi.org/10.1007/978-981-10-0287-8_19
Sultan ABaharom SGhani ADin JZulzalil H(2015)Genetic Algorithm Application for Enhancing State-Sensitivity PartitioningProceedings of the 27th IFIP WG 6.1 International Conference on Testing Software and Systems - Volume 944710.1007/978-3-319-25945-1_16(249-256)Online publication date: 23-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-25945-1_16
Catal CZhang HYang YBabar M(2012)On the application of genetic algorithms for test case prioritizationProceedings of the 2nd international workshop on Evidential assessment of software technologies10.1145/2372233.2372238(9-14)Online publication date: 22-Sep-2012
https://dl.acm.org/doi/10.1145/2372233.2372238
Williams ZKapfhammer GPelikan MBranke J(2010)Using synthetic test suites to empirically compare search-based and greedy prioritizersProceedings of the 12th annual conference companion on Genetic and evolutionary computation10.1145/1830761.1830891(2119-2120)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830761.1830891
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten