Granted Patent B2

US 7,743,415 · App. 10/066,232 · Granted Jun 22, 2010

Abstract

Claims (97)

1. A process that monitors network traffic through a monitoring device disposed between a data center and a network for thwarting denial of service attacks on the data center, the process comprises:

a detection process to determine if the values of a parameter of network traffic exceed normal values for the parameter to indicate an attack on the data center;

a characterization process to build a histogram for the parameter to compute significant outliers in a parameter and classify the attack; and

a filtering process for filtering of network packets based on the characterization process, wherein the filtering process comprises:

constructing a master correlation bit vector, wherein bits of the master correlation bit vector correspond to parameter correlations;

initializing bits of a packet's correlation bit vector as not suspicious;

retrieving a parameter from a parameter suspicious correlation bit vector, which comprises a list of suspicious values for the parameter, to construct the packet's correlation bit vector; and

using a value of the packet's correlation bit vector to index the master correlation bit vector.

2. The process of claim 1 wherein, in the characterization process, suspicious parameter values are represented by a bit vector with a 1 in every position corresponding to a “bad” value, and a 0 in every position corresponding to a “good” value.

3. The process of claim 1 wherein the characterization process comprises:

a correlation process that correlates suspicious parameters and determines existence of correlations of those parameters that indicate types of attacks.

4. The process of claim 3 wherein the correlation process is used to reduce dropping of legitimate traffic.

5. The process of claim 1 wherein filtering is aggregate filtering.

6. The process of claim 1 wherein parameters include at least one of source IP address, destination IP address, source TCP/UDP ports, destination TCP/UDP ports, IP protocol, IP TTL, IP length, hash of payload fragment, IP TOS field, and TCP flags.

7. A method for thwarting denial of service attacks on a data center, the method comprising:

producing a histogram of received network traffic for at least one parameter of network packets;

characterizing an attack based on comparison of a historical histogram with the produced histogram data for one or more parameters; and

filtering out traffic characterized as part of an attack, wherein filtering out the traffic comprises:

constructing a master correlation bit vector, wherein bits of the master correlation bit vector correspond to parameter correlations;

initializing bits of a packet's correlation bit vector as not suspicious;

retrieving a parameter from a parameter suspicious correlation bit vector, which comprises a list of suspicious values for the parameter, to construct the packet's correlation bit vector; and

using a value of the packet's correlation bit vector to index the master correlation bit vector.

8. The method of claim 7 further comprising:

filtering network packets sent to the data center based on whether a value of an attribute represented in the produced histogram is within a normal range of the values for the attribute, as determined by comparison to the historical histogram.

9. The method of claim 7 wherein the historical histogram is based on time periods of at least one hour.

10. The method of claim 7 wherein the produced histogram is produced during an attack and over time periods of approximately 10-300 seconds.

11. The method of claim 7 further comprising:

normalizing the produced and the historical histograms for each parameter; and

computing their difference to identify significant outliers that are considered indicators of suspicious traffic.

12. The method of claim 11 further comprising:

correlating suspicious parameters to reduce blocking of legitimate traffic.

13. The method of claim 12 wherein the packet's correlation bit vector contains sufficient bits to represent the parameter space.

14. The method of claim 11 further comprising:

correlating suspicious parameters to determine a correlation of those parameters that can indicate an attack.

15. The method of claim 8 wherein filtering the network packets further comprises:

producing the master correlation bit vector from a stream of sampled packets and examining the network packets using a process that is constant-time, independently of the number of correlations or of the number of suspicious values for a parameter.

16. The method of claim 15 wherein filtering the network packets further comprises:

testing bits in the master correlation bit vector to decide whether to drop or forward the packet.

17. The method of claim 8 wherein the attribute comprises at least one of source IP address, destination IP address, source TCP/UDP ports, destination TCP/UDP ports, IP protocol, IP TTL, IP length, hash of payload fragment, IP TOS field, and TCP flags.

18. The method of claim 7 wherein the method is executed on a data collector.

19. The method of claim 7 wherein the method is executed on a gateway.

20. A monitoring device for thwarting denial of service attacks on a data center, the monitoring device comprises:

a computing device executing:

a process to build at least one histogram for at least one parameter of network traffic;

a process to characterize an attack based on a comparison of a historical histogram of the at least one parameter to the built at least one histogram for the at least one parameter; and

a process to filter network packets based on characterization, wherein the process to filter the network packets comprises:

constructing a master correlation bit vector, wherein bits of the master correlation bit vector correspond to parameter correlations;

initializing bits of a packet's correlation bit vector as not suspicious;

retrieving a parameter from a parameter suspicious correlation bit vector, which comprises a list of suspicious values for the parameter, to construct the packet's correlation bit vector; and

using a value of the packet's correlation bit vector to index the master correlation bit vector.

21. The monitoring device of claim 20 further comprising:

a process to correlate suspicious parameters to reduce blocking of legitimate traffic.

22. The monitoring device of claim 20 wherein the characterization process normalizes the historical and built histograms for each parameter and computes their difference to identify significant outliers that are considered indicators of suspicious traffic.

23. The monitoring device of claim 22 wherein the characterization process produces the master correlation vector from a stream of sampled packets and examines the sampled packets using a process that is constant-time, independently of the number of correlations or of the number of suspicious values for a parameter.

24. The monitoring device of claim 20 wherein the device is a gateway device that is adaptable to dynamically install filters on nearby routers.

25. The monitoring device of claim 20 wherein the device is a data collector.

26. The monitoring device of claim 20 wherein the parameters include at least one of source IP address, destination IP address, source TCP/UDP ports, destination TCP/UDP ports, IP protocol, IP TTL, IP length, hash of payload fragment, IP TOS field, and TCP flags.

27. A computer program product residing on a computer readable medium comprising instructions for causing a processor to:

build a histogram for a parameter of network traffic;

use the histogram data for the parameter to characterize an attack; and

filter the network traffic based on characterization of the attack, wherein the instructions to filter the network traffic comprises instructions to:

construct a master correlation bit vector, wherein bits of the master correlation bit vector correspond to parameter correlations;

initialize bits of a packet's correlation bit vector as not suspicious;

retrieve a parameter from a parameter suspicious correlation bit vector, which comprises a list of suspicious values for the parameter, to construct the packet's correlation bit vector; and

use a value of the packet's correlation bit vector to index the master correlation bit vector.

28. The computer program product of claim 27 further comprising instructions to:

determine if a parameter value exceeds a normal value for the parameter to indicate an attack on the site.

29. The computer program product of claim 28 further comprising instructions to:

use the histogram to characterize the attack when it is determined that a parameter value exceeds a threshold.

30. A method of protecting a data center during a denial of service attack, the method comprises:

monitoring network traffic through a gateway disposed between the data center and a network:

determining if values of at least one parameter exceed normal, threshold values expected for the parameter to indicate an attack on the site;

producing a histogram for the at least one parameter of network traffic to characterize the attack by comparing the histogram to at least one historical histogram for that parameter; and

filtering out traffic based on characterizing the traffic, which the gateway deems to be part of an attack, wherein filtering out the traffic comprises:

constructing a master correlation bit vector, wherein bits of the master correlation bit vector correspond to parameter correlations;

initializing bits of a packet's correlation bit vector as not suspicious;

retrieving a parameter from a parameter suspicious correlation bit vector, which comprises a list of suspicious values for the parameters, to construct the packet's correlation bit vector; and

using a value of the packet's correlation bit vector to index the master correlation bit vector.

31. The method of claim 30 further comprising:

communicating statistics collected in the gateway to a control center.

32. The method of claim 31 wherein communicating occurs over a dedicated link to the control center via a hardened network.

33. The method of claim 31 wherein the gateway is physically deployed in line in the network.

34. The method of claim 31 wherein filtering occurs on nearby routers.

35. A method to reduce blocking of legitimate traffic in a process to protect a victim site during a denial of service attack, comprises:

producing a histogram of network traffic to characterize an attack; and

filtering out traffic deemed part of an attack with filtering comprising:

constructing a master correlation vector having asserted bits corresponding to the most important parameter correlations;

initializing a packet's correlation bit vector to 0, and for every parameter:

retrieving the parameter in a parameter suspicious vector to construct the packet' correlation bit vector; and

using the value of the packet's correlation bit vector to index into the master correlation bit vector.

36. The method of claim 35 further comprising:

testing the indexed bit in the master correlation vector, where if the bit in the master correlation bit vector is a one, the packet is dropped, otherwise the packet is forwarded.

37. The method of claim 35 wherein the master correlation vector is constructed from a stream of sampled packets.

38. The method of claim 35 further comprising:

maintaining a correlation bit vector with as many bits as there are parameters; and

if a parameter's suspicious vector has a 1 in a bit position corresponding to the parameter's value in a packet, the method further comprises:

setting the bit corresponding to the parameter in the packet's correlation vector to 1.

Assignments (18)