Data Analysis for Network Cyber-Security

There is increasing pressure to protect computer networks against unauthorized intrusion, and some work in this area is concerned with engineering systems that are robust to attack. However, no system can be made invulnerable. Data Analysis for Network Cyber-Security focuses on monitoring and analyzing network traffic data, with the intention of preventing, or quickly identifying, malicious activity. Such work involves the intersection of statistics, data mining and computer science. Fundamentally, network traffic is relational, embodying a link between devices. As such, graph analysis approaches are a natural candidate. However, such methods do not scale well to the demands of real problems, and the critical aspect of the timing of communications events is not accounted for in these approaches. This book gathers papers from leading researchers to provide both background to the problems and a description of cutting-edge methodology. The contributors are from diverse institutions and areas of expertise and were brought together at a workshop held at the University of Bristol in March 2013 to address the issues of network cyber security. The workshop was supported by the Heilbronn Institute for Mathematical Research. Readership: Researchers and graduate students in the fields of network traffic data analysis and network cyber security. Contents 10 Preface 6 Chapter 1. Inference for Graphs and Networks: Adapting Classical Tools to Modern Data 12 1.1. Introduction 12 1.1.1. Modern network data sets 13 1.1.2. Organization and aims of the chapter 13 1.2. Networks as Relational Data 14 1.2.1. Relational data matrices and covariates 14 1.2.2. Networks as distinct from relational data 16 1.3. Model Specification and Inference 16 1.3.1. Erdos–Renyi: A first illustrative example 17 1.3.2. Approximate inference 20 1.4. Testing for Network Structure 22 1.4.1. The Zachary karate data 23 1.4.2. Tests with known categorial covariates 24 1.4.3. The case of latent categorial covariates 25 1.4.4. Decoupling degree sequence and connectivity 27 1.5. Open Problems in Network Inference 28 1.5.1. Model elicitation and selection 29 1.5.2. Approximate inference and validation 30 1.5.3. Sampling, missingness, and data reduction 31 1.6. Conclusion 32 Acknowledgments 32 Appendix: A Review of Approaches to Network Analysis 33 A.1. Model Elicitation 33 A.2. Model Fitting and Inference 35 A.3. Approximate Inference Procedures 36 A.3.1. Algorithmic approaches 36 A.3.2. Evaluation of efficacy 37 References 38 Chapter 2. Rapid Detection of Attacks in Computer Networks by Quickest Changepoint Detection Methods 44 2.1. Introduction 44 2.2. Quickest Changepoint Detection 47 2.3. Anomaly-based IDS 59 2.3.1. CUSUM and SR score-based algorithms 59 2.3.2. Experimental study 64 2.3.2.1. Detection of DDoS attacks 64 2.3.2.2. Rapid detection of spam at the network level 72 2.4. Hybrid Anomaly–Signature IDS 74 2.4.1. IDS structure 74 2.4.2. Experimental study 76 2.5. Conclusion 79 Acknowledgments 79 References 79 Chapter 3. Statistical Detection of Intruders Within Computer Networks Using Scan Statistics 82 3.1. Introduction 82 3.1.1. Basic graph concepts and computer network data 83 3.1.2. Example traversal attack 84 3.1.3. Attack shapes in the graph 85 3.1.4. Related work 86 3.2. The Scan Statistic 89 3.2.1. Windows in the cross product space 89 3.2.2. A scan statistic for windows in the Time × Graph space 90 3.3. Independence Among Edges in a Path 90 3.4. Modeling, Estimation, and Hypothesis Testing 92 3.4.1. Observed Markov model 93 3.4.2. Hidden Markov model 93 3.4.3. New edges 98 3.4.4. Alternative hypotheses 99 3.4.5. P-value calculation 100 3.4.6. Threshold determination 101 3.5. Simulation Study 102 3.5.1. A comparison of stars and paths 105 3.6. Real Network Detections 107 3.6.1. Detection of user change 107 3.6.2. Detection of real attack 110 3.7. Conclusions and Future Work 111 Acknowledgments 113 References 113 Chapter 4. Characterizing Dynamic Group Behavior in Social Networks for Cybernetics 116 4.1. Introduction 116 4.2. User Interaction Pattern Analysis 118 4.3. Motivation 120 4.4. Proposed Framework 123 4.5. Data Preprocessing 125 4.5.1. Projection of tripartite to bipartite graph 126 4.5.2. Projection of bipartite to one-mode graph 127 4.6. Feature Extraction 128 4.6.1. Tag sense disambiguation 129 4.6.2. Clique percolation method 129 4.6.3. Tag concept hierarchy 129 4.6.4. Effective tag sense disambiguation using tag concept hierarchy 130 4.7. Higher-order Mining 130 4.7.1. User profile 131 4.7.2. Types of user profiles 131 4.7.3. Linking users based on similarity 132 4.7.3.1. Projection of bipartite to one-mode graph 133 4.7.4. Communities in a graph 134 4.7.5. Identifying user communities in social graph 134 4.7.5.1. Detecting ad hoc communities 135 4.7.5.2. Louvain community detection 135 4.7.6. Temporal analysis of communities 135 4.8. Conclusion 136 References 137 Chapter 5. Several Approaches for Detecting Anomalies in Network Traffic Data 140 5.1. Introduction 140 5.2. Description of the Methods 143 5.2.1. Centralised approaches 144 5.2.1.1. TopRank 145 5.2.2. Decentralised approaches 148 5.2.2.1. DTopRank 148 5.2.2.2. BTopRank 149 5.2.2.3. MultiRank 150 5.3. Application of the Centralised Approaches to Real Data 151 5.3.1. Choice of parameters 152 5.3.2. Performance of the method 154 5.3.2.1. Statistical performance 154 5.3.2.2. Numerical performance 156 5.4. Application of the Decentralised Approaches 157 5.4.1. Performance of the methods 157 References 160 Chapter 6. Monitoring a Device in a Communication Network 162 6.1. Introduction 162 6.2. VAST 2008 Challenge Data 163 6.3. Continuous Time Behavioural Modelling 165 6.3.1. Markov jump processes 165 6.3.1.1. Idle and connected states, undirected edges 166 6.3.1.2. Idle and connected states, directed edges 166 6.3.1.3. Embedded Markov chain for connection identities 167 6.3.1.4. Separate states for each connecting node, undirected edges 168 6.3.1.5. Separate states for each connecting node, directed edges 169 6.3.2. Inference for Markov jump processes 170 6.3.3. Seasonal changepoints 171 6.3.3.1. Bayesian changepoint density estimation 172 6.4. Discrete Time Behavioural Modelling 175 6.4.1. Markov chain modelling of a node: idle and connected states 176 6.4.2. Seasonal changepoints 177 6.4.3. Node connection counts 178 6.4.4. Edge-level modelling 178 6.5. Continuous Time Behavioural Monitoring 178 6.5.1. Changepoint analysis 179 6.5.2. Anomaly function 180 6.6. Discrete Time Behavioural Monitoring 180 6.6.1. Quality control chart 181 6.6.2. Discrete p-values 182 6.6.2.1. Basic theory of discrete p-values 182 6.6.2.2. Deterministic adjustment 184 6.6.2.3. Two-sided adjusted p-values 185 6.6.2.4. P-values for variables of mixed type 186 6.6.2.5. Expected adjustment 188 6.6.3. Poisson process p-values 188 6.6.4. Bernoulli process p-values 189 6.7. Results for the VAST Data 190 6.7.1. Continuous time Markov jump process model 190 6.7.1.1. Control charts when monitoring node connection times 191 6.7.1.2. Control charts when monitoring edge connection times of each node 194 6.7.1.3. Changepoint analysis results 195 6.7.2. Discrete time Markov chain model 197 6.8. Conclusions 198 6.8.1. Summary of methods 198 6.8.2. Summary of VAST data results 198 References 198 Index 200 There is increasing pressure to protect computer networks against unauthorized intrusion, and some work in this area is concerned with engineering systems that are robust to attack. However, no system can be made invulnerable. Data Analysis for Network Cyber-Security focuses on monitoring and analyzing network traffic data, with the intention of preventing, or quickly identifying, malicious activity. Such work involves the intersection of statistics, data mining and computer science. Fundamentally, network traffic is relational, embodying a link between devices. As such, graph analysis approaches are a natural candidate. However, such methods do not scale well to the demands of real problems, and the critical aspect of the timing of communications events is not accounted for in these approaches. The contributors are from diverse institutions and attended a workshop held at the University of Bristol in March 2013 to address the issues of network cyber-security. The workshop was supported by the Heilbronn Institute for Mathematical research (HIMR, University of Bristol). Inference for graphs and networks : adapting classical tools to modern data -- Benjamin P. Olding and Patrick J. Wolfe Rapid detection of attacks in computer networks by quickest changepoint detection methods -- Alexander G. Tartakovsky Statistical detection of intruders within computer networks using scan statistics -- Joshua Neil, Curtis Stolie, Curtis Hash and Alex Brugh Characterizing dynamic group behavior in social networks for cybernetics -- Sumeet Dua and Pradeep Chowriappa Several approaches for detecting anomalies in network traffic data -- Céline Lévy-Leduc Monitoring a device in a communication network -- Nick A. Heard and Melissa J. Turcotte.