Network Inspection for Detecting Strategic Attacks

Mathieu Dahan (), Lina Sela () and Saurabh Amin ()
Additional contact information
Mathieu Dahan: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Lina Sela: Department of Civil, Architectural and Environmental Engineering, The University of Texas at Austin, Austin, Texas 78712
Saurabh Amin: Department of Civil and Environmental Engineering, Laboratory for Information and Decision Systems and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2022, vol. 70, issue 2, 1008-1024

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 ( 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.

Keywords: Policy Modeling and Public Sector OR; strategic network inspection; attack detection; multiple resources; large-scale bilevel optimization; equilibrium analysis (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2180 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:2:p:1008-1024

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().