Skip to main content
SpringerLink
Log in

A Large-Scale Markov Game Approach to Dynamic Protection of Interdependent Infrastructure Networks

  • Conference paper
  • First Online:
Decision and Game Theory for Security (GameSec 2017)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 10575))

Included in the following conference series:

Abstract

The integration of modern information and communication technologies (ICTs) into critical infrastructures (CIs) improves its connectivity and functionalities yet also brings cyber threats. It is thus essential to understand the risk of ICTs on CIs holistically as a cyber-physical system and design efficient security hardening mechanisms. To this end, we capture the system behaviors of the CIs under malicious attacks and the protection strategies by a zero-sum game. We further propose a computationally tractable approximation for large-scale networks which builds on the factored graph that exploits the dependency structure of the nodes of CIs and the approximate dynamic programming tools for stochastic Markov games. This work focuses on a localized information structure and the single-controller game solvable by linear programming. Numerical results illustrate the proper tradeoff of the approximation accuracy and computation complexity in the new design paradigm and show the proactive security at the time of unanticipated attacks.

This research is partially supported by NSF grants EFRI-1441140, SES-1541164, CNS-1544782, DOE grant DE-NE0008571, and a DHS CIRI grant.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Chen, J., Zhu, Q.: Interdependent network formation games with an application to critical infrastructures. In: American Control Conference (ACC), pp. 2870–2875 (2016)

    Google Scholar 

  2. Chen, J., Zhu, Q.: Optimal contract design under asymmetric information for cloud-enabled internet of controlled things. In: Zhu, Q., Alpcan, T., Panaousis, E., Tambe, M., Casey, W. (eds.) GameSec 2016. LNCS, vol. 9996, pp. 329–348. Springer, Cham (2016). doi:10.1007/978-3-319-47413-7_19

    Google Scholar 

  3. Chen, J., Zhu, Q.: Resilient and decentralized control of multi-level cooperative mobile networks to maintain connectivity under adversarial environment. In: IEEE Conference on Decision and Control (CDC), pp. 5183–5188 (2016)

    Google Scholar 

  4. Chen, J., Zhu, Q.: Security as a service for cloud-enabled internet of controlled things under advanced persistent threats: a contract design approach. IEEE Trans. Inf. Forensics Secur. 12(11), 2736–2750 (2017)

    Article  Google Scholar 

  5. De Farias, D.P., Van Roy, B.: On constraint sampling in the linear programming approach to approximate dynamic programming. Math. Oper. Res. 29(3), 462–478 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Guestrin, C., Koller, D., Parr, R., Venkataraman, S.: Efficient solution algorithms for factored MDPs. J. Artif. Intell. Res. 19, 399–468 (2003)

    MathSciNet  MATH  Google Scholar 

  7. Huang, L., Chen, J., Zhu, Q.: A factored MDP approach to optimal mechanism design for resilient large-scale interdependent critical infrastructures. In: Proceedings of 2017 Workshop on Modeling and Simulation of Cyber-Physical Energy Systems (MSCPES), CPS Week, 18–21 April 2017, Pittsburgh, PA, USA (2017)

    Google Scholar 

  8. Korkali, M., Veneman, J.G., Tivnan, B.F., Hines, P.D.: Reducing cascading failure risk by increasing infrastructure network interdependency. arXiv preprint arXiv:1410.6836 (2014)

  9. Lee II, E.E., Mitchell, J.E., Wallace, W.A.: Restoration of services in interdependent infrastructure systems: a network flows approach. IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.) 37(6), 1303–1317 (2007)

    Article  Google Scholar 

  10. Li, L., Shamma, J.: LP formulation of asymmetric zero-sum stochastic games. In: 2014 IEEE 53rd Annual Conference on Decision and Control (CDC), pp. 1930–1935. IEEE (2014)

    Google Scholar 

  11. Malek, A., Abbasi-Yadkori, Y., Bartlett, P.: Linear programming for large-scale Markov decision problems. In: International Conference on Machine Learning, pp. 496–504 (2014)

    Google Scholar 

  12. Manshaei, M.H., Zhu, Q., Alpcan, T., BacÅŸar, T., Hubaux, J.P.: Game theory meets network security and privacy. ACM Comput. Surv. (CSUR) 45(3), 25 (2013)

    Article  MATH  Google Scholar 

  13. Monga, A., Zhu, Q.: On solving large-scale low-rank zero-sum security games of incomplete information. In: 2016 IEEE International Workshop on Information Forensics and Security (WIFS), pp. 1–6. IEEE (2016)

    Google Scholar 

  14. Ouyang, M.: Review on modeling and simulation of interdependent critical infrastructure systems. Reliab. Eng. Syst. Saf. 121, 43–60 (2014)

    Article  Google Scholar 

  15. Pawlick, J., Farhang, S., Zhu, Q.: Flip the cloud: cyber-physical signaling games in the presence of advanced persistent threats. In: Khouzani, M.H.R., Panaousis, E., Theodorakopoulos, G. (eds.) GameSec 2015. LNCS, vol. 9406, pp. 289–308. Springer, Cham (2015). doi:10.1007/978-3-319-25594-1_16

    Chapter  Google Scholar 

  16. Pederson, P., Dudenhoeffer, D., Hartley, S., Permann, M.: Critical infrastructure interdependency modeling: a survey of US and international research. Ida. Nat. Lab. 25, 27 (2006)

    Google Scholar 

  17. Rinaldi, S.M., Peerenboom, J.P., Kelly, T.K.: Identifying, understanding, and analyzing critical infrastructure interdependencies. IEEE Control Syst. 21(6), 11–25 (2001)

    Article  Google Scholar 

  18. Rosato, V., Issacharoff, L., Tiriticco, F., Meloni, S., Porcellinis, S., Setola, R.: Modelling interdependent infrastructures using interacting dynamical models. Int. J. Crit. Infrastruct. 4(1–2), 63–79 (2008)

    Article  Google Scholar 

  19. Zhu, Q., Başar, T.: Game-theoretic approach to feedback-driven multi-stage moving target defense. In: Das, S.K., Nita-Rotaru, C., Kantarcioglu, M. (eds.) GameSec 2013. LNCS, vol. 8252, pp. 246–263. Springer, Cham (2013). doi:10.1007/978-3-319-02786-9_15

    Chapter  Google Scholar 

  20. Zhu, Q., Basar, T.: Game-theoretic methods for robustness, security, and resilience of cyberphysical control systems: games-in-games principle for optimal cross-layer resilient control systems. IEEE Control Syst. 35(1), 46–65 (2015)

    Article  MathSciNet  Google Scholar 

  21. Zhu, Q., Fung, C., Boutaba, R., Basar, T.: Guidex: a game-theoretic incentive-based mechanism for intrusion detection networks. IEEE J. Sel. Areas Commun. 30(11), 2220–2230 (2012)

    Article  Google Scholar 

  22. Zhu, Q., Li, H., Han, Z., Basar, T.: A stochastic game model for jamming in multi-channel cognitive radio systems. In: 2010 IEEE International Conference on Communications (ICC), pp. 1–6. IEEE (2010)

    Google Scholar 

  23. Zhu, Q., Tembine, H., Başar, T.: Network security configurations: a nonzero-sum stochastic game approach. In: American Control Conference (ACC), pp. 1059–1064. IEEE (2010)

    Google Scholar 

  24. Zimmerman, R., Zhu, Q., De Leon, F., Guo, Z.: Conceptual modeling framework to integrate resilient and interdependent infrastructure in extreme weather. J. Infrastruct. Syst. 23, 04017034 (2017)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, New York University, 2 Metrotech Center, Brooklyn, 11201, USA

    Linan Huang, Juntao Chen & Quanyan Zhu

Authors
  1. Linan Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juntao Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Quanyan Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Linan Huang .

Editor information

Editors and Affiliations

  1. Universität Klagenfurt, Klagenfurt, Austria

    Stefan Rass

  2. Nanyang Technological University, Singapore, Singapore

    Bo An

  3. University of Texas at El Paso, El Paso, Texas, USA

    Christopher Kiekintveld

  4. Carnegie Mellon University, Pittsburgh, Pennsylvania, USA

    Fei Fang

  5. AIT Austrian Institute of Technology GmbH, Klagenfurt, Austria

    Stefan Schauer

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Huang, L., Chen, J., Zhu, Q. (2017). A Large-Scale Markov Game Approach to Dynamic Protection of Interdependent Infrastructure Networks. In: Rass, S., An, B., Kiekintveld, C., Fang, F., Schauer, S. (eds) Decision and Game Theory for Security. GameSec 2017. Lecture Notes in Computer Science(), vol 10575. Springer, Cham. https://doi.org/10.1007/978-3-319-68711-7_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-68711-7_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-68710-0

  • Online ISBN: 978-3-319-68711-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation