Distributed architecture for statistical overload control against distributed denial of service attacks

• US 7,526,807 B2
• Filed: 11/26/2003
• Issued: 04/28/2009
• Est. Priority Date: 11/26/2003
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Chuah, Mooi Choo, Kim, Yoohwan, Lau, Wing Cheong, Chao, Hung-Hsiang Jonathan
• Primary Examiner(s): Barron, Jr., Gilberto
• Assistant Examiner(s): ZECHER, CORDELIA P K
• Application Number:
  US10/723,450
• Publication Number:
  US 20050111367A1
• Time in Patent Office: 1,980 Days
• Field of Search: 726/22, 726/23
• US Class Current: 726/23
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

In a network including a centralized controller and a plurality of routers forming a security perimeter, a method for selectively discarding packets during a distributed denial-of-service (DDoS) attack over the network. The method includes aggregating victim destination prefix lists and attack statistics associated with incoming packets received from the plurality of routers to confirm a DDoS attack victim, and aggregating packet attribute distribution frequencies for incoming victim related packets received from the plurality of security perimeter routers. Common scorebooks are generated from the aggregated packet attribute distribution frequencies and nominal traffic profiles, and local cumulative distribution function (CDF) of the local scores derived from the plurality of security perimeter routers are aggregated. A common discarding threshold is derived from the CDF and sent to each of the plurality of security perimeter routers, where the discarding threshold defines a condition in which an incoming packet may be discarded at the security perimeter.

Claims

1. A method for determining packets to be discarded in response to a distributed denial-of-service (DDoS) attack, said method comprising:

confirming a DDoS attack at a network location using a plurality of packet attribute values aggregated from a plurality of routers forming a security perimeter of a network;

computing an aggregate conditional probability measure for each packet entering said location based on selected attributes included within said packet from each of said plurality of security perimeter routers;

computing an aggregate cumulative distribution function (CDF) of scores based on said computed aggregate conditional probability measures;

determining a discarding threshold using said cumulative probability function; and

sending said discarding threshold to each of said plurality of security perimeter routers.

2. The method of claim 1, wherein said step of computing an aggregate conditional probability measure further comprises:

updating an individual marginal probability mass function and a joint probability mass function for attributes carried by each said packet.

3. The method of claim 1, further comprising:

granting immunity to packets of a specified sub-type entering said location.

4. The method of claim 1, wherein said aggregate conditional probability measure is computed in accordance with the following equation:

$\mathrm{CP}<br><br>\left(p\right)=\frac{{\mathrm{\rho <br><br>}}_n}{{\mathrm{\rho <br><br>}}_m}·<br><br>\frac{{\mathrm{JP}}_n}{{\mathrm{JP}}_m}<br><br>\frac{(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}<br><br>)}{(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}<br><br>)}$

where;

ρ

_m is currently measured utilization of a system;

ρ

_n is nominal utilization of the system;

A, B, C, . . . is a set of packet attributes;

JP_n (A, B, C, . . .) is a joint probability mass function of the set of attributes under normal traffic conditions;

JP_m (A, B, C, . . .) is the joint probability mass function of the set of attributes measured under current traffic conditions; and

a, b, c, . . . are the particular values that the attributes A, B, C, . . . take.

5. The method of claim 1, wherein said aggregate conditional probability measure is computed in accordance with the following equation:

$\mathrm{CP}<br><br>\left(p\right)=\frac{{\mathrm{\rho <br><br>}}_n}{{\mathrm{\rho <br><br>}}_m}·<br><br>\frac{P_n<br><br>\left(A=a_p\right)}{P_m<br><br>\left(A=a_p\right)}·<br><br>\frac{P_n<br><br>\left(B=b_p\right)}{P_m<br><br>\left(B=b_p\right)}·<br><br>\frac{P_n<br><br>\left(C=c_p\right)}{P_m<br><br>\left(C=c_p\right)}<br><br>$

where;

ρ

_m is currently measured utilization of a system;

ρ

_n is nominal utilization of the system;

A, B, and C is a set of packet attributes;

P_n (A, B, C) is a marginal probability mass function of the set of attributes under normal traffic conditions;

P_m (A, B, C) is the marginal probability mass function of the set of attributes measured under current traffic conditions; and

