Abstract: This study presents a novel approach for the prediction and detection of distributed denial of service (DDoS) attacks by using EAQPSO-SVM algorithm which is implemented through combining the improved Quantum-behaved Particle Swarm Optimization (QPSO) algorithm with Support Vector Machine (SVM) theory. In order to improve the global searching performance of the classical QPSO algorithm for avoiding falling into local extreme value point, the Evolution Speed Factor (ESF) and Aggregation Degree Factor (ADF) were introduced in the EAQPSO-SVM algorithm to establish a binary relation function for correcting the self-adaptive expansion-contraction coefficient. Furthermore, a hybrid entropies strategy is proposed to identify the potential DDoS attacks by comparing the mean value entropy with average alarm threshold. Simulation results demonstrate that the proposed method remarkably improves the abilities of prediction and detection of DDoS attacks. Meanwhile, a novel framework of performance evaluation further proves that the proposed algorithm has better generalization ability and superior performance in terms of less algorithm execution time, average iterations, average relative variance and root mean square error.
INTRODUCTION
Particle Swarm Optimization (PSO) is a random population based optimization algorithm and has wide range of applications (Kuok et al., 2010; Yang et al., 2009) but the disadvantages that need to be improved such as premature convergence, inferior global optimization ability and slow convergence rate are sometimes occurred in the actual application of PSO algorithm. The evolutionary model of Quantum-behaved Particle swarm Optimization (QPSO) which is proposed by Sun et al. (2004) and Coelho (2008) can expand in a better global search space and outperform PSO in terms of evolution equation, control parameters and convergence speed.
Although, the QPSO algorithm has more superior performance, it exposes problems in iterative operations such as premature. The expansion-contraction coefficient which is the only parameter for controlling the convergence speed of particles in QPSO will be linearly decreasing so that it cannot adapt to the complex and nonlinear optimization process (Huang et al., 2012; Zhang et al., 2005). On one hand, with using the linear regressive strategy to reflect the actual optimization search process will make the algorithm run into premature convergence. On the other hand, the changes in the value of expansion-contraction coefficient only have linearly associated with the iterations but not reflect change states of the swarm.
Point to the conditions above, in this study the EAQPSO algorithm is proposed to improve the classical QPSO algorithm with introducing the Evolution Speed Factor (ESF) and Aggregation Degree Factor (ADF) for implementing the self-adaption of expansion-contraction coefficient. Meanwhile, the hybrid entropies strategy which is applied into EAQPSO-SVM model can better optimize the performance of DDoS attacks prediction and detection.
RELEVANT TECHNOLOGIES
Theory of support vector machine (SVM) algorithm: The main idea of SVM which overcomes the deficiency of the neural network is using a linear model to separate the sample sets through some nonlinear mapping from the input vectors into the high dimensional feature space (Bernhard, 2000; Cristianini and Shawe-Taylor, 2000; Kecman, 2001), structuring Optimal Separate Hyper-plane (OSH) that provides the minimum number of training errors (Vapnik, 1995) in the high dimensional feature space. SVM method finds the OSH which is subject to f (x) = ω.x+b by quadratic programming (QP) method to solve the following optimization problems. Supposing the training set is:
| (1) |
where, xi denotes an input vector and yi denotes a label which determines the class of xi. Parameter n denotes the max number of the input vectors. Given the kernel function K and sample training set D defined in relations (1). A global optimal solution is proposed to meet the QP problem described as follows:
| • | Minimize: |
| (2) |
| • | Subject to: |
| (3) |
where, C denotes the error penalty factor which controls the tradeoff between the training errors. ξi represents the non-negative slack variables, ω represents the vector of OSH and b is the offset of OSH. Combining Eq. 2 with 3, Lagrange duality method is introduced to solve the global optimal solution with Karush-Kuhn-Tucker (KKT condition), the nonlinear decision function is defined as follows:
| (4) |
where, αi≥0 ,μi≥0, parameters αi and μi are Lagrange multipliers, KKT condition should meet the following relations:
| (5) |
In Eq. 5, αi meets the following inequalities:
The nonlinear SVM maps the training samples from the original finite dimensional space into a higher dimensional feature space by the Kernel function K (x, xi) whose value is equal to the inner product function φ (x). φ(xi) of the two vectors x and xi in the original feature space. The optimal decision-making function can be written as:
| (6) |
| (7) |
where C denotes the error penalty factor and parameter σ denotes the kernel width of Gaussian radial basis function (RBF). Choosing the proper value of C can regulate the fiducial interval range of learning machine and the empirical risk proportion in order to make learning machine have the best generalization ability and outreach capacity. Kernel function parameter σ can influence the distribution complexity of sample data in high dimensional feature space. As to the analysis above, we come to the conclusion that C and σ are the main factors for influencing the classification accuracy and efficiency of SVM algorithm.
Quantum-behaved particle swarm optimization (QPSO) algorithm: QPSO algorithm which is based on quantum mechanics was proposed by Sun to make an improvement in global searching ability and fast convergence of PSO algorithm. QPSO outperforms PSO in terms of evolutionary method (particle position updating method), global searching capability and searching space. In the traditional PSO algorithm, particles just move in a restricted area with limited searching range, PSO has the shortcoming of local optimal solution. However, particles can make movements with a certain probability in any position of whole searching space in the QPSO algorithm which is applied in the field of multi-objective optimization. Take N particles in R-dimensional searching space for example, each dimension position of the i-th (1 = i = N) particle could generate a potential well to attract other particles in the movement around the attracting factor Pi,j (t), it’s in accordance with the following location of the evolution equation:
| (8) |
where, N denotes the scale of particle swarm, integer i = {1, 2, ..., N} denotes the number of swarm and integer j = {1, 2,...,R} denotes the number of j-th dimensional searching space. Parameter pbestid denotes the best position of the particle in its flying course and gbestd represents the best position of the whole swarm. The learning parameters c1, c2 and r1(i,j)(t), r2(i,j)(t) are the uniformly distributed random numbers in the interval of [0,1], in other words, they meet r1(i,j) (t)~U (0, 1), r2(i,j)(t)~U (0, 1). The Eq. 8 could be evolved into the following:
| (9) |
According to Eq. 9, when the parameter c1 is equals to c2, ni,j (t) will meets ni,j(t)~U (0, 1). Supposing each particle has a quantum behavior, the following evolution formulas are used to update the position of particles in order to make every particle aggregation and converge to the attracting factor (Pant et al., 2008; Ma et al., 2008; Yang and Meng, 2012; Liu and Ma, 2011). In:
| (10) |
| (11) |
where, the parameter mbest (Mean Best Position) denotes the central point of the best position among the whole swarm. pid is the random point of interval of pbestid and gbestd. The parameters ui,j (t) is uniformly distributed random numbers in the interval of [0, 1]. β is the expansion-contraction coefficient (CE) which is an only parameter for controlling the convergence speed of particles in QPSO; “±” in Eq. 10 is decided randomly in the iteration process of the algorithm. The particles move to meet the following iterative equation:
| (12) |
The CE can be calculated in the l-th iteration is defined as (Li et al., 2012):
| (13) |
Given the parameters βmax∈β(t) and βmin∈β(t) are, respectively denotes the maximum and minimum values of CE, where β (t) is the distributed random numbers which is in the interval of [0.4, 0.9], Imax denotes the maximum iteration number.
Novel EAQPSO algorithm: As discussed in the previous section, the selection and control of CE will affect the convergence efficiency of QPSO algorithm, the simulation experimental results in Sun et al. (2005, 2006a) show that when the value of CE meets β<1.782, the improved particle swarm algorithm based on constriction factors can guarantee the constringency of the algorithm, while the restriction of velocity can be released. On the contrary, if β = 1.8, the particle swarm will be divergence. Sun et al. (2006b) and Chen et al. (2012) illustrates that the QPSO algorithm is inevitably descending into prematurity convergence. In order to improve the global searching performance of QPSO algorithm so that avoiding algorithm falling into local extreme value point, this study proposed an improved QPSO algorithm with introducing the evolution speed factor (ESF) ΔESF and aggregation degree factor (ADF) ΩADF (Coelho, 2008; Guo et al., 2006; Yang et al., 2007).
Based on the characteristics of QPSO algorithm, global optimum which reflects the movements of each particle depends on the changes of individual optimal values. In the process of iteration, the (T+1)-th global optimum gbestT is always better than or at least equals to the T-th global optimum gbestT. According to the optimization objective of searching for maximum Global Optimum (GOmax) or minimum Global Optimum (GOmin), ΔESF and the evolution speed Vevo is defined using the following equation:
| (14) |
| (15) |
Combining Eq. 14 with 15, the evolution speed factor ΔESF can be described as follows:
| (16) |
wherem F (gbestiT) and F (gbestiT+1) respectively denote the T-th and (T+1)-th iterations’ fitness values of i-th particle. Under the assumption and definition in Eq. 7-9, ΔESF∈(0, 1]. When ΔESF→0, Vevo will evolve faster. After several iterations, when ΔESF→1, it comes to the conclusion that the algorithm will be terminated and generated the optimal solution.
The aggregation degree of particle is another important influence factor of
QPSO algorithm, the global optimal fitness value F (gbest)best is
always superior to F (gbestiT).
| (17) |
During the process of optimization in searching for GOmax or GOmin, aggregation degree factor (ADF) ΩADF can be defined as the following equation:
| (18) |
| (19) |
Combining Eq. 18 with 19, the Aggregation Degree Factor (ADF) ΩADF is described as follows:
| (20) |
By the analysis of Eq. 17-20, the aggregation degree factor ΩADF meets ΩADF→(0, 1], it also reflects the diversity and the aggregation degree of the particle swarm. In other word, the larger value of ΩADF which meets ΩADF→1 indicates the higher aggregation degree and the smaller diversity of swarm. When ΩADF achieves ΩADF = 1, each particle of the swarm has the identity. With the changes of the evolution degree factor values, every particle makes movements to close to or away from the optimal position, it means that the searching space of each particle is constantly changing.
This study designed a self-adaptive algorithm called EAQPSO to improve QPSO algorithm. The particle is closed to the current optimal position, EAQPSO will increase the value of β to expand the global searching space of particles for avoiding falling into the local optimal solution. While the particle is far away from the optimal position, the value of β should be decreased to limit the searching space of particles for convergence. The EAQPSO algorithm with self-adaptive expansion-contraction coefficient is defined as follows:
| (21) |
| (22) |
| (23) |
where β0 which meets β0 = 1 is the initial value of CE, the values of β1 and β2 typically meets the condition of β1 ∈[0, 1] and β2∈(0, 1]. Under the initial conditions, (ΔESF)init = (ΩADF)init = 0, the EAQPSO optimization steps are described as follows:
| • | Step 1: Initialize the values of x0init(t), pbestidinit, gbestdinit, mbestinit, ni,jinit(t) and Calculate the F (gbest)init |
| • | Step 2: Initialize the values of (β1)init and (β2)init |
| • | Step 3: If the EAQPSO is terminated at the maximum number of iterations Imax, algorithm goes into Step 7. Otherwise follows Step 4 |
| • | Step 4: Compare the global optimal value with the former one, then update the velocity and position of the whole swarm based on Eq. 10-13 if the current is better, recalculate the F (gbest) and update mbest |
| • | Step 5: According to Eq. 14-20, the parameters ΔESF and ΩADF can be determined. β (t) is calculated based on Eq. 21-23 |
| • | Step 6: The current number of iterations meet iter++ |
| • | Step 7: Output the global optimal position value, algorithm is terminated |
DDoS DETECTION BASED ON EAQPSO-SVM ALGORITHM
In general, network flow will not change greatly in a short period under the normal circumstances. Yu and Li (2012) defined the discrete packets’ set as the detecting data source of DDoS attack, the set is described in Definition 1.
Definition 1: Discrete packets’ set is P = {p[1], … , p[i], …, p[R]}, characteristics’ set of i-th packet is defined to be p[i] = {SPort[i], DPort[i], SIP[i], DIP[i], Type[i]}:
| • | SPORT[i]: | Source port of p[i] |
| • | DPORT[i]: | Destination port of p[i] |
| • | SIP[i]: | Source IP address of p[i] |
| • | DIP[i]: | Destination IP address of p[i] |
| • | Type[i]: | The type of p[i] |
where, integer i denotes current packet number, integer R denotes the maximum packet number, packet array p [i] denotes the number of captured i-th packet.
This study is focus on the collected network flows that are divided into five sub-populations with the same characteristic defined in Definition 1 as the data source of DDoS attack detection. The Entropy methods can well distinguish the changes of network flows in a short period so that accurately detecting external unknown DDoS attacks (Yu and Li, 2012, 2013). The study adopts the hybrid entropy method proposed in (Yu and Li, 2013) to verify the performance of the EAQPSO-SVM algorithm.
Definition 2: Suppose the information entropy value is H(t), Rényi entropy value as Hα(t). The two kinds of entropy equations are, respectively defined as follows:
| (24) |
| (25) |
where, p (t) denotes the distribution of probabilities of packet characteristics,
parameter α denotes order of the Rényi probability distribution.
The initial captured packets are classified by the same characteristics of SIP/SPORT/DIP/DPORT.
Then divided the classified packets into different arrays. EAQPSO-SVM algorithm
can be used in selecting and training the optimal samples for DDoS attacks detection.
Combining Eq. 24, 25, the mean value entropy
| (26) |
where, H’(t) and Hα’(t) respectively denotes the first derivatives of H(t) and Hα(t).
The studies in Yu and Li (2012, 2013) and Oshima et al. (2010) revealed that when the target host suffers from large scale abnormal attacks, it induces the much steeper change of network flows. The values of will be sharply fluctuated.
Definition 3: The parameter HHHH is defined as the Average Alarm Threshold (AAT) which meets the following relationship between mean value entropy:
| (27) |
| (28) |
where, integer n denotes the total numbers of alarm tests, the parameter l denotes obviously abnormal values which are picked out as the invalid alarm threshold. Integer ii (1= ii = n-l) denotes ii-th alarm threshold test.
The three hundred test times were tested before the simulation experiment starts, eleven times obviously abnormal test values are picked out and the alarm threshold of DDoS attacks is described in Eq. 27, 28 is described as follows:
| (29) |
| (30) |
By using the arithmetic developed from EAQPSO and SVM theories, the former algorithm could better optimize the error penalty factor C meets C∈[10-2, 103] and kernel parameter σ meets σ∈[10-3, 102], the EAQPSO-SVM optimization steps are shown as follows:
| • | Step 1: Data preparation – Collect the network flows at detection server. Capture and classify the data packets due to the different features –SIP/SPORT/ DIP/DPORT. Then put above classified packets into respective arrays |
| • | Step 2: Initialization of characteristic packets-Initialize the classified packets as training sample |
| • | Step 3: EAQPSO optimization-Execute by the EAQPSO optimization steps mentioned in Section 2 |
| • | Step 4: Search optimum-Find the optimal values of parameter C and σ for SVM training the DDoS attack flows |
| • | Step 5: Algorithm terminated-Finish loop and end the optimizing and training procedures |
APPLICATION EXAMPLES AND ANALYSIS OF EXPERIMENTAL RESULTS
Settings of experimental deployment environment: The source data samples of simulation experiment are produced from the different Vlans of South Central University for Nationalities and DDoS detection module is deployed in the data center network (DCN). Figure 1. depicts the network topological structure of DCN.
The network topology structure of DDoS attacks detection simulation experiment is described in Fig. 2.
| Fig. 1: | Network topology structure of DCN |
| Fig. 2: | Network topology structure of DDoS attacks detection simulation experiment |
As shown in Fig. 1, 2, data source is generated from the computer terminals of Vlan1-3, the network attacking flows were collected by the data collecting server which was used to synchronize real-time data with DdoS detection server in DdoS detection module. Simulation experiment is carried out by the Libsvm v2.91 and performed based on Cisco UCS VMware with the configuration of “Intel(R) Xeon(R) E5620 2.40 GHz Duo Core CPU and 4.0G DIMM”.
Simulation experiment parameters: The parameters of EAQPSO-SVM algorithm in the study is set as: The total size of swarm meets N = NI + NII, NI is the detection particle arrays NI = 70, NII is the prediction test particle arrays NII = 60. The maximum iterations Imax = 100, the initial value of CE meets β0 = 0, (ΔESF)init = (ΩADF)init = 0. According to the experiments in Huang et al. (2012), the DCWQPSO algorithm will have the best performance with β1 [0.40, 0.60], set β1=0.5, β2∈[0.05, 0.20], set β2 = 0.2. In study algorithm, we define the same configuration with β1 = 0.5 and β2 = 0.2.
| Fig. 3(a-d): | (a) SIP detection of DDoS attacks, (b) SPORT detection of DDoS attacks, (c) DIP detection of DDoS attacks and (d) DPORT detection of DDoS attacks |
After EAQPSO-SVM optimized, the optimal SVM training parameters are C = 29.6322, σ = 0.1429.
Simulation results and analysis: Simulation experiments based on EAQPSO-SVM
algorithm are carried out in Fig. 2. The results are shown
in Fig. 3a-d that present the
Based on the analysis of prediction test particle arrays in 88~125 training periods, the results of Fig. 3a prove that the accuracy of SIP detection of DDoS attacks is 92.11%±γ, Fig. 3b shows the accuracy of SPORT detection of DDoS attacks is 94.74%±γ, Fig. 3c shows the accuracy of DIP detection of DDoS attacks is 93.62%±γ, Fig. 3d shows the accuracy of DPORT detection of DDoS attacks is 94.23%±γ. The parameter γ which meets γ = 0.05% is used to revise the predictive deviation in simulation experiments.
Framework of performance evaluation: This study introduces the generalization ability which is used to measure a difference in predictive values and measured values to evaluate the performance of the proposed algorithm. Average Relative Variance (ARV) is adopted to determine the intensity of generalization ability, equation is shown as follows (Cholewo and Zurada, 1997):
| (31) |
where, integer W denotes the number of prediction samples, x (jj) denotes the
real value,
| (32) |
According to Eq. 31, 32, the performance comparison results of QPSO, DCWQPSO and EAQPSO are shown in Table 1.
| Table 1: | Performance comparisons of QPSO, DCWQPSO and EAQPSO algorithm |
From the comparisons in Table 1, it comes to the conclusion that EAQPSO algorithm has better generalization ability and superior performance in terms of less algorithm execution time, average iterations, ARV and RMSE.
CONCLUSION
The methodology of EAQPSO based on SVM theory has been presented in this study as a solution to the problem of DDoS attacks prediction and detection, its effectiveness has been tested by being applied in DCN of South Central University for Nationalities with many simulation experiments. On one hand, improved QPSO which is based on the evolution speed factor and aggregation degree factor makes the EAQPSO with self-adaptive mechanism so that avoiding falling into premature. On the other hand, introducing the entropy method into the algorithm guides DDoS attacks prediction and detection with AAT fluctuation. Simulation results show that the proposed method posses the traits of accuracy, high efficiency and superior generalization ability.
ACKNOWLEDGMENTS
This study was supported by the Special Fund for Basic Scientific Research of Central Colleges, South-Central University for Nationalities (CZY13015) and the National Natural Science Foundation of China (61103248).