1. Network Inspection for Detecting Strategic Attacks.
- Author
-
Dahan, Mathieu, Sela, Lina, and Amin, Saurabh
- Subjects
BILEVEL programming ,INFRASTRUCTURE (Economics) ,NASH equilibrium ,COMPUTER network security ,DETECTORS - Abstract
Ensuring the security of critical infrastructures is crucial for the society's welfare and prosperity. However, these infrastructure networks are inherently vulnerable to both intentional and unintentional threats. In "Network Inspection for Detecting Strategic Attacks," Dahan, Sela, and Amin study a strategic network inspection problem, formulated as a large-scale bilevel optimization problem, in which a utility seeks to determine an inspection strategy with minimum number of smart detectors that ensures a desirable expected detection performance under worst-case attacks. The authors derive structural properties of optimal solutions and show that the problem can be solved using Nash equilibria of a large-scale zero-sum game. Their analysis leads to a computationally tractable and operationally feasible solution approach with theoretical guarantees based on combinatorial objects that capture the nature of equilibrium inspection and attack strategies. Their computational study indicates that utilities can achieve a high level of protection in large-scale networks by strategically positioning a small number of detectors. This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem (P) as a large-scale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ensures a target expected detection rate under worst-case attacks. We show that optimal solutions of (P) can be obtained from the equilibria of a large-scale zero-sum game. Our equilibrium analysis involves both game-theoretic and combinatorial arguments and leads to a computationally tractable approach to solve (P). First, we construct an approximate solution by using solutions of minimum set cover (MSC) and maximum set packing (MSP) problems and evaluate its detection performance. In fact, this construction generalizes some of the known results in network security games. Second, we leverage properties of the optimal detection rate to iteratively refine our MSC/MSP-based solution through a column generation procedure. Computational results on benchmark water networks demonstrate the scalability, performance, and operational feasibility of our approach. The results indicate that utilities can achieve a high level of protection in large-scale networks by strategically positioning a small number of detectors. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF