PaperlayerView exact revision on arXiv

Source-linked AI summary

Byzantine-Resilient Distributed Observers for LTI Systems

Aritra Mitra, Shreyas Sundaram

arXiv:1802.09651v2eess.SYcs.SY

TL;DR

Distributed state estimation must contend with local-only communication and potentially adversarial sensors. The paper characterizes necessary conditions and develops a local-filtering strategy with graph-based guarantees; its strong-robustness condition can be checked in polynomial time.

  • Problem

    The paper asks how to estimate an LTI system’s state over neighbor-constrained sensor networks when nodes may behave arbitrarily under Byzantine attacks.

    Source: §1 · p. 1, §2 · p. 4

  • Method

    It derives necessary measurement and communication conditions and develops a local-filtering algorithm whose distributed implementation depends on graph-theoretic conditions.

    Source: §1 · p. 2, §6.1 · p. 10, §9 · p. 13

  • Results

    The proposed strategy enables noncompromised nodes to recover the full state when network conditions hold, and strong-robustness can be checked in polynomial time.

    Source: §1 · p. 2, §9 · p. 13

  • Takeaways & Limitations

    Strong-robustness provides a polynomial-time-checkable topological condition for determining whether the proposed approach applies.

    Source: §1 · p. 2

    Whether the stated necessary conditions are also sufficient remains an open question.

    Source: §3 · p. 6

Abstract

from arXiv · show

Consider a linear time-invariant (LTI) dynamical system monitored by a network of sensors, modeled as nodes of an underlying directed communication graph. We study the problem of collaboratively estimating the state of the system when certain nodes are compromised by adversaries. Specifically, we consider a Byzantine adversary model, where a compromised node possesses complete knowledge of the system dynamics and the network, and can deviate arbitrarily from the rules of any prescribed algorithm. We first characterize certain fundamental limitations of any distributed state estimation algorithm in terms of the measurement and communication structure of the nodes. We then develop an attack-resilient, provably correct state estimation algorithm that admits a fully distributed implementation. To characterize feasible network topologies that guarantee success of our proposed technique, we introduce a notion of `strong-robustness' that captures both measurement and communication redundancy. Finally, by drawing connections to bootstrap percolation theory, we argue that given an LTI system and an associated sensor network, the `strong-robustness' property can be checked in polynomial time.

1 Introduction

The paper addresses the challenge of resilient state estimation when sensors communicate only with nearby nodes, rather than sending all measurements to a central location. It sets out necessary conditions, a distributed filtering approach, and a graph property for characterizing feasible networks.

1 Introduction

  • Local communication avoids delays and bottlenecks from routing all sensor information centrally, but makes reliable operation under sensor faults or adversarial attacks a key challenge.Prior security work often assumes measurements are available at one location, unlike this paper’s neighbor-constrained setting.Source: §1 · p. 1
  • Earlier distributed estimation work, lacked theoretical success guarantees and graph-theoretic conditions, while this paper develops both for arbitrary adversarial behavior.The paper also distinguishes its approach from [28], which considers a restricted class of attack inputs.Source: §1 · p. 2
  • The paper characterizes necessary measurement and communication conditions for any algorithm to solve distributed state estimation under arbitrary adversarial behavior.The authors say these conditions generalize impossibility results for centralized systems with sensor attacks.Source: §1 · p. 2
  • A distributed filtering algorithm enables each uncompromised node to recover the entire state dynamics when specified graph conditions hold.The paper provides a thorough analysis of the filtering scheme.Source: §1 · p. 2
  • Strong-robustness characterizes networks where the proposed approach applies, and the property can be checked in polynomial time.The paper says its framework extends earlier work to arbitrary system spectra, including complex and possibly repeated eigenvalues; it also adds the necessary-condition analysis and polynomial-time check.Source: §1 · p. 2

2 System and Attack Model

The model assigns partial measurements of an LTI system to nodes in a directed communication network, each tasked with estimating the full state. It studies whether regular nodes can do so despite locally bounded Byzantine adversaries, under specified operating assumptions.

