A comparative study of algorithms for generating switch cover test sets
Resumo
Test case generation based on Finite State Machines (FSMs) has been extensively investigated due to its accuracy and simplicity. Several test criteria have been proposed in the literature to generate test cases based on FSMs. One of the oldest criteria is the Switch Cover. As a main feature, the Switch Cover criterion defines that all transition pairs of an FSM must be covered. The classical Switch Cover algorithm converts the FSM into a graph (known as Dual Graph); this graph is balanced, and, finally, traversed based on an Eulerian Cycle algorithm. In this context, considering the stage where an FSM is converted into a graph, this study investigates other search algorithms on graphs, namely Depth-First Search (DFS) and Breadth-First Search (BFS), for generating test sets from a Dual Graph. We presented an experimental study that compares the DFS, BFS algorithms with the Eulerian Cycle. The study was conducted with a set of random and real-world machines, taking into account the number of test cases, the test suite size, the average length of sequences and generation time.
Palavras-chave:
comparative study, algorithms, cover test sets
Referências
Arantes, A., Santiago, V. A. J., Vijaykumar, N. L., and Souza, E. F. (2014). Tool support for generating model-based test cases via web. International Journal of Web Engineering and Technology, 9:62–96.
Arantes, A. O., Vijaykumar, N. L., Santiago, V. A. J., and Guimaraes, D. (2008). Test Case Generation for Critical Systems through a Collaborative Web-based Tool. In International conference on inovation in software engineering (ISE), pages 163–168.
Bang-Jensen, J. and Gutin, G. Z. (2009). Digraphs: Theory, Algorithms and Applications. Springer, 2 edition.
Bondy, J. and Murty, U. (2008). Graduate Texts in Mathematics: Graph Theory. Springer, USA.
De Bruijn, N. G. (1946). A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen, 49:758–764.
Dorofeeva, R., El-Fakih, K., Maag, S., Cavalli, A., and Yevtushenko, N. (2010). FSMbased conformance testing methods: a survey annotated with experimental evaluation.Information and Software Technology, 52:1286–1297. Dorofeeva, R., El-Fakih, K., and Yevtushenko, N. (2005). An improved conformance
Dorofeeva, R., El-Fakih, K., and Yevtushenko, N. (2005). An improved conformance testing method. In International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), pages 204–218.
El-Far, I. K. and Whittaker, J. A. (2001). Model-based software testing. In Encyclopedia on Software Engineering, pages 825–837.
Endo, A. and Simao, A. (2013). Evaluating test suite characteristics, cost, and effectiveness of FSM-based testing methods. Information and Software Technology, 55(6):1045–1062.
Gill, A. (1962). Introduction to the Theory of Finite-State Machines. McGraw-Hill, New York.
Guney, G. (1970). A method for the design of fault detection experiments. IEEE Transactions on Computers, 19:551–558.
Martins, E., Sabiao, S. B., and Ambrosio, A. M. (1999). ConData: a tool for automating specification-based test case generation for communication systems. In International Conference on System Sciences, pages 303–319.
Naito, S. and Tsunoyama, M. (1981). Fault detection for sequential machines by transition tours. In Fault Tolerant Computing Conference (FTCS), pages 238–243.
Neumann, F. (2004). Expected runtimes of evolutionary algorithms for the eulerian cycle problem. In Congress on Evolutionary Computation, pages 904–910.
Petrenko, A. and Yevtushenko, N. (2005). Testing from partial deterministic FSM specifications. IEEE Transactions on Computers, 54:1154–1165.
Pimont, S. and Rault, J. (1976). A software reliability assessment based on a structural and behavioral analysis of programs. In International Conference on Software Engineering (ICSE), pages 486–491.
Pinheiro, A. C., Simao, A., and Ambrosio, A. M. (2014). FSM-Based Test Case Generation Methods Applied to Test the Communication Software on Board the ITASAT University Satellite: A Case Study. Journal of Aerospace Technology and Management, 6:447–461.
Pontes, R. P., Veras, P. C., Ambrosio, A. M., and Villani, E. (2014). Contributions of model checking and CoFI methodology to the development of space embedded software. Empirical Software Engineering, 19:39–68.
Sabnani, K. K. (1988). A protocol test generation procedure. Computer networks and ISDN systems, 15:285–297.
Santiago, V., Mattiello, F., Costa, R., Silva, W. P., and Ambrosio, A. M. (2007). QSEE project: An experience in outsourcing software development for space. In Int. conference on software engineering and knowledge engineering, pages 183–188.
Santiago, V. A. J. (2011). SOLIMVA: A methodology for generating model-based test cases from natural language requirements and detecting incompleteness in software specifications. PhD thesis, National Institute for Space Research (INPE), Doctorate at Post Graduation Course in Applied Computing. Sao Jos e dos Campos, SP, Brazil.
Shi, Q., Chen, Z., Fang, C., Feng, Y., and Xu, B. (2016). Measuring the Diversity of a Test Set With Distance Entropy. IEEE Transactions on Reliability, 65(1):19–27.
Sidhu, D. P. and Leung, T. (1989). Formal methods for protocol testing: A detailed study. Transactions on Software Engineering, 15:413–426.
Simao, A., Petrenko, A., and Maldonado, J. (2009). Comparing finite state machine test coverage criteria. IET Software, 3:91–105.
Simao, A., Petrenko, A., and Maldonado, J. (2010). Fault coverage-driven incremental test generation. Computer Journal, 53:1508–1522.
Souza, E. F., Santiago, V. A. J., Guimar aes, D., and Vijaykumar, N. L. (2008). Evaluation of test criteria for space application software modeling in statecharts. In International conference on innovation in software engineering, pages 157–162.
Utting, M. and Legeard, B. (2006). Practical Model-Based Testing. Morgan Kaufmann Publishers Inc, San Francisco, CA, USA.
Zhang, X., M., Y., Geng, G., and Luo, W. (2011). A DFSM-Based Protocol Conformance Testing and Diagnosing Method. Informatica, 22:447–469.
Arantes, A. O., Vijaykumar, N. L., Santiago, V. A. J., and Guimaraes, D. (2008). Test Case Generation for Critical Systems through a Collaborative Web-based Tool. In International conference on inovation in software engineering (ISE), pages 163–168.
Bang-Jensen, J. and Gutin, G. Z. (2009). Digraphs: Theory, Algorithms and Applications. Springer, 2 edition.
Bondy, J. and Murty, U. (2008). Graduate Texts in Mathematics: Graph Theory. Springer, USA.
De Bruijn, N. G. (1946). A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen, 49:758–764.
Dorofeeva, R., El-Fakih, K., Maag, S., Cavalli, A., and Yevtushenko, N. (2010). FSMbased conformance testing methods: a survey annotated with experimental evaluation.Information and Software Technology, 52:1286–1297. Dorofeeva, R., El-Fakih, K., and Yevtushenko, N. (2005). An improved conformance
Dorofeeva, R., El-Fakih, K., and Yevtushenko, N. (2005). An improved conformance testing method. In International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), pages 204–218.
El-Far, I. K. and Whittaker, J. A. (2001). Model-based software testing. In Encyclopedia on Software Engineering, pages 825–837.
Endo, A. and Simao, A. (2013). Evaluating test suite characteristics, cost, and effectiveness of FSM-based testing methods. Information and Software Technology, 55(6):1045–1062.
Gill, A. (1962). Introduction to the Theory of Finite-State Machines. McGraw-Hill, New York.
Guney, G. (1970). A method for the design of fault detection experiments. IEEE Transactions on Computers, 19:551–558.
Martins, E., Sabiao, S. B., and Ambrosio, A. M. (1999). ConData: a tool for automating specification-based test case generation for communication systems. In International Conference on System Sciences, pages 303–319.
Naito, S. and Tsunoyama, M. (1981). Fault detection for sequential machines by transition tours. In Fault Tolerant Computing Conference (FTCS), pages 238–243.
Neumann, F. (2004). Expected runtimes of evolutionary algorithms for the eulerian cycle problem. In Congress on Evolutionary Computation, pages 904–910.
Petrenko, A. and Yevtushenko, N. (2005). Testing from partial deterministic FSM specifications. IEEE Transactions on Computers, 54:1154–1165.
Pimont, S. and Rault, J. (1976). A software reliability assessment based on a structural and behavioral analysis of programs. In International Conference on Software Engineering (ICSE), pages 486–491.
Pinheiro, A. C., Simao, A., and Ambrosio, A. M. (2014). FSM-Based Test Case Generation Methods Applied to Test the Communication Software on Board the ITASAT University Satellite: A Case Study. Journal of Aerospace Technology and Management, 6:447–461.
Pontes, R. P., Veras, P. C., Ambrosio, A. M., and Villani, E. (2014). Contributions of model checking and CoFI methodology to the development of space embedded software. Empirical Software Engineering, 19:39–68.
Sabnani, K. K. (1988). A protocol test generation procedure. Computer networks and ISDN systems, 15:285–297.
Santiago, V., Mattiello, F., Costa, R., Silva, W. P., and Ambrosio, A. M. (2007). QSEE project: An experience in outsourcing software development for space. In Int. conference on software engineering and knowledge engineering, pages 183–188.
Santiago, V. A. J. (2011). SOLIMVA: A methodology for generating model-based test cases from natural language requirements and detecting incompleteness in software specifications. PhD thesis, National Institute for Space Research (INPE), Doctorate at Post Graduation Course in Applied Computing. Sao Jos e dos Campos, SP, Brazil.
Shi, Q., Chen, Z., Fang, C., Feng, Y., and Xu, B. (2016). Measuring the Diversity of a Test Set With Distance Entropy. IEEE Transactions on Reliability, 65(1):19–27.
Sidhu, D. P. and Leung, T. (1989). Formal methods for protocol testing: A detailed study. Transactions on Software Engineering, 15:413–426.
Simao, A., Petrenko, A., and Maldonado, J. (2009). Comparing finite state machine test coverage criteria. IET Software, 3:91–105.
Simao, A., Petrenko, A., and Maldonado, J. (2010). Fault coverage-driven incremental test generation. Computer Journal, 53:1508–1522.
Souza, E. F., Santiago, V. A. J., Guimar aes, D., and Vijaykumar, N. L. (2008). Evaluation of test criteria for space application software modeling in statecharts. In International conference on innovation in software engineering, pages 157–162.
Utting, M. and Legeard, B. (2006). Practical Model-Based Testing. Morgan Kaufmann Publishers Inc, San Francisco, CA, USA.
Zhang, X., M., Y., Geng, G., and Luo, W. (2011). A DFSM-Based Protocol Conformance Testing and Diagnosing Method. Informatica, 22:447–469.
Publicado
24/10/2016
Como Citar
MARIANO, Matheus Monteiro; SOUZA, Érica Ferreira; ENDO, André Takeshi; VIJAYKUMAR, Nandamudi L..
A comparative study of algorithms for generating switch cover test sets. In: SIMPÓSIO BRASILEIRO DE QUALIDADE DE SOFTWARE (SBQS), 15. , 2016, Maceió.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 6-20.
DOI: https://doi.org/10.5753/sbqs.2016.15122.
