Granted Patent B2

US 8,707,419 · App. 11/769,609 · Granted Apr 22, 2014

Abstract

Claims (109)

1. A method for protecting against high volume attacks using an apparatus comprising a processor communicably coupled to a memory, the method comprising the steps of:

receiving a packet at the apparatus;

determining a source of the received packet using the processor;

creating a pattern key that uniquely identifies the source of the received packet;

updating a tree-based data structure within the memory based on the pattern key using the processor, wherein the tree-based data structure comprises a set of root, intermediate and leaf nodes linked together based on the pattern key such that two or more statistics are maintained for each node and the two or more statistics comprise an actual aggregation count of how many sources of the received packets are represented by the corresponding node and a packet count of how many of the received packets have traversed the corresponding node;

accepting the received packet whenever none of the statistics stored within the tree-based data structure for each node between the root node and the node corresponding to the source of the received packet exceed a threshold using the processor, wherein the threshold comprises:

a maximum effective traffic rate per endpoint determined by (R*T)/Σλi where i=1 to n, R is an allowed traffic rate, T is a time period and λi is a trust index of ith endpoint;

a global threshold determined by (R−r)*δ+R where R is the allowed traffic rate r is a cumulative traffic rate and δ is a maximum delay that can be introduced for the communications packet; and

a node threshold determined by (R″*(node->trust_index)*node->act_agr_count−node->trafficJate)*δ+R″*(node->trust index)*node->act_agr_count+(MAX_KEY LENGTH*8−d)*node->act_agr_count where R″ is an effective rate per endpoint, and d is a bit position in a key after traversing the node;

or a combination thereof; and

dropping the received packet whenever one or more of the statistics stored within the tree-based data structure for any node between the root node and the node corresponding to the source of the received packet exceed the threshold using the processor.

2. The method as recited in claim 1 , wherein the updating step executed by the processor further comprises one or more of the steps of:

updating the one or more statistics;

determining the threshold;

determining a new traffic rate at the node and resetting one or more counters;

creating one or more new nodes within the tree-based data structure corresponding to the source of the received packet;

deleting one or more existing nodes within the tree-based data structure after a specified time period with no activity;

automatically adjusting the threshold based on a packet volume; or

reserving a bandwidth for one or more trusted sources.

3. The method as recited in claim 1 , wherein the processor performs the steps at a link speed or substantially at the link speed or near the link speed.

4. The method as recited in claim 1 , wherein the pattern key is derived from an Internet Protocol address of the source of the received packet.

5. The method as recited in claim 1 , wherein each node within the tree-based data structure comprises:

a common pattern length;

a length of the common pattern;

a common pattern;

a common pattern that this node represents;

a common pattern mask;

a drop flag;

a refresh flag;

the actual aggregation count;

an outstanding aggregation count;

the packet count;

a drop count;

a node traffic rate; and

a node trust index.

6. The method as recited in claim 1 , further comprising the step of obtaining all information about a node's descendants from an immediate child of the node within the tree-based data structure.

7. The method as recited in claim 1 , wherein a threshold for each node within the tree-based data structure is always greater that a sum of the threshold for all descendants of the node.

8. The method as recited in claim 1 , wherein the apparatus further comprises a bit matching engine communicably coupled to the processor that does not require a mask field at each node within the tree-based data structure.

9. The method as recited in claim 1 , wherein the one or more statistics comprise one or more global statistics, one or more node statistics, a traffic rate, a maximum delay, a maximum number of sources in a time period, a minimum number of allowed messages from a source within the time period, a maximum number or allowed messages from the source within the time period, an endpoint count, a cumulative packet count, a cumulative traffic rate, a trust index, a drop flag, or a combination thereof.

10. The method as recited in claim 1 , wherein a node within the tree-based data structure is defined by:

struct node_data {

UCHAR pattern_length;

UCHAR pattern[MAX_KEY_LENGTH];

UCHAR mask [MAX KEY LENGTH]; - - -

UCHAR drop —flag;

UINT drop_count;

UCHAR refresh_flag;

INT act_agr_count;

INT outs_agr_count;

UINT packet_count;

UINT trafficJate;

UINT trust_index;

struct node *child node[MAX NO CHILD]; - - -

} node_data;

wherein MAX_KEY_LENGTH is a length of a key in number of bytes; and

