Practical network support for IP traceback

ABSTRACT

This paper describes a technique for tracing anonymous packet flooding attacks in the Internet back towards their source. This work is motivated by the increased frequency and sophistication of denial-of-service attacks and by the difficulty in tracing packets with incorrect, or ``spoofed'', source addresses. In this paper we describe a general purpose traceback mechanism based on probabilistic packet marking in the network. Our approach allows a victim to identify the network path(s) traversed by attack traffic without requiring interactive operational support from Internet Service Providers (ISPs). Moreover, this traceback can be performed ``post-mortem'' -- after an attack has completed. We present an implementation of this technology that is incrementally deployable, (mostly) backwards compatible and can be efficiently implemented using conventional technology.

REFERENCES

• 1: F. Baker. Requirements for IP Version 4 Routers. RFC 1812, June 1995.
• 2: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 3: S. M. Bellovin, Security problems in the TCP/IP protocol suite, ACM SIGCOMM Computer Communication Review, v.19 n.2, p.32-48, April 1, 1989 [doi>10.1145/378444.378449]
• 4: S. M. Bellovin. ICMP Traceback Messages. Internet Draft: draft-bellovin-itrace-00.txt, Mar. 2000.
• 5: R. Braden. Requirements for Internet Hosts - Communication Layers. RFC 1122, Oct. 1989.
• 6: H. Burch and B. Cheswick. Tracing Anonymous Packets to Their Approximate Source. Unpublished paper, Dec. 1999.
• 7: Robert L. Carter , Mark E. Crovella, Server Selection Using Dynamic Path Characterization in Wide-Area Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1014, April 09-11, 1997
• 8: B. Cheswick and H. Burch. Internet Mapping Project. http://cm.bell-labs.com/who/ches/map/ index.html, 2000.
• 9: Cisco Systems. Configuring TCP Intercept (Prevent Denial-of-Service Attacks). Cisco IOS Documentation, Dec. 1997.
• 10: K. Claffy and S. McCreary. Sampled Measurements from June 1999 to December 1999 at the AMES Inter-exchange Point. Personal Communication, Jan. 2000.
• 11: Computer Emergency Response Team. CERT Advisory CA-96.26 Denial-of-Service Attack via pings. http://www.cert.org/advisories/CA-96.26. ping.html, Dec. 1996.
• 12: Computer Emergency Response Team. CERT Advisory CA-97.28 IP Denial-of-Service Attacks. http://www. cert.org/advisories/CA-97.28.smurf.html, Dec. 1997.
• 13: Computer Emergency Response Team. CERT Advisory CA-98.01 smurf IP Denial-of-Service Attacks. http://www.cert.org/advisories/CA-98.01. smurf.html, Jan. 1998.
• 14: Computer Emergency Response Team. CERT Advisory CA-2000-01 Denial-of-Service Developments. http:// www.cert.org/advisories/CA-2000-01.html, Jan. 2000.
• 15: Computer Emergency Response Team. CERT Incident Note IN-2000-04 Denial-of-Service Attacks using Nameservers. http://www.cert.org/incident_notes/ IN-200-04.html, Apr. 2000.
• 16: Computer Security Institute and Federal Bureau of Investigation. 1999 CSI/FBI Computer Crime and Security Survey. Computer Security Institute publication, Mar. 1999.
• 17: Cooperative Associationfor Internet Data Analysis. Skitter Analysis. http: //www.caida.org/Tools/Skitter/Summary/, 2000.
• 18: S. Deering. Internet protocol, version 6 (ipv6). RFC 2460, Dec. 1998.
• 19: W. Feller. An Introduction to Probability Theory and Its Applications (2nd edition), volume 1. Wiley and Sons, 1966.
• 20: P. Ferguson and D. Senie. Network Ingress Filtering: Defeating Denial of Service Attacks Which Employ IP Source Address Spoofing. RFC 2267, Jan. 1998.
• 21: J. Glave. Smurfing Cripples ISPs. Wired Technolgy News: (http://www.wired.com/news/news/ technology/story/9506.html), Jan. 1998.
• 22: I. Goldberg and A. Shostack. Freedom Network 1.0 Architecture and Protocols. Zero-Knowledge Systems White Paper, Nov. 1999.
• 23: R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. In Proceedings of the 2000 IEEE INFOCOM Conference, Tel Aviv, Israel, Mar. 2000.
• 24: L. T. Heberlein and M. Bishop. Attack Class: Address Spoofing. In 1996 National Information Systems Security Conference, pages 371-378, Baltimore, MD, Oct. 1996.
• 25: John Douglas Howard, An analysis of security incidents on the Internet 1989-1995, Carnegie Mellon University, Pittsburgh, PA, 1998
• 26: P. Karn and W. Simpson. Photuris: Session-Key Management Protocol. RFC 2522, Mar. 1999.
• 27: C. A. Kent , J. C. Mogul, Fragmentation considered harmful, Proceedings of the ACM workshop on Frontiers in computer communications technology, p.390-401, August 11-13, 1987, Stowe, Vermont, United States
• 28: S. Kent and R. Atkinson. Security architecture for the internet protocol. RFC 2401, Nov. 1998.
• 29: Catherine Meadows, A Formal Framework and Evaluation Method for Network Denial of Service, Proceedings of the 1999 IEEE Computer Security Foundations Workshop, p.4, June 28-30, 1999
• 30: J. Mogul and S. Deering. Path MTU Discovery. RFC 1191, Nov. 1990.
• 31: R. T. Morris. A Weakness in the 4.2BSD Unix TCP/IP Software. Technical Report Computer Science #117, AT&T Bell Labs, Feb. 1985.
• 32: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 33: C. Perkins. IP Mobility Support. RFC 2002, Oct. 1996.
• 34: J. Postel. Internet Protocol. RFC 791, Sept. 1981.
• 35: M. G. Reed, P. F. Syverson, and D. M. Goldschlag. Anonymous Connections and Onion Routing. IEEE Journal on Selected Areas in Communications, 16(4):482-494, May 1998.
• 36: E. C. Rosen, Y. Rekhter, D. Tappan, D. Farinacci, G. Fedorkow, T. Li, and A. Conta. MPLS Label Stack Encoding. Internet Draft: draft-ietf-mpls-label-encaps-07.txt (expires March 2000), Sept. 1998.
• 37: G. Sager. Security Fun with OCxmon and cflowd. Presentation at the Internet 2 Working Group, Nov. 1998.
• 38: Oliver Spatscheck , Larry L. Peterson, Defending against denial of service attacks in Scout, Proceedings of the third symposium on Operating systems design and implementation, p.59-72, February 1999, New Orleans, Louisiana, United States
• 39: S. Staniford-Chen , L. T. Heberlein, Holding intruders accountable on the Internet, Proceedings of the 1995 IEEE Symposium on Security and Privacy, p.39, May 08-10, 1995
• 40: Ion Stoica , Hui Zhang, Providing guaranteed services without per flow management, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.81-94, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 41: R. Stone. CenterTrack: An IP Overlay Network for Tracking DoS Floods. In to appear in Proceedings of thje 2000 USENIX Security Symposium, Denver, CO, July 2000.
• 42: W. Theilmann and K. Rothermel. Dynamic Distance Maps of the Internet. In Proceedings of the 2000 IEEE INFOCOM Conference, Tel Aviv, Israel, Mar. 2000.
• 43: C. Villamizar. Personal Communication, Feb. 2000.
• 44: Marco de Vivo , Eddy Carrasco , Germinal Isern , Gabriela O. de Vivo, A review of port scanning techniques, ACM SIGCOMM Computer Communication Review, v.29 n.2, April 1999 [doi>10.1145/505733.505737]
• 45: Y. Zhang and V. Paxson. Stepping Stone Detection. In to appear in Proceedings of thje 2000 USENIX Security Symposium, Denver, CO, July 2000.

INDEX TERMS

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

          Nouns: TCP/IP

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Security, Standardization, Theory