IP Traceback

An Improved Single-Packet Hybrid IP Traceback for D/DoS attacks Kamaldeep*1, Manisha Malik2, Dr. Maitreyee Dutta3 *1ME Student, Computer Science Department, National Institute of Technical Teachers Training and Research, Chandigarh, India 2ME Student, Computer Science Department, National Institute of Technical Teachers Training and Research, Chandigarh, India 3Professor and Head, Computer Science Department, National Institute of Technical Teachers Training and Research, Chandigarh, India

*[email protected]; [email protected]; [email protected]

Abstract. As the Internet technologies continue to flourish; cyber-criminals have found several ways to use these technologies to perform various types of cyber-attacks. Among these attacks, D/DoS attacks make an attempt to prohibit legitimate users from accessing resources, which they are eligible for. Attackers use IP Spoofing techniques to hide their original identity on the Internet which makes it even more difficult to prevent and defend these attacks. Hence, a technique that traces the source of packet without relying on its IP address becomes inevitable. Such a technique is called IP traceback. IP traceback schemes like packet logging and hybrid IP traceback trace the source of attack using a few packets. Since, packet logging schemes demand huge storage at the routers, we propose a single-packet hybrid IP traceback approach which considerably reduces the packet logging time at the routers and at the same time resolves the fragmented packet reassembly problem.

1 Introduction There have been a lot of reports and incidents against DDoS attacks on web based popular applications like Amazon, Yahoo, e-bay, Google and their root Domain Name Servers as well. They include politically and economically motivated attacks on companies causing considerable financial losses and several days of downtime. According to a recent survey in 2014, the average recognized DDoS attacks were recorded to be 28 per hour [18]. The impact of attacks has also increased proportionally with the addition of several high end applications and with the increased use of internet in later years [2]. As of December 2014, Sony’s PlayStation and Entertainment Network was hit by a massive DDoS attack costing the company approximately $170M [19]. D/DoS attacks are evolving in frequency and severity, and sophistication of such attacks is increasing very fast. On the basis of number of attacking packets, D/DoS attacks are classified as flooding attacks and software exploit attacks [1]. As for software exploit attacks, attackers need to find hosts’ vulnerabilities and then launch attacks with only a few packets, for example, Teardrop attacks and LAND attacks. In both cases, the consequences are extremely serious that lead to huge financial losses. IP protocol is a stateless protocol and attackers sometimes spoof their IP addresses to perform various attacks. A technique needs to find the origin of attack while not relying on the IP address field of the incoming packet. This technique is known as IP Traceback. IP Traceback systems scout for the real attack sources by employing methods and techniques that do not depend on the source IP address of the packet (that may/ may not be spoofed) [4][5]. Once traced, the source is taken under the security policies of the network and suspected nodes are blocked permanently. IP traceback is a suitable and successful implementation in this regard, where the affected destination node can easily identify the attacker and thus employ required measures to avoid similar attacks [6]. In order to perform traceback of a flooding attack, we require large number of attack packets for path reconstruction. So, packet marking schemes are instituted that

mark the packets with router or path information. Packet marking approaches are categorized into: (i) Deterministic Packet Marking (DPM) and, (ii) Probabilistic Packet Marking(PPM). Savage et al. [9] proposed three PPM approaches, namely: Node append, Node sampling and edge sampling. On the other hand, Belenky and Ansari [11] proposed DPM traceback scheme to overcome the shortcomings of PPM approaches. Each packet is deterministically marked with the IP address of the edge ingress router. The 16-bit Identification field of IP header is used to mark the router's IP address. Since, the complete IP address (32-bit) cannot be marked in a single packet, the address is split into two segments (bits 0-15 and 16-31) and the ID field of each incoming packet is randomly marked with either of these two segments. The 1bit reserved flag is set to 0 if the incoming packet contains the first segment else if the packet contains second segment, the bit is set to 1. The destination needs atleast 7 packets to be able to generate IP address of ingress edge router, so it may not be able to trace origin of software exploit attacks which use only one packet to disenable the system. However, we cannot rely on marking schemes because these attacks are confined to lesser number of packets. For such attacks, packet logging and hybrid schemes are deployed on the routers so that even with a few packets source of attack can be identified. In packet logging, Hash based IP traceback [7][8] can trace even a single IP packet provided, the copy of the packet, its destination and approximate time of the packet’s reception at the victim are available. A Source Path Isolation Engine (SPIE) is developed for this purpose. Our consideration in this paper emphasizes on hybrid traceback techniques which combines the goodness of both packet marking and packet logging techniques. When compared to IP logging schemes, processing and storage overhead at the routers are significantly minimized using Hybrid Scheme. Such schemes lowers the storage overhead on the routers and access time of digest tables. Over time newly emerging ideas and interface numbers of routers came into the picture. Instead of IP addresses or link information specified partially router interface numbers are marked. However, as the mark field size is limited, it still requires storage at the routers. Several techniques like Huffman codes [12], Modulo /Reverse modulo techniques like MRT [13] and MORE [14], and RIHT [15] have used router interface number rather than IP address. A major motivation of this work is to develop an algorithm which decreases the logging time at the routers during the traceback of origins of software exploit attacks and at the same time does not suffer from the problem of reassembly of fragmented packets. In Section 2, we surveyed related research on single packet, packet logging, 32-bit, and 16-bit hybrid traceback techniques. Section 3 discusses our traceback scheme. Section 4 presents a comparative view of our scheme with existing approaches. Section 5 discusses the concluding remarks with scope of future research work.

