# Detection of Variations of Local Irregularity of Traffic under DDOS Flood Attack

Authors: Ming Li; Wei Zhao
Journal: Mathematical Problems in Engineering
 (2008)

---

## Abstract

The aim of distributed denial-of-service (DDOS) flood attacks is to overwhelm the attacked site or to make its service performance deterioration considerably by sending flood packets to the target from the machines distributed all over the world. This is a kind of local behavior of traffic at the protected site because the attacked site can be recovered to its normal service state sooner or later even though it is in reality overwhelmed during attack. From a view of mathematics, it can be taken as a kind of short-range phenomenon in computer networks. In this paper, we use the Hurst parameter (H) to measure the local irregularity or self-similarity of traffic under DDOS flood attack provided that fractional Gaussian noise (fGn) is used as the traffic model. As flood attack packets of DDOS make the H value of arrival traffic vary significantly away from that of traffic normally arriving at the protected site, we discuss a method to statistically detect signs of DDOS flood attacks with predetermined detection probability and false alarm probability.


---

## Body

## 1. Introduction

IP Networks are subject to electronic attacks [1]. An intrusion detection system (IDS) collects information from a variety of systems
and network sources to analyze the information of attack signs. A network-based
IDS monitors the traffic on its network as a data source [2]. For distributed
denial-of-service (DDOS) flood attack, an intruder bombs attack packets upon a
site (victim) with a huge amount of traffic the sources of which are
distributed over the world [3]. Hence the pattern of traffic under DDOS flood
attack may suddenly differ significantly from the normal pattern of the arrival
traffic. From the perspective of dynamical aspects for limited time interval in
physics [4], one may regard this sudden change as a specific “pulse.” Though
DDOS flood attack may not be a sole factor to make traffic pattern vary significantly,
we assume that secure officers can distinguish significant variation of
monitored traffic pattern caused by other known factors (e.g., normally heavy
traffic) from DDOS flood attack. Without confusions causing, the term abnormal
traffic used in this paper specifically implies a traffic series that has
significant variation of traffic pattern caused by DDOS flood attack.In this research, we ponder two
fundamental issues in detection. One is feature extraction of monitored traffic
time series. The other is detection scheme that can be used to assure
predetermined detection probability(Pd) and false alarm probability (Pf). The first issue will be
discussed in Section 2 from a view of feature extraction of traffic based on
self-similarity of traffic. The second will be dissertated in Section 3 based
on statistical detection. Section 4 will explain the performance analysis of
the present detection system. A case study is demonstrated in Section 5.
Discussions are given in Section 6, which is followed by conclusions.


## 2. Feature Extraction of Traffic

### 2.1. Self-Similar Traffic

