Hop-Count Filtering: An Effective Defense Against Spoofed DDos Traffic :1 Hop-Count Filtering: An Effective Defense Against Spoofed DDos Traffic Cheng Jin CS Department Caltech Pasadena Haining Wang CS Department College of William and Mary Williamsburg Kang G. Shin EECS Department University of Michigan Ann Arbor CCS’03, October 27–31, 2003


Outline :2 Outline Introduction Hop-count inspection Feasibility of hop-count filtering Effectiveness of HCF Construction of HCF table Running states of HCF Resource Savings Related work Conclusion and future work


INTRODUCTION :3 INTRODUCTION IP spoofing makes DDoS attack more difficult to defend against. Conceal flooding sources and localities in flooding traffic Coax legitimate hosts into becoming reflectors Two approaches to thwart DDoS attack Router-based Victim-based


INTRODUCTION :4 INTRODUCTION Router-based : improve routing infrastructure Off-line analysis of flooding traffic Off-line IP traceback On-line filtering of DDoS traffic inside routers Rely on IP router enhancement Victim-based : enhances the resilience of Internet servers against attacks Advantage of being immediately deployable Current approach : resource management


INTRODUCTION :5 INTRODUCTION Hop-Count Filtering (HCF) Victim-based filtering Using TTL field of IP header to determine hop counts build an IP-to-hop count(IP2HC) mapping table using a moderate amount of storage clustering address prefixes based on hop-count. pollution-proof method update procedure for the IP2HC mapping table that prevents pollution by HCF-aware attackers. IP2HC mapping table initialization and adding new IP addresses Two running states : alert and action


HOP-COUNT INSPECTIONTTL-based Hop-Count Computation :6 HOP-COUNT INSPECTIONTTL-based Hop-Count Computation The challenge in hop-count computation a destination only sees the final TTL value. Final TTL value= initial TTL value – hop-count cannot assume a single static initial TTL value for each IP address. Fortunately, most modern OSs use only a few initial TTL values, 30, 32, 60, 64, 128, 255. most of these initial TTL values are far apart except {30,32} {60,64},{32,60} Since Internet traces have shown that few Internet hosts are apart by more than 30 hops


HOP-COUNT INSPECTIONInspection Algorithm :7 HOP-COUNT INSPECTIONInspection Algorithm


FEASIBILITY OF HCFHop-Count Stability :8 FEASIBILITY OF HCFHop-Count Stability The feasibility of HCF hinges on three factors: (1) stability of hop-counts (2) diversity of hop-count distribution (3) robustness against possible evasions stability of hop-counts Frequent changes in the hop-count excessive mapping updates out-of-date mapping Dictated by the end-to-end routing behaviors two thirds of the Internet paths persist for either days or weeks 95%of the paths had fewer than five observable daily changes


FEASIBILITY OF HCFDiversity of Hop-Count Distribution :9 FEASIBILITY OF HCFDiversity of Hop-Count Distribution a diverse hop-count distribution is critical to effective filtering. the hop-count distributions at all traceroute gateways the Gaussian distribution (bell-shaped curve) is a good first-order approximation. We are interested in the girth of a distribution We are not making any definitive claim of whether hop-count distributions are Gaussian or not. The largest percentage of IP addresses that have a common hop-count value is only 10%.


FEASIBILITY OF HCFDiversity of Hop-Count Distribution :10 FEASIBILITY OF HCFDiversity of Hop-Count Distribution


FEASIBILITY OF HCFDiversity of Hop-Count Distribution :11 FEASIBILITY OF HCFDiversity of Hop-Count Distribution


FEASIBILITY OF HCFDiversity of Hop-Count Distribution :12 FEASIBILITY OF HCFDiversity of Hop-Count Distribution most of the mean values fall between 14 and 19 hop


FEASIBILITY OF HCFDiversity of Hop-Count Distribution :13 FEASIBILITY OF HCFDiversity of Hop-Count Distribution standard deviations between 3 and 5 hops.


FEASIBILITY OF HCFRobustness against Evasion :14 FEASIBILITY OF HCFRobustness against Evasion The key for an attacker to evade HCF is to set an appropriate initial TTL value build a priori an IP2HC mapping table that covers the entire random IP address space. attacker cannot observe the final TTL values of normal traffic at the victim. have to compromise at least one end-host behind every stub network whose IP addresses are in the random IP address space


FEASIBILITY OF HCFRobustness against Evasion :15 FEASIBILITY OF HCFRobustness against Evasion Without compromising end-host probe the hs value for the quiescent host (1) force the victim into the action state by launching a DDoS attack (2) probe the quiescent host and extract the latest value of its IP ID field of the header (3) send a spoofed packet with a tentative initial TTL (4) re-probe the quiescent host and check if its IP ID has increased by more than one. accurate router-level topology of the Internet / the underlying routing algorithms and policies. topology maps are generally time-averaged approximations the routing policies are not disclosed to the public.


EFFECTIVENESS OF HCFSimple Attacks :16 EFFECTIVENESS OF HCFSimple Attacks Single source Given a single flooding source whose hop-count to the victim is h, let ah denote the fraction of IP addresses that have the same hop-count to the victim as the flooding source. the fraction of spoofed IP addresses that cannot be detected is ah. The remaining fraction 1-ah will be identified and discarded by HCF. Multiple sources n sources that flood a total of F packets, each flooding source generates F/n spoofed packets. The fraction, Z, of identifiable spoofed packets generated by n flooding sources is:


EFFECTIVENESS OF HCFSimple Attacks :17 EFFECTIVENESS OF HCFSimple Attacks


