Automatic test data generation for path testing using a new stochastic algorithm
Resumo
O teste de software é uma atividade importante do processo de desenvolvimento de software, e automatizar a geração de dados de teste contribui para a redução de esforço de custo e tempo. O teste de caminhos é um problema complexo e metaheurísticas foram propostas para lidar com ele. Neste artigo é feita uma avaliação inicial da eficácia de uma metaheurística proposta recentemente, a Otimização Extrema Generalizada, no tratamento deste tipo de problema. Os resultados mostram que ela pode ser competitiva com a tão utilizada metaheurística chamada Algoritmo Genético, exigindo muito menos esforço na definição dos parâmetros e tornando-a uma alternativa a este método no teste de caminhos.
Palavras-chave:
Testes de software, Geração automática de dados de testes, Algoritmos evolutivos, Teste de caminhos
Referências
Bak, P. (1996). How Nature Works: The Science of Self-Organized Criticality. Springer.
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.
Beizer, B. (1995). Black-Box Testing. John Wiley & Sons.
Berndt, D., Fisher, J., Johnson, L., Pinglikar, J., and Watkins, A. (2003). Breeding Software Test Cases with Genetic Algorithms. In 36th Annual Hawaii Int. Conference on System Sciences (HICSS'03).
Binder, R. V. (2000). Testing Object-Oriented Systems: Models, Patterns, and Tools. Addison-Wesley.
Boettcher, S. and Percus, A. G. (2001). Optimization with Extremal Dynamics. Physical Review Letters, 86:5211-5214.
Borgelt, K. (1999). Software Test Data Generation from a Genetic Algorithm. In Karr, C. L. and Freeman, L. M., editors, Industrial Applications of Genetic Algorithms, pages 49-68. CRC Press, Boca Raton, FL.
Clarke, L. A. (1976). A system to generate test data and symbolically execute programs. IEEE Trans. Software Eng., 2(3):215-222.
Deason, W. H., Brown, D. B., Chang, K. H., and II, J. H. C. (1991). A Rule-Based Software Test Data Generator. IEEE Trans. on Knowl. and Data Eng., 3(1):108-117.
Deb, K., Poli, R., Banzhaf, W., Beyer, H., Burke, E. K., Darwen, P. J., Dasgupta, D., Floreano, D., Foster, J. A., Harman, M., Holland, O., Lanzi, P. L., Spector, L., Tettamanzi, A., Thierens, D., and Tyrrell, A. M., editors (2004a). Genetic and Evolutionary Computation Conference GECCO, Seattle, WA, USA, 2004, Proceedings, Part I, volume 3102 of Lecture Notes in Computer Science. Springer.
Deb, K., Poli, R., Banzhaf, W., Beyer, H., Burke, E. K., Darwen, P. J., Dasgupta, D., Floreano, D., Foster, J. A., Harman, M., Holland, O., Lanzi, P. L., Spector, L., Tettamanzi, A., Thierens, D., and Tyrrell, A. M., editors (2004b). Genetic and Evolutionary Computation Conference GECCO, Seattle, WA, USA, June 26-30, 2004, Proceedings, Part II, volume 3103 of Lecture Notes in Computer Science. Springer.
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).
Godefroid, P. and Khurshid, S. (2002). Exploring Very Large State Spaces Using Genetic Algorithms. In TACAS '02: Proc. of the 8th Int. Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 266-280. Springer.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
Gould, S. J. and Eldredge, N. (1993). Punctuated equilibrium comes of age. Nature, 366:223-227.
Hajnal, A. and Forgács, I. (1998). An applicable test data generation algorithm for domain errors. In ISSTA '98: Proc. of the 1998 ACM SIGSOFT Int. Symposium on Software Testing and Analysis, pages 63-72, New York, NY, USA. ACM Press.
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
Korel, B. (1990). Automated Software Test Data Generation. IEEE Trans. Software Eng., 16(8):870-879.
Koza, J. R. (1992). Genetic Programming: On the programming of computers by means of natural selection. MIT Press.
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.
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. Software Eng., 27(12):1085-1110.
Myers, G. J. (1979). Art of Software Testing. John Wiley & Sons.
NIST (2000). National Institute of Standards and Technology. http://www.nist.gov. Last access on 03/13/2005.
Pargas, R. P., Harrold, M. J., and Peck, R. (1999). Test-Data Generation Using Genetic Algorithms. Software Testing, Verification & Reliability, 9(4):263-282.
Pressman, R. S. (1997). Software Engineering: A practitioner's approach. McGraw-Hill, 4th edition.
Sousa, F. L. (2002). Otimização Extrema Generalizada: Um novo algoritmo estocástico para o projeto ótimo. PhD thesis, Instituto Nacional de Pesquisas Espaciais (INPE). INPE-9564-TDI/836.
Sousa, F. L., Ramos, F. M., Galski, R. L., and Muraoka, I. (2004a). Generalized Extremal Optimization: A New Meta-heuristic Inspired by a Model of Natural Evolution. In L. N. de Castro, F. J. V. Z., editor, Recent Developments in Biologically Inspired Computing. Idea Group Inc.
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. (2004b). 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.
Wegener, J., Baresel, A., and Sthamer, H. (2001). Evolutionary test environment for automatic structural testing. Information & Software Technology, 43(14):841-854.
Whittaker, J. A. (2000). What is software testing? and why is it so hard? IEEE Software, 17(1):70-79.
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.
Beizer, B. (1995). Black-Box Testing. John Wiley & Sons.
Berndt, D., Fisher, J., Johnson, L., Pinglikar, J., and Watkins, A. (2003). Breeding Software Test Cases with Genetic Algorithms. In 36th Annual Hawaii Int. Conference on System Sciences (HICSS'03).
Binder, R. V. (2000). Testing Object-Oriented Systems: Models, Patterns, and Tools. Addison-Wesley.
Boettcher, S. and Percus, A. G. (2001). Optimization with Extremal Dynamics. Physical Review Letters, 86:5211-5214.
Borgelt, K. (1999). Software Test Data Generation from a Genetic Algorithm. In Karr, C. L. and Freeman, L. M., editors, Industrial Applications of Genetic Algorithms, pages 49-68. CRC Press, Boca Raton, FL.
Clarke, L. A. (1976). A system to generate test data and symbolically execute programs. IEEE Trans. Software Eng., 2(3):215-222.
Deason, W. H., Brown, D. B., Chang, K. H., and II, J. H. C. (1991). A Rule-Based Software Test Data Generator. IEEE Trans. on Knowl. and Data Eng., 3(1):108-117.
Deb, K., Poli, R., Banzhaf, W., Beyer, H., Burke, E. K., Darwen, P. J., Dasgupta, D., Floreano, D., Foster, J. A., Harman, M., Holland, O., Lanzi, P. L., Spector, L., Tettamanzi, A., Thierens, D., and Tyrrell, A. M., editors (2004a). Genetic and Evolutionary Computation Conference GECCO, Seattle, WA, USA, 2004, Proceedings, Part I, volume 3102 of Lecture Notes in Computer Science. Springer.
Deb, K., Poli, R., Banzhaf, W., Beyer, H., Burke, E. K., Darwen, P. J., Dasgupta, D., Floreano, D., Foster, J. A., Harman, M., Holland, O., Lanzi, P. L., Spector, L., Tettamanzi, A., Thierens, D., and Tyrrell, A. M., editors (2004b). Genetic and Evolutionary Computation Conference GECCO, Seattle, WA, USA, June 26-30, 2004, Proceedings, Part II, volume 3103 of Lecture Notes in Computer Science. Springer.
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).
Godefroid, P. and Khurshid, S. (2002). Exploring Very Large State Spaces Using Genetic Algorithms. In TACAS '02: Proc. of the 8th Int. Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 266-280. Springer.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
Gould, S. J. and Eldredge, N. (1993). Punctuated equilibrium comes of age. Nature, 366:223-227.
Hajnal, A. and Forgács, I. (1998). An applicable test data generation algorithm for domain errors. In ISSTA '98: Proc. of the 1998 ACM SIGSOFT Int. Symposium on Software Testing and Analysis, pages 63-72, New York, NY, USA. ACM Press.
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
Korel, B. (1990). Automated Software Test Data Generation. IEEE Trans. Software Eng., 16(8):870-879.
Koza, J. R. (1992). Genetic Programming: On the programming of computers by means of natural selection. MIT Press.
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.
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. Software Eng., 27(12):1085-1110.
Myers, G. J. (1979). Art of Software Testing. John Wiley & Sons.
NIST (2000). National Institute of Standards and Technology. http://www.nist.gov. Last access on 03/13/2005.
Pargas, R. P., Harrold, M. J., and Peck, R. (1999). Test-Data Generation Using Genetic Algorithms. Software Testing, Verification & Reliability, 9(4):263-282.
Pressman, R. S. (1997). Software Engineering: A practitioner's approach. McGraw-Hill, 4th edition.
Sousa, F. L. (2002). Otimização Extrema Generalizada: Um novo algoritmo estocástico para o projeto ótimo. PhD thesis, Instituto Nacional de Pesquisas Espaciais (INPE). INPE-9564-TDI/836.
Sousa, F. L., Ramos, F. M., Galski, R. L., and Muraoka, I. (2004a). Generalized Extremal Optimization: A New Meta-heuristic Inspired by a Model of Natural Evolution. In L. N. de Castro, F. J. V. Z., editor, Recent Developments in Biologically Inspired Computing. Idea Group Inc.
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. (2004b). 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.
Wegener, J., Baresel, A., and Sthamer, H. (2001). Evolutionary test environment for automatic structural testing. Information & Software Technology, 43(14):841-854.
Whittaker, J. A. (2000). What is software testing? and why is it so hard? IEEE Software, 17(1):70-79.
Publicado
03/10/2005
Como Citar
ABREU, Bruno T. de; MARTINS, Eliane; SOUSA, Fabiano L. de.
Automatic test data generation for path testing using a new stochastic algorithm. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SOFTWARE (SBES), 19. , 2005, Uberlândia/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2005
.
p. 247-262.
DOI: https://doi.org/10.5753/sbes.2005.23823.