2 System and Attack Model

  • Each node estimates the full LTI state from its local measurements, if any, and information received from neighbors; the collective measurement pair must be detectable, though individual node pairs need not be.Information exchange is necessary for nodes whose local measurements do not make their individual system pair detectable.Source: §2 · p. 3
  • Adversaries know the network topology, system dynamics, and algorithm, while regular nodes follow causal, synchronous, deterministic algorithms with identically initialized iterative quantities.The causal and deterministic assumptions apply only to regular nodes.Source: §2 · p. 3
  • The adversarial set is f-local when each non-adversarial node has at most f adversarial neighbors; regular nodes do not know adversaries’ identities or number.The model assumes nodes are programmed to tolerate up to f adversaries in the network or in their neighborhood, depending on whether the f-total or f-local model is used.Source: §2 · p. 3
  • In the illustrated network, nodes 1–3 detect λ1 and nodes 8–10 detect λ2; H={4,5,6,7} is a 1-local pair cut for both virtual sources, but no 1-total pair cut exists.The figure identifies {1,2,3} and {8,9,10} as the minimal critical sets for the two modes.Source: Figure 1 · p. 4
  • The goal is for every regular node’s estimate to converge to the true state despite any f-locally bounded set of Byzantine adversaries.Adversaries may collude, deviate arbitrarily, and send different estimates to different neighbors at the same time.Source: §2 · pp. 3–4
  • The interplay of node measurements and communication structure imposes necessary conditions on whether the estimation problem is solvable, regardless of algorithm choice.Source: §2 · p. 4

3 Fundamental Limitations of any Distributed State Estimation Algorithm

The section establishes necessary measurement and communication conditions for resilient distributed state estimation under Byzantine attacks. Its results bound adversary tolerance and show how detectability requirements translate into sensor redundancy.

Necessary conditions

  • If an f-local pair cut exists with respect to s_i for a minimal critical set, no causal, synchronous, deterministic algorithm can solve Problem 1.The proof couples two executions with swapped adversarial sets, leaving nodes in Y unable to distinguish different initial states from identical information.Source: §3 · pp. 4–5
  • For f-total resilience, no f-total pair cut may exist; after removing any set D_i of at most 2f nodes in X_i, the remaining nodes reaching i must make (A, C_i ∪ P_i) detectable.These equivalent conditions combine graph structure and system detectability; when f = 0, the conditions reduce to detectability of every source component.Source: §3 · p. 5

Implications

  • The total number of adversaries must satisfy f < k, where k is the smallest positive integer yielding a k-total pair cut for a minimal critical set.This gives an upper bound on the number of adversaries that can be tolerated.Source: §3 · p. 6
  • Every minimal critical set must contain at least 2f + 1 nodes; with distinct eigenvalues, each unstable eigenvalue must be detectable by at least 2f + 1 nodes.The eigenvalue-specific requirement follows from the PBH test and the critical-set size condition.Source: §3 · p. 6
  • The proposed estimation strategy identifies locally detectable and undetectable eigenvalues, then uses separate estimation strategies for their associated subspaces.Source: §3 · p. 6
  • Open questions include efficient computation of k and whether the stated necessary conditions are also sufficient for resilient estimation.The main computational burden in finding k comes from identifying all minimal critical sets.Source: §3 · p. 6

4 Resilient Distributed State Estimation

The estimation scheme separates state modes detectable locally from modes that require resilient information exchange. LFRE uses filtered neighbor estimates to recover the latter, while local Luenberger observers recover detectable modes.

4.1 Preliminaries

  • Nodes locally estimate detectable state modes with Luenberger observers after transforming the system into real Jordan coordinates.The transformation separates the state into portions associated with real eigenvalues and non-real conjugate pairs.Source: §4.1 · pp. 6–7
  • For an eigenvalue a node cannot detect, source nodes use Luenberger observers while non-source nodes rely on resilient consensus to estimate that mode.The source set for each unstable eigenvalue comprises nodes able to detect it.Source: §4.1 · p. 7

4.2 Local-Filtering Based Resilient Estimation

  • LFRE sorts each received mode component and removes the f largest and f smallest neighbor estimates before updating the estimate.The algorithm uses only a designated subset of neighbors, and its weights can be chosen to achieve exponential convergence when they satisfy its rules.Source: §4.2 · pp. 7–8
  • The authors do not optimize LFRE weights for noise performance, and disregarding neighbor estimates without attacks may potentially degrade that performance.For f = 0, the paper states exponential convergence without noise and bounded mean square error under i.i.d. noise with bounded second moments, if the stated topological conditions hold.Source: §4.2 · p. 8

5 Analysis of the Resilient Distributed Estimation Strategy

The analysis uses a mode-specific MEDAG to organize redundant information flow from source nodes to non-source nodes. If such a graph exists for each relevant eigenvalue, LFRE lets every regular node asymptotically estimate the plant state despite f-locally bounded Byzantine adversaries.

