[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

An efficient intrusion detection technique based on support vector machine and improved binary gravitational search algorithm

  • Published:
Artificial Intelligence Review Aims and scope Submit manuscript

Abstract

‘Curse of Dimensionality’ and the trade-off between high detection rate and less false alarm rate make the design of an efficient and robust Intrusion Detection System, an open research challenge. In this way, we present Hyper Clique—Improved Binary Gravitational Search Algorithm based Support Vector Machine (HC-IBGSA SVM), an efficient and adaptive intrusion detection technique to improve the performance of SVM in terms of detection rate and false alarm rate. HC-IBGSA SVM employs hyper clique property of hypergraph, novel mutation operator, and Newton–Raphson inspired position update function to fasten the search for an optimal solution and to prevent premature convergence. Further, HC-IBGSA uses a weighted objective function to maintain the trade-off between maximizing detection rate and minimizing the false alarm rate and the optimal number of features. The experimental evaluations were carried out using two benchmark intrusion datasets, namely NSL-KDD CUP dataset and UNSW-NB15 dataset under two scenarios (1) SVM trained with all features, and (2) SVM trained with the optimal feature subset and model parameters obtained from HC-IBGSA in terms of various quality metrics, stability analysis and statistical test.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

Download references

Acknowledgements

This work was supported by The Ministry of Electronics and Information Technology, India; Department of Science and Technology (SR/FST/ETI-349/2013), India; TATA Realty—SASTRA Srinivasa Ramanujan Research Cell, India (Grant No: AAA-22/7/2018-CSRD-MeitY, MRT/2017/000155, SR/FST/MSI-107/2015).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to V. S. Shankar Sriram.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

1.1 A The convergence of improved binary gravitational search algorithm

To prove the convergence of the improved binary gravitational search algorithm, the position of the agents or objects \( \left( {x_{i} } \right) \) has to the traced analytically by considering its interaction with other objects of the same generation along with its time varying parameters and random characteristics. The convergence of the IBGSS can be proven mathematically, if \( \lim_{t \to \infty } x_{i}^{t} = A, \) where A is the constant i.e. \( \lim_{t \to \infty } \left( {x_{i}^{t + 1} - x_{i}^{t} } \right) = 0 \). The convergence proof as follows (Farzaneh Ghorbani 2012).

Theorem A.1

Let us consider two real valued functions\( x^{t} \)and\( y^{t} \)such that for few values of\( N > 0, \left| {x^{t} } \right| < N \)and\( \lim_{t \to \infty } y^{t} = 0 \). Hence, we can conclude that\( \lim_{t \to \infty } x^{t} y^{t} = 0 \).

Proof

Let \( \varepsilon > 0, \) then there exist \( T > 0\left| {\forall t} \right\rangle T \quad {\text{and}}\quad \left| {y^{t} } \right| < \frac{\varepsilon }{N} \). Hence, \( \forall t > T \).

$$ x^{t} y^{t} < \frac{{\left( {N*\varepsilon } \right)}}{N} = \varepsilon $$
(A.1)

Theorem A.2

Let us consider\( \lim_{t \to \infty } G^{t} = 0 \), then\( \lim_{t \to \infty } \left( {x_{i}^{t + 1} - x_{i}^{t} } \right) = 0 \).□

Proof

From Eq. (6), we can state that \( (R_{ij} + \varepsilon ) > x_{j}^{t} - x_{i}^{t} \), which implies,

$$ \frac{{\|x_{j}^{t} - x_{i}^{t} \|}}{{(R_{ij} + \varepsilon )}} < 1 $$
(A.2)

Similarly, from Eq. (4), we conclude that,

$$ M_{j}^{t} \ge 0 \quad {\text{and}}\quad \mathop \sum \limits_{j = 1}^{k } M_{j}^{t} = 1 $$
(A.3)

For the general case, \( M_{j}^{t} \) can be rewritten as \( \sum\nolimits_{j = 1}^{k } {M_{j}^{t} = L > 0} \)

From Eq. (A.2), we derive the following equation,

$$ \left| {\mathop \sum \limits_{j = 1,j \ne i}^{k} \left(r_{j} M_{j}^{t} \left( {\frac{{x_{j}^{t} - x_{i}^{t} }}{{(R_{ij} + \varepsilon )}}} \right)\right)} \right| \le \left|\mathop \sum \limits_{j = 1,j \ne i}^{k} M_{j}^{t} \left( {\frac{{x_{j}^{t} - x_{i}^{t} }}{{(R_{ij} + \varepsilon )}}} \right)\right| < \mathop \sum \limits_{j = 1,j \ne i}^{k} M_{j}^{t} < \mathop \sum \limits_{j = 1}^{k} M_{j}^{t} < K $$
(A.4)

Since we consider only the \( K_{best} \) particles, Eq. (A.4) can be modified as follows,

$$ \begin{aligned} & \left| \mathop \sum \limits_{{j \in K_{best} ,j \ne i}}^{k} \left(r_{j} M_{j}^{t} \left( {\frac{{x_{j}^{t} - x_{i}^{t} }}{{(R_{ij} + \varepsilon )}}} \right)\right) \right|\le \left| \mathop \sum \limits_{{j \in K_{best} ,j \ne i}}^{k} M_{j}^{t} \left( {\frac{{x_{j}^{t} - x_{i}^{t} }}{{(R_{ij} + \varepsilon )}}} \right)\right| \\ & < \mathop \sum \limits_{{j \in K_{best} ,j \ne i}}^{k} M_{j}^{t} < \mathop \sum \limits_{j = 1,j \ne i}^{k} M_{j}^{t} < \mathop \sum \limits_{j = 1}^{k} M_{j}^{t} < K \\ \end{aligned} $$
(A.5)

From Eq. (A.5) and Theorem A.1, we conclude that \( \lim_{t \to \infty } a_{i}^{t} = 0 \).

Form the Eq. (8),

$$ a_{i}^{t} = v_{i}^{t + 1} - r_{i} v_{i}^{t} $$
(A.6)

Applying limits for Eq. (A.6), we get,

$$ \mathop { \lim }\limits_{t \to \infty } a_{i}^{t} = \mathop { \lim }\limits_{t \to \infty } \left( {v_{i}^{t + 1} - r_{i} v_{i}^{t} } \right) $$
(A.7)

Further rearranging Eq. (A.7), we get,

$$ \mathop { \lim }\limits_{t \to \infty } a_{i}^{t} = \mathop { \lim }\limits_{t \to \infty } \left( {\left( {1 - r_{i} } \right)v_{i}^{t} } \right) $$
(A.8)

Using Eq. (A.8), we get \( { \lim }_{t \to \infty } \left( {\left( {1 - r_{i} } \right)v_{i}^{t} } \right) = 0 \).

As \( r_{i} \) is uniformly distributed in a range of [0,1], it cannot converge to 0 since it is independent of t. Hence \( { \lim }_{t \to \infty } \left( {v_{i}^{t} } \right) = 0 \).

Similarly, for case 1 in Eq. (12), i.e., \( rand > \frac{{Tanh\left( {V_{i}^{t + 1} } \right)}}{{{\text{sech}}^{2} \left( {V_{i}^{t + 1} } \right)}} \)

$$ v_{i}^{t + 1} = x_{i}^{t + 1} - \bar{x}_{i}^{t} $$
(A.9)

Applying limits on Eq. (A.9), we get,

$$ \mathop { \lim }\limits_{t \to \infty } v_{i}^{t + 1} = \mathop { \lim }\limits_{t \to \infty } \left( {x_{i}^{t + 1} - \bar{x}_{i}^{t} } \right) = 0 $$
(A.10)

Similarly, for case 2 in Eq. (11), i.e., \( rand > \frac{{Tanh\left( {V_{i}^{t + 1} } \right)}}{{{\text{sech}}^{2} \left( {V_{i}^{t + 1} } \right)}} \)

$$ v_{i}^{t + 1} = x_{i}^{t + 1} - x_{i}^{t} $$
(A.11)

Applying limits on Eq. (A.11), we get,

$$ \mathop { \lim }\limits_{t \to \infty } v_{i}^{t + 1} = \mathop { \lim }\limits_{t \to \infty } \left( {x_{i}^{t + 1} - x_{i}^{t} } \right) = 0 $$
(A.12)

Therefore, we can state that either \( \bar{x}_{i}^{t} \quad {\text{or}}\quad x_{i}^{t} \) is a convergent sequence and agents in IBGSA convergence to a stable point. □

1.2 B Time and computational complexity of IBGSA

In standard BGSA and IBGSA, the process that incurs computational cost are (1) Initialization \( \left( {T_{Ini} } \right) \) (2) Fitness computation \( \left( {T_{Fit} } \right) \) (3) Acceleration computation \( \left( {T_{Acc} } \right) \) (4) Velocity and position updation \( \left( {T_{Upa} } \right) \). The overall computational cost of BGSA is defined as in Eq. (B.1)) (Zhang et al. 2018).

$$ \begin{aligned} C_{Tot} & = T_{Ini} + \left( {T_{Fit} + T_{Acc} + T_{Upa} } \right)*Gen_{Max} \\ & = \left( {2*n*PoP_{Max} } \right) + \left( {3*n*PoP_{Max} *Gen_{Max} } \right) \\ & \quad + \left( {n*PoP_{Max}^{2} *Gen_{Max} } \right) \\ \end{aligned} $$
(B.1)

Similarly, the time complexity is given in Eq. (B.2))

$$ T_{Tot} = \left( {n*PoP_{Max}^{2} *Gen_{Max} } \right) $$
(B.2)

However, in IBGSA, the hyper clique property was introduced in the initialization phase that reduces the dimension of search space from \( n \) to \( n^{\prime} \) such that \( n^{{\prime }} \ll n \). The overall computational cost \( \left( {C_{Tot }^{{\prime }} } \right) \) and time complexity \( \left( {T_{Tot}^{{\prime }} } \right) \) of IBGSA are given in Eqs. (B.3) and (B.4).

$$ C_{Tot }^{{\prime }} = \left( {2*n^{{\prime }} *PoP_{Max} } \right) + \left( {3*n^{{\prime }} *PoP_{Max} *Gen_{Max} } \right) + \left( {n^{{\prime }} *PoP_{Max}^{2} *Gen_{Max} } \right) $$
(B.3)
$$ T_{Tot}^{{\prime }} = n^{{\prime }} *PoP_{Max}^{2} *Gen_{Max} $$
(B.4)

From Eqs. (B.1) to (B.4), it is clear that \( C_{Tot }^{{\prime }} \ll C_{Tot} \) and \( T_{Tot}^{{\prime }} \ll T_{Tot} \). An important point to note is that we introduce mutation operator in the updation process when there exists a conflict, and therefore, it has the least impact on the time and computational complexity.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gauthama Raman, M.R., Somu, N., Jagarapu, S. et al. An efficient intrusion detection technique based on support vector machine and improved binary gravitational search algorithm. Artif Intell Rev 53, 3255–3286 (2020). https://doi.org/10.1007/s10462-019-09762-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10462-019-09762-z

Keywords

Navigation