A new technique for generating protocol test

ABSTRACT

A novel procedure presented here generates test sequences for checking the conformity of protocol implementations to their specifications. The test sequences generated by this procedure only detect the presence of many faults, but they do not locate the faults. It can always detect the problem in an implementation with a single fault. A protocol entity is specified as a finite state machine (FSM). It typically has two interfaces: an interface with the user and with the lower-layer protocol. The inputs from both interfaces are merged into a single set I and the outputs from both interfaces are merged into a single set O. The implementation is assumed to be a black box. The key idea in this procedure is to tour all states and state transitions and to check a unique signature for each state, called the Unique Input/Output (UIO) sequence. A UIO sequence for a state is an I/O behavior that is not exhibited by any other state.

REFERENCES

• AHU76: "The Design and Analysis of Computer Algorithms," A. V. Aho, J. E. Hopcroft, and J. D. Ullman, pp. 143-145, 207-209, Addison- Wesley Publishing Company, 1976.
• Bi83: "Methodology and tools for qualitative protocol validation," I. F. Billiard, Protocol Specification, Testing, and Verification, IlI, R. Rudin and C. H. West (editors), Elsevier Science Publishers B. g., IFIP 1983.
• BS83: "A Survey of Formal Methods," Gregor V. Bochmann and Cart A. Sunshine, pp. 561-578, Chapter 20, "Computer Networks and Protocols,' Paul E. Green (Editor), May 1983, Plenum Press.
• GJ79: "Computers and Intractability: ,4 guide to the theory of NP-Completeness." M. Garey and D. Johnson, Freeman and Co., San Francisco, 1979, Page 285.
• Gr82: "The Structure of Computer Networks,' Paul E. Green, Jr., Chapter 1, pp. 3-32, Computer Network Architectures and Protocols, Edited by Paul E. Green, Plenum Press, 1982.
• He64: "Fault-Detecting Experiments for Sequential Circuits," F. C. Hcnni~, Proceedings of the Fifth Annual Symposium, Princeton University, Princeton, NJ, November 11-13, 1964, pp 95- 110.
• Kl72: "Introduction to the Methodology of Switching Circuits," George J. Kilt, D. Van Nostrand Company, 1972, pp. 264-325.
• LM83: "Producing Tests for Implementations of OSI Protocols," R. J. Linn and W. H. McCoy, Protocol Specification, Testing, and Verification, IIi, R. Rudin and C. H. West (editors), Elsevier Science Publishers B. V., IFIP 1983.
• Pi80: "Remarks on the Feasibility of Validating and Testing ADCCP Implementations,' T. F. Piatkowski, IEEE Proceedings of Trends and Applications, May 1980.
• Ra83: 'Towards an objective understanding of conformance," D. Rayner, Protocol Specification, Testing, and Verification, III, R. Rudin and C. H. West (editors), Elsevier Science Publishers B. V., IFIP 1983.
• SB82: Behçet Sarikaya , Gregor von Bochmann, Some Experience with Test Sequence Generation for Protocols, Proceedings of the IFIP WG6.1 Second International Workshop on Protocol Specification, Testing and Verification, p.555-567, May 17-20, 1982

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Design, Theory, Verification