Cyber-physical critical infrastructures integrate networks of computational and physical processes to provide the society with essential services. The power grid, in particular, is a vast and interconnected cyber-physical network for delivering electricity from generation plants to end-point consumers. Protecting power grid critical infrastructures is a vital necessity because the failure of these systems would have a debilitating impact on economic security and public health and safety. However, several recent large-scale outages and the significant increase in the number of major attacks over the past four years confirm the insufficiency of the current protection solutions for these systems. Existing tedious manual tolerance procedures cannot protect those grids against sophisticated attacks. Additionally, use of purely-cyber security solutions for power grid resiliency is not sufficient because they ignore the cyber-physical interdependencies, power-side sensor measurements, and the possibility of countermeasures in power infrastructures. The objective of this research is to investigate fundamental problems in cyber-physical tolerance and develop an integrated set of mathematically rigorous and real-world deployable capabilities, resulting in a system that can model, analyze, predict, and tolerate complex security incidents in computing, physical, or communication assets in a near-real-time manner. The proposed research will provide system administrators and power grid operators with scalable and online integrated cyber-physical monitoring and incident response capabilities through keeping track of cyber-physical infrastructure's dynamic evolution caused by distributed security incidents, optimal proactive response and recovery countermeasures and adaptive preparation for potential future security incidents. The proposed research will facilitate trustworthy operation of next-generation complex and large-scale power grids. The research outcomes will be integrated into educational and knowledge transfer initiatives that involves implementation of curricular activities, innovative learning game development, university workshops, and hands-on K-12 summer camps and academic-year high-school courses, as well as Industry technology transfer efforts to develop a workforce with the capability to reason across multiple disciplines. Through holistic consideration of both cyber and physical factors under adversarial situations, this fundamental work will be applicable to other cyber-physical domains and can transform the way people approach the problem of cyber-physical security.