Abstract
Finite-state-machine-based conformance testing has been extensively studied in the literature in the context of centralized test architecture. With a distributed test architecture which involves multiple remote testers, the application of a test sequence may encounter controllability problems. This problem can be overcome by introducing additional external coordination messages exchanged among remote testers. Such an approach requires for extra resources for the communication among remote testers and sometimes suffers from unexpected delay. It is thus desirable to avoid the controllability problem by selecting suitable test sequences. However, this is not always possible. For some finite state machines, we cannot generate a test sequence without using external coordination messages and apply it without encountering controllability problems during testing. In this paper, we present sufficient and necessary conditions on a given finite state machine for constructing test sequences so that it does not involve external coordination messages and its application to the implementation under test is free from controllability problems.
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.V., Dahbura, A.T., Lee, D., Uyar, M.U.: An optimization technique for protocol conformance test generation based on UIO sequences and Rural Chinese Postman Tours. IEEE Trans. Comm. 39(11), 1604–1615 (1991)
Bochmann, G.v., Petrenko, A., Bellal, O., Maguiraga, S.: Automating the process of test derivation from SDL specifications. In: Proc. of 8th SDL Forum (1997)
Boyd, S., Ural, H.: The synchronization problem in protocol testing and its complexity. Information Processing Letters 4(3), 131–136 (1991)
Cacciari, L., Rafiq, O.: Controllability and observability in distributed testing. Information and Software Technology 41, 767–780 (1999)
Chen, J., Hierons, R.M., Ural, H.: Conditions for resolving observability problems in distributed testing. In: de Frutos-Escrig, D., Núñez, M. (eds.) FORTE 2004. LNCS, vol. 3235, pp. 229–242. Springer, Heidelberg (2004)
Chen, J., Hierons, R.M., Ural, H.: Overcoming observability problems in distributed test architectures. Information Processing Letter 98(5), 177–182 (2006)
Chen, J., Ural, H.: Detecting observability problems in distributed testing. In: Uyar, M.Ü., Duale, A.Y., Fecko, M.A. (eds.) TestCom 2006. LNCS, vol. 3964, pp. 213–226. Springer, Heidelberg (2006)
Chow, T.S.: Testing software design modeled by finite-state machines. IEEE Trans. Software Eng. SE-4(3), 178–187 (1978)
Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Computing 19(3), 500–510 (1990)
Gonenc, G.: A method for the design of fault detection experiments. IEEE Trans. Computers 19(6), 551–558 (1970)
Hennie, F.C.: Fault detecting experiments for sequential circuits. In: Proc. of 5th Ann. Symp. Switching Circuit Theory and Logical Design, pp. 95–110 (1964)
Hierons, R.M., Harman, M.: Testing conformance to a quasi-non-deterministic stream X-machine. Formal Aspects of Computing 12(6), 423–442 (2000)
Hierons, R.M., Ural, H.: Reduced length checking sequences. IEEE Transactions on Computers 51(9), 1111–1117 (2002)
Hierons, R.M., Ural, H.: UIO sequence based checking sequences for distributed test architectures. Information and Software Technology 45(12), 793–803 (2003)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley, Reading (2001)
ISO/IEC 9646. Information technology – Open Systems Interconnection – Conformance testing methodology and framework – Part 1-7. ISO (June 1996)
Johnson, W.L., Porter, J.H., Ackley, S.I., Ross, D.T.: Automatic generation of efficient lexical processors using finite state techniques. Communications of the ACM 11(12), 805–813 (1968)
Kohavi, Z.: Switching and finite automata theory, 2nd edn. McGraw-Hill, New York (1978)
Lai, R.: A survey of communication protocol testing. Journal of Systems and Software 62, 21–46 (2002)
Lee, D., Yannakakis, M.: Testing finite state machines: state identification and verification. IEEE Tran. Computers 43, 306–320 (1994)
Lee, D., Yannakakis, M.: Principles and methods of testing finite state machines — a survey. Proceedings of The IEEE 84(8), 1090–1123 (1996)
Luo, G., Das, A., von Bochmann, G.: Generating tests for control portion of SDL specification. In: Proc. of Protocol test systems VI, pp. 51–66 (1994)
Luo, G., Dssouli, R., Bochmann, G.V., Venkataram, P., Ghedamsi, A.: Test generation with respect to distributed interfaces. Computer Standards and Interfaces 16, 119–132 (1994)
Miller, R.E., Paul, S.: On the generation of minimal length conformance tests for communications protocols. IEEE/ACM Transactions on Networking 1(1), 116–129 (1993)
Moore, E.F.: Gedanken-experiments on sequenctial machines. Automata Studies 34, 129–153 (1956)
Motteler, H., Chung, A., Sidhu, D.: Fault coverage of UIO-based methods for protocol testing. In: Proc. of IFIP TC6/WG6.1 6th International Workshop on Protocol Test Systems, pp. 21–33 (1994)
Naito, S., Tsunoyama, M.: Fault detection for sequential machines by transition tours. In: Proc. of 11th. IEEE Fault Tolerant Computing Symposium, pp. 238–243 (1981)
Pomeranz, I., Reddy, S.M.: Test generation for multiple state-table faults in finite-state machines. IEEE Transactions on Computers 46, 783–794 (1997)
Sabnani, K.K., Dahbura, A.T.: A protocol test generation procedure. Computer Networks and ISDN Systems 4(15), 285–297 (1988)
Saleh, K., Ural, H., Williams, A.: Test generation based on control and data dependencies within system specifications in SDL. Computer Communications 23(7), 609–627 (2000)
Sarikaya, B., Bochmann, G.V.: Synchronization and specification issues in protocol testing. IEEE Transactions on Communications 32, 389–395 (1984)
Sidhu, D.P., Leung, T.-K.: Formal methods for protocol testing: A detailed study. IEEE Transactions on Software Engineering 15(4), 413–426 (1989)
Tan, Q.M., Petrenko, A.G.: Modeling basic LOTOS by FSMs for conformance testing. In: Proc. of 15th International Symposium on Protocol Specification, Testing and Verification (PSTV 15), pp. 137–152 (1995)
Tarjan, R.: Depth-first search and linear graph algorithms. J. SIAM Comput. 1(2), 146–160 (1972)
Ural, H., Whittier, D.: Distributed testing without encountering controlability and observability problems. Information Processing Letters 88, 133–141 (2003)
Ural, H., Wu, X., Zhang, F.: On minimizing the lengths of checking sequences. IEEE Transactions on Computers 46(1), 93–99 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, J., Duan, L. (2006). Conditions for Avoiding Controllability Problems in Distributed Testing. In: Liu, Z., He, J. (eds) Formal Methods and Software Engineering. ICFEM 2006. Lecture Notes in Computer Science, vol 4260. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11901433_25
Download citation
DOI: https://doi.org/10.1007/11901433_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-47460-9
Online ISBN: 978-3-540-47462-3
eBook Packages: Computer ScienceComputer Science (R0)