# Strategic Monitoring of Networked Systems with Heterogeneous Security Levels

Jezdimir Milošević, Mathieu Dahan, Saurabh Amin, and Henrik Sandberg
Manuscript received April 6, 2023. The work of JM and HS was supported in part
by the Swedish Civil Contingencies Agency (project CERCES2) and Digital
Futures (project DEMOCRITUS). The work of MD was supported by the Georgia Tech
new faculty start up grant. The work of SA was supported in part by AFOSR
grant “Building Attack Resilience into Complex Networks” and NSF grant #
2039771.Jezdimir Milošević was with the School of Electrical Engineering and
Computer Science, KTH Royal Institute of Technology, Stockholm, Sweden. He is
now with Scania Autonomous Transport Solutions (e-mail:
jezdimirmilosevic@gmail.com).Mathieu Dahan is with the School of Industrial
and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332
USA (e-mail: mathieu.dahan@isye.gatech.edu).Saurabh Amin is with the
Department of Civil and Environmental Engineering, Massachusetts Institute of
Technology, Cambridge, MA 02139 USA (e-mail: amins@mit.edu).Henrik Sandberg is
with the School of Electrical Engineering and Computer Science, KTH Royal
Institute of Technology, Stockholm, Sweden (e-mail: hsan@kth.se).

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

Strategic Network Monitoring, Optimization, Game Theory, Networked Control
Systems, Other Applications

##  1 Introduction

Large-scale networked systems, such as water distribution or power systems,
are lucrative targets for malicious attackers. Indeed, several attacks have
already occurred [1, 2], demonstrating the need for rapid development of
effective defense strategies for these systems. An essential component of
every defense strategy is attack detection [3], which can be accomplished by
allocating multiple sensors for system monitoring. Yet, for large-scale
systems, the number of available sensors is likely to be insufficient to
ensure complete coverage. A strategic adversary can exploit this deficiency to
target the most critical components of the system that are unmonitored. While
the literature on sensor placement has studied fixed [4, 5] and randomized
sensing strategies [6, 7], none of these works has accounted for the
heterogeneous criticality of the network components, and its impact on
monitoring decisions. Hence, the question that arises is how to strategically
allocate multiple sensors to monitor a large-scale system of critical
networked components.

Specifically, we focus on determining a randomized scheduling of monitoring
operations to maximize the protection of a networked system against a
strategic adversary. In this network monitoring problem, the network operator
seeks to randomize the placement of multiple protected sensors to monitor the
components and protect them against an attacker who aims to sabotage a system
component while remaining undetected. To better account for the attacker’s
behavior and preference, we consider that the components have possibly
heterogeneous security levels, which represent the corresponding levels of
effort required by an adversary to target them. This model is motivated by
risk management, where one first identifies critical system components in a
risk assessment, and then allocates protection resources accordingly [3]. By
monitoring a component with a protected sensor, the operator maximizes the
security level of that component. Then, to protect the system against a
strategic adversary, we assume that the operator aims to maximize the lowest
expected security level across all components.

#### Our contributions

In our first set of contributions, we analyze the structure of the network
monitoring problem and gather insights on the impact of the problem
characteristics on the operator’s optimal strategy. This leads us to a three-
step approach for efficiently computing an approximate monitoring strategy and
evaluating its optimality gap. First, we formulate and solve a mixed-integer
program (MIP) to compute generalized covering sets and obtain marginal
probabilities of placing sensors at each location. Second, we employ the
combinatorial algorithm of [8] to construct a randomized monitoring strategy
that is consistent with the marginal probabilities computed from the MIP.
Finally, by leveraging our structural insights, we formulate a MIP to compute
nonlinear set packings and obtain an optimality gap on our approximate
solution to the network monitoring problem.

In our second set of contributions, we refine our solution approach and
analysis for problem instances with special structures. In particular, we find
that our solution approach optimally solves the network monitoring problem
when the sets of components that are monitored from each sensor location are
mutually disjoint. Furthermore, when security levels are identical, our
solution approach can be simplified by solving the minimum set cover and
maximum set packing problems.

We also describe and implement two classical solution methods for solving the
network monitoring problem based on column generation and multiplicative
weights updates. In particular, we show that these algorithms can be utilized,
as the pricing problem for the column generation algorithm and the best-
response problem for the multiplicative weights update algorithm, can both be
formulated as maximum weighted covering problems.

In our last set of contributions, we evaluate our solution approach based on
generalized covering sets and nonlinear set packings and compare it with the
two classical solution methods using two security applications. In the first
application, we consider the problem of detecting contaminants injected in a
water distribution system. In the second application, we consider the problem
of protecting actuators in a large-scale power system against extended replay
attacks, during which the attacker uses actuators in addition to sensors to
lead an undetectable attack [9, 10]. Our computational results show that our
solution approach provides excellent solutions to the network monitoring
problem and outperforms the two classical methods in different aspects: It
generates solutions with low optimality gaps, and its running time is
marginally impacted by the number of available sensors. In contrast, the
running time of the other methods exponentially increases with respect to the
number of sensors. Finally, the monitoring strategies generated by our
solution approach are significantly simpler to implement in practice compared
to the ones generated by the classical methods, thus reinforcing the value of
our solution approach derived from structural insights.

#### Related work

Optimization and game theoretic models have been developed for studying
various security related problems, including the development of defense
strategies [11, 12, 13, 14], the design of anomaly detectors [15], the
allocation of security budget [16], and the placement of sensors [4, 5, 6, 7].
For instance, [17, 18, 19, 20] consider bilevel and trilevel optimization
problems to model defender-attacker interactions where each player selects a
pure strategy. In contrast, we focus on randomized strategies, which are
recognized to be more effective when the number of sensors to deploy is
limited [11, 16].

Other models that have been studied include inspection problems [21, 22, 23]
and search games [24, 25], in which a searcher is concerned with the optimal
way of looking for a hidden adversary in a search space; see for example [26,
27, 28, 29]. In particular, the recent literature on hide-and-seek games
investigates the problem of coordinating multiple inspection resources for
detecting hidden objects in boxes [8, 30, 31]. However, such problems do not
account for the impact of sensing range and the network topology on the
monitoring strategies. Still, we leverage the algorithm of [8] as part of our
solution approach for computing randomized monitoring strategies with small
supports.

Finally, the existing literature on sensor placement considers developing both
fixed [4, 5] and randomized monitoring strategies [6, 7]. The placement
problems considered previously aimed to minimize estimation error [32],
achieve optimal coverage [33], detect faults [34], or improve the system’s
security [35]. The study [35] is related to ours, and proposes two static
sensor placement strategies to improve the security of actuators in large-
scale systems. Our focus is instead on randomized strategies, which can be
translated into random scheduling of inspections that can be performed on a
day-to-day basis by utility or security personnel [36].

Our problem is also related to the simultaneous zero-sum game in [6], where
the operator places multiple sensors to maximize the number of detected
(homogeneous) attacks. Recent work extended this model by considering the
imperfect detection by sensors [37], and the different types of sensing
resources [38], for which they derive heuristic approaches. In addition, [39]
formulated a game in which sensors are positioned in the nodes of a networked
control system to detect attacks on them, and considered imperfect detection
through a linear filter that processes the sensors’ measurements to detect
attacks. The authors derived equilibrium results using tools from structured
systems and graph theory. However, to the best of our knowledge, no article
investigates the coordination of _multiple_ sensing resources to
_strategically_ monitor a _networked_ system with components of
_heterogeneous_ criticalities.

Preliminary results (without proofs) have been presented in [40].
Specifically, [40] investigate a simpler solution approach based on minimal
set covers, maximal set packings, and column generation. They also provide
approximation bounds under restrictive assumptions. By further leveraging the
problem structure, we generalize their results and obtain a more efficient
solution approach with stronger approximation bounds. We also provide a more
comprehensive evaluation of our solution approach through an extended
computational study that involves two other solution algorithms and two
security applications.

#### Organization

Section 2 introduces and formulates the strategic network monitoring problem.
In Section 3, we derive and analyze our solution approach based on generalized
covering sets and nonlinear set packings. We then present two alternative
solution methods based on column generation and multiplicative weights updates
in Section 4. Section 5 evaluates and compares these solution approaches
through a computational study. Finally, Section 6 summarizes our findings and
provides avenues for future work.

##  2 Problem Formulation

We consider a networked system consisting of a set of components
$\mathcal{U}$. Each component $u\in\mathcal{U}$ faces a risk of attack by an
adversary who wishes to disrupt or take control of the network. For every
$u\in\mathcal{U}$, let $\varphi_{u}\in[0,1]$ denote its _security level_ ,
i.e., the effort that the attacker needs to spend in order to successfully
target $u$ and compromise its operation. Security levels can for example be
estimated based on previously deployed security measures, configuration of the
system, or monetary cost for conducting an attack against the components. A
component $u$ for which $\varphi_{u}=0$ (resp. $\varphi_{u}=1$) is unsafe
(resp. highly secure).

The network operator can increase the security levels of some components by
positioning $r$ sensors within a set of locations $\mathcal{X}$. Specifically,
a sensor positioned at location $x\in\mathcal{X}$ can monitor and secure a
subset of components $U_{x}\subseteq\mathcal{U}$. For every $x\in\mathcal{X}$,
we refer to $U_{x}$ as the monitoring set of $x$. Typically, monitoring sets
are computed from the characteristics of the sensors and the network. If
multiple sensors are positioned at locations $X\subseteq\mathcal{X}$, then the
monitored and secured components are given by $U_{X}\coloneqq\cup_{x\in
X}U_{x}$.

We let $\mathcal{A}\coloneqq\\{X\subseteq\mathcal{X}\ |\ |X|\leq r\\}$ denote
the set of actions of the operator. Thus, for every sensor positioning
$X\in\mathcal{A}$ and every component $u\in\mathcal{U}$, the resulting _post-
security level_ of $u$ is given by
$f(X,u)\coloneqq\varphi_{u}\mathds{1}_{\\{u\notin
U_{X}\\}}+\mathds{1}_{\\{u\in U_{X}\\}}$. Specifically, the post-security
levels of all monitored components are maximal and equal to one. Without loss
of generality, we assume the following: 1) $U_{x}\neq\emptyset$ for every
$x\in\mathcal{X}$; 2) every component can be monitored from at least one
sensor location; and 3) $\varphi_{u}<1$ for every $u\in\mathcal{U}$.

Next, we illustrate the monitoring model with an example.

######  Example 2.1.

Consider the networked system and monitoring model illustrated in Fig. 1.

$x_{1}$$x_{2}$$x_{3}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$ Figure
1: Networked system containing 3 sensor locations and 7 components.

In this example, the set of sensor locations is
$\mathcal{X}=\\{x_{1},x_{2},x_{3}\\}$, the set of components is
$\mathcal{U}=\\{u_{1},\dots,u_{7}\\}$, and the monitoring sets are
$U_{x_{1}}=\\{u_{1},u_{2},u_{3}\\}$, $U_{x_{2}}=\\{u_{3},u_{4},u_{5}\\}$, and
$U_{x_{3}}=\\{u_{4},u_{6},u_{7}\\}$. The security levels are given by
$\varphi_{u_{3}}=\varphi_{u_{4}}=0.2$ (red in the figure),
$\varphi_{u_{1}}=\varphi_{u_{5}}=\varphi_{u_{7}}=0.5$ (blue in the figure),
and $\varphi_{u_{2}}=\varphi_{u_{6}}=0.8$ (green in the figure). We assume
that the operator has two sensors that they place on $X=\\{x_{2},x_{3}\\}$.
Then, each component $u$ in $U_{X}=\\{u_{3},u_{4},u_{5},u_{6},u_{7}\\}$ is
monitored and has a post-security level equal to $f(X,u)=1$. On the other
hand, the remaining components $u_{1}$ and $u_{2}$ are not monitored, and
their post-security levels are equal to their original security levels:
$f(X,u_{1})=0.5$ and $f(X,u_{2})=0.8$. Note that $u_{1}$ has the lowest
resulting post-security level and is the most vulnerable to attacks.

