Information-Theoretic and Algorithmic Thresholds for Network Attack Detection via Spectral and CUSUM Methods

Abstract

We develop a unified theory for the detectability of network-borne attacks under two canonical observation models: (i) a static graph drawn from an Erdős–Rényi background with a planted anomalous community, and (ii) a temporal interaction network modeled by multivariate point processes (Poisson or Hawkes). Our main contribution is to match, up to universal constants, information-theoretic lower and upper bounds that govern when reliable testing is possible. In the static case, the core quantity is the accumulated edgewise signal k²·χ²(Bern(p+Δ) ‖ Bern(p)), where χ² ≈ Δ²/[p(1−p)] for small Δ; detection is impossible when this falls below c·log n, and a non-backtracking spectral statistic succeeds above C·log n. In the temporal case, detectability is controlled by the Kullback–Leibler information rate I contributed by internal edges over a window of length T, yielding a threshold T I ≳ log n; a likelihood-based cumulative-sum (CUSUM) test achieves first-order optimal delay ≈ |log α|/I at false-alarm level α. We complement these limits with concrete algorithms and simple experiments. A pruning-based non-backtracking spectral detector for static graphs and a sparsity-aware CUSUM procedure for temporal streams are given with near-linear time and memory complexity. Monte Carlo simulations on Erdős–Rényi graphs with planted dense subgraphs and on Poisson streams illustrate the predicted phase transitions: detection power increases as k²·χ²/log n crosses a constant-level boundary, and empirical detection delays closely track the log(ARL)/I prediction. We also discuss robustness under bounded edge perturbations and mild misspecification, and show how these thresholds can be used to dimension practical security monitoring systems.