5 Analysis of the Resilient Distributed Estimation Strategy

  • In the illustrated f = 1 example, nodes 2 and 3 occupy level 0, nodes 4–6 level 1, and node 7 level 2.For A = {1}, each non-source node has at least three neighbors.Source: Figure 2 · p. 9
  • A MEDAG supplies each non-source node at least 2f + 1 neighbors and places its regular neighbors in strictly lower levels.These properties organize redundant information flow from source nodes toward non-source nodes for each relevant eigenvalue.Source: §5 · pp. 8–9
  • If a MEDAG exists for every eigenvalue in Ω_U(A), LFRE lets each regular node asymptotically estimate the plant state despite any f-locally bounded Byzantine adversaries.Ω_U(A) includes unstable eigenvalues for which some nodes are not source nodes.Source: §5 · pp. 8–9

6 Checking the Existence of a MEDAG

The distributed initialization constructs, for each relevant eigenvalue, a MEDAG that specifies which neighbors nodes use during estimation. Once the construction terminates, its subgraphs support the state-estimation guarantee, and the complete scheme combines this initialization with local observers and LFRE.

6 Checking the Existence of a MEDAG

  • For each relevant eigenvalue, the MEDAG construction has source nodes broadcast first; non-source nodes join after receiving “1” from 2f + 1 distinct neighbors.Joining nodes record those neighbors as parents, broadcast “1,” and stop listening for further messages.Source: §6 · pp. 9–10
  • If construction terminates, its subgraph contains no directed cycles among regular nodes and satisfies the MEDAG properties for f-local sets containing the design-phase misbehaving nodes.The returned neighbor sets determine which information each node uses in LFRE.Source: §6 · pp. 9–10

6.1 Summary of the Resilient Distributed State Estimation Scheme

  • The full scheme transforms the state, constructs MEDAGs, estimates locally detectable modes with Luenberger observers, and estimates undetectable modes with LFRE.The MEDAG construction and estimation steps form the design and estimation phases, respectively.Source: §6.1 · p. 10
  • When the scheme's graph conditions hold, it admits a fully distributed implementation under worst-case adversarial behavior.If design-phase nodes misbehave, the scheme does not guarantee estimation for those nodes, which are contained in the adversarial set.Source: §6.1 · p. 10, §6 · p. 10

7 Feasible Graph Topologies

Strong robustness characterizes graph conditions under which the proposed algorithm can construct the required MEDAGs and succeed. The paper connects this property to bootstrap percolation to provide a polynomial-time feasibility check, with a tighter condition when attacks occur only during estimation.

7 Feasible Graph Topologies

  • Strong (3f + 1)-robustness with respect to each relevant source set guarantees that the MEDAG construction terminates and the proposed algorithm solves the estimation problem.The (3f + 1) threshold accounts for adversaries that transmit no messages during construction.Source: §7 · p. 11
  • If adversarial behavior is restricted to estimation, strong (2f + 1)-robustness with respect to each relevant source set is necessary and sufficient for the algorithm to solve the problem.This condition is for the paper's algorithm and need not be necessary for solving the problem in general.Source: §7 · p. 11
  • Losing k source nodes, for k < r, leaves an r-feasible network at least (r − k)-feasible.The paper also notes that measurement structure bounds network robustness and that non-source nodes unable to estimate the full state alone have in-degree at least r.Source: §7 · p. 12
  • A set percolates under threshold-r bootstrap percolation exactly when the graph is strongly r-robust with respect to that set.For a fixed initial set, the process takes O(N|E|) time to simulate.Source: §7 · p. 12
  • The paper gives O(nN|E|) time to verify r-feasibility for a system of dimension n and an N-node graph.This yields a polynomial-time check of whether the approach applies to a given system and network.Source: §7 · pp. 12–13

8 Simulations

The simulations compare ordinary distributed observer updates with the LFRE algorithm under a single adversarial node. Although the network is strongly 3-robust, the ordinary observer diverges under a small constant attack, while LFRE counteracts it.

8 Simulations

  • Source nodes 2 and 3 use Luenberger observers with gain 1.5, chosen to ensure stability.Nodes 1, 2, and 3 directly measure the state; the other nodes have zero measurements.Source: §8 · p. 13
  • A single adversarial node transmitting a small constant signal makes non-source estimates diverge under the non-resilient observer, but LFRE counteracts the attack.The example uses a = 2 and ϵ = 0.001; the network is strongly 3-robust.Source: §8 · p. 13
  • The simulation sets x[0] = 0.5 and initializes each node estimate to a random number between 0 and 1.Source: §8 · p. 13

9 Conclusions

The paper identifies necessary feasibility conditions, develops a local-filtering algorithm, and uses strong r-robustness to characterize networks where the strategy succeeds. It also notes open work on relaxing worst-case conditions and extending the framework to network-induced issues.

