Higher-Order Moment-Based Anomaly Detection

Venkatraman Renganathan, Navid Hashemi, Justin Ruths, Tyler H. SummersIEEE Control. Syst. Lett 2020 · DOI · OpenReview

TL;DR

This paper introduces a novel method for detecting anomalies in complex cyber-physical systems (CPS) by using higher-order moments of system data. This approach guarantees a controlled false alarm rate, even when system noise deviates from standard Gaussian assumptions, and effectively limits the impact of stealthy attacks.

What Problem Does This Paper Address?

Modern cyber-physical systems (CPS) are increasingly complex and interconnected, making them vulnerable to malicious attacks. A critical aspect of ensuring their robust operation is anomaly detection. Traditional anomaly detection methods often rely on the assumption of Gaussian noise, which simplifies analysis but can lead to significantly higher false alarm rates than expected in real-world scenarios where noise distributions can be non-Gaussian or even heavy-tailed. This inaccuracy can be exploited by attackers to remain undetected. The paper addresses this by developing a method that can guarantee a desired false alarm rate even under uncertainty about the exact noise distribution, and crucially, it quantifies how this improved detection capability restricts an attacker's ability to operate stealthily.

Methods

The core of this paper lies in the application of Distributionally Robust Optimization (DRO), specifically using moment-based ambiguity sets. Instead of assuming a specific noise distribution (like Gaussian), the authors define a set of possible distributions that are consistent with known finite higher-order moments of the system's detection measure.

Here's a breakdown of the key methodological contributions:

  • Higher-Order Moment Ambiguity Sets: The paper formulates ambiguity sets for noise distributions based on the first k moments. This allows for a more flexible representation of uncertainty compared to methods relying solely on mean and variance.
  • Distributionally Robust Thresholding: They propose a method to design an anomaly detector threshold that guarantees the worst-case false alarm rate across all distributions within the defined moment-based ambiguity set. This is achieved by finding a threshold that satisfies a desired false alarm rate A such that sup Pr(rrt ≤ aq,k) = 1 − A, where the supremum is taken over the ambiguity set.
  • Semidefinite Programming (SDP): To compute the tightest possible probability bounds and thus the most effective thresholds, the authors leverage semidefinite programming. This is particularly important for higher-order moments where analytical solutions become intractable.
  • Attack-Reachable Set Analysis: The paper connects the tightened detection threshold to the attacker's capabilities. By bounding the "attack-reachable set" – the set of system states an attacker can manipulate without triggering an alarm – they demonstrate that a more robust detector directly shrinks this set, limiting the attacker's options.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and numerical simulations using synthetic data generated from a model.

Key Insights and Ideas

  • Gaussian Assumption is Risky: The paper strongly emphasizes that assuming Gaussian noise in CPS anomaly detection is not just a simplification but can lead to dangerously high actual false alarm rates, creating blind spots for attackers.
  • Higher-Order Moments Matter: Incorporating information beyond just the mean and variance (i.e., skewness, kurtosis, etc.) significantly tightens the bounds on false alarm rates and, consequently, the detector's threshold. This is the key to improving robustness.
  • Guaranteed Performance: The DRO approach provides a formal guarantee on the false alarm rate, which is crucial for safety-critical systems. This is a significant improvement over methods that might only achieve the desired rate on average or under specific (and potentially incorrect) distributional assumptions.
  • Direct Link Between Detection and Security: The paper elegantly demonstrates that improving anomaly detection robustness directly translates to enhanced system security by shrinking the "attack-reachable set." This provides a quantitative measure of how much harder it becomes for an attacker to operate stealthily.

Key Results

  • Tightened Thresholds: Numerical simulations show that using higher-order moments (k=2, 4) leads to significantly tighter detection thresholds compared to methods using only the first two moments (k=1). For instance, thresholds decreased from 39.83 to 16.54 when moving from k=1 to k=4 for Laplacian noise.
  • Reduced False Alarm Rates: The proposed method guarantees that the false alarm rate does not exceed the desired value (e.g., 5%). In simulations, the actual false alarm rates for higher-order moment thresholds were significantly lower (e.g., 0%, 0.45%, 0% for k=1, 2, 4 respectively, with a desired 5% rate).
  • Shrinking Attack-Reachable Sets: The paper demonstrates that as the detector threshold is tightened by incorporating higher-order moments, the volume of the attack-reachable set shrinks. This means attackers have fewer opportunities to manipulate the system without detection. For example, the reachable sets for higher-order moment thresholds were visibly smaller than those for lower-order ones in the provided figures.

Limitations and Future Work

  • Computational Complexity: While the framework is powerful, solving the semidefinite programs for higher-order moments can become computationally intensive as k increases. The paper mentions that for large k, using Legendre polynomial bases can improve numerical stability.
  • Data Requirements: Estimating higher-order moments accurately requires a substantial amount of data. The paper acknowledges that determining the exact amount of data needed is a topic for future work, though it notes that significant improvements can be seen even with a small number of moments.
  • Data-Driven Uncertainty: The paper discusses the potential for incorporating uncertainty in moment estimates themselves, which would be relevant for data-driven approaches. This is flagged as a direction for future research.
  • Future Work: The authors suggest exploring data-driven formulations with moment estimation uncertainty, securing nonlinear CPS with distributionally robust unscented Kalman filters, and further investigating the computational tractability of higher-order moment problems.

Summary updated

Abstract

The identification of anomalies is a critical component of operating complex, and possibly large-scale and geo-graphically distributed cyber-physical systems. While designing anomaly detectors, it is common to assume Gaussian noise models to maintain tractability; however, this assumption can lead to the actual false alarm rate being significantly higher than expected. Here we design a distributionally robust threshold of detection using finite and fixed higher-order moments of the detection measure data such that it guarantees the actual false alarm rate to be upper bounded by the desired one. Further, we bound the states reachable through the action of a stealthy attack and identify the trade-off between this impact of attacks that cannot be detected and the worst-case false alarm rate. Through numerical experiments, we illustrate how knowledge of higher-order moments results in a tightened threshold, thereby restricting an attacker's potential impact.
BibTeX
@inproceedings{renganathan2020higher,
  author = {Venkatraman Renganathan and Navid Hashemi and Justin Ruths and Tyler H. Summers},
  title = {{Higher-Order Moment-Based Anomaly Detection}},
  booktitle = {IEEE Control. Syst. Lett},
  year = {2020},
  doi = {10.1109/lcsys.2021.3058269},
}
Figure