Strategic Monitoring of Networked Systems with Heterogeneous Security Levels
Preprint
Abstract
We consider a strategic network monitoring problem involving the operator of a networked system and an attacker. The operator aims to randomize the placement of multiple protected sensors to monitor and protect components that are vulnerable to attacks. We account for the heterogeneity in the components' security levels and formulate a large-scale maximin optimization problem. After analyzing its structure, we propose a three-step approach to approximately solve the problem. First, we solve a generalized covering set problem and run a combinatorial algorithm to compute an approximate solution. Then, we compute approximation bounds by solving a nonlinear set packing problem. To evaluate our solution approach, we implement two classical solution methods based on column generation and multiplicative weights updates, and test them on real-world water distribution and power systems. Our numerical analysis shows that our solution method outperforms the classical methods on large-scale networks, as it efficiently generates solutions that achieve a close to optimal performance and that are simple to implement in practice.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Stackelberg production-protection games: Defending crop production against intentional attacksEuropean Journal of Operational Research, 2022
- Strategic sensor placement on graphsSystems & Control Letters, 2021
- A hybrid stochastic game for secure control of cyber-physical systemsAutomatica, 2018
- Sensor placement for fault location identification in water networks: A minimum test cover approachAutomatica, 2016
- Infrastructure security gamesEuropean Journal of Operational Research, 2014
- In-pipe water quality monitoring in water supply systems under steady and unsteady state flow conditions: A quantitative assessmentWater Research, 2012
- Analytical method to identify the number of containers to inspect at U.S. ports to deter terrorist attacksAnnals of Operations Research, 2009
- Sequential, nonzero-sum “Blotto”: Allocating defensive resources prior to attackGames and Economic Behavior, 2009
- Improving Wireless Sensor Network Lifetime through Power Aware OrganizationWireless Networks, 2005
- Adaptive Game Playing Using Multiplicative WeightsGames and Economic Behavior, 1999