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

article

Search based software testing of object-oriented containers

Authors:

Xin YaoAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 178, Issue 15

Pages 3075 - 3095

https://doi.org/10.1016/j.ins.2007.11.024

Published: 01 August 2008 Publication History

Abstract

Automatic software testing tools are still far from ideal for real world object-oriented (OO) software. The use of nature inspired search algorithms for this problem has been investigated recently. Testing complex data structures (e.g., containers) is very challenging since testing software with simple states is already hard. Because containers are used in almost every type of software, their reliability is of utmost importance. Hence, this paper focuses on the difficulties of testing container classes with nature inspired search algorithms. We will first describe how input data can be automatically generated for testing Java containers. Input space reductions and a novel testability transformation are presented to aid the search algorithms. Different search algorithms are then considered and studied in order to understand when and why a search algorithm is effective for a testing problem. In our experiments, these nature inspired search algorithms seem to give better results than the traditional techniques described in literature. Besides, the problem of minimising the length of the test sequences is also addressed. Finally, some open research questions are given.

References

[1]

A. Arcuri, X. Yao, A memetic algorithm for test data generation of object-oriented software, in: IEEE Congress on Evolutionary Computation (CEC), 2007, pp. 2048-2055.

[2]

A. Arcuri, X. Yao, On test data generation of object-oriented software, in: Testing: Academic and Industrial Conference, Practice and Research Techniques (TAIC PART), 2007, pp. 72-76.

Digital Library

[3]

A. Baresel, D. Binkley, M. Harman, B. Korel, 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), 2004, pp. 43-52.

Digital Library

[4]

A. Baresel, H. Sthamer, Evolutionary testing of flag conditions, in: Genetic and Evolutionary Computation Conference (GECCO), 2003, pp. 2442-2454.

Digital Library

[5]

A. Baresel, H. Sthamer, M. Schmidt, Fitness function design to improve evolutionary structural testing, in: Genetic and Evolutionary Computation Conference (GECCO), 2002, pp. 1329-1336.

Digital Library

[6]

Barr, R.S., Golden, B.L., Kelly, J.P., Rescende, M.G.C. and Stewart, W.R., Designing and reporting on computational experiments with heuristic methods. Journal of Heuristics. v1 i1. 9-32.

[7]

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

Digital Library

[8]

C. Boyapati, S. Khurshid, D. Marinov, Korat: automated testing based on java predicates, in: Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), 2002.

Digital Library

[9]

U. Buy, A. Orso, M. Pezzè, Automated testing of classes, in: Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), 2000, pp. 39-48.

Digital Library

[10]

Chen, T.Y. and Lau, M.F., On the divide-and-conquer approach towards test suite reduction. Information Sciences. v152. 89-119.

Digital Library

[11]

Y. Cheon, M. Kim, A specification-based fitness function for evolutionary testing of object-oriented programs, in: Genetic and Evolutionary Computation Conference (GECCO), 2006, pp. 1952-1954.

Digital Library

[12]

Y. Cheon, M.Y. Kim, A. Perumandla, A complete automation of unit testing for java programs, in: Proceedings of the 2005 International Conference on Software Engineering Research and Practice, 2005, pp. 290-295.

[13]

Clark, J., Dolado, J.J., Harman, M., Hierons, R., Jones, B., Lumkin, M., Mitchell, B., Mancoridis, S., Rees, K., Roper, M. and Shepperd, M., Reformulating software engineering as a search problem. IEE Proceedings - Software. v150 i3. 161-175.

[14]

