Source: http://www.google.com/patents/US7873997?dq=645576
Timestamp: 2017-10-22 04:42:48
Document Index: 194485477

Matched Legal Cases: ['art0', 'art0', 'art0', 'art0', 'art1', 'art0']

Patent US7873997 - Deterministic packet marking - Google Patents
The deterministic packet marking (DPM) method is based on marking packets with the partial address information of ingress interface only. The attack victim is able to recover the complete address(es) information after receiving several packets from a particular attacking host or hosts. The full path...http://www.google.com/patents/US7873997?utm_source=gb-gplus-sharePatent US7873997 - Deterministic packet marking
Publication number US7873997 B2
Application number US 11/079,453
Also published as US20050204171
Publication number 079453, 11079453, US 7873997 B2, US 7873997B2, US-B2-7873997, US7873997 B2, US7873997B2
Inventors Andrey Belenky, Nirwan Ansari
Patent Citations (7), Non-Patent Citations (27), Referenced by (2), Classifications (5), Legal Events (2)
US 7873997 B2
2. The method of claim 1 wherein the network communication device is a router interface.
3. The method of claim 1, wherein the set of bits of the network address written into the packet is selected at random, for each received packet, from among a collection of sets of bits corresponding to non-overlapping sets of bits of the network address.
4. The method of claim 1 wherein the information is written in a header of the packet.
5. The method of claim 1 wherein the packet is an Internet Protocol (IP) version 4 packet.
6. The method of claim 5 wherein the information is written into identification field and reserved flag field of the packet.
7. The method of claim 1 wherein the packet is an Internet Protocol (IP) version 6 packet.
at startup, preparing k marks corresponding to respective non-overlapping, equal-length segments of the network address, wherein a respective mark includes three fields: a-bit address segment field, d-bit digest field, and s-bit segment number field;
calculating once and inserting in a digest field of every mark a d-bit hash value, of the network address, each of the k marks having address segment bits set to a different segment of the network address, and the segment number field being set to a value corresponding to the address segment; and
generating a small random number from 0 to k−1 and inserting a corresponding mark into the received packet as said information.
9. A method in accordance with claim 1, wherein a family of ƒ hash functions, H0(x) through Hƒ-1(x), is used to produce ƒ digests of the network address, and wherein the digest of the entire network address includes a selected one of the digests produced by the ƒ hash functions concatenated with a hash function identifier corresponding to the hash function used to produce the selected one of the digests.
a processor configured to modify each received packet by writing into the received racket information comprising a set of bits including one or more consecutive bits of a network address of the communication device, a digest of the entire network address, and an identifier of the set of bits; and
11. A method for identifying, by a device at a victim destination of an anonymous attack in a network in which the victim destination resides, a source of the anonymous attack, the method comprising:
receiving at the victim destination sufficient ones of marked packets to recover an entire ingress address corresponding to at least a subset of the packets, wherein each packet entering the network is marked by an ingress node through which the packet enters the network, with information including a set of bits comprising one or more consecutive bits of a network address of the ingress node, a digest of the entire network address of the ingress node, and an identifier of the set of bits, and wherein the information remains unchanged for as long as the packet traverses the network; and
correlating the recovered ingress address with the source address of the associated packets upon entering the network, to thereby identify the ingress address for the source address.
12. A method in accordance with claim 11, wherein the node comprises a said packet entering the network is marker an edge ingress router.
13. A method in accordance with claim 12, wherein incoming packets to the network are marked and outgoing packets leaving the network are not marked, thereby assuring that an egress router will not overwrite the marks placed by said ingress router.
14. A method in accordance with claim 13, wherein a continuous perimeter of marking enabled interfaces is maintained.
15. A method in accordance with claim 11, wherein said correlating is enabled by an ingress table maintained at said victim for matching source addresses to ingress addresses.
16. A method in accordance with claim 15, further including placing the said ingress address segments at the victim destination in a reconstruction table, identifying the ingress address out of the possible permutations of the segments, and transferring the identified ingress address to said ingress table.
17. A method in accordance with claim 16, wherein a single hash function is used for identifying the segments of an ingress address.
18. A method in accordance with claim 16, wherein a family of hash functions is used for identifying the segments of an ingress address.
19. A method in accordance with claim 16, wherein a family of ƒ hash functions, H0(x) through Hƒ-1(x), is used to produce ƒ digests of the network address of the ingress node, and wherein the digest of the entire network address of the ingress node includes a selected one of the digests produced by the ƒ hash functions concatenated with a hash function identifier corresponding to the hash function used to produce the selected one of the digests.
20. A method in accordance with claim 19, wherein the ingress node follows an algorithm corresponding to the pseudo code given by:
Marking procedure at router R, edge interface A: for z = 0 to f − 1 Digest:= Hz(A) for y = 0 to k − 1 Marks[z × k + y].Hash_num := z Marks[z × k + y].Digest := Digest Marks[z × k + y].Seg_Num := y Marks[z × k + y].A_bits := A[y] for each incoming packet w let x be a random integer from [0, f × k) write Marks[x] into w.Mark Mark Recording procedure at victim V: for each attack packet w Part := w.Mark.Hash_num Area := w.Mark.Digest Seg := w.Mark.Seg_Num Bit := w.Mark.A_bits RecTbl[Part, Area, Seg, Bit] := ‘1’ Address Recovery procedure at victim V: for Area = 0 to 2d − 1 for Bit0 = 0 to 2a − 1 if RecTbl[0, Area, 0, Bit0] == ‘1’ then if RecTbl[0, Area, k − 2, Bitk−2] == ‘1’ then for Bitk−i = 0 to 2a − 1 if RecTbl[0, Area, k − 1, Bitk−1] == ‘1’ then Prm := Bit0 . Bit1 . ... . Bitk−1 Digest := H0(Prm) if Area == Digest then for Part = 0 to f − 1 for Seg = 0 to k − 1 if RecTbl[Part, HPart(Prm), → Seg, BitSeg] ≠ ‘1’ then False_flag := ‘1’ if False_flag ≠ ‘1’ then Prm
IngressTbl.
21. A method in accordance with claim 11, wherein the one or more consecutive bits correspond to an a-bit address field, the digest corresponds to a d-bit digest field, and the identifier corresponds to an s-bit segment number field, and wherein the one or more consecutive bits are chosen from among a number, k, of different sets of one or more consecutive bits of the network address of the ingress node, the method further comprising:
reconstructing said entire ingress address at the victim destination, said reconstructing including:
mark recording, said mark recording including:
setting the appropriate bits in a reconstruction table to indicate which marks have arrived at the destination, said marks corresponding to the information used to mark respective packets, said reconstruction table comprising a structure where every possible mark can be uniquely represented, the reconstruction table having 2d areas of k segments each, and each segment consisting of 2a bits;
setting an appropriate bit in the reconstruction table when a mark becomes available to the mark recording process; and
extracting the digest from the mark and determining the area where the bit will be set,
wherein the segment number field in the mark indicates the segment in the reconstruction table area where the appropriate bit would be set, and wherein the value of the bits in the address value of the mark indicate the actual bit, which will be set to ‘1’;
repeating the mark recording for every mark received at the victim destination; and ingress address recovery, said ingress address recovery including:
recovering the address by checking the bits from the mark recording for every mark;
composing address segment permutations; and
determining which ones are valid ingress addresses.
This application claims priority from U.S. Provisional patent Application Ser. No. 60/552,645, filed Mar. 12, 2004; Ser. No. 60/552,647 filed Mar. 12, 2004, and 60/553,212 filed Mar. 15, 2004.
After several high-profile DDoS attacks on major U.S. web sites in 2000, numerous EP traceback approaches have been suggested to identify the attacker(s). See A. Belenky and N. Ansari, On IP traceback, IEEE Commun. Mag, vol 41, no, 7, pp. 142-153, July 2003. IP Traceback is defined in Chang (op. cit.) as identifying a source of any packet on the Internet. The previously proposed schemes can be categorized in four broad groups. One group of the solutions relies on the routers in the network to send their identities to the destinations of certain packets, either encoding this information directly in rarely used bits of the IP header, or by generating a new packet to the same destination. The biggest limitation of solutions of this type is that they are focused only on flood-based DoS and DDoS attacks, and cannot handle attacks comprised of a small number of packets. Moreover, for large scale DDoS attacks, these schemes are not very effective.
Now in accordance with the present invention a method for IP Traceback is disclosed which is based on Deterministic Packet Marking (DPM). The method is based on marking packets with the partial address information of ingress interface-only. The attack victim is able to recover the complete address(es) information after receiving several packets from a particular attacking host or hosts. The full path is not really essential for the traceback since it can be different for different packets for different reasons. The approach is scalable, simple to implement, and introduces no bandwidth and practically no processing overhead on the network equipment. It is capable of tracing thousands of simultaneous attackers during a DDoS attack. As disclosed in our concurrently filed applications Ser. No. 11/079,451 and Ser. No. 11/079,452, the entire disclosure of which are incorporated herein by reference. DPM is capable of tracing back to the slaves responsible for DDoS attacks that involve reflectors. Tracing back to the slaves cannot be done by other existing schemes. Most of the processing is done at the victim. The traceback process can be performed post-mortem allowing for tracing the attacks that may not have been noticed initially, or the attacks which would deny service to the victim so that traceback is impossible in real time. The involvement of the Internet Service Providers (ISPs) is very limited, and changes to the infrastructure and operation required to deploy DPM are minimal. DPM performs the traceback without revealing the internal topology of the provider's network, which is a desirable quality of a traceback scheme.
FIG. 6 illustrates address recovery for the multiple digest DDoS modification; and
FIG. 7 shows the pseudo code for the modified multiple digest DPM algorithm.
The limitation of the basic DPM in handling a certain type of DDoS attacks lies in the fact that the destination would associate segments of the ingress address with the source address of the attacker. If it could be guaranteed that only one host participating in the attack has a given source address, even though it might have been spoofed, and that the attacker would not change its address during the attack, the basic DPM would be sufficient. There are two situations when the reconstruction procedure of the basic DPM is inadequate. First, is the situation where two hosts with the same SA attack the victim. The ingress addresses corresponding to these two attackers are A0 and A1, respectively. The victim would receive four address segments: A0 [0], A0 [1], A1 [0], and A1 [1]. The victim, not being equipped to handle such attack, would eventually reconstruct four ingress addresses since four permutations are ultimately possible: A0 [0], A0 [1], A0 [0]. A1 [1], A1 [0], A0 [1], and A1 [0]. A1 [1], where ‘.’ denotes concatenation. Only two of the four would be valid.
The address recovery process is a part of a larger traceback procedure. It analyzes each area of the RecTbl. Once again, it runs independently from the mark recording process, thus allowing post-mortem traceback. The value of a certain bit in RecTbl indicates that the corresponding mark has arrived at the victim. For example, bit 12 in segment 3 of area 671 set to ‘1’ means that there is an ingress address of interest, with digest of 671 having segment 3 equal to ‘1100’ 2 as shown in FIG. 4. This segment has to be combined with other segments of this area in order to create permutations of segments. Hash function, H(x), is applied to each of these permutations. If the result matches the area number, which is actually the digest embedded in the marks (in this example 671), then the recovery process concludes that this permutation of segments is in fact a valid ingress address.
E [ H ] = 2 d - 2 d ( 1 - 1 2 d ) N . ( 1 )
Therefore, the rate of false positives is 0 for the values of N, for which the expected number of digests, E[H], equals to N, since every ingress address will have a unique digest.
2 a - 2 a ( 1 - 1 2 a ) N d , ( 2 )
for those areas, which have segments of more than one ingress addresses, and 1 for those which have segments of only a single ingress address. The expected number of all permutations of address segments for a given digest is
[ 2 a - 2 a ( 1 - 1 2 a ) N d ] k .
Recall that after a permutation of segments is obtained, the hash function H(x) is applied to it, and if the result does not match the original digest, that permutation is not considered. The expected number of permutations that result in a given digest for a given area of the RecTbl is
[ 2 a - 2 a ( 1 - 1 2 a ) N d ] k 2 d .
The number of false positives for a given area would be the total number of permutations, less the number of valid ingress addresses, which match the digest. For this modification, just a few areas, which have segments of more than one ingress addresses, will produce more than 0.01N of false positives. We assume that for all those areas Nd=2. The number of those areas is N−E[H], and the number of valid ingress addresses with segments in those areas is 2(N−E[H]). The number of false positives is given by
( N - E [ H ] ) [ 2 a - 2 a ( 1 - 1 2 a ) 2 ] k - 2 ( N - E [ H ] ) 2 d ( 3 )
This number has to be less than 1% of N. Therefore, Eq. (3) has to be set to be less or equal to 0.01N, and solved for N. Recall that a, d, and E[H] can be expressed in terms of k. The maximum N, NMAX, which would satisfy this inequality, is difficult to be expressed in terms of k. However, it is possible to find NMAX by substitution. Table tab:single provides the values of NMAX for selected k. Another important consideration is the expected number of datagrams required for reconstruction. This number is related to k, the number of segments that the ingress address was split. The larger the k, the more different packets it would be required for the victim to receive in order to reconstruct the ingress address. The expected number of datagrams, E[D], required to be marked by a single DPM-enabled interface in order for the victim to be able to reconstruct its ingress address is given by the Coupon Collector problem [Feller op. cit.]:
E [ D ] = k ( 1 k + 1 k - 1 + … + 1 ) .
Table I provides the value of E[D] for selected values of k.
k A s d NMAX E[D]
2 16 1 0 1 3
4 8 2 7 26 9
8 4 3 10 108 22
16 2 4 11 45 55
32 1 5 11 45 130
Multiple Digest DDoS Modification to DPM
In this scheme, the family of ƒ hash functions, H0(x) through Hƒ-1(x), is used to produce ƒ digests of the ingress address. As in the single digest scheme, the address segment and the segment number are transferred in each mark. Instead of the single digest, however, one of the several digests produced by each of ƒ hash functions concatenated with the function identifier is embedded in the mark. The d-bit field, which was used solely for the digest in the single-digest scheme, is split into two fields: log2(ƒ)-bit long field carrying the identifier of the hash function, and d-bit field with the digest itself.
FIG. 5 illustrates the process of the mark encoding. The process is very similar to the one described in the single digest modification, but differs in that for every ingress address, not k, but ƒ×k marks have to be created at startup and then randomly selected for every packet. This does not affect the DPM-enabled interface per-packet overhead since per-packet will be limited to generating a small random number and overwriting 17 bits in the header, just as for the single-digest or basic DPM schemes.
The address recovery process, shown in FIG. 6, identifies the permutations which match the digest in areas of Part0 of RecTbl. Once a permutation is validated by comparing its digest obtained by applying ‘H0(x) to the area number, the rest of the hash functions, H1(x) to Hƒ-1(x), are applied to it to produce ƒ−1 digests. These digests are used to verify the existence of this permutation in other parts of RecTbl. The process then checks these areas of the remaining parts for the permutation in question. If the permutation is present in the appropriate area of every part of the RecTbl, it is concluded that the permutation is a valid ingress address. Notice that the permutation does not have to be verified in every part. It is known that the digest obtained by applying Hi(x) to the permutation being checked will match the area number since the area was identified by this operation. Therefore, such verification would be redundant and will always produce a positive outcome. The pseudo code in FIG. 7 provides the details of the mark encoding, mark recording, and address recovery processes.
[ 2 a - 2 a ( 1 - 1 2 a ) N d ] k ,
where Nd is the number of ingress addresses with this digest. Since for the multiple digest scheme, unlike the single digest scheme, the number of ingress addresses with the same digest will be more than 2, the following analysis is more suitable. The number of ingress addresses with the same digest is
N E [ H ] .
The number of permutations in a single digest is then
[ 2 a - 2 a ( 1 - 1 2 a ) N E [ H ] ] k .
The number of false positives for this digest is
[ 2 a - 2 a ( 1 - 1 2 a ) N E [ H ] ] k - N 2 d .
The number of false positives in Part0 is given by:
E [ H ] 2 d ( [ 2 a - 2 a ( 1 - 1 2 a ) N E [ H ] ] k - N ) .
For large values of N, E[H]=2d, and thus
E [ H ] 2 d = 1.
So the number of false positives in Part0 is
[ 2 a - 2 a ( 1 - 1 2 a ) N E [ H ] ] k - N . ( 4 )
Once the permutation was identified as a possible ingress address in Part0, the remaining digests are calculated. Since we assume uniform distribution of addresses, any permutation is as likely to appear as any other. The probability of any random permutation to appear is
1 2 32 .
The probability that a given permutation, which is a false positive, will occur in the appropriate area of Part1 is:
[ 2 a - 2 a ( 1 - 1 2 a ) N E [ H ] ] k 2 32
This expression is not divided by 2d because if the permutation in question is present in the identified areas of all other parts, it must match the appropriate digest per discussion at the end of Section sec:MultMultipleReconstruciton. The probability that a given permutation will occur in the appropriate areas of all parts of RecTbl is:
[ [ 2 a - 2 a ( 1 - 1 2 a ) N E [ H ] ] k 2 32 ] f - 1
Multiplying this expression by the number of false positives in Part0 results in the number of false positives, after areas matching the digests 1 through ƒ-1 in all the other parts of the RecTbl were checked. This is the total number of false positives for the RecTbl. Setting it not to exceed
results in the following inequality:
{ [ 2 a - 2 a ( 1 - 1 2 a ) N E [ H ] ] k } f 2 32 ( f - 1 ) ≤ N 100
Recall that a, d, and E[H] can be expressed in terms of k. So, the whole inequality can be expressed in terms of k and f. Similar to the single-digest scheme, NMAX can be found by substitution.
E [ D ] = f × k ( 1 f × k + 1 f × k - 1 + … + 1 ) .
Table II provides the values of NMAX and E[D] for selected combinations of f, a, k, and d.
F k a d NMAX E[D]
4 8 4 8 2911 130
4 4 8 5 2296 55
8 4 8 4 2479 130
1 A. Belenky and N. Ansari, IP traceback with deterministic packet marking, IEEE Commun. Lett., Apr. 2003, 162-164 vol. 7 No. 4.
2 A. Belenky and N. Ansari, On IP traceback, IEEE Commun. Mag., Jul. 2002 vol. 41, No. 7.
3 A. Belenky and N. Ansari, Tracing multiple attackers with deterministic packet marking (DPM), Proc. of IEEE PacRim, Aug. 2003, to be published.
4 A.C. Snoren et al., Single-packet IP traceback, IEEE/ACM Trans. Networking. Dec. 2002, pp. 721-734, vol. 10, No. 6.
5 Andrey Belenky, "IP Traceback with Deterministic Packet Marking (DPM)," Ph.D. dissertation, New Jersey Institute of Technology, Oct. 2003.
6 D. Dean et al., An algebraic approach to IP traceback, ACM Trans. on Information and System Security, (TISSEC), May 2002, pp. 1190137, vol. 5, No. 2.
7 D. Moore et al., Inferring internet denial of service activity, Proc. of 10th USENIX Service Symposium, 2001, pp. 9-22.
8 D. Wei and N. Ansari, "Implementing IP Traceback in the Internet-An ISP Perspective," Proc. 3rd Annual IEEE Workshop on Information Assurance, West Point, NY, pp. 326-332, Jun. 17-19, 2002.
9 D. Wei and N. Ansari, "Implementing IP Traceback in the Internet—An ISP Perspective," Proc. 3rd Annual IEEE Workshop on Information Assurance, West Point, NY, pp. 326-332, Jun. 17-19, 2002.
10 D.X. Song and A. Perrig, Advanced and authenticated marking schemes for IP traceback, Proc. of INFOCOM 2001, 2001, pp. 878-886, vol. 2.
11 H. Burch and B. Cheswick, Tracing anonymous packets to their approximate source, Proc. of 2000 USENIX LISA Conference, Dec. 2000, pp. 319-327.
12 H. Chang et al., DecldUouS: Decentralized source identification for network intrusions, Proc. of 6th IFEP/IEEE International Symposium on Integrated Net. Management, May 1999, pp. 701-714.
13 H. Cheng et al., Design and implementation of a real-time decentralized source identification system for untrusted ip packets, Proc. of the DARPA Information Survivability Conference & Exposition, Jan. 2000, pp. 100-111, vol. 2.
14 L. Subramanian et al., Characterizating the Internet hierarchy from multiple vantage points, Proceedings of INFOCOM 2002 Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, Jun. 2002, pp. 618-627, vol. 2.
15 M. Bellovin, ICMP traceback message, IETF Draft, Mar. 2000, [Online]. Available: http//www.research.att.com/smb/papers/draft-bellovin-itrace-00.txt.
16 P. Ferguson and D.Senie, Network ingress filtering: defeating denial of service attacks which employ IP source address spoofing, RFC 2827, May 2000.
17 P. Srisuresh and K. Egevang, Traditional IP network address translator (traditional NAT), RFC 3022, Jan. 2001.
18 R. Stone, Center Track: An IP overlay network for tracking DoS floods, Proc. of 9th USENIX Security Symposium, Aug. 2000.
19 R.K.C. Chang, Defending against flooding-based distributed denial-of-service attacks: A tutorial, IEEE Commun. Mag. Oct. 2002, pp. 42-51, vol. 40, No. 10.
20 S. Matsuda et al., Design and implementation of unauthorized access tracing system, Proc. of the 2002 Symposium on Applications and the Internet, Jan./Feb. 2002, pp. 74-81.
21 S. Savage et al., Network support for IP Traceback, IEEE/ACM Trans. Networking, Jun. 2001, pp. 226-237, vol. 9, No. 3.
22 S.C. Lee and C. Sheilds, Technical, Legal, and Societal challenges to automated attack Traceback, IT Profesional, May/Jun. 2002, 12-18, Vo. 4, No. 3.
23 S.F. Wu et al., On design and evaluation of ‘intention-driven’ ICMP traceback, Proc. of 10th Inter. Conf. on Computer Comm. and Networks, Oct. 2001, pp. 159-165.
24 S.F. Wu et al., On design and evaluation of 'intention-driven' ICMP traceback, Proc. of 10th Inter. Conf. on Computer Comm. and Networks, Oct. 2001, pp. 159-165.
25 T. Baba and S. Matsuda, Tracing network attacks to their sources, IEEE Internet Comput., Mar./Apr. 2002, pp. 20-26, vol. 6, No. 2.
26 T.W. Doeppner, Using router stamping to identify the source of IP packets, Proc. of 7th ACM Inter. Conf. on Computer Comm. and Networks, Nov. 2000, pp. 184-189.
27 Y. Kim, J.-Y. Jo, and F. Merat, "Defeating Distributed Denial-of-Service Attack with Deterministic Bit Marking," IEEE GLOBECOM, pp. 1363-1367, Dec. 2003.
International Classification H04L9/00, H04L29/14
Cooperative Classification H04L63/1441, H04L63/126
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BELENKY, ANDREY;ANSARI, NIRWAN;REEL/FRAME:016613/0555;SIGNING DATES FROM 20050425 TO 20050510
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BELENKY, ANDREY;ANSARI, NIRWAN;SIGNING DATES FROM 20050425 TO 20050510;REEL/FRAME:016613/0555