Slide 1The ProblemPacket Marking TracebackMultiple AttackersExact Traceback ProblemApproximate Traceback ProblemMethodologyBasic Marking AlgorithmsI. Node AppendI. Node AppendII. Node SamplingII. Node SamplingII. Node SamplingII. Node SamplingII. Node SamplingII. Node SamplingIII. Edge SamplingIII. Edge SamplingIII. Edge SamplingIII. Edge SamplingIII. Edge SamplingIII. Edge SamplingPath ReconstuctionIII. Edge SamplingEncoding IssueMarking With XORReconstructing With XORSubdividing Edge-idCreating Unique Edge-idsCreating Unique Edge-idsCandidate Edge-idsConstruction Candidate EdgesEncoding Edge FragmentsTesting the AlgorithmExperimental ResultsSlide 36Backup slides Future WorkRelated ResearchReferencesDoS Counter MeasuresIngress FilteringLink TestingInput DebuggingControlled FloodingLoggingICMP TracebackDoS Attack AssumptionsDesign AssumptionsIP Header EncodingFragmentation IssuesEvaluationNETWORK SUPPORT FOR IP TRACEBACK-SIGCOMM ‘00Stefan Savage, David Wetherall, Anna Karlin and Tom AndersonUniversity of Washington- Seattle, WAPresented by Mohammad Hajjat- Purdue UniversitySlides courtesy of Teng Fei - Umass April, 20021The ProblemDenial of Service (DoS) attackRemotely consume resource of server or networkIncrease in number and frequencySimple to implementDoS attacks are difficult to trace:IndirectionAttacking packets sent from slave machines, which under the control of a remote master machineSpoof of IP source addressesDisguise their location using incorrect IP addresses, hence the true origin is lost2Packet Marking TracebackMark packets with router addressdeterministically or probabilisticallyTrace attack using marked packetsProsRequire no cooperation with ISPsDoes not cause heavy network overheadCan trace attack “post mortem”3Multiple AttackersA1A2A3R5R3R6R7R4R2R1attackorigin4victimVExact Traceback ProblemA1A2A3R5R3R6R7R4R2R1Vattackpathexact tracebackR6, R3, R2, R15Approximate Traceback ProblemA1A2A3R5R3R6R7R4R2R1Vapprox. tracebackR5, R6, R3, R2, R16MethodologyI. Marking procedureby routersadd information to packetsII. Path reconstruction procedureby victimuse information in marked packetsconvergence time: # of packets to reconstruct the attack path7Basic Marking AlgorithmsI. Node AppendII. Node SamplingIII. Edge Sampling8I. Node AppendAppend address of each node to the end of the packetComplete, ordered list of routers attack pathoriginal packetrouter list9I. Node AppendProscomplete, ordered attack pathconverge quickly (single packet)Consinfeasibly high router overheadattacks can create false path information10II. Node SamplingReserve node file in packet headerRouter write address in node field with probability pReconstruct path using relative # of node samplesOnly require additional write, checksum update11II. Node SamplingR1R1R2R312II. Node SamplingR1R1R2R313II. Node SamplingR1R1R2R314II. Node SamplingR1R3R2R315II. Node SamplingCons:Slow convergenceneed many packetsusually order of 10,000 - 100,000Can not trace multiple attackers ▪16III. Edge SamplingEdge represent routers at each end of the linkStore edges instead of nodesstart and end addresses of edge routersdistance from edge to victim17R1R2III. Edge SamplingA router writes its own address in the start field, and 0 into the distance fieldDistance field of 0 means the packet is already markedrouter writes its own address in the end address field and increase the distance field by 1Other routers may then reset these fields. Otherwise, the distance field is incremented18III. Edge SamplingR1R2R3R1#1 #119III. Edge SamplingR1R2R3R1#1 020III. Edge SamplingR1R2R3R1R2121III. Edge SamplingR1R2R3R1R2222Path ReconstuctionConsider G is a graph with root vInsert tuples (start, end, distance) into GRemove any edge (x, y, d) with d != distance from x to v in GExtract path from G23III. Edge SamplingProsConverge much faster than node samplingEfficiently discern multiple attacksConsSpace: requires additional space in the IP header- 72 bits of space in every IP packet (2 x 32 bit IP address and 8 bit for distance) Compatibility ▪24Encoding IssueOverload the IP identification fieldused for fragmentationDecreases the space requirementstore the XOR of the edge addresses (edge-id)- B XOR A XOR B = APros:Reduced spaceCons:Increases reconstruction time25Marking With XORabc d vattack pathresulting XOR edgesa XOR bb XOR c c XOR d d26Reconstructing With XORa XOR bb XOR cc XOR d dcreconstructed pathba27Subdividing Edge-idReduce per packet space more by dividing the edge-id (XORed address) into k non-overlapping packets, and store only 1 of themNeed offset of fragment28Creating Unique Edge-idsProblem: Edge-id fragments are not uniquewith multiple attackers, multiple edge fragments with the same offset and distanceSolutoin: Bit-interleave hash code with IP address29Creating Unique Edge-ids0000...1111AddressHash(Address)0011…110000000101...11111010Bit-interleavesend k fragments into network0 k-130Candidate Edge-idsCombine all permutations of fragments at each distance with disjoint offset valuesCheck that the hash matches hash of the address31Construction Candidate Edges0000...1111Address?Hash(Address)?0011…110000000101...111110100k-1Hash(Address?)0011…1100=?No, rejectYes, correct address32Encoding Edge FragmentsOverload the 16-bit identification fieldused to differentiate IP fragments33Testing the AlgorithmSimulatorCreate random pathsOriginate attacksMarking probability is 1/251,000 random test runsvary path lengths34Experimental Resultsnumber of packets to reconstruct paths35Thanks for listeningQuestions?36Backup slidesFuture WorkSuffix validationspoof end edgesinclude a router “secret”Attack origin (host)Find attacker (person)37Related ResearchSteven M. Bellovin ICMP Traceback Message AT&Thttp://www.research.att.com/~smb/papers/draft-bellovin-itrace-00.txt Alex Snoeren Hash-Based IP Traceback BBN SigCOMMhttp://www.acm.org/sigcomm/sigcomm2001/p1-snoeren.pdf38ReferencesStefan Savage Practical Network Support For IP Traceback http://www.cs.washington.edu/homes/savage/papers/UW-CSE-00-02-01.pdf Sara Sprenkle Practical Network Support Duke Universityhttp://www.duke.edu/~ses12/presentations/nerdSavage.ppt Hal Burch IP Traceback Carnegie Mellon
View Full Document