PaperlayerView exact revision on arXiv

Source-linked AI summary

Event-Triggered State Observers for Sparse Sensor Noise/Attacks

Yasser Shoukry, Paulo Tabuada

arXiv:1309.3511v3math.OCcs.CRcs.ITeess.SY

TL;DR

Sparse, otherwise arbitrary sensor attacks make state reconstruction in cyber-physical systems a security problem. This paper proposes two event-triggered observers—one batch and one recursive—and reports computationally efficient reconstruction of the state and attack signal, including an order-of-magnitude computation-time decrease.

  • Problem

    The paper addresses computationally efficient state reconstruction for discrete-time linear systems whose measurements are corrupted by sparse adversarial noise.

  • Method

    The paper proposes two event-triggered state observers: a projected gradient-descent algorithm and a recursive projected Luenberger observer.

  • Results

    The proposed algorithms reconstruct both the system state and sparse attack signal, with simulations showing an order-of-magnitude decrease in computation time.

  • Takeaways & Limitations

    Sparse observability characterizes solvability, while event-triggered implementations improve the timing performance of the proposed reconstruction algorithms.

Abstract

from arXiv · show

This paper describes two algorithms for state reconstruction from sensor measurements that are corrupted with sparse, but otherwise arbitrary, "noise". These results are motivated by the need to secure cyber-physical systems against a malicious adversary that can arbitrarily corrupt sensor measurements. The first algorithm reconstructs the state from a batch of sensor measurements while the second algorithm is able to incorporate new measurements as they become available, in the spirit of a Luenberger observer. A distinguishing point of these algorithms is the use of event-triggered techniques to improve the computational performance of the proposed algorithms.

I. INTRODUCTION

The paper addresses state reconstruction for linear systems with sparse, arbitrary sensor corruption, proposing two event-triggered observers designed for computational efficiency. The algorithms reconstruct both the system state and the sparse attack signal, with simulations reporting an order-of-magnitude reduction in computation time.

  • Proposed algorithms: The paper proposes two observers for discrete-time linear systems with sparsely corrupted measurements: a batch reconstruction method and a recursive Luenberger-like method.The recursive implementation incorporates new measurements as they become available.
  • Problem setting: The paper models attacked sensor measurements as sparse noise whose nonzero values may be arbitrary in magnitude, statistics, and temporal evolution.Measurements from unattacked sensors are noise-free, while attacked sensors can produce arbitrary real-valued errors.
  • Research gap: Prior steady-state approaches fail to exploit constraints imposed by continuous dynamics, which this paper uses for state reconstruction.Existing work is divided between steady-state and linear time-invariant dynamical models.
  • Computational design: Customized lightweight gradient-descent algorithms replace classical Lr\L1, r > 1 optimization to support implementation on computationally limited platforms.The proposed algorithms are designed to reconstruct both the state and the sparse noise or attack signal.
  • Evaluation: Numerical simulations show an order of magnitude decrease in computation time for the proposed algorithms.The paper also reports successful state reconstruction under different attacks in simulation.
  • Theoretical contributions: The paper characterizes solvability using sparse observability and develops event-triggered projected gradient-descent and projected Luenberger observer algorithms with convergence properties.These notions support the theoretical analysis of the proposed reconstruction methods.

II. THE SECURE STATE RECONSTRUCTION PROBLEM

The paper models sensor attacks as sparse, arbitrary measurement corruptions and seeks simultaneous reconstruction of a delayed system state and the attack sequence. A cyclic sparsity representation captures attacks whose sensor support remains fixed over time.

  • Cyclic Sparsity: Cyclic s-sparsity means each time slice is s-sparse and all slices share the same support, matching a fixed set of potentially attacked sensors.After reshaping the stacked vector as a matrix, attacked rows may contain arbitrary values while unattacked rows contain zeros.
  • Dynamics and Attack Model: The discrete-time linear system includes an s-sparse attack vector a(t) that alters sensor measurements, with s denoting the number of attacked sensors.Attack values have no assumed bounds, statistical properties, or temporal restrictions, and only an upper bound on s is known.
  • Dynamics and Attack Model: The attacker’s accessible sensor set remains constant, but attacked sensors and attack timing may vary, including attacks on all accessible sensors at every time.
  • Secure State Reconstruction: The objective is to reconstruct the delayed state x(t−τ +1) and the cyclic s-sparse attack vector E(t) from the last τ measurements.The attack vector stacks the attack signals over the measurement window.
  • Cyclic Sparsity: The formulation defines the cyclic s-sparse set S_s as vectors that are cyclic r-sparse for every r from 0 through s.
  • Problem Formulation: Using cyclic sparsity, the paper poses two reconstruction problems that lead to its two proposed algorithms.

C. Static Batch Optimization

