Luận Văn Network Anomaly Detection with Incomplete Audit Data

ABSTRACT
With the ever increasing deployment and usage of gigabit networks, traditional network anomaly detection based intrusion detection systems have not scaled accordingly. Most, if not all, systems deployed assume the availability of complete and clean data for the purpose of intrusion detection. We contend that this assumption is not valid. Factors like noise in the audit data, mobility of the nodes, and the large amount of data generated by the network make it difficult to build a normal traffic profile of the network for the purpose of anomaly detection.
From this perspective, the leitmotif of the research effort described in this dissertation is the design of a novel intrusion detection system that has the capability to detect intrusions with high accuracy even when complete audit data is not available. In this dissertation, we take a holistic approach to anomaly detection to address the threats posed by network based denial-of-service attacks by proposing improvements in every step of the intrusion detection process. At the data collection phase, we have implemented an adaptive sampling scheme that intelligently samples incoming network data to reduce the volume of traffic sampled, while maintaining the intrinsic characteristics of the network traffic. A Bloom filters based fast flow aggregation scheme is employed at the data pre-processing stage to further reduce the response time of the anomaly detection scheme. Lastly, this dissertation also proposes an expectation-maximization algorithm based anomaly detection scheme that uses the sampled audit data to detect intrusions in the incoming network traffic.
Contents
Dedication iii
Acknowledgements iv
List of Figures xi
List of Tables xiii
1 Introduction 1
1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Research Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Document Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Background 9
2.1 Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Anomaly Detection Techniques . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Premise of Anomaly Detection . . . . . . . . . . . . . . . . . . . 15
2.2.2 Techniques Used in Anomaly Detection . . . . . . . . . . . . . . 16
2.2.2.1 Statistical Anomaly Detection . . . . . . . . . . . . . . 16
2.2.2.2 Machine Learning based Anomaly Detection . . . . . . 22
2.2.2.3 Data Mining based Anomaly Detection . . . . . . . . . 30
2.3 Hybrid Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3 Adaptive Sampling for Anomaly Detection 48
3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3 Self-Similarity and Network Traffic . . . . . . . . . . . . . . . . . . . . 55
3.3.1 Properties of Network Traffic . . . . . . . . . . . . . . . . . . . 55
3.3.2 Self-Similarity and the Hurst Parameter . . . . . . . . . . . . . . 57
3.4 Proposed Sampling Algorithm . . . . . . . . . . . . . . . . . . . . . . . 59
3.4.1 Weighted Least Square Predictor . . . . . . . . . . . . . . . . . . 60
3.4.2 Adaptive Weighted Sampling . . . . . . . . . . . . . . . . . . . 61
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4 System Design 66
4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3 Adaptive Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.4 Flow Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.5 POTION: EM Algorithm-Based Clustering Algorithm . . . . . . . . . . . 73
4.6 Data Summaries for Data Reduction . . . . . . . . . . . . . . . . . . . . 77
4.7 Anomalous Flow Detection . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5 Experimental Analysis 83
5.1 Data Set Descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.1 Evaluation of the Sampling Algorithm . . . . . . . . . . . . . . . 88
5.2.1.1 Experimental Setup . . . . . . . . . . . . . . . . . . . 89
5.2.1.2 Metrics for Evaluation . . . . . . . . . . . . . . . . . . 90
5.2.1.3 Experimental Results . . . . . . . . . . . . . . . . . . 91
5.2.2 Evaluation of the Clustering Algorithm . . . . . . . . . . . . . . 93
5.2.2.1 Experimental Setup . . . . . . . . . . . . . . . . . . . 94
5.2.2.2 Metrics for Evaluation . . . . . . . . . . . . . . . . . . 95
5.2.2.3 Experimental Results . . . . . . . . . . . . . . . . . . 96
5.2.3 Evaluation of the Anomaly Detection Algorithm . . . . . . . . . 98
5.2.3.1 Experimental Setup . . . . . . . . . . . . . . . . . . . 98
5.2.3.2 Metrics for Evaluation . . . . . . . . . . . . . . . . . . 99
5.2.3.3 Experimental Results . . . . . . . . . . . . . . . . . . 99
5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6 Summary and FutureWork 105
6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
References 111
Appendices 129
A The Expectation–Maximization Algorithm 129
Vita 133