Abstract:
Methods and systems for detecting and defeating a low and slow application DDoS attack, comprising: computing the Entropy of a plurality of detectors, at least in part selected from a group Geo detector, a group response size detector, a group preference detector, and an individual client behavior detector, wherein the plurality of detectors each describe a feature of traffic affected by the DDoS attack; composing the plurality of detectors on one or more of a Receiver Operating Characteristic (ROC) curve basis and a correlation basis; and implementing a countermeasure to mitigate the DDoS attack.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    The present patent application/patent claims the benefit of priority of co-pending U.S. Provisional Patent Application No. 62/331,563, filed on May 4, 2016, and entitled “MULTIPLE DETECTOR COMPOSITION AGAINST LOW AND SLOW APPLICATION DDOS ATTACKS,” the contents of which are incorporated in full by reference herein. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The present invention relates generally to multiple detector methods and systems for defeating low and slow application Distributed Denial of Service (DDoS) attacks. 
       BACKGROUND OF THE INVENTION 
       [0003]    Low and slow DDoS attacks targeting critical services can cause serious problems. In low and slow DDoS attacks, computer criminals mimic legitimate client behavior by sending proper-looking requests via compromised and commandeered hosts. These low and slow DDoS attacks exploit the fact that many Internet servers have “open clientele” (i.e., they cannot tell a good client from the request alone), and force the victim server to spend much of its resources on spurious requests. The main properties of low and slow DDoS attacks are: (1) they are large scale, since the attacks can be launched from a large number of bots, and (2) they are stealthy (i.e., low volume), since the attack traffic is undetectable using browser fingerprinting, as the attack requests are generated from legitimate browsers (e.g., using man-in-the-browser malware), are undetectable at the server level since individual attack flow looks legitimate, and are undetectable at the network level since the flow volume is small. 
         [0004]    Thus, what are still needed in the art are improved multiple detector methods and systems for defeating low and slow application DDoS attacks. 
       BRIEF SUMMARY OF THE INVENTION 
       [0005]    In general, DDoS attack traffic always tends to change the normal behaviors of various traffic features. A traffic feature is a distinctive attribute or aspect of the traffic information that can be extracted from the web logs or traces. In various exemplary embodiments, the present invention uses an Entropy measure as a metric to identify features that can be used in identifying low and slow DDoS attacks. The following features are selected in some exemplary embodiments of the detectors described herein: 
         [0006]    client Geo IP, 
         [0007]    request time (i.e., the time when the request is made), 
         [0008]    response size (i.e., the size of the server response packets), 
         [0009]    response time (i.e., the time or the server to respond the request), 
         [0010]    user preference (i.e., the web page requested), or 
         [0011]    user ISP. 
         [0012]    In one exemplary embodiment, the present invention provides a method for detecting and defeating a low and slow application DDoS attack, comprising: computing the Entropy of a plurality of detectors, at least in part selected from a group Geo detector, a group response size detector, a group preference detector, and an individual client behavior detector, wherein the plurality of detectors each describe a feature of traffic affected by the DDoS attack; composing the plurality of detectors on one or more of a Receiver Operating Characteristic (ROC) curve basis and a correlation basis; and implementing a countermeasure to mitigate the DDoS attack. The Geo detector comprises one or more of country, state, city, latitude, and longitude information that is obtained from an IP to location mapping database. The Geo detector comprises a normal traffic profile representing a conditional Entropy conditioned on one or more of time, preference, and ISP and a current traffic profile representing a conditional Entropy conditioned on one or more of time, preference, and ISP. The Geo detector compares the current traffic profile to the normal traffic profile and raises an alarm if a predetermined threshold difference is met or exceeded. The response size detector is based on one or more of location and time and is obtained from a web log. The response size detector compares a current traffic profile to a normal traffic profile and raises an alarm if a predetermined threshold difference is met or exceeded. The preference detector is based on one or more of location and time and is obtained from a web log. The preference detector compares a current traffic profile to a normal traffic profile and raises an alarm if a predetermined threshold difference is met or exceeded. The client behavior detector comprises a consecutive requested resources sub-detector that is a Markov chain of consecutive requested resources of individual users and an inter-arrival time sub-detector that is a Markov chain of time length between consecutive requests. The client behavior detector compares an Entropy of a Markov chain of a current traffic profile to an Entropy of a Markov chain of a normal traffic profile and raises an alarm if a predetermined threshold difference is met or exceeded. The ROC curve basis for composing the plurality of detectors comprises, for every detector, estimating a true positive rate and a false positive rate for different threshold values based on a history profile, drawing an ROC curve, and selecting detectors and thresholds based on the ROC curve and predetermined constraints. The correlation basis for composing the plurality of detectors comprises calculating an evasion resistance of the detectors and combining them with a weighted sum to provide a trigger for alarm, wherein the alarm is triggered if one or more of a summation of a weighted risk of all detectors meets or exceeds a threshold and a threshold number of individual above-threshold detectors is met or exceeded. Optionally, the countermeasure implemented is based on a weighted risk value. 
         [0013]    In another exemplary embodiment, the present invention provides a system for detecting and defeating a low and slow application DDoS attack, comprising: a processor executing instructions to: compute the Entropy of a plurality of detectors, at least in part selected from a group Geo detector, a group response size detector, a group preference detector, and an individual client behavior detector, wherein the plurality of detectors each describe a feature of traffic affected by the DDoS attack; compose the plurality of detectors on one or more of a Receiver Operating Characteristic (ROC) curve basis and a correlation basis; and implement a countermeasure to mitigate the DDoS attack. The Geo detector comprises one or more of country, state, city, latitude, and longitude information that is obtained from an IP to location mapping database. The Geo detector comprises a normal traffic profile representing a conditional Entropy conditioned on one or more of time, preference, and ISP and a current traffic profile representing a conditional Entropy conditioned on one or more of time, preference, and ISP. The Geo detector compares the current traffic profile to the normal traffic profile and raises an alarm if a predetermined threshold difference is met or exceeded. The response size detector is based on one or more of location and time and is obtained from a web log. The response size detector compares a current traffic profile to a normal traffic profile and raises an alarm if a predetermined threshold difference is met or exceeded. The preference detector is based on one or more of location and time and is obtained from a web log. The preference detector compares a current traffic profile to a normal traffic profile and raises an alarm if a predetermined threshold difference is met or exceeded. The client behavior detector comprises a consecutive requested resources sub-detector that is a Markov chain of consecutive requested resources of individual users and an inter-arrival time sub-detector that is a Markov chain of time length between consecutive requests. The client behavior detector compares an Entropy of a Markov chain of a current traffic profile to an Entropy of a Markov chain of a normal traffic profile and raises an alarm if a predetermined threshold difference is met or exceeded. The ROC curve basis for composing the plurality of detectors comprises, for every detector, estimating a true positive rate and a false positive rate for different threshold values based on a history profile, drawing an ROC curve, and selecting detectors and thresholds based on the ROC curve and predetermined constraints. The correlation basis for composing the plurality of detectors comprises calculating an evasion resistance of the detectors and combining them with a weighted sum to provide a trigger for alarm, wherein the alarm is triggered if one or more of a summation of a weighted risk of all detectors meets or exceeds a threshold and a threshold number of individual above-threshold detectors is met or exceeded. Optionally, the countermeasure implemented is based on a weighted risk value. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]    The present invention is illustrated and described herein with reference to the various drawings, in which like reference numbers are used to denote like method steps/system components, as appropriate, and in which: 
           [0015]      FIG. 1  shows one exemplary embodiment of the flow architecture of the methods and systems of the present invention; and 
           [0016]      FIG. 2  shows one exemplary embodiment of a hardware environment in which the methods and systems of the present invention can be implemented. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0017]    Referring now specifically to  FIG. 1 , in one exemplary embodiment, the detectors used herein may be classified into two categories based on the behaviors involved: group or individual. Group detectors are based on the collective behavior of all users using the aggregate traffic, and individual detectors are based on individual user behavior. The following describes the detectors: 
         [0018]    A. Geo detectors (Group) compute the Entropy of Geo IP given time (denoted D(Geo|time)), preference (denoted D(Geo|preference)), or ISP (denoted D(Geo|ISP)). The following are the steps to construct these detectors:
       (1) The Geo IP of the client includes country, state, city, latitude, and longitude, which can be obtained by the IP to location (ip2loc) mapping database. That is, Geo(user)=ip2loc(IP).   (2) We build the normal profile of the detector by calculating the conditional Entropy of Geo IP conditioned on time, preference, or ISP, which is:
           Σ j q j Σ i p i  log p i , where p i  is the percentage of the requests with the ith Geo IP over total number of requests and q j  is the percentage of requests with the jth time, preference, or ISP.   
           (3) For the current traffic, we also calculate the Entropy of user Geo IP based on time, preference, or ISP.   (4) We compare the current traffic distribution and normal profile distribution by calculating the difference between them. If the difference is larger than the threshold, we trigger the alarm for possible attack.       
 
         [0024]    B. Response Size detectors (Group), given location (denoted as D(size|location)) or time (denoted D(size|time)). The steps to construct these detectors are similar to the Geo detectors, the only difference is that the response size can be directly obtained from the web log. 
         [0025]    C. Preference detectors (Group), given location (denoted as D(preference|location)) or time (denoted as D(preference|time)). The steps to construct these detectors are similar to the Response Size detectors. 
         [0026]    D. Client Behavior detectors (Individual), which contain sub-detectors:
       Consecutive requested resources, which is the Markov chain of consecutive requested resources of individual users (denoted as D(consecutive resource)); and   Inter-arrival time, which is the Markov chain of time length between consecutive requests (denoted as D(inter-arrival time)).
 
The steps to construct these detectors are similar to the Response Size detectors, the only difference is that the difference is measured on the difference of Entropy of Markov chains between the normal profile and current traffic.
       
 
         [0029]    The Composition of Multiple Detectors: 
         [0030]    (A) Receiver Operating Characteristic (ROC) curve based composition. The main idea is to model the problem as a constraint satisfaction problem to achieve desired detection effectiveness with bounded cost based on the ROC curve of multiple detectors. The following are the steps:
       (1) For every detector, estimate the true positive rate (T) and false positive rate (F) for different threshold values, based on a history profile (e.g., log files). Here true positive rate T=TP/(TP+FN), where TP is the number of true positives and FN is the number of false negatives. The false positive rate F=FP/(TP+FP), where FP is the number of false positives.   (2) Draw the ROC curve for the detectors.   (3) Select the detectors and threshold for the detectors based on the ROC curve and the following constraints:       
 
         [0000]        i−Π   i (1− v   i   T   jk   i )&gt;Δ 1j , for all  j   (1)
 
         [0000]      Π i (1− v   i   +v   i   F   jk   i )&lt;Δ 2j , for all  j   (2)
 
         [0000]      Σ i   C   i   v   i &lt;Δ 3   (3)
 
         [0000]        v   i ε{0,1}  (4)
 
         [0034]    Here T jk   i  is the true positive rate for detector i against attack j with threshold k, F jk   i  is the false positive rate for detector i against attack j with threshold k, C i  is the cost for detector i, and v i  is the variable to denote whether detector i is selected or not. Δ 1 ,Δ 2 , and Δ 3  are user specified thresholds. Equations (1) and (2) guarantee that the true positive rate and false positive rate should be bounded by user defined thresholds. Equation (3) guarantees that the total cost of the detectors should be bounded. Equation (4) specifies the range of variable v i . 
         [0035]    B. Correlation-Based Composition. The main idea here is to measure the evasion resistance of multiple detectors and combine them with a weighted sum to provide the trigger for alarm or mitigation. The following are the steps:
       (1) For every detector i, calculate the evasion resistance:       
 
         [0000]      σ i =( t   i   −s   i )/( t   i   −b   i )  (5)
           where t i  is the threshold, Si is the standard deviation of normal profile, and b i  is the base line.       (2) Calculate the normalized evasion resistance for detector i as:       
 
         [0000]        n   i   =c   i /( c   1   + . . . +c   k )  (6)
           where k is the number of detectors.       (3) For the current traffic calculate the weighted risk for detector i as:       
 
         [0000]      =η= n   i ( c   i   −t   i )/( t   i   −b   i )  (7)
           where c i  is the current traffic value for detector i.       (4) Two methods can be used for alarm trigger. We can either calculate the summation of the weighted risk of all detectors (Σ i =η), and trigger the alarm if it is larger than the threshold, or set the threshold for every detector, and trigger the alarm if the number of above-threshold detectors is above a threshold.       
 
         [0043]    Note that countermeasures can also be based on the weighted risk. Different countermeasures (such as CAPTCHA, Re-Authentication, Blacklist, Proxy Mutation, etc.) can be triggered by different risk values. 
         [0044]    DDoS attacks can be categorized into three non-mutually exclusive categories: (1) Volumetric based attacks, (2) Semantic based attacks, and (3) Blended Traffic based attacks. For volumetric based attacks, existing countermeasures include Black Listing and Rate Limiting. However, they cannot detect low and slow DDoS attacks. For semantic based attacks, existing countermeasures include behavior monitoring to identify anomaly and proactive resource release. However, behavior monitoring may fail to detect low and slow DDoS attacks if the specified feature is below threshold and proactive resource release may inadvertently disrupt legitimate users. For blended traffic based attacks, existing countermeasures include feature profiling, source authentication, bandwidth currency, protocol pattern matching, and source verification. However, feature profiling based measures have static baseline profiles which may not be able to detect adaptive attackers. Source authentication is not applicable to large scale attacks. Bandwidth currency is not applicable to low DDoS attacks. Protocol pattern matching is too costly and inefficient. Source verification is intrusive and reduces application productivity. The techniques of the present invention utilizing detector and mitigation composition are more robust and resilient than existing approaches in defending low and slow DDoS attacks since we consider multiple attack features and mitigation techniques simultaneously and apply formal method based approaches to minimize false negative/positive and maximize benefits. 
         [0045]    Referring now specifically to  FIG. 2 , in one exemplary embodiment, one or more servers  100  may be used in conjunction with the methods and systems of the present invention. Each server  100  may be a digital computer that, in terms of hardware architecture, generally includes a processor  102 , input/output (I/O) interfaces  104 , a network interface  106 , a data store  108 , and memory  110 . It should be appreciated by those of ordinary skill in the art that  FIG. 2  depicts the server  100  in an oversimplified manner, and a practical embodiment may include additional components and suitably configured processing logic to support known or conventional operating features that are not described in detail herein. The components ( 102 ,  104 ,  106 ,  108 , and  110 ) are communicatively coupled via a local interface  112 . The local interface  112  may be, for example, but not limited to, one or more buses or other wired or wireless connections, as is known in the art. The local interface  112  may have additional elements, which are omitted for simplicity, such as controllers, buffers (caches), drivers, repeaters, and receivers, among many others, to enable communications. Further, the local interface  112  may include address, control, and/or data connections to enable appropriate communications among the aforementioned components. 
         [0046]    The processor  102  is a hardware device for executing software instructions. The processor  102  may be any custom made or commercially available processor, a central processing unit (CPU), an auxiliary processor among several processors associated with the server  100 , a semiconductor-based microprocessor (in the form of a microchip or chip set), or generally any device for executing software instructions. When the server  100  is in operation, the processor  102  is configured to execute software stored within the memory  110 , to communicate data to and from the memory  110 , and to generally control operations of the server  100  pursuant to the software instructions. The I/O interfaces  104  may be used to receive user input from and/or for providing system output to one or more devices or components. User input may be provided via, for example, a keyboard, touchpad, and/or a mouse. System output may be provided via a display device and a printer (not shown). I/O interfaces  104  may include, for example, a serial port, a parallel port, a small computer system interface (SCSI), a serial ATA (SATA), a fibre channel, Infiniband, iSCSI, a PCI Express interface (PCI-x), an infrared (IR) interface, a radio frequency (RF) interface, and/or a universal serial bus (USB) interface. 
         [0047]    The network interface  106  may be used to enable the server  100  to communicate on a network, such as the Internet. The network interface  106  may include, for example, an Ethernet card or adapter (e.g., 10BaseT, Fast Ethernet, Gigabit Ethernet, 10 GbE) or a wireless local area network (WLAN) card or adapter (e.g., 802.11a/b/g/n/ac). The network interface  106  may include address, control, and/or data connections to enable appropriate communications on the network. A data store  108  may be used to store data. The data store  108  may include any of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, and the like)), nonvolatile memory elements (e.g., ROM, hard drive, tape, CDROM, and the like), and combinations thereof. Moreover, the data store  108  may incorporate electronic, magnetic, optical, and/or other types of storage media. In one example, the data store  108  may be located internal to the server  100  such as, for example, an internal hard drive connected to the local interface  112  in the server  100 . Additionally, in another embodiment, the data store  108  may be located external to the server  100  such as, for example, an external hard drive connected to the I/O interfaces  104  (e.g., SCSI or USB connection). In a further embodiment, the data store  108  may be connected to the server  100  through a network, such as, for example, a network attached file server. 
         [0048]    The memory  110  may include any of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, etc.)), nonvolatile memory elements (e.g., ROM, hard drive, tape, CDROM, etc.), and combinations thereof. Moreover, the memory  110  may incorporate electronic, magnetic, optical, and/or other types of storage media. Note that the memory  110  may have a distributed architecture, where various components are situated remotely from one another but can be accessed by the processor  102 . The software in memory  110  may include one or more software programs, each of which includes an ordered listing of executable instructions for implementing logical functions. The software in the memory  110  includes a suitable operating system (O/S)  114  and one or more programs  116 . The operating system  114  essentially controls the execution of other computer programs, such as the one or more programs  116 , and provides scheduling, input-output control, file and data management, memory management, and communication control and related services. The one or more programs  116  may be configured to implement the various processes, algorithms, methods, techniques, etc. described herein. 
         [0049]    Although the present invention is illustrated and described herein with reference to preferred embodiments and specific examples thereof, it will be readily apparent to those of ordinary skill in the art that other embodiments and examples may perform similar functions and/or achieve like results. All such equivalent embodiments and examples are within the spirit and scope of the present invention, are contemplated thereby, and are intended to be covered by the following non-limiting claims.