Tracers placement for IP traceback against DDoS attacks

ABSTRACT

This paper explores the tracers deployment problem for IP traceback methods how many and where the tracers should be deployed in the network to be effective for locating the attack origins. The minimizing the number of tracers deployment problems depended on locating the attack origins are defined. The problem is proved to be NP-complete. A heuristic method which can guarantee that the distance between any attack origin and its first met tracer be within an assigned distance is proposed. The upper bound for the probability of an undetected attack node can be calculated in advance and used to evaluate the number of tracers needed for the proposed heuristic method. Extended simulations are performed to study the performance of the tracers deployment.

REFERENCES

• 1: Jelena Mirkovic , Peter Reiher, A taxonomy of DDoS attack and DDoS defense mechanisms, ACM SIGCOMM Computer Communication Review, v.34 n.2, April 2004 [doi>10.1145/997150.997156]
• 2: Rocky K. C. Chang, "Defending against Flooding-Based Distributed Denial-od-Service Attacks: A Tutorial," IEEE Communicatin Magazine, Oct. 2002, pp.42--51.
• 3: A. Belenky and N. Ansari, "On IP Traceback," IEEE Communicatin Magazine, July 2003, pp.142--153.
• 4: 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]
• 5: D. X. Song and A. Perring, "Advanced and Authenticated Marking Schemes for IP Traceback," Proc. INFOCOM, 2001, vol. 2, pp. 878--86.
• 6: A. Yaar, A. Perrig, and D. Song, "FIT: Fast Internet Traceback," Proc. INFOCOM, 2005, pp.1395--1406.
• 7: S. M. Bellovin, "ICMP Traceback Messages," IETF draft, 2000; http://www.research.att.com/smb/papers/draft-bellovin-itrace-00.txt.
• 8: Alex C. Snoeren , Craig Partridge , Luis A. Sanchez , Christine E. Jones , Fabrice Tchakountio , Beverly Schwartz , Stephen T. Kent , W. Timothy Strayer, Single-packet IP traceback, IEEE/ACM Transactions on Networking (TON), v.10 n.6, p.721-734, December 2002 [doi>10.1109/TNET.2002.804827]
• 9: Udaya Kiran Tupakula , Vijay Varadharajan, A practical method to counteract denial of service attacks, Proceedings of the 26th Australasian computer science conference, p.275-284, February 01, 2003, Adelaide, Australia
• 10: H. Y. Chang et al., "Deciduous: Decentralized Source Identification for Network-Based Intrusion," Proc. 6th IFIP/IEEE Int'l, Symp. Integrated Net. Mgmt., 1999.
• 11: S. Kent and R. Atkinson. Security Architecture for the Internet Protocol. RFC 2401, November 1998.
• 12: Jangwon Lee , Gustavo de Veciana, Scalable multicast based filtering and tracing framework for defeating distributed DoS attacks, International Journal of Network Management, v.15 n.1, p.43-60, January 2005 [doi>10.1002/nem.543]
• 13: R. Stone, "Centertrack: An IP Overlay Network for Tracing DoS Floods," Proc. 9th USENIX Sec. Symp., 2000, pp. 319--27.
• 14: M. R. Garey and D. S. Johnson, Computers and Intractability, San Francisco, CA: Freeman, 1979.
• 15: P. Erdös, "On the graph-theorem of Turán," Math. Lapok, vol. 21, pp. 249--251, 1970
• 16: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 17: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 18: B. M. Waxman, "Routing of Multipoint Connections," IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, December 1988.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

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

General Terms:
Design, Management, Security

Keywords:
DDoS, IP tracerback, tracers