Unformatted text preview:

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 ProblemDenial of Service (DoS) attackRemotely consume resource of server or networkIncrease in number and frequencySimple to implementDoS attacks are difficult to trace:IndirectionAttacking packets sent from slave machines, which under the control of a remote master machineSpoof of IP source addressesDisguise their location using incorrect IP addresses, hence the true origin is lost2Packet Marking TracebackMark packets with router addressdeterministically or probabilisticallyTrace attack using marked packetsProsRequire no cooperation with ISPsDoes not cause heavy network overheadCan trace attack “post mortem”3Multiple AttackersA1A2A3R5R3R6R7R4R2R1attackorigin4victimVExact Traceback ProblemA1A2A3R5R3R6R7R4R2R1Vattackpathexact tracebackR6, R3, R2, R15Approximate Traceback ProblemA1A2A3R5R3R6R7R4R2R1Vapprox. tracebackR5, R6, R3, R2, R16MethodologyI. Marking procedureby routersadd information to packetsII. Path reconstruction procedureby victimuse information in marked packetsconvergence time: # of packets to reconstruct the attack path7Basic Marking AlgorithmsI. Node AppendII. Node SamplingIII. Edge Sampling8I. Node AppendAppend address of each node to the end of the packetComplete, ordered list of routers attack pathoriginal packetrouter list9I. Node AppendProscomplete, ordered attack pathconverge quickly (single packet)Consinfeasibly high router overheadattacks can create false path information10II. Node SamplingReserve node file in packet headerRouter write address in node field with probability pReconstruct path using relative # of node samplesOnly require additional write, checksum update11II. Node SamplingR1R1R2R312II. Node SamplingR1R1R2R313II. Node SamplingR1R1R2R314II. Node SamplingR1R3R2R315II. Node SamplingCons:Slow convergenceneed many packetsusually order of 10,000 - 100,000Can not trace multiple attackers ▪16III. Edge SamplingEdge represent routers at each end of the linkStore edges instead of nodesstart and end addresses of edge routersdistance from edge to victim17R1R2III. Edge SamplingA router writes its own address in the start field, and 0 into the distance fieldDistance field of 0 means the packet is already markedrouter writes its own address in the end address field and increase the distance field by 1Other routers may then reset these fields. Otherwise, the distance field is incremented18III. Edge SamplingR1R2R3R1#1 #119III. Edge SamplingR1R2R3R1#1 020III. Edge SamplingR1R2R3R1R2121III. Edge SamplingR1R2R3R1R2222Path ReconstuctionConsider G is a graph with root vInsert tuples (start, end, distance) into GRemove any edge (x, y, d) with d != distance from x to v in GExtract path from G23III. Edge SamplingProsConverge much faster than node samplingEfficiently discern multiple attacksConsSpace: 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 IssueOverload the IP identification fieldused for fragmentationDecreases the space requirementstore the XOR of the edge addresses (edge-id)- B XOR A XOR B = APros:Reduced spaceCons: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-idReduce per packet space more by dividing the edge-id (XORed address) into k non-overlapping packets, and store only 1 of themNeed offset of fragment28Creating Unique Edge-idsProblem: Edge-id fragments are not uniquewith multiple attackers, multiple edge fragments with the same offset and distanceSolutoin: Bit-interleave hash code with IP address29Creating Unique Edge-ids0000...1111AddressHash(Address)0011…110000000101...11111010Bit-interleavesend k fragments into network0 k-130Candidate Edge-idsCombine all permutations of fragments at each distance with disjoint offset valuesCheck 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 FragmentsOverload the 16-bit identification fieldused to differentiate IP fragments33Testing the AlgorithmSimulatorCreate random pathsOriginate attacksMarking probability is 1/251,000 random test runsvary path lengths34Experimental Resultsnumber of packets to reconstruct paths35Thanks for listeningQuestions?36Backup slidesFuture WorkSuffix validationspoof end edgesinclude a router “secret”Attack origin (host)Find attacker (person)37Related ResearchSteven 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.pdf38ReferencesStefan 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

Purdue CS 63600 - Lecture notes

Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?