Sharad Agarwal Network Reading Group Presentation Notes ======================= Hash Based IP Traceback ======================= GOAL Reliably identify the originator of an IP packet WHY IMPORTANT Identify attackers attack = degrades performance, disable vital services ___WHAT DOES THIS MEAN?___ ___what is an attack vs normal use?___ Make them accountable DIFFICULTIES Stateless routers ___WHAT PROBLEMS WOULD BE SOLVED W/ STATEFUL ROUTERS?___ Spoofed IP addresses NAT Mobile-IP UDLR Inadequate ingress Filtering ___TERM TRANSIT NETWORK USED RATHER LOOSELY___ Unstable routing Weak end hosts Low storage at routers Privacy ASSUMPTIONS Identify means ingress point to traceback-enabled network host or network of origin compromised router in enabled network ___NOT___ Do this infrequently Concerned with low packet attacks Ignore compromised routers Ignore packet munging Ignore duplicate packets Ignore non-first fragmented packets Ignore lossy fragmented encapsulated packets PAST WORK ???? SOLUTION Make routers stateful, temporarily Hash based technique (SPIE) recent past space efficient (0.5% of link capacity / time storage) uses packet digests 32 Bytes ver, length, protocol, addrs, 8bytes of payload 0.00092% WA 0.139% LAN collision ___WHAT % IS ACCEPTABLE?___ Bloom filters computes k distinct packet digests per packet using independent uniform has functions uses n-bit results to index into a 2^n sized shared bit array (init 0, set 1 on receipt) different routers use diff functions k? n? false positives? clearing time? size? ___NOTE: NO FALSE NEGATIVES___ Transformed packets store TLT (64 bits / packet) capture suspect packet, victim last hop, time reverse-path flooding FreeBSD implementation MD5 hash functions random selection k = 4 n = 32 BBN topology of 70 routers simulate attack - 1000 attack packets false positive rate - background traffic ___WHY NOT USE PREVIOUS WA LAN TRAFFIC?___ memory & refresh 0.5% of link capacity in table Scalable Packet Classification ============================== GOAL Packet classification scalable (in rules, upto 100,000) wire speed WHY IMPORTANT Routers do additional processing differentiated services security load balancing traffic measurements Need to classify packets into flows DIFFICULTIES / PAST WORK Linear time search Linear amount of TCAMS Lucent scheme worst case doesn't scale ASSUMPTIONS SOLUTION Aggregated Bit Vector improvement on Lucent bit vector rule aggregation rule rearrangement Lucent Bit Vector Linear Search k one-dimension tries each node - N bit vector N = number of rules k = number of fields which rules match on packet receipt longest match for each field intersect matches O(Nk/W) find lowest cost (highest order) Rule Aggregation bit vectors are sparse i.e., few rules match split N bit vector into A bit chunks ___NOTE: BUG IN FIG 2, FIELD 2, 10___ ___POOR MAN'S COMPRESSION___ intersect matches of length N/A intersect matching vectors of length A false matches possible Rule Rearrangement overlap is rare place rules w/ common values together sort out rule ordering later Evaluation ___WHO CARES ABOUT STARTUP & ADD & DEL___ storage is marginally higher worst case lookup is worse!! ___OPTIMIZING FOR COMMON CASE___ 4 firewall DBs 40-75% reduction in mem accesses some ___CONFUSING___ use of routing tables ___ACK IS WEIRD - WAS THERE A 3rd AUTHOR?___