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

research-article

Empirical evaluation of a nesting testability transformation for evolutionary testing

Authors:

Mark HarmanAuthors Info & Claims

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

Article No.: 11, Pages 1 - 27

https://doi.org/10.1145/1525880.1525884

Published: 04 June 2009 Publication History

Abstract

Evolutionary testing is an approach to automating test data generation that uses an evolutionary algorithm to search a test object's input domain for test data. Nested predicates can cause problems for evolutionary testing, because information needed for guiding the search only becomes available as each nested conditional is satisfied. This means that the search process can overfit to early information, making it harder, and sometimes near impossible, to satisfy constraints that only become apparent later in the search. The article presents a testability transformation that allows the evaluation of all nested conditionals at once. Two empirical studies are presented. The first study shows that the form of nesting handled is prevalent in practice. The second study shows how the approach improves evolutionary test data generation.

References

[1]

Baresel, A. 2000. Automatisierung von strukturtests mit evolutionren algorithmen. Diploma Thesis, Humboldt University, Berlin, Germany.

[2]

Baresel, A., Binkley, D., Harman, M., and Korel, B. 2004. Evolutionary testing in the presence of loop-assigned flags: A testability transformation approach. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA'04). ACM, 43--52.

Digital Library

[3]

Baresel, A. and Sthamer, H. 2003. Evolutionary testing of flag conditions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'03). Lecture Notes in Computer Science vol. 2724. Springer-Verlag, 2442--2454.

Digital Library

[4]

Baresel, A., Sthamer, H., and Schmidt, M. 2002. Fitness function design to improve evolutionary structural testing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'02). Morgan Kaufmann, New York, 1329--1336.

Digital Library

[5]

Boyer, R. S., Elspas, B., and Levitt, K. N. 1975. SELECT - A formal system for testing and debugging programs by symbolic execution. In Proceedings of the International Conference on Reliable Software. ACM Press, 234--244.

Digital Library

[6]

Clarke, L. 1976. A system to generate test data and symbolically execute programs. IEEE Trans. Softw. Engin. 2, 3, 215--222.

Digital Library

[7]

DeMillo, R. A. and Offutt, A. J. 1991. Constraint-Based automatic test data generation. IEEE Trans. Softw. Engin. 17, 9, 900--909.

Digital Library

[8]

Do, H., Elbaum, S., and Rothermel, G. 2005. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empir. Softw. Engin. 10, 4, 405--435.

Digital Library

[9]

Ferguson, R. and Korel, B. 1996. The chaining approach for software test data generation. ACM Trans. Softw. Engin. Methodol. 5, 1, 63--86.

Digital Library

[10]

Harman, M., Hassoun, Y., Lakhotia, K., McMinn, P., and Wegener, J. 2007. The impact of input domain reduction on search-based test data generation. In Proceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE'07). ACM Press, 155--164.

Digital Library

[11]

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

Digital Library

[12]

Harman, M., Hu, L., Hierons, R., Wegener, J., Sthamer, H., Baresel, A., and Roper, M. 2004. Testability transformation. IEEE Trans. Softw. Engin. 30, 1, 3--16.

Digital Library

[13]

Harman, M. and McMinn, P. 2009. A theoretical and empirical study of search-based testing: Local, global, and hybrid search. IEEE Trans. Softw. Engin. To appear.

Digital Library

[14]

Hierons, R., Harman, M., and Fox, C. 2005. Branch-Coverage testability transformation for unstructured programs. Comput. J. 48, 4, 421--436.

Digital Library

[15]

Jones, B., Sthamer, H., and Eyres, D. 1996. Automatic structural testing using genetic algorithms. Softw. Engin. J. 11, 5, 299--306.

[16]

Jones, B., Sthamer, H., Yang, X., and Eyres, D. 1995. The automatic generation of software test data sets using adaptive search techniques. In Proceedings of the 3rd International Conference on Software Quality Management, 435--444.

[17]

King, J. 1976. Symbolic execution and program testing. Comm. ACM 19, 7, 385--394.

Digital Library

[18]

Korel, B. 1990. Automated software test data generation. IEEE Trans. Softw. Engin. 16, 8, 870--879.

Digital Library

