Using SVM and Clustering Algorithmsin IDS Systems

Peter Scherer, Martin Vicher, Pavla Drázdilová, Jan Martinovic, Jiri Dvorský, Václav SnáselDATESO 2011

TL;DR

This paper explores the effectiveness of Support Vector Machines (SVM) and various clustering algorithms (K-means, Farthest First Traversal, COBWEB/CLASSIT) for improving intrusion detection systems (IDS). The authors found that SVM, particularly with an RBF kernel, achieved the highest average accuracy, significantly outperforming clustering methods in detecting network attacks.

What Problem Does This Paper Address?

Intrusion Detection Systems (IDS) are crucial for maintaining the security of computer systems by monitoring network traffic for malicious activities. While various machine learning techniques have been applied to IDS, there's a continuous need to improve their accuracy and efficiency in identifying diverse types of network attacks. This paper investigates how combining clustering algorithms with SVM can enhance the detection capabilities of IDS, aiming to improve accuracy by leveraging the strengths of both approaches.

Methods

The study evaluates several machine learning algorithms for IDS:

  • Clustering Algorithms:
    • K-means: A partitional clustering algorithm that aims to partition data into a pre-defined number of clusters (K).
  • Farthest First Traversal (FFT): Another partitional clustering algorithm that iteratively selects cluster centers based on their dissimilarity to existing centers.
  • COBWEB/CLASSIT: An incremental conceptual clustering algorithm that builds a hierarchical structure of clusters.
  • Classification Algorithm:
    • Support Vector Machine (SVM) type 1 (C-SVM): A powerful supervised learning algorithm for binary classification, particularly effective for linear and non-linear data separation. The paper discusses its underlying principles, including hyper-plane separation, margin maximization, slack variables, and the use of kernels (linear, polynomial, RBF, sigmoid) to handle non-linear data.

The authors also explored the optimization of these algorithms using KD-trees to potentially speed up training and improve search efficiency.

Datasets

The experiments utilized data prepared by the Agency DARPA intrusion detection evaluation program in 1998 from MIT Lincoln Labs. The dataset consisted of five pairs of learning and testing sets, each corresponding to a specific type of network attack. Each data instance (vector) comprised 42 attributes, with the first 41 being features describing network traffic and the 42nd attribute indicating the type of network attack. For testing, the attack type attribute was neglected, and the focus was on classifying the network traffic vectors.

Key Insights and Ideas

  • SVM's Superiority in Attack Detection: SVM, especially with an RBF kernel, demonstrated significantly higher accuracy in classifying network attacks compared to the tested clustering algorithms. This highlights SVM's robustness in distinguishing complex attack patterns from normal traffic.
  • Clustering as a Preprocessing Step: While clustering algorithms alone did not achieve the same accuracy as SVM, they could potentially serve as a preprocessing step or be used in conjunction with SVM for more nuanced detection.
  • Kernel Choice Matters for SVM: The choice of kernel function for SVM had a noticeable impact on performance, with the RBF kernel yielding the best results in this study.
  • KD-tree Optimization: The use of KD-trees showed a significant reduction in training time for the Farthest First Traversal algorithm, almost halving it. However, for K-means, the benefit was less pronounced, and in some cases, it even increased training time due to overhead.
  • Parameter Tuning is Crucial: For both SVM and COBWEB/CLASSIT, careful selection of parameters (like C and γ for SVM, and Acuity and Cutoff for COBWEB/CLASSIT) was essential for achieving optimal performance.

Key Results

  • Highest Accuracy: The SVM algorithm using the RBF kernel achieved the highest average success rate of 99.846%.
  • SVM Performance: Across different kernels, SVM achieved an average accuracy of 99.722% (linear), 99.266% (polynomial), 99.846% (RBF), and 99.754% (sigmoid).
  • Clustering Performance:
    • K-means achieved the best average accuracy among clustering algorithms at 98.998%.
  • Farthest First Traversal (FFT) achieved an average accuracy of 92.128%.
  • COBWEB/CLASSIT achieved an average accuracy of 91.228%.
  • Training Time: Training times varied significantly. SVM generally had faster training times compared to clustering algorithms, especially for COBWEB/CLASSIT, which was considerably slower. KD-tree optimization reduced FFT training time by nearly half.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that selecting the best parameters for COBWEB/CLASSIT (Acuity and Cutoff) was done manually and is not an automated process.
  • The study focused on a specific dataset from 1998, which might not fully represent current network attack landscapes.
  • Future Work:
    • Investigate other kernel functions for SVM to further improve attack prediction.
  • Explore SVM parallelization for faster training on large datasets.
  • Optimize clustering algorithms further.
  • Compare these methods on other document collections to assess generalizability.
  • Investigate combining SVM with other clustering algorithms or using clustering as a preprocessing step for SVM.

Summary updated

BibTeX
@inproceedings{scherer2011using,
  author = {Peter Scherer and Martin Vicher and Pavla Drázdilová and Jan Martinovic and Jiri Dvorský and Václav Snásel},
  title = {{Using SVM and Clustering Algorithmsin IDS Systems}},
  booktitle = {DATESO},
  year = {2011},
}
Figure