2 Related Work Single packet traceback is achieved by either packet logging or hybrid schemes. Snoeren et al. [8] proposed a packet logging scheme i.e. SPIE (Source Path Isolation Engine) that stores packet's digest at the routers. The digest is computed by using the invariant bytes of the IP packet en route to the destination i.e. TTL, checksum and ToS bytes not used for computing the digest. The advantage of storing the packet digest rather than packet themselves is preservation of traffic confidentiality. To reduce storage overhead, SPIE uses space efficient data structures called bloom filters to implement digest tables. But, it suffers from the problem of false positives (in Bloom filter) and incurs a lot of storage overhead on the routers. To improve efficiency and precision of SPIE, Zhang and Guan [17] proposed TOPO which itself suffers from false positive problem (in Bloom filter) and needs large storage capacity. Hybrid traceback schemes are another single packet approaches that aim to solve the large storage problem in packet logging schemes. Hybird schemes like Huffman codes[12], Modulo/Reverse Modulo(MORE) [14], Modulo/ Reverse Modulo technique (MRT) [13], RIHT [15] and HAHIT[16], mark packets with router or path information and logs this information if the routers are unable to accommodate mark in the specified marking field. Choi and Dai [12] proposed a marking scheme using Huffman codes for IP

traceback. The interface number of the routers are encoded using Huffman algorithm. The resultant codeword is reversed and then appended to the marking field of the IP packet. If the bit space in marking field in the packet is not sufficient to hold the new codeword, the router sets the log field to 1, computes the message digest of the packet, uses it as an index and logs the marking field in its memory. The router then clears the marking field and forwards the packet to next router. The scheme incurs less computational overhead for traceback, performs better if traffic distribution is unequal for each interface, and even supports traceback of DDoS attacks. However, the scheme suffers from false positive problem whenever the message digest of two or more different packets comes out to be the same. Malliga and Tamilarasi proposed MRT [13], which uses a 32-bit marking field and Modulo/Reverse modulo Technique. The routers mark the packets with modulo technique and reconstruct attack path using reverse modulo technique. The marking procedure is different at the edge router and the core router. Each of the upstream routers mark only if the edge router marks the packet or otherwise not. If packet's mark value exceeds the bit space in marking field, the router computes the digest of the packet, stores it in its memory and reinitializes the marking field to zero. In the reconstruction of attack path, the old marking field and upstream interface number are calculated by the routers to which a packet is traced back. The scheme is non-resistant to MAC spoofing when the edge router maintains a lookup table called MACtoID table. Besides, if MRT’s marking field, after logging, is 0 on the adjoining downstream router, the router will be identified as a logged one during traceback. As a result, it cannot find correct information on the router and is unable to find the origin of an attack. In MRT, the size of a log table escalates rapidly with the number of logged packets. Since, the router's memory is finite, the scheme generates a number of false negatives whenever routers refresh their log tables. M-H Yang and M-C Yang [15] proposed RIHT scheme i.e. Router Interface marking using hash tables. RIHT modifies the formula of marking to prevent the problem of MRT when upstream interface is zero. If the marking field overflows, the router computes the hash of the packet mark, uses it as an index to the hash table and logs the mark and upstream interface into the hash table. The router then calculates the new marking field and sets this as packet mark and forwards packet to the adjacent router. In reconstruction of attack path, the old marking field and the upstream interface number are computed. As RIHT’s log table does not need to be refreshed, it effectively reduces the false negative rate. RIHT uses the IP header's 32bit field (including Identification, flag and fragment offset fields) as marking field. This scheme achieves zero false positive as it does not uses digests to compute index. RIHT aims to have a definite storage requirement of under 320KB and does not need to refresh the logged data. Thus, achieving zero false negatives in attack path reconstruction. Since, RIHT exploits fragment offset field of IP packet as a part of marking field, this scheme is unable to solve the problem caused by packet fragmentation. Thus, the reassembly of fragmented packets at the destination becomes almost impossible. Also, RIHT employs quadratic probing algorithm to search an available index for log table and the unsuccessful search rate increases when each log table has used over half of its slots. Ming Hour Yang [16] proposed HAHIT (Hybrid Single-Packet IP Traceback with low storage and high accuracy) which overcomes the problem of fragmented packers by using only 16-bit Identification field of the IP header as the marking field. Since, the index of a single table is very long for 16-bit marking fields, this scheme further reduces the storage requirement at the routers by using multi-tables to store packets' logs. It is worth noting that in this scheme, different packets on the same route will have the same ID because they use the scheme for marking. Since, this scheme uses ID field, the routers assemble all the fragmented segments according to their offset values. The storage requirement is 2 MB, higher than [15], hence, the chance of router refreshing its memory is negligible resulting in zero false negatives. The scheme has zero false positives because it does not use packet digests for indexing. To minimize the impact of collision and each table's usage rate, [16] sets the load factor to 0.5. However, the approach still uses quadratic probing algorithm causing half of the log tables to be unused which results in wastage of space at the routers. There are two drawbacks of RIHT[15] and HAHIT[16]:  An increased average logging time required in quadratic probing.  The load factor of each hash table in quadratic probing for successful search

