Protocol conformance test generation using multiple UIO sequences with overlapping

ABSTRACT

This paper describes an optimization method for reducing the length of protocol conformance test sequences by overlapping test subsequences obtained using UIO sequences. It is shown that test sequences generated by this method are substantially shorter than those generated by other methods employing UIO sequences.

REFERENCES

• 1: G.v. Bochmann and C. A. Sunshine, "A survey of formal methods", in" P. E. Green. ed., Computer Networks and Protocols, New York: Plenum Press, 1983. pp. 561-578.
• 2: F. C. Hennie, "Fault-detecting experiments for sequential circuits", Proc. 5th Annual Symp. on Switching Circuit Theory and Logical Design, Nov. 1964. pp. 95-110.
• 3: G. Gonenc, "A method for the design of fault detection experiments", IEEE Trans. on Computers, vol .19, no, 6, June 1970. pp. 551-558.
• 4: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
• 5: S. Naito and M. Tsunoyama, "Fault detection for sequential machines by transition tours", Proc. 11th IEEE F.T.C. Symp., 1981. pp. 238-243.
• 6: M. U. Uyar and A. T. Dahbura, "Optimal test sequence generation for protocols" the Chinese postman algorithm applied to Q.931", Proc. IEEE Global Telecomm. Conf., 1986. pp. 68-72.
• 7: T. Chow, "Testing software design modeled by finitestate machines", IEEE Trans. on Software Eng., vol. 4, no. 3, 1978. pp. 178-187.
• 8: Krishan Sabnani , Anton Dahbura, A new technique for generating protocol test, Proceedings of the ninth symposium on Data communications, p.36-43, September 1985, Whistler Moutain, British Columbia, Canada
• 9: Krishan Sabnani , Anton Dahbura, A protocol test generation procedure, Computer Networks and ISDN Systems, v.15 n.4, p.285-297, Sept. 1988 [doi>10.1016/0169-7552(88)90064-5]
• 10: A.V. Aho, A. T. Dahbura, D. Lee, and M. U. Uyar, "An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours", Proc. 8th IFIP Symp. on Protocol Spec., Test. and Ver., Atlantic City, June 1988.
• 11: Yinan N. Shen , Fabrizio Lombardi , Anton T. Dahbura, Protocol Conformance Testing Using Multiple UIO Sequences, Proceedings of the IFIP WG6.1 Ninth International Symposium on Protocol Specification, Testing and Verification IX, p.131-143, June 06-09, 1989
• 12: 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]
• 13: B. Sarikaya , G. v. Bochmann , E. Cerny, A test design methodology for protocol testing, IEEE Transactions on Software Engineering, v.13 n.5, p.518-531, May 1987 [doi>10.1109/TSE.1987.233197]
• 14: Hasan Ural, Test sequence selection based on static data flow analysis, Computer Communications, v.10 n.5, p.234-242, Oct. 1987 [doi>10.1016/0140-3664(87)90137-X]
• 15: H. Ural and Bo Yang, "A test sequence selection method for protocols testing", Accepted for publication. To appear in: IEEE Trans on Communications.
• 16: Hasan Ural , B. Yang, A structural test selection criterion, Information Processing Letters, v.28 n.3, p.157-163, July 4, 1988 [doi>10.1016/0020-0190(88)90162-7]
• 17: Baoyu Wang , David Hutchison, Protocol testing techniques, Computer Communications, v.10 n.2, p.79-87, April 1987 [doi>10.1016/0140-3664(87)90104-6]
• 18: M. K. Kuan, "Graphic programming using odd or even points", Chinese Math., vol. 1, 1962. pp. 273- 277.
• 19: J. Edmonds and E. L Johnson, "Matching, Euler tours and the Chinese postman", Mathematical Programming, vol. 5. 1973. pp. 88-124.
• 20: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 21: B. Yang and H. Ural, "On FSM-based optimum test sequence generation", To appear in: Proc. 2nd Int'l Conf. on Comm. Systems (ICCS'90), Nov. 1990.
• 22: S. Boyd and H. Ural, "On the complexity of optimal test sequence generation", Tech. Rep. TR-90-15, Comp. Sc. Dept., Univ. of Ottawa, Ottawa, Canada.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance