KNOWLEDGE DISCOVERY IN COMPUTER NETWORK DATA: A SECURITY PERSPECTIVE by Kendall E. Giles A dissertation submitted to The Johns Hopkins University in conformity with the requirements for the degree of Doctor of Philosophy. Baltimore, Maryland October, 2006 © Kendall E. Giles 2006 All rights reserved UMI Number: 3240712 Copyright 2006 by Giles, Kendall E.
All rights reserved. INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.
Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3240712 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.
ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Abstract From a security perspective, computer network data is analyzed largely for two purposes: to detect known structures, and to identify previously unknown struc- tures. As an example of the former, it is considered standard procedure to filter network traffic for previously identified viruses in order to prevent infection and to reduce virus spread. As an example of the latter, security researchers may want to search datasets in order to identify and discover previously unknown relationships or structures in the data, such as intrusions into a network by an external hacker.
However, among other limitations, traditional methods of network data analysis are insufficient when processing large volumes of network traffic, do not allow for the discovery of local structures, do not visualize high-dimensional data in meaningful ways, and do not allow user input during search iterations. We present the development, analysis, and testing of a new framework for the analysis of network traffic data. In particular, and among others, the frame- work addresses the following questions: How is network traffic represented in high- dimensional space? (normalized graph Laplacians); How can we extract features ii from the data? (flow-based feature extraction); How to embed high-dimensional representations in low dimensions? (Laplacian Eigenmaps); How to intuitively vi- sualize low-dimensional structures? (Fiedler Space projections); How to address scaleability concerns? (proximity computation, partitioning, and eigenpair com- putation approximations); How can the user be involved in the search? (iterative denoising applied to network data); How might this framework be used on empirical network data? (application to computer network intrusion data, backscatter data, and computer network application data). As such, this work presents theoretical as well as practical contributions, and these results are discussed within the con- text of traditional methods and techniques.
Thus, due to its theoretical and applied benefits of visualizing and classifying a variety of unsupervised, heterogeneous, high- dimensional computer network traffic datasets, we feel that Iterative Denoising can be a unifying technology for protection, detection, and response groups coordinating around a network security monitoring system. Carey Priebe (Advisor) Dr. Fabian Monrose Dr. David Marchette Dr.
Donniell Fishkind ili Acknowledgements Foremost, I would like to thank the members of my committee, Dr. Carey Priebe, Dr. David Marchette, Dr. Fabian Monrose, and Dr.
Donniell Fishkind, for their extreme patience and willingness to take a chance on helping me see this dissertation through to completion. I would also like to thank Dr. Michael Trosset for working with me and helping me to learn about many of the theoretical aspects contained herein. I must also thank my wife for letting me realize this goal.
And to my Mom and Dad, no amount of thanks can suffice. iv Contents Abstract ii Acknowledgements iv List of Tables vii List of Figures viii 1 Introduction 1. Q HQ ung ng V va 1. c c c Q k nà kg và v.3 Structure of the TheSs.Ặ QC Q 000 eee eee eee 2 A Taxonomy of Computer Network Data Analysis Approaches 2.
eee ee ee es 3 The Iterative Denoising Framework 3.2 Overview of the Algorithm. eee ee ee 3.4 Design “6 6 NHHaAaäaa.41 Extract Summary Metrics. LH nu ng cv v k k k k kg 3. c Q Q Q Q Q Q HQ và gà kg TT va 3.5 Application: Science News Corpus.1 An Iterative Denoising of Documents .2 A Detailed Analysis of Clustered Documents.3 Tllustration by Comparison of Two Key Features.
Iterative Denoising of KDDCup 4.2 Description of the Dataset. Q Q rà gà và và 4.3 Combined Normal and Attack Trafc.4 Iterative Denoising Results. ee te ee 4.3 Combined Normal and Attack Traffic .ee A Hierarchical Analysis of Network Application Flows 5.2 A Linear Iterative Denoising Implementation.3 Description of the Dataset. ee 6 Conclusions Vita vi List of Tables 3.1 Text Corpus Metrics.
we ee Q Q HH HN uc cán VY kg KH N 3.2 Science News Corpus. 6 6 1 ee et ee eeV4 3.3 Similarities in Node 8 Document Neighbors. 66 eee et ee te ee 3.4 Physics and Math/CS Confusion Matrix, With Corpus-Dependent Feature Extraction (Iterative Denoising), 2. 6 6 6 HH u Q VY cv V V Ro Ro Ko N 3.5 Physics and Math/CS Confusion Matrix, Without Corpus-Dependent Feature Extrac- tion (Hierarchical Clustering).
6 6 ee ee Q cv cv cv cv ck ca N k A k Và 4.1 Categories of Network TYaflc.2 Network Traffic Features. 6 6 ẶẰẮŠ MN áaa | a q HH 4.3 Records Used for Analysis. 6 6 6 6 oe ee Q Q Q Q VU VU Q Q ee ng 4.4 Normal Traffic Confusion Matrix, k=1. 1 1 ee ee ee et ee et ee 4.5 Attack Traffic Confusion Matrix,k=1.
1 we ee ee te et ee 4.6 Combined Traffic Confusion Matrix,k=1. eee eee et ee es 4.7 Attack Type Colors. ee ee HH nu cv cv can cv cv CV CV ca KT 5.2 Dataset Window Distribution, ©.3 Hierarchical k-Means Confusion Matrix. 6 ee ee ee eee ee 5.4 Linear Iterative Denoising Confusion Matrix.
6 6 6 LH LH ee 5.9 Nonlinear Iterative Denoising Confusion Matrix. 6 6 ee ee ee ee ee vii List of Figures 1.3 Curse of Dimensionality: As the Dimensionality Increases, the Range of the Feature Space that Must Be Searched Increases Dramatically.4 Pairs Plot of KDD Cup Attack Data, Showing the Combinatorial Problem with Visu- alizing Large Numbers of Features. 6 6 eee ee ee ee ee t 11 2.1 A Taxonomy of Computer Network Data Analysis Approaches.2 The Data Modeling Approach. 1 eee eee ee tt te 22 2.3 The Algorithmic Modeling Approach.
6 eee eee ee ee te 25 3.1 Iterative Denoising Flowchart. 6 1 ee ee ee ee eev 33 3. ng cv na cv kg v KV vn 43 3.3 An Iterative Denoising Tree on Science News Corpus. 1 1 eee ee es 68 3.4 Node 1, Fiedler Space Embedding: Anthropology (yellow), Astronomy (black), Behav- ioral Sciences (pink), Earth Sciences (light gray), Life Sciences (orange), Math & CS (red), Medicine (green), Physics (blue).5 Node 4, Fiedler Space Embedding: Anthropology (yellow), Astronomy (black), Behav- ioral Sciences (pink), Earth Sciences (light gray), Life Sciences (orange), Math & CS (red), Medicine (green), Physics (blue).6 Node 3, Fiedler Space Embedding: Anthropology (yellow), Astronomy (black), Behav- ioral Sciences (pink), Earth Sciences (light gray), Life Sciences (orange), Math & CS (red), Medicine (green), Physics (blue).7 Node 8, Fiedler Space Embedding: Anthropology (yellow), Astronomy (black), Behav- ioral Sciences (pink), Earth Sciences (light gray), Life Sciences (orange), Math & CS (red), Medicine (green), Physics (blue), 6 26.8 Node 9, Fiedler Space Embedding: Anthropology (yellow), Astronomy (black), Behav- ioral Sciences (pink), Earth Sciences (light gray), Life Sciences (orange), Math & CS (red), Medicine (green), Physics (blue), 6 6 1 6 we ee ee 75 vill 3.9 Node 10, Fiedler Space Embedding: Anthropology (yellow), Astronomy (black), Behav- ioral Sciences (pink), Earth Sciences (light gray), Life Sciences (orange), Math & CS (red), Medicine (green), Physics (blue).
we ee Q HQ HQ gu Q v kia 3.10 Four-Class Science News, Root Node: Astronomy (black), Physics (blue), Medicine (green), Math & CS (red), 6 6 ee 3.11 Physics and Math/CS Node, With Corpus-Dependent Feature Extraction (Iterative Denoising): Astronomy (black), Physics (blue), Medicine (green), Math & CS (red).12 Physics and Math/CS Node, Without Corpus-Dependent Feature Extraction (Hierar- chical Clustering): Astronomy (black), Physics (blue), Medicine (green), Math & CS (red), ccĐ 3.13 Node 4 Computed Without Corpus-Dependent Feature Extraction: Anthropology (yel- low), Astronomy (black), Behavioral Sciences (pink), Earth Sciences (light gray), Life Sciences (orange), Math & CS (red), Medicine (green), Physics (blue),. 4,1 Normal Traffic, Iterative Denoising Tree. 0 HQ HQ Q Q na va 4.2 Normal Traffic—Root Node, Fiedler Spa€8. ee ee ng Và sa 4.3 Normal Traffic—Node 2, Fiedler Space.4 Normal Traffic—Node 4, Fiedler Space.5 Normal Traffic—Iterative Denoising Tree, 3 levels.
ee ee es 4.6 Normal Traffic—Node 4, Denoised Partition 1, Fiedler Space.7 Normal Traffic—Node 4, Denoised Partition 3, Fiedler Space.8 Normal Traffic—Local Time-Series Structure.9 Attack Traflic—lterative Denoising Tree. HQ L Q HQ ee 4.10 Attack Traffic—Root Node, Fiedler Space. ee HQ Q Q va kia 4.11 Attack Traffic—Node 4, Fiedler Space. c 1 we ee ee và 4.12 Attack Traffic—Iterative Denoising Tree, 3 levels.13 Attack Traffic—Node 4, Denoised Partition 1, Fiedler Space.14 Attack Traffic—Node 4 Denoised Partition 4, Fiedler Spaces .15 Combined Traffic—Iterative Denoising Tree.16 Combined Traffic—Root Node, Fiedler Space.
0 ce Q HH et Quà sa 4.17 Combined Traffic—Iterative Denoising Tree, 3 levels.18 Combined Traffic—Node 3, Denoised Partition 1, Fiedler Space.19 Combined Traffic—Node 3, Denoised Partition 4, Fiedler Space.1 Flows by Number of Packets. ‹ ee et HQ na Q v TQ na 5.2 Flows by Number of Bytes. ce ng kg cv v kg va 5.3 Flows by Duration. HQ nu cu va và va va xa 5.4 Variation Explained by Principal Components.
6 ee Q Q ee ee 5.5 Scatterplot of PƠI and PC2 by Class. © 6 6 6 Q Q HQ HQ Hạ va 5.6 Iterative Denoising Tree Part 1.7 Iterative Denoising Tree Part 2. 6 0 ee ng và kà Ka ix 5.8 Root Node of Fiedler Space Embedding, Showing in Particular Clear Separation of FTP Traffic (Yellow) and Multiple Groups of NNTP Traffic (Red).9 Root Node Cluster Features of Multiple NNTP Groups, Showing Features Clustered by Application Behavior, 2. 6 1 6 ee ee ee ee VN V V Và Chapter 1 Introduction Across many fields, the acceleration of technology and human inquisitiveness has led to a vast (over)abundance of heterogeneous, high-dimensional data.
This means that a user, who wants to understand a large, complex set of data and find interesting information and relationships in that data, needs a sufficiently flexible and powerful computational framework in hand to facilitate data processing and knowledge discovery. For example, imagine that a user has been presented a large collection of text documents and wants to examine and understand those documents from an analytical perspective. This broad desire can take many forms. The user might have an information retrieval task in mind, where it is desired to find a set of documents relevant to a specific query.
Or the user might wish to understand relationships between multiple documents. The user might also wish to identify the topic of discussion in a collection of emails, or to cluster them according to relevant criteria. However, such tasks often have technical constraints. Increasingly the user must analyze large, unstructured datasets, meaning that the dataset may not include class labels for the documents, and that the number of documents to be analyzed is large and possible complex +.
So the user’s task is to explore the data (the corpus of documents), extract meaningful, implicit, and previously-unknown information from a large unstructured corpus. From this scenario we can identify several relevant issues and needs.