Simultaneous Distributed Estimation and Attack Detection/Isolation in Social Networks: Structural Observability, Kronecker-Product Network, and Chi-Square Detector

Mohammadreza Doostmohammadian, Themistoklis Charalambous, Miadreza Shafie-khah, Nader Meskin, Usman A. KhanarXiv 2021 · arXiv · OpenReview

TL;DR

This paper introduces a novel distributed system for social networks that can simultaneously estimate the network's state and detect/isolate adversarial attacks. It achieves this by equipping each sensor with a local chi-square detector, eliminating the need for a central coordinator and making it suitable for large-scale, potentially unstable networks.

What Problem Does This Paper Address?

In today's interconnected world, social networks are vast and complex, making it crucial to monitor their states and ensure their integrity. However, these networks are vulnerable to adversarial attacks that can corrupt the data collected by sensors, leading to inaccurate estimations. Existing methods for detecting and isolating these attacks often rely on centralized architectures, which become impractical for large-scale networks due to communication overhead. Furthermore, many approaches make simplifying assumptions about the noise distribution (e.g., bounded support), which can lead to errors when dealing with real-world, unbounded noise. This paper tackles the challenge of developing a distributed, scalable, and robust solution for simultaneous state estimation and attack detection/isolation in social networks, even under unbounded noise conditions.

Methods

The core of the proposed solution lies in a distributed estimation framework combined with a novel attack detection mechanism.

  • Distributed Estimation: The paper adapts a single time-scale distributed estimator, incorporating a consensus mechanism (averaging information from neighbors) and a measurement update step. This allows each sensor to iteratively refine its estimate of the global social state using local information and data from its connected sensors.
  • Structural Observability and Kronecker-Product Networks: To ensure that the distributed system can effectively observe the network's state, the authors leverage the concept of structural observability. They introduce the idea of a "Kronecker-product network" to analyze the composite structure of the social network and the sensor network, determining the minimal connectivity requirements for distributed observability. This is a key theoretical contribution that allows for efficient network design.
  • Local Chi-Square ($χ^2$) Detector: For attack detection, each sensor employs a local $χ^2$ detector. This detector analyzes the "residual" – the difference between the sensor's actual measurement and its estimated measurement – to identify anomalies. Unlike previous methods, this detector uses a probabilistic threshold based on a desired false alarm rate (FAR) and a sliding window of past residuals. This approach is robust to unbounded noise.
  • Attack Isolation: A crucial aspect is the ability to isolate the attacked sensor. The paper shows that the residual at an attacked sensor is biased by the attack, while other sensors' residuals are not directly affected by that specific attack. This localized bias allows for the identification of the compromised sensor.
  • Gain Matrix Design: Linear Matrix Inequalities (LMIs) are used to design block-diagonal gain matrices for the estimators. This ensures that each sensor's estimation process is decentralized and only relies on local information, a critical requirement for large-scale networks.

Datasets

Not discussed in the paper. The paper uses a simulated social network for evaluation.

Key Insights and Ideas

  • Decentralized Attack Detection is Feasible: The paper demonstrates that sophisticated attack detection and isolation can be achieved at each sensor locally, without relying on a central authority. This is a significant step towards secure and scalable distributed systems.
  • Unbounded Noise Robustness: By using a probabilistic $χ^2$-test with a sliding window, the method effectively handles Gaussian noise with unbounded support, a more realistic scenario than many prior works.
  • Structural Observability for Network Design: The introduction of the Kronecker-product network concept provides a powerful theoretical tool for understanding and designing the sensor network's structure to guarantee distributed observability, even for potentially unstable social systems.
  • Local Observability Not Required: The proposed technique does not require each individual sensor to be able to observe the entire system state locally, making it applicable to a much wider range of large-scale social networks where individual sensors have limited views.

Key Results

The paper presents a theoretical framework and a simulation-based evaluation.

  • Successful Simulation: In a simulated social network of 10 nodes with 4 sensors, the proposed algorithm successfully tracked the global social state in an attack-free scenario.
  • Attack Detection and Isolation: When simulated attacks were introduced, the distance measures at the attacked sensors ($v_i$) exceeded the probabilistic thresholds, correctly indicating the presence of attacks. The method was able to distinguish between different FARs, with a less conservative threshold (higher FAR) detecting both simulated attacks, while a more conservative threshold (lower FAR) detected only one.
  • Theoretical Guarantees: The paper provides theoretical conditions for distributed observability based on the structure of both the social network and the sensor network.

Limitations and Future Work

  • Limitations:
    • The paper assumes known system and measurement noise covariances (Q and R).
  • The attack model is additive and random, and the paper doesn't explicitly address more complex attack types (e.g., stealthy attacks that mimic normal behavior).
  • The simulation uses a small network size.
  • Future Work:
    • The authors suggest adopting strategies from existing literature to optimally locate sensing nodes and design the sensor network for cost-effectiveness.
  • Exploring pruning strategies to modify the social network structure to improve observability and information flow for better estimation and detection.
  • Investigating more advanced attack models and detection mechanisms.

Summary updated

Abstract

This paper considers distributed estimation of linear systems when the state observations are corrupted with Gaussian noise of unbounded support and under possible random adversarial attacks. We consider sensors equipped with single time-scale estimators and local chi-square ($χ^2$) detectors to simultaneously opserve the states, share information, fuse the noise/attack-corrupted data locally, and detect possible anomalies in their own observations. While this scheme is applicable to a wide variety of systems associated with full-rank (invertible) matrices, we discuss it within the context of distributed inference in social networks. The proposed technique outperforms existing results in the sense that: (i) we consider Gaussian noise with no simplifying upper-bound assumption on the support; (ii) all existing $χ^2$-based techniques are centralized while our proposed technique is distributed, where the sensors \textit{locally} detect attacks, with no central coordinator, using specific probabilistic thresholds; and (iii) no local-observability assumption at a sensor is made, which makes our method feasible for large-scale social networks. Moreover, we consider a Linear Matrix Inequalities (LMI) approach to design block-diagonal gain (estimator) matrices under appropriate constraints for isolating the attacks.
BibTeX
@misc{doostmohammadian2021simultaneous,
  author = {Mohammadreza Doostmohammadian and Themistoklis Charalambous and Miadreza Shafie-khah and Nader Meskin and Usman A. Khan},
  title = {{Simultaneous Distributed Estimation and Attack Detection/Isolation in Social Networks: Structural Observability, Kronecker-Product Network, and Chi-Square Detector}},
  year = {2021},
  eprint = {2105.10639},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.10639},
}
Figure