Botnet Detection Based on Anomaly and Community Detection
Authors:
Open Access
- 29 February 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Control of Network Systems
- Vol. 4 (2) , 392-404
Abstract
We introduce a novel two-stage approach for the important cybersecurity problem of detecting the presence of a botnet and identifying the compromised nodes (the bots), ideally before the botnet becomes active. The first stage detects anomalies by leveraging large deviations of an empirical distribution. We propose two approaches to create the empirical distribution: 1) a flow-based approach estimating the histogram of quantized flows and 2) a graph-based approach estimating the degree distribution of node interaction graphs, encompassing both Erdös-Rényi graphs and scale-free graphs. The second stage detects the bots using ideas from social network community detection in a graph that captures correlations of interactions among nodes over time. Community detection is performed by maximizing a modularity measure in this graph. The modularity maximization problem is nonconvex. We propose a convex relaxation, an effective randomization algorithm, and establish sharp bounds on the suboptimality gap. We apply our method to real-world botnet traffic and compare its performance with other methods.Keywords
Funding Information
- National Science Foundation (CNS-1239021, IIS-1237022, CCF-1527292)
- ARO (W911NF-11-1-0227, W911NF-12-1-0390)
- ONR (N00014-10-1-0952)
This publication has 17 references indexed in Scilit:
- Statistical Traffic Anomaly Detection in Time-Varying Communication NetworksIEEE Transactions on Control of Network Systems, 2014
- Botnet detection using social graph analysis2014
- On a preferential attachment and generalized Pólya’s urn modelThe Annals of Applied Probability, 2013
- Large deviations for the degree structure in preferential attachment schemesThe Annals of Applied Probability, 2013
- Robust and distributed stochastic localization in sensor networksACM Transactions on Sensor Networks, 2009
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006
- Detecting community structure in networksThe European Physical Journal B, 2004
- Generalizations of Polya's urn ProblemAnnals of Combinatorics, 2003
- Lectures on Modern Convex Optimization2001
- Large Deviations Techniques and Applications1998