Network inspection for detecting strategic attacks

DOI10.1287/OPRE.2021.2180zbMATH Open1493.90157arXiv1705.00349OpenAlexW4211167717MaRDI QIDQ5080657FDOQ5080657

Authors: Mathieu Dahan, Lina Sela, Saurabh Amin 

Publication date: 31 May 2022

Published in: Operations Research (Search for Journal in Brave)

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 $(mathcalP)$ 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 $(mathcalP)$ 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 $(mathcalP)$. 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.

Full work available at URL: https://arxiv.org/abs/1705.00349

Recommendations

• Game theoretical security detection strategy for networked systems
• Optimal inspection points for malicious attack detection in smart grids
• Strategic sensor placement on graphs
• Connected subgraph defense games
• Strategic monitor placement against malicious flows

zbMATH Keywords

equilibrium analysisattack detectionmultiple resourceslarge-scale bilevel optimizationpolicy modeling and public sector ORstrategic network inspection

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Noncooperative games (91A10)

Cites Work

• A Greedy Heuristic for the Set-Covering Problem
• Modeling secrecy and deception in a multiple-period attacker-defender signaling game
• Balancing Terrorism and Natural Disasters—Defensive Strategy with Endogenous Attacker Effort
• New Branch-and-Bound Rules for Linear Bilevel Programming
• Submodular functions and optimization.
• Adaptive game playing using multiplicative weights
• Title not available (Why is that?)
• Analytical method to identify the number of containers to inspect at U.S. ports to deter terrorist attacks
• Decomposition Principle for Linear Programs
• Stochastic network interdiction
• On the infiltration game
• Search games and other applications of game theory
• Patrolling games
• Infrastructure security games
• Two-Person Zero-Sum Games for Network Interdiction
• Nuclear threat detection with mobile distributed sensor networks
• Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Sensor placement for fault location identification in water networks: a minimum test cover approach
• Attack, Defence, and Contagion in Networks
• A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems
• A network game with attackers and a defender
• Title not available (Why is that?)
• On the power of randomization in network interdiction
• Robust monotone submodular function maximization
• Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games

Cited In (5)

• Optimal inspection points for malicious attack detection in smart grids
• The all-pairs vitality-maximization (VIMAX) problem
• Attack chain detection
• A two‐stage network interdiction‐monitoring game
• Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey

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)