research-article

An Adaptive Search Budget Allocation Approach for Search-Based Test Case Generation

Authors:

Simone Scalabrino,

Antonio Mastropaolo,

Gabriele Bavota,

Rocco OlivetoAuthors Info & Claims

ACM Transactions on Software Engineering and Methodology (TOSEM), Volume 30, Issue 3

Article No.: 36, Pages 1 - 26

https://doi.org/10.1145/3446199

Published: 23 April 2021 Publication History

Abstract

Search-based techniques have been successfully used to automate test case generation. Such approaches allocate a fixed search budget to generate test cases aiming at maximizing code coverage. The search budget plays a crucial role; due to the hugeness of the search space, the higher the assigned budget, the higher the expected coverage. Code components have different structural properties that may affect the ability of search-based techniques to achieve a high coverage level. Thus, allocating a fixed search budget for all the components is not recommended and a component-specific search budget should be preferred. However, deciding the budget to assign to a given component is not a trivial task.

In this article, we introduce Budget Optimization for Testing (BOT), an approach to adaptively allocate the search budget to the classes under test. BOT requires information about the branch coverage that will be achieved on each class with a given search budget. Therefore, we also introduce BRANCHOS, an approach that predicts coverage in a budget-aware way. The results of our experiments show that (i) BRANCHOS can approximate the branch coverage in time with a low error, and (ii) BOT can significantly increase the coverage achieved by a test generation tool and the effectiveness of generated tests.

References

[1]

Andrea Arcuri and Lionel Briand. 2011. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Proceedings of the 2011 33rd International Conference on Software Engineering (ICSE’11). IEEE, 1--10.

Digital Library

[2]

Earl T. Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo. 2015. The oracle problem in software testing: A survey. IEEE Transactions on Software Engineering 41, 5 (2015), 507--525.

Digital Library

[3]

David W. Binkley and Keith Brian Gallagher. 1996. Program slicing. In Advances in Computers. Vol. 43. Elsevier, 1--50.

[4]

Leo Breiman. 2001. Random forests. Machine Learning 45, 1 (2001), 5--32.

Digital Library

[5]

José Campos, Andrea Arcuri, Gordon Fraser, and Rui Abreu. 2014. Continuous test generation: Enhancing continuous integration with automated test generation. In Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering. ACM, 55--66.

Digital Library

[6]

Norman Cliff. 1993. Dominance statistics: Ordinal analyses to answer ordinal questions. Psychological Bulletin 114, 3 (1993), 494.

[7]

Jacob Cohen. 2013. Statistical Power Analysis for the Behavioral Sciences. Academic Press.

[8]

Camila Faria de Castro, Decio de Souza Oliveira, and Marcelo Medeiros Eler. 2016. Identifying characteristics of Java methods that may influence branch coverage: An exploratory study on open source projects. In Proceedings of the 2016 35th International Conference of the Chilean Computer Science Society (SCCC’16). IEEE, 1--8.

[9]

Javier Ferrer, Francisco Chicano, and Enrique Alba. 2013. Estimating software testing complexity. Information and Software Technology 55, 12 (2013), 2125--2139.

Digital Library

[10]

Gordon Fraser and Andrea Arcuri. 2011. Evosuite: Automatic test suite generation for object-oriented software. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering. ACM, 416--419.

Digital Library

[11]

Gordon Fraser and Andrea Arcuri. 2013. Whole test suite generation. IEEE Transactions on Software Engineering 39, 2 (2013), 276--291.

Digital Library

[12]

Gordon Fraser and Andrea Arcuri. 2014. A large-scale evaluation of automated unit test generation using EvoSuite. ACM Transactions on Software Engineering and Methodology (TOSEM) 24, 2 (2014), 8.

Digital Library

[13]

Patrice Godefroid, Nils Klarlund, and Koushik Sen. 2005. DART: Directed automated random testing. In ACM Sigplan Notices, Vol. 40. ACM, 213--223.

Digital Library

[14]

Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten. 2009. The WEKA data mining software: An update. ACM SIGKDD Explorations Newsletter 11, 1 (2009), 10--18.

Digital Library

[15]

Richard Hamlet. 1994. Random testing. Encyclopedia of Software Engineering (1994).

[16]

Simon Haykin and Neural Network. 2004. A comprehensive foundation. Neural Networks 2, 2004 (2004), 41.

[17]

Pavneet Singh Kochhar, Ferdian Thung, David Lo, and Julia Lawall. 2014. An empirical study on the adequacy of testing in open source projects. In 2014 21st Asia-Pacific Software Engineering Conference, Vol. 1. IEEE, 215--222.

Digital Library

[18]

Kiran Lakhotia, Mark Harman, and Hamilton Gross. 2013. AUSTIN: An open source tool for search based software testing of C programs. Information and Software Technology 55, 1 (2013), 112--125.

Digital Library

[19]

Phil McMinn. 2007. IGUANA: Input Generation Using Automated Novel Algorithms. A Plug and Play Research Tool. Technical Report CS-07-14. Department of Computer Science, University of Sheffield.

[20]

Phil McMinn. 2011. Search-based software testing: Past, present and future. In International Conference on Software Testing, Verification and Validation Workshops. IEEE, 153--163.

Digital Library

[21]

Carlos Pacheco and Michael D. Ernst. 2007. Randoop: Feedback-directed random testing for Java. In Companion to the 22nd ACM SIGPLAN Conference on Object-Oriented Programming Systems and Applications Companion. ACM, 815--816.