9 Conclusions

  • The paper identifies necessary measurement and communication conditions for distributed state estimation to remain feasible under worst-case adversarial behavior.Source: §9 · p. 13
  • The local-filtering algorithm enables noncompromised nodes to recover the full state, while strong r-robustness characterizes networks that guarantee success.Source: §9 · p. 13
  • Future work could seek necessary and sufficient conditions, relax worst-case assumptions, and address packet drops, delays, and asynchronicity.Source: §9 · p. 13

A Proof of Theorem 2

The proof establishes the two directions of Theorem 2 by contraposition, relating measurement detectability after node removal to the existence of an f-total pair cut.

A Proof of Theorem 2

  • For one direction, violation of the detectability condition yields a critical set and a virtual-node graph with an f-total pair cut, violating the graph condition.The construction adds directed edges from virtual node s to each node in F.Source: A Proof of Theorem 2 · p. 15
  • For the reverse direction, an f-total pair cut either leaves a node unreachable outside Y or yields a removed set D_i of at most 2f nodes after which only Y can reach it.Because (A, C_Y) is not detectable, that node cannot estimate the state and the detectability condition is violated.Source: A Proof of Theorem 2 · p. 15

B Proof of Theorem 4

The proof shows that each regular node can asymptotically recover the full state by estimating its detectable components locally and propagating estimates of the remaining eigencomponents through MEDAG levels.

B Proof of Theorem 4

  • Each regular node first estimates the components associated with its detectable eigenvalues using a locally constructed Luenberger observer.The proof then treats recovery of the components associated with the remaining eigenvalues.Source: B Proof of Theorem 4 · p. 15
  • Induction over MEDAG levels extends convergence to every regular node, which can then asymptotically estimate the full state.The proof gives the same conclusion for real and non-real eigenvalues.Source: B Proof of Theorem 4 · pp. 15–16
  • For an undetectable eigenvalue, the proof partitions received estimates by component and discards the f highest and f lowest values before forming an update from the remaining set.Under the f-local adversary model, the extreme sets contain regular nodes, bounding the update through regular estimates.Source: B Proof of Theorem 4 · p. 16
  • Each updated error component lies in the convex hull of corresponding neighbor errors, and regular nodes at the initial MEDAG level converge to the eigencomponent.Source: B Proof of Theorem 4 · p. 16

C Proof of Theorem 7

The proof establishes sufficiency by showing that the stated conditions ensure MEDAG construction terminates for every relevant eigenvalue. For necessity, it argues that failure of strong robustness contradicts a required MEDAG property.

C Proof of Theorem 7

  • The stated conditions guarantee termination of MEDAG construction for every λ_j, establishing sufficiency.The remaining sufficiency argument follows the proof of Theorem 6.Source: C Proof of Theorem 7 · p. 16
  • The algorithm requires a MEDAG for every relevant λ_j when all nodes behave regularly.The proof uses this requirement to establish necessity.Source: C Proof of Theorem 7 · p. 16
  • If strong (2f + 1)-robustness fails, a nonempty set C is not (2f + 1)-reachable, contradicting the MEDAG neighbor requirement.The proof argues that nodes in the selected MEDAG levels have neighbors only outside C, while C's lack of reachability leaves them with fewer than 2f + 1 neighbors.Source: C Proof of Theorem 7 · pp. 16–17

D The Strong r-robustness Property of Random Graphs

This section characterizes when random sensor-network topologies are r-feasible, focusing on Erdős–Rényi, Barabási–Albert, and two-dimensional random geometric graphs. Its results connect source-set percolation to feasibility and to the algorithm’s Byzantine-adversary tolerance.

Section overview

Barabási–Albert graphs

  • Adding nodes with incoming edges from at least r existing nodes preserves r-feasibility; proportional neighbor selection yields the Barabási–Albert construction.The paper presents this construction as a way to expand an attack-resilient network without reducing its tolerated adversary count.Source: D The Strong r-robustness Property of… · p. 17

Erdős–Rényi random graphs

  • If N^-1 ≪ p ≪ N^-1/2, an Erdős–Rényi graph is r-feasible w.h.p. iff Np − (ln N + (r − 1)ln ln N) → ∞.Source: D The Strong r-robustness Property of… · p. 17
  • For p ≫ N^-1/r, Erdős–Rényi graphs are r-feasible w.h.p. when each source set has size at least r.The result concerns randomly chosen source sets for each relevant eigenvalue.Source: D The Strong r-robustness Property of… · p. 17
  • Under either Erdős–Rényi condition, each regular node can asymptotically estimate the state despite any ⌊(r − 1)/3⌋-locally bounded Byzantine adversarial set.The paper also notes that source-set size must scale with network size in one regime, while sufficiently large edge probability permits the minimum constant size.Source: D The Strong r-robustness Property of… · p. 17

Random geometric graphs

Loading 1802.09651v2…