
Optimal Defense Strategy

As a cyberphysical 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. 

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 lookahead 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 noninteresting states are important enough to be evaluated together with the interesting states, and preliminary results of applying the algorithm on a simple 9bus power system are promising.
More


FaultTolerant Communication

The security of a complex interconnected cyberphysical 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 faulttolerant way, what will the communication complexity be?


Our Approach
We study the faulttolerant 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 faulttolerant communication complexity lower bounds under increasing time complexity of the SUM protocol. Our results also imply the optimality (within polylog factors) of some recent faulttolerant protocols for computing SUM via duplicateinsensitive techniques, thereby answering an open research question.
More
