  Given a linear dynamical system affected by noise, we study the problem of
optimally placing sensors (at design-time) subject to a sensor placement budget
constraint in order to minimize the trace of the steady-state error covariance
of the corresponding Kalman filter. While this problem is NP-hard in general,
we consider the underlying graph associated with the system dynamics matrix,
and focus on the case when there is a single input at one of the nodes in the
graph. We provide an optimal strategy (computed in polynomial-time) to place
the sensors over the network. Next, we consider the problem of attacking (i.e.,
removing) the placed sensors under a sensor attack budget constraint in order
to maximize the trace of the steady-state error covariance of the resulting
Kalman filter. Using the insights obtained for the sensor placement problem, we
provide an optimal strategy (computed in polynomial-time) to attack the placed
sensors. Finally, we consider the scenario where a system designer places the
sensors under a sensor placement budget constraint, and an adversary then
attacks the placed sensors subject to a sensor attack budget constraint. The
resilient sensor placement problem is to find a sensor placement strategy to
minimize the trace of the steady-state error covariance of the Kalman filter
corresponding to the sensors that survive the attack. We show that this problem
is NP-hard, and provide a pseudo-polynomial-time algorithm to solve it.
