Network inspection for detecting strategic attacks
From MaRDI portal
Publication:5080657
Abstract: 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 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 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 . Firstly, we construct an approximate solution by utilizing 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. Secondly, 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5968956 (Why is no real title available?)
- scientific article; zbMATH DE number 3078983 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems
- A network game with attackers and a defender
- Adaptive game playing using multiplicative weights
- Analytical method to identify the number of containers to inspect at U.S. ports to deter terrorist attacks
- Attack, Defence, and Contagion in Networks
- Balancing Terrorism and Natural Disasters—Defensive Strategy with Endogenous Attacker Effort
- Decomposition Principle for Linear Programs
- Infrastructure security games
- Modeling secrecy and deception in a multiple-period attacker-defender signaling game
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- New Branch-and-Bound Rules for Linear Bilevel Programming
- Nuclear threat detection with mobile distributed sensor networks
- On the infiltration game
- On the power of randomization in network interdiction
- Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality
- Patrolling games
- Robust monotone submodular function maximization
- Search games and other applications of game theory
- Sensor placement for fault location identification in water networks: a minimum test cover approach
- Solving zero-sum games using best-response oracles with applications to search games
- Stochastic network interdiction
- Submodular functions and optimization.
- Two-Person Zero-Sum Games for Network Interdiction
Cited in
(6)- The all-pairs vitality-maximization (VIMAX) problem
- Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey
- A two‐stage network interdiction‐monitoring game
- Optimal inspection points for malicious attack detection in smart grids
- Strategic sensor placement on graphs
- Attack chain detection
This page was built for publication: Network inspection for detecting strategic attacks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080657)
