Network protocol system monitoring: a formal approach with passive testing

ABSTRACT

We study network protocol system monitoring for fault detection using a formal technique of passive testing that is a process of detecting system faults by passively observing its input/output behaviors without interrupting its normal operations. After describing a formal model of event-driven extended finite state machines, we present two algorithms for passive testing of protocol system control and data portions. Experimental results on OSPF and TCP are reported.

REFERENCES

• 1: [1] D. Lee and M. Yannakakis, "Principles and methods of testing finite state machines-a survey," Proc. IEEE, vol. 84, no. 8, pp. 1090-1123, Aug. 1996.
• 2: D. Lee , A. N. Netravali , K. K. Sabnani , B. Sugla , A. John, Passive testing and applications to network management, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.113, October 28-31, 1997
• 3: [3] A. Bouloutas, G. Hart, and M. Schwartz, "On the design of observers for failure detection of discrete event systems," presented at the IEEE Workshop on Network Management, Tarrytown, NY, Sep. 1989.
• 4: Clark Wang , Mischa Schwartz, Fault detection with multiple observers, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.48-55, Feb. 1993 [doi>10.1109/90.222906]
• 5: [5] K. V. Noubir and H. J. Nussbaumer, "Signature-based method for run-time fault detection in communication protocols," Comput. Commun. J., vol. 21, no. 5, May 1998.
• 6: [6] R. E. Miller, "Passive testing of networks using a cfsm specification," in Proc. IEEE Int. Performance, Computing and Communications Conf., Feb. 1998, pp. 111-116.
• 7: [7] R. E. Miller and K. A. Arisha, "On fault location in networks by passive testing," in Proc. IEEE Int. Performance, Computing and Communications Conf., Feb. 2000, pp. 281-287.
• 8: [8] B. Alcalde, A. Cavalli, D. Chen, D. Khuu, and D. Lee, "Network protocol system passive testing for fault management: a backward checking approach," in Proc. FORTE 2004, Madrid, Spain, Sep. 2004, pp. 150-166.
• 9: [9] S. Jaiswal, G. Iannaccone, C. Diot, J. F. Kurose, and D. Towsley, "Inferring TCP connection characteristics through passive measurements," in Proc. IEEE INFOCOM, 2004, pp. 1582-1592.
• 10: [10] M. Tabourier and A. Cavalli, "Passive testing and application to the GSM-MAP Protocol," J. Inf. Software Technol., vol. 41, pp. 813-821, Sep. 1999.
• 11: David Lee , Dongluo Chen , Ruibing Hao , Raymond E. Miller , Jianping Wu , Xia Yin, A Formal Approach for Passive Testing of Protocol Data Portions, Proceedings of the 10th IEEE International Conference on Network Protocols, p.122-131, November 12-15, 2002
• 12: [12] W. Wang, A. A. Lazar, and R. H. Deng, "Models and algorithms for network fault detection and identification: a review," in Proc. ICCS/ ISITA, 1992, pp. 999-1003.
• 13: Cynthia S. Hood , Chuanyi Ji, Proactive Network Fault Detection, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1147, April 09-11, 1997
• 14: [14] R. W. Buskens and R. P. Bianchini, Jr., "Distributed on-line diagnosis in the presence of arbitrary faults," in Proc. 23rd Int. Conf. Fault-Tolerant Computing (FTCS-23), Toulouse, France, 1993, pp. 470-479.
• 15: [15] N. Anerousis, R. Caceres, N. Duffield, A. Feldmann, A. Greenberg, C. Kalmanek, P. Mishra, K. Ramakrishnan, and J. Rexford, Using the AT&T Labs PacketScope for Internet measurements, design, and performance analysis Nov. 1997.
• 16: [16] J. Hall, I. Pratt, and I. Leslie, "Observing web browser behavior using the Nprobe passive monitoring architecture," Cabernet, 2001, [Online.] Available: http://www.cl.cam.ac.uk/Research/SRG/netos/nprobe/publications/cabernet-2001.pdf.
• 17: Othmar Kyas, Network troubleshooting, Agilent Technologies, 2001
• 18: [18] "Singing the network blues: MCI WorldCom outage strikes with little explanation," [Online]. Available: http://telephonyonline.com/ar/ telecom_singing_network_blues/
• 19: [19] R. E. Miller, D. L. Chen, D. Lee, and R. Hao, "Coping with nondeterminism in network protocol testing," in Proc. TestCom 2005, pp. 129-145.
• 20: [20] P. R. Thie, An Introduction to Linear Programming and Game Theory, 2nd ed. New York: Wiley, 1988.
• 21: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 22: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 23: [23] J. Moy, OSPF Version 2, RFC 2328, Apr. 1998.
• 24: [24] Information Sciences Inst., Univ. Southern California, Transmission Control Protocol, RFC 793, 1981.
• 25: Ruibing Hao , David Lee , Rakesh K. Sinha , Dario Vlah, Testing IP Routing Protocols - From Probabilistic Algorithms to a Software Tool, Proceedings of the FIP TC6 WG6.1 Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols (FORTE XIII) and Protocol Specification, Testing and Verification (PSTV XX), p.249-264, October 10-13, 2000
• 26: Douglas E. Comer , David L. Stevens, Internetworking with TCP/IP (vol. 2, 2nd ed.): design, implementation, and internals, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 27: R. Elz , R. Bush, Serial Number Arithmetic, RFC Editor, 1996
• 28: [28] PassiveTest1.1. [Online]. Available: http://netlab.cs.tsinghua.edu.cn/ ~chdl/PassiveTestingTools.htm

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol verification

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

General Terms:
Design, Management, Performance, Verification

Keywords:
event-driven extended finite state machine, formal method, network protocol, passive monitoring, testing