Improving anomaly detection in BGP time-series data by new guide features and moderated feature selection algorithm

  The Internet infrastructure relies on the Border Gateway Protocol (BGP) to provide essential routing information where abnormal routing behavior impairs global Internet connectivity and stability. Hence, employing anomaly detection algorithms is important for improving the performance of BGP routing protocol. In this paper, we propose two algorithms; the first is the guide feature generator (GFG), which generates guide features from traditional features in BGP time-series data using moving regression in combination with smoothed moving average. The second is a modified random forest feature selection algorithm which is employed to automatically select the most dominant features (ASMDF). Our mechanism shows that the detected anomalies are more realistic and the selected features are generally consistent across time series. Experimental evaluations using multiple machine learning models reveal that the proposed algorithms achieve up to 32.36 % improvement in accuracy rate, up to 35.44 % reduction in false negative rate, and up to 43.99 % reduction in false positive rate compared to not using these algorithms. Moreover, the ASMDF option increases the feature selection speed more than 3 times compared to most existing feature selection algorithms.

___

  • Al-Musawi B, Branch P, Armitage G. BGP anomaly detection techniques: a survey. IEEE Commun Surv Tut 2017; 19: 377-396.
  • Ho TK. The random subspace method for constructing decision forests. IEEE T Pattern Anal 1998; 20: 832-844.
  • Sidorov G, Gelbukh A, Gómez-Adorno H, Pinto D. Soft similarity and soft cosine measure: similarity of features in vector space model. Computación y Sistemas 2014; 18: 491-504.
  • Chandola V, Banerjee A, Kumar V. Anomaly detection: a survey. ACM Comput Surv 2009; 41: 1-58.
  • Hajji H. Statistical analysis of network traffic for adaptive faults detection. IEEE T Neural Networ 2005; 16: 1053-1063.
  • Thottan M, Liu G. Anomaly detection approaches for communication networks. In: Cormode G, Thottan M, editors. Algorithms for Next Generation Networks. London, UK: Springer, 2010. pp. 239-261.
  • Tan P, Steinbach M, Kumar V. Introduction to Data Mining. 1st ed. Boston, MA, USA: Addison-Wesley, 2005.
  • Augusteijn M, Folkert B. Neural network classification and novelty detection. Int J Remote Sens 2002; 23: 2891-2902.
  • Diaz I, Hollmen J. Residual generation and visualization for understanding novel process conditions. In: IEEE IJCNN’02 Neural Networks Conference; 12–17 May 2002; Honolulu, HI, USA. New York, NY, USA: IEEE. pp. 2070-2075.
  • Sharma O, Girolami M, Sventek J. Detecting worm variants using machine learning. In: Proceedings of CoNEXT Conference; 10–13 December 2007; New York, NY, USA. New York, NY, USA: ACM. pp. 1-12.
  • Moore A, Zuev D. Internet traffic classification using Bayesian analysis techniques. In: Proceedings Conference on Measurement and Modeling of Computer Systems; 6–10 June 2005; Alberta, Canada. New York, NY, USA: ACM. pp. 50-60.
  • El-Arini K, Killourhy K. Bayesian detection of router configuration anomalies. In: Proceedings of Workshop on Mining Network Data; 26 August 2005; Philadelphia, PA, USA. New York, NY, USA: ACM. pp.221-222.
  • Wubbeling M, Elsner T, Meier M. Inter-AS routing anomalies: improved detection and classification. In: IEEE 6th International Conference On Cyber Conflict; 3–6 June 2014; Tallinn, Estonia. New York, NY, USA: IEEE. pp. 223-238.
  • Deshpande S, Thottan M, Sikdar B. Early detection of BGP instabilities resulting from Internet worm attacks. In: IEEE GLOBECOM’04 Global Telecommunications Conference; 29 November–3 December 2004; Dallas, TX, USA. New York, NY, USA: IEEE. pp. 2266-2270.
  • Bilski T. Disaster’s impact on Internet performance – case study. In: Bilski T, editor. Communications in Computer and Information Science. Heidelberg, Germany: Springer, 2009. pp. 210-217.
  • Makridakis G, Wheelwright C, Hyndman J. Forecasting: Methods and Applications. 3rd ed. New York, NY, USA: Wiley, 1997.
  • Cohen J, Cohen P, West G, Aiken S. Applied Multiple Regression Correlation Analysis for the Behavioral Sciences. 3rd ed. Mahwah, NJ, USA: Lawrence Erlbaum Associates, 2003.
  • Draper R, Smith H. Applied Regression Analysis. 3rd ed. New York, NY, USA: Wiley, 1998.
  • Ladha L, Deepa T. Feature selection methods and algorithms. International Journal on Computer Science and Engineering 2011; 3: 1787-1797.
  • Strobl C, Malley J, Tutz G. An introduction to recursive partitioning: rationale, application and characteristics of classification and regression trees, bagging and random forests. Psychol Methods 2009; 14: 323-348.
  • Weibo L, Zidong W, Xiaohui L, Nianyin Z, Yurong L, Alsaadi F. A survey of deep neural network architectures and their applications. Neurocomputing 2017; 234: 11-26.
  • Jundong L, Kewei C, Suhang W, Fred M, Robert P, Jiliang T, Huan L. Feature selection: a data perspective. ACM Comput Surv 2010; 9: 1-45.