[22]

Carlos Pacheco, Shuvendu K. Lahiri, Michael D. Ernst, and Thomas Ball. 2007. Feedback-directed random test generation. In Proceedings of the 29th International Conference on Software Engineering. IEEE Computer Society, 75--84.

Digital Library

[23]

Annibale Panichella, Fitsum Kifetew, and Paolo Tonella. 2017. Automated test case generation as a many-objective optimisation problem with dynamic selection of the targets. IEEE Transactions on Software Engineering 44 (2017), 122–158.

[24]

Annibale Panichella, Fitsum Meshesha Kifetew, and Paolo Tonella. 2015. Reformulating branch coverage as a many-objective optimization problem. In Proceedings of the 2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST’15). IEEE, 1--10.

[25]

José Miguel Rojas, José Campos, Mattia Vivanti, Gordon Fraser, and Andrea Arcuri. 2015. Combining multiple coverage criteria in search-based unit test generation. In International Symposium on Search Based Software Engineering. Springer, 93--108.

[26]

José Miguel Rojas, Mattia Vivanti, Andrea Arcuri, and Gordon Fraser. 2017. A detailed investigation of the effectiveness of whole test suite generation. Empirical Software Engineering 22, 2 (2017), 852--893.

Digital Library

[27]

Simone Scalabrino, Giovanni Grano, Dario Di Nucci, Rocco Oliveto, and Andrea De Lucia. 2016. Search-based testing of procedural programs: Iterative single-target or multi-target approach?. In International Symposium on Search Based Software Engineering. Springer, 64--79.

[28]

Koushik Sen. 2007. Effective random testing of concurrent programs. In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering. ACM, 323--332.

Digital Library

[29]

Koushik Sen, Darko Marinov, and Gul Agha. 2005. CUTE: A concolic unit testing engine for C. In ACM SIGSOFT Software Engineering Notes, Vol. 30. ACM, 263--272.

[30]

Paolo Tonella. 2004. Evolutionary testing of classes. In ACM SIGSOFT Software Engineering Notes, Vol. 29. ACM, 119--128.

Digital Library

Cited By

Zhang GLi LSu ZYue FChen YLi MYao X(2024)On Estimating the Feasible Solution Space of Multi-objective Testing Resource AllocationACM Transactions on Software Engineering and Methodology10.1145/365444433:6(1-41)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3654444
Verma AChoudhary ATiwari S(2023)Software Test Case Generation Tools and Techniques: A ReviewInternational Journal of Mathematical, Engineering and Management Sciences10.33889/IJMEMS.2023.8.2.0188:2(293-315)Online publication date: 1-Apr-2023
https://doi.org/10.33889/IJMEMS.2023.8.2.018
Panigrahi SJena A(2022)Spider Monkey Particle Swarm Optimization (SMPSO) With Coverage Criteria for Optimal Test Case Generation in Object-Oriented SystemsInternational Journal of Open Source Software and Processes10.4018/IJOSSP.30075013:1(1-20)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.4018/IJOSSP.300750

Index Terms

An Adaptive Search Budget Allocation Approach for Search-Based Test Case Generation
1. Software and its engineering
  1. Software creation and management
    1. Search-based software engineering
    2. Software post-development issues
      1. Maintaining software

Recommendations

RESTful API Automated Test Case Generation with EvoMaster

RESTful APIs are widespread in industry, especially in enterprise applications developed with a microservice architecture. A RESTful web service will provide data via an API over the network using HTTP, possibly interacting with databases and other web ...
Diversifying Focused Testing for Unit Testing
Continuous Special Section: AI and SE

Software changes constantly, because developers add new features or modifications. This directly affects the effectiveness of the test suite associated with that software, especially when these new modifications are in a specific area that no test case ...
Test Data Generation for Path Coverage of MPI Programs Using SAEO
Continuous Special Section: AI and SE

Message-passing interface (MPI) programs, a typical kind of parallel programs, have been commonly used in various applications. However, it generally takes exhaustive computation to run these programs when generating test data to test them. In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology

ACM Transactions on Software Engineering and Methodology Volume 30, Issue 3

Continuous Special Section: AI and SE

July 2021

600 pages

ISSN:1049-331X

EISSN:1557-7392

DOI:10.1145/3450566

Editor:
Mauro Pezzè
Università della Svizzera italiana and Università di Milano-Bicocca, Switzerland

Issue’s Table of Contents

Copyright © 2021 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 2021

Accepted: 01 December 2020

Revised: 01 November 2020

Received: 01 October 2019

Published in TOSEM Volume 30, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
232
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang GLi LSu ZYue FChen YLi MYao X(2024)On Estimating the Feasible Solution Space of Multi-objective Testing Resource AllocationACM Transactions on Software Engineering and Methodology10.1145/365444433:6(1-41)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3654444
Verma AChoudhary ATiwari S(2023)Software Test Case Generation Tools and Techniques: A ReviewInternational Journal of Mathematical, Engineering and Management Sciences10.33889/IJMEMS.2023.8.2.0188:2(293-315)Online publication date: 1-Apr-2023
https://doi.org/10.33889/IJMEMS.2023.8.2.018
Panigrahi SJena A(2022)Spider Monkey Particle Swarm Optimization (SMPSO) With Coverage Criteria for Optimal Test Case Generation in Object-Oriented SystemsInternational Journal of Open Source Software and Processes10.4018/IJOSSP.30075013:1(1-20)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.4018/IJOSSP.300750

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents