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.  
ChallengesWe 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. For instance, as we consider the interactions of both players (the defender and the adversary) on each transmission link of the power grid, the number of possible states will be two to the power of the number of transmission links. 

Our approachWe are considering the use of approximation to make the computation complexity manageable by exploiting the fact that users are only interested to know their optimal strategy in a few states (the interesting states, such as the state when the system is running normally, or one or a few transmission links are down) instead of all of the states in the Markov games formulation. However, we cannot only evaluate the interesting states because other noninteresting states can also affect these interesting states to different extends. 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 relativelysimple power systems are promising. We are looking for computational resources to compute the results without approximation to compare the performance with our approximation approach using more complicated and realistic power grid topologies. Our resultsFig 1 depicts the power system, a simple 9bus system with 9 transmission links, we used for the preliminary evaluation. Table 1 shows the percentage difference in the computed state value (the amount of power loads to be shed in order to maintain the stability of the power grid) using the approximation algorithm with the exact results for different threshold values, and Fig 2 depicts the computation time of the approximation algorithm using three computation threads as a function of threshold value. A noninteresting state is only evaluated if its effect on any interesting states is greater than the threshold. We can observe from the table and the figure that the approximation algorithm is able to reduce the computation time without much sacrifice in the state value computed. 
Fig 1. Standard WCSS 9bus system.
Table 1. Percentage difference of state values.
Fig 2. Runtime of the approximation algorithm.

CollaborationsThis work is a collaboration with Dr. Nageswara S. V. Rao from the Oak Ridge National Laboratory, TN, US. Publications
