Source-linked AI summary
Efficient Computer Network Anomaly Detection by Changepoint Detection Methods
Alexander G. Tartakovsky, Aleksey S. Polunchenko, Grigory Sokolov
TL;DR
The paper addresses rapid online detection of anomalies in computer-network traffic while limiting false alarms. It proposes a score-based repeated Shiryaev–Roberts procedure, which is experimentally shown to outperform repeated CUSUM on a real SYN flood trace, while also motivating a spectral-signature complement for filtering and confirmation.
Problem
The problem is to detect computer-network anomalies quickly despite unknown attack onset, non-Gaussian traffic distributions, and the need to control false alarms.
Method
The paper uses a multi-cyclic Shiryaev–Roberts procedure with a linear-quadratic score replacing the likelihood ratio, without assuming Gaussian pre- and post-change distributions.
Results
0.14 seconds (7 samples) versus 0.21 seconds (10 samples): repeated score-based SR detected the real SYN flood faster than repeated CUSUM, with approximately 7 false alarms per 1000 samples for both.
Takeaways & Limitations
A score-based multi-cyclic SR detector is a computationally simple network-anomaly watchdog, and a spectral-signature IDS could filter false alarms and confirm true attacks.
Takeaways & Limitations
Instantaneous detection is unavailable unless false-alarm risk is high; raising thresholds reduces false alarms but increases detection delay.
Abstract
from arXiv · showhide
We consider the problem of efficient on-line anomaly detection in computer network traffic. The problem is approached statistically, as that of sequential (quickest) changepoint detection. A multi-cyclic setting of quickest change detection is a natural fit for this problem. We propose a novel score-based multi-cyclic detection algorithm. The algorithm is based on the so-called Shiryaev-Roberts procedure. This procedure is as easy to employ in practice and as computationally inexpensive as the popular Cumulative Sum chart and the Exponentially Weighted Moving Average scheme. The likelihood ratio based Shiryaev-Roberts procedure has appealing optimality properties, particularly it is exactly optimal in a multi-cyclic setting geared to detect a change occurring at a far time horizon. It is therefore expected that an intrusion detection algorithm based on the Shiryaev-Roberts procedure will perform better than other detection schemes. This is confirmed experimentally for real traces. We also discuss the possibility of complementing our anomaly detection algorithm with a spectral-signature intrusion detection system with false alarm filtering and true attack confirmation capability, so as to obtain a synergistic system.
I. INTRODUCTION
Computer-network anomaly detection is framed as an online statistical changepoint problem, and the paper proposes a score-based multi-cyclic detector built on Shiryaev–Roberts. The approach is motivated by the SR procedure’s computational simplicity and exact multi-cyclic optimality, with real-data experiments used for confirmation.
- Network anomaly detection is a topical cybersecurity problem addressed by statistical methods that detect deviations from normal traffic.
- The Shiryaev–Roberts procedure is computationally as simple as the CUSUM chart or EWMA scheme and is exactly optimal in a certain multi-cyclic setting.
- The paper proposes a novel multi-cyclic anomaly detector using the Shiryaev–Roberts procedure as its prototype.
- The proposed detector is expected to outperform other schemes, particularly multi-cyclic CUSUM, and this is tested experimentally on real data.
II. QUICKEST CHANGEPOINT DETECTION
Quickest changepoint detection seeks rapid detection of a transition from normal to abnormal behavior under a false-alarm constraint. This section develops the multi-cyclic setting, formalizes its stationary delay objective, and identifies Shiryaev–Roberts as exactly optimal for detecting distant changes after repeated false alarms.
- Quickest changepoint detection sequentially identifies an unknown transition from a normal to an abnormal process while controlling false-alarm risk.
- The iid model assumes observations follow density f before an unknown changepoint and density g after it.
- Detection procedures distinguish hypotheses for a change at time k from the hypothesis that no change ever occurs using likelihood ratios and sequential statistics.
- CUSUM maximizes the log-likelihood ratio over possible changepoints and stops when its recursively updated statistic crosses a threshold.
- The multi-cyclic setting repeatedly restarts a stopping rule after false alarms, making stationary average detection delay suitable for changes occurring far in the future.
- The Shiryaev–Roberts procedure is exactly optimal for every γ > 1 under stationary average detection delay, making it a better alternative to CUSUM and EWMA in this setting.
III. TRANSITION TO CYBERSECURITY
The paper frames network anomaly detection as quickest changepoint detection and develops a score-based, multi-cyclic Shiryaev–Roberts procedure for unknown traffic distributions. The method uses score statistics and thresholds to detect mean or variance shifts while controlling false alarms.
- Network anomalies are formulated as changes in the statistical profile of traffic that should be detected rapidly while limiting false detections.
- The proposed detector is a score-based modification of the multi-cyclic Shiryaev–Roberts procedure designed for situations where pre- and post-anomaly distributions are unknown.
- Score-based SR and CUSUM procedures operate when score functions have negative expected values before changes and positive expected values after changes, although optimality is then lost.
- The score construction targets mean and variance shifts, using training-data estimates of baseline parameters that are periodically re-estimated for long-term traffic nonstationarity.
- A linear-quadratic score uses positive design coefficients for simultaneous mean and variance increases, with C2 or C1 set to zero when one shift is negligible.
- Under Gaussian pre- and post-change distributions with known putative parameters, the linear-quadratic score becomes the log-likelihood ratio and is optimal for those parameter values.
IV. A CASE STUDY
The case study evaluates score-based multi-cyclic SR and CUSUM detection on a real SYN flood trace. Both detect the attack quickly, while SR achieves the shorter reported delay under comparable false-alarm rates.
- Data and setup: The experiment uses a real SYN flood trace, a volume anomaly caused by SYN requests that congest the victim’s link and exhaust resources.The data comes from the LANDER project.
- Data and setup: Attack onset is difficult to identify because a fluctuation precedes the attack, making automatic false-alarm control challenging.
- Data and setup: Connections are observed in 20 msec batches, with legitimate traffic averaging 1669.09 connections and attack traffic averaging 1887.56.The corresponding standard deviations are 113.884 and 218.107 connections per 20 msec, respectively.
- Data and setup: The empirical legitimate-traffic distribution resembles a Gaussian process more closely than the attack-traffic distribution, and score-based SR and CUSUM use a linear-quadratic score.
- Detection results: Low thresholds support very small detection delays but unavoidably produce multiple false alarms before the attack, which require filtering.
- Detection results: The repeated SR procedure detects the attack after approximately 0.14 seconds, compared with about 0.21 seconds for CUSUM, while both produce roughly 7 false alarms per 1000 samples.
V. FURTHER DISCUSSION
The discussion identifies a speed–false-alarm trade-off in changepoint detection and proposes combining a fast detector with a more computationally demanding spectral-signature IDS. The proposed alliance is intended to filter false alarms and confirm true attacks.
- Trade-off: Changepoint detectors can be computationally inexpensive, but instantaneous detection is unavailable without high false-alarm risk.
- Trade-off: Raising detection thresholds reduces false alarms but increases detection delay.
- Synergistic system: The paper proposes triggering a flow-based spectral-signature IDS only after a changepoint detector suspects an anomaly.The signature detector uses Fourier transforms to obtain traffic’s spectral characteristics.
- Synergistic system: This division of labor uses the inexpensive preliminary detector to offset the spectral-signature method’s higher computational complexity while supporting false-alarm rejection and true-detection confirmation.
VI. CONCLUSION
The paper proposes a score-based, multi-cyclic Shiryaev–Roberts anomaly detector for network traffic and reports that it outperformed multi-cyclic CUSUM in a real SYN flood case study. It also proposes complementing changepoint detection with a signature-based spectral IDS to filter false alarms and confirm real attacks.
- The method replaces the likelihood ratio in a repeated Shiryaev–Roberts procedure with a linear-quadratic score to accommodate mismatched real-world traffic distributions.The authors note that both pre-attack and post-attack distributions can differ from hypothesized Gaussian or Poisson models.
- The score-based detector remains easy to implement and has practically no computational complexity.
- The Shiryaev–Roberts procedure provides exact multi-cyclic optimality in a simple known-density change-detection problem, unlike SPRT, CUSUM, and EWMA.
- The score-based multi-cyclic Shiryaev–Roberts algorithm outperformed the multi-cyclic CUSUM procedure in a real SYN flood case study.
- A signature-based spectral IDS could complement changepoint detection by filtering false alarms and confirming real attacks.