In such combinatorial security settings, the network operator can
significantly benefit from randomizing the positioning of their sensors [41,
36, 42]. Thus, we consider the problem where the operator is interested in
positioning their sensors in a randomized manner to protect the network
against an attacker who would target the most vulnerable component. In other
words, the operator aims to maximize the lowest expected post-security level
across all network’s components. Let
$\Delta^{1}\coloneqq\\{\sigma^{1}\in[0,1]^{|\mathcal{A}|}\ |\
\sum_{X\in\mathcal{A}}\sigma^{1}_{X}=1\\}$ denote the set of mixed strategies
of the operator, i.e., the set of probability distributions over
$\mathcal{A}$; here, $\sigma^{1}_{X}$ denotes the probability that the
operator positions sensors on locations $X\in\mathcal{A}$. Then, the problem
of strategic network monitoring can be formulated as

$\displaystyle\max_{\sigma^{1}\in\Delta^{1}}\min_{u\in\mathcal{U}}\mathbb{E}_{X\sim\sigma^{1}}[f(X,u)].$
($\mathcal{M}$)

Problem ($\mathcal{M}$) can be formulated as a linear program with
$|\mathcal{A}|+1$ variables and $|\mathcal{U}|+1$ constraints. However, the
cardinality of $\mathcal{A}$ grows combinatorially with respect to the number
of available sensors. Thus, standard methods for solving linear programs
cannot be used for large-scale systems, and different approaches are needed to
compute an optimal or approximate monitoring strategy. In Section 3, we
develop an approach based on mixed-integer programs (MIPs) to compute an
approximate solution of ($\mathcal{M}$), while in Section 4 we discuss
alternative approaches based on column generation and multiplicative weights
updates.

##  3 Main Results

In this section, we analyze the structure of the network monitoring problem
($\mathcal{M}$) and derive an approximate solution approach. Our approach
first solves a generalized covering set problem and runs a combinatorial
algorithm to construct a monitoring strategy with small support. Then, it
computes an optimality gap by solving a nonlinear set packing problem. We
further investigate problem instances with special structures, for which we
refine our approach and optimality gaps.

###  3.1 Preliminaries

To carry out our analysis, we first introduce additional quantities and
notations: For any optimization problem $(\mathcal{O})$, we denote by
$z^{*}_{(\mathcal{O})}$ its optimal value. Then, for every location
$x\in\mathcal{X}$, let $\overline{\varphi}_{x}\coloneqq\min_{u\in
U_{x}}\varphi_{u}$ denote the lowest security level of a component in the
monitoring set of $x$. This quantity will impact the operator’s monitoring
strategy, as the objective is to maximize the worst-case component post-
security level. We quantify the _criticality_ of a location $x\in\mathcal{X}$
(resp. component $u\in\mathcal{U}$) from the value of $\overline{\varphi}_{x}$
(resp. $\varphi_{u}$): If $\overline{\varphi}_{x}$ (resp. $\varphi_{u}$) is
low, we say that $x\in\mathcal{X}$ (resp. $u\in\mathcal{U}$) is more critical.
We additionally define, for every sensor positioning $X\in\mathcal{A}$ and
every location $x\in\mathcal{X}$,
$\bar{f}(X,x)\coloneqq\overline{\varphi}_{x}\mathds{1}_{\\{x\notin
X\\}}+\mathds{1}_{\\{x\in X\\}}$ to be the lowest post-security level within
the monitoring set $U_{x}$.

For any subset of locations $C\subseteq\mathcal{X}$ (resp. any subset of
components $T\subseteq\mathcal{U}$), we denote as $\overline{\varphi}_{C}$
(resp. $\varphi_{T}$) the following vector $(\overline{\varphi}_{x})_{x\in C}$
(resp. $(\varphi_{u})_{u\in T}$), sorted in nondecreasing order. For every
subset of components $T\subseteq\mathcal{U}$, we also define the following
quantity $S_{T}\coloneqq\sum_{u\in T}(1-\varphi_{u})^{-1}$.

For any vector $y\in\mathbb{R}^{n}$, we denote its support as
$\operatorname{supp}(y)\coloneqq\\{i\in\llbracket 1,n\rrbracket\ |\ y_{i}\neq
0\\}$, where $\llbracket 1,n\rrbracket=\\{1,\dots,n\\}$. Then, given a
monitoring strategy $\sigma^{1}\in\Delta^{1}$, we define its _node basis_ as
$\mathcal{X}(\sigma^{1})\coloneqq\cup_{X\in\operatorname{supp}(\sigma^{1})}X$,
that is, the set of nodes that are monitored with positive probability under
the monitoring strategy $\sigma^{1}$. Note that node bases provide a good
indicator of the practical implementability of a monitoring strategy: A
strategy that monitors a small number of locations can easily be implemented
in practice via a randomized scheduling of operations [36].

We consider the collection of set covers $\mathcal{S}$ of our networked
system. Specifically, a subset of locations $C\subseteq\mathcal{X}$ is a set
cover if $U_{C}=\mathcal{U}$, i.e., every component is monitored from at least
one location in $C$. Let $n^{*}$ denote the minimum set cover size. We note
that if $r\geq n^{*}$, then an optimal solution of the network monitoring
problem ($\mathcal{M}$) consists of placing sensors on a set cover and
ensuring a post-security level of 1 for every component. Henceforth, we assume
that $r<n^{*}$.

Finally, we consider the collection of set packings $\mathcal{T}$ of our
networked system. Specifically, a subset of components $T\subseteq\mathcal{U}$
is a set packing if $|T\cap U_{x}|\leq 1$ holds for every $x\in\mathcal{X}$.
Set packings indicate the _spread_ of the network, which directly impacts the
monitoring strategy of the operator: Since components in a set packing must be
monitored from distinct sensor locations, a network with large set packings is
more challenging to protect. We denote the maximum set packing size as
$m^{*}$.

###  3.2 Structural Analysis

We first analyze the structure of the network monitoring problem
($\mathcal{M}$) and derive bounds on its optimal value. To obtain a lower
bound on $z^{*}_{(\mathcal{M})}$, we simplify the problem by supposing that
when the operator places a sensor at location $x\in\mathcal{X}$, they protect
the component $u$ within the monitoring set $U_{x}$ that is the most critical.
The premise is that the post-security level achieved for any component in
$U_{x}$ will be at least that of component $u$. Formally, we relax the
objective function of ($\mathcal{M}$) and consider the following problem:

$\displaystyle\max_{\sigma^{1}\in\Delta^{1}}\min\bigg{\\{}\
\min_{\quad\mathclap{x\in\mathcal{X}(\sigma^{1})}\quad}\mathbb{E}_{X\sim\sigma^{1}}[\bar{f}(X,x)],\
\min_{\quad\mathclap{u\notin
U_{\mathcal{X}(\sigma^{1})}}\quad}\varphi_{u}\bigg{\\}}.$
($\overline{\mathcal{M}}$)

Problem ($\overline{\mathcal{M}}$) selects a monitoring strategy $\sigma^{1}$
that partitions the set of components $\mathcal{U}$ into two subsets: the
subset of components $\mathcal{U}\setminus U_{\mathcal{X}(\sigma^{1})}$ that
are never monitored by $\sigma^{1}$ and for which the post-security levels are
given by the corresponding original security levels; and the subset of
components $U_{\mathcal{X}(\sigma^{1})}$ that are monitored with positive
probability. In this latter set, $\sigma^{1}$ guarantees a post-security level
for every component in $U_{\mathcal{X}(\sigma^{1})}$ by improving the lowest
security level within each monitoring set $U_{x}$ for
$x\in\mathcal{X}(\sigma^{1})$.

In fact, we provide in the next lemma a different perspective on problem
($\overline{\mathcal{M}}$) to guide our analysis:

######  Lemma 3.2.

Problem ($\overline{\mathcal{M}}$) satisfies the following property:

$\displaystyle
z^{*}_{(\overline{\mathcal{M}})}=\max_{C\subseteq\mathcal{X}}\min\Big{\\{}z^{*}_{(\mathcal{R}_{C})},\min_{u\notin
U_{C}}\varphi_{u}\Big{\\}},$

where for every $C\subseteq\mathcal{X}$, $z^{*}_{(\mathcal{R}_{C})}$ is the
optimal value of

$\displaystyle\max_{\sigma^{1}\in\Delta^{1}}\min_{x\in
C}\mathbb{E}_{X\sim\sigma^{1}}[\bar{f}(X,x)].$ ($\mathcal{R}_{C}$)

Thus, ($\overline{\mathcal{M}}$) can be solved by first determining the set of
locations $C$ over which to randomize the placement of sensors, and then
determining the monitoring strategy that optimizes ($\mathcal{R}_{C}$). Given
a preselected subset of $n$ locations
$C=\\{x_{1},\dots,x_{n}\\}\subseteq\mathcal{X}$, indexed such that
$\overline{\varphi}_{x_{1}}\leq\cdots\leq\overline{\varphi}_{x_{n}}$, we
provide some intuition on the monitoring strategy $\sigma^{1}$ that maximizes
$\min_{x\in C}\mathbb{E}_{X\sim\sigma^{1}}[\bar{f}(X,x)]$. Initially, the goal
is to randomize the placement of the sensors among the locations in $C$ so as
to equalize the post-security level of the most critical component in each of
their monitoring sets. However, because of the heterogeneity of the security
levels, the operator should instead focus on the most critical locations and
not monitor the most secure locations. The number of most critical locations
in $C$ to monitor is given by

$\displaystyle k^{*}_{C}\coloneqq\max\bigg{\\{}k\in\llbracket 1,n\rrbracket\
\bigg{|}\ \overline{\varphi}_{x_{k}}\leq
1-\frac{k-r}{\sum_{l=1}^{k}(1-\overline{\varphi}_{x_{l}})^{-1}}\bigg{\\}}.$

For simplicity, we also denote
$S^{k^{*}}_{C}\coloneqq\sum_{l=1}^{k^{*}_{C}}(1-\overline{\varphi}_{C})^{-1}$.

Using this property and the collection of set packings $\mathcal{T}$, we can
then derive the following main theorem:

######  Theorem 3.3.

The optimal value of the network monitoring problem ($\mathcal{M}$) is bounded
as follows:

$\displaystyle z_{(\overline{\mathcal{M}})}^{*}$
$\displaystyle=\max_{C\subseteq\mathcal{X}}\min\bigg{\\{}1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}},\min_{\mathclap{u\notin
U_{C}}}\varphi_{u}\bigg{\\}}$ $\displaystyle\leq
z_{(\mathcal{M})}^{*}\leq\min\bigg{\\{}1,\min_{T\in\mathcal{T}}1-\frac{|T|-r}{S_{T}}\bigg{\\}}.$

Furthermore, for any set of $n>r$ locations
$C=\\{x_{1},\dots,x_{n}\\}\subseteq\mathcal{X}$ indexed in nondecreasing order
of their criticalities, any monitoring strategy $\sigma^{1^{\prime}}$
satisfying the following conditions is an optimal solution of
($\mathcal{R}_{C}$):

$\displaystyle\mathbb{P}_{X\sim\sigma^{1^{\prime}}}(x\in
X)=\begin{cases}1-\dfrac{k^{*}_{C}-r}{(1-\overline{\varphi}_{x})S^{k^{*}}_{C}},&\text{if
}x\in\\{x_{1},\dots,x_{k^{*}_{C}}\\}\\\ 0,&\text{otherwise.}\end{cases}$ (1)

Interestingly, from this theorem, we find that solving problem
($\overline{\mathcal{M}}$) indeed provides a lower bound on the optimal value
of ($\mathcal{M}$). Furthermore, given a subset of sensor locations
$C\subseteq\mathcal{X}$ of size greater than $r$, the post-security level that
can be guaranteed for any component in $U_{C}$ is given by
$1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}}$. To achieve this post-security level,
the network operator must ensure that the probability that each location in
$C$ is monitored follows (1). Importantly, we find that the $k^{*}_{C}$ most
critical locations must be monitored, with a probability that is decreasing
with the associated lowest security level. In contrast, the remaining
locations should not be monitored, as their security levels are already larger
than the post-security level achieved for the $k^{*}_{C}$ most critical
locations (by definition of $k^{*}_{C}$). We note that a monitoring strategy
satisfying (1) is guaranteed to exist by Farkas’ lemma [41, 6].

From Theorem 3.3, we also find that upper bounds on the optimal value of the
network monitoring problem ($\mathcal{M}$) can be computed from set packings.
We will leverage this finding to efficiently compute optimality gaps for our
solutions.

###  3.3 Solution Approach

From our structural analysis and Theorem 3.3, we next derive a three-step
approach to approximately solve the network monitoring problem
($\mathcal{M}$). Steps 1 and 2 compute a monitoring strategy that optimally
solves the relaxed problem ($\overline{\mathcal{M}}$), and step 3 computes a
set packing that achieves the upper bound from Theorem 3.3.

In the first step, we formulate a MIP to compute
$z^{*}_{(\overline{\mathcal{M}})}$ as well as the marginal probabilities of
monitoring each location at optimality of ($\overline{\mathcal{M}}$). In
particular, we leverage the fact that the objective function in
($\mathcal{R}_{C}$) can be expressed using these marginal probabilities.
Indeed, for every $\sigma^{1}\in\Delta^{1}$ and $x\in\mathcal{X}$,

$\displaystyle\mathbb{E}_{X\sim\sigma^{1}}[\bar{f}(X,x)]=\overline{\varphi}_{x}+(1-\overline{\varphi}_{x})\mathbb{P}_{X\sim\sigma^{1}}(x\in
X).$ (2)

Using Lemma 3.2, we then formulate the following MIP, which we refer to as a
_generalized covering set problem_ :

$\displaystyle\max_{y,z,\rho}\ $ $\displaystyle z$ ($\mathcal{C}$) s.t.
$\displaystyle
z\leq\overline{\varphi}_{x}+(1-\overline{\varphi}_{x})\rho_{x}+M_{1}(1-y_{x}),\
$ $\displaystyle\forall\,x\in\mathcal{X}$ (3) $\displaystyle
z\leq\varphi_{u}+M_{1}\sum_{\quad\mathclap{\\{x\in\mathcal{X}\,|\,u\in
U_{x}\\}}\quad}y_{x},$ $\displaystyle\forall\,u\in\mathcal{U}$ (4)
$\displaystyle 0\leq\rho_{x}\leq y_{x},$
$\displaystyle\forall\,x\in\mathcal{X}$ (5)
$\displaystyle\sum_{x\in\mathcal{X}}\rho_{x}=r,$ (6) $\displaystyle
y_{x}\in\\{0,1\\},$ $\displaystyle\forall\,x\in\mathcal{X}.$

Here, for every $x\in\mathcal{X}$, the binary variable $y_{x}$ determines if
$x$ can receive a sensor, while the continuous variable $\rho_{x}$ determines
the marginal probability that $x$ receives a sensor. $M_{1}$ is a “big M”,
which we can set to $1-\min_{u\in\mathcal{U}}\varphi_{u}$. Given
$C=\\{x\in\mathcal{X}\ |\ y_{x}=1\\}$, we then observe that constraints (3)
(combined with (2)) model $\min_{x\in
C}\mathbb{E}_{X\sim\sigma^{1}}[\bar{f}(X,x)]$, while constraints (4) model
$\min_{u\notin U_{C}}\varphi_{u}$. In fact, we show the equivalence between
($\overline{\mathcal{M}}$) and ($\mathcal{C}$):

######  Proposition 3.4.

Problems ($\overline{\mathcal{M}}$) and ($\mathcal{C}$) have identical optimal
values: $z^{*}_{(\overline{\mathcal{M}})}=z^{*}_{(\mathcal{C})}$. Furthermore,
a monitoring strategy $\sigma^{1^{*}}\in\Delta^{1}$ is an optimal solution of
($\overline{\mathcal{M}}$) if and only if there exists an optimal solution
$(y^{*},z^{*},\rho^{*})$ of ($\mathcal{C}$) satisfying
$\rho^{*}_{x}=\mathbb{P}_{X\sim\sigma^{1^{*}}}(x\in X)$ for every
$x\in\mathcal{X}$.

Thus, the optimal value of ($\overline{\mathcal{M}}$) can be computed by
solving ($\mathcal{C}$). In addition, given an optimal solution
$(y^{*},z^{*},\rho^{*})$ of ($\mathcal{C}$), $\rho^{*}$ provides the marginal
probabilities that each node must be monitored at optimality of
($\overline{\mathcal{M}}$).

The second step of our approach consists of reconstructing an optimal solution
of ($\overline{\mathcal{M}}$) from $\rho^{*}$. To this end, we utilize the
combinatorial algorithm derived in [8] that computes a probability
distribution $\sigma^{1^{*}}\in\Delta^{1}$ satisfying
$\mathbb{P}_{X\sim\sigma^{1^{*}}}(x\in X)=\rho^{*}_{x}$ for every
$x\in\mathcal{X}$. From Proposition 3.4, this guarantees the optimality of
$\sigma^{1^{*}}$ for ($\overline{\mathcal{M}}$).

Specifically, the algorithm iteratively expresses a vector
$\rho\in[0,1]^{|\mathcal{X}|}$ satisfying (6) as a convex combination of the
incidence vector of a sensor positioning $X\in\mathcal{A}$, and another vector
$\rho^{\prime}\in[0,1]^{|\mathcal{X}|}$ satisfying (6) and with at least one
additional integral component compared to $\rho^{*}$. We refer the reader to
[8] for the detailed algorithm, which we henceforth refer to as the
_coordination algorithm_.

Importantly, given $n=|\operatorname{supp}(\rho^{*})|$ the number of locations
that must receive a sensor with positive probability, this algorithm runs in
time $O(n^{2})$ and constructs a monitoring strategy of support size $n+1$. We
recall that a monitoring strategy with small support and/or small node basis
can more easily be implemented in practice. We will numerically evaluate the
node basis sizes of our solutions in our computational study.

The final step of our approach consists of evaluating the optimality gap of
our solution for the network monitoring problem. To this end, we derive a MIP
to efficiently compute the upper bound on $z^{*}_{(\mathcal{M})}$ from Theorem
3.3. Specifically, we aim to compute a set packing $T\in\mathcal{T}$ that
minimizes $1-\frac{|T|-r}{S_{T}}$, which is equivalent to finding a set
packing of size greater than $r$ that minimizes $\frac{S_{T}}{|T|-r}$.
Although this is a _nonlinear set packing problem_ , we can reformulate it as
the following MIP:

$\displaystyle\min_{t,y,z}$
$\displaystyle\displaystyle\sum_{l=r+1}^{|\mathcal{U}|}\frac{1}{l-r}t_{l}$
($\mathcal{P}$) s.t. $\displaystyle\sum_{u\in U_{x}}y_{u}\leq 1,$
$\displaystyle\forall\,x\in\mathcal{X}$ (7)
$\displaystyle\sum_{u\in\mathcal{U}}y_{u}=\sum_{l=r+1}^{|\mathcal{U}|}lz_{l},$
(8) $\displaystyle\sum_{l=r+1}^{|\mathcal{U}|}z_{l}=1,$ (9) $\displaystyle
t_{l}\geq\sum_{u\in\mathcal{U}}(1-\varphi_{u})^{-1}y_{u}-M_{2}(1-z_{l}),$
$\displaystyle\forall\,l\in\llbracket r+1,|\mathcal{U}|\rrbracket$ (10)
$\displaystyle t_{l}\geq 0,$ $\displaystyle\forall\,l\in\llbracket
r+1,|\mathcal{U}|\rrbracket$ (11) $\displaystyle z_{l}\in\\{0,1\\},$
$\displaystyle\forall\,l\in\llbracket r+1,|\mathcal{U}|\rrbracket$
$\displaystyle y_{u}\in\\{0,1\\},$ $\displaystyle\forall\,u\in\mathcal{U}.$

Specifically, the binary variables $y_{u}$, for $u\in\mathcal{U}$ select the
components to be part of the set packing. To parametrize the nonlinearity of
the problem, we introduced for every $l\in\llbracket
r+1,|\mathcal{U}|\rrbracket$ the binary variable $z_{l}$, which is equal to 1
if the set packing is of size $l$. Finally, for every $l\in\llbracket
r+1,|\mathcal{U}|\rrbracket$, the continuous variable $t_{l}$ represents the
product $z_{l}\sum_{u\in\mathcal{U}}(1-\varphi_{u})^{-1}y_{u}$. Constraints
(7) ensure that $\operatorname{supp}(y)$ is a set packing. Constraints (8)-(9)
select the set packing size. Then, constraints (10)-(11) ensure that at
optimality, the objective value is equal to
${\sum_{u\in\operatorname{supp}(y)}(1-\varphi_{u})^{-1}}/{(|\operatorname{supp}(y)|-r)}$.
$M_{2}$ is also a “big M”, which we can set to
$|\mathcal{U}|(1-\max_{u\in\mathcal{U}}\varphi_{u})^{-1}$.

As a consequence, the upper bound on the optimal value of ($\mathcal{M}$) from
Theorem 3.3 can computed by solving ($\mathcal{P}$):

######  Proposition 3.5.

The following equality holds:

$\min\bigg{\\{}1,\min_{T\in\mathcal{T}}1-\frac{|T|-r}{S_{T}}\bigg{\\}}=1-\frac{1}{z^{*}_{(\mathcal{P})}}.$

We note that the number of variables in ($\mathcal{P}$) can be reduced in
practice by computing an upper bound on the maximum set packing size in the
networked system. Given the maximum set packing size $m^{*}$ (or an upper
bound), then we can reduce the variables in ($\mathcal{P}$) from
$|\mathcal{U}|+2(|\mathcal{U}|-r)$ to $|\mathcal{U}|+2(m^{*}-r)$, and set
$M_{2}$ to $m^{*}(1-\max_{u\in\mathcal{U}}\varphi_{u})^{-1}$, which can
provide significant computational benefits.