The batch formulation estimates the state and sparse attack vector by minimizing measurement residuals over R^n × S_s. Its solution is unique exactly when the system is 2s-sparse observable, while computational constraints motivate a Luenberger-like alternative.

  • Static Batch Optimization: The batch problem estimates the state and attack vector as the minimizer of 1/2∥Y−Qẑ∥2^2 over R^n × S_s.The optimization is solved at every time instance using collected measurements and known inputs.
  • Static Batch Optimization: The batch estimate reconstructs a delayed state, from which the current state can be obtained by rolling the dynamics forward.When A is invertible, the current state can instead be recovered by rewriting the measurement equation in terms of x(t).
  • Luenberger-like Observer: New measurements may arrive before the batch optimization finishes, motivating a dynamical observer that incorporates measurements as they become available.
  • Luenberger-like Observer: The observer targets z*(t)=(x*(t−τ+1),E*(t)), where E*(t) is the attack sequence associated with the last τ corrupted outputs.
  • s-Sparse Observability: s-Sparse observability is equivalent to strong observability for every attack-support matrix formed from all possible supports of size at most s.
  • s-Sparse Observability: The batch objective has a unique solution if and only if the system is 2s-sparse observable.
  • Fundamental Limitation: Correct reconstruction is impossible when p/2 or more sensors are attacked, because removing 2s sensors can eliminate all rows of the measurement matrix.

B. s-Restricted Eigenvalue

The s-restricted eigenvalue gives a quantitative version of sparse observability and supports gradient-descent-based solutions to the reconstruction problems. Under 2s-sparse observability, this restricted eigenvalue is strictly positive, although computing it is combinatorial.

  • For a chosen set of p−s sensor indices, the construction removes the corresponding identity columns to form Q_Γs.
  • The s-restricted eigenvalue quantitatively characterizes sparse observability and is directly related to solving the reconstruction problems with gradient-descent-inspired methods.
  • The 2s-restricted eigenvalue δ2s is bounded below by a positive value when the system is 2s-sparse observable.
  • On cyclic 2s-sparse vectors, QTQ has a non-zero minimum eigenvalue despite Q having a non-trivial kernel.
  • Computing δ2s is combinatorial because it requires calculating eigenvalues over the relevant restricted matrices.

IV. EVENT TRIGGERED PROJECTED GRADIENT DESCENT

ETPG extends iterative hard thresholding to a setting where part of the signal is sparse and part follows linear dynamics. It alternates gradient and projection steps, using event triggering to adapt the number of gradient steps while maintaining Lyapunov stability.

  • ETPG extends iterative hard thresholding to reconstruct signals combining a sparse component with a component governed by linear dynamics.
  • The algorithm alternates gradient steps with projections because gradient updates do not generally preserve the desired sparsity constraints.
  • ETPG performs multiple gradient steps when needed, rather than fixing the number of gradient steps before each projection.
  • Event triggering monitors the Lyapunov candidate V and determines when gradient descent has compensated for projection-induced increases in V.
  • The event-triggered mechanism ensures that the blue subsequence converges, attaining stability in the Lyapunov sense.

B. The Projection Operator

The projection operator maps an estimate onto the set enforcing the required cyclic sparsity. Under 2s-sparse observability, the resulting ETPG algorithm converges to the unique reconstructed state when the attack affects no more than s sensors.

  • B. The Projection Operator: The projection operator Π maps z=(x,E) onto the closest point in R^n × S_s while preserving the state component x.
  • B. The Projection Operator: For the error component, Π′ sets to zero the p−s entries of E with the smallest magnitudes.
  • The ETPG convergence theorem assumes 2s-sparse observability and a 2s-restricted eigenvalue δ2s, and concludes convergence to z∗.
  • The algorithm correctly reconstructs the state when the attacker accesses no more than s sensors and the system is 2s-sparse observable.
  • ETPG generalizes NIHT by combining multiple gradient steps with event triggering, whereas NIHT uses one gradient step.
  • The Lyapunov function W is suitable for stability analysis but cannot design the algorithm because evaluating it requires prior knowledge of z∗.

1) Effect of the Projection Operator:

The convergence analysis separates the effects of projection and gradient descent, then uses the event-triggering condition to establish Lyapunov decrease. The inner loop reaches a prescribed projection accuracy after finitely many gradient steps, while direct pseudoinverse computation may be numerically problematic.

  • 1) Effect of the Projection Operator:: Under 2s-sparse observability and the stated conditions, recursive gradient steps bound the Lyapunov candidate after m steps.
  • 1) Effect of the Projection Operator:: For any ε>0, the projection error becomes at most ε after no more than the stated finite number of steps.
  • 1) Effect of the Projection Operator:: The analysis permits replacing the inner loop with a one-step projection onto the kernel of Q, reducing the algorithm to alternating two operations.
  • 1) Effect of the Projection Operator:: Computing Q+ can suffer numerical issues, so recursive methods such as gradient descent, Newton, or conjugate gradients are preferred.

