Streaming algorithms for robust, real-time detection of DDoS attacks
View Patent ↗A distinct-count estimate is obtained in a guaranteed small footprint using a two level hash, distinct count sketch. A first hash fills the first-level hash buckets with an exponentially decreasing number of data-elements. These are then uniformly hashed to an array of second-level-hash tables, and have an associated total-element counter and bit-location counters. These counters are used to identify singletons and so provide a distinct-sample and a distinct-count. An estimate of the total distinct-count is obtained by dividing by the distinct-count by the probability of mapping a data-element to that bucket. An estimate of the total distinct-source frequencies of destination address can be found in a similar fashion. By further associating the distinct-count sketch with a list of singletons, a total singleton count and a heap containing the destination addresses ordered by their distinct-source frequencies, a tracking distinct-count sketch may be formed that has considerably improved query time.
1. A method of maintaining a data-structure capable of providing an approximate distinct-count of data-elements, said method comprising the steps of:
obtaining a plurality of data-elements including a source value comprising a source IP address and a destination value comprising a destination IP address;
using a processor for
generating an indexed set of samples of said data-elements, each of said samples having a sample rate that is an exponentially decreasing function of the index of said sample;
hashing said data-elements contained in one of a set of first-level hash buckets to a set of second-level hash buckets wherein hashing is performed using an address pair formed by combining said source value and said destination value;
associating a set of count signatures with a first one of said samples, each of said count signatures comprising a total-element count and a bit-location count, wherein the associating comprises associating one of said count signatures with each of said second-level hash buckets;
determining a set of distinct-source, half-open connection frequencies for the destination addresses; and
determining whether any of the destinations has a frequency that increases in a manner that is indicative of a distributed denial of service attack including distinguishing between a distributed denial of service attack and a legitimate surge in traffic based on an increase in a volume of data and an associated change in half-open connections of the frequency increase.
2. The method of claim 1 , comprising obtaining a distinct-count of said first sample using said count signatures, said distinct-count comprising a number indicative of data-elements contained in said sample each of which has a distinct domain value.
3. The method of claim 2 , comprising identifying said second-level hash buckets containing only data-elements having a same domain value.
4. The method of claim 3 , comprising identifying said second-level hash buckets in which each bit of said bit-location count is either equal to zero or equal to said total-element count.
5. The method of claim 4 , wherein said data-elements further comprise an event insertion value and an event deletion value, and further comprising the step of updating a count signature by incrementing said total-element count and said bit-location count if said event has said event insertion value, and decrementing said total-element count and said bit-location count if said data-element has said event deletion value.
6. The method of claim 5 , comprising calculating a distinct-count estimate for said plurality of data-elements by dividing said distinct-count by said sample rate of said first sample.
7. The method of claim 1 , comprising calculating a distinct-source frequency for a first distinct destination by analyzing said count signatures, said distinct-source frequency being a total number of distinct data-elements having said destination value of said first distinct destination.
8. The method of claim 7 , comprising:
repeating said step of calculating a distinct-source frequency for a plurality of distinct-destinations; and
ordering said plurality of distinct-destinations by size of said distinct-source frequency.
9. The method of claim 1 , comprising the steps of:
storing a distinct-sample comprising said data-elements having a same domain value in said first of said first-level hash buckets;
analyzing said distinct sample to obtain a distinct-source frequency for a first distinct destination; and
updating a distinct-destination heap containing a plurality of distinct-destinations ordered by size of said distinct-source frequency.
10. The method of claim 9 , comprising obtaining a distinct-count of said first sample using said count signatures, said distinct-count comprising a number indicative of data-elements contained in said sample each of which has a distinct domain value; and
storing said distinct-count.
11. The method of claim 10 , comprising:
using said stored distinct-count to locate an appropriate first-level hash bucket having a sample of a predetermined size; and
providing said plurality of distinct-destinations ordered by size of said distinct-source frequency contained in said distinct-destination heap associated with said appropriate first-level hash bucket.
12. Computer readable instructions embodied on computer-readable storage medium, comprising;
first computer readable instructions for obtaining a plurality of data-elements including a source value comprising a source IP address and a destination value comprising a destination IP address;
second computer readable instructions for generating an indexed set of event samples of said data-elements, each of said samples having a sample rate that is an exponentially decreasing function of the index of said sample, wherein generating the indexed set of event samples comprises hashing said events to a first-level set of hash buckets so that each of said first-level hash buckets contains a number of events that decreases exponentially with hash index, wherein hashing is performed using an address pair formed by combining said source value and said destination value;
third computer readable instructions for hashing said data-elements contained in one of said first-level hash buckets to a set of second-level hash buckets;
fourth computer readable instructions for associating a set of count signatures with a first sample, each of said count signatures comprising a total event count and a bit-location count, wherein the associating comprises associating one of said count signatures with each of said second-level hash buckets;
fifth computer readable instructions for determining a set of distinct-source, half-open frequencies for the destination addresses; and
sixth computer readable instructions for determining whether any of the destinations has a frequency that increases in a manner that is indicative of a distributed denial of service attack including distinguishing between a distributed denial of service attack and a legitimate surge in traffic based on an increase in a volume of data and an associated change in half-open connections of the frequency increase.
13. A computing device comprising:
a computer-readable storage medium comprising instructions for:
obtaining a plurality of data-elements including a source value comprising a source IP address and a destination value comprising a destination IP address;
generating an indexed set of event samples of said data-elements, each of said samples having a sample rate that is an exponentially decreasing function of the index of said sample, wherein generating the indexed set of event samples comprises hashing said events to a first-level set of hash buckets so that each of said first-level hash buckets contains a number of events that decreases exponentially with hash index, wherein hashing is performed using an address pair formed by combining said source value and said destination value;
hashing said data-elements contained in one of said first-level hash buckets to a set of second-level, hash buckets;
associating a set of count signatures with a first sample, each of said count signatures comprising a total event count and a bit-location count, wherein the associating comprises associating one of said count signature with each of said second-level hash buckets;
fifth computer readable instructions for determining a set of distinct-source, half-open frequencies for the destination addresses; and
sixth computer readable instructions for determining whether any of the destinations has a frequency that increases in a manner that is indicative of a distributed denial of service attack including distinguishing between a distributed denial of service attack and a legitimate surge in traffic based on an increase in a volume of data and an associated change in half-open connections of the frequency increase.