With the integration of modern information and communication technologies (ICTs) into critical infrastructures (CIs) such as 5G networks and the Internet of Things (IoTs), the CIs are becoming vulnerable to cyber threats at the same time improving its connectivity and functionalities. Hence it is essential to understand the risk of ICTs on CIs holistically as a cyber-physical system and design efficient security hardening mechanisms to reduce the cyber risks. To this end, we establish a game-theoretic framework to capture the system behaviors of the CIs under malicious attacks and the security design objectives. We propose the factored Markov game theory to enable a computationally scalable model of large-scale infrastructure networks and provide approximate algorithms for designing optimal mechanisms. The proposed theory 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 trade-off of the approximation accuracy and computation complexity in the new design paradigm and show the proactive security at the time of unanticipated attacks.