3) Termination of the ETPG’s Inner Loop:

The paper establishes sufficient conditions ensuring that the ETPG inner loop terminates after finitely many iterations. The result relies on 2s-sparse observability, a restricted eigenvalue condition, and sparsity assumptions.

  • Under 2s-sparse observability with restricted eigenvalue δ2s, Proposition IV.10 provides sufficient conditions for inner-loop termination.The proposition bounds the required number of inner-loop iterations under the stated condition.
  • The analysis assumes that the relevant error vector E is at most 2s-sparse.

D. Stability of ETPG Algorithm

The ETPG algorithm is shown to converge in the Lyapunov sense by combining projection and gradient-descent updates with event-triggered termination. The proof also identifies a sparsity condition limiting one upper bound.

  • D. Stability of ETPG Algorithm: The paper establishes convergence of the ETPG algorithm using the termination of its inner loop.The convergence result is stated directly after the preceding inner-loop analysis.
  • D. Stability of ETPG Algorithm: Upper bound (IV.8) applies only when the estimated attack set is cyclic s-sparse.The paper explicitly limits this bound to that sparsity pattern.
  • D. Stability of ETPG Algorithm: The ETPG solution is introduced for Problem II.4, the Luenberger-like state-reconstruction problem.
  • D. Stability of ETPG Algorithm: Alternating multiple gradient-descent updates with projection steps decreases the Lyapunov candidate function V.The updates are monitored until their decrease compensates the increase introduced by the time-update step.

B. Convergence of the ETPL Observer

The ETPL observer is proven to converge under 2s-observability, a restricted eigenvalue condition, and an admissible Luenberger gain. The proof accounts for the time-update increase in the Lyapunov function.

  • B. Convergence of the ETPL Observer: Theorem V.2 states that the ETPL observer solves Problem II.4 under the paper’s observability and restricted-eigenvalue conditions.
  • B. Convergence of the ETPL Observer: The observer permits gains L = Q^TΣ when Σ is positive definite and λmax{Σ} < λ^-1.
  • B. Convergence of the ETPL Observer: The proof follows the ETPG convergence argument while accounting for the Lyapunov candidate’s increase during time updates.

C. Effect of Time Update

The ETPL observer compensates for the Lyapunov increase caused by each time update through event-triggered Luenberger and projection updates. In the UGV example, both algorithms reconstruct the state under sensor attacks, while ETPL is less noise-sensitive.

  • C. Effect of Time Update: The event-triggered Luenberger-update loop terminates, allowing its decrease in V to compensate for the time-update increase.
  • C. Effect of Time Update: The resulting ETPL dynamics satisfy lim_t→∞ W(ẑΠ(t)) = 0, so the estimate converges to the desired value.
  • C. Effect of Time Update: The UGV is resilient to one attack on either encoder, whereas attacking another sensor prevents 2s-sparse observability.
  • C. Effect of Time Update: In the UGV example, both ETPG and ETPL successfully reconstruct the state and enable the vehicle to reach its goal despite attacks.The experiments include random noise, step-and-ramp corruption, and replay attacks on motor encoders.
  • C. Effect of Time Update: ETPL is less sensitive to noise than ETPG because it uses all available sensor data as measurements arrive.
  • C. Effect of Time Update: The experiment reconstructs the state even though the assumed attacked-sensor set changes over time, because each single-sensor attack lasts sufficiently long.

B. Computational Performance

The paper compares computational timing and convergence behavior of ETPG and ETPL against an L1/Lr decoder under varying numbers of attacked sensors. ETPG and ETPL achieve faster execution, while ETPL trades shorter execution for longer convergence.

  • Timing evaluation: An evaluation compares ETPG and ETPL with the L1/Lr decoder using randomly generated systems and increasing numbers of attacked sensors.The experiments average results across random attack supports, attack signals, and initial conditions, without claiming statistical significance.
  • Execution time: Both ETPG and ETPL outperform the L1/Lr decoder by an order of magnitude in execution time.
  • Execution time: ETPG requires more execution time than ETPL because its outer loop requires additional Lyapunov-function processing.
  • Convergence time: ETPG and the L1/Lr decoder have equal execution and convergence times, whereas ETPL requires longer convergence than ETPG.Convergence time is measured until the estimate becomes ϵ-close to the state, with ϵ = 10^-6 in the example.
  • Timing tradeoff: The timing results illustrate a tradeoff between execution timing and reconstruction performance.Execution time affects the deployed algorithm's sampling-period choice, while convergence time reflects algorithm performance.
  • Algorithm design: The algorithms use event-triggered execution to determine online how many gradient steps are performed per projection.The paper identifies dynamic step-size adjustment and refined gradient methods as possible improvement directions.
Loading 1309.3511v3…