A scalable, efficient and informative approach for anomaly-based intrusion detection systems: theory and practice

In this paper, we present the design and implementation of a new approach for anomaly detection and classification over high speed networks. This approach is efficient in terms of its scalability, the anomaly detection delays and its ability not only to detect an anomaly but also to provide detailed and accurate information about the ongoing attack (attack type, IP addresses, port numbers, etc.). The proposed approach is based first of all on a data reduction phase through flow sampling by focusing mainly on short lived flows. The second step is then a random aggregation of some descriptors such as a number of SYN packets per flow in two different data structures called Count Min Sketch and Multi-Layer Reversible Sketch. A sequential change point detection algorithm continuously monitors the sketch cell values. An alarm is raised if a significant change is identified in cell values. We make profit of the reversibility properties of the Multi-Layer Reversible Sketch to retrieve useful information about which ''flow'' was the culprit one. The good properties of the Count Min Sketch in terms of resistance to collisions make it possible to check the accuracy of the information about the ongoing attack. With an appropriate definition of the combination of IP header fields that should be used to identify one flow we are able not only to detect the anomaly but also to classify the anomaly as DoS, DDoS or flash crowd, network scanning and port scanning. We validate our framework for anomaly detection on various real world traffic traces and demonstrate the accuracy of our approach on these real-life case studies. Some of our test traffic traces are measurements obtained on a geographical and technical subdivision of an ADSL network of a major Internet Service Provider. Other traces were collected in the framework of a French national research project during online experiments on a distributed measurement network with well known attack types and instants. Our analysis results from online implementation of our algorithm over measurements gathered by a DAG sniffing card are very attractive in terms of accuracy and response time. The proposed approach is very effective in detecting and classifying anomalies, and in providing information by extracting the culprit flows with a high level of accuracy