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.


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. 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 approach

We 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 non-interesting states can also affect these interesting states to different extends. 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 relatively-simple 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 results

Fig 1 depicts the power system, a simple 9-bus 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 non-interesting 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 9-bus system.
Table 1. Percentage difference of state values.
Fig 2. Runtime of the approximation algorithm.


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


  • Chris Y. T. Ma, David K. Y. Yau, Xin Lou, and Nageswara S. V. Rao
    Markov Game Analysis for Attack-Defense of Power Networks under Possible Misinformation
    IEEE Transactions on Power Systems
    Volume: 28, Issue: 2, Pages: 1676 – 1686, May 2013 [pdf]
  • Chris Y. T. Ma, David K. Y. Yau, and Nageswara S. V. Rao
    Scalable Solutions of Markov Games for Smart-Grid Infrastructure Protection
    IEEE Transactions on Smart Grid, Special Section on Smart Grid Communications Systems: Reliability, Dependability, and Performance
    Volume: 4, Issue: 1, Pages: 47 – 55, March 2013 [pdf]
  • Chris Y. T. Ma, David K. Y. Yau, Xin Lou, and Nageswara S. V. Rao
    Extended Abstract: Markov Game Analysis for Attack and Defense of Power Networks
    In Proceedings of the International Conference on Applied Cryptography and Network Security (ACNS’12) (Industrial Track)
    Singapore, June 2012 [pdf]