Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1273463.1273475acmconferencesArticle/Chapter ViewAbstractPublication PagesisstaConference Proceedingsconference-collections
Article

A theoretical & empirical analysis of evolutionary testing and hill climbing for structural test data generation

Published: 09 July 2007 Publication History

Abstract

Evolutionary testing has been widely studied as a technique for automating the process of test case generation. However, to date, there has been no theoretical examination of when and why it works. Furthermore, the empirical evidence for the effectiveness of evolutionary testing consists largely of small scale laboratory studies. This paper presents a first theoretical analysis of the scenarios in which evolutionary algorithms are suitable for structural test case generation. The theory is backed up by an empirical study that considers real world programs, the search spaces of which are several orders of magnitude larger than those previously considered.

References

[1]
The Software-artifact Infrastructure Repository, http://sir.unl.edu/portal/index.html.
[2]
J. E. Baker. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the 2nd International Conference on Genetic Algorithms and their Application, Hillsdale, New Jersey, USA, 1987. Lawrence Erlbaum Associates.
[3]
A. Baresel, D. Binkley, M. Harman, and B. Korel. Evolutionary testing in the presence of loop-assigned ags: A testability transformation approach. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA 2004), pages 43--52, Boston, Massachusetts, USA, 2004. ACM.
[4]
A. Baresel and H. Sthamer. Evolutionary testing of ag conditions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), volume 2724 of LNCS, pages 2442--2454, Chicago, 12-16 July 2003. Springer-Verlag.
[5]
A. Baresel, H. Sthamer, and M. Schmidt. Fitness function design to improve evolutionary structural testing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), pages 1329--1336, San Francisco, CA 94104, USA, 9-13 July 2002. Morgan Kaufmann Publishers.
[6]
L. Bottaci. Instrumenting programs with ag variables for test data search by genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), pages 1337--1342, New York, 9-13 July 2002. Morgan Kaufmann Publishers.
[7]
L. C. Briand, Y. Labiche, and M. Shousha. Stress testing real-time systems with genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005), Washington DC, USA, June 25-29, 2005, pages 1021--1028. ACM, 2005.
[8]
K. Derderian, R. Hierons, M. Harman, and Q. Guo. Automated Unique Input Output sequence generation for conformance testing of FSMs. The Computer Journal, 49(3):331--344, 2006.
[9]
H. Do, S. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering, 10(4):405--435, Oct. 2005.
[10]
M. Harman, L. Hu, R. Hierons, J. Wegener, H. Sthamer, A. Baresel, and M. Roper. Testability transformation. IEEE Transactions on Software Engineering, 30(1):3--16, 2004.
[11]
J. H. Holland. Adaption in Natural and Artificial Systems. MIT Press, Ann Arbor, 1975.
[12]
B. Korel. Automated software test data generation. IEEE Transactions on Software Engineering, 16(8):870--879, 1990.
[13]
N. Mansour and M. Salame. Data generation for path testing. Software Quality Journal, 12(2):121--134, 2004.
[14]
G. McGraw, C. Michael, and M. Schatz. Generating software test data by evolution. IEEE Transactions on Software Engineering, 27(12):1085--1110, 2001.
[15]
P. McMinn. Search-based software test data generation: A survey. Software Testing, Verification and Reliability, 14(2):105--156, 2004.
[16]
P. McMinn. IGUANA: Input generation using automated novel algorithms. A plug and play research tool. Technical Report, Department of Computer Science, University of Sheffield, 2007.
[17]
P. McMinn, M. Harman, D. Binkley, and P. Tonella. The species per path approach to search-based test data generation. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA 2006), pages 13--24, Portland, Maine, USA, 2006. ACM.
[18]
P. McMinn and M. Holcombe. Evolutionary testing using an extended chaining approach. Evolutionary Computation, 14:41--64, 2006.
[19]
W. Miller and D. Spooner. Automatic generation of oating-point test data. IEEE Transactions on Software Engineering, 2(3):223--226, 1976.
[20]
M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. In F. J. Varela and P. Bourgine, editors, Proceedings of the First European Conference on Artificial Life, pages 245--254, Cambridge, MA, 1992. MIT Press.
[21]
H. Mühlenbein and D. Schlierkamp-Voosen. Predictive models for the breeder genetic algorithm: I. continuous parameter optimization. Evolutionary Computation, 1(1):25--49, 1993.
[22]
R. Pargas, M. Harrold, and R. Peck. Test-data generation using genetic algorithms. Software Testing, Verification and Reliability, 9(4):263--282, 1999.
[23]
C. R. Reeves and J. E. Rowe. Genetic Algorithms - Principles and Perspectives, A Guide to GA Theory. Springer, 2002.
[24]
N. Tracey, J. Clark, and K. Mander. Automated program aw finding using simulated annealing. In International Symposium on Software Testing and Analysis (ISSTA 98), pages 73--81, March 1998.
[25]
H. -C. Wang and B. Jeng. Structural testing using memetic algorithm. In Proceedings of the Second Taiwan Conference on Software Engineering, Taipei, Taiwan, 2006.
[26]
J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Information and Software Technology, 43(14):841--854, 2001.
[27]
J. Wegener, H. Sthamer, B. F. Jones, and D. E. Eyres. Testing real-time systems using genetic algorithms. Software Quality, 6:127--135, 1997.
[28]
D. Whitley. The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In J. D. Schaffer, editor, Proceedings of the 3rd International Conference on Genetic Algorithms, pages 116--121, San Mateo, California, USA, 1989. Morgan Kaufmann.
[29]
S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas, and K. Karapoulios. Application of genetic algorithms to software testing (Application des algorithmes génétiques au test des logiciels). In 5th International Conference on Software Engineering and its Applications, pages 625--636, Toulouse, France, 1992.
[30]
M. Xiao, M. El-Attar, M. Reformat, and J. Miller. Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques. Empirical Software Engineering, 12(2):183--239, 2007.