a, b, and c, are the particular values that the attributes A, B, and C take.

6. The method of claim 1, wherein said discarding threshold is calculated using a load shedding algorithm, combined with an inverse lookup on the aggregate CDF of scores.

7. The method of claim 2, wherein said joint and marginal probability functions are maintained using iceberg-style histograms.

8. A method for selectively discarding packets during a distributed denial-of-service (DDoS) attack over a network, comprising:

aggregating, in said network comprising a centralized controller and a plurality of routers forming a security perimeter, victim destination prefix lists and attack statistics associated with incoming packets received from said plurality of security perimeter routers to confirm a DDoS attack victim;

aggregating packet attribute distribution frequencies for incoming victim related packets received from said plurality of security perimeter routers;

generating common scorebooks from said aggregated packet attribute distribution frequencies and nominal traffic profiles;

aggregating local cumulative distribution function (CDF) of local scores derived from said plurality of security perimeter routers; and

providing, to each of said plurality of security perimeter routers, a common discarding threshold, said discarding threshold defining a condition in which an incoming packet may be discarded at said security perimeter.

9. The method of claim 8, wherein said aggregating victim destination prefix lists and attack statistics associated with incoming packets comprises:

comparing measured attribute values to nominal traffic attribute values for packet traffic sent to a particular destination; and

identifying increases in said measured attribute values over said nominal traffic attribute values.

10. The method of claim 9, wherein said confirming said DDoS attack victim comprises determining if said identified increases for said measured attribute values exceed respective predetermined thresholds.

11. The method of claim 8, wherein said victim destination prefix list and attack statistics comprise at least one of packets per second (pps), bits per second (bps), flow counts, and flow rates of incoming packets.

12. The method of claim 8, wherein said aggregating packet attribute distribution frequencies for incoming victim related packets comprises:

receiving packet attribute distribution frequencies from said plurality of security perimeter routers, said packet attribute distribution frequencies including incoming packet attribute information comprising at least one of;

IP protocol-type values, packet size, source/destination port numbers, source/destination IP prefixes, Time-to-Live (TTL) values, IP/TCP header length, TCP flag combinations, use IP fragmentation, and incorrect packet protocol checksums.

13. The method of claim 8, wherein said aggregating packet attribute distribution frequencies for incoming victim related packets comprises:

receiving packet attribute distribution frequencies from said plurality of security perimeter routers routers, said packet attribute distribution frequencies including incoming packet attribute information comprising joint distribution of the fraction of packets having various combinations of Time-to-Live (TTL) values and source IP prefix, packet-size and protocol-type, and destination port number and protocol-type.

14. The method of claim 13, wherein said receiving packet attribute distribution frequencies comprises receiving iceberg-style histograms comprising said incoming packet attribute information.

15. The method of claim 8, wherein said generating common scorebooks comprises:

computing partial scores of different attributes; and

computing a weighted sum of said partial scores to yield a logarithmic function of conditional legitimate probability for each incoming packet.

16. The method of claim 8, wherein said common discarding threshold comprises:

performing a load-shedding algorithm to determine a fraction (%_PD) of arriving suspicious packets required to be discarded; and

performing an inverse lookup on the aggregate CDF of scores.

17. The method of claim 16, where at each of said plurality of security perimeter routers, said method further comprises:

determining whether a score of an incoming packet is less than or equal to said discarding threshold;

discarding said incoming packet in an instance said score is less than or equal to said discarding threshold; and

forwarding said incoming packet for routing to destination in an instance said score is greater than to said discarding threshold.

18. A method for selectively discarding packets at a security perimeter of a network during a distributed denial-of-service (DDoS) attack over said network, comprising:

sending, from each of a plurality of routers forming said security perimeter, victim destination prefix list and attack statistics associated with incoming packets to a centralized controller adapted to confirm a victim of said DDoS attack;

sending, from each of said plurality of security perimeter routers, packet attribute distribution frequencies for incoming victim related packets;

receiving, at each of said plurality of security perimeter routers from said centralized controller, common scorebooks formed using aggregated packet attribute distribution frequencies and nominal traffic profiles;

sending, from each of said plurality of security perimeter routers, a local cumulative distribution function (CDF) of scores to said centralized controller; and