M.L. Collard, Addressing source code using srcml, in: IEEE International Workshop on Program Comprehension Working Session: Textual Views of Source Code to Support Comprehension (IWPC'05), 2005.

[15]

M. d'Amorim, C. Pacheco, T. Xie, D. Marinov, M.D. Ernst, An empirical comparison of automated generation and classification techniques for object-oriented unit testing, in: IEEE International Conference on Automated Software Engineering (ASE), 2006, pp. 59-68.

Digital Library

[16]

Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms. 2001. John Wiley and Sons.

Digital Library

[17]

R. Doong, P.G. Frankl, The astoot approach to testing object-oriented programs, ACM Transactions on Software Engineering and Methodology, 1994, pp. 101-130.

Digital Library

[18]

Ellims, M., Bridges, J. and Ince, D.C., The economics of unit testing. Empirical Software Engineering. v11 i1. 5-31.

Digital Library

[19]

Ferguson, R. and Korel, B., The chaining approach for software test data generation. ACM Transactions on Software Engineering and Methodology. v5 i1. 63-86.

Digital Library

[20]

M. Harman, L. Hu, R. Hierons, A. Baresel, H. Sthamer, Improving evolutionary testing by flag removal, in: Genetic and Evolutionary Computation Conference (GECCO), 2002, pp. 1351-1358.

Digital Library

[21]

Harman, M., Hu, L., Hierons, R., Wegener, J., Sthamer, H., Baresel, A. and Roper, M., Testability transformation. IEEE Transactions on Software Engineering. v30 i1. 3-16.

Digital Library

[22]

M. Harman, M. Munro, L. Hu, X. Zhang, Side-effect removal transformation, in: Proceedings of the 9th IEEE International Workshop on Program Comprehension, 2001, pp. 310-319.

Digital Library

[23]

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

Digital Library

[24]

IEEE-Standards-Board. IEEE standard for software unit testing: an american national standard, ansi/ieee std 1008-1987. IEEE Standards: Software Engineering, Process Standards, vol. 2, 1999.

[25]

King, J.C., Symbolic execution and program testing. Communications of the ACM. 385-394.

Digital Library

[26]

S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing. Science, Number 4598, 13 May 1983, 220, 4598:671-680, 1983.

[27]

Korel, B., Automated software test data generation. IEEE Transactions on Software Engineering. 870-879.

Digital Library

[28]

Lin, J.C. and Yeh, P.L., Automatic test data generation for path testing using GAs. Information Sciences. v131 i1-4. 47-64.

Digital Library

[29]

X. Liu, B. Wang, H. Liu, Evolutionary search in the context of object oriented programs, in: MIC2005: The Sixth Metaheuristics International Conference, 2005.

[30]

Mann, H.B. and Whitney, D.R., On a test of whether one of two random variables is stochastically larger than the other. Annals of Mathematical Statistics. v18 i1. 50-60.

[31]

D. Marinov, S. Khurshid, Testera: A novel framework for testing java programs, in: IEEE International Conference on Automated Software Engineering (ASE), 2001.

Digital Library

[32]

J. McDonald, D. Hoffman, P. Strooper, Programmatic testing of the standard template library containers, in: IEEE International Conference on Automated Software Engineering (ASE), 1998, pp. 147-156.

Digital Library

[33]

McMinn, P., Search-based software test data generation: a survey. Software Testing, Verification and Reliability. v14 i2. 105-156.

Digital Library

[34]

P. McMinn, Evolutionary Search for Test Data in the Presence of State Behaviour. Ph.D. Thesis, University of Sheffield, 2005.

[35]

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

[36]

P. McMinn, M. Holcombe, The state problem for evolutionary testing, in: Genetic and Evolutionary Computation Conference (GECCO), 2003, pp. 2488-2500.

Digital Library

[37]

P. McMinn, M. Holcombe, Hybridizing evolutionary testing with the chaining approach, in: Genetic and Evolutionary Computation Conference (GECCO), 2004, pp. 1363-1374.

[38]

P. McMinn, M. Holcombe, Evolutionary testing of state-based programs, in: Genetic and Evolutionary Computation Conference (GECCO), 2005, pp. 1013-1020.

Digital Library

[39]

Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A. and Teller, E., Equations of state calculations by fast computing machines. Journal of Chemical Physics. v21. 1087-1091.

[40]

Miller, J., Reformat, M. and Zhang, H., Automatic test data generation using genetic algorithm and program dependence graphs. Information and Software Technology. v48 i7. 586-605.

[41]

P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Concurrent Computation Program, C3P Report 826, 1989.

[42]

Myers, G., The Art of Software Testing. 1979. Wiley, New York.

Digital Library

[43]

P. Netisopakul, L. White, J. Morris, D. Hoffman, Data coverage testing of programs for container classes, in: Proceedings 13th International Symposium on Software Reliability Engineering, 2002, pp. 183-194.

Digital Library

[44]

Runarsson, T.P. and Yao, X., Stochastic ranking for constrained evolutionary optimization. IEEE Transactions on Evolutionary Computation. v4 i3. 284-294.

Digital Library

[45]

R. Sagarna, A. Arcuri, X. Yao, Estimation of distribution algorithms for testing object oriented software, in: IEEE Congress on Evolutionary Computation (CEC), 2007, pp. 438-444.

[46]

A. Seesing, Evotest: test case generation using genetic programming and software analysis. Master's thesis, Delft University of Technology, 2006.

[47]

G. Tassey, The economic impacts of inadequate infrastructure for software testing, final report, National Institute of Standards and Technology, 2002.

[48]

P. Tonella, Evolutionary testing of classes, in: Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), 2004, pp. 119-128.