Computer scientists in the last decade discovered that
traffic is a type of fractal time series. It has the properties of
self-similarity, long memory, and multiscales (see e.g., [5]). A commonly used
model in traffic engineering is fractional Gaussian noise (fGn) (see e.g., [6–8]).LetB(t),t∈(0,∞) be Wiener Brownian motion. Let BH(t) be fractional Brownian motion with the Hurst
parameter H∈(0,1) [9]. Let Γ(⋅) be Gamma
function. Then by using fractional calculus, BH(t) is expressed
by (2.1)BH(t)−BH(0)=1Γ(H+1/2){∫−∞0[(t−u)H−0.5−(−u)H−0.5]dB(u)+∫0t(t−u)H−0.5dB(u)}.LetG(t) be the increment series of BH(t): (2.2)G(t)=BH(t+a)−BH(t), where a is a real number. Then G(t) is fGn [9]. The autocorrelation
function (ACF) of fGn in the discrete case is given by (2.3a)ρ(τ)=σ22[||τ|+1|2H−2|τ|2H+||τ|−1|2H], where σ2=Γ(2−H)cos⁡(πH)/πH(2H−1) is the intensity of fGn [10]. The
normalized ACF of fGn is given by (2.3b)R(τ)=12[||τ|+1|2H−2|τ|2H+||τ|−1|2H]. The
relationship between the fractal dimension of fGn and H is given by (2.4)D=2−H.Approximating the right side of (2.3b) with the second-order differential
of 0.5(τ)2H, see [9, H15, page 350], for τ≥0, yields (2.5)0.5[(τ+1)2H−2τ2H+(τ−1)2H]≈H(2H−1)τ2H−2.Lety and R be a
traffic series and its ACF, respectively. Then according to (2.5), (2.6)R(τ)∼cτ2H−2,H∈(0.5,1), where ~ implies the asymptotical equivalence under the
limit τ→∞ and c>0 is a constant [11].The ACF (2.5)
is nonsummable for H>0.5, implying long-range dependence (LRD). Hence H is a measure of LRD of traffic. It is kindly noted that LRD of
traffic does not mean that DDOS attacking is a long-range phenomenon. On the contrary,
DDOS attacking and its detection are short-range phenomena since both sides,
namely, an attacker and its opponent, are engaged with each other during a
short period of time. Such a battle makes local irregularity of traffic vary dramatically [12].Without
losing generality, we consider traffic seriesy in the discrete case. By
dividing y into nonoverlapping blocks of size L and averaging
over each block, we obtain another series given by (2.7)y(i)(L)=1L∑j=iL(i+1)Ly(j). According to the analysis in [5, 9, 11], in the fGn sense, one has (2.8)Var(y(L))=L2H−2Var(y), where Var implies the variance
operator. Thus the self-similarity is measured by H.A series
encountered in engineering is usually of finite length. Lety be a
series of P length. Divide it into N nonoverlapping sections.
Each section is divided into M nonoverlapping segments. Divide each
segment into K nonoverlapping blocks. Each block is of L length. Let y(i)m(L)(n) be the series with aggregated level L in
the mth segment of the nth section (m=0,1,…,M−1;n=0,1,…,N−1). Let
Hm(n) be the H value of y(i)m(L)(n). Let r(k;Hm(n)) be the measured ACF of y(i)m(L)(n) in the normalized case. The theoretic ACF form
corresponding y(i)m(L)(n) in the fGn sense is given by (2.9)R(k;Hm(n))=0.5[||k|+1|2Hm(n)−2|k|2Hm(n)+||k|−1|2Hm(n)]. The above expression exhibits the multifractal property of
traffic as can be seen from [13].Let(2.10)J(Hm(n))=∑k[R(k;Hm(n))−r(k;Hm(n))]2 be the cost function. Then one has (2.11)Hm(n)=arg⁡min⁡J[Hm(n)]. Averaging Hm(n) in terms of index m yields (2.12)H(n)=1M∑m=0M−1Hm(n), representing
the H estimate of the  series in the nth section.Usually,H(n1)≠H(n2) for n1≠n2. However, stationarity of traffic time
series implies that H(n) at a specific site is a number falling
within a certain confidence interval [5, Paragraph 5, Section 5, page 966]. In
practical terms, a normality assumption for H(n) is quite
accurate in most cases for M>10 regardless of probability
distribution function of H [14]. Thus we take (2.13)Hx=E[H(n)] as a mean estimate of H of x, where E is the mean operator. It can be taken as a template of H of x for
the purpose of statistical detection. The appendix gives a case of the H estimation of a real-traffic series to clarify the reasonableness of H in featuring traffic time series.


### 2.2. Characterizing Traffic Time Series withH

Letx be normal
traffic time series. Normally, the site serves x peacefully though x may
sometimes be unpleasantly delayed because of the normal traffic jam. The
arrival traffic x is contributed by
many connections distributed all over the world. Figure 1 shows x contributed by traffic from d connections. From previous discussions, we see that x can be characterized by the Hurst
parameter and we denote it as Hx.Figure 1
Normal traffic at input of a server.Assume that the site is
intruded by DDOS flood attacking. Then actual arrival traffic (abnormal
traffic) consists of normal trafficx and attack traffic a, see
Figure 2, where a is contributed by e connections. We use Hy as a feature of y.Figure 2
Illustration of abnormal traffic.