Thus, we obtain a three-strep approach to compute an approximate solution to
the network monitoring problem ($\mathcal{M}$) and evaluate its optimality
gap. Next, we further study our solution for problem instances with particular
characteristics.

###  3.4 Special Cases

####  3.4.1 Non-overlapping monitoring sets

We consider problem instances for which monitoring sets are pairwise disjoint,
i.e., $U_{x}\cap U_{x^{\prime}}=\emptyset$ for every $x\neq
x^{\prime}\in\mathcal{X}$. Such instances occur when it is desirable to reduce
sensor interference or the energetic cost of the network [43, 44]. In other
contexts such as in security games, disjoint monitoring is naturally satisfied
[45, 46, 47]. For such instances, we show that our approach in Section 3.3
optimally solves the network monitoring problem:

######  Proposition 3.6.

If the monitoring sets are pairwise disjoint, then
$z^{*}_{(\overline{\mathcal{M}})}=z^{*}_{(\mathcal{M})}$. Furthermore, any
monitoring strategy satisfying (1) for $C=\mathcal{X}$ is an optimal solution
of ($\mathcal{M}$).

For instances when monitoring sets do not overlap, we find that problem
($\mathcal{M}$) can be optimally solved by first selecting the
$k^{*}_{\mathcal{X}}$ most critical sensor locations and monitoring them with
probabilities given by (1); and then by utilizing the coordination algorithm
to construct a monitoring strategy that randomizes the placement of $r$
sensors and is consistent with the marginal probabilities in (1).

####  3.4.2 Homogeneous security levels

We now consider instances where the security levels are identical across the
components in $\mathcal{U}$. In such cases, we refine the bounds on the
optimal value of ($\mathcal{M}$) using the minimum set cover and maximum set
packing sizes ($n^{*}$ and $m^{*}$):

######  Proposition 3.7.

If the security levels are identical and equal to $\varphi$, then:

$\displaystyle
z^{*}_{(\overline{\mathcal{M}})}=\varphi+(1-\varphi)\frac{r}{n^{*}}\leq
z^{*}_{(\mathcal{M})}\leq\min\bigg{\\{}1,\varphi+(1-\varphi)\frac{r}{m^{*}}\bigg{\\}}.$

In such instances, we find that ($\mathcal{C}$) and ($\mathcal{P}$) can be
simplified and the bounds on $z^{*}_{(\mathcal{M})}$ can be computed by
solving a minimum set cover and maximum set packing problem, as in [6]. If
$C^{*}$ denotes a minimum set cover, then a monitoring strategy that optimizes
$z^{*}_{(\overline{\mathcal{M}})}$ monitors each location in $C^{*}$ with
identical probability (given by (1)), and can be constructed by cycling the
$r$ sensors over $C^{*}$ (see [6] for reference).

##  4 Alternative Approaches

In order to compare our solution approach derived in Section 3.3, we next
consider two alternative approaches for solving the network monitoring
problem. In particular, we show how the column generation algorithm and
multiplicative weights update algorithm can be applied to solve
($\mathcal{M}$).

###  4.1 Column Generation Algorithm

Problem ($\mathcal{M}$) can be formulated as a linear program with a large
number (${|\mathcal{X}|\choose r}+1$) of variables and a small number
($|\mathcal{U}|+1$) of constraints. Such problems can potentially be solved
using the column generation algorithm, as long as the pricing problem can be
solved efficiently.

Specifically, at each iteration of the column generation algorithm, the
following restricted master problem is solved:

$\displaystyle\max\ $ $\displaystyle z$ ($\mathcal{M}_{\mathcal{I}}$) s.t.
$\displaystyle z-\sum_{X\in\mathcal{I}}\sigma^{1}_{X}f(X,u)\leq 0,\ $
$\displaystyle\forall\,u\in\mathcal{U}$ (12)
$\displaystyle\sum_{X\in\mathcal{I}}\sigma^{1}_{X}=1,$ (13)
$\displaystyle\sigma^{1}_{X}\geq 0,$ $\displaystyle\forall\,X\in\mathcal{I},$

where $\mathcal{I}\subseteq\mathcal{A}$ is a subset of feasible sensor
positionings. To determine if the optimal solution of
($\mathcal{M}_{\mathcal{I}}$) is optimal for ($\mathcal{M}$), the algorithm
then determines the variable in ($\mathcal{M}$) with highest reduced cost. Let
$(\alpha^{*},\beta^{*})$ denote the optimal dual variables of
($\mathcal{M}_{\mathcal{I}}$), associated with constraints (12)-(13). Then,
the variable with highest reduced cost can be determined by solving the
following pricing problem:

$\displaystyle\max_{X\in\mathcal{A}}-\beta^{*}+\sum_{u\in\mathcal{U}}\alpha^{*}_{u}f(X,u).$

In fact, the pricing problem for ($\mathcal{M}$) is a maximum weighted
covering problem, and can be solved using the following IP:

$\displaystyle\max_{y,z}\ $
$\displaystyle-\beta^{*}+\sum_{u\in\mathcal{U}}\alpha^{*}_{u}(\varphi_{u}+(1-\varphi_{u})y_{u})$
($\mathcal{W}$) s.t. $\displaystyle y_{u}\leq\sum_{\\{x\in\mathcal{X}\,|\,u\in
U_{x}\\}}z_{x},\ $ $\displaystyle\forall\,u\in\mathcal{U}$ (14)
$\displaystyle\sum_{x\in\mathcal{X}}z_{x}=r,$ (15) $\displaystyle
y_{u}\in\\{0,1\\},$ $\displaystyle\forall\,u\in\mathcal{U}$ (16)
$\displaystyle z_{x}\in\\{0,1\\},$ $\displaystyle\forall\,x\in\mathcal{X}.$
(17)

In this IP, the binary variables $z_{x}$, for $x\in\mathcal{X}$, represent the
nodes that receive a sensor, and the binary variables $y_{u}$, for
$u\in\mathcal{U}$, represent the components that are monitored by at least one
sensor.

If $z^{*}_{(\mathcal{W})}=0$, then the optimal solution of
($\mathcal{M}_{\mathcal{I}}$) is optimal for ($\mathcal{M}$), and the
algorithm terminates. If instead $z^{*}_{(\mathcal{W})}>0$, then given an
optimal solution $(y^{*},z^{*})$ of ($\mathcal{W}$), the algorithm adds
$X^{*}=\operatorname{supp}(z^{*})$ to the set $\mathcal{I}$ of variable
indices, and solves the new restricted master problem
($\mathcal{M}_{\mathcal{I}}$).

###  4.2 Multiplicative Weights Update Algorithm

Problem ($\mathcal{M}$) is also equivalent to a simultaneous two-person zero-
sum game, where the first player is the network operator who places $r$
sensors across the networked system and the second player is an attacker who
targets a component. The payoff function is given by $f$, which the operator
(resp. attacker) wants to maximize (resp. minimize).

In fact, [48] devised a multiplicative weights update algorithm for computing
approximate mixed Nash equilibria of such simultaneous games, as long as one
player has a small number of actions and the other player can efficiently
compute best responses. The algorithm runs for $N$ iterations, and at each
iteration $t\in\llbracket 1,N\rrbracket$, generates a probability distribution
$\sigma^{2,t}$ over $\mathcal{U}$ for the attacker as well a feasible sensor
positioning $X^{t}\in\mathcal{A}$ for the network operator. The algorithm
starts by setting $\sigma^{2,1}$ to the uniform distribution over
$\mathcal{U}$. Then, at each iteration $t\in\llbracket 1,N\rrbracket$, the
algorithm determines the operator’s best response to $\sigma^{2,t}$ by solving
the following problem:

$X^{t}\in\arg\max_{X\in\mathcal{A}}\mathbb{E}_{u\sim\sigma^{2,t}}[f(X,u)].$

In our setting, this problem can also be formulated as a maximum weighted
covering problem and can be solved using the following IP:

$\displaystyle\max_{y,z}\ $
$\displaystyle\sum_{u\in\mathcal{U}}\sigma^{2,t}_{u}(\varphi_{u}+(1-\varphi_{u})y_{u})$
($\mathcal{W}^{\prime}$) s.t.
$\displaystyle\eqref{covering_pb_1}-\eqref{covering_pb_4}.$

Then, the algorithm updates the attacker’s strategy using the following
multiplicative weights update:

$\forall\,u\in\mathcal{U},\
\sigma^{2,t+1}_{u}=\sigma^{2,t}_{u}\frac{\eta^{f(X^{t},u)}}{\sum_{u^{\prime}\in\mathcal{U}}\sigma^{2,t}_{u^{\prime}}\eta^{f(X^{t},{u^{\prime}})}},$

where $\eta=\left(1+\sqrt{2\frac{\ln|\mathcal{U}|}{N}}\right)^{-1}$. The
authors in [48] showed that the monitoring strategy
$\bar{\sigma}^{1}\in\Delta^{1}$ that uniformly randomizes over the $N$ best
responses $X^{1},\dots,X^{N}$ satisfies:

$\displaystyle\min_{u\in\mathcal{U}}\mathbb{E}_{X\sim\bar{\sigma}^{1}}[f(X,u)]\geq
z^{*}_{(\mathcal{M})}-\sqrt{\frac{2\ln|\mathcal{U}|}{N}}-\frac{\ln|\mathcal{U}|}{N}.$

Thus, if $N=4\lceil\frac{\ln|\mathcal{U}|}{\epsilon^{2}}\rceil$ for
$\epsilon>0$, then the (absolute) optimality gap associated with the
monitoring strategy $\bar{\sigma}^{1}$ generated by this algorithm is upper
bounded by $\epsilon$.

In fact, [7] showed that each iteration of this algorithm can be conducted in
polynomial time by approximately solving ($\mathcal{W}^{\prime}$) using a
greedy algorithm. However, the resulting guarantee on the monitoring strategy
$\bar{\sigma}^{1}$ becomes

$\displaystyle\min_{u\in\mathcal{U}}\mathbb{E}_{X\sim\bar{\sigma}^{1}}[f(X,u)]\geq(1-1/e)z^{*}_{(\mathcal{M})}-\epsilon,$

for $T=4\lceil\frac{\ln|\mathcal{U}|}{\epsilon^{2}}\rceil$. Since commercial
solvers are now highly efficient at solving classical IPs, we instead
optimally solve ($\mathcal{W}^{\prime}$) at each iteration of the algorithm.

We now move to computational experiments, where we evaluate the three
approaches presented in this article and compare their running times, as well
as the performance and implementability of the monitoring strategies they
generate.

##  5 Computational Study

In this section, we describe how our strategic network monitoring problem can
be applied for contamination detection in water distribution systems and
actuator protection in networked control systems. Our experiments are coded in
Julia and all optimization problems are solved using the Gurobi solver v9.0 on
a computer with 2.3-GHz, 8-Core Intel Core i9 processor and 32 GB of RAM.

###  5.1 Application I: Contamination Detection in Water Distribution Systems

We first consider the security problem where the operator of a water
distribution system aims to allocate sensors to monitor their network against
adversarially-induced contamination events. We model the water distribution
system as a directed graph, with the vertices representing pumps, junctions,
and water tanks, while the edges represent pipes. The direction of every edge
is adopted to be in the direction of the water flow. We assume that the
operator has access to contaminant detection sensors that can be deployed on
valve access points or fire hydrants and measure water quality indicators such
as electrical conductivity, free and total chlorine, turbidity, and oxygen
reduction potential in the water [49, 50, 51].

