Abstract
We propose a bounded incremental algorithm to generate test cases for deterministic finite state machine models. Our approach, in contrast to the traditional view, is based on the observation that system specifications are in most cases modified incrementally in practice as requirements evolve. We utilize an existing test set available for a previous version of the system to efficiently generate tests for the current – modified – system.
We use a widely accepted framework to evaluate the complexity of the proposed incremental algorithm, and show that it is a function of the size of the change in the specification rather than the size of the specification itself. Thus, the method is very efficient in the case of small changes, and never performs worse than the relevant traditional algorithm – the HIS-method. We also demonstrate our algorithm through an example.
Chapter PDF
Similar content being viewed by others
References
Ramalingam, G., Reps, T.: On the computational complexity of dynamic graph problems. Theoretical Computer Science 158(1-2), 233–277 (1996)
Sabnani, K., Dahbura, A.: A protocol test generation procedure. Computer Networks and ISDN Systems 15(4), 285–297 (1988)
Yannakakis, M., Lee, D.: Testing finite state machines: fault detection. In: Selected papers of the 23rd annual ACM symposium on Theory of computing, pp. 209–227 (1995)
Petrenko, A., Yevtushenko, N., Lebedev, A., Das, A.: Nondeterministic state machines in protocol conformance testing. In: Proceedings of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test systems, vol. VI, pp. 363–378 (1994)
Subramaniam, M., Pap, Z.: Analyzing the impact of protocol changes on tests. In: Uyar, M.Ü., Duale, A.Y., Fecko, M.A. (eds.) TestCom 2006. LNCS, vol. 3964, pp. 197–212. Springer, Heidelberg (2006)
Friedman, A.D., Menon, P.R.: Fault Detection in Digital Circuits. Prentice-Hall, Englewood Cliffs (1971)
Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley, London (1986)
Holzmann, G.J.: Design and Validation of Protocols. Prentice-Hall, Englewood Cliffs (1990)
ITU-T: Recommendation Z.100: Specification and description language (2000)
TC97/SC21, I.: Estelle – a formal description technique based on an extended state transition model. international standard 9074 (1988)
Subramaniam, M., Chundi, P.: An approach to preserve protocol consistency and executability across updates. In: Davies, J., Schulte, W., Barnett, M. (eds.) ICFEM 2004. LNCS, vol. 3308, pp. 341–356. Springer, Heidelberg (2004)
Pap, Z., Csopaki, G., Dibuz, S.: On the theory of patching. In: Proceedings of the 3rd IEEE International Conference on Software Engineering and Formal Methods, SEFM, pp. 263–271 (2005)
Lee, D., Yiannakakis, M.: Principles and methods of testing finite state machines – a survey. Proceedings of the IEEE 84(8), 1090–1123 (1996)
Bochmann, G.V., Petrenko, A.: Protocol testing: review of methods and relevance for software testing. In: ISSTA 1994. Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, pp. 109–124. ACM Press, New York, USA (1994)
Chow, T.: Testing software design modelled by finite-state machines. IEEE Transactions on Software Engineering 4(3), 178–187 (1978)
Fujiwara, S., Bochmann, G.v., Khendec, F., Amalou, M., Ghedamsi, A.: Test selection based on finite state model. IEEE Transactions on Software Engenieering 17, 591–603 (1991)
Kohavi, Z.: Switching and Finite Automata Theory. McGraw-Hill, New York (1978)
El-Fakih, K., Yevtushenko, N., von Bochmann, G.: FSM-based incremental conformance testing methods. IEEE Transactions on Software Engineering 30(7), 425–436 (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 IFIP International Federation for Information Processing
About this paper
Cite this paper
Pap, Z., Subramaniam, M., Kovács, G., Németh, G.Á. (2007). A Bounded Incremental Test Generation Algorithm for Finite State Machines. In: Petrenko, A., Veanes, M., Tretmans, J., Grieskamp, W. (eds) Testing of Software and Communicating Systems. FATES TestCom 2007 2007. Lecture Notes in Computer Science, vol 4581. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73066-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-73066-8_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73065-1
Online ISBN: 978-3-540-73066-8
eBook Packages: Computer ScienceComputer Science (R0)