## 2.1. Self-Similar Traffic

Computer scientists in the last decade discovered that
traffic is a type of fractal time series. It has the properties of
self-similarity, long memory, and multiscales (see e.g., [5]). A commonly used
model in traffic engineering is fractional Gaussian noise (fGn) (see e.g., [6–8]).LetB(t),t∈(0,∞) be Wiener Brownian motion. Let BH(t) be fractional Brownian motion with the Hurst
parameter H∈(0,1) [9]. Let Γ(⋅) be Gamma
function. Then by using fractional calculus, BH(t) is expressed
by (2.1)BH(t)−BH(0)=1Γ(H+1/2){∫−∞0[(t−u)H−0.5−(−u)H−0.5]dB(u)+∫0t(t−u)H−0.5dB(u)}.LetG(t) be the increment series of BH(t): (2.2)G(t)=BH(t+a)−BH(t), where a is a real number. Then G(t) is fGn [9]. The autocorrelation
function (ACF) of fGn in the discrete case is given by (2.3a)ρ(τ)=σ22[||τ|+1|2H−2|τ|2H+||τ|−1|2H], where σ2=Γ(2−H)cos⁡(πH)/πH(2H−1) is the intensity of fGn [10]. The
normalized ACF of fGn is given by (2.3b)R(τ)=12[||τ|+1|2H−2|τ|2H+||τ|−1|2H]. The
relationship between the fractal dimension of fGn and H is given by (2.4)D=2−H.Approximating the right side of (2.3b) with the second-order differential
of 0.5(τ)2H, see [9, H15, page 350], for τ≥0, yields (2.5)0.5[(τ+1)2H−2τ2H+(τ−1)2H]≈H(2H−1)τ2H−2.Lety and R be a
traffic series and its ACF, respectively. Then according to (2.5), (2.6)R(τ)∼cτ2H−2,H∈(0.5,1), where ~ implies the asymptotical equivalence under the
limit τ→∞ and c>0 is a constant [11].The ACF (2.5)
is nonsummable for H>0.5, implying long-range dependence (LRD). Hence H is a measure of LRD of traffic. It is kindly noted that LRD of
traffic does not mean that DDOS attacking is a long-range phenomenon. On the contrary,
DDOS attacking and its detection are short-range phenomena since both sides,
namely, an attacker and its opponent, are engaged with each other during a
short period of time. Such a battle makes local irregularity of traffic vary dramatically [12].Without
losing generality, we consider traffic seriesy in the discrete case. By
dividing y into nonoverlapping blocks of size L and averaging
over each block, we obtain another series given by (2.7)y(i)(L)=1L∑j=iL(i+1)Ly(j). According to the analysis in [5, 9, 11], in the fGn sense, one has (2.8)Var(y(L))=L2H−2Var(y), where Var implies the variance
operator. Thus the self-similarity is measured by H.A series
encountered in engineering is usually of finite length. Lety be a
series of P length. Divide it into N nonoverlapping sections.
Each section is divided into M nonoverlapping segments. Divide each
segment into K nonoverlapping blocks. Each block is of L length. Let y(i)m(L)(n) be the series with aggregated level L in
the mth segment of the nth section (m=0,1,…,M−1;n=0,1,…,N−1). Let
Hm(n) be the H value of y(i)m(L)(n). Let r(k;Hm(n)) be the measured ACF of y(i)m(L)(n) in the normalized case. The theoretic ACF form
corresponding y(i)m(L)(n) in the fGn sense is given by (2.9)R(k;Hm(n))=0.5[||k|+1|2Hm(n)−2|k|2Hm(n)+||k|−1|2Hm(n)]. The above expression exhibits the multifractal property of
traffic as can be seen from [13].Let(2.10)J(Hm(n))=∑k[R(k;Hm(n))−r(k;Hm(n))]2 be the cost function. Then one has (2.11)Hm(n)=arg⁡min⁡J[Hm(n)]. Averaging Hm(n) in terms of index m yields (2.12)H(n)=1M∑m=0M−1Hm(n), representing
the H estimate of the  series in the nth section.Usually,H(n1)≠H(n2) for n1≠n2. However, stationarity of traffic time
series implies that H(n) at a specific site is a number falling
within a certain confidence interval [5, Paragraph 5, Section 5, page 966]. In
practical terms, a normality assumption for H(n) is quite
accurate in most cases for M>10 regardless of probability
distribution function of H [14]. Thus we take (2.13)Hx=E[H(n)] as a mean estimate of H of x, where E is the mean operator. It can be taken as a template of H of x for
the purpose of statistical detection. The appendix gives a case of the H estimation of a real-traffic series to clarify the reasonableness of H in featuring traffic time series.


