Single-packet IP traceback

ABSTRACT

The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet. Even in the absence of any deliberate attempt to disguise a packet's origin, widespread packet forwarding techniques such as NAT and encapsulation may obscure the packet's true source. Techniques have been developed to determine the source of large packet flows, but, to date, no system has been presented to track individual packets in an efficient, scalable fashion. We present a hash-based technique for IP traceback that generates audit trails for traffic within the network, and can trace the origin of a single IP packet delivered by the network in the recent past. We demonstrate that the system is effective, space efficient (requiring approximately 0.5% of the link capacity per unit time in storage), and implementable in current or next-generation routing hardware. We present both analytic and simulation results showing the system's effectiveness.

REFERENCES

• 1: Microsoft Corporation. Stop 0A in tcpip.sys when receiving out of band (OOB) data. {Online}. Available: http://support.microsoft.com/support/kb/articles/Q143/4/78.asp
• 2: P. Ferguson and D. Senie, "Network ingress filtering: Defeating denial of service attacks which employ IP source address spoofing," IETF, RFC 2267, Jan. 1998.
• 3: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 4: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 5: C. Shannon, D. Moore, and K. Claffy, "Characteristics of fragmented IP traffic on Internet links," presented at the RIPE Workshop Passive and Active Measurements, Amsterdam, The Netherlands, Apr. 2001.
• 6: Vern Paxson, An analysis of using reflectors for distributed denial-of-service attacks, ACM SIGCOMM Computer Communication Review, v.31 n.3, July 2001 [doi>10.1145/505659.505664]
• 7: F. Baker, "Requirements for IP version 4 routers," IETF, RFC 1812, June 1995.
• 8: S. McCreary and K. Claffy, "Trends in wide area IP traffic patterns: A view from Ames Internet exchange," presented at the ITC Specialist Seminar IP Traffic Modeling, Measurement and Management, Monterey, CA, Sept. 2000.
• 9: Hal Burch, Tracing Anonymous Packets to Their Approximate Source, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 10: Stefan Savage , David Wetherall , Anna Karlin , Tom Anderson, Network support for IP traceback, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.226-237, June 2001 [doi>10.1109/90.929847]
• 11: S. M. Bellovin, M. Leech, and T. Taylor, "ICMP traceback messages," IETF, Internet Draft, draft-ietf-itrace-01.txt (work in progress), Oct. 2001.
• 12: D. X. Song and A. Perrig, "Advanced and authenticated marking schemes for IP traceback," in Proc. IEEE Infocom'01, Apr. 2001, pp. 878-886.
• 13: A. Mankin, D. Massey, C.-L. Wu, S. F. Wu, and L. Zhang, "On design and evaluation of 'intention-driven' ICMP traceback," in Proc. IEEE Int. Conf. Computer Communications and Networks, Oct. 2001, pp. 159-165.
• 14: G. Sager. "Security fun with OCxmon and cflowd", presented at Internet 2 Working Group Meeting. {Online}. Available: http://www.caida.org/projects/NGI/content/security/1198.
• 15: D. Schnackenberg, K. Djahandari, and D. Sterne, "Infrastructure for intrusion detection and response," in Proc. First DARPA Information Survivability Conf. Exposition, vol. 2, Jan. 2000, pp. 1003-1011.
• 16: R. Stone, "CenterTrack: An IP overlay network for tracking DoS floods," in Proc. USENIX Security Symp., July 2000, pp. 199-212.
• 17: N. G. Duffield , M. Grossglauser, Trajectory sampling for direct traffic observation, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.271-282, August 28-September 01, 2000, Stockholm, Sweden
• 18: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 19: L. Carter and M. Wegman, "Universal classes of hash functions," J. Comput. Syst. Sci., vol. 18, no. 2, pp. 143-154, 1979.
• 20: John Black , Shai Halevi , Hugo Krawczyk , Ted Krovetz , Phillip Rogaway, UMAC: Fast and Secure Message Authentication, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.216-233, August 15-19, 1999
• 21: Shai Halevi , Hugo Krawczyk, MMH: Software Message Authentication in the Gbit/Second Rates, Proceedings of the 4th International Workshop on Fast Software Encryption, p.172-189, January 20-22, 1997
• 22: Hugo Krawczyk, LFSR-based Hashing and Authentication, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.129-139, August 21-25, 1994
• 23: J. Postel, "Internet protocol," IETF, RFC 791, Sept. 1981.
• 24: ____, "Internet control message protocol," IETF, RFC 792, Sept. 1981.
• 25: R. Rivest, "The MD5 message-digest algorithm," IETF, RFC 1321, Apr. 1992.
• 26: L. A. Sanchez, W. C. Milliken, A. C. Snoeren, F. Tchakountio, C. E. Jones, S. T. Kent, C. Partridge, and W. T. Strayer, "Hardware support for a hash-based IP traceback," in Proc. Second DARPA Information Survivability Conf. Exposition, vol. 2, June 2001, pp. 146-152.
• 27: C. Fraleigh, C. Diot, B. Lyles, S. Moon, P. Owezarski, D. Papagiannaki, and F. Tobagi, "Design and deployment of a passive monitoring infrastructure," presented at the RIPE Workshop Passive and Active Measurements, Amsterdam, The Netherlands, Apr. 2001.
• 28: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978

INDEX TERMS

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

          Nouns: IP

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Algorithms, Performance, Reliability

Keywords:
IP traceback, computer network management, computer network security, denial of service (DoS), network fault diagnosis, wide-area networks (WANs)