research-article

Insight knowledge in search based software testing

Author:

Andrea ArcuriAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 1649 - 1656

https://doi.org/10.1145/1569901.1570122

Published: 08 July 2009 Publication History

Abstract

Software testing can be re-formulated as a search problem, hence search algorithms (e.g., Genetic Algorithms) can be used to tackle it. Most of the research so far has been of empirical nature, in which novel proposed techniques have been validated on software testing benchmarks. However, only little attention has been spent to understand why meta-heuristics can be effective in software testing. This insight knowledge could be used to design novel more successful techniques. Recent theoretical work has tried to fill this gap, but it is very complex to carry out. This has limited its scope so far to only small problems. In this paper, we want to get insight knowledge on a difficult software testing problem. We combine together an empirical and theoretical analysis, and we exploit the benefits of both.

References

[1]

A. Arcuri. Full theoretical runtime analysis of alternating variable method on the triangle classification problem. In International Symposium on Search Based Software Engineering (SSBSE), 2009. (to appear).

Digital Library

[2]

A. Arcuri, P.K. Lehre, and X. Yao. Theoretical runtime analyses of search algorithms on the test data generation for the triangle classification problem. In International Workshop on Search-Based Software Testing (SBST), pages 161--169, 2008.

Digital Library

[3]

A. Arcuri and X. Yao. Search based software testing of object-oriented containers. Information Sciences, 178(15):3075--3095, 2008.

Digital Library

[4]

B. Beizer. Software Testing Techniques. Van Nostrand Rheinhold, New York, 1990.

Digital Library

[5]

T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press and McGraw-Hill, second edition, 2001.

Digital Library

[6]

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.

Digital Library

[7]

M. Harman and P. McMinn. A theoretical&empirical analysis of evolutionary testing and hill climbing for structural test data generation. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), pages 73--83, 2007.

Digital Library

[8]

J.H. Holland. Adaptation in Natural and Artificial Systems, second edition. MIT Press, Cambridge, 1992.

Digital Library

[9]

K. Inkumsah and T. Xie. Improving structural testing of object-oriented programs via integrating evolutionary testing and symbolic execution. In IEEE International Conference on Automated Software Engineering (ASE), pages 297--306, 2008.

Digital Library

[10]

T. Jansen, K.A.D. Jong, and I.A. Wegener. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation, 13(4):413--440, 2005.

Digital Library

[11]

P. Lehre and X. Yao. Crossover can be constructive when computing unique input output sequences. In Proceedings of the International Conference on Simulated Evolution and Learning (SEAL), pages 595--604, 2008.

Digital Library

[12]

P.K. Lehre and X. Yao. Runtime analysis of (1+1) ea on computing unique input output sequences. In IEEE Congress on Evolutionary Computation (CEC), pages 1882--1889, 2007.

[13]

P. McMinn. Search-based software test data generation: A survey. Software Testing, Verification and Reliability, 14(2):105--156, June 2004.

Digital Library

[14]

P. McMinn and D. Binkley. Testability transformation for efficient automated test data search in the presence of nesting. In Proceedings of the Third UK Software Testing Workshop, pages 165--182, 2005.

[15]

M. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[16]

P.S. Oliveto, J. He, and X. Yao. Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4(3):281--293, 2007.

[17]

W. Visser, C.S. Pasareanu, and R. Pelànek. Test input generation for java containers using state matching. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), pages 37--48, 2006.

Digital Library

[18]

D. Whitley. The genitor algorithm and selective pressure: Why rank-based allocation of reproductive trials is best. In Proceedings of the Third International Conference on Genetic Algorithms (ICGA-89), pages 116--121, 1989.

Digital Library

[19]

C. Witt. Runtime analysis of the (¼+1) ea on simple pseudo-boolean functions. Evolutionary Computation, 14(1):65--86, 2006.

Digital Library

Cited By