Digital Library

[49]

N. Tracey, J. Clark, K. Mander, J.A. McDermid, An automated framework for structural test-data generation, in: IEEE International Conference on Automated Software Engineering (ASE), 1998, pp. 285-288.

Digital Library

[50]

W. Visser, C.S. Pasareanu, S. Khurshid, Test input generation with java pathfinder, in: Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), 2004.

Digital Library

[51]

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

Digital Library

[52]

Waeselynck, H., Fosse, P.T. and Kaddour, O.A., Simulated annealing applied to test generation: landscape characterization and stopping criteria. Empirical Software Engineering. v12 i1. 35-63.

Digital Library

[53]

S. Wappler, F. Lammermann, Using evolutionary algorithms for the unit testing of object-oriented software, in: Genetic and Evolutionary Computation Conference (GECCO), 2005, pp. 1053-1060.

Digital Library

[54]

S. Wappler, J. Wegener, Evolutionary unit testing of object-oriented software using a hybrid evolutionary algorithm, in: IEEE Congress on Evolutionary Computation (CEC), 2006, pp. 851-858.

[55]

S. Wappler, J. Wegener, Evolutionary unit testing of object-oriented software using strongly-typed genetic programming, in: Genetic and Evolutionary Computation Conference (GECCO), 2006, pp. 1925-1932.

Digital Library

[56]

Wegener, J., Baresel, A. and Sthamer, H., Evolutionary test environment for automatic structural testing. Information and Software Technology. v43 i14. 841-854.

[57]

Wolpert, D.H. and Macready, W.G., No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation. v1 i1. 67-82.

Digital Library

[58]

Xiao, M., El-Attar, M., Reformat, M. and Miller, J., Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques. Empirical Software Engineering. v12 i2. 183-239.

Digital Library

[59]

T. Xie, D. Marinov, D. Notkin, Rostra: a framework for detecting redundant object-oriented unit tests, in: IEEE International Conference on Automated Software Engineering (ASE), 2004, pp. 196-205.

Digital Library

[60]

T. Xie, D. Marinov, W. Schulte, D. Notkin, Symstra: a framework for generating object-oriented unit tests using symbolic execution, in: Proceedings of the 11th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 2005, pp. 365-381.

Digital Library

[61]

Yao, X., Simulated annealing with extended neighbourhood. International Journal of Computer Mathematics. v40. 169-189.

[62]

