Abstract
A method is presented for deriving test suites with the guaranteed fault coverage for deterministic possibly partial Timed Finite State Machines (TFSMs). TFSMs have integer boundaries for time guards and the time reset operation at every transition; for TFSM implementations the upper bound on the number of states is known as well as the largest finite boundary and the smallest duration of time guards. We consider two fault models and present corresponding techniques for deriving complete test suites. In the first fault model inputs can be applied at integer time instances while in the second fault model time instances can be rational. The derivation method for integer time instances is extended to the case when the number of states of an implementation under test can be larger than the number of states of the given specification.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alur, R., Dill, D.L.: A Theory of Timed automata. Theoretical Computer Science 126(2), 183–235 (1994)
Bochmann, G.v., Petrenko, A.: Protocol Testing: Review of Methods and Relevance for Software Testing. In: International Symposium on Software Testing and Analysis, Seattle, pp. 109–123 (1994)
Chow, T.S.: Test Design Modeled by Finite-state Machines. IEEE TSE 4(3), 178–187 (1978)
Dorofeeva, R., El-Fakih, K., Yevtushenko, N.: An Improved Conformance Testing Method. In: Wang, F. (ed.) FORTE 2005. LNCS, vol. 3731, pp. 204–218. Springer, Heidelberg (2005)
En-Nouaary, A., Dssouli, R., Khendek, F.: Timed Wp-Method: Testing Real-Time Systems. IEEE TSE 28(11), 1023–1038 (2002)
Fujiwara, S., Bochmann, G.v., Khendek, F., Amalou, M., Ghedamsi, A.: Test Selection Based on Finite State Models. IEEE Trans. SE 17(6), 591–603 (1991)
Gromov, M., El-Fakih, K., Shabaldina, N., Yevtushenko, N.: Distinguishing Non-deterministic Timed Finite State Machines. In: 11th Formal Methods for Open Object-Based Distributed Systems and 29th Formal Techniques for Networked and Distributed Systems, FMOODS/FORTE. LNCS, vol. 5522, pp. 137–151. Springer, Heidelberg (2009)
Hierons, R.M., Merayo, M.G., Nunez: Testing from a Stochastic Timed System with a Fault Model. Journal of Logic and Algebraic Programming 72(8), 98–115 (2009)
Lee, D., Yannakakis, M.: Principles and Methods of Testing Finite State Machines-A Survey. Proc. of the IEEE 84(8), 1090–1123 (1996)
Merayo, M.G., Nunez, M., Rodriguez, I.: Formal Testing from Timed Finite State Machines. Computer Networks 52(2), 432–460 (2008)
Petrenko, A.: Checking Experiments with Protocol Machines. In: Proc. 4th Int. Workshop on Protocol Test Systems (IWPTS), pp. 83–94 (1991)
Petrenko, A., Yevtushenko, N.: Testing from Partial Deterministic FSM Specifications. IEEE Trans. Computers 54(9), 1154–1165 (2005)
Petrenko, A., Yevtushenko, N., Lebedev, A., Das, A.: Nondeterministic State Machines in Protocol Conformance Testing. In: Proc. of the IFIP 6th IWPTS, France, pp. 363–378 (1993)
Springintveld, J., Vaandrager, F., D’Argenio, P.: Testing Timed Automata. Theoretical Computer Science 254(1-2), 225–257 (2001)
Vasilevskii, M.P.: Failure Diagnosis of Automata. translated from Kibernetika 4, 98–108 (1973)
Yevtushenko, N., Petrenko, A.: Test derivation method for an arbitrary deterministic automaton. In: Automatic Control and Computer Science, vol. 5. Allerton Press Inc., USA (1990)
Yannakakis, M., Lee, D.: Testing Finite State Machines: Fault Detection. Journal of Computer and System Sciences 50, 209–227 (1995)
Cardell-Oliver, R., Glover, T.: A Practical and Complete Algorithm for Testing Real-Time Systems. Formal Techniques for Real-Time Fault Tolerant Systems (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
El-Fakih, K., Yevtushenko, N., Fouchal, H. (2009). Testing Timed Finite State Machines with Guaranteed Fault Coverage. In: Núñez, M., Baker, P., Merayo, M.G. (eds) Testing of Software and Communication Systems. FATES TestCom 2009 2009. Lecture Notes in Computer Science, vol 5826. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-05031-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-05031-2_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-05030-5
Online ISBN: 978-3-642-05031-2
eBook Packages: Computer ScienceComputer Science (R0)