In this application, the set of vulnerable components $\mathcal{U}$ (resp. set
of sensor locations $\mathcal{X}$) is given by the set of edges (resp. nodes)
of the graph modeling the water network. Monitoring sets are constructed
through simulations using a hydraulic network solver [52] that tracks the
advection and reaction dynamics from a contaminant intrusion event [53]. In
practice, the security levels of components can be assessed based on
previously deployed security measures and their accessibility to an adversary.
One can then use different security scales to determine quantitative values
for the security levels based on that assessment [54]. In this application, we
adopt the scale $\\{0.2,0.4,0.6,0.8\\}$ for security levels, and randomly
assign them to each component.

Next, we implement the three solution approaches described in Sections 3 and 4
on the water distribution system ky5 [55]. This anonymized real-world water
network from Kentucky comprises 496 pipes and 420 nodes (junctions, water
tanks, pumps), satisfies a demand of 2.28 million gallons of water per day,
and spans 52.3 miles. In Fig. 2, we illustrate the bounds derived in Theorem
3.3 and computed by solving the generalized covering set problem
($\mathcal{C}$) and the nonlinear set packing problem ($\mathcal{P}$),
respectively.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$0.2$$0.4$$0.6$$0.8$$1$Number of sensors
$r$Lowest post-security level
$\min\limits_{u\in\mathcal{U}}\mathbb{E}_{X\sim\sigma^{1}}[f(X,u)]$$z^{*}_{(\mathcal{P})}$$z^{*}_{(\mathcal{M})}$$z^{*}_{(\mathcal{C})}$
Figure 2: Illustration of the bounds from Theorem 3.3 for varying numbers of
sensors.

From Fig. 2, we observe that the bounds obtained from ($\mathcal{C}$) and
($\mathcal{P}$) are close to the optimal value of ($\mathcal{M}$). On average,
the optimality gap given by the bounds does not exceed $4.7\,\%$, while the
actual optimality gap is equal to $3.6\,\%$ on average.

In general, we observe that $z^{*}_{(\mathcal{M})}$ increases nonlinearly with
respect to the number of sensors. When $r$ is small, the optimal monitoring
strategy focuses on protecting the most vulnerable components (with a security
level of $0.2$). As the operator has access to more sensors, they randomize
their placement to increase the post-security level of less critical
components. With 19 sensors, the operator can monitor all components and
ensure a post-security level of 1 for the entire network.

Next, we compare the running times of the various approaches. Specifically, we
illustrate the time to (a) solve ($\mathcal{P}$) and get an upper bound on
$z^{*}_{(\mathcal{M})}$, (b) solve ($\mathcal{C}$) and construct a monitoring
strategy using the coordination algorithm (CA), (c) solve ($\mathcal{M}$)
using column generation (CG), and (d) solve ($\mathcal{M}$) using
multiplicative weights updates (MWU) with $N=2,480$ iterations to ensure a
theoretical (absolute) optimality gap of $\epsilon=0.1$. Their running times
are illustrated in Fig. 3.

$1$$3$$5$$7$$9$$11$$13$$15$$17$$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$Number
of sensors $r$Running time [s]($\mathcal{C}$) + CA ($\mathcal{P}$) CG MWU
Figure 3: Approaches’ running times for varying numbers of sensors.

Fig. 3 shows that the upper bound on $z^{*}_{(\mathcal{M})}$ derived in
Theorem 3.3 can be efficiently computed; by solving ($\mathcal{P}$), we obtain
the upper bound in less than $0.2$ seconds. We also observe that the number of
sensors has limited impact on the running time.

Furthermore, we find that CG is approximately 100 times faster than MWU. This
is in part due to the number of iterations that are required for MWU to
theoretically guarantee a small optimality gap. Interestingly, we find that CG
can efficiently compute an optimal solution of ($\mathcal{M}$) when the number
of sensors is small. However, as $r$ increases, the running time of CG
increases exponentially. Finally, we find that our approximate monitoring
strategy, which achieves the lower bound in Theorem 3.3 and is obtained by
solving ($\mathcal{C}$) + CA, can be efficiently computed.

Finally, we compare the implementability of the solutions generated by the
three approaches by illustrating their node basis sizes in Fig. 4.

$1$$3$$5$$7$$9$$11$$13$$15$$17$$0$$50$$100$$150$$200$Number of sensors $r$Node
basis size $|\mathcal{X}(\sigma^{1})|$($\mathcal{C}$) + CACGMWU Figure 4: Node
basis sizes for varying numbers of sensors.

Fig. 4 clearly shows the implementability advantage of our monitoring
strategy. In particular, we find that our solution requires monitoring at most
20 different locations and achieves an excellent worst-case post-security
level (from Fig. 2). In contrast, the optimal post-security level achieved
using CG or MWU requires monitoring up to 180 different locations. From an
implementation perspective, our monitoring strategy is considerably easier to
translate into a daily/weekly scheduling of monitoring operations.

###  5.2 Application II: Protecting Actuators from Extended Replay Attacks

We now show how our findings can be used to protect actuators in a networked
control system from extended replay attacks. The networked system consists of
a set of physical states $\mathcal{X}$ and actuators $\mathcal{U}$, as well as
fixed unprotected sensors. We consider an attacker who aims to conduct an
undetectable attack on an actuator using an extended replay strategy. More
precisely an extended replay attack on an actuator is undetectable if the
sensor measurements remain in the steady state during the attack. To this end,
the attacker must also compromise a subset of components (i.e., unprotected
sensors and other actuators) to ensure that the attack is undetected. Such
subset of components typically depends on the dynamics of the networked
system, and can be efficiently determined in large-scale systems [10, Chapter
7],[35].

Importantly, the vulnerability of an actuator $u$ with respect to extended
replay attacks can be determined based on its security index $\delta_{u}$,
which represents the minimum number of sensors and actuators, including $u$
itself, that the attacker must compromise to conduct an undetectable extended
replay attack against $u$, in the absence of protected sensors [10, Chapter
7]. If no undetectable extended replay attack against $u$ is possible, then
$\delta_{u}=+\infty$. We can then scale these security indices and define
security levels for this application, following our modeling framework.
Specifically, we adopt an identical scale as in the previous application, and
define the security level of each actuator $u\in\mathcal{U}$ as follows:

$\displaystyle\varphi_{u}=$ $\displaystyle\textstyle
0.2\cdot\mathds{1}_{[\delta_{u}\in(0,5]]}+0.4\cdot\mathds{1}_{\\{\delta_{u}\in(5,15]\\}}+0.6\cdot\mathds{1}_{\\{\delta_{u}\in(15,20]\\}}$
$\displaystyle\textstyle+0.8\cdot\mathds{1}_{\\{\delta_{u}\in(20,+\infty)\\}}+1.0\cdot\mathds{1}_{\\{\delta_{u}=+\infty\\}}.$

Table 1: Comparison of solution approaches on IEEE 2383 bus power system. # sensors |  | Optimality gap [%] |  | Running time [s] |  | Node basis size
---|---|---|---|---|---|---
$r$ |  | ($\mathcal{C}$) + CA | CG | MWU |  | ($\mathcal{C}$) + CA | CG | MWU |  | ($\mathcal{C}$) + CA | CG | MWU
150 |  | 0.0 |  10.0 | 0.3 |  |  111.6 | 71.3 | 227.7 |  | 223 | 373 |  1430
100 |  | 0.0 |  10.4 | 0.4 |  |  111.9 | 600 | 245.1 |  | 318 | 868 |  1737
150 |  | 0.0 |  11.1 | 0.4 |  |  113.2 | 600 | 302.6 |  | 328 | 981 |  1824
200 |  | 0.0 |  18.0 | 0.3 |  |  115.1 | 600 | 412.2 |  | 328 | 1009 |  1827
250 |  | 0.0 | 15.0 | 0.3 |  | 174.2 | 600 | 581.2 |  | 344 | 1024 | 1115
300 |  | 0.0 | 24.0 | 0.3 |  |  139.2 | 600 | 591.0 |  | 344 | 1086 |  1612

To defend the networked system, we assume the operator possesses protected
sensors that cannot be compromised by the attacker and that can be positioned
within the network. We assume that each positioned sensor can only measure one
physical state, which is a commonly adopted model of large–scale systems [56,
57, 32]. In particular, a protected sensor can detect if the state it measures
deviates from its steady state value during an extended replay attack. Thus,
actuator $u\in\mathcal{U}$ belongs to the monitoring set of state
$x\in\mathcal{X}$ if placing a protected sensor at $x$ prevents the attacker
from conducting an undetectable extended replay attack on $u$.

We now consider the IEEE 2383 bus power system. We model the system using
linearized swing equations where the generators are represented by two states
(rotor angle and frequency) and load buses with one state (voltage angle)
[58]. We assume that all $|\mathcal{X}|=3037$ states are measurable, and that
the attacker can conduct an attack using $|\mathcal{U}|=1042$ loads (we
randomly selected 30$\%$ of the loads to be attackable) [59]. Table 1 compares
the performance of the different solution approaches on this networked system.
Note that we set a time limit of 10 minutes for each approach.

We observe that for this network, our solution approach optimally solves the
network monitoring problem ($\mathcal{M}$). Indeed, the upper bound obtained
by solving ($\mathcal{P}$) guarantees that the monitoring strategy computed
from ($\mathcal{C}$) + CA is optimal for ($\mathcal{M}$) for every number of
sensors. Although we observe some variance in the running time of our
approach, the average running time for this network is 29 seconds. In general,
we find that the hardest instances to solve are for which the number of
sensors to position is high but not too close to the minimum set cover size.
On the other hand, MWU achieves a very high performance, but requires 393
seconds on average. This illustrates the fact that the empirical performance
of MWU is better than the theoretical guarantees [48]. In contrast, we find
that CG scales poorly with the number of sensors, which is interesting given
that MWU and CG solve the very similar IPs ($\mathcal{W}$) and
($\mathcal{W}^{\prime}$). Finally, we similarly note that the node basis
(i.e., the locations that are monitored with positive probability) of our
monitoring strategy is up to 3 times smaller than when utilizing CG or MWU,
thus providing a solution that is more easily implementable in practice.

###  5.3 Summary and Extension of Solution Methodology

In summary, we find that by extracting the structure of the network monitoring
problem, we could derive an efficient solution approach. Our approach solves
two IPs and runs the coordination algorithm to directly obtain a monitoring
strategy with strong performance guarantees and that is easier to implement in
practice. This contrasts with the classical CG and MWU algorithms that
iteratively refine their solutions and generally run more slowly.

Interestingly, more flexibility can be embedded in our solution approach. For
instance, if the operator is interested in an even simpler monitoring
strategy, we can add the cardinality constraint
$\sum_{x\in\mathcal{X}}y_{x}\leq s$ in ($\mathcal{C}$) to find the best
monitoring strategy of ($\overline{\mathcal{M}}$) that monitors at most $s$
locations. This permits the operator to achieve the desired tradeoff between
solution implementability and guaranteed post-security level.

Finally, we note that the three solution approaches can be combined for an
even better performance. Indeed, for the instances for which our approach does
not provide an optimal solution to the network monitoring problem
($\mathcal{M}$), we can utilize our solution as a warm start for CG and/or
MWU, which will then iteratively improve it.

##  6 Conclusion