Cited By

View all
  • (2024)Measuring Impact of Generative AI in Software Development and InnovationIntelligent IT Solutions for Sustainability in Industry 5.0 Paradigm10.1007/978-981-97-1682-1_6(57-67)Online publication date: 5-Jul-2024
  • (2023)An Approach of Improving the Efficiency of Software Fault Localization based on Feedback Ranking InformationApplied Sciences10.3390/app13181035113:18(10351)Online publication date: 15-Sep-2023
  • (2023)Instance Space Analysis of Search-Based Software TestingIEEE Transactions on Software Engineering10.1109/TSE.2022.322833449:4(2642-2660)Online publication date: 1-Apr-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ISSTA '07: Proceedings of the 2007 international symposium on Software testing and analysis
July 2007
258 pages
ISBN:9781595937346
DOI:10.1145/1273463
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

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. automated test data generation
  2. evolutionary testing
  3. genetic algorithms
  4. hill climbing
  5. royal road
  6. schema theory

Qualifiers

  • Article

Conference

ISSTA07
Sponsor:

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)1
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Measuring Impact of Generative AI in Software Development and InnovationIntelligent IT Solutions for Sustainability in Industry 5.0 Paradigm10.1007/978-981-97-1682-1_6(57-67)Online publication date: 5-Jul-2024
  • (2023)An Approach of Improving the Efficiency of Software Fault Localization based on Feedback Ranking InformationApplied Sciences10.3390/app13181035113:18(10351)Online publication date: 15-Sep-2023
  • (2023)Instance Space Analysis of Search-Based Software TestingIEEE Transactions on Software Engineering10.1109/TSE.2022.322833449:4(2642-2660)Online publication date: 1-Apr-2023
  • (2022)Comparison and Validation of Mutation Testing Tools Based on Java LanguageOptimization of Automated Software Testing Using Meta-Heuristic Techniques10.1007/978-3-031-07297-0_2(13-29)Online publication date: 27-Sep-2022
  • (2019)Testing extended finite state machines using NSGA-IIIProceedings of the 10th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation10.1145/3340433.3342820(1-7)Online publication date: 26-Aug-2019
  • (2019)Approximate Oracles and Synergy in Software Energy Search SpacesIEEE Transactions on Software Engineering10.1109/TSE.2018.282706645:11(1150-1169)Online publication date: 1-Nov-2019
  • (2019)Automatic Generation of Tests to Exploit XML Injection Vulnerabilities in Web ApplicationsIEEE Transactions on Software Engineering10.1109/TSE.2017.277871145:4(335-362)Online publication date: 1-Apr-2019
  • (2019)Search-based testing in membrane computingJournal of Membrane Computing10.1007/s41965-019-00027-w1:4(241-250)Online publication date: 2-Dec-2019
  • (2019)Empirical Study of Hybrid Optimization Strategy for Evolutionary TestingData Science10.1007/978-981-15-0121-0_3(41-53)Online publication date: 13-Sep-2019
  • (2018)Multi-trajectory Fitness Function-based Method of Automated Test Coverage for Code Using Evolutionary AlgorithmsMechanical Engineering and Computer Science10.24108/1018.0001434(30-40)Online publication date: 6-Dec-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media