On the Application of Relative Entropy in Sequential Detection and Cyber-Physical Security

As a measure of difference between two probability distributions, relative entropy (or Kullback-Leibler divergence) is of fundamental importance in many fields including information theory and detection theory. In this dissertation, we formulate and solve two major problems in which relative entropy plays an important role.

We first study the problem of binary sequential hypothesis testing using multiple sensors with associated observation costs. The objective is to find a sequential detection rule and a sensor selection strategy (SSS) such that the expected total observation cost is minimized when subject to constraints on reliability and sensor usage. We consider randomized SSS in which a sensor can be selected randomly based on a specified probability distribution at each time step. We present two types of scheme — an off-line SSS and an on-line SSS. For the off-line schemes, the sensor selection probability vector is fixed and not updated. For this problem, we begin by first showing that the sequential probability ratio test is the optimal sequential detection rule. Further, by characterizing the optimal sensor selection probability vector, efficient algorithms for obtaining the optimal sensor selection probability vector are derived. In particular, a special class of problems in which the algorithm has complexity that is linear in the number of sensors is identified. For the on-line SSS, the sensor selection probability can be adaptively updated according to the sensor selected and measurements obtained in the past. We begin by providing a dynamic programming interpretation of the optimization problem. By partitioning the state space for sensor selection into three regions, we propose a novel approach that solves the on-line sensor selection problem by minimizing the cost-to-go at every step.

In the second part of the dissertation, we consider security for cyber-physical systems. Suppose that a linear time-invariant plant regulated by an output feedback control law. A malicious attacker can hijack and replace the control signal or the measurement data by an arbitrary attack sequence. The objective of the attacker is to maximize the estimation error of the Kalman filter (which in turn quantifies the degradation of the control performance), while remaining undetected. We introduce a notion of stealthiness to quantify the difficulty of detecting an attack in progress by the controller using any possible detection algorithm. For a desired level of stealthiness, we quantify the largest estimation error that an attacker can induce, and also analytically characterize an optimal attack strategy. Because our bounds are independent of the detection mechanism implemented by the controller, our analysis characterizes the fundamental security limitations of stochastic cyber-physical systems.