Zhang MArcuri A(2023)Open Problems in Fuzzing RESTful APIs: A Comparison of ToolsACM Transactions on Software Engineering and Methodology10.1145/359720532:6(1-45)Online publication date: 30-Sep-2023
https://dl.acm.org/doi/10.1145/3597205
Neelofar NSmith-Miles KMuñoz MAleti A(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
https://doi.org/10.1109/TSE.2022.3228334
Mayan JRavi TRangan PJayaraman B(2014)Test Case Optimization Using Hybrid Search TechniqueProceedings of the 2014 International Conference on Interdisciplinary Advances in Applied Computing10.1145/2660859.2660906(1-7)Online publication date: 10-Oct-2014
https://dl.acm.org/doi/10.1145/2660859.2660906
Show More Cited By

Index Terms

Insight knowledge in search based software testing

Recommendations

A Theoretical and Empirical Analysis of the Role of Test Sequence Length in Software Testing for Structural Coverage

In the presence of an internal state, often a sequence of function calls is required to test software. In fact, to cover a particular branch of the code, a sequence of previous function calls might be required to put the internal state in the ...
Predicting software complexity by means of evolutionary testing
ASE '12: Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering

One characteristic that impedes software from achieving good levels of maintainability is the increasing complexity of software. Empirical observations have shown that typically, the more complex the software is, the bigger the test suite is. Thence, a ...
An extensive evaluation of search-based software testing: a review

In recent years, search-based software testing (SBST) is the active research topic in software testing. SBST is the process of generating test cases that use metaheuristics for optimization of a task in the framework of software testing to solve ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

Copyright © 2009 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
307
Total Downloads

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

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang MArcuri A(2023)Open Problems in Fuzzing RESTful APIs: A Comparison of ToolsACM Transactions on Software Engineering and Methodology10.1145/359720532:6(1-45)Online publication date: 30-Sep-2023
https://dl.acm.org/doi/10.1145/3597205
Neelofar NSmith-Miles KMuñoz MAleti A(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
https://doi.org/10.1109/TSE.2022.3228334
Mayan JRavi TRangan PJayaraman B(2014)Test Case Optimization Using Hybrid Search TechniqueProceedings of the 2014 International Conference on Interdisciplinary Advances in Applied Computing10.1145/2660859.2660906(1-7)Online publication date: 10-Oct-2014
https://dl.acm.org/doi/10.1145/2660859.2660906
Arcuri A(2012)A Theoretical and Empirical Analysis of the Role of Test Sequence Length in Software Testing for Structural CoverageIEEE Transactions on Software Engineering10.1109/TSE.2011.4438:3(497-519)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1109/TSE.2011.44
Fraser GArcuri A(2012)The Seed is StrongProceedings of the 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation10.1109/ICST.2012.92(121-130)Online publication date: 17-Apr-2012
https://dl.acm.org/doi/10.1109/ICST.2012.92
Sharma RGligoric MArcuri AFraser GMarinov D(2011)Testing container classesProceedings of the 14th international conference on Fundamental approaches to software engineering: part of the joint European conferences on theory and practice of software10.5555/1987434.1987460(262-277)Online publication date: 26-Mar-2011
https://dl.acm.org/doi/10.5555/1987434.1987460
Sharma RGligoric MArcuri AFraser GMarinov D(2011)Testing Container Classes: Random or Systematic?Fundamental Approaches to Software Engineering10.1007/978-3-642-19811-3_19(262-277)Online publication date: 2011
https://doi.org/10.1007/978-3-642-19811-3_19
Arcuri A(2011)It really does matter how you normalize the branch distance in search‐based software testingSoftware Testing, Verification and Reliability10.1002/stvr.45723:2(119-147)Online publication date: 23-Mar-2011
https://doi.org/10.1002/stvr.457
Arcuri A(2010)Longer is BetterProceedings of the 2010 Third International Conference on Software Testing, Verification and Validation10.1109/ICST.2010.16(469-478)Online publication date: 6-Apr-2010
https://dl.acm.org/doi/10.1109/ICST.2010.16
Ribeiro JZenha-Rela MFernández de Vega F(2010)Enabling object reuse on genetic programming-based approaches to object-oriented evolutionary testingProceedings of the 13th European conference on Genetic Programming10.1007/978-3-642-12148-7_19(220-231)Online publication date: 7-Apr-2010
https://dl.acm.org/doi/10.1007/978-3-642-12148-7_19
Show More Cited By

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents