PaperlayerView exact revision on arXiv

Source-linked AI summary

Secure State Estimation against Sensor Attacks in the Presence of Noise

Shaunak Mishra, Yasser Shoukry, Nikhil Karamchandani, Suhas Diggavi, Paulo Tabuada

arXiv:1510.02462v2math.OCcs.CRcs.ITcs.SYeess.SYmath.IT

TL;DR

The paper studies state estimation for noisy linear systems with an unknown, bounded-size set of arbitrarily corrupted sensors. It searches sensor subsets using Kalman-based detection and reports an estimator achieving lower-bound error guarantees, alongside a coding-theoretic interpretation for noiseless conditions.

  • Problem

    The paper addresses state estimation in noisy linear systems when an unknown subset of sensors is arbitrarily corrupted, with the number of attacked sensors bounded.

    Source: §I · p. 1

  • Method

    The estimator searches sensor subsets using Kalman-filter-based effective-attack detection, with SMT techniques proposed to speed the combinatorial search.

    Source: §I · p. 2, A. Overall Architecture · p. 7

  • Results

    The proposed state-estimation algorithm is stated to achieve the lower bounds on estimation error in the adversarial setup.

    Source: §I · p. 2

  • Takeaways & Limitations

    In the noiseless setting, the sparse-observability condition is related to Hamming-distance requirements for error detection and correction.

    Source: §I · p. 2

Abstract

from arXiv · show

We consider the problem of estimating the state of a noisy linear dynamical system when an unknown subset of sensors is arbitrarily corrupted by an adversary. We propose a secure state estimation algorithm, and derive (optimal) bounds on the achievable state estimation error given an upper bound on the number of attacked sensors. The proposed state estimator involves Kalman filters operating over subsets of sensors to search for a sensor subset which is reliable for state estimation. To further improve the subset search time, we propose Satisfiability Modulo Theory based techniques to exploit the combinatorial nature of searching over sensor subsets. Finally, as a result of independent interest, we give a coding theoretic view of attack detection and state estimation against sensor attacks in a noiseless dynamical system.

I. INTRODUCTION

The paper studies state estimation for noisy linear systems under bounded sparse sensor attacks, proposing Kalman-based subset search with optimal error guarantees and an SMT speedup. It also relates noiseless secure-estimation conditions to coding theory.

I. INTRODUCTION

  • In the three-sensor example, two sensors can be selected by checking consistency with their subset-based Kalman estimate over a sufficiently long window.The approach avoids treating noisy output differences alone as evidence of an attack, and attains the optimal estimation error for this setup.Source: §I · pp. 1–2
  • A Kalman-based detector screens sensor subsets for state estimation, and the proposed estimator is described as achieving the lower bounds on estimation error.SMT techniques exploit the combinatorial subset search to reduce search time.Source: §I · pp. 1–2
  • The paper gives a coding-theoretic interpretation of the noiseless sparse-observability condition, relating it to Hamming-distance requirements for error detection and correction.The interpretation is presented as an alternate proof of necessary and sufficient conditions for secure state estimation.Source: §I · p. 2

A. Notation

  • Notation defines vector support and set cardinality, indexed matrix rows, trace and eigenvalue symbols, covariance and sample averages, and elementwise matrix comparison.For a matrix and an index set, the text also defines the corresponding row-restricted matrix.Source: A. Notation · p. 2

B. System model

  • The system has linear state dynamics and sensor outputs combining the state, sensor noise, and attack; known inputs are omitted without loss of generality.Process and sensor noises have i.i.d. instantiations over time and are independent of each other.Source: B. System model · p. 2

II. SETUP

  • The model uses Gaussian process and sensor noises; a k-adversary can arbitrarily alter any k sensors, with a fixed attacked set and only causal noise knowledge.Apart from the causality assumptions, the attack corruptions are otherwise unrestricted in their statistical properties, boundedness, and time evolution.Source: B. System model · pp. 2–3

C. Effective Attack Detection Problem

The paper defines effective attacks by their effect on Kalman estimation error and frames their detection as an attack-indicator problem. It then characterizes a lower bound for secure estimation and defines optimality by attaining that bound.

C. Effective Attack Detection Problem

  • An attack is (ϵ, s)-effective when it raises empirical estimation error relative to the attack-free Kalman estimate using the same sensors.A sample average serves as the error proxy because attacked errors may not be ergodic.Source: C. Effective Attack Detection Problem · p. 3
  • The detection problem constructs a binary indicator that is 1 for an effective attack and 0 otherwise.The stated problem concerns the full sensor set.Source: C. Effective Attack Detection Problem · p. 3

D. Optimal Secure State Estimation Problem

  • Even an oracle that knows which sensors are attacked faces a lower bound tied to the worst-case Kalman estimate from p−k sensors.The proof considers attacks that make attacked outputs zero, leaving the remaining sensors as the best available estimation source.Source: D. Optimal Secure State Estimation… · pp. 3–4
  • A state estimate is defined as optimal when it is guaranteed to achieve the lower bound from Theorem 1 over the estimation window.The problem asks for estimates across a time window and uses sample averages because attacked errors may not be ergodic.Source: D. Optimal Secure State Estimation… · p. 4

III. SPARSE OBSERVABILITY AND (ϵ, s)-EFFECTIVE ATTACK DETECTION

The section defines sparse observability and develops a Kalman-filter-based detector that tests whether a sensor subset’s residuals match their attack-free behavior. The detector supports later secure state estimation by identifying subsets that pass the test.

III. SPARSE OBSERVABILITY AND (ϵ, s)-EFFECTIVE ATTACK DETECTION

  • The section presents sparse observability as the condition used to determine when attack detection and secure state estimation are solvable.Its detector is based on this condition and has a stated performance guarantee.Source: §III · p. 4, B. (ϵ, s)-Effective Attack Detector · p. 4

A. k-Sparse Observability

  • A system is k-sparse observable when it remains observable after any choice of k sensors is eliminated.The detector section uses sparse observability to establish its performance guarantees.Source: A. k-Sparse Observability · p. 4, §III · p. 4

1) Additional notation:

  • The section introduces observability matrices for individual sensors and sensor subsets, formed by stacking the corresponding sensor matrices.It also defines notation for sensor outputs and noises over a time window.Source: 1) Additional notation · p. 4

2) Attack Detection Algorithm:

  • The detector runs a Kalman filter on a sensor subset, forms block residues over a time window, and compares their sample covariance with its attack-free expectation.The attack-free covariance can be computed offline, without data from attack-free sensors.Source: 2) Attack Detection Algorithm · p. 5, 1) Additional notation · p. 5
  • The algorithm sets its attack flag to indicate no detected attack when the element-wise residue test passes; otherwise, it flags an attack.The test checks whether the window’s sample average of residue outer products is close to its attack-free expected value.Source: 2) Attack Detection Algorithm · p. 5, 1) Additional notation · p. 5

C. Performance Guarantees

The section gives performance guarantees for the residue-based detector and the secure state estimate. Under sparse-observability and adversary assumptions, sufficiently long windows yield high-probability guarantees, including detection of effective attacks.

IV. EFFECTIVE ATTACK DETECTION AND SECURE STATE ESTIMATION

  • The section introduces these guarantees as the basis for the main results on effective attack detection and secure state estimation.The proof uses large-window behavior, including the law of large numbers and a cross term with vanishingly small variance.Source: C. Performance Guarantees · pp. 5–6, §IV · p. 6

C. Performance Guarantees

  • For a 2k-sparse observable system, a k-adversary, and |s| ≥ p−k, an accepted subset’s estimation error trace is bounded by ϵ with high probability for sufficiently large N.The guarantee applies when ATTACK-DETECT returns no detected attack for subset s.Source: C. Performance Guarantees · p. 5
  • For sufficiently large N, the detector identifies any (ϵ, s)-effective attack with high probability.Its detection flag is compared with that of an oracle detector that knows the attacked sensors.Source: C. Performance Guarantees · p. 5

A. Attack detection

The paper uses sparse-observability-based detection to identify effective attacks and screen sensor subsets for state estimation. It also replaces exhaustive subset enumeration with an SMT-style Boolean and theory-solver search that prunes invalid candidates while preserving optimality.

A. Attack detection

  • For a k-sparse observable system and a k-adversary satisfying Assumptions 1–5, ATTACK-DETECT on all sensors identifies the effective-attack indicator with high probability for sufficiently large N.The proof requires the good sensors to form an observable system.Source: A. Attack detection · p. 6

B. Secure State Estimation

  • Algorithm 2 searches sensor subsets of size p−k and uses the first subset that passes ATTACK-DETECT for state estimation.It exhaustively checks the subsets until the detector indicates no effective attack.Source: B. Secure State Estimation · p. 6, A. Attack detection · p. 6
  • Under 2k-sparse observability and the stated adversary assumptions, Algorithm 2’s state estimate achieves the theorem’s error bound with high probability for sufficiently large N.The bound is stated for any ϵ > 0 and δ > 0.Source: B. Secure State Estimation · p. 6

V. REDUCING SEARCH TIME USING SATISFIABILITY MODULO THEORY SOLVING

  • The SMT-based search is proposed to reduce subset search time while preserving the optimality of the solution.It targets the combinatorial search performed by exhaustive subset enumeration.Source: §V · pp. 6–7
  • Smaller conflicting certificates can prune more candidate assignments; the figure’s three-variable example shows b3 ≥ 1 eliminating four combinations.The four excluded assignments have b3 = 0.Source: §V · p. 7, Figure 1 · p. 7

A. Overall Architecture

  • The SMT architecture encodes sensor-attack hypotheses as Boolean assignments and checks each candidate with ATTACK-DETECT in a theory-solver step.A failed candidate yields an UNSAT certificate that constrains the next Boolean search.Source: §V · p. 7, A. Overall Architecture · p. 7

B. Conflicting Certificates

The search procedure compacts conflict certificates to prune more sensor-subset candidates while preserving state-estimate optimality. In the residue-test experiment, only the attack-free subset passes the test.

B. Conflicting Certificates

  • Removing sensors from a conflicting set yields smaller UNSAT certificates, which prune more candidates and can improve search time.A certificate involving only b1 eliminates four samples, whereas one involving b1, b2, and b3 eliminates only one.Source: B. Conflicting Certificates · p. 7
  • Algorithm 3 preserves the optimality of the state estimate it computes for a 2k-sparse observable linear dynamical system under a k-adversary satisfying Assumptions 1–5.Source: B. Conflicting Certificates · p. 8
  • The paper does not analytically bound Algorithm 3’s worst-case iteration count; its practical speed advantage is supported by numerical results.The authors compare it with exhaustive search in Section VI.Source: B. Conflicting Certificates · p. 8, §VI · p. 8

A. Experiment 1: Residue test performance in Algorithm 2

B. Experiment 2: Performance of SMT-based Search

The experiments compare SMT-based and exhaustive sensor-subset search, while the coding-theoretic view relates sparse observability to attack resilience. In the noiseless setting, this view also extends to nonlinear systems.

B. Experiment 2: Performance of SMT-based Search

VII. SPARSE OBSERVABILITY: CODING THEORETIC VIEW

  • For θ-sparse observable systems, distinct initial states have observation vectors with minimum symbol Hamming distance θ + 1.This connects sparse observability to the coding-theoretic measure of distance between observation vectors.Source: §VII · p. 9
  • The coding view gives exact state estimation when 2k ≤ θ and permits detection of up to k ≤ θ sensor corruptions.The exact-estimation condition is stated as necessary and sufficient.Source: §VII · p. 9
  • For noiseless nonlinear systems, the same coding-theoretic interpretation yields necessary and sufficient conditions for attack detection and secure state estimation.The interpretation follows by defining θ-sparse observability analogously.Source: §VII · p. 10

APPENDIX

The appendix proof uses time-grouping and concentration arguments to establish the asymptotic behavior of the terms involved.

1) Proof of (16) using LLN:

  • The proof partitions the time window into n groups by time index modulo n, so observations within each group correspond to i.i.d. realizations.The groups each have size N_B.Source: 1) Proof of (16) using LLN · p. 10
  • The cross term has zero mean and vanishingly small variance, so Chebyshev’s inequality completes the proof of (17).The variance argument uses Cauchy–Schwarz to control the cross term.Source: 1) Proof of (16) using LLN · pp. 10–11
  • For sufficiently large N_B, the variance of each grouped term ζ_l becomes vanishingly small.The proof uses an intermediate result and the law of large numbers.Source: 1) Proof of (16) using LLN · p. 11

B. Bounds on the trace of product of symmetric matrices

The appendix states a trace bound for products of symmetric matrices and outlines how the paper’s prediction-filter results are adapted to filtering.

B. Bounds on the trace of product of symmetric matrices

C. Results for the filtering version of the Kalman filter

  • The paper uses the prediction version of the Kalman filter for its main results and says similar filtering-version results follow by the same techniques.The filtering setup and its effective-attack detector are then described.Source: C. Results for the filtering version… · p. 11

1) Filtering setup and additional notation:

2) ϵ-effective attack detector for filtering setup:

Algorithm 5 uses a Kalman filter over a sensor subset to estimate states across a time window, then applies a block-residue test to classify whether that subset is under attack.

2) ϵ-effective attack detector for filtering setup:

3) Performance guarantees for Algorithm 5:

For a 2k-sparse observable system and a k-adversary satisfying the stated assumptions, Lemma 4 gives a probability guarantee when Algorithm 5 declares a sensor subset attack-free. Its proof handles the filtering error’s dependence on current-time sensor noise.

3) Performance guarantees for Algorithm 5:

  • For a 2k-sparse observable system and a k-adversary satisfying Assumptions 1–3 and 6–7, Lemma 4 guarantees a probability bound when Algorithm 5 declares no attack on a subset of at least p−k sensors.For any ϵ > 0 and δ > 0, a sufficiently large window length N exists; the bound’s expression is not included in the supplied passage.Source: 3) Performance guarantees for… · p. 12
  • The proof differs from the prediction case because filtering error at time t depends on sensor noise at time t.Source: 3) Performance guarantees for… · p. 12
  • Within a subset of at least p−k sensors, the proof identifies an attack-free subset of at least p−2k sensors; sparse observability keeps the relevant minimum eigenvalues bounded away from zero.Source: 3) Performance guarantees for… · pp. 12–13
  • The filtering state-estimation guarantees follow from Lemma 4, with further derivation omitted for brevity.Source: 3) Performance guarantees for… · p. 13

D. Cross term analysis for filtering and proof of (42)

The filtering proof analyzes a cross term by partitioning the time window into groups, then bounding the mean and variance of each group’s contribution. Independence and large windows support the resulting vanishing-variance argument.

D. Cross term analysis for filtering and proof of (42)

Loading 1510.02462v2…