  This article studies a fundamental problem of security of cyber-physical
systems (CPSs): that of detecting, almost surely, the presence of malicious
components in the CPS. We assume that some of the actuators may be malicious
while all sensors are honest. We introduce a novel idea of separability of
state trajectories generated by CPSs in two situations: those under the nominal
no-attack situation and those under the influence of an attacker. We establish
its connection to security of CPSs in the context of detecting the presence of
malicious actuators (if any) in them. As primary contributions we establish
necessary and sufficient conditions for the aforementioned detection in CPSs
modeled as Markov decision processes (MDPs). Moreover, we focus on the
mechanism of perturbing the pre-determined control policies of the honest
agents in CPSs modeled as stochastic linear systems, by injecting a certain
class of random process called private excitation; sufficient conditions for
detectability and non-detectability of the presence of malicious actuators
assuming that the policies are randomized history dependent and randomized
Markovian, are established. Several technical aspects of our results are
discussed extensively.
