Traceback for Wireless Sensor Networks
▶ Introduction

Traceback in communicatio networks is a promising solution to counter the spoofed attacks by determining the probable source of the malicious packet(s) or the attack path(s). Traceback schemes are very well addressed in the literature; however, most of the schemes are proposed for IP networks and very limited work can be seen in the field of WSN (Wireless Sensor Network) traceback. The traceback schemes proposed for IP networks are not straight forwardly applicable to WSN, as traditional IP traceback solutions require fair amount of resources to be implemented; however, private ownership of WSNs makes it relatively easier to add a traceback support as compared to traditional IP networks. Traceback schemes can be divided into three categories: messaging, packet marking, and logging. Messaging has communication overhead due to extra message passing and packet marking requires extra bits in packet header, which increases the size of packets. As communication is the most costly function in a sensor node, our work falls under the category of logging based traceback; in which packet relaying nodes store the information of the forwarded packets in a suitable data structure. In case of an attack, the victims consult upstream nodes to reconstruct attack paths by broadcasting the information of the malicious packet(s) in the traceback request.

Very limited work has been done on logging based traceback schemes for WSNs. We can see two schemes namely CAPTRA and SNTS in this regard. Both of these schemes use Bloom filters to store the traffic logs. A Bloom filter is a randomized data structure, which is represented in a form of a bit vector. It is used for membership queries, whether an entity (data packet in traceback) in question is a part of the dataset or not; however, with controllable false positives. In its basic form, a Bloom filter can only be used for membership queries. It does not have any information about the entity who added the element in question; therefore, a traceback request is usually broadcasted to the neighboring nodes. Consequently, due to the false positives of Bloom filter, the chances of generating false query also increase. To eliminate this shortcoming, we propose two advancements in current Bloom filter based traceback schemes for WSNs.

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