## 2.2. Characterizing Traffic Time Series withH

Letx be normal
traffic time series. Normally, the site serves x peacefully though x may
sometimes be unpleasantly delayed because of the normal traffic jam. The
arrival traffic x is contributed by
many connections distributed all over the world. Figure 1 shows x contributed by traffic from d connections. From previous discussions, we see that x can be characterized by the Hurst
parameter and we denote it as Hx.Figure 1
Normal traffic at input of a server.Assume that the site is
intruded by DDOS flood attacking. Then actual arrival traffic (abnormal
traffic) consists of normal trafficx and attack traffic a, see
Figure 2, where a is contributed by e connections. We use Hy as a feature of y.Figure 2
Illustration of abnormal traffic.


## 3. Detection Method and System Structure

To explain
our detection principle, we introduce three terms. Correctly recognizing an
abnormal sign is termeddetection;
failing to recognize it, miss;
mistakenly recognizing a normal as abnormal is a false alarm.Letξ=∥Hx−Hy∥. Then ξ represents the deviation of H of
monitored traffic time series. Let V>0 be the threshold. Then the
detection hypotheses are as follows. ξ>V, implies detection, while ς=∥Hx−Hxl∥>V represents false alarm, where Hxl stands for H which is not used as the template
but obtained when there is no attacking. Clearly, ξ and ζ are random variables. Mathematically, there
are many distance measures available [15–17], but the
following works well: (3.1)ξ=E[∑k|HyHx−log⁡HyHx−1|].According
to the previous discussions, we give the system diagram in Figure3. The
measured arrival traffic first passes through an H estimator. The result
of H estimator goes to template database to produce the template Hx. In addition, it outputs an online estimate of  Hy. Hx and Hy are compared in the distance
detector. The comparison result ξ is
fed into threshold detector to compare with a given threshold V. In the
stage of decision analysis, the output of the threshold detector is analyzed
and its output gives a sign of detection according to preset detection
probability and false alarm probability.Figure 3
System diagram.


## 4. Performance Analysis

With the
partition explained in Section2, we see that there is a value of ξ representing the deviation of H of y in each segment. Therefore, in each
section, ξ is a random sequence of M length. Denote ξ¯ as the expectation of ξ in each section. Then ξ¯ is a random sequence of N length. In the case of N≥10,ξ¯ well obeys Gaussian distribution [14]. For the simplicity, we still denote ξ¯ as ξ.


### 4.1. Detection Probability

Letμξ and σξ2 be the expectation and the variance of ξ, respectively. Then (4.1)ξ∼N(μξ,σξ2)=12πσξe−(ξ−μξ)2/2σξ2. Let (4.2)Φ(t)=∫−∞t12πe−t2/2dt. Then detection probability is given by (4.3)Pd=P{V<ξ<∞}=∫(V−μξ)/σξ∞12πe−t2/2dt=1−Φ[V−μξσξ].


### 4.2. False Alarm Probability

