  This paper discusses the problem of estimating the state of a linear
time-invariant system when some of its sensors and actuators are compromised by
an adversarial agent. In the model considered in this paper, the malicious
agent attacks an input (output) by manipulating its value arbitrarily, i.e., we
impose no constraints (statistical or otherwise) on how control commands
(sensor measurements) are changed by the adversary. In the first part of this
paper, we introduce the notion of sparse strong observability and we show that
is a necessary and sufficient condition for correctly reconstructing the state
despite the considered attacks. In the second half of this work, we propose an
estimator to harness the complexity of this intrinsically combinatorial
problem, by leveraging satisfiability modulo theory solving. Numerical
simulations demonstrate the effectiveness and scalability of our estimator.
