A new method of generating synchronizable test sequences that detect output-shifting faults based on multiple UIO sequences

ABSTRACT

The objective of testing is to determine the conformance between a system and its specification. When testing distributed systems, the existence of multiple testers brings out the possibility of synchronization problems among remote testers and the possibility that output-shifting faults go undetected. This paper proposes a new method of generating minimal synchronizable test sequences that detect output-shifting faults based on multiple UIO sequences. The procedure of test generation involves two steps: constructing several auxiliary digraphs from a given specification and finding a rural Chinese post tour (RCPT) in the resultant digraph. When constructing the auxiliary digraphs, different from all the former methods, we use vertices to denote transitions and edges to represent two consecutive transitions. In terms of property and application, the proposed method can construct a relatively simple digraph which makes test generation easily. After applying it to practice, we got hold of better results than the existing methods.

REFERENCES

• 1: B. Sarikaya, G. V. Bochmann, Synchronization and specification issues in protocol testing, IEEE Trans. Comm. 32(1984) 389--395.
• 2: Sylvia Boyd , Hasan Ural, The synchronization problem in protocol testing and its complexity, Information Processing Letters, v.40 n.3, p.131-136, Nov. 1991 [doi>10.1016/0020-0190(91)90166-F ]
• 3: Gang Luo , Rachida Dssouli , Gregor V. Bochmann , Pallapa Venkataram , Abderrazak Ghedamsi, Test generation with respect to distributed interfaces, Computer Standards & Interfaces, v.16 n.2, p.119-132, June 1994 [doi>10.1016/0920-5489(94)90003-5]
• 4: L. Cacciari, O. Rafiq, Controllability and observability in distributed testing, Inform. Software Technol. 41(1999) 767--780.
• 5: J. Chen, R. M. Hierons, H. Ural, Conditions for Resolving Observability Problems in Distributed testing, FORTE 2004, LNCS 3235, 229--242.
• 6: Wen-Huei Chen , Hasan Ural, Synchronizable test sequences based on multiple UIO sequences, IEEE/ACM Transactions on Networking (TON), v.3 n.2, p.152-157, April 1995 [doi>10.1109/90.374116]
• 7: W. I. Wu, W. H. Chen, C. Y. Tang, Synchronizable test sequence for multi-party protocol conformance testing, Computer Communications, 19--98, 21: 1177--1183.
• 8: Hong Liu, Jian-Ping Wu, Xia Yin, Generating external synchronizable test sequences that detect output-shifting faults, ConTEL 2003, 565--571.
• 9: R. M. Hierons, Testing a distributed system: generating minimal synchronised test sequences that detect output-shifting faults, Inform. Software Technol. 43(9)(2001) 551--560.
• 10: A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
• 11: Deepinder P. Sidhu , Ting-kau Leung, Formal Methods for Protocol Testing: A Detailed Study, IEEE Transactions on Software Engineering, v.15 n.4, p.413-426, April 1989 [doi>10.1109/32.16602 ]
• 12: A. Aho, A. Dahbura, D. Lee, M. Uyar, An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours, IEEE Trans. Comm.39 (11)(1991) 1604--1615.
• 13: Y.-N. Shen, F. Lombardi, A. T. Dabbura, Protocol conformance testing using multiple UIO sequences, IEEE Trans. Commun, vol. 40, pp. 1282--1287, 1992.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.5 Reliability, Testing, and Fault-Tolerance**

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery

General Terms:
Algorithms, Performance, Reliability, Verification

Keywords:
FSM, conformance testing, distributed system, output-shifting faults, synchronization problems