Abstract
Under certain well–defined conditions, determining the correctness of a system under test (SUT) is based on a checking sequence generated from a finite state machine (FSM) specification of the SUT. When there is a distinguishing sequence for the FSM, an efficient checking sequence may be produced from the elements of a set E α′ of α′-sequences that verify subsets of states and the elements of a set E C of subsequences that test the individual transitions. An optimization algorithm may be used in order to produce a shortest checking sequence by connecting the elements of E α′ and E C using transitions drawn from an acyclic set. Previous work did not consider whether some transition tests may be omitted from E C . This paper investigates the problem of eliminating subsequences from E C for those transitions that correspond to the last transitions traversed when a distinguishing sequence is applied in an α′–sequence to obtain a further reduction in the length of a checking sequence.
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
Tanenbaum, A.S.: Computer Networks, 3rd edn. Prentice Hall International Editions. Prentice Hall, Englewood Cliffs (1996)
Pomeranz, I., Reddy, S.M.: Test generation for multiple state–table faults in finite–state machines. IEEE Transactions on Computers 46, 783–794 (1997)
Hierons, R.M., Harman, M.: Testing conformance to a quasi–non–determinstic stream X–machine. Formal Aspects of Computing 12, 423–442 (2000)
Holcombe, M., Ipate, F.: Correct Systems: Building a Business Process Solution. Springer, Heidelberg (1998)
Luo, G., Das, A., van Bochmann, G.: Generating tests for control portion of SDL specifications. In: Proceedings of Protocol Test Systems VI, pp. 51–66. Elsevier (North-Holland), Amsterdam (1994)
Tan, Q.M., Petrenko, A., van Bochmann, G.: Modeling basic lotos by fsms for conformance testing. In: IFIP Protocol Specification, Testing, and Verification XV, pp. 137–152 (1995)
Ural, H., Saleh, K., Williams, A.: Test generation based on control and data dependencies within system specifications in SDL. Computer Communications 23, 609–627 (2000)
van Bochmann, G., Petrenko, A., Bellal, O., Maguiraga, S.: Automating the process of test derivation from SDL specifications. In: SDL Forum 1997, Paris, France (1997)
International Telecommunications Union Geneva, Switzerland: Recommendation Z.500 Framework on formal methods in conformance testing (1997)
Moore, E.P.: Gedanken-experiments. In: Shannon, C., McCarthy, J. (eds.) Automata Studies. Princeton University Press, Princeton (1956)
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: Proceedings of Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 95–110. Princeton, New Jersey (1964)
Hierons, R.M., Ural, H.: Reduced length checking sequences. IEEE Transactions on Computers 51, 1111–1117 (2002)
Ural, H., Wu, X., Zhang, F.: On minimizing the lengths of checking sequences. IEEE Transactions on Computers 46, 93–99 (1997)
Lee, D., Yannakakis, M.: Principles and methods of testing finite–state machines – a survey. Proceedings of the IEEE 84, 1089–1123 (1996)
Lee, D., Yannakakis, M.: Testing finite state machines: state identification and verification. IEEE Trans. Computers 43, 306–320 (1994)
Kohavi, I., Kohavi, Z.: Variable-length distinguishing sequences and their application to the design of fault–detection experiments. IEEE Transactions on Computers, 792–795 (1968)
Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Company, New York (1979)
Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.: Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and bayesian inference. In: Proceedings of Fifth ACM-SIAM Symposium on Discrete Algorithms, pp. 344–354 (1994)
Fujito, T.: A note on approximation of the vertex cover and feedback vertex set problems. Information Processing Letters 59, 59–63 (1996)
Hierons, R.M., Ural, H.: Optimizing the length of checking sequences (submitted)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 IFIP International Federation for Information Processing
About this paper
Cite this paper
Chen, J., Hierons, R.M., Ural, H., Yenigun, H. (2005). Eliminating Redundant Tests in a Checking Sequence. In: Khendek, F., Dssouli, R. (eds) Testing of Communicating Systems. TestCom 2005. Lecture Notes in Computer Science, vol 3502. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11430230_11
Download citation
DOI: https://doi.org/10.1007/11430230_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26054-7
Online ISBN: 978-3-540-32076-0
eBook Packages: Computer ScienceComputer Science (R0)