In this article, we studied the problem of strategically monitoring large-
scale networked systems with heterogeneous component criticalities using
multiple sensors. Specifically, we formulated a large-scale maximin problem
where the network operator selects a randomized placement of their protected
sensors to improve the post-security level of the network’s most critical
components against an attacker.

We developed a three-step solution approach that leverages the structure of
the network monitoring problem. First, we solved a generalized covering set
problem to determine the marginal probabilities to monitor each location.
Then, we utilized a combinatorial algorithm to randomize the positioning of
the multiple sensors and obtain a monitoring strategy that is consistent with
the marginal probabilities. Finally, we solved a nonlinear set packing problem
to evaluate our solution’s optimality gap. We also investigated problem
instances with special structures, for which we refined our solution approach
and optimality gaps.

We then adapted two classical solution methods for solving our monitoring
problem based on column generation and multiplicative weights updates, and
compared them on real-world benchmark water distribution and power systems.
Our computational study revealed that our solution approach outperforms the
classical methods as the size of the problem increases. In particular, we find
that our approach can efficiently compute near optimal solutions for large
instances and are significantly simpler to implement.

As part of future work, it would be interesting to investigate how the
solution method developed in this article (combining smaller IPs and
combinatorial algorithms) can be applied to solve problems where an attacker
targets multiple components simultaneously, or where sensors are faulty.

######  Proof .8 (Proof of Lemma 3.2).

We consider an optimal solution $\sigma^{1^{*}}$ of ($\overline{\mathcal{M}}$)
and we set $C=\mathcal{X}(\sigma^{1^{*}})$. Then,
$z^{*}_{(\mathcal{R}_{C})}\geq\min_{x\in\mathcal{X}(\sigma^{1^{*}})}\mathbb{E}_{X\sim\sigma^{1^{*}}}[\bar{f}(X,x)]$.
Furthermore, $\min_{u\notin U_{C}}\varphi_{u}=\min_{u\notin
U_{\mathcal{X}(\sigma^{1^{*}})}}\varphi_{u}$. Therefore,
$z^{*}_{(\overline{\mathcal{M}})}\leq\max_{C\subseteq\mathcal{X}}\min\\{z^{*}_{(\mathcal{R}_{C})},\min_{u\notin
U_{C}}\varphi_{u}\\}$.

To show the reverse inequality, let
$C^{*}\in\arg\max_{C\subseteq\mathcal{X}}\min\\{z^{*}_{(\mathcal{R}_{C})},\min_{u\notin
U_{C}}\varphi_{u}\\}$. We also consider an optimal solution $\sigma^{1^{*}}$
of $(\mathcal{R}_{C^{*}})$. Without loss of generality, we can assume that
$\mathcal{X}(\sigma^{1^{*}})\subseteq C^{*}$ (i.e., $\sigma^{1^{*}}$ only
places sensors within $C^{*}$). Then,
$\min_{x\in\mathcal{X}(\sigma^{1^{*}})}\mathbb{E}_{X\sim\sigma^{1^{*}}}[\bar{f}(X,x)]\geq
z^{*}_{(\mathcal{R}_{C^{*}})}$. Furthermore, let $u^{\prime}\notin
U_{\mathcal{X}(\sigma^{1^{*}})}$. If $u^{\prime}\in U_{C^{*}}\setminus
U_{\mathcal{X}(\sigma^{1^{*}})}$, let $x^{\prime}\in
C^{*}\setminus\mathcal{X}(\sigma^{1^{*}})$ such that $u^{\prime}\in
U_{x^{\prime}}$. We then obtain:

$\displaystyle\varphi_{u^{\prime}}\geq\overline{\varphi}_{x^{\prime}}=\mathbb{E}_{X\sim\sigma^{1^{*}}}[\bar{f}(X,x^{\prime})]\geq
z^{*}_{(\mathcal{R}_{C^{*}})}.$

If instead $u^{\prime}\notin U_{C^{*}}$, then
$\varphi_{u^{\prime}}\geq\min_{u\notin U_{C^{*}}}\varphi_{u}$. In conclusion,
$z^{*}_{(\overline{\mathcal{M}})}=\max_{C\subseteq\mathcal{X}}\min\\{z^{*}_{(\mathcal{R}_{C})},\min_{u\notin
U_{C}}\varphi_{u}\\}$.

######  Proof .9 (Proof of Theorem 3.3).

We first show that $z_{(\mathcal{M})}^{*}\geq
z_{(\overline{\mathcal{M}})}^{*}$: Let $\sigma^{1^{*}}\in\Delta^{1}$ be an
optimal solution of ($\overline{\mathcal{M}}$) and let
$u^{\prime}\in\mathcal{U}$. If $u^{\prime}\in
U_{\mathcal{X}(\sigma^{1^{*}})}$, then let
$x^{\prime}\in\mathcal{X}(\sigma^{1^{*}})$ such that $u^{\prime}\in
U_{x^{\prime}}$. Since
$\varphi_{u^{\prime}}\geq\overline{\varphi}_{x^{\prime}}$ and for every
$X\in\mathcal{A}$, $\mathds{1}_{\\{x^{\prime}\notin
X\\}}\geq\mathds{1}_{\\{u^{\prime}\notin U_{X}\\}}$, then

$\displaystyle\mathbb{E}_{X\sim\sigma^{1^{*}}}[f(X,u^{\prime})]$
$\displaystyle\geq\mathbb{E}_{X\sim\sigma^{1^{*}}}[1-(1-\overline{\varphi}_{x^{\prime}})\mathds{1}_{\\{x^{\prime}\notin
X\\}}]$
$\displaystyle\geq\min_{\quad\mathclap{x\in\mathcal{X}(\sigma^{1^{*}})}\quad}\mathbb{E}_{X\sim\sigma^{1^{*}}}[1-(1-\overline{\varphi}_{x})\mathds{1}_{\\{x\notin
X\\}}].$

If instead $u^{\prime}\notin U_{\mathcal{X}(\sigma^{1^{*}})}$, then:

$\displaystyle\mathbb{E}_{X\sim\sigma^{1^{*}}}[f(X,u^{\prime})]=\varphi_{u^{\prime}}\geq\min_{u\notin
U_{\mathcal{X}(\sigma^{1^{*}})}}\varphi_{u}.$

Thus, $z^{*}_{(\mathcal{M})}\geq z^{*}_{(\overline{\mathcal{M}})}$. We next
show that for every $C\subseteq\mathcal{X}$ of size greater than $r$,
$z^{*}_{(\mathcal{R}_{C})}=1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}}$.

We rewrite $C=\\{x_{1},\dots,x_{n}\\}$ with $n>r$ and indices satisfying
$\overline{\varphi}_{x_{1}}\leq\cdots\leq\overline{\varphi}_{x_{n}}$. Then
necessarily, $k_{C}^{*}\geq r+1$ since

$\displaystyle
1-\frac{r+1-r}{\sum_{l=1}^{r+1}(1-\overline{\varphi}_{x_{l}})^{-1}}\geq
1-(1-\overline{\varphi}_{x_{r+1}})=\overline{\varphi}_{x_{r+1}}.$

Let $\sigma^{1^{\prime}}\in\Delta^{1}$ be a monitoring strategy satisfying
(1). The existence of such a monitoring strategy follows from Farkas’ lemma
(for instance, see [6, Lemma EC.4]), since

$\displaystyle\sum_{l=1}^{k^{*}_{C}}1-\frac{k^{*}_{C}-r}{(1-\overline{\varphi}_{x})S^{k^{*}}_{C}}=r,$

and for every $l\in\llbracket 1,k^{*}_{C}\rrbracket$,

$\displaystyle 1\geq
1-\frac{k^{*}_{C}-r}{(1-\overline{\varphi}_{x_{l}})S^{k^{*}}_{C}}\geq
1-\frac{k^{*}_{C}-r}{(1-\overline{\varphi}_{x_{k^{*}_{C}}})S^{k^{*}}_{C}}\geq
0.$

We next consider $x\in C$. If $x\in\\{x_{1},\dots,x_{k^{*}_{C}}\\}$, then:

$\displaystyle\mathbb{E}_{X\sim\sigma^{1^{\prime}}}[\bar{f}(X,x)]$
$\displaystyle=\overline{\varphi}_{x}+(1-\overline{\varphi}_{x})\mathbb{P}_{X\sim\sigma^{1^{\prime}}}(x\in
X)$ $\displaystyle=1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}}.$

If instead $x\in C\setminus\\{x_{1},\dots,x_{k^{*}_{C}}\\}$, then:

$\displaystyle\mathbb{E}_{X\sim\sigma^{1^{\prime}}}[\bar{f}(X,x)]$
$\displaystyle=\overline{\varphi}_{x}\geq\overline{\varphi}_{x_{k^{*}_{C}+1}}$
$\displaystyle>1-\frac{k^{*}_{C}+1-r}{S^{k^{*}}_{C}+(1-\overline{\varphi}_{x_{k^{*}_{C}+1}})^{-1}},$

which is equivalent to

$\displaystyle\mathbb{E}_{X\sim\sigma^{1^{\prime}}}[\bar{f}(X,x)]>1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}}.$

Thus, $z^{*}_{(\mathcal{R}_{C})}\geq 1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}}$.

Now, let us assume by contradiction that
$z^{*}_{(\mathcal{R}_{C})}>1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}}$. Let
$\sigma^{1^{*}}$ be an optimal solution of $z^{*}_{(\mathcal{R}_{C})}$. Then,
we deduce that:

$\displaystyle\forall\,x\in C,\ \mathbb{P}_{X\sim\sigma^{1^{*}}}(x\in
X)>1-\frac{k^{*}_{C}-r}{(1-\overline{\varphi}_{x})S^{k^{*}}_{C}},$

which induces the following contradiction:

$\displaystyle r$
$\displaystyle=\sum_{X\in\mathcal{A}}\sigma^{1^{*}}_{X}|X|=\sum_{x\in\mathcal{X}}\sum_{X\in\mathcal{A}}\sigma^{1^{*}}_{X}\mathds{1}_{\\{x\in
X\\}}$
$\displaystyle=\sum_{x\in\mathcal{X}}\mathbb{P}_{X\sim\sigma^{1^{*}}}(x\in
X)>\sum_{l=1}^{k^{*}_{C}}1-\frac{k^{*}_{C}-r}{(1-\overline{\varphi}_{x_{l}})S^{k^{*}}_{C}}=r.$

In conclusion,
$z^{*}_{(\mathcal{R}_{C})}=1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}}$, and an
optimal solution is given by $\sigma^{1^{\prime}}$ satisfying (1).

We note that for every $C\subseteq\mathcal{X}$ of size no more than $r$,
$z^{*}_{(\mathcal{R}_{C})}=1$ (which is obtained by placing a sensor on each
location in $C$). Also note that in such cases, $\mathcal{U}\setminus
U_{C}\neq\emptyset$ and $1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}}\geq
1\geq\min_{u\notin U_{C}}\varphi_{u}$. Thus, from Lemma 3.2, we deduce that

$z^{*}_{(\overline{\mathcal{M}})}=\max_{C\subseteq\mathcal{X}}\min\bigg{\\{}1-\frac{k^{*}_{C}-r}{S^{k^{*}}_{C}},\min_{\mathclap{u\notin
U_{C}}}\varphi_{u}\bigg{\\}}.$

