research-article

Fitness calculation approach for the switch-case construct in evolutionary testing

Authors:

Xiyang LiuAuthors Info & Claims

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

Pages 1767 - 1774

https://doi.org/10.1145/1389095.1389436

Published: 12 July 2008 Publication History

Abstract

A well-designed fitness function is essential to the effectiveness and efficiency of evolutionary testing. Fitness function design has been researched extensively. For fitness calculation, so far the switchcase construct has been regarded as a nested if-else structure with respect to the control flow. Given a target embraced in a case branch, test data taking different case branches receive different approximation levels. Since the approximation levels received by test data do not evaluate their suitability accurately, the guidance provided by the existing approach to evolutionary search is misleading or lost. Despite the switch-case construct.s wide use in industrial applications, no previous work has addressed this problem.

In this paper, a Flattened Control Flow Graph and a Flattened Control Dependence Graph for the switch-case construct are first presented, and a unified fitness calculation approach based on Alternative Critical Branches is proposed for the switch-case and other constructs. The concept of Alternative Critical Branches is extended from the single critical branch. Experiments on several large-scale open source programs demonstrate that this approach contributes a much better guidance to evolutionary search.

References

[1]

M. Harman, K. Lakhotia, and P. McMinn. A multi-objective approach to search-based test data generation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'07), pp.1098--1105, London, England, 2007

Digital Library

[2]

M. Harman and P. McMinn. A Theoretical & Empirical Analysis of Evolutionary Testingand Hill Climbing for Structural Test Data Generation. In International Symposium on Software Testing and Analysis(ISSTA'07), to appear, 2007.

Digital Library

[3]

K. Derderian, R. Hierons, M. Harman, and Q. Guo. Automated Unique Input Output sequence generation for conformance testing of FSMs. In The Computer Journal, 49(3):331--344, 2006.

Digital Library

[4]

C. C. Michael, G. McGraw, and M. A. Schatz. Generating software test data by evolution. IEEE Transactions on Software Engineering, 27(12):1085--1110, 2001.

Digital Library

[5]

L. Briand, Y. Labiche, and M. Shousha. Stress testing real-time systems with genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'05), pp.1021--1028, Washington, USA, 2005.

Digital Library

[6]

J. Clarke, J. J.Dolado, M. Harman, R. Hierons, B. Jones, M. Lumkin, B. Mitchell, S. Mancoridis, K. Rees, M. Roper, and M. Shepperd. Reformulating software engineering as a search problem. In IEE Proceedings - Software, 5(1):161--175, June 2003.

[7]

J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. In Information and Software Technology, 43(14):841--854, December 2001.

[8]

X. Liu, H. Liu, B. Wang, P. Chen, and X. Cai. A unified fitness function calculation rule for flag conditions to improve evolutionary testing. In Proceedings of the International Conference on Automated Software Engineering (ASE'05), pp.337--341, California,USA, November 2005.

Digital Library

[9]

N. Tracey, J. Clark, and K. Mander. Automated program flaw finding using simulated annealing. In International Symposium on Software Testing and Analysis (ISSTA'98), pp.73--81, Florida, USA, 1998.

Digital Library

[10]

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'02), pp.1329--1336. New York, USA, July 2002.

Digital Library

[11]

J. Ferrante, K. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. In ACM Transactions on Programming Languages and Systems, 9(3):319--349, 1987.

Digital Library

[12]

P. McMinn and M. Holcombe. Hybridizing evolutionary testing with the chaining approach. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'04), pp.1363--1374. Seattle, USA, June 2004.

[13]

R. Ferguson and B. Korel. The chaining approach for software test data generation. In ACM Transactions on Software Engineering and Methodology, 150(3):63--86, January 1996.

Digital Library

[14]

P. McMinn and M. Holcombe. Evolutionary testing of state-based programs. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'05), pp.1013--1020. Washington DC, USA, June 2005.

Digital Library

[15]

P. McMinn. Search-based software test data generation: A survey. In Software Testing, Verification and Reliability, pp.105--156, 2004.

Digital Library

[16]

M. Harman, L. Hu, R. Hierons, A. Baresel, and H. Sthamer. Improving evolutionary testing by flag removal. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'02), pp.1351--1358. New York, USA, 2002.

Digital Library

[17]

P. McMinn, D. Binkley, and M. Harman. Testability Transformation for Efficient Automated Test Data Search in the Presence of Nesting. In Proceedings of the Third UK Software Testing Workshop,pp.165--182, UK, 2005.

[18]

T. Parr. ANTLR - ANother Tool for Language Recognition. http://antlr.org/.

[19]

Mark Harman, Lin Hu, Rob Hierons, Joachim Wegener, Harmen Sthamer, Andre Baresel, and Marc Roper. Testability Transformation. In IEEE Transactions on Software Engineering. 30(1): 3--16, 2004.

Digital Library

[20]

W. Miller and D. Spooner. Automatic generation of floating-point test data. In IEEE Transactions on Software Engineering. 2(3):223--226, 1976.

Digital Library

[21]

S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas, and K. Karapoulios. Application of genetic algorithms to software testing. In In International Conference on Software Engineering and its Applications. pp.625--636, Toulouse, France, 1992.

Cited By

Mayandi GArumugam C(2014)Parallelized genetic operations for SBST using Hadoop MapReduce framework2014 IEEE International Conference on Advanced Communications, Control and Computing Technologies10.1109/ICACCCT.2014.7019396(1686-1691)Online publication date: May-2014
https://doi.org/10.1109/ICACCCT.2014.7019396
Pachauri ASrivastava G(2013)Automated test data generation for branch testing using genetic algorithmJournal of Systems and Software10.1016/j.jss.2012.11.04586:5(1191-1208)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.jss.2012.11.045
Ghiduk A(2009)Search-Based Testing Guidance Using Dominances vs. Control DependenciesProceedings of the 2009 16th Asia-Pacific Software Engineering Conference10.1109/APSEC.2009.13(145-151)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/APSEC.2009.13

Index Terms

Fitness calculation approach for the switch-case construct in evolutionary testing
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Fitness calculation approach for nested if-else construct in evolutionary testing
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

This poster paper addresses the fitness calculation problem fornested if-else constructs. A new term "optimism level" is incorporated into the fitness function to assess the branch distance of nested branches for a given test data.
A specification-based fitness function for evolutionary testing of object-oriented programs
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Encapsulation of states in object-oriented programs hinders the search for test data using evolutionary testing. As client code is oblivious to the internal state of a server object, no guidance is available to test the client code using evolutionary ...
A unified fitness function calculation rule for flag conditions to improve evolutionary testing
ASE '05: Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering

Evolutionary testing (ET), automatically generating test data with good quality, is an effective technique based on evolutionary algorithm. However, the presence of flag variables will make it degenerate to random testing in structural testing. Much of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 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: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
204
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mayandi GArumugam C(2014)Parallelized genetic operations for SBST using Hadoop MapReduce framework2014 IEEE International Conference on Advanced Communications, Control and Computing Technologies10.1109/ICACCCT.2014.7019396(1686-1691)Online publication date: May-2014
https://doi.org/10.1109/ICACCCT.2014.7019396
Pachauri ASrivastava G(2013)Automated test data generation for branch testing using genetic algorithmJournal of Systems and Software10.1016/j.jss.2012.11.04586:5(1191-1208)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.jss.2012.11.045
Ghiduk A(2009)Search-Based Testing Guidance Using Dominances vs. Control DependenciesProceedings of the 2009 16th Asia-Pacific Software Engineering Conference10.1109/APSEC.2009.13(145-151)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/APSEC.2009.13

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