Redução do Número de Seqüências no Teste de Conformidade de Protocolos

• Jorge Francisco Cutigi USP
• Paulo Henrique Ribeiro USP
• Adenilso da Silva Simão USP
• Simone do Rocio Senger de Souza USP

DOI: https://doi.org/10.5753/wtf.2010.23099

Abstract

Formal specification is a very important step in the development process of protocol, since the specification can be used as basis to the implementation and the conformance testing. Among formal models for protocol specification, Finite State Machines have been often used. This model allows obtaining test sequences for the specified protocol. Several test generation methods have been developed in past decades, aiming at obtaining a test suite that is able to reveal implementation faults. Nevertheless, most of the generated test suites are huge, with a large number of sequences. In this paper, we present an approach to reduce sequences in a test suite. The main goal is the reduction of the number of sequences, since the large number of sequences can turn the test activity impracticable. We present experimental results, which show that the approach reduces the number of sequences while maintaining the effectiveness in revealing faults.

References

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.