[19]

Korel, B. 1992. Dynamic method for software test data generation. Softw. Test. Verif. Reliabil. 2, 4, 203--213.

[20]

Korel, B. and Al-Yami, A. M. 1996. Assertion-Oriented automated test data generation. In Proceedings of the 18th International Conference on Software Engineering (ICSE), 71--80.

Digital Library

[21]

Korel, B., Harman, M., Chung, S., Apirukvorapinit, P., and R., G. 2005. Data dependence based testability transformation in automated test generation. In 16th International Symposium on Software Reliability Engineering (ISSRE'05). 245--254.

Digital Library

[22]

McMinn, P. 2004. Search-Based software test data generation: A survey. Softw. Test. Verif. Reliabil. 14, 2, 105--156.

Digital Library

[23]

McMinn, P., Binkley, D., and Harman, M. 2005. Testability transformation for efficient automated test data search in the presence of nesting. In Proceedings of the UK Software Testing Workshop (UKTest'05). University of Sheffield Computer Science tech. rep. CS-05-07, 165--182.

[24]

McMinn, P. and Holcombe, M. 2006. Evolutionary testing using an extended chaining approach. Evolution. Comput. 14, 41--64.

Digital Library

[25]

Miller, W. and Spooner, D. 1976. Automatic generation of floating-point test data. IEEE Trans. Softw. Engin. 2, 3, 223--226.

Digital Library

[26]

Mühlenbein, H. and Schlierkamp-Voosen, D. 1993. Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization. Evolution. Comput. 1, 1, 25--49.

Digital Library

[27]

Pargas, R., Harrold, M., and Peck, R. 1999. Test-Data generation using genetic algorithms. Softw. Test. Verif. Reliabil. 9, 4, 263--282.

[28]

Puschner, P. and Nossal, R. 1998. Testing the results of static worst-case execution-time analysis. In Proceedings of the 19th IEEE Real-Time Systems Symposium. IEEE Computer Society Press, 134--143.

Digital Library

[29]

Tracey, N. 2000. A search-based automated test-data generation framework for safety critical software. Ph.D. thesis, University of York.

[30]

Tracey, N., Clark, J., and Mander, K. 1998a. Automated program flaw finding using simulated annealing. Softw. Engin. Not. 23, 2, 73--81.

Digital Library

[31]

Tracey, N., Clark, J., and Mander, K. 1998b. The way forward for unifying dynamic test-case generation: The optimisation-based approach. In Proceedings of the International Workshop on Dependable Computing and Its Applications. 169--180.

[32]

Tracey, N., Clark, J., Mander, K., and McDermid, J. 1998c. An automated framework for structural test-data generation. In Proceedings of the International Conference on Automated Software Engineering. IEEE Computer Society Press, 285--288.

Digital Library

[33]

Tracey, N., Clark, J., Mander, K., and McDermid, J. 2000. Automated test data generation for exception conditions. Softw. Pract. Exper. 30, 1, 61--79.

Digital Library

[34]

Wegener, J., Baresel, A., and Sthamer, H. 2001. Evolutionary test environment for automatic structural testing. Inform. Softw. Technol. 43, 14, 841--854.

[35]

Wegener, J., Grimm, K., Grochtmann, M., Sthamer, H., and Jones, B. 1996. Systematic testing of real-time systems. In Proceedings of the 4th European Conference on Software Testing, Analysis and Review (EuroSTAR'96).

[36]

Wegener, J. and Grochtmann, M. 1998. Verifying timing constraints of real-time systems by means of evolutionary testing. Real-Time Syst. 15, 3, 275--298.

Digital Library

[37]

Whitley, D. 2001. An overview of evolutionary algorithms: Practical issues and common pitfalls. Inform. Softw. Technol. 43, 14, 817--831.

[38]

Xanthakis, S., Ellis, C., Skourlas, C., Le Gall, A., Katsikas, S., and Karapoulios, K. 1992. Application of genetic algorithms to software testing (Application des algorithmes génétiques au test des logiciels). In Proceedings of the 5th International Conference on Software Engineering and its Applications, 625--636.

Cited By

Arcuri AZhang MGaleotti J(2024)Advanced White-Box Heuristics for Search-Based Fuzzing of REST APIsACM Transactions on Software Engineering and Methodology10.1145/365215733:6(1-36)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3652157
Zhang MBelhadi AArcuri A(2023)JavaScript SBST Heuristics to Enable Effective Fuzzing of NodeJS Web APIsACM Transactions on Software Engineering and Methodology10.1145/359380132:6(1-29)Online publication date: 24-Apr-2023
https://dl.acm.org/doi/10.1145/3593801
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://dl.acm.org/doi/10.1109/TSE.2022.3228334
Show More Cited By

Index Terms

Empirical evaluation of a nesting testability transformation for evolutionary testing
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Testability Transformation

Abstract--A testability transformation is a source-to-source transformation that aims to improve the ability of a given test generation method to generate test data for the original program. This paper introduces testability transformation, ...
Evaluating evolutionary testability for structure-oriented testing with software measurements

Test case design is the most important test activity with respect to test quality. For this reason, a large number of testing methods have been developed to assist the tester with the definition of appropriate, error-sensitive test data. Evolutionary ...
An Improved Technique of Fitness Evaluation for Evolutionary Testing
COMPSACW '11: Proceedings of the 2011 IEEE 35th Annual Computer Software and Applications Conference Workshops

Many Search Based Software testing (SBST) have been proposed and experiments show that they can generate effective test data. However, a meta-heuristic search (MHS) algorithm in these techniques incurs considerable computation cost to evaluate fitness ...

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 18, Issue 3

May 2009

142 pages

ISSN:1049-331X

EISSN:1557-7392

DOI:10.1145/1525880

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2009

Accepted: 01 November 2007

Revised: 01 November 2007

Received: 01 May 2006

Published in TOSEM Volume 18, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
742
Total Downloads

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

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Arcuri AZhang MGaleotti J(2024)Advanced White-Box Heuristics for Search-Based Fuzzing of REST APIsACM Transactions on Software Engineering and Methodology10.1145/365215733:6(1-36)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3652157
Zhang MBelhadi AArcuri A(2023)JavaScript SBST Heuristics to Enable Effective Fuzzing of NodeJS Web APIsACM Transactions on Software Engineering and Methodology10.1145/359380132:6(1-29)Online publication date: 24-Apr-2023
https://dl.acm.org/doi/10.1145/3593801
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://dl.acm.org/doi/10.1109/TSE.2022.3228334
Barisal SKishore PNayak G(2022)Source Code Features Based Branch Coverage Prediction Using Ensemble TechniqueMeta Heuristic Techniques in Software Engineering and Its Applications10.1007/978-3-031-11713-8_2(10-19)Online publication date: 18-Oct-2022
https://doi.org/10.1007/978-3-031-11713-8_2
Arcuri AGaleotti J(2021)Enhancing Search-based Testing with Testability Transformations for Existing APIsACM Transactions on Software Engineering and Methodology10.1145/347727131:1(1-34)Online publication date: 28-Sep-2021
https://dl.acm.org/doi/10.1145/3477271
Vogl SSchweikl SFraser GKrawiec K(2021)Encoding the certainty of boolean variables to improve the guidance for search-based test generationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459339(1088-1096)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459339
Chouksey RMaddheshiya SKarfa C(2021)VP_TT: A value propagation based equivalence checker for testability transformationsIET Software10.1049/sfw2.1200815:1(147-159)Online publication date: 26-Jan-2021
https://doi.org/10.1049/sfw2.12008
Binkley DGlenn JAlsharif AMcMinn P(2020)An Investigation into the Effect of Control and Data Dependence Paths on Predicate Testability2020 IEEE 20th International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM51674.2020.00023(160-170)Online publication date: Sep-2020
https://doi.org/10.1109/SCAM51674.2020.00023
ArcuriJuan AGaleotti P(2020)Testability Transformations For Existing APIs2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST)10.1109/ICST46399.2020.00025(153-163)Online publication date: Oct-2020
https://doi.org/10.1109/ICST46399.2020.00025
Khari MKumar P(2019)An extensive evaluation of search-based software testingSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-017-2906-y23:6(1933-1946)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s00500-017-2906-y
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents