Apparatus and method for an overload control procedure against denial of service attack

• US 7,313,092 B2
• Filed: 09/30/2002
• Issued: 12/25/2007
• Est. Priority Date: 09/30/2002
• Status: Active Grant

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Lau, Wing Cheong, Zhang, Yinglu
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Hyun; Soon D.
• Application Number:
  US10/261,299
• Publication Number:
  US 20040062199A1
• Time in Patent Office: 1,912 Days
• Field of Search: None
• US Class Current: 370/230
• CPC Class Codes: H04L 1/20 using signal quality detector
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

The present invention is a methodology to prioritize packets based on the conditional probability that given the values of attributes carried by packet, the packet is a legitimate one. We will call this the conditional legitimate probability of a packet from here onward. The conditional probability of each packet is evaluated based on Bayesian estimation technique. This is accomplished by comparing the attributes carried by an incoming packet against the “nominal” distribution of attributes of legitimate packet stream. Since an exact prioritization of packets based on their conditional legitimate probability would require offline, multiple-pass operations, e.g. sorting, we take the following alternative approach to realize an online, one-pass selectively dropping scheme. In particular, we maintain the cumulative distribution function (CDF) of the conditional legitimate probability of all incoming packets and apply a threshold-based selective dropping mechanism according to the conditional probability value computed for each incoming packet. To speed-up the computation of the conditional legitimate probability for each incoming packet, we may, as an alternative, use the logarithmic version of the equation to implement the Bayesian estimation process. Other features of the invention include: providing means to guarantee minimum throughput of particular (pre-configured) type(s) of packets; providing a. Filtering Mechanism to suppress the noise during estimation/maintenance of nominal attributes distribution; applying state-of-the-art efficient algorithm/data-structures for quantile and histogram building/updates; using the proven, industrial-strength load-shedding algorithms as a submodule in the overload control algorithm; and being amenable to practical implementation to support online, one-pass processing on high-speed communication links.

Claims

1. A method of determining packets to be dropped in regard to a potential denial of service attack at a location within a packet network, said method comprising the steps of:

receiving packets at said location within said network;

computing a conditional probability measure for each packet entering said location based on selected attributes included within said packet;

periodically updating a cumulative distribution function based on previously computed conditional probability measures;

determining a drop threshold based on access to said cumulative distribution function;

passing packets that exceed said determined drop threshold to said location.

2. The method of claim 1, wherein said step of computing a conditional probability measure further includes the steps of updating an individual marginal probability mass function and a joint probability mass function for attributes carried by each said packet.

3. The method of claim 1, further including the step of filtering said conditional probability measure to ensure stable estimates thereof.

4. The method of claim 3, wherein said filtering is selected from the group consisting of sliding window and step-size filtering.

5. The method of claim 1, further including the step of determining whether said packet is believed to be an attacking packet prior to updating said cumulative distribution function.

6. The method of claim 1, further including the step of granting immunity to packets of a specified sub-type entering said location.

7. The method of claim 1, wherein said conditional probability measure is computed in accordance with the following equation:

$\mathrm{CP}<br><br>\left(p\right)=\frac{N_n<br><br>{\mathrm{JP}}_n<br><br>\left(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}\right)}{N_n<br><br>{\mathrm{JP}}_n<br><br>\left(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}\right)+N_o<br><br>{\mathrm{JP}}_u<br><br>\left(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}\right)}=\frac{N_n<br><br>{\mathrm{JP}}_n<br><br>\left(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}\right)}{N_m<br><br>{\mathrm{JP}}_m<br><br>\left(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}\right)}=\frac{{\mathrm{\rho <br><br>}}_n}{{\mathrm{\rho <br><br>}}_m}·<br><br>\frac{{\mathrm{JP}}_n<br><br>\left(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}\right)}{{\mathrm{JP}}_m<br><br>\left(A=a_p,B=b_p,C=c_p,\mathrm{\dots <br><br>}\right)}$

where;

