Generalized Extremal Optimization: a competitive algorithm for test data generation
Resumo
O teste de software é uma parte importante do processo de desenvolvimento de software, e automatizar a geração de dados de teste contribui para reduzir esforços de custo e tempo. Foi mostrado recentemente que os Algoritmos Evolutivos (AEs) como, por exemplo, os Algoritmos Genéticos (AGs), são ferramentas valiosas para gerar dados de teste. Este trabalho avalia o desempenho de um AE proposto recentemente, a Otimização Extrema Generalizada (GEO), na geração de dados para programas que possuem caminhos com laços. O desempenho do GEO foi comparado com o de um AG, e os resultados mostraram que o GEO exigiu muito menos esforço computacional, tanto na geração de dados quanto no ajuste interno dos parâmetros. Isto indica que o GEO é uma opção competitiva para automatizar a geração de dados.
Referências
Abreu, B. T., Martins, E., and de Sousa, F. L. (2005). Automatic test data generation for path testing using a new stochastic algorithm. In Proc. of the 19th Brazilian Symp. on Software Engineering, volume 19, pages 247–262, Uberlandia, Brazil.
Abreu, B. T., Martins, E., and de Sousa, F. L. (2006). Generalized Extremal Optimization Applied to Path Testing. In Supplementary proc. of the 17th IEEE Int. Symp. on Software Reliability Engineering, volume 17, Raleigh, USA.
Bak, P. and Sneppen, K. (1993). Punctuated Equilibrium and Criticality in a Simple Model of Evolution. Physical Review Letters, 71(24):4083–4086.
Beizer, B. (1990). Software Testing Techniques. Van Nostrand Reinhold, 2nd edition.
Binder, R. V. (2000). Testing Object-Oriented Systems: Models, Patterns, and Tools. Addison-Wesley, 1st edition.
Boettcher, S. and Percus, A. G. (2001). Optimization with Extremal Dynamics. Physical Review Letters, 86:5211–5214.
Bueno, P. M. S. and Jino, M. (2002). Automatic test data generation for program paths using genetic algorithms. International Journal of Software Engineering and Knowledge Engineering, 12(6):691–710.
Burnstein, I. (2003). Practical Software Testing: A Process-oriented Approach. Springer, 1st edition.
Clarke, L. A. (1976). A system to generate test data and symbolically execute programs. IEEE Trans. on Software Engineering, 2(3):215–222.
Díaz, E., Tuya, J., and Blanco, R. (2003). Automated software testing using a metaheuristic technique based on tabu search. In ASE, pages 310–313.
Eiben, A. E. and Smith, J. E. (2003). Introduction to Evolutionary Computing. Springer.
Galski, R. L., Sousa, F. L., Ramos, F. M., and Muraoka, I. (2004). Spacecraft Thermal Design with the Generalized Extremal Optimization Algorithm. In Proc. of the Inverse Problems, Design and Optimization Symposium, Rio de Janeiro, RJ, Brazil, 2004, (in CDROM).
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
Korel, B. (1990). Automated Software Test Data Generation. IEEE Trans. on Software Engineering, 16(8):870–879.
Lin, J. and Yeh, P. (2001). Automatic test data generation for path testing using GAs. Information Sciences, 131(1-4):47–64.
Mansour, N. and Salame, M. (2004). Data Generation for Path Testing. Software Quality Journal, 12(2):121–136.
McCabe, T. J. (1976). A complexity measure. In ICSE ’76: Proc. of the 2nd international conference on Software engineering, page 407, Los Alamitos, CA, USA. IEEE Computer Society Press.
McMinn, P. (2004). Search-based software test data generation: a survey. Software Testing, Verification & Reliability, 14(2):105–156.
Michael, C. C., McGraw, G., and Schatz, M. (2001). Generating Software Test Data by Evolution. IEEE Trans. on Software Engineering, 27(12):1085–1110.
Miller, W. and Spooner, D. L. (1976). Automatic Generation of Floating-Point Test Data. IEEE Trans. on Software Engineering, 2(3):223–226.
Pargas, R. P., Harrold, M. J., and Peck, R. P. (1999). Test-data generation using genetic algorithms. Software Testing, Verification & Reliability, 9(4):263–282.
Pei, M., Goodman, E., Gao, Z., and Zhong, K. (1994). Automated Software Test Data Generation Using A Genetic Algorithm. Technical Report 6/2/1994, Michigan State University. Available at http://www.egr.msu.edu/˜pei/paper/GApaper94-02.ps. Last access on 03/28/2006.
Sousa, F. L., Ramos, F. M., Paglione, P., and Girardi, R. M. (2003). New Stochastic Algorithm for Design Optimization. AIAA Journal, 41(9):1808–1818.
Sousa, F. L., Vlassov, V., and Ramos, F. M. (2004). Generalized Extremal Optimization: An application in Heat Pipe Design. Applied Mathematical Modeling, 28:911–931.
Sthamer, H. (1996). The Automatic Generation of Software Test Data Using Genetic Algorithms. PhD thesis, University of Glamorgan, Pontyprid, Wales, Great Britain.
Tracey, N., Clark, J., and Mander, K. (1998). Automated program flaw finding using simulated annealing. SIGSOFT Softw. Eng. Notes, 23(2):73–81.
Watkins, A. and Hufnagel, E. M. (2006). Evolutionary test data generation: a comparison of fitness functions. Software Practice and Experience, 36(1):95–116.
Wikipedia (2006). Computer Bugs. Available at http://en.wikipedia.org/wiki/Computer_bugs. Last access on 01/14/2007.
Abreu, B. T., Martins, E., and de Sousa, F. L. (2006). Generalized Extremal Optimization Applied to Path Testing. In Supplementary proc. of the 17th IEEE Int. Symp. on Software Reliability Engineering, volume 17, Raleigh, USA.
Bak, P. and Sneppen, K. (1993). Punctuated Equilibrium and Criticality in a Simple Model of Evolution. Physical Review Letters, 71(24):4083–4086.
Beizer, B. (1990). Software Testing Techniques. Van Nostrand Reinhold, 2nd edition.
Binder, R. V. (2000). Testing Object-Oriented Systems: Models, Patterns, and Tools. Addison-Wesley, 1st edition.
Boettcher, S. and Percus, A. G. (2001). Optimization with Extremal Dynamics. Physical Review Letters, 86:5211–5214.
Bueno, P. M. S. and Jino, M. (2002). Automatic test data generation for program paths using genetic algorithms. International Journal of Software Engineering and Knowledge Engineering, 12(6):691–710.
Burnstein, I. (2003). Practical Software Testing: A Process-oriented Approach. Springer, 1st edition.
Clarke, L. A. (1976). A system to generate test data and symbolically execute programs. IEEE Trans. on Software Engineering, 2(3):215–222.
Díaz, E., Tuya, J., and Blanco, R. (2003). Automated software testing using a metaheuristic technique based on tabu search. In ASE, pages 310–313.
Eiben, A. E. and Smith, J. E. (2003). Introduction to Evolutionary Computing. Springer.
Galski, R. L., Sousa, F. L., Ramos, F. M., and Muraoka, I. (2004). Spacecraft Thermal Design with the Generalized Extremal Optimization Algorithm. In Proc. of the Inverse Problems, Design and Optimization Symposium, Rio de Janeiro, RJ, Brazil, 2004, (in CDROM).
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
Korel, B. (1990). Automated Software Test Data Generation. IEEE Trans. on Software Engineering, 16(8):870–879.
Lin, J. and Yeh, P. (2001). Automatic test data generation for path testing using GAs. Information Sciences, 131(1-4):47–64.
Mansour, N. and Salame, M. (2004). Data Generation for Path Testing. Software Quality Journal, 12(2):121–136.
McCabe, T. J. (1976). A complexity measure. In ICSE ’76: Proc. of the 2nd international conference on Software engineering, page 407, Los Alamitos, CA, USA. IEEE Computer Society Press.
McMinn, P. (2004). Search-based software test data generation: a survey. Software Testing, Verification & Reliability, 14(2):105–156.
Michael, C. C., McGraw, G., and Schatz, M. (2001). Generating Software Test Data by Evolution. IEEE Trans. on Software Engineering, 27(12):1085–1110.
Miller, W. and Spooner, D. L. (1976). Automatic Generation of Floating-Point Test Data. IEEE Trans. on Software Engineering, 2(3):223–226.
Pargas, R. P., Harrold, M. J., and Peck, R. P. (1999). Test-data generation using genetic algorithms. Software Testing, Verification & Reliability, 9(4):263–282.
Pei, M., Goodman, E., Gao, Z., and Zhong, K. (1994). Automated Software Test Data Generation Using A Genetic Algorithm. Technical Report 6/2/1994, Michigan State University. Available at http://www.egr.msu.edu/˜pei/paper/GApaper94-02.ps. Last access on 03/28/2006.
Sousa, F. L., Ramos, F. M., Paglione, P., and Girardi, R. M. (2003). New Stochastic Algorithm for Design Optimization. AIAA Journal, 41(9):1808–1818.
Sousa, F. L., Vlassov, V., and Ramos, F. M. (2004). Generalized Extremal Optimization: An application in Heat Pipe Design. Applied Mathematical Modeling, 28:911–931.
Sthamer, H. (1996). The Automatic Generation of Software Test Data Using Genetic Algorithms. PhD thesis, University of Glamorgan, Pontyprid, Wales, Great Britain.
Tracey, N., Clark, J., and Mander, K. (1998). Automated program flaw finding using simulated annealing. SIGSOFT Softw. Eng. Notes, 23(2):73–81.
Watkins, A. and Hufnagel, E. M. (2006). Evolutionary test data generation: a comparison of fitness functions. Software Practice and Experience, 36(1):95–116.
Wikipedia (2006). Computer Bugs. Available at http://en.wikipedia.org/wiki/Computer_bugs. Last access on 01/14/2007.
Publicado
15/10/2007
Como Citar
ABREU, Bruno T. de; MARTINS, Eliane; SOUSA, Fabiano L. de.
Generalized Extremal Optimization: a competitive algorithm for test data generation. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SOFTWARE (SBES), 21. , 2007, João Pessoa.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 342-358.
DOI: https://doi.org/10.5753/sbes.2007.21315.
