Abstract
Finite state machine-based testing aims at generating checking sequences that guarantee the conformance between the implementation and the specification of a system. For that purpose, several methods have been proposed to generate checking sequences which ensure full coverage of possible faults in the implementation. Many existing methods are based on a special sequence, called distinguishing sequence, which does not exist for every minimal machine. Some methods are based on characterization sets since they exist for every machine. However, these methods generate checking sequences exponentially long. In this paper, we propose a method to generate checking sequences using identification sets. These sets exist for every minimal FSM and also lead to shorter checking sequences. We conducted an experimental study to compare the proposed method with the existing methods. The results show that on average our method generates checking sequences 31.7% to 99.9% shorter than the ones produced by existing methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A., Dahbura, A., Lee, D., Uyar, M.: An optimization technique for protocol conformance test generation based on uio sequences and rural chinese postman tours. IEEE Transactions on Communications 39, 1604–1615 (1991)
Boute, R.T.: Distinguishing sets for optimal state identification in checking experiments. IEEE Transactions on Computers 23, 874–877 (1974)
Chen, J., Hierons, R.M., Ural, H., Yenigun, H.: Eliminating redundant tests in a checking sequence. In: Khendek, F., Dssouli, R. (eds.) TestCom 2005. LNCS, vol. 3502, pp. 146–158. Springer, Heidelberg (2005)
Endo, A.T., Simao, A.: Evaluating test suite characteristics, cost, and effectiveness of FSM-based testing methods. Information and Software Technology 55(6), 1045–1062 (2013)
Fujiwara, S., van Bochmann, G., Khendek, F., Amalou, M., Ghedamsi, A.: Test selection based on finite state models. IEEE Transactions on Software Engineering 17, 591–603 (1991)
Gill, A.: Introduction to the theory of finite state machines. McGraw-Hill, New York (1962)
Gonenc, G.: A method for the design of fault detection experiments. IEEE Transactions on Computers 19, 551–558 (1970)
Hennie, F.C.: Fault detecting experiments for sequential circuits. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 95–110 (1964)
Hierons, R.M., Ural, H.: Optimizing the length of checking sequences. IEEE Transactions on Computers 55, 618–629 (2006)
Hierons, R.M., Bogdanov, K., Bowen, J.P., Cleaveland, R., Derrick, J., Dick, J., Gheorghe, M., Harman, M., Kapoor, K., Krause, P., Lüttgen, G., Simons, A.J.H., Vilkomir, S., Woodward, M.R., Zedan, H.: Using formal specifications to support testing. ACM Computing Surveys 41, 1–76 (2009)
Hierons, R.M., Ural, H.: Reduced length checking sequences. IEEE Transactions on Computers 51, 93–99 (2002)
Lee, D., Yannakakis, M.: Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE 84, 1090–1123 (1996)
Moore, E.F.: Gedanken Experiments on Sequential Machines. In: Automata Studies. Annals of Mathematical Studies, vol. 34, pp. 129–153 (1956)
R-Project: The R project for statistical computing (2013), http://www.r-project.org/
Rezaki, A., Ural, H.: Construction of checking sequences based on characterization sets. Computer Communications 18, 911–920 (1995)
Simão, A.S., Petrenko, A.: Generating checking sequences for partial reduced finite state machines. In: Suzuki, K., Higashino, T., Ulrich, A., Hasegawa, T. (eds.) TestCom/FATES 2008. LNCS, vol. 5047, pp. 153–168. Springer, Heidelberg (2008)
Simao, A., Petrenko, A.: Checking sequence generation using state distinguishing subsequences. In: The IEEE International Conference on Software Testing, Verification, and Validation Workshops, pp. 48–56 (2009)
Ural, H., Wu, X., Zhang, F.: On minimizing the lengths of checking sequences. IEEE Transactions on Computers 46, 93–99 (1997)
Ural, H., Zhang, F.: Reducing the lengths of checking sequences by overlapping. In: Uyar, M.Ü., Duale, A.Y., Fecko, M.A. (eds.) TestCom 2006. LNCS, vol. 3964, pp. 274–288. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Porto, F.R., Endo, A.T., Simao, A. (2013). Generation of Checking Sequences Using Identification Sets. In: Groves, L., Sun, J. (eds) Formal Methods and Software Engineering. ICFEM 2013. Lecture Notes in Computer Science, vol 8144. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41202-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-41202-8_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41201-1
Online ISBN: 978-3-642-41202-8
eBook Packages: Computer ScienceComputer Science (R0)