Finally, we prove the upper bound on $z^{*}_{(\mathcal{M})}$. Since
$f(X,u)\leq 1$ for every $X\in\mathcal{A}$ and every $u\in\mathcal{U}$, then
$z^{*}_{(\mathcal{M})}\leq 1$. Furthermore, by strong duality, we know that
$z^{*}_{(\mathcal{M})}=\min_{\sigma^{2}\in\Delta^{2}}\max_{X\in\mathcal{A}}\mathbb{E}_{u\sim\sigma^{2}}[f(X,u)]$,
where $\Delta^{2}\coloneqq\\{\sigma^{2}\in[0,1]^{|\mathcal{U}|}\ |\
\sum_{u\in\mathcal{U}}\sigma^{2}_{u}=1\\}.$ Then, given a set packing
$T\in\mathcal{T}$, we define $\sigma^{2^{\prime}}\in\Delta^{2}$ as follows:

$\displaystyle\sigma^{2^{\prime}}_{u}=\begin{cases}\frac{1}{(1-\varphi_{u})S_{T}},&\text{
if }u\in T\\\ 0,&\text{ otherwise.}\end{cases}$

We can then derive the following upper bound.

$\displaystyle z^{*}_{(\mathcal{M})}$
$\displaystyle\leq\max_{X\in\mathcal{A}}\mathbb{E}_{u\sim\sigma^{2^{\prime}}}[f(X,u)]$
$\displaystyle=\max_{X\in\mathcal{A}}\sum_{u\in
T}\sigma^{2^{\prime}}_{u}(1-(1-\varphi_{u})\mathds{1}_{\\{u\notin U_{X}\\}})$
$\displaystyle=1-\frac{1}{S_{T}}\min_{X\in\mathcal{A}}\sum_{u\in
T}\mathds{1}_{\\{u\notin U_{X}\\}}\leq 1-\frac{|T|-r}{S_{T}}$

In conclusion,
$z_{(\mathcal{M})}^{*}\leq\min\\{1,\min_{T\in\mathcal{T}}1-\frac{|T|-r}{S_{T}}\\}$.

######  Proof .10 (Proof of Proposition 3.4).

Let $(y^{*},z^{*},\rho^{*})$ be an optimal solution of ($\mathcal{C}$), and we
set $C=\operatorname{supp}(y^{*})$. Then, ($\mathcal{C}$) can be rewritten as
follows:

$\displaystyle\max_{y}$
$\displaystyle\min\bigg{\\{}\max_{\rho}\min_{x\in\operatorname{supp}(y)}$
$\displaystyle\overline{\varphi}_{x}+(1-\overline{\varphi}_{x})\rho_{x},\min_{u\notin
U_{\operatorname{supp}(y)}}\varphi_{u}\bigg{\\}}.$ s.t. $\displaystyle
0\leq\rho_{x}\leq y_{x},\ $ $\displaystyle\forall\,x\in\mathcal{X}$ (18)
$\displaystyle\sum_{x\in\mathcal{X}}\rho_{x}=r,$ (19) $\displaystyle
y_{x}\in\\{0,1\\},\ $ $\displaystyle\forall\,x\in\mathcal{X}.$

The equivalence between ($\overline{\mathcal{M}}$) and ($\mathcal{C}$) then
follows from Lemma 3.2, equality (2), and the existence of monitoring
strategies satisfying constraints (18)-(19).

######  Proof .11 (Proof of Proposition 3.5).

We argued in the main text that Problem ($\mathcal{P}$) is indeed a MIP
formulation of the following problem
$\min_{T\in\mathcal{T}}\frac{S_{T}}{|T|-r}$. In particular, at optimality,
constraints (9) and $M_{2}$ ensure that at optimality all $t_{l}$ variables
are equal to 0 except for the index corresponding to the set packing size,
thus ensuring the validity of the formulation. Then,
$\min\\{1,\min_{T\in\mathcal{T}}1-\frac{|T|-r}{S_{T}}\\}=1-\frac{1}{z^{*}_{(\mathcal{P})}}.$
Note that we used the convention that if a ($\mathcal{P}$) is infeasible
(which occurs if there is no set packing of size greater than $r$), then
$z^{*}_{(\mathcal{P})}=+\infty$.

######  Proof .12 (Proof of Proposition 3.6).

We consider an instance where $U_{x}\cap U_{x^{\prime}}=\emptyset$ for every
$x\neq x^{\prime}\in\mathcal{X}$. We index the locations in
$\mathcal{X}=\\{x_{1},\dots,x_{n}\\}$ in nondecreasing order of their
criticalities. Then, we consider the set packing
$T^{\prime}=\\{u_{1},\dots,u_{k^{*}_{\mathcal{X}}}\\}\in\mathcal{T}$, where
for every $l\in\llbracket 1,k^{*}_{\mathcal{X}}\rrbracket$,
$\varphi_{u_{l}}=\overline{\varphi}_{x_{l}}$. In other words, $T^{\prime}$
selects the most critical component within each of the first
$k^{*}_{\mathcal{X}}$ monitoring sets. As a consequence,
$|T^{\prime}|=k^{*}_{\mathcal{X}}$ and
$S_{T^{\prime}}=S^{k^{*}}_{\mathcal{X}}$. Since $U_{\mathcal{X}}=\mathcal{U}$,
then from Theorem 3.3, we obtain:

$\displaystyle z^{*}_{(\mathcal{R}_{\mathcal{X}})}$
$\displaystyle=1-\frac{k^{*}_{\mathcal{X}}-r}{S^{k^{*}}_{\mathcal{X}}}\leq
z_{(\overline{\mathcal{M}})}^{*}\leq z^{*}_{(\mathcal{M})}$ $\displaystyle\leq
1-\frac{|T^{\prime}|-r}{S_{T^{\prime}}}=1-\frac{k^{*}_{\mathcal{X}}-r}{S^{k^{*}}_{\mathcal{X}}}.$

Thus, $z^{*}_{(\mathcal{M})}=z^{*}_{(\overline{\mathcal{M}})}$. Furthermore,
any monitoring strategy $\sigma^{1^{\prime}}\in\Delta^{1}$ satisfying (1) for
$C=\mathcal{X}$, which is optimal for $(\mathcal{R}_{\mathcal{X}})$, is then
optimal for ($\mathcal{M}$).

######  Proof .13 (Proof of Proposition 3.7).

We suppose that for every component, the security levels are identical and
equal to $\varphi$. Let $C\subseteq\mathcal{X}$. Then, we find that
$k^{*}_{C}=|C|$ since for every $k\in\llbracket 1,|C|\rrbracket$,
$\frac{k-r}{k}(1-\varphi)\leq 1-\varphi$. Therefore,
$z^{*}_{(\overline{\mathcal{M}})}=\max_{C\subseteq\mathcal{X}}\min\\{1-\frac{|C|-r}{|C|}(1-\varphi),\min_{u\notin
U_{C}}\varphi\\}$.

Note that for any $C\subseteq\mathcal{X}$,
$1-\frac{|C|-r}{|C|}(1-\varphi)=\varphi+\frac{r}{|C|}(1-\varphi)\geq\varphi$.
Therefore,

$\displaystyle
z^{*}_{(\overline{\mathcal{M}})}=\max_{C\in\mathcal{S}}\varphi+\frac{r}{|C|}(1-\varphi)=\varphi+\frac{r}{n^{*}}(1-\varphi),$

where $\mathcal{S}$ is the collection of set covers. Similarly,

$\displaystyle\min_{T\in\mathcal{T}}1-\frac{|T|-r}{S_{T}}=\min_{T\in\mathcal{T}}1+\frac{r}{|T|}(1-\varphi)=1+\frac{r}{m^{*}}(1-\varphi).$

