Redução do Número de Seqüências no Teste de Conformidade de Protocolos
Resumo
A especificação formal é uma etapa crucial no ciclo de desenvolvimento de protocolos, uma vez que ela pode ser usada como base para a implementação e para o teste de conformidade. Dentre os modelos formais de especificação de protocolos, as Máquinas de Estados Finitos têm sido muito utilizadas. Esse modelo permite a derivação de seqüências de teste para o protocolo especificado. Vários métodos de geração de seqüências de teste têm sido desenvolvidos há várias décadas, com o objetivo de obter um conjunto de teste que seja capaz de revelar os defeitos de uma implementação. Entretanto, muitas vezes os conjuntos gerados são muito grandes e possuem um grande número de seqüências. Neste artigo é apresentada uma abordagem de redução de seqüências de teste. Busca-se como objetivo principal a redução do número de seqüências do conjunto de teste, uma vez que o grande número de seqüências pode tornar o teste inviável. São apresentados os resultados de dois estudos experimentais, os quais mostram ganhos consideráveis na redução de seqüências nos conjuntos de teste, mantendo a efetividade em revelar defeitos.
Referências
Bochmann, G. V. and Petrenko, A. (1994). Protocol testing: review of methods and relevance for software testing. In ISSTA ’94: Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, pages 109–124, New York, NY, USA. ACM.
Chen, J., Hierons, R. M., Ural, H., and Yenigun, H. (2005). Eliminating redundant tests in a checking sequence. In TestCom 2005, number 3502 in lncs, pages 146–158.
Chow, T. S. (1978). Testing software design modeled by finite-state-machines. IEEE Transactions on Software Engineering, 4(3):178–186.
Dorofeeva, R., El-Fakih, K., and Yevtushenko, N. (2005). An improved conformance testing method. In FORTE, pages 204–218.
Fujiwara, S., Bochman, G. V., Khendek, F., Amalou, M., and Ghedamsi, A. (1991). Test selection based on finite state models. IEEE Transactions on Software Engineering, 17(6):591–603.
Gill, A. (1962). Introduction to the Theory of Finite-State Machines. McGraw-Hill, New York.
Gonenc, G. (1970). A method for design of fault detection experiments. IEEE Transactions on Computers, 19(6):551–558.
Hennie, F. C. (1964). Fault detecting experiments for sequential circuits. pages 95–110.
Hierons, R. M. (2004). Using a minimal number of resets when testing from a finite state machine. Inf. Process. Lett., 90(6):287–292.
Hierons, R. M. and Ural, H. (2002). Reduced length checking sequences. IEEE Transactions on Computers, 51(9):1111–1117.
Hierons, R. M. and Ural, H. (2006). Optimizing the length of checking sequences. IEEE Transactions on Computers, 55(5):618–629.
Hogrefe, D. (1991). Osi formal speci cation case study: the inres protocol and service. Technical report, University of Bern.
Lee, D. and Yannakakis, M. (1994). Testing finite-state machines: State identification and verification. IEEE Trans. Comput., 43(3):306–320.
Luo, G., Petrenko, R., and Bochmann, G. V. (1994). Selecting test sequences for partially-specified nondeterministic finite state machines. In In IFIP 7th International Workshop on Protocol Test Systems, pages 91–106.
McGill, R., Tukey, J. W., and Larsen, W. A. (1978). Variations of box plots. The American Statistician, 32(1):12–16.
Petrenko, A., von Bochmann, G., and Yao, M. Y. (1996). On fault coverage of tests for finite state specifications. Computer Networks and ISDN Systems, 29(1):81–106.
Petrenko, A., Yevtushenko, N., Lebedev, A., and Das, A. (1993). Nondeterministic state machines in protocol conformance testing. In Protocol Test Systems, pages 363–378.
Sidhu, D., Chung, A., and Blumer, T. P. (1991). Experience with formal methods in protocol development. SIGCOMM Comput. Commun. Rev., 21(2):81–101.
Simao, A. S. and Petrenko, A. (2008). Generating checking sequences for partial reduced finite state machines. In TestCom ’08 / FATES ’08: Proceedings of the 20th IFIP TC 6/WG 6.1 international conference on Testing of Software and Communicating Systems, pages 153–168, Berlin, Heidelberg. Springer-Verlag.
Simao, A. S. and Petrenko, A. (2009). Checking fsm test completeness based on sufficient conditions. IEEE Transactions on Computers. (Aceito para publicacao. Versão preliminar disponível em: [link]).
Tan, Q. M., Petrenko, A., and Bochmann, G. V. (1996). A test generation tool for specifications in the form of state machines. In in Proceedings of the International Communications Conference, pages 225–229.
Ural, H., Wu, X., and Zhang, F. (1997). On minimizing the lengths of checking sequences. IEEE Transactions on Computers, 46(1):93–99.
Ural, H. and Zhang, F. (2006). Reducing the lengths of checking sequences by overlapping. Lecture Notes on Computer Science, (3964):274–288.
Yao, M., Petrenko, A., and Bochmann, G. v. (1993). Conformance testing of protocol machines without reset. In Proceedings of the IFIP TC6/WG6.1 Thirteenth International Symposium on Protocol Specification, Testing and Verification XIII,pages 241–256, Amsterdam, The Netherlands, The Netherlands. North-Holland Publishing Co.
Chen, J., Hierons, R. M., Ural, H., and Yenigun, H. (2005). Eliminating redundant tests in a checking sequence. In TestCom 2005, number 3502 in lncs, pages 146–158.
Chow, T. S. (1978). Testing software design modeled by finite-state-machines. IEEE Transactions on Software Engineering, 4(3):178–186.
Dorofeeva, R., El-Fakih, K., and Yevtushenko, N. (2005). An improved conformance testing method. In FORTE, pages 204–218.
Fujiwara, S., Bochman, G. V., Khendek, F., Amalou, M., and Ghedamsi, A. (1991). Test selection based on finite state models. IEEE Transactions on Software Engineering, 17(6):591–603.
Gill, A. (1962). Introduction to the Theory of Finite-State Machines. McGraw-Hill, New York.
Gonenc, G. (1970). A method for design of fault detection experiments. IEEE Transactions on Computers, 19(6):551–558.
Hennie, F. C. (1964). Fault detecting experiments for sequential circuits. pages 95–110.
Hierons, R. M. (2004). Using a minimal number of resets when testing from a finite state machine. Inf. Process. Lett., 90(6):287–292.
Hierons, R. M. and Ural, H. (2002). Reduced length checking sequences. IEEE Transactions on Computers, 51(9):1111–1117.
Hierons, R. M. and Ural, H. (2006). Optimizing the length of checking sequences. IEEE Transactions on Computers, 55(5):618–629.
Hogrefe, D. (1991). Osi formal speci cation case study: the inres protocol and service. Technical report, University of Bern.
Lee, D. and Yannakakis, M. (1994). Testing finite-state machines: State identification and verification. IEEE Trans. Comput., 43(3):306–320.
Luo, G., Petrenko, R., and Bochmann, G. V. (1994). Selecting test sequences for partially-specified nondeterministic finite state machines. In In IFIP 7th International Workshop on Protocol Test Systems, pages 91–106.
McGill, R., Tukey, J. W., and Larsen, W. A. (1978). Variations of box plots. The American Statistician, 32(1):12–16.
Petrenko, A., von Bochmann, G., and Yao, M. Y. (1996). On fault coverage of tests for finite state specifications. Computer Networks and ISDN Systems, 29(1):81–106.
Petrenko, A., Yevtushenko, N., Lebedev, A., and Das, A. (1993). Nondeterministic state machines in protocol conformance testing. In Protocol Test Systems, pages 363–378.
Sidhu, D., Chung, A., and Blumer, T. P. (1991). Experience with formal methods in protocol development. SIGCOMM Comput. Commun. Rev., 21(2):81–101.
Simao, A. S. and Petrenko, A. (2008). Generating checking sequences for partial reduced finite state machines. In TestCom ’08 / FATES ’08: Proceedings of the 20th IFIP TC 6/WG 6.1 international conference on Testing of Software and Communicating Systems, pages 153–168, Berlin, Heidelberg. Springer-Verlag.
Simao, A. S. and Petrenko, A. (2009). Checking fsm test completeness based on sufficient conditions. IEEE Transactions on Computers. (Aceito para publicacao. Versão preliminar disponível em: [link]).
Tan, Q. M., Petrenko, A., and Bochmann, G. V. (1996). A test generation tool for specifications in the form of state machines. In in Proceedings of the International Communications Conference, pages 225–229.
Ural, H., Wu, X., and Zhang, F. (1997). On minimizing the lengths of checking sequences. IEEE Transactions on Computers, 46(1):93–99.
Ural, H. and Zhang, F. (2006). Reducing the lengths of checking sequences by overlapping. Lecture Notes on Computer Science, (3964):274–288.
Yao, M., Petrenko, A., and Bochmann, G. v. (1993). Conformance testing of protocol machines without reset. In Proceedings of the IFIP TC6/WG6.1 Thirteenth International Symposium on Protocol Specification, Testing and Verification XIII,pages 241–256, Amsterdam, The Netherlands, The Netherlands. North-Holland Publishing Co.
Publicado
28/05/2010
Como Citar
CUTIGI, Jorge Francisco; RIBEIRO, Paulo Henrique; SIMÃO, Adenilso da Silva; SOUZA, Simone do Rocio Senger de.
Redução do Número de Seqüências no Teste de Conformidade de Protocolos. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 11. , 2010, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2010
.
p. 105-117.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2010.23099.