EFFECTIVENESS OF HCFSimple Attacks :18 EFFECTIVENESS OF HCFSimple Attacks


EFFECTIVENESS OF HCFSophisticated Attackers :19 EFFECTIVENESS OF HCFSophisticated Attackers


EFFECTIVENESS OF HCFSophisticated Attackers :20 EFFECTIVENESS OF HCFSophisticated Attackers a uniform distribution the range of possible hop-counts is [hi, hj ] where i = j and H = j-i+1 the fraction of spoofed source IP addresses that have correct TTL values, is given as: initial TTLs within the range [hm,hn], based on some known distribution the probability of IP addresses with hop-count hk is phk . the fraction of the IP addresses that have a hop-count of hk is ahk , the fraction of the spoofed IP packets that will not be caught by HCF is:


EFFECTIVENESS OF HCFSophisticated Attackers :21 EFFECTIVENESS OF HCFSophisticated Attackers Hop-count between 10~20,so H=11 Summation’s maximum=1 So maximum


EFFECTIVENESS OF HCFSophisticated Attackers :22 EFFECTIVENESS OF HCFSophisticated Attackers m=0,n=30


CONSTRUCTION OF HCF TABLEIP Address Aggregation :23 CONSTRUCTION OF HCF TABLEIP Address Aggregation objectives in building an HCF table are: (1) accurate IP2HC mapping, (2) up-to-date IP2HC mapping (3) moderate storage requirement. By aggregating IP address reduce the space requirement of IP2HC covers those unseen co-located IP addresses Aggregation into 24-bit Address Prefixes straightforward to implement and can offer fast lookup a one-byte entry per network prefix for hop-count, the storage requirement is 2^24 bytes or 16 MB. Aggregation with Hop-Count Clustering


CONSTRUCTION OF HCF TABLEIP Address Aggregation :24 CONSTRUCTION OF HCF TABLEIP Address Aggregation


CONSTRUCTION OF HCF TABLEIP Address Aggregation :25 CONSTRUCTION OF HCF TABLEIP Address Aggregation


CONSTRUCTION OF HCF TABLEIP Address Aggregation :26 CONSTRUCTION OF HCF TABLEIP Address Aggregation


CONSTRUCTION OF HCF TABLEPollution-Proof Initialization and Update :27 CONSTRUCTION OF HCF TABLEPollution-Proof Initialization and Update Keeping the IP2HC mapping up-to-date is necessary initialization and dynamic update is through TCP connection establishment One way to ensure that only legitimate packets are used attacker cannot slowly pollute an HCF table by spoofing source IP addresses. may be too expensive to inspect and update with each newly-established TCP connection user-configurable parameter to adjust the frequency of update. a counter p that records the number of established TCP connections p can also be a function of system load and hence, updates are made more frequently when the system is lightly-loaded. mapping updates may require re-clustering hop-count changes are not a frequent event, the overhead incurred by re-clustering is negligible.


RUNNING STATES OF HCF :28 RUNNING STATES OF HCF


RUNNING STATES OF HCF :29 RUNNING STATES OF HCF Introduction of the alert state lowers the overhead of HCF stop DRDoS HCF specifically looks for IP spoofing, so it will be able to detect attempts to fool servers into acting as reflectors. Blocking Bandwidth Attacks detection and filtering (at the ISP’s edge router) of spoofed packets must be separated One or more machines inside the stub network and the access router must run HCF at least one machine inside the stub network maintain an updated HCF table


RUNNING STATES OF HCF :30 RUNNING STATES OF HCF


RESOURCE SAVINGSBuilding the Hop-Count Filter :31 RESOURCE SAVINGSBuilding the Hop-Count Filter The test module resides in the IP packet receive function, ip_rcv. insert the filtering function before the expensive checksum verification. The hop-count mapping 4096-bucket hash table with chaining to resolve collisions. Each entry in the hash table represents a 24-bit address prefix. A binary tree is used to cluster hosts within each 24-bit address prefix. This tree can then be implemented as a linear array of 127 elements. Each element in the array stores the hop-count value of a particular clustering. the HCF-table update insert the function call into the kernel TCP code


RESOURCE SAVINGSExperimental Evaluation :32 RESOURCE SAVINGSExperimental Evaluation


RESOURCE SAVINGSExperimental Evaluation :33 RESOURCE SAVINGSExperimental Evaluation Without HCF ,CPU cycles=a*tD+b*tL With HCF,CPU cycles=(1-a)*a*tDF+a*a*td+b*(tL+tLF)


RELATED WORK :34 RELATED WORK Despoof compares the TTL of a received packet with the actual TTL of a test packet sent to the source IP address Requires the administrator to determine ,and manually verify. High overhead Detecting spoofed packets. S. Templeton/K. Levitt. using TTL for detecting spoofed packet ingress filtering blocks spoofed packets at edge routers, Rely on wide-eployment in IP routers. route-based distributed packet filtering (DPF) Given the reachability constraints


RELATED WORK :35 RELATED WORK SAVE builds a table of incoming source IP addresses at each router associates each of its incoming interfaces with a set of valid incoming network Path Identifier (Pi) IP traceback marking a path fingerprint in each packet


CONCLUSION FUTURE WORK :36 CONCLUSION FUTURE WORK HCF Can detect and discard spoofed IP Without router support Using moderate storage NAT (Network Address Translator) each of which may connect multiple stub networks, could make a single IP address appear to have multiple valid hop-counts at the same time install the HCF system at a victim site for practical use