## References

  * [1] J. Slay and M. Miller, “Lessons learned from the Maroochy water breach,” in _Proceedings of the International Conference on Critical Infrastructure Protection_ , 2007.
  * [2] J. Majkut and A. Dawes, “Responding to Russian attacks on Ukraine’s power sector,” Center for Strategic & International Studies, https://www.csis.org/analysis/responding-russian-attacks-ukraines-power-sector, Nov 2022, accessed: March 6th, 2023.
  * [3] K. Stouffer, J. Falco, and K. Scarfone, “Guide to industrial control systems security,” _National Institute of Standards & Technology_, 2011.
  * [4] A. Rahmattalabi, P. Vayanos, and M. Tambe, “A robust optimization approach to designing near-optimal strategies for constant-sum monitoring games,” in _Decision and Game Theory for Security_. Springer International Publishing, 2018, pp. 603–622.
  * [5] M. Pirani, E. Nekouei, H. Sandberg, and K. H. Johansson, “A game-theoretic framework for security-aware sensor placement problem in networked control systems,” in _Proceedings of the American Control Conference_ , 2019.
  * [6] M. Dahan, L. Sela, and S. Amin, “Network inspection for detecting strategic attacks,” _Operations Research_ , vol. 70, no. 2, pp. 1008–1024, 2022.
  * [7] A. Krause, A. Roper, and D. Golovin, “Randomized sensing in adversarial environments,” in _Twenty-Second International Joint Conference on Artificial Intelligence_ , 2011.
  * [8] M. Dziubiński and J. Roy, “Hide and seek game with multiple resources,” in _International Symposium on Algorithmic Game Theory_. Springer, 2018, pp. 82–86.
  * [9] Y. Mo, S. Weerakkody, and B. Sinopoli, “Physical authentication of control systems: Designing watermarked control inputs to detect counterfeit sensor outputs,” _IEEE Control Systems Magazine_ , vol. 35, no. 1, pp. 93–109, 2015\.
  * [10] J. Milošević, “Security metrics and allocation of security resources for control systems,” Ph.D. dissertation, KTH Royal Institute of Technology, 2020\.
  * [11] Q. Zhu and T. Basar, “Game-theoretic methods for robustness, security, and resilience of cyberphysical control systems: games-in-games principle for optimal cross-layer resilient control systems,” _IEEE control systems_ , vol. 35, no. 1, pp. 46–65, 2015.
  * [12] M. Baykal-Gürsoy, Z. Duan, H. V. Poor, and A. Garnaev, “Infrastructure security games,” _Eur. J. Oper. Res._ , vol. 239, no. 2, pp. 469–478, 2014\.
  * [13] S. Goyal and A. Vigier, “Attack, defense, and contagion in networks,” _Rev. Econ. Stud._ , vol. 81, no. 4, pp. 1518–1542, 2014.
  * [14] J. Zhuang and V. M. Bier, “Balancing terrorism and natural disasters—defensive strategy with endogenous attacker effort,” _Oper. Res._ , vol. 55, no. 5, pp. 976–991, 2007.
  * [15] F. Miao, Q. Zhu, M. Pajic, and G. J. Pappas, “A hybrid stochastic game for secure control of cyber-physical systems,” _Automatica_ , vol. 93, pp. 55–63, 2018.
  * [16] A. R. Hota, A. A. Clements, S. Sundaram, and S. Bagchi, “Optimal and game-theoretic deployment of security investments in interdependent assets,” in _International Conference on Decision and Game Theory for Security_. Springer, 2016, pp. 101–113.
  * [17] G. Brown, M. Carlyle, J. Salmerón, and K. Wood, “Defending critical infrastructure,” _INFORMS J. Applied Analytics_ , vol. 36, no. 6, pp. 530–544, 2006.
  * [18] V. M. Bier and N. Haphuriwat, “Analytical method to identify the number of containers to inspect at U.S. ports to deter terrorist attacks,” _Ann. Oper. Res._ , vol. 187, no. 1, pp. 137–158, 2011.
  * [19] D. L. Alderson, G. G. Brown, and W. M. Carlyle, “Operational models of infrastructure resilience,” _Risk Anal._ , vol. 35, no. 4, pp. 562–586, 2015\.
  * [20] D. L. Alderson, G. G. Brown, W. M. Carlyle, and R. K. Wood, “Assessing and improving the operational resilience of a large highway infrastructure system to worst-case losses,” _Transportation Sci._ , vol. 52, no. 4, pp. 1012–1034, 2018.
  * [21] A. Washburn and K. Wood, “Two-person zero-sum games for network interdiction,” _Oper. Res._ , vol. 43, no. 2, pp. 243–251, 1995.
  * [22] K. J. Cormican, D. P. Morton, and R. K. Wood, “Stochastic network interdiction,” _Oper. Res._ , vol. 46, no. 2, pp. 184–197, 1998.
  * [23] J. C. Smith and C. Lim, “Algorithms for network interdiction and fortification games,” in _Pareto Optimality, Game Theory And Equilibria _(Springer, New York, NY)__ , A. Chinchuluun, P. M. Pardalos, A. Migdalas, and L. Pitsoulis, Eds., 2008, pp. 609–644.
  * [24] S. Gal and J. Casas, “Succession of hide–seek and pursuit–evasion at heterogeneous locations,” _J. Roy. Soc. Interface_ , vol. 11, no. 94, p. 20140062, 2014.
  * [25] L. Hellerstein, T. Lidbetter, and D. Pirutinsky, “Solving zero-sum games using best-response oracles with applications to search games,” _Operations Research_ , vol. 67, no. 3, pp. 731–743, 2019.
  * [26] T. Lidbetter, “Search games with multiple hidden objects,” _SIAM Journal on Control and Optimization_ , vol. 51, no. 4, pp. 3056–3074, 2013.
  * [27] J. Clarkson, K. Y. Lin, and K. D. Glazebrook, “A classical search game in discrete locations,” _Mathematics of Operations Research_ , 2022.
  * [28] S. Alpern and S. Gal, _The theory of search games and rendezvous_. Springer Science & Business Media, 2006, vol. 55.
  * [29] R. Hohzaki, “Search games: Literature and survey,” _Journal of the Operations Research Society of Japan_ , vol. 59, no. 1, pp. 1–34, 2016.
  * [30] S. Gal and J. Casas, “Succession of hide–seek and pursuit–evasion at heterogeneous locations,” _Journal of the Royal Society Interface_ , vol. 11, no. 94, p. 20140062, 2014.
  * [31] B. Bahamondes and M. Dahan, “Hide-and-seek game with capacitated locations and imperfect detection,” 2023.
  * [32] V. Tzoumas, A. Jadbabaie, and G. J. Pappas, “Sensor placement for optimal Kalman filtering: Fundamental limits, submodularity, and algorithms,” in _Proceedings of the American Control Conference_ , 2016.
  * [33] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” _IEEE Transactions on robotics and Automation_ , vol. 20, no. 2, pp. 243–255, 2004.
  * [34] L. S. Perelman, W. Abbas, X. Koutsoukos, and S. Amin, “Sensor placement for fault location identification in water networks: A minimum test cover approach,” _Automatica_ , vol. 72, pp. 166–176, 2016.
  * [35] J. Milošević, A. Teixeira, K. H. Johansson, and H. Sandberg, “Actuator security indices based on perfect undetectability: Computation, robustness, and sensor placement,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 9, pp. 3816–3831, 2020.
  * [36] J. Pita, M. Jain, J. Marecki, F. Ordóñez, C. Portway, M. Tambe, C. Western, P. Paruchuri, and S. Kraus, “Deployed armor protection: the application of a game theoretic model for security at the los angeles international airport,” in _Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems_ , 2008.
  * [37] B. Bahamondes and M. Dahan, “Network inspection from locations with imperfect detection capabilities,” in _2022 American Control Conference (ACC)_ , 2022, pp. 613–620.
  * [38] B. McCann and M. Dahan, “Network inspection using heterogeneous sensors for detecting strategic attacks,” in _55th Hawaii International Conference on System Sciences (HICSS)_ , 2022, pp. 6802–6811.
  * [39] M. Pirani, J. A. Taylor, and B. Sinopoli, “Strategic sensor placement on graphs,” _Systems & Control Letters_, vol. 148, p. 104855, 2021.
  * [40] J. Milošević, M. Dahan, S. Amin, and H. Sandberg, “A Network Monitoring Game with Heterogeneous Component Criticality Levels,” in _2019 IEEE 58th Annual Conference on Decision and Control (CDC)._ , Dec 2019.
  * [41] A. Washburn and K. Wood, “Two-person zero-sum games for network interdiction,” _Operations research_ , vol. 43, no. 2, pp. 243–251, 1995\.
  * [42] A. Gupta, C. Langbort, and T. Başar, “Dynamic games with asymmetric information and resource constrained players with applications to security of cyberphysical systems,” _IEEE Transactions on Control of Network Systems_ , vol. 4, no. 1, pp. 71–81, 2016.
  * [43] M. Cardei and D.-Z. Du, “Improving wireless sensor network lifetime through power aware organization,” _Wireless Networks_ , vol. 11, no. 3, pp. 333–340, 2005.
  * [44] W.-Q. Wang and H. Shao, “Radar-to-radar interference suppression for distributed radar sensor networks,” _Remote Sensing_ , vol. 6, no. 1, pp. 740–755, 2014.
  * [45] R. Powell, “Sequential, nonzero-sum “Blotto”: Allocating defensive resources prior to attack,” _Games and Economic Behavior_ , vol. 67, no. 2, pp. 611–615, 2009.
  * [46] S. Behnezhad, A. Blum, M. Derakhshan, M. HajiAghayi, M. Mahdian, C. H. Papadimitriou, R. L. Rivest, S. Seddighin, and P. B. Stark, “From battlefields to elections: Winning strategies of Blotto and auditing games,” in _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 2018, pp. 2291–2310.
  * [47] M. Musegaas, L. Schlicher, and H. Blok, “Stackelberg production-protection games: Defending crop production against intentional attacks,” _European Journal of Operational Research_ , vol. 297, no. 1, pp. 102–119, 2022.
  * [48] Y. Freund and R. E. Schapire, “Adaptive game playing using multiplicative weights,” _Games and Economic Behavior_ , vol. 29, no. 1, pp. 79–103, 1999\.
  * [49] C.-Y. Chong and S. P. Kumar, “Sensor networks: evolution, opportunities, and challenges,” _Proceedings of the IEEE_ , vol. 91, no. 8, pp. 1247–1256, Aug 2003.
  * [50] J. C. von Fischer, D. Cooley, S. Chamberlain, A. Gaylord, C. J. Griebenow, S. P. Hamburg, J. Salo, R. Schumacher, D. Theobald, and J. Ham, “Rapid, vehicle-based identification of location and magnitude of urban natural gas pipeline leaks,” _Environmental Science & Technology_, vol. 51, no. 7, pp. 4091–4099, 04 2017.
  * [51] A. Aisopou, I. Stoianov, and N. J. D. Graham, “In-pipe water quality monitoring in water supply systems under steady and unsteady state flow conditions: A quantitative assessment,” _Water Research_ , vol. 46, no. 1, pp. 235 – 246, 2012.
  * [52] USEPA, _EPANET 2.00.12_. Cincinnati, Ohio: U.S. Environmental Protection Agency, 2002, http://www2.epa.gov/water-research/epanet, Accessed: 2014-10-24.
  * [53] L. Perelman, J. Arad, M. Housh, and A. Ostfeld, “Event detection in water distribution systems from multivariate water quality time series,” _Environmental Science & Technology_, vol. 46, no. 15, pp. 8212–8219, 2012\.
  * [54] R. S. Ross, “Guide for conducting risk assessments,” _NIST Special Publication_ , vol. 800, no. 30, 2012.
  * [55] M. D. Jolly, A. D. Lothes, L. Sebastian Bryson, and L. Ormsbee, “Research database of water distribution system models,” _Journal of Water Resources Planning and Management_ , 2013.
  * [56] V. Tzoumas, M. A. Rahimian, G. J. Pappas, and A. Jadbabaie, “Minimal actuator placement with bounds on control effort,” _IEEE Transactions on Control of Network Systems_ , vol. 3, no. 1, pp. 67–78, 2016.
  * [57] F. Pasqualetti, S. Zampieri, and F. Bullo, “Controllability metrics, limitations and algorithms for complex networks,” _IEEE Transactions on Control of Network Systems_ , vol. 1, no. 1, pp. 40–52, 2014.
  * [58] A. R. Bergen and D. J. Hill, “A structure preserving model for power system stability analysis,” _IEEE Transactions on Power Apparatus and Systems_ , vol. PAS-100, no. 1, pp. 25–35, Jan 1981.
  * [59] A. Mohsenian-Rad and A. Leon-Garcia, “Distributed internet-based load altering attacks against smart power grids,” _IEEE Transactions on Smart Grid_ , vol. 2, no. 4, pp. 667–674, Dec 2011.

Jezdimir Milošević received the M.Sc. degree in electrical engineering and
computer science from the University of Belgrade, Belgrade, Serbia, in 2015
and the Ph.D. in electrical engineering and computer science from the KTH
Royal Institute of Technology, Stockholm, Sweden, in 2020.

He is currently a research and development engineer in Scania’s Autonomous
Transport Solutions, Södertälje, Sweden. His research interests are within
cyber-security of industrial control systems.

Mathieu Dahan received the M.S. and Ph.D. degrees in computational science and
engineering from the Massachusetts Institute of Technology, Cambridge, MA,
USA, in 2016 and 2019, respectively.

He is currently an Assistant Professor in the School of Industrial and Systems
Engineering at the Georgia Institute of Technology, Atlanta, GA, USA. His
research interests are in combinatorial optimization, game theory, and
predictive analytics, with applications to service and healthcare operations,
humanitarian systems, and logistics and supply chain management.

Saurabh Amin received the Ph.D. degree in systems engineering from the
University of California, Berkeley, Berkeley, CA, USA, in 2011.

He is currently a Professor with the Department of Civil and Environmental
Engineering. He is a member of the Laboratory for Information and Decision
Systems with the Massachusetts Institute of Technology, Cambridge, MA, USA.
His fields of expertise include control and optimization, applied game theory,
and networks. His research focuses on the design and implementation of
resilient monitoring and control algorithms for networked infrastructure
systems.

Henrik Sandberg (F’23) received the M.Sc. degree in engineering physics and
the Ph.D. degree in automatic control from Lund University, Lund, Sweden, in
1999 and 2004, respectively.

He is currently a Professor with the Division of Decision and Control Systems,
KTH Royal Institute of Technology, Stockholm, Sweden. His current research
interests include security of cyber-physical systems, power systems, model
reduction, and fundamental limitations in control.

Dr. Sandberg was a recipient of the Best Student Paper Award from the IEEE
Conference on Decision and Control in 2004, an Ingvar Carlsson Award from the
Swedish Foundation for Strategic Research in 2007, and a Consolidator Grant
from the Swedish Research Council in 2016\. He has served on the editorial
boards of IEEE Transactions on Automatic Control and the IFAC Journal
Automatica. and the IFAC Journal Automatica.