Letμζ and σς2 be the mean and the variance of ζ. Then false alarm probability is
given by (4.4)Pf=P{V<ζ<∞}=∫(V−μς)/σς∞12πe−t2/2dt=1−Φ[V−μζσζ].


### 4.3. Miss Probability

LetPm be miss probability. Then (4.5)Pm=P{−∞<ξ<V}=∫−∞(V−μξ)/σξ12πe−t2/2dt=Φ[V−μξσξ].Generally,μζ=0. Besides, the numeric computation in data processing can be arranged such that σζ=σξ=σ. In this
case, three probabilities are given by (4.6)Pd=∫(V−μξ)/σ∞12πe−t2/2dt=1−Φ[V−μξσ],Pf=∫V/σ∞12πe−t2/2dt=1−Φ(Vσ),Pm=∫−∞(V−μξ)/σ12πe−t2/2dt=1−Φ[V−μξσ]. Figures 4–6 show the curves of three distributions, respectively. As Pd+Pm=1, high Pd implies low Pm and vice versa.Figure 4
Detection probability.Figure 5
Miss probability.Figure 6
False alarm probability.


### 4.4. Threshold and Detection Region

As can be
seen from the previous discussions, the selection of a threshold value is
crucial to our system. In fact, given a false alarm probabilityf, we want to find the threshold Vf such that P(Vf)≤f. Clearly, (4.7)Vf≥−σΦ−1(f). If f=0 and when the selected precision is 4, we obtain (4.8)Vf≥4σ. Given a detection probability d, we want to find the threshold Vd such that Pd(Vd)≥d. Clearly,(4.9)Vd≤μξ−σΦ−1(d),ifμξ−σΦ−1(d)>0. In the case of d=1,(4.10)Vd≤μξ−4σ,ifμξ−4σ>0. Therefore, when −σΦ−1(f)<μξ−σΦ−1(d) and V∈[−σΦ−1(f),μξ−σΦ−1(d)],Pd≥d and Pf≤f are assured. That is, (4.11)Pd≥d,Pf≤f,ifV∈[−σΦ−1(f),μξ−σΦ−1(d)],μξ−σΦ−1(d)>0. In the case of d=1 and f=0, (4.12)Pd=1,Pf=0,ifV∈[4σ,μξ−4σ],μξ−4σ>0. The constraint of (4.12) is given
by μξ>8σ.Obviously,
the detection region is the intersection of three probability functions. Under
the condition ofμξ=80 and σ=10, the detection region is shown in Figure 7.Figure 7
Intersection of three probability distributions: detection region.


## 4.1. Detection Probability

Letμξ and σξ2 be the expectation and the variance of ξ, respectively. Then (4.1)ξ∼N(μξ,σξ2)=12πσξe−(ξ−μξ)2/2σξ2. Let (4.2)Φ(t)=∫−∞t12πe−t2/2dt. Then detection probability is given by (4.3)Pd=P{V<ξ<∞}=∫(V−μξ)/σξ∞12πe−t2/2dt=1−Φ[V−μξσξ].


## 4.2. False Alarm Probability

Letμζ and σς2 be the mean and the variance of ζ. Then false alarm probability is
given by (4.4)Pf=P{V<ζ<∞}=∫(V−μς)/σς∞12πe−t2/2dt=1−Φ[V−μζσζ].


## 4.3. Miss Probability

LetPm be miss probability. Then (4.5)Pm=P{−∞<ξ<V}=∫−∞(V−μξ)/σξ12πe−t2/2dt=Φ[V−μξσξ].Generally,μζ=0. Besides, the numeric computation in data processing can be arranged such that σζ=σξ=σ. In this
case, three probabilities are given by (4.6)Pd=∫(V−μξ)/σ∞12πe−t2/2dt=1−Φ[V−μξσ],Pf=∫V/σ∞12πe−t2/2dt=1−Φ(Vσ),Pm=∫−∞(V−μξ)/σ12πe−t2/2dt=1−Φ[V−μξσ]. Figures 4–6 show the curves of three distributions, respectively. As Pd+Pm=1, high Pd implies low Pm and vice versa.Figure 4
Detection probability.Figure 5
Miss probability.Figure 6
False alarm probability.


