Protocol testing: review of methods and relevance for software testing

ABSTRACT

Communication protocols are the rules that govern the communication between the different components within a distributed computer system. Since protocols are implemented in software and/or hardware, the question arises whether the existing hardware and software testing methods would be adequate for the testing of communication protocols. The purpose of this paper is to explain in which way the problem of testing protocol implementations is different from the usual problem of software testing. We review the major results in the area of protocol testing and discuss in which way these methods may also be relevant in the more general context of software testing.

REFERENCES

• Aho88: A. V. Aho et al., "An Optimization Technique for Protocol Conformance Test Generation based on UIO Sequences and Rural Chinese Postman Tours", PSTV'88.
• Alde90: Rudie Alderden, COOPER - The Compositional Construction of a Canonical Tester, Proceedings of the IFIP TC/WG6.1 Second International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols, p.13-17, December 05-08, 1989
• Beli89: F. Belina , D. Hogrefe, The CCITT-specification and description language SDL, Computer Networks and ISDN Systems, v.16 n.4, p.311-341, March 1989 [doi>10.1016/0169-7552(89)90078-0]
• Boch90: Gregor Bochmann, Protocol specification for OSI, Computer Networks and ISDN Systems, v.18 n.3, p.167-184, April 1990 [doi>10.1016/0169-7552(90)90132-C]
• Boch91: Gregor von Bochmann , Anindya Das , Rachida Dssouli , Martin Dubuc , Abderrazak Ghedamsi , Gang Luo, Fault Models in Testing, Proceedings of the IFIP TC6/WG6.1 Fourth International Workshop on Protocol Test Systems IV, p.17-30, October 15-17, 1991
• Boch93: G. v. Bochmann, "Protocol Engineering", contribution to Concise Encyclopedia of Software Engineering, Derrick Morris and Boris Tamm eds., Pergamon Press, 1993.
• Bolo87: Tommaso Bolognesi , Ed Brinksma, Introduction to the ISO specification language LOTOS, Computer Networks and ISDN Systems, v.14 n.1, p.25-59, March, 1987 [doi>10.1016/0169-7552(87)90085-7]
• Boyd91: 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]
• Brin87: E. Brinksma, "On the Existence of Canonical Testers", Memorandum INF-87-5, Univ. of Twente, 1987.
• Brin89: E. Brinksma, et al, "A Formal Approach to Conformance Testing", 1WPTS'89.
• Brin91: Ed Brinksma , Jan Tretmans , Louis Verhaard, A Framework for Test Selection, Proceedings of the IFIP WG6.1 International Symposium on Protocol Specification, Testing and Verification XI, p.233-248, June 18-20, 1991
• Brya86: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• Dsso90: R. Dssouli, R. Fournier, G. v. Bochmann, "Conformance Testing and FIFO Queues", FORTEg0.
• Dsso91: R. Dssouli and R. Fournier, "Communication Software Testability", PTS'91.
• Budk87: S. Budkowski , P. Dembinski, An introduction to Estelle: a specification language for distributed systems, Computer Networks and ISDN Systems, v.14 n.1, p.3-23, March, 1987 [doi>10.1016/0169-7552(87)90084-5]
• Cast86: R. Castanet et al," Methods and Semi-automatic Tools for Preparing Distributed Testing", PSTV'86.
• Chan93: S. T. Chanson , A. A. F. Loureiro , S. T. Vuong, On tools supporting the use of formal description techniques in protocol development, Computer Networks and ISDN Systems, v.25 n.7, p.723-739, Feb. 1993 [doi>10.1016/0169-7552(93)90045-6]
• Chen93: Kwang Ting Cheng , A. S. Krishnakumar, Automatic functional test generation using the extended finite state machine model, Proceedings of the 30th international conference on Design automation, p.86-91, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164585]
• Cho91: Hyunwoo Cho , Gary D. Hachtel , Fabio Somenzi, Fast Sequential ATPG Based on Implicit State Enumeration, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.67-74, October 26-30, 1991
• Chow78: T.S. Chow, "Test Design Modeled by Finite- State Machines", IE~ Trans. SE-4, 3, 1978.
• Chun90: Woojik Chun , Paul D. Amer, Test Case Generation for Protocols Specified in Estelle, Proceedings of the IFIP TC6/WG6.1 Third International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols: Formal Description Techniques, III, p.191-206, November 05-08, 1990
• Dahb88: A. Dahbura and K. Sabnani, "Experience in Estimating Fault Coverage of a Protocol Test", INFOCOM'88.
• Drir93: Khalil Drira , Pierre Azéma , B. Soulas , A. M. Chemali, Testability of a Communicating System Through an Environment, Proceedings of the International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.529-543, April 13-17, 1993
• Dubu91: Martin Dubuc , Rachida Dssouli , Gregor von Bochmann, TESTL: An Environment for Incremental Test Suite Design Based on Finite-State Models, Proceedings of the IFIP TC6/WG6.1 Fourth International Workshop on Protocol Test Systems IV, p.195-206, October 15-17, 1991
• Faro90: A. Faro and A. Petrenko, "Sequence Generation from EFSMs for Protocol Testing", COMNET'90.
• Favr86: J.-P. Favreau, R. S. Linn, "Automatic Generation of Test Scenario Skeletons from Protocol Specifications Written in ESTELLE", ISPTSV'86.
• Frank93: P. G. Frankl , S. N. Weiss, An Experimental Comparison of the Effectiveness of Branch Testing and Data Flow Testing, IEEE Transactions on Software Engineering, v.19 n.8, p.774-787, August 1993 [doi>10.1109/32.238581]
• FuBo91: Susumu Fujiwara , Gregor von Bochmann, Testing Non-Deterministic State Machines with Fault Coverage, Proceedings of the IFIP TC6/WG6.1 Fourth International Workshop on Protocol Test Systems IV, p.267-280, October 15-17, 1991
• Glab90: R. J. v. Glabbeek, "The Linear Time-Branching Time Spectrum", LNCS, 458, 1990.
• Guo91: F. Guo, R. Probert, "E-MPT Protocol Testing: Preliminary Experimental Results", PSTVgl.
• Fuji91: Susumu Fujiwara , Gregor von Bochmann , Ferhat Khendek , Mokhtar Amalou , Abderrazak Ghedamsi, Test Selection Based on Finite State Models, IEEE Transactions on Software Engineering, v.17 n.6, p.591-603, June 1991 [doi>10.1109/32.87284]
• Glab93: Rob J. van Glabbeek, The Linear Time - Branching Time Spectrum II, Proceedings of the 4th International Conference on Concurrency Theory, p.66-81, August 23-26, 1993
• Henn64: F. C. Hennie, "Fault Detecting Experiments for Sequential Circuits", IEEE 5th Ann. Syrup. on Switching Circuits Theory and Logical Design, 1964.
• Higa94: T. Higashino , G. V. Bochmann, Automatic Analysis and Test Case Derivation for a Restricted Class of LOTOS Expressions with Data Parameters, IEEE Transactions on Software Engineering, v.20 n.1, p.29-42, January 1994 [doi>10.1109/32.263753]
• Hoar85: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• Hoff93: Daniel Hoffman , Paul Strooper, A case study in class testing, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada
• IS9646: OSI Conformance Testing Methodology and Framework.
• IS7498: Reference Model for OSI.
• Lang89: R. Langer~, "A Testing Theory for LOTOS Using ~ock Dexecfion", PSTV'89.
• Ledu91: Guy Leduc, Conformance Relation, Associated Equivalence, and New Canonical Tester in LOTOS, Proceedings of the IFIP WG6.1 International Symposium on Protocol Specification, Testing and Verification XI, p.249-264, June 18-20, 1991
• Liu93: F. Liu, "Test Generation Based on the FSM Model with Timers and Counters,", M. Sc. Theses, Universit6 de Monutal, DIRO, 1993.
• Luo93: Gang Luo , Rachida Dssouli , Gregor von Bochmann , Pallapa Venkataram , Abderrazak Ghedamsi, Generating Synchronizable Test Sequences Based on Finite State Machine with Distributed Ports, Proceedings of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test systems VI, p.139-153, September 28-30, 1993
• Luo94: Gang Luo , G. von Bochmann , A. Petrenko, Test Selection Based on Communicating Nondeterministic Finite-State Machines Using a Generalized Wp-Method, IEEE Transactions on Software Engineering, v.20 n.2, p.149-162, February 1994 [doi>10.1109/32.265636]
• Miln80: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• Mill92: Raymond E. Miller , Sanjoy Paul, Generating Conformance Test Sequences for Combined Control and Data Flow of Communication Protocols, Proceedings of the IFIP TC6/WG6.1 Twelth International Symposium on Protocol Specification, Testing and Verification XII, p.13-27, June 22-25, 1992
• Moor56: E. F. Moore, "Gedanken-Experiments on Sequential Machines", Automata Studies, Princeton University Press, Prince~n, New Jersey, 1956.
• Mott93: Howard E. Motteler , Anthony Chung , Deepinder P. Sidhu, Fault Coverage of UIO-based Methods for Protocol Testing, Proceedings of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test systems VI, p.21-34, September 28-30, 1993
• Neuf92: Gerald Neufeld , Son Vuong, An overview of ASN.1, Computer Networks and ISDN Systems, v.23 n.5, p.393-415, Feb. 1992 [doi>10.1016/0169-7552(92)90014-H]
• Petr91: Alexandre Petrenko, Checking Experiments with Protocol Machines, Proceedings of the IFIP TC6/WG6.1 Fourth International Workshop on Protocol Test Systems IV, p.83-94, October 15-17, 1991
• Petr92: Alexandre Petrenko , Nina Yevtushenko, Test Suite Generation from a FSM with a Given Type of Implementation Errors, Proceedings of the IFIP TC6/WG6.1 Twelth International Symposium on Protocol Specification, Testing and Verification XII, p.229-243, June 22-25, 1992
• PBD93: Alexandre Petrenko , Gregor von Bochmann , Rachida Dssouli, Conformance Relations and Test Derivation, Proceedings of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test systems VI, p.157-178, September 28-30, 1993
• Petr93: Alexandre Petrenko , Nina Yevtushenko , Alexandre Lebedev , Anindya Das, Nondeterministic State Machines in Protocol Conformance Testing, Proceedings of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test systems VI, p.363-378, September 28-30, 1993
• Petr94: A. Petrenko, N. Yevtushenko, R. Dssouli, "Grey- Box FSM-based Testing Strategies", De~ent Publication 911, Universit6 de Montr6al, 1994, 22p.
• Prob89: R. L. Probert, H. Ural, M. W. A. Hombeek, "A Comprehensive Software Environment for Developing Standardized Conformance Test Suites", Computer Networks and ISDN Systems, 18, 1989/1990.
• Rayn87: D. Rayner, OSI conformance testing, Computer Networks and ISDN Systems, v.14 n.1, p.79-98, March, 1987 [doi>10.1016/0169-7552(87)90087-0]
• Sari84: B. Sarikaya, O. v. Bochmann, "Synchronization and Specification Issues in Protocx)l Testing", IEEE Trans., vol. COM-32, No.4, 1984.
• Sari87: 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]
• Sari92: Behcet Sarikaya , A. Wiles, Standard conformance test specification language TTCN, Computer Standards & Interfaces, v.14 n.2, p.117-144, March 1992 [doi>10.1016/0920-5489(92)90054-H]
• Sher90: M. H. Sherif, M. U. Uyar, "Protocol Modeling for Conformance Testing: Case Study for the ISDN LAPD Protocol", AT&T Technical Journal, january 1990.
• Shev91: V. Shevelkov, "Development of Methods and Tools for Session Interconnection Provision in Open Systems Networks", Ph.D. Theses, Riga, 1991.
• Sidh89: 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]
• Star72: P. H. Starke, Abstract Automata, North-Holland/American Elsevier, 1972, 419p.
• Tret91: Jan Tretmans , Pim Kars , Ed Brinksma, Protocol Conformance Testing: A Formal Perspective on ISO IS-9646, Proceedings of the IFIP TC6/WG6.1 Fourth International Workshop on Protocol Test Systems IV, p.131-142, October 15-17, 1991
• Turn92: C.D. Turner and D J. Robson, "The Testing of Object-Oriented Programs", TR- 13/92, Univ. of Durham, 1992.
• Ural87: 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]
• Ural91: Hasan Ural, Formal methods for test sequence generation, Computer Communications, v.15 n.5, p.311-325, June 1992 [doi>10.1016/0140-3664(92)90092-S]
• Ural93: Hasan Ural , Alan Williams, Test Generation by Exposing Control and Data Dependencies Within System Specifications in SDL, Proceedings of the IFIP TC6/WG6.1 Sixth International Conference on Formal Description Techniques, VI, p.335-350, October 26-29, 1993
• Vasi73: M. P. Vasilevski, "Failure Diagnosis of Automata", Cybernetics, Plenum Publ. Corporation, N.Y., No. 4, 1973.
• Vuon89: S. T. Vuong, W. L. Chan, and M. R. Ito, "The UIOv-method for Protocol Test Sequence Generation", IWPTS'89.
• Vuon93: Son T. Vuong , Antonio Alfredo Ferreira Loureiro , Samuel T. Chanson, A Framework for the Design for Testability of Communication Protocols, Proceedings of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test systems VI, p.89-108, September 28-30, 1993
• Wang93: C.-J. Wang and M. T. Liu, "Generating Test Cases for EFSM with Given Fault Model", INFOCOM'93.
• Wata93: Yosinori Watanabe , Robert K. Brayton, The maximum set of permissible behaviors for FSM networks, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.316-320, November 07-11, 1993, Santa Clara, California, United States
• Weze90: Clazien D. Wezeman, The CO-OP Method for Compositional Derivation of Conformance Testers, Proceedings of the IFIP WG6.1 Ninth International Symposium on Protocol Specification, Testing and Verification IX, p.145-158, June 06-09, 1989
• Yann91: Mihalis Yannakakis , David Lee, Testing finite state machines, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.476-485, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103468]
• Yao94: M. Yao, A. Petrenko, G. v. Bochmann, "A Stmcunal Analysis Approach to Evaluating Fault Coverage of Software Testing in Respect to the FSM Model", Dep. Publ. g920, Universite de Montreal, 1994.
• Yevt90a: N. V. Evtushenko , A. F. Petrenko, Synthesis of test experiments in some classes of automata, Automatic Control and Computer Sciences, v.24 n.4, p.50-55, 1990
• Yevt90b: N. V. Evtushenko , A. F. Petrenko, Method of constructing a test experiment for an arbitrary deterministic automation, Automatic Control and Computer Sciences, v.24 n.5, p.65-68, 1990
• Yevt91: N. Yevtushenko, A. Le~ev, A. Petrenko, "On the Checking Experiments with Nondcterministic Automata", Automatic Control and Computer Sciences, Allerton Press, inc., N.Y., Vol.25, No.6, 1991.
• YPB93: Mingyu Yao , Alexandre Petrenko , Gregor von Bochmann, Conformance Testing of Protocol Machines without Reset, Proceedings of the IFIP TC6/WG6.1 Thirteenth International Symposium on Protocol Specification, Testing and Verification XIII, p.241-256, May 25-28, 1993
• YPB94: M. Yao, A. Petrenko and G.v. Bochmann, "Fault Coverage Analysis in Respect to an FSM Specification", INFOCOM'94.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: OSI
      C.2.2 Network Protocols
          Subjects: Protocol verification

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages
          Nouns: Lotos

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Algorithms, Design, Languages, Verification