wherein MAX NO CHILD IS a maXImum number of children any node can have.

11. A computer program embodied on a non-transitory computer readable medium for protecting against high volume attacks comprising:

a code segment for receiving a packet;

a code segment for determining a source of the received packet;

a code segment for creating a pattern key that uniquely identifies the source of the received packet;

a code segment for updating a tree-based data structure based on the pattern key, wherein the tree-based data structure comprises a set of root, intermediate and leaf nodes linked together based on the pattern key such that two or more statistics are maintained for each node and the two or more statistics comprise an actual aggregation count of how many sources of the received packets are represented by the corresponding node and a packet count of how many of the received packets have traversed the corresponding node;

a code segment for accepting the received packet whenever none of the statistics stored within the tree-based data structure for each node between the root node and the node corresponding to the source of the received packet exceed a threshold, wherein the threshold comprises:

a maximum effective traffic rate per endpoint determined by (R*T)/Σλi where i=1 to n, R is an allowed traffic rate, T is a time period and λi is a trust index of ith endpoint;

a global threshold determined by (R−r)*δ+R where R is the allowed traffic rate, r is a cumulative traffic rate and δ is a maximum delay that can be introduced for the communications packet; and

a node threshold determined by (R″*(node->trust_index)*node->act_agr_count−node->trafficJate)*δ+R″*(node->trust_index)*node->act_agr_count+(MAX KEY LENGTH*8−d)*node->act agr count where R″ is an effective rate per endpoint, and d is a bit position in a key after traversing the node; or a combination thereof; and

a code segment for dropping the received packet whenever one or more of the statistics stored within the tree-based data structure for any node between the root node and the node corresponding to the source of the received packet exceed the threshold.

12. The computer program as recited in claim 11 , wherein the updating code segment further comprises:

a code segment for updating the one or more statistics;

a code segment for determining the threshold;

a code segment for determining a new traffic rate at the node and resetting one or more counters;

a code segment for creating one or more new nodes within the tree-based data structure corresponding to the source of the received packet;

a code segment for deleting one or more existing nodes within the tree-based data structure after a specified time period with no activity;

a code segment for automatically adjusting the threshold based on a packet volume; or

a code segment for reserving a bandwidth for one or more trusted sources.

13. The computer program as recited in claim 11 , wherein the code segments are performed at a link speed or substantially at the link speed or near the link speed.

14. The computer program as recited in claim 11 , wherein the pattern key is derived from an Internet Protocol address of the source of the received packet.

15. The computer program as recited in claim 11 , wherein the one or more statistics comprise one or more global statistics, one or more node statistics, a traffic rate, a maximum delay, a maximum number of sources in a time period, a minimum number of allowed messages from a source within the time period, a maximum number or allowed messages from the source within the time period, an endpoint count, a cumulative packet count, a cumulative traffic rate, a trust index, a drop flag, or a combination thereof.

16. An apparatus for protecting against high volume attacks comprising:

first and second communications interfaces; and

a processor communicably coupled to the first and second communications interfaces wherein the processor: (a) determines a source of a packet received at the first communications interface, (b) creates a pattern key that uniquely identifies the source of the received packet, (c) updates a tree-based data structure based on the pattern key, wherein the tree-based data structure comprises a set of root, intermediate and leaf nodes linked together based on the pattern key such that two or more statistics are maintained for each node and the two or more statistics comprise an actual aggregation count of how many sources of the received packets are represented by the corresponding node and a packet count of how many of the received packets have traversed the corresponding node, (d) passes the received packet to the second communications interface whenever none of the statistics stored within the tree-based data structure for each node between the root node and the node corresponding to the source of the received packet exceed a threshold, wherein the threshold comprises: a maximum effective traffic rate per endpoint determined by (R*T)/Σλi where i=1 to n, R is an allowed traffic rate, T is a time period and λi is a trust index of ith endpoint, a global threshold determined by (R−r)*δ+R where R is the allowed traffic rate, r is a cumulative traffic rate and δ is a maximum delay that can be introduced for the communications packet, and a node threshold determined by (R″*(node->trust_index)*node->act_agr_count−node->trafficJate)*δ+R″*(node->trust_index)*node->act_agr_count+(MAX KEY LENGTH*8−d)*node->act agr count where R″ is an effective rate per endpoint, and d is a bit position in a key after traversing the node; or a combination thereof, and (e) drops the received packet whenever one or more of the statistics stored within the tree-based data structure for any node between the root node and the node corresponding to the source of the received packet exceed the threshold.