## 4.4. Threshold and Detection Region

As can be
seen from the previous discussions, the selection of a threshold value is
crucial to our system. In fact, given a false alarm probabilityf, we want to find the threshold Vf such that P(Vf)≤f. Clearly, (4.7)Vf≥−σΦ−1(f). If f=0 and when the selected precision is 4, we obtain (4.8)Vf≥4σ. Given a detection probability d, we want to find the threshold Vd such that Pd(Vd)≥d. Clearly,(4.9)Vd≤μξ−σΦ−1(d),ifμξ−σΦ−1(d)>0. In the case of d=1,(4.10)Vd≤μξ−4σ,ifμξ−4σ>0. Therefore, when −σΦ−1(f)<μξ−σΦ−1(d) and V∈[−σΦ−1(f),μξ−σΦ−1(d)],Pd≥d and Pf≤f are assured. That is, (4.11)Pd≥d,Pf≤f,ifV∈[−σΦ−1(f),μξ−σΦ−1(d)],μξ−σΦ−1(d)>0. In the case of d=1 and f=0, (4.12)Pd=1,Pf=0,ifV∈[4σ,μξ−4σ],μξ−4σ>0. The constraint of (4.12) is given
by μξ>8σ.Obviously,
the detection region is the intersection of three probability functions. Under
the condition ofμξ=80 and σ=10, the detection region is shown in Figure 7.Figure 7
Intersection of three probability distributions: detection region.


## 5. A Case Study

Suppose the templateH0=0.7671 as described in the appendix. Assume that the confidence level is
99.9999%. Thus we suppose y′sH∈(0.5000,0.7669) or (0.7673,0.9900) during
the transition process of intrusion. In this case study, 1000 points of Hs in (0.5000,0.7669) or (0.7673,0.9900) are randomly selected to simulate the abnormal traffic deviating from
the normal one. The error sequence is indicated in Figure 8. By the numeric
computation, we obtain μξ=210.3011 and σ=7.7490. Therefore, we obtain the probability
distributions for detection, false alarm and miss as shown in Figure 9. Under
the conditions of Pd=1 and Pf=0,
we obtain Vmin⁡=30.9951 and Vmax⁡=179.3052. Hence when we select V∈[30.9951,179.3052], we have 99.9999% confidence
to say that Pd=1 and Pf=0 are assured, which can be easily observed from Figure 9.Figure 8
Random variableξ.Figure 9
Case study: detection region.


## 6. Discussions

Since Yahoo servers were successfully attacked in 2001,
the issue of detecting DDOS flood attacking has been paid much attention to.
Various methods and systems have been proposed, see, for example, [18–25]. As known,
traffic under DDOS flood attack must be significantly different from that of
normal one [25]. Otherwise, DDOS flood attack would have no effect. From this
point of view, the value of H of traffic under DDOS flood attacks is
considerably different from that of normal one, see [12] for details.For a stationary random time
series of finite length, ACF and power spectrum density (PSD) function are
commonly used in engineering for feature extraction in statistical
classifications [16, 17]. However, the PSD of traffic does not exist in the
domain of ordinary functions since it has long memory [8]. To avoid such a
difficulty in mathematics, consequently, ACF of traffic is considered for
feature extraction in our early work [25]. This paper focuses on detection of
local variations of traffic based on the self-similarity of traffic. Thus it
suggests a new method that substantially develops the work of [25], from the
point of view of traffic pattern matching, because feature extraction of
traffic time series by using a single parameter H makes pattern matching
more efficient.


## 7. Conclusions

We have discussed the
characterization of the local irregularity of traffic byH(n). We
have explained a principle of statistical detection to capture signs of DDOS
flood attacking with predetermined detection probability and false alarm
probability based on the variation of the local irregularity of traffic.



---

*Source: 475878-2008-09-01.xml*