More Web Proxy on the site http://driver.im/

research-article

A theoretical runtime and empirical analysis of different alternating variable searches for search-based testing

Authors:

Dirk SudholtAuthors Info & Claims

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Pages 1445 - 1452

https://doi.org/10.1145/2463372.2463549

Published: 06 July 2013 Publication History

Abstract

The Alternating Variable Method (AVM) has been shown to be a surprisingly effective and efficient means of generating branch-covering inputs for procedural programs. However, there has been little work that has sought to analyse the technique and further improve its performance. This paper proposes two new local searches that may be used in conjunction with the AVM, Geometric and Lattice Search. A theoretical runtime analysis shows that under certain conditions, the use of these searches is proven to outperform the original AVM. These theoretical results are confirmed by an empirical study with four programs, which shows that increases of speed of over 50% are possible in practice.

References

[1]

A. Arcuri. Full theoretical runtime analysis of alternating variable method on the triangle classification problem. In SSBSE, 2009.

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 SBST, 2008.

Digital Library

[3]

A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics -- Foundations and Recent Developments. Number 1 in Series on Theoretical Computer Science. World Scientific, 2011.

Digital Library

[4]

D. E. Ferguson. Fibonaccian searching. Comm. of the ACM, 3(12), 1960.

Digital Library

[5]

G. Fraser, A. Arcuri, and P. McMinn. Test suite generation with memetic algorithms. In GECCO, 2013.

Digital Library

[6]

M. Harman and P. McMinn. A theoretical and empirical study of search based testing: Local, global and hybrid search. IEEE Trans. Soft. Eng., 36(2).

Digital Library

[7]

J. Kiefer. Sequential minimax search for a maximum. Amer. Math. Soc., 4, 1953.

[8]

B. Korel. Automated software test data generation. IEEE Trans. on Soft. Eng., 16(8), 1990.

Digital Library

[9]

P. K. Lehre and X. Yao. Crossover can be constructive when computing unique input-output sequences. Soft Computing, 15, 2011.

Digital Library

[10]

P. K. Lehre and X. Yao. Runtime analysis of the (1+1) EA on computing unique input output sequences. Information Sciences, 2013. (To appear).

[11]

P. McMinn. An identification of program factors that impact crossover performance in evolutionary test input generation for the branch coverage of C programs. Inf. and Soft. Tech., 55(1).

Digital Library

[12]

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

Digital Library

[13]

P. McMinn. IGUANA: Input generation using automated novel algorithms. a plug and play research tool. Technical Report CS-07-14, Uni. Sheffield, 2007.

[14]

L. L. Minku, D. Sudholt, and X. Yao. Evolutionary algorithms for the project scheduling problem: Runtime analysis and improved design. In GECCO, 2012.

Digital Library

[15]

J. F. Monahan. Numerical Methods of Statistics. Cam. Univ. Press, 2nd edition, 2011.

Digital Library

[16]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[17]

A. Vargha and H. D. Delaney. A Critique and Improvement of the CL Common Language Effect Size Statistics of McGraw and Wong. Journal on Educational and Behavioral Statistics, 25(2), 2000.

[18]

J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Inf. and Soft. Tech., 43(14), 2001.

Cited By

Liu FHuang HSu JSemujju SYang ZHao Z(2022)Manifold-Inspired Search-Based Algorithm for Automated Test Case GenerationIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2021.307096810:2(1075-1090)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TETC.2021.3070968
Cai GSu QHu Z(2022)Binary searching iterative algorithm for generating test cases to cover pathsApplied Soft Computing10.1016/j.asoc.2021.107910113:PAOnline publication date: 3-Jan-2022
https://dl.acm.org/doi/10.1016/j.asoc.2021.107910
Alsharif AKapfhammer GMcMinn P(2020)Hybrid Methods for Reducing Database Schema Test SuitesProceedings of the IEEE/ACM 1st International Conference on Automation of Software Test10.1145/3387903.3389305(41-50)Online publication date: 7-Oct-2020
https://dl.acm.org/doi/10.1145/3387903.3389305
Show More Cited By

Index Terms

A theoretical runtime and empirical analysis of different alternating variable searches for search-based testing
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A Theoretical and Empirical Study of Search-Based Testing: Local, Global, and Hybrid Search

Search-based optimization techniques have been applied to structural software test data generation since 1992, with a recent upsurge in interest and activity within this area. However, despite the large number of recent studies on the applicability of ...
Design and analysis of different alternating variable searches for search-based software testing

Manual software testing is a notoriously expensive part of the software development process, and its automation is of high concern. One aspect of the testing process is the automatic generation of test inputs. This paper studies the Alternating Variable ...
Full Theoretical Runtime Analysis of Alternating Variable Method on the Triangle Classification Problem
SSBSE '09: Proceedings of the 2009 1st International Symposium on Search Based Software Engineering

Runtime Analysis is a type of theoretical investigation that aims to determine, via rigorous mathematical proofs,the time a search algorithm needs to find an optimal solution.This type of investigation is useful to understand why a search algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Copyright © 2013 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: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
140
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu FHuang HSu JSemujju SYang ZHao Z(2022)Manifold-Inspired Search-Based Algorithm for Automated Test Case GenerationIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2021.307096810:2(1075-1090)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TETC.2021.3070968
Cai GSu QHu Z(2022)Binary searching iterative algorithm for generating test cases to cover pathsApplied Soft Computing10.1016/j.asoc.2021.107910113:PAOnline publication date: 3-Jan-2022
https://dl.acm.org/doi/10.1016/j.asoc.2021.107910
Alsharif AKapfhammer GMcMinn P(2020)Hybrid Methods for Reducing Database Schema Test SuitesProceedings of the IEEE/ACM 1st International Conference on Automation of Software Test10.1145/3387903.3389305(41-50)Online publication date: 7-Oct-2020
https://dl.acm.org/doi/10.1145/3387903.3389305
Alsharif AKapfhammer GMcMinn P(2020)STICCER: Fast and Effective Database Test Suite Reduction Through Merging of Similar Test Cases2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST)10.1109/ICST46399.2020.00031(220-230)Online publication date: Oct-2020
https://doi.org/10.1109/ICST46399.2020.00031
Mironovich VBuzdalov MVyatkin VTakadama K(2018)From fitness landscape analysis to designing evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208230(1902-1905)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208230
McMinn PKapfhammer G(2016)AVMf: An Open-Source Framework and Implementation of the Alternating Variable MethodSearch Based Software Engineering10.1007/978-3-319-47106-8_21(259-266)Online publication date: 24-Sep-2016
https://doi.org/10.1007/978-3-319-47106-8_21

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.

Media

Figures

Other

Tables

View Table of Contents