17. The apparatus as recited in claim 16 , wherein the tree-based data structure updates further comprise:

pdating the one or more statistics;

determining the threshold;

determining a new traffic rate at the node and resetting one or more counters;

creating one or more new nodes within the tree-based data structure corresponding to the source of the received packet;

deleting one or more existing nodes within the tree-based data structure after a specified time period with no activity;

automatically adjusting the threshold based on a packet volume; or

reserving a bandwidth for one or more trusted sources.

18. The apparatus as recited in claim 16 , wherein the received packets are processed at a link speed or substantially at the link speed or near the link speed.

19. The apparatus as recited in claim 16 , wherein the pattern key is derived from an Internet Protocol address of the source of the received packet.

20. The apparatus as recited in claim 16 , wherein the one or more statistics comprise one or more global statistics, one or more node statistics, a traffic rate, a maximum delay, a maximum number of sources in a time period, a minimum number of allowed messages from a source within the time period, a maximum number or allowed messages from the source within the time period, an endpoint count, a cumulative packet count, a cumulative traffic rate, a trust index, a drop flag, or a combination thereof.

21. A system for protecting against high volume attacks comprising:

a first network;

a first communications interface communicably coupled to the first network;

a second network or destination device;

a second communication interface communicably coupled to the second network; and

a processor communicably coupled to the first and second communications interfaces wherein the processor: (a) determines a source of a packet received at the first communications interface, (b) creates a pattern key that uniquely identifies the source of the received packet, (c) updates a tree-based data structure based on the pattern key, wherein the tree-based data structure comprises a set of root, intermediate and leaf nodes linked together based on the pattern key such that two or more statistics are maintained for each node and the two or more statistics comprise an actual aggregation count of how many sources of the received packets are represented by the corresponding node and a packet count of how many of sources of the received packets have traversed the corresponding node, (d) passes the received packet to the second communications interface whenever none of the statistics stored within the tree-based data structure for each node between the root node and the node corresponding to the source of the received packet exceed a threshold , wherein the threshold comprises: a maximum effective traffic rate per endpoint determined by (R*T)/Σλi where i=1 to n, R is an allowed traffic rate, T is a time period and λi is a trust index of ith endpoint, a global threshold determined by (R−r)*δ+R where R is the allowed traffic rate, r is a cumulative traffic rate and δ is a maximum delay that can be introduced for the communications packet, and a node threshold determined by (R″*(node->trust_index)*node->act_agr 13 count−node->trafficJate)*δ+R″*(node->trust_index)*node->act_agr_count +(MAX_KEY_LENGTH*8−d)*node->act_agr_count where R″ is an effective rate per endpoint, and d is a bit position in a key after traversing the node; or a combination thereof, and (e) drops the received packet whenever one or more of the statistics stored within the tree-based data structure for any node between the root node and the node corresponding to the source of the received packet exceed the threshold.

22. The system as recited in claim 21 , wherein the tree-based data structure updates further comprise:

updating the one or more statistics;

determining the threshold;

determining a new traffic rate at the node and resetting one or more counters;

creating one or more new nodes within the tree-based data structure corresponding to the source of the received packet;

deleting one or more existing nodes within the tree-based data structure after a specified time period with no activity;

automatically adjusting the threshold based on a packet volume; or

reserving a bandwidth for one or more trusted sources.

23. The system as recited in claim 21 , wherein the received packets are processed at a link speed or substantially at the link speed or near the link speed.

24. The system as recited in claim 21 , wherein the pattern key is derived from an Internet Protocol address of the source of the received packet.

25. The system as recited in claim 21 , wherein the one or more statistics are maintained for an individual source and at an aggregated level.

26. The system as recited in claim 21 , wherein the one or more statistics comprise one or more global statistics, one or more node statistics, a traffic rate, a maximum delay, a maximum number of sources in a time period, a minimum number of allowed messages from a source within the time period, a maximum number or allowed messages from the source within the time period, an endpoint count, a cumulative packet count, a cumulative traffic rate, a trust index, a drop flag, or a combination thereof.

Assignments (14)