IP Traceback on the Attackers
▶ Introduction

Fig. 1. Attack Path

IP traceback is an solution for defending against distributed denial-of-service attacks (DDoS). The purpose of IP traceback [1] is to identify the actual source of attack packets. Among many proposed schemes [1], [6] for IP traceback, Probabilistic Packet Marking scheme [2] is practical due to its low router overhead and incremental deployment support. Probabilistic Packet Marking (PPM) [2] is a scheme for IP traceback, where routers on the attack path from attacker to victim randomly mark traversing packets with their IP addresses in order for the victim (collector) to infer the path of attack. In this scheme, once a router decides to mark, it will overwrite the previous mark of the previous router on a packet. Therefore, each received packet at the collector contains at most one router’s mark. Thus, the collector’s problem in the PPM scheme is to collect all distinct markings of routers on the attack path, which is essentially a Coupon Collector’s Problem (CCP) [3, pp. 32].
Fig. 2. PPM scheme on an attack path with a setting of marking probabilities

Fig. 3. IP Header Encoding

There are some well known PPM-based schemes: Fragment Marking Scheme (FMS) [2], Advanced Marking Scheme (AMS) [7], and Fast Internet Traceback (FIT) [8]. They mainly use 16-bit IP identification field [2] in IPv4 packet header for marking, and could use more 8-bit TOS field and 1-bit fragment flag [9].

FMS [2] can do well in the single-path attack, but it has large number of false positives and high computation overhead in the multi-path attacks due to very large possible number of combinations of fragments marked at the same distance [7].

AMS [7] tackled FMS’s problems by assuming a map of upstream routers already built by traceroute tool before and using a set of hash functions instead of fragmentation to avoid gathering fragments, which reduce false positives and computation in the path reconstruction phase during attacks.

FIT [8] proposed using packet marking instead of traceroute tool in AMS to reduce false positives in the map of upstream routers. It also proposed a 1-bit distance mechanism (instead of well known 5-bit using) together with TTL modification technique, which enlarges allocated space for marking leading to reduced false positives in the path reconstruction phase. However, FIT scheme always has false positives in the map reconstruction phase because FIT routers put its hash fragments in traversing packets, which impacts on the false positives in the path reconstruction phase.

In [4], Sattari et al. proposed a Practical PPM+NC scheme that combines random linear network coding [10] with PPM, where each marked packet received at the victim contains k b-bit coefficients drawn uniformly at random from the Galois field and an associated linear combination result of k fragments with same offset from k consecutive traceback routers. Simulations demonstrated that this scheme requires less average number of packets than FMS scheme to derive all routers on the attack path. However, it has several limitations.

▶ Research Issues

  • Number of Attacking Packets Needed for Traceback
  • Processing Overhead
  • Bandwidth Overhead
  • Memory Requirement
  • Scalability

  • ▶ References

    1. A. Belenky and N. Ansari, “On IP Traceback,” Communications Magazine, IEEE, 2003.
    2. S. Savage, D.Wetherall, A. Karlin, and T. Anderson, “Network Support for IP Traceback,” Networking, IEEE/ACM Transactions on, 2001.
    3. M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.
    4. P. Sattari, M. Gjoka, and A. Markopoulou, “A Network Coding Approach to IP Traceback,” Network Coding (NetCod), IEEE, 2010.
    5. C. Fragouli and E. Soljanin, Network Coding Applications, Foundations and Trends in Networking, 2007.
    6. M. Siddiqui, S. Amin, and C.S. Hong, “Hop-by-hop traceback in wireless sensor networks,” Communications Letters, IEEE, vol.16, no.2, pp.242 ?245, february 2012.
    7. D.X. Song and A. Perrig, “Advanced and Authenticated Marking Schemes for IP Traceback,” Proc. of IEEE INFOCOM 2001, 2001.
    8. A. Yaar, A. Perrig, and D. Song, “FIT: Fast Internet Traceback,” Proc. of IEEE INFOCOM 2005, 2005.
    9. D. Dean, M. Franklin, and A. Stubblefield, “An Algebraic Approach to IP Traceback,” ACM Trans. Inf. Syst. Secur., 2002.
    10. T. Ho and D. Lun, Network Coding: An Introduction, Cambridge University Press, 2008.
    11. G. Strang, Introduction to Linear Algebra, 4th Edition, Wellesley Cambridge Press, 2009.
    12. S.M. Ross, Introduction to Probability Models, Tenth Edition, Academic Press, 2009.

    ▶ Achievements

    1. Dung Tien NGO, Tuan Anh LE, Choong Seon HONG, Sungwon LEE, Won-Tae LEE and Jae -Jo LEE, "Benefit of Network Coding for Probabilistic Packet Marking and Collecting Coupons from Different Perspectives at the Collector", IEICE Transactions on Communications 2013 (in press)
    2. Dung Tien Ngo, Choong Seon Hong, "Limitations of Proof for Benefit of Network Coding to IP Traceback", 2012 한국컴퓨터종합학술대회(KCC 2012), 2012.6.27~29(29)
    3. Ngo Tien Duong, Choong Seon Hong, "Analysis of Algorithm design in the Fast Internet Traceback scheme", 한국정보과학회 2010년 가을 학술 발표 논문집(KIISE 2010), 2010년 11월 5일-11월 6일
    4. Syed Obaid Amin, Muhammad Shoaib Siddiqui and Choong Seon Hong, "A Novel IPv6 Traceback Architecture Using COPS Protocol", Annals of Telecommunications, 19 Feb 2008
    5. Syed Obaid Amin, Myung Su Kang and Choong Seon Hong, “A Lightweight IP Traceback Mechanism on IPv6”, EUC Workshops 2006, LNCS 4097(EUC 2006), pp.671-680, August 2006. (acceptance rate: 27.2%)
    6. Syed Obaid Amin, Choong Seon Hong, “On IPv6 Traceback”, Proceedings of 8th IEEE ICACT 2006, Volume III, pp.2139-2143, Phoenix Park, Korea, 20-22 February 2006
    7. Syed Obaid Amin, Choong Seon Hong, Dongjin Kwak, and Jaehwa Lee, "IPv6 Traceback Using Policy Based Management System", KNOM Review, Vol.9, No.2, pp. 1-7, Dec. 2006
    8. Dae Sun Kim, Choong Seon Hong, Yu Xiang, “An Intelligent Approach of Packet Marking at Edge Router for IP Traceback”, Lecture Notes in Artificial Intelligence, pp. 303-308, Vol. 3683, September 2005
    9. Syed Obaid Amin, Choong Seon Hong, Il Joong Kim “On IPv6 Traceback using Deterministic Packet Marking”, 한국정보처리학회 추계학술발표대회 논문집 제12권 제2호(하), pp. 977-980, 2005년 11월
    10. Yu Xiang, Choong Seon Hong, "An Approach of Marking Packet at Source Side For IP Traceback", WISA 2004, pp. 713-720, August 2004
    11. 이호재,홍충선, "Active Network 기반 Lightweight IP Traceback 메커니즘 개발", 한국정보처리학회 추계학술발표대회, 제 11권 2호, pp.1229-1234, November 2004
    12. 여상, 홍충선, "An Efficient Approach of Marking Packet at Source Side for IP Traceback", 한국통신학회 하계학술발표대회, July 2004