N_n=total number of legitimate, i.e. Normal, packets over a certain observation interval;

N_o=total number of attack packets over a certain observation interval

N_m=total number of packets over a certain observation interval =N_n+N_o;

ρ

_m=current measured utilization of the system;

ρ

_n=nominal/baselined utilization of the system (at a specific time-of-the-day, day-of-the-week, etc);

JP_n(A,B,C, . . . ) is the joint probability mass function of this set of attributes under normal traffic situation;

JP_m(A,B,C, . . . ) is the joint probability mass function of packet attributes measured from current incoming traffic, which may be normal or under attack;

JP_a(A, B,C, . . . ) is the joint probability mass function of this set of attributes under attack situation; and

a, b and c, . . . are the particular values that the attributes A, B and C take.

8. The method of claim 1, wherein said conditional probability measure is computed in accordance with the following equation:

$\mathrm{CP}<br><br>\left(p\right)=\frac{{\mathrm{\rho <br><br>}}_n}{{\mathrm{\rho <br><br>}}_m}·<br><br>\frac{P_n<br><br>\left(A=a_p\right)}{P_m<br><br>\left(A=a_p\right)}·<br><br>\frac{P_n<br><br>\left(B=b_p\right)}{P_m<br><br>\left(B=b_p\right)}·<br><br>\frac{P_n<br><br>\left(C=c_p\right)}{P_m<br><br>\left(C=c_p\right)}$

where;

ρ

_m=current measured utilization of the system;

ρ

_n=nominal/baselined utilization of the system (at a specific time-of-the-day, day-of-the-week, etc);

P_n(A, B,C, . . . ) is the probability mass function of this set of attributes under normal traffic situation;

P_m(A, B,C, . . . ) is the probability mass function of packet attributes measured from current incoming traffic, which may be normal or under attack; and

a, b and c, . . . are the particular values that the attributes A, B and C take.

9. The method of claim 1, wherein said drop threshold is calculated using a load shedding algorithm.

10. The method of claim 2, wherein said joint and marginal probability functions are maintained using iceberg style histograms.

11. A method of determining packets to be dropped in regard to a potential denial of service attack at a location within a packet network, said method comprising the steps of:

receiving packets at said location within said network;

computing a probability measure of an incoming packet based on selected attributes included within said packet;

adjusting a conditional legitimate probability value of said packet;

updating a conditional probability function of conditional probabilities of incoming packets; and

performing a throttling decision as to whether to drop or pass packets through said location.

12. The method of claim 11, wherein said step of computing a probability measure includes the steps of:

updating a probability mass function for said packet;

updating a target maximum utilization measure;

updating parameters in a normal traffic profile if it is determined that no attack is in progress; and

calculating a conditional probability that a packet is a legitimate packet based on said probability mass function.

13. The method of claim 11, wherein said step of adjusting a conditional probability function includes the steps of:

updating the current measured throughput for a specified type of packet;

updating a conditional probability distribution function of said specified type of packet;

calculating a fraction of said specified type of packet to be granted immunity;

determining a conditional probability threshold based on said calculated fraction;

adjusting the conditional probability distribution function if said conditional probability of said packet is greater than said conditional probability threshold.

14. The method of claim 11, wherein said step of updating a conditional probability function includes the steps of:

adjusting the conditional probability function if said packet belongs to a known type of attack packet;

updating the conditional probability function or conditional probability values of all incoming packets after the conditional probability for said packet has been potentially adjusted; and

determining a conditional probability threshold based on a fraction of current traffic needed to be kept to reduce a system load.

15. An apparatus for determining packets to be dropped in regard to a potential denial or service attack at a location within a packet network, said apparatus comprising:

means for receiving packets at said location within said network;

means for computing a probability measure of an incoming packet based on selected attributes included within said packet;

means for adjusting a conditional legitimate probability value of said packet;

means for updating a conditional probability function of conditional probabilities of incoming packets; and

means for performing a throttling decision as to whether or not to pass packets through said location.