X. Yao, Comparison of different neighbourhood size in simulated annealing, in: Proceedings of the Fourth Australian Conference on Neural Networks (ACNN'93), 1993, pp. 216-219.

Cited By

Xiao DGuo YLi YChen L(2024)Optimizing Search-Based Unit Test Generation with Large Language Models: An Empirical StudyProceedings of the 15th Asia-Pacific Symposium on Internetware10.1145/3671016.3674813(71-80)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1145/3671016.3674813
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
Lin YOng YSun JFraser GDong JSpinellis DGousios GChechik MDi Penta M(2021)Graph-based seed object synthesis for search-based unit testingProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468619(1068-1080)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468619
Show More Cited By

Index Terms

Search based software testing of object-oriented containers

Recommendations

Longer is Better: On the Role of Test Sequence Length in Software Testing
ICST '10: Proceedings of the 2010 Third International Conference on Software Testing, Verification and Validation

In the presence of an internal state, often it is required a sequence of function calls 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 ...
An Automatic Testing Platform for Object-oriented Software based on Code Coverage
ICCNS '19: Proceedings of the 2019 9th International Conference on Communication and Network Security

The development of automatic object-oriented software testing tools is a challenging and realistic subject in the field of software engineering. A testing prototype system named ARTCovPS (Adaptive Random Testing Coverage-based testing Prototype System) ...
Testing object-oriented software systems
ETOOS '10: Proceedings of the 1st Workshop on Testing Object-Oriented Systems

Object-oriented Software Systems present a particular challenge to the software testing community. This review of the problem points out the particular aspects of object-oriented systems which makes it costly to test them. The flexibility and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 178, Issue 15

August, 2008

178 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2007.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 August 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
0
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

Xiao DGuo YLi YChen L(2024)Optimizing Search-Based Unit Test Generation with Large Language Models: An Empirical StudyProceedings of the 15th Asia-Pacific Symposium on Internetware10.1145/3671016.3674813(71-80)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1145/3671016.3674813
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
Lin YOng YSun JFraser GDong JSpinellis DGousios GChechik MDi Penta M(2021)Graph-based seed object synthesis for search-based unit testingProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468619(1068-1080)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468619
Anjum MRyan CCoello Coello C(2020)Scalability analysis of grammatical evolution based test data generationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390167(1213-1221)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390167
Anjum MRyan C(2019)Ariadne: Evolving Test Data Using Grammatical EvolutionGenetic Programming10.1007/978-3-030-16670-0_1(3-18)Online publication date: 24-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-16670-0_1
Rojas JVivanti MArcuri AFraser G(2017)A detailed investigation of the effectiveness of whole test suite generationEmpirical Software Engineering10.1007/s10664-015-9424-222:2(852-893)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s10664-015-9424-2
El Ariss OBou ghosn SXu W(2016)Testing Software Using Swarm Intelligence: A Bee Colony Optimization ApproachProceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS)10.4108/eai.3-12-2015.2262529(205-213)Online publication date: 24-May-2016
https://dl.acm.org/doi/10.4108/eai.3-12-2015.2262529
Moreno MRosete APavón J(2016)An agent based approach for the implementation of cooperative proactive S-MetaheuristicsExpert Systems with Applications: An International Journal10.1016/j.eswa.2016.07.01363:C(344-374)Online publication date: 30-Nov-2016
https://dl.acm.org/doi/10.1016/j.eswa.2016.07.013
Sakti APesant GGuéhéneuc Y(2015)Instance Generator and Problem Representation to Improve Object Oriented Code CoverageIEEE Transactions on Software Engineering10.1109/TSE.2014.236347941:3(294-313)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1109/TSE.2014.2363479
Marculescu BFeldt RTorkar RPoulding S(2015)An initial industrial evaluation of interactive search-based testing for embedded softwareApplied Soft Computing10.1016/j.asoc.2014.12.02529:C(26-39)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1016/j.asoc.2014.12.025
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents