Models and Algorithms for Critical Infrastructure Protection with an Application to Cybersecurity Planning

摘要

Globalized supply chains bring enormous security risks to the information system, concerns of which have been widely and intensively expressed by both federal agencies and commercial organizations. In this dissertation, we investigate how to prioritize investment in mitigations to enhance the security of Information Technology (IT) infrastructure that balances cost and threat reduction. We propose an optimization framework consisting of mixed-integer programming and bi-level programming models and algorithms for protecting the critical infrastructure with a focus on cybersecurity planning and management.;First, we propose budgeted maximum multiple coverage (BMMC) models that identify a set of cost-effective mitigations to maximally reduce generic vulnerabilities in the IT infrastructure. We address the uncertainty regarding mitigation effectiveness, an inherent issue associated with cybersecurity planning, by proposing a stochastic expected-value BMMC model, denoted as EBMMC. Approximation algorithms with guaranteed approximation ratios are proposed to solve the models. Next, we extend EBMMC to three alternative models that provide solutions robust to worst case scenarios given uncertain mitigation effectiveness, including models that maximize the worst case coverage, minimize the worst case regret, and maximize the average coverage in some of the worst cases.;Furthermore, we address a more complicated and realistic problem when adversarial attackers are present. We investigate how to identify a best combination of cost-effective mitigations that maximally delay supply chain attacks when there exist multiple adversaries and uncertainty regarding mitigation effectiveness. We propose new Stackelberg game models that explicitly formulate the interaction between a defender and multiple attackers, including a deterministic interdiction model for delaying multiple adversarial projects (DIMAP) and a stochastic model variant (SIMAP) that incorporates uncertain delay times. We propose a Lagrangian heuristic that identifies near-optimal solutions efficiently. Finally, we propose a new exact algorithm for solving a particular critical infrastructure protection problem, the r-interdiction median problem with fortification (RIMF), which improves an existing algorithm in the literature and can be generalized to solve a broader range of facility interdiction and protection problems.