Multivariate Online Anomaly Detection Using Kernel Recursive Least Squares
Abstract
High-speed backbones are regularly affected by various kinds of network anomalies, ranging from malicious attacks to harmless large data transfers. Different types of anomalies affect the network in different ways, and it is difficult to know a priori how a potential anomaly will exhibit itself in traffic statistics. In this paper we describe an online, sequential, anomaly detection algorithm, that is suitable for use with multivariate data. The proposed algorithm is based on the kernel version of the recursive least squares algorithm. It assumes no model for network traffic or anomalies, and constructs and adapts a dictionary of features that approximately spans the subspace of normal behaviour. The algorithm raises an alarm immediately upon encountering a deviation from the norm. Through comparison with existing block-based offline methods based upon Principal Component Analysis, we demonstrate that our online algorithm is equally effective but has much faster time-to-detection and lower computational complexity. We also explore minimum volume set approaches in identifying the region of normality.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
KOAD can detect 30 anomaly records with 17 false positives, and 26 anomaly records with 1 false positive, under different parameters, in the packet time series.
“it can detect 30 anomaly records with 17 FPs, and 26 anomaly records with 1 FP”
From A comprehensive survey on machine learning for networking: Evolution, applications and research opportunities (2018) · cites this paper as [7]
For the flow-count time series, KOAD outperforms PCA and OCNM in terms of detection rate but at the cost of a higher false positive rate.
“On the other hand, for the flow-count time series, KOAD outperforms PCA and OCNM in terms of detection rate but at the cost of a higher FP.”
From A comprehensive survey on machine learning for networking: Evolution, applications and research opportunities (2018) · cites this paper as [7]
PCA can detect 25 anomalies with 0 false positives in the packet time series.
“However, PCA can detect 25 anomalies with 0 FP.”
From A comprehensive survey on machine learning for networking: Evolution, applications and research opportunities (2018) · cites this paper as [7]
In the packet time series, OCNM flags 26 out of 34 anomalies but generates 14 false positives.
“In packet time series, OCNM flags 26 out of 34 anomalies but generates 14 FPs”
From A comprehensive survey on machine learning for networking: Evolution, applications and research opportunities (2018) · cites this paper as [7]
Cites
Rayward-Smith, V. J., Cormen, T. H., Leiserson, C. E., & Rivest, R. L. (1991) · Journal of the Operational Research Society · doi:10.2307/2583667 · Cited by 16,953 · see citing works
Schölkopf, B., & Smola, A. J. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4175.001.0001 · Cited by 11,934 · see citing works
Grossman, P. (2009) · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,906 · see citing works
Introduction to algorithms [2nd ed.]
Cormen, T. H. (2001) · Cited by 1,902 · see citing works
Diagnosing network-wide traffic anomalies
Lakhina, A., Crovella, M., & Diot, C. (2004) · Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication · doi:10.1145/1015467.1015492 · Cited by 1,399 · see citing works
Self-citationControl Procedures for Residuals Associated With Principal Component Analysis
Jackson, J. E., & Mudholkar, G. S. (1979) · Technometrics · doi:10.1080/00401706.1979.10489779 · Cited by 1,189 · see citing works
The Kernel Recursive Least-Squares Algorithm
Engel, Y., Mannor, S., & Meir, R. (2004) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2004.830985 · Cited by 1,110 · see citing works
Mining anomalies using traffic feature distributions
Lakhina, A., Crovella, M. E., & Diot, C. (2005) · ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM) · doi:10.1145/1080091.1080118 · Cited by 1,062 · see citing works
Self-citationA signal analysis of network traffic anomalies
Barford, P., Kline, J., Plonka, D., & Ron, A. (2002) · ACM SIGCOMM Internet Measurement Workshop (IMW) · doi:10.1145/637201.637210 · Cited by 811 · see citing works
State transition analysis: a rule-based intrusion detection approach
Ilgun, K., Kemmerer, R. A., & Porras, P. A. (1995) · IEEE Transactions on Software Engineering · doi:10.1109/32.372146 · Cited by 753 · see citing works
Structural analysis of network traffic flows
Lakhina, A., Papagiannaki, K., Crovella, M. E., et al. (2004) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/1005686.1005697 · Cited by 454 · see citing works
Self-citationMining anomalies using traffic feature distributions
Lakhina, A., Crovella, M. E., & Diot, C. (2005) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1090191.1080118 · Cited by 445 · see citing works
Self-citationAberrant Behavior Detection in Time Series for Network Monitoring
Brutlag, J. D. (2000) · USENIX Large Installation Systems Administration Conference · Cited by 298 · see citing works
Adaptive real-time anomaly detection using inductively generated sequential patterns
Teng, H., Chen, K., & Lu, S. (1990) · IEEE Computer Society Symposium on Research in Security and Privacy · doi:10.1109/risp.1990.63857 · Cited by 206 · see citing works
Machine learning approaches to network anomaly detection
Ahmed, T., Oreshkin, B. N., & Coates, M. (2007) · Cited by 130 · see citing works
Self-citationMachine learning techniques for the computer security domain of anomaly detection
Lane, T. D. R., & Brodley, C. E. (2000) · Cited by 113 · see citing works
Statistical Analysis of Network Traffic for Adaptive Faults Detection
Hajji, H. (2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2005.853414 · Cited by 93 · see citing works
Estimation of high-density regions using one-class neighbor machines
Muñoz, A., & Moguerza, J. M. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.52 · Cited by 67 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Boutaba, R., Salahuddin, M. A., Limam, N., Ayoubi, S., Shahriar, N., Estrada-Solano, F., & Caicedo, O. M. (2018) · Journal of Internet Services and Applications · doi:10.1186/s13174-018-0087-2 · Cited by 1,036 · see citing works
- Authors
- Ahmed, T., Coates, M., & Lakhina, A.
- Affiliations
- McGill University (CA)
- Boston University (US)
- Venue
- IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications
- Publisher
- IEEE
- Published
- 2007-05
- Pages
- 625-633
- OpenAlex
- W2134583708
- Cited by
- 148
- References
- 18
- Citations by year
- 2025: 1 · 2023: 4 · 2022: 5 · 2021: 8 · 2020: 7 · 2019: 14 · 2018: 14 · 2017: 10 · 2016: 12 · 2015: 9 · 2014: 9 · 2013: 11 · 2012: 17
- FWCI
- 4.55
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE Conference on Computer Communications (INFOCOM) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Anomaly Detection Techniques and Applications
- Physical Sciences › Computer Science › Computer Networks and Communications › Network Security and Intrusion Detection
- Physical Sciences › Engineering › Biomedical Engineering › Artificial Immune Systems Applications
- Keywords
- network anomaly detection, online anomaly detection, kernel recursive least squares, multivariate data, network traffic monitoring, feature dictionary, detection time, principal component analysis comparison
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
