Computational Complexity of Secure State Reconstruction

15 concepts11 papers1 proposal

To safely control a cyber-physical system—such as an autonomous vehicle, a robotic arm, or a power grid—a controller must continuously estimate the system's internal state. This estimation relies on data streaming from a network of sensors. But if a sophisticated adversary hijacks a subset of these sensors and injects arbitrary, malicious lies, how can the system discover the truth?

If we knew exactly which sensors were compromised, the solution would be trivial: we could simply discard the corrupted streams and reconstruct the state using the remaining honest sensors. The core challenge of secure state reconstruction is that the compromised subset is entirely unknown. The system must simultaneously deduce what the true state is and which sensors are lying.

The Combinatorial Explosion

Why is this problem so computationally daunting? To find the true state, an estimator must isolate a subset of sensors whose measurements are mutually consistent with the system's known physical dynamics. As Mehrdad Showkatbakhsh et al. and Xiao Tan 0002 et al. observe, the number of possible combinations of clean and attacked sensors grows exponentially with the total number of sensors. This combinatorial explosion creates a severe processing bottleneck, making real-time deployment in large-scale systems highly impractical (Xusheng Luo et al.; Yanwen Mao et al.).

To formalize this barrier, Aritra Mitra et al. proved that secure state reconstruction is fundamentally NP-hard. They demonstrated this by reducing the problem to finding the sparsest solution to an underdetermined linear system—the exact same mathematical challenge that underpins compressed sensing. Because the attack vector is sparse (only a bounded number of sensors are attacked), finding the exact state requires solving an inherently intractable combinatorial puzzle.

Worse yet, the computational difficulty extends to the design phase. Verifying whether a specific sensor layout is resilient enough to withstand a given number of adversarial attacks is a coNP-complete problem (Yanwen Mao et al.; Aritra Mitra et al.). This means engineers cannot efficiently verify or guarantee the security of large-scale cyber-physical systems using exact methods. In related security contexts, such as identifying system identities within Hidden Markov Models under attack, the complexity can escalate even further to PSPACE-complete (S. Akshay et al.).

Isolating Hardness via Eigenspace Decomposition

Is secure state reconstruction always a lost cause? Not necessarily. The NP-hardness proofs establish that the problem is intractable for general linear systems, but specific structural properties can make it manageable.

Yanwen Mao et al. and Aritra Mitra et al. introduced a system decomposition technique based on generalized eigenspaces to isolate the "hard" and "easy" parts of a system's state space. The intuition relies on how the system's internal modes interact with its sensors. If a system's eigenvalues are sufficiently observable or possess a geometric multiplicity of one, the mathematical ambiguity introduced by the attacker vanishes. By breaking the system down into decoupled sub-problems, the authors showed that the state components corresponding to these well-behaved eigenvalues can be reconstructed in polynomial time (PTIME), bypassing the combinatorial nightmare.

Bypassing Reconstruction via Sets and Safety Filters

When a system cannot be neatly decomposed, researchers often change the objective. If finding the exact state is NP-hard, can we find a bounding region or ensure safety without full reconstruction?

One powerful alternative is set-based estimation. Instead of calculating a single point estimate, M. Umar B. Niazi et al. use geometric shapes called zonotopes to represent the set of all possible states. Even when facing stealthy attacks that deliberately hide within normal sensor noise bounds, this method guarantees that the true state remains trapped within the estimated zonotope, mitigating the need to explicitly evaluate every sensor subset combination.

Another paradigm shift focuses on safe control rather than state estimation. In autonomous systems, the ultimate goal is to avoid unsafe states (like crashes), not necessarily to know every coordinate perfectly. Xiao Tan 0002 et al. and Xiao Tan et al. developed secure safety filters using Control Barrier Functions (CBFs). Instead of trying to pinpoint which sensors are lying, their algorithms identify the collection of all "plausible" states consistent with the uncompromised sensor combinations. By ensuring that the control action keeps all plausible states safe, they guarantee system safety in real-time, completely sidestepping the exponential processing bottleneck of traditional state reconstruction.

Finally, optimization and data-driven methods offer alternative ways to smooth out the combinatorial landscape. For instance, Jiaqi Yan et al. leverage behavioral systems theory to reconstruct trajectories directly from data streams using convex optimization techniques like $\ell_1$-minimization and group LASSO, avoiding the need to identify an explicit mathematical model of the system first.

Key Foundational Work

When is the Secure State-Reconstruction Problem Hard? (2019) — contributed 5 concept elements to this direction.
An SMT-based approach to secure state estimation under sensor and actuator attacks (2017) — contributed 1 concept elements to this direction.
Classification Among Hidden Markov Models (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_resilience_verification_complexity_13b5f05f,
  title = {resilience verification complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/resilience-verification-complexity/rdr_13b5f05fb722447f9d0da41d9ea9a641},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_resilience_verification_complexity_13b5f05f_v1,
  title = {resilience verification complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/resilience-verification-complexity/rdr_13b5f05fb722447f9d0da41d9ea9a641/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake