Nearly Optimal Change-Point Detection with an Application to Cybersecurity

Abstract

We address the sequential change-point detection problem for the Gaussian model where baseline distribution is Gaussian with variance σ² and mean μ such that σ² = aμ, where a > 0 is a known constant; the change is in μ from one known value to another. First, we carry out a comparative performance analysis of four detection procedures: the Cumulative Sum (CUSUM) procedure, the Shiryaev–Roberts (SR) procedure, and two its modifications—the Shiryaev–Roberts–Pollak and Shiryaev–Roberts–r procedures. The performance is benchmarked via Pollak's maximal average delay to detection and Shiryaev's stationary average delay to detection, each subject to a fixed average run length to false alarm. The analysis shows that in practically interesting cases the accuracy of asymptotic approximations is “reasonable” to “excellent”. We also consider an application of change-point detection to cybersecurity for rapid anomaly detection in computer networks. Using real network data we show that statistically traffic's intensity can be well described by the proposed Gaussian model with σ² = aμ instead of the traditional Poisson model, which requires σ² = μ. By successively devising the SR and CUSUM procedures to “catch” a low-contrast network anomaly (caused by an Internet Control Message Protocol reflector attack), we then show that the SR rule is quicker. We conclude that the SR procedure is a better cyber “watch dog” than the popular CUSUM procedure.

Keywords:

• Anomaly detection
• CUSUM procedure
• Cybersecurity
• Intrusion detection
• Sequential analysis
• Sequential change-point detection
• Shiryaev–Roberts procedure
• Shiryaev–Roberts–Pollak procedure
• Shiryaev–Roberts–r procedure

Subject Classifications:

• 62L10
• 62L15
• 62P30

ACKNOWLEDGMENTS

The work of Aleksey Polunchenko and Alexander Tartakovsky was supported by the U.S. Army Research Office under MURI grant W911NF-06-1-0044, by the U.S. Air Force Office of Scientific Research under MURI grant FA9550-10-1-0569, by the U.S. Defense Threat Reduction Agency under grant HDTRA1-10-1-0086, and by the U.S. National Science Foundation under grants CCF-0830419 and EFRI-1025043 at the University of Southern California, Department of Mathematics. We also thank Christos Papadopoulos of Colorado State University and John Heidemann of the Information Sciences Institute for providing real computer network data traces.

Notes

Recommended by T. K. S. Solanky.