Theory

Optimal Defense Strategy

As a cyber-physical system becomes smarter, more communications will take place within the network, and more vulnerabilities can be exploited by an adversary whose goal is to disrupt the system. Our goal is to develop a tool to assist the system defender to allocate her resource on protecting the system, such as making the communication channel or the software more secure, building a larger response team to speedup the recovery time after an attack, or preparing backup systems to replace the original one. We will illustrate the approach using the smart grid as an example. defense-strategy-state-machine

Our Approach

We use Markov games to model the continual interactions between the defender and the adversary on various components of the smart grid system. Markov games are the desired approach to model the continual interactions between the defender and the adversary because Markov games incorporate the look-ahead horizons, which allow the defender and the adversary to optimize their respective actions considering the future impact of their present moves. However, complexity of using Markov games is very high when the number of states of the power system is large.

Our Results

We have developed an approximation algorithm to decide which non-interesting states are important enough to be evaluated together with the interesting states, and preliminary results of applying the algorithm on a simple 9-bus power system are promising.

More

Fault-Tolerant Communication

The security of a complex interconnected cyber-physical system like a smart grid critically depends on its capability to correctly and timely compute various functions with inputs held by distributed sensors (e.g. computing the total power being consumed by certain types of end loads), even when its communication system is under attacks. Thus, a natural question to ask is:

If we want to compute a certain function in a fault-tolerant way, what will the communication complexity be?

fault-tolerant-cc

Our Approach

We study the fault-tolerant communication complexity of SUM function with the following two natural assumptions: (1) we assume that the special root node who needs to learn the final result never fails; (2) we allow the computation to ignore/omit the inputs held by nodes that have failed or been disconnected from the root due to other nodes’ failures.

Our Results

Since there is a tradeoff between communication complexity and time complexity, we prove a series of fault-tolerant communication complexity lower bounds under increasing time complexity of the SUM protocol. Our results also imply the optimality (within polylog factors) of some recent fault-tolerant protocols for computing SUM via duplicate-insensitive techniques, thereby answering an open research question.

More