Two-stage hash based logic for application layer distributed denial of service (DDoS) attack attribution

• US 9,973,528 B2
• Filed: 12/21/2015
• Issued: 05/15/2018
• Est. Priority Date: 12/21/2015
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: Fortinet Inc.
• Inventors: Jain, Hemant Kumar
• Primary Examiner(s): Armouche, Hadi S
• Assistant Examiner(s): TAYLOR, SAKINAH W
• Application Number:
  US14/976,938
• Publication Number:
  US 20170180415A1
• Time in Patent Office: 876 Days
• Field of Search: 726 23
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

Methods and systems for a two-stage attribution of application layer DDoS attack are provided. In a first table just a hash index is maintained whereas the second stage table keeps the string parameter corresponding to the application layer attribute under attack. A linked list maintains a plurality of rows if there is hash collision in the first table. The second table is aged out and reported periodically with details of large strings.

Claims

1. A method comprising:

receiving, by a distributed denial of service (DDoS) detection module of a DDoS mitigation appliance within a network, information regarding a plurality of application layer attributes for which an attack status is to be monitored, wherein the plurality of application layer attributes comprise strings of characters and wherein the strings are variable-length and some of the strings have a potential for exceeding one hundred characters;

determining the attack status for each of the plurality of monitored attributes by comparing, by the DDoS detection module, granular traffic rates directed to a first hash value of each of the plurality of monitored attributes to a plurality of corresponding adaptive thresholds, wherein the first hash value is calculated based on a first hash algorithm;

when a granular traffic rate for the first hash value of a particular monitored attribute of the plurality of monitored attributes exceeds an adaptive threshold for the particular monitored attribute, the particular monitored attribute is determined to be an under-attack attribute;

storing, by the DDoS monitor module, details regarding the under-attack attribute in a memory of the DDoS detection module;

storing, by the DDoS monitor module, the first hash value of each of the plurality of monitored attributes in a first stage table in the memory;

storing, by the DDoS monitor module, the details of the under-attack attribute in a second stage table in the memory after the under-attack attribute is determined;

calculating, by the DDoS monitor module, a second hash value of the under-attack attribute based on a second hash algorithm;

calculating, by the DDoS monitor module, a drop count for the second hash value of the under-attack attribute;

when the drop count for the second hash value of the under-attack attribute does not exceed an adaptive threshold for the under-attack attribute, the under-attack attribute is determined to be a victim attribute;

notifying, by the DDoS detection module, a host computer coupled to the DDoS detection module of the attack status and the details of the under-attack attribute; and

responsive to identifying the under-attack attribute, causing, by the DDoS detection module, subsequently received packets having the under-attack attribute to be dropped for a pre-determined blocking period.

2. The method of claim 1, further comprising:

scanning, by an ager logic of the DDoS monitor module, the second stage table; and

removing, by the ager logic, an entry from the second stage table if the entry is not in use within a pre-determined time period.

3. The method of claim 2, further comprising reporting, by the ager logic, the entries of the second stage table with the details of under-attack attributes at an end of the pre-determined blocking period.

4. The method of claim 3, wherein the pre-determined blocking period is from 0 to 15 seconds.

5. The method of claim 1, further comprising:

when a collision between the first hash value occurs between multiple of the plurality of monitored attributes, generating, by the DDoS monitor module, multiple second hash values for the multiple monitored attributes;

storing, by the DDoS monitor module, the multiple second hash values of the multiple monitored attributes within multiple entries of the second stage table; and

linking, by the DDoS monitor module, the multiple entries of the second hash values with the collided first hash value in the second stage table.

6. The method of claim 1, wherein the details of the under-attack attribute comprise a full-length string representing the under-attack attribute.

7. The method of claim 1, wherein the first hash value of each of the plurality of monitored attributes is less than 20 bits.

8. The method of claim 1, wherein the first hash algorithm is selected from any one of MD5, Secure Hash Algorithm (SHA), cyclic redundancy check (CRC).

9. The method of claim 1, wherein the application layer attributes are associated with Hypertext Transfer Protocol (HTTP) and wherein the application layer attributes include one or more of a user-agent, a host, a referrer, a cookie and a Uniform Resource Locator (URL).

10. A computer system comprising:

non-transitory storage device having tangibly embodied therein instructions representing a security application; and

one or more processors coupled to the non-transitory storage device and operable to execute the security application to perform a method comprising;

receiving, by a distributed denial of service (DDoS) detection module within a network, information regarding a plurality of application layer attributes for which an attack status is to be monitored, wherein the plurality of application layer attributes comprise strings of characters and wherein the strings are variable-length and some of the strings have a potential for exceeding one hundred characters;

determining the attack status for each of the plurality of monitored attributes by comparing, by the DDoS detection module, granular traffic rates directed to a first hash value of each of the plurality of monitored attributes to a plurality of corresponding adaptive thresholds, wherein the first hash value is calculated based on a first hash algorithm;

when a granular traffic rate for the first hash value of a particular monitored attribute of the plurality of monitored attributes exceeds an adaptive threshold for the particular monitored attribute, the particular monitored attribute is determined to be an under-attack attribute;

storing, by the DDoS monitor module, details regarding the under-attack attribute in a memory of the DDoS detection module;

storing, by the DDoS monitor module, the first hash value of each of the plurality of monitored attributes in a first stage table in the memory;

storing, by the DDoS monitor module, the details of the under-attack attribute in a second stage table in the memory after the under-attack attribute is determined;

calculating, by the DDoS monitor module, a second hash value of the under-attack attribute based on a second hash algorithm;

calculating, by the DDoS monitor module, a drop count for the second hash value of the under-attack attribute;

when the drop count for the second hash value of the under-attack attribute does not exceed an adaptive threshold for the under-attack attribute, the under-attack attribute is determined to be a victim attribute;

notifying, by the DDoS detection module, a host computer coupled to the DDoS detection module of the attack status and the details of the under-attack attribute; and

responsive to identifying the under-attack attribute, causing, by the DDoS detection module, subsequently received packets having the under-attack attribute to be dropped for a pre-determined blocking period.

11. The computer system of claim 10, wherein the method further comprises:

scanning, by an ager logic of the DDoS monitor module, the second stage table; and

removing, by the ager logic, an entry from the second stage table if the entry is not in use within a pre-determined time period.

12. The computer system of claim 11, wherein the method further comprises reporting, by the ager logic, the entries of the second stage table with the details of under-attack attributes at an end of the pre-determined blocking period.

13. The computer system of claim 12, wherein the pre-determined blocking period is from 0 to 15 seconds.

14. The computer system of claim 10, wherein the method further comprises:

when a collision between the first hash value occurs between multiple of the plurality of monitored attributes, generating, by the DDoS monitor module, multiple second hash values for the multiple monitored attributes;

storing, by the DDoS monitor module, the multiple second hash values of the multiple monitored attributes within multiple entries of the second stage table; and

linking, by the DDoS monitor module, the multiple entries of the second hash values with the collided first hash value in the second stage table.

15. The computer system of claim 10, wherein the details of the under-attack attribute comprise a full-length string representing the under-attack attribute.

16. The computer system of claim 10, wherein the first hash value of each of the plurality of monitored attributes is less than 20 bits.

17. The computer system of claim 10, wherein the first hash algorithm is selected from any one of MD5, Secure Hash Algorithm (SHA), cyclic redundancy check (CRC).

18. The computer system of claim 10, wherein the application layer attributes are associated with Hypertext Transfer Protocol (HTTP) and wherein the application layer attributes include one or more of a user-agent, a host, a referrer, a cookie and a Uniform Resource Locator (URL).