discarding, at each of said plurality of security perimeter routers, incoming packets based on a commonly distributed discarding threshold defined by said centralized controller.

19. The method of claim 18, further including the step of classifying said incoming packets as being one of suspicious and non-suspicious packets based on a destination address of said incoming packet.

20. The method of claim 19, wherein said local victim destination prefix list and attack statistics comprise at least one of packets per second (pps), bits per second (bps), flow counts, and flow rates of incoming packets.

21. The method of claim 19, wherein said sending packet attribute distribution frequencies comprises monitoring packet attribute distribution frequencies including incoming packet attribute information comprising at least one of IP protocol-type values, packet size, source/destination port numbers, source/destination LP prefixes, Time-to-Live (TTL) values, IP/TCP header length, TCP flag combinations, use IP fragmentation, and incorrect packet protocol checksums.

22. The method of claim 21, wherein said packet attribute distribution frequencies are sent in a form of iceberg-style histograms.

23. The method of claim 20, wherein said sending a local cumulative distribution function (CDF) of scores comprises:

determining a predetermined number of incoming packets to monitor;

for each incoming packet of said predetermined number of incoming packets;

determining attribute scores from said received scorebooks; and

locally aggregating said scores; and

forming said CDF from said aggregated scores associated with said predetermined number of incoming packets.

24. The method of claim 19 wherein said commonly distributed discarding threshold comprises:

a fraction (%_PD) of arriving suspicious packets associated with an aggregated CDF from all of said routers.

25. The method of claim 23, wherein said discarding said incoming packets comprises:

determining whether a score of an incoming packet is less than or equal to said discarding threshold;

discarding said incoming packet in an instance said score is less than or equal to said discarding threshold; and

forwarding said incoming packet for routing to destination in an instance said score is greater than to said discarding threshold.

26. A centralized controller for determining packets to be dropped in regard to a potential distributed denial-of-service (DDoS) attack at a location within a packet network, said centralized controller comprising:

means for aggregating a plurality of packet attribute values respectively received from a plurality routers forming a security perimeter of a network to confirm said attack at said location, wherein said centralized controller is associated with said network;

means for computing an aggregate conditional probability measure for each packet entering said location based on selected attributes included within said packet from each location;

means for computing an aggregate cumulative distribution function (CDF) based on said computed aggregate conditional probability measures;

means for determining a drop threshold based on access to said cumulative probability function; and

means for sending said drop threshold to each of said plurality of security perimeter routers, wherein each of said plurality of security perimeter routers is adapted to pass through packets, that exceed said determined drop threshold, to said location.

27. A centralized controller for determining packets to be dropped in regard to a potential distributed denial-of-service (DDoS) attack at a location within a packet network, said centralized controller comprising:

means for aggregating, local victim destination prefix lists and attack statistics associated with incoming packets received from a plurality of routers of a network forming a security perimeter in said network, to confirm a victim of said DDoS attack, wherein said centralized controller is associated with said network;

means for aggregating packet attribute distribution frequencies for incoming victim related packets received from said plurality of security perimeter routers;

means for generating common scorebooks from said aggregated packet attribute distribution frequencies and nominal traffic profiles;

means for aggregating local cumulative distribution function (CDF) of the local scores derived from said plurality of security perimeter routers; and

means for providing, to each of said plurality of security perimeter routers, a common discarding threshold, said discarding threshold defining a condition in which an incoming packet may be discarded at said security perimeter.

28. A network comprising:

a centralized controller for determining packets to be dropped in regard to a potential distributed denial-of-service (DDoS) attack at a location within a packet network; and

a plurality of security perimeter routers wherein each of said security perimeter routers comprises;

means for sending victim destination prefix lists and attack statistics associated with incoming packets to said centralized controller adapted to confirm a victim of said DDoS attack;

means for sending to said centralized controller packet attribute distribution frequencies for incoming victim related packets;

means for receiving, from said centralized controller, common scorebooks formed by aggregated packet attribute distribution frequencies and nominal traffic profiles;

means for sending a local cumulative distribution function (CDF) of scores to said centralized controller; and

means for discarding incoming packets based on a commonly distributed, to said plurality of security perimeter routers, discarding threshold defined by said centralized controller.