can be at most 0.5. We propose an improved scheme which overcomes both these drawbacks in the next section.

3 An Efficient and Improved 16-bit Hybrid Single Packet Traceback Scheme In this section, we propose an improved and efficient hybrid single packet IP traceback scheme which is partly based on RIHT[15]. Our proposed scheme extends and improves RIHT[15] and thus it should not be difficult to apply our scheme to single-packet D/DoS attack situations. We use the double hashing technique to resolve collisions in the hash tables. It is most efficient technique when the size of the table is prime and it also avoids clustering. Besides this, it does not put any restriction on the number of items that can be inserted in the hash table. A brief analysis of different collision resolution techniques on the basis of some evaluation metrics is done in [20]. In order to allow reassembly of fragmented packets at the destination, we use 16bit ID field of an IP header, shown in Table I. Further, our proposed scheme reduces the logging time at the routers. We call a router as a core router if it receives packets from other routers. But, if it receives packets from a local network, it is called a border (or an edge) router. A router can act as a border router as well as a core router simultaneously. The notations used in this paper are listed in Table II. Table I: IP header; ID field used for marking

Following are the assumptions that any router Ri in our network has to satisfy[15]: i. Rk is secure from attacks. ii. A router create an interface table and initializes the upstream interfaces from 0 to D(Rk)-1 in advance. iii. A router knows whether a packet comes from a router or from a local network. iv. All routers in the network support the traceback scheme. Table II: Notations NOTATIONS

MEANING

Rk

{R1, R2, R3,......Rx} routers in a network

D(Rk)

Degree of router Rk

Pi

Received packet Pi

UIk

The upstream interface number of router Rk & it ranges from 0 to D(Rk)-1

Pi.mark

Marking field of Pi

Pi.srcIP

Pi's source IP

HT

Hash table

%

Modulo operation

Our traceback process is composed of two phases: marking/logging phase and the path reconstruction phase. The following subsections will detail the steps of our scheme.

3.1 Marking and Logging When an edge router accrues packets from local network connected to it, it initializes the packet's mark to zero and then passes it on to the adjacent core router in the network. As soon as the core router, say Rk, receives a packet Pi , Rk uses packet's mark (Pi.mark), the incoming interface (UIk), and its degree (D(Rk)) to compute a new marking field: (1) The value of marknew decides whether the packet will be marked or logged at the router. Hence there are two cases: CASE 1: If marknew does not overflow, the core router Rk forwards the packet to the next router after overwriting P i.mark with the computed marknew. CASE 2: If marknew overflows, then the core router calculates hash of packet P i as H(Pi.mark) and inserts Pi.mark and UIk as a pair into the log table; see Algorithm 1. Next, we use the index l to compute a new mark as (2) Then, the router overwrites the packet's Pi.mark with the new mark and the marked packet is forwarded to the next router. Our algorithm for packet marking/logging uses the double hashing collision resolution technique (see italic lines 4-9 in Algorithm 1) instead of quadratic probing as in [15]-[16]. MARK_AND_LOG(P,UIk) 1. begin 2. 3. if marknew > 65535 4. index Pi.mark % m; 5. skip 1 + (Pi.mark % (m - 1)); 6. probe 0; 7. while (HT[index]!=null OR HT[index]!=Pi.mark AND probe