# Computing Effective Mixed Strategies for Protecting Targets in Large-Scale Critical Infrastructure Networks Zhen Wang, et al.

Dec 30, 2021

## 1 Introduction

In recent years, malicious activities against the critical infrastructures lead to new challenges to the world’s security, which have inflicted enormous economic losses and threatened public safety. For instance, in July 2019, a cyber attack on a Venezuelan hydroelectric power plant collapsed the water grid in the capital and more than 10 states, plunging the entire country into darkness [1]. Very recently, the largest oil pipeline company in the United States, Colonial Pipeline, was attacked by the hacker organization DarkSide, which led the country to announce an emergency state [2]. Thus, analyzing the robustness of the critical infrastructure networks against the malicious attacks and accordingly improving the efficiency of defending the targets with limited resources remain major problems.

Prior works have designed methods to protect the critical infrastructure networks against malicious attacks, and we summarize them into three classes. The first class comes up with adding nodes (e.g., adding additional base stations), adding edges (e.g., adding additional power lines), or swapping edges (e.g., rewiring power lines) to enhance the network robustness [35]. But these methods will change the network structure, while the structure of a network is a defining characteristic that can identify its functionality and thus should remain unchanged. The second class proposes resource-allocation methods to significantly reduce the time cost of allocating resources and increase the probability of successful defending tasks, considering the cooperativity between resources and tasks [6, 7], which will increase the complexity of the defending problem. The third class develops algorithms to monitor (e.g., closely monitor substation) or immunize important nodes for protecting networks, according to a range of network centrality measures (e.g., degree centrality and betweenness centrality) [813]. However, all these existing centrality metrics do not consider the protector’s combinatorial pure policy space. Though these defending policies can protect the network against attacks to a certain extent, we can consider mixing the pure strategies and scheduling the defense resources dynamically to design more protective defending strategies.

To address the problem of designing more robust measures for defending the critical infrastructure networks, we can model the urban infrastructure cybersecurity problem as a problem with both defender and attacker participants. The infrastructure-based confrontation between the attacker and the defender can be modeled using game theory. However, most of the research studies that compute the attack and defense strategies by establishing different game models only consider a few typical strategies to shrink the space of strategies, rather taking a large strategy set into account [1419]. Only one article is distinct; Li et al. proposed the two-player zero-sum simultaneous-move game model to solve the defending problem [20]. Their algorithm enumerates all strategies for obtaining the Nash equilibrium (ESE) on the network with 20 nodes and computes mixed strategies for both players. Unfortunately, their algorithm cannot solve the problem of computing the global equilibrium in large-scale networks. So, the challenge is how to compute effective strategies with the full strategy space of both players growing exponentially with the increase of the network size.

To solve the pervious challenge, based on the existing two-person zero-sum model and settings, we propose our solution containing four key contributions:

1) First, we extend the defending problem to a real large-scale infrastructure network that is vulnerable.

2) Second, we propose the effective mixed strategies for large-scale networks (EMSL) algorithm, which is based on greed under the Double Oracle framework to obtain an effective defense solution.

3) Third, we design mixed-integer linear programming (MILP) to compute the best pure attack strategy for an attacker.

4) Finally, we conduct extensive experiments on two networks of different sizes by comparing with other defense strategies under different attacks. The experimental results show that the mixed defense strategies obtained by our approximation algorithm bring the highest utility to a defender on different networks when dealing with different attacks.

## 2 Infrastructure Network Protecting Game

As in the pioneering work [14], we define the problem of protecting targets in infrastructure networks as a single-round defender–attacker zero-sum game. The defender chooses a subset of nodes to protect, while the attacker chooses some nodes to attack in the target network. Only the nodes chosen by the attacker, meanwhile not protected by the defender, will be removed from the network, and then the payoff function for both players is determined by the remaining network. Both players are assumed to have the complete information of the target network and full knowledge about the opponent. Hence, they are fully aware of all the strategies that the opponent may adopt, as well as the payoffs to each other under each combination of strategies. Nevertheless, the game is a simultaneous one, that is to say, the players do not know exactly which nodes the opponent will choose when making their own decisions.

### 2.1 Network

The infrastructure system can be easily abstracted as a target network, which is formalized in terms of a simple undirected graph G = (V, E). Each node vV represents an infrastructure, where V is the set of nodes in the network. An edge eij = (vi, vj) ∈ E denotes a directionless edge with vi and vj as endpoints, while EV × V denotes the set of edges. We define N = |V| as the number of nodes in the network.

The connectivity between nodes is the equivalence relation on the node vV. Based on the equivalence relation, V can be divided into several non-empty subsets V1, V2, …, Vn, and each non-empty subset Vi determines a connected subgraph G(Vi). Especially for a node vV, we denote the node’s connected neighbors as follows:

$V′=u∈Vv|u,v∈E,distanceu,v≠∞,v∈V,(1)$

where distance(u, v) ≠ indicates that there always exists a path from u to v. The connected subgraph

$(V′,E∩V′2)$

induced by V′ is denoted by G(V′). So, G(V1), G(V2), …, G(Vn) are defined as the connected components of G. Let G(Vmax) represent the largest connected component (LCC) of G, where Vmax is defined as the largest connected node subset of V.

Let

$Ṽ⊆V$

denote the subset of nodes in V and

$Ẽ⊆E$

denote the set of edges where each edge in

$Ẽ$

is connected to at least one node in

$Ṽ$

. The graph

$Ĝ=(V̂,Ê)$

obtained by removing all nodes in

$Ṽ$

and all associated edges in

$Ẽ$

from G is expressed as follows:

### 2.2 Strategies

A pure defender strategy D = ⟨dv⟩ is an assignment of the RD defending resources to RD vertices, that is, vVdv = RD, where dv ∈ {0, 1}. dv = 1 indicates the node v is protected by a defender and will never be deleted. We define the set of nodes protected by the defender as VD = {vV|dv = 1}, where |VD| = RD. The defender’s strategy space is defined as

$D$

. So, a mixed attacker strategy x = ⟨xD⟩ is a probability distribution over pure strategies, with xD representing the probability that the pure strategy D is played.

Meanwhile, the attacker can choose a subset of nodes VAV to plan an attack. A pure attacker strategy is defined as a vector

$A=⟨av⟩∈A$

, where

$A$

represents the attacker’s strategy space and vVav = RA indicates that the attacker’s resource number is RA. If vVA, then av = 1; otherwise, av = 0. A mixed attacker strategy y = ⟨yA⟩ is a probability distribution over pure strategies, with yA representing the probability that the pure strategy A is played.

### 2.3 Utility

In our defender–attacker zero-sum game, given a defender’s strategy D and an attacker’s strategy A, only when av = 1, and dv = 0, the node v will be deleted from the network by the attacker; otherwise, the defender protects the targets successfully. If the attacker succeeds, he will receive a payoff PA and the defender’s payoff PD will be − PA; otherwise, both players will gain 0.

In many critical infrastructure systems, the targets are networked and the functionality relies heavily on the connectivity and topology structures. If the network connectivity decreases during the node deletion, the performance of the networks will degrade. The node number of the largest connected component (NLCC) of the graphs is a robust measure function which is widely used to evaluate the network performance. Hence, we adopt NLCC to construct the payoff functions. NLCC(G) is calculated by determining the maximal connected node subset VmaxV in G [21], and it can be expressed as follows:

If the defender’s strategy D and the attacker’s strategy A select sets of nodes differently, that is, VAVDVD, which means the defender fails in protecting the targets and the attacker succeeds, then the node subset

$Ṽ=VA−VA∩VD$

and its associated edge set

$Ẽ$

will be deleted from the target network, and we define

$V̂max⊆(V−Ṽ)$

as the largest connected node subset of the residual graph

$Ĝ$

.

$NLCC(Ĝ)$

is computed by determining the size of

$V̂max$

as follows:

where

$V̂max⊆(V−(VA−VA∩VD))$

in

$Ĝ$

. Otherwise, if the defender protects the network successfully, that is, VAVD = VD = VA, which means that no node will be deleted from G, then

$NLCC(Ĝ)=NLCC(G)$

.

Hence, the payoff function of the attacker PA is defined as follows:

$PA=NLCCG−NLCCĜNLCCG∈0,1(5)$

and the defender’s payoff function PD is given as follows:

$PD=NLCCĜ−NLCCGNLCCG∈−1,0,(6)$

where NLCC can be replaced by any other measure functions that meet the monotonicity assumption.

After the payoff functions of the players are obtained, we define UD as the expected utility function of the defender. Given a defender’s mixed strategy x and an attacker’s pure strategy A, the expected defender utility UD(x, A) is given as follows:

$UDx,A=∑D∈D1−zD,AxDPD,(7)$

where zD,A indicates whether the defender strategy D successfully protects the targets that are attacked by A, that is, zD,A = 0 if DA = D or 1 otherwise.

The defender’s expected utility UD(D, y) of playing a pure defense strategy D against the mixed attack strategy y is

$UDD,y=PD∑A∈A1−zD,AyA.(8)$

When playing a mixed defense strategy x against the mixed attack strategy y, the defender’s expected utility UD(x, y) is given as follows:

$UDx,y=∑D∈DxDUDD,y=∑A∈AyAUDx,A.(9)$

Generally, based on the two-person zero-sum game, we note UA = − UD.

### 2.4 Equilibrium

The Nash equilibrium of two-person zero-sum games is the maximum equilibrium. The aim of the defender is to protect the target nodes of the network to maximize their minimum utility and minimize the attacker’s maximum utility. We use linear programming to solve the zero-sum game. The defender’s optimal mixed strategy x can be computed by solving the following linear programming (LP):

$s.t.U≤UDx,A,∀A∈A,(11)$

When the strategy spaces of both sides are small, the optimal solution can be obtained by solving the programming Equations 1014. However, as the network scale expands, the defender’s strategy space

$D$

and the attacker’s strategy space

$A$

will grow exponentially with the number of resources RD. At this time, it is difficult to calculate the optimal solution in a short time by mathematical programming, so it is necessary to design new algorithms to get efficient strategies for both players.

## 3 Approach

In this section, we first give a brief introduction to the ESE algorithm, which is very similar to the problem solved in this study [20], and analyze the limitations of the algorithm. Then we propose our EMSL algorithm and describe it in detail.

### 3.1 Limitation of ESE Algorithm

The ESE algorithm is adopted by Li et al., which solves the attacker–defender game by computing the global equilibrium with full strategy space on a small network [20]. First, they enumerate all possible attack and defense strategies and calculate the payoffs of the players in each strategy to construct the payoff matrix. Next, they start the two-person zero-sum game by choosing nodes with the largest degrees to attack, satisfying the resource constraint, and identify the defender’s best response to the attacker’s strategy. Then they compute the best response pure strategies over the payoff matrix for the players. Finally, the Nash equilibrium is computed to calculate the players’ best mixed response strategies over each pure strategy.

Unfortunately, the ESE algorithm can only be solved on the network with 20 nodes. Since the strategy space is too large as the network scale grows, it is very time-consuming to calculate the payoffs in each strategy profile one by one. It is impossible to solve the problem by enumerating all strategies to maximize the benefits of both the attacker and the defender. So, the ESE algorithm cannot be applied to real large-scale networks due to its limited computing power.

We find that the interaction process of the players in the ESE algorithm is similar to the Double Oracle (DO) framework. The DO framework is a standard method for solving zero-sum games with large strategy spaces.

However, there are two challenges to solving the INP game under the DO framework: 1) We can only present the MILP for computing the best response strategy of the attacker (in Section 4.2), and we solve it on the network with 20 nodes. The best attack method is used as an attack method for comparison in the experiments. But it is difficult to present the MILP for computing the best response strategy of the defender because of the weakness of high complexity. 2) Computing the MILP is time-consuming, and it is difficult to solve it for an optimal solution on large networks. We aim to find an efficient solution for the INP problem, but not an optimal solution. The effective solution can be obtained by designing an approximate algorithm under the suboracles of DO framework. Hence, we propose the effective mixed strategies for large-scale networks (EMSL) algorithm for computing the improved solution.

### 3.2 EMSL Algorithm

To solve the INP problem, we propose our EMSL algorithm based on greedy search under the DO framework. The DO framework can efficiently solve the zero-sum games on real large networks. For instance, Jain et al. proposed the SNARES algorithm to solve the security scheduling problem on the Mumbai road network with 9,503 nodes and 20,416 edges [22]. And Wang et al. introduced the DO-TPD algorithm to compute an optimal monitoring strategy for detecting terrorist plots on realistic-sized problems, which contains about 100 such potential terrorists in some 1,400 French nationals [23]. The DO framework is formed from Defender Oracle and Attacker Oracle. And both of the oracles contain Best Oracle and Better Oracle. Best Oracle can compute the optimal solution by solving the MILP, instead of enumerating all possible strategies, while Better Oracle can improve the computing efficiency for an approximate solution. Due to the challenges of solving Best Oracle mentioned in Section 3.1, we design the EMSL algorithm under Better Oracle (EMSL-Better-O). It is sketched in Algorithm 1.

Algorithm 1 EMSL-Better-O overview

$G,RD,RA$

.

Line 1 first initializes EMSL-Better-O by generating a small strategy space

$⟨D′,A′⟩$

randomly. Then Equation 9 computes the equilibrium with

$⟨D,A⟩$

replaced by

$⟨D′,A′⟩$

to solve the restricted version of INP (CoreLP, Line 3). The restricted INP can be solved efficiently because the strategy space

$⟨D′,A′⟩$

is small. Obviously, the solution obtained is an equilibrium of the restricted INP and does not form an equilibrium to the original INP. So, both players want to improve their utilities with other strategies out of

$⟨D′,A′⟩$

. EMSL-Better-O allows them to do so with Better Oracle (Lines 4–5 and Lines 6–7). Specifically, EMSL-Better-O calls BetterO-D (Better Oracle for Defender) to search a set of improving strategies for the defender (Lines 4–5). And in the similar manner, EMSL-Better-O calls BetterO-A (Better Oracle for Attacker) to find improving strategies for the attacker (Lines 6–7). The process repeats until no improving strategy can be found for both players (Line 8), when the final solution obtained for the original INP is close to optimal.The EMSL-Better-O algorithm of Defender Oracle (EMSL-Better-OD) is presented in Algorithm 2. EMSL-Better-OD generates a defender pure strategy DBetter. The core of each iteration (Lines 5–8) is designed based on the greedy search.

Algorithm 2 EMSL-Better-OD (x, y).

EMSL-Better-OD repeatedly starts from an empty strategy space

$DBetter$

and initializes a random pure strategy

$D∈D$

(Lines 1–2). Then in a greedy manner, it iteratively applies

$GreedySearchv,D,x$

(Algorithm 3) for a new local optimal strategy D′ that brings the maximum utility to the defender (Line 6). Afterward, the strategy set D is updated systematically by D′ (Lines 7–8). The loop repeats until the termination conditions are met: 1) UD (D, y) > UD (x, y); 2) D+ = ∅; and 3) UD (D, y) − UD (x, y) ϵ, where ϵ is a pre-defined global variable to constrain the total number of iterations. The defense strategy

$DBetter$

is computed over the local optimal strategies (Lines 9–10). Compared with enumerating all strategies to construct a payoff matrix and calculating the global equilibrium, our algorithm based on greedy search effectively improves the computing power.

Algorithm 3 GreedySearch(v, D, x).

The goal of GreedySearch (v, D, x) is to find a pure defense strategy that can improve the defender’s utility. It repeatedly starts from an empty strategy D = ∅, and it consecutively tries to add a best node v′ in the hope of improving the defender’s utility UD (Line 4). If the node v′ satisfies UD (D ∪ {v′}, y) > UD (D, y), then DD ∪ {v′} (Lines 5–6); otherwise, it tries to add a best node v′ from the rest node set D{v′} (Line 8). If UD (D{v′}, y) > UD (D, y), then DD{v′} (Line 9–10). Finally, it stops when |D| = RD. Note that the utility function is a submodular set function, which guarantees the approximate solution a

$(1−1e)$

approximation ratio to the optimal solution [24].The time complexity of our approximate algorithm is O(N2), and the spatial complexity is S(N2), where N is the size of the networks. Our algorithm can be solved within a limited time complexity.

## 4 Experimental Results and Analysis

$15*N$

(see Section 4.3.1), and the attack resource number RA is set to be equal and variable from 0 to N. We conduct experiments on two types of graphs with N1 = 20 and N2 = 500.

In this section, the defense methods for comparison and the attack methods for confrontation are introduced first. Then the solution of the approximate algorithm on two different networks is presented and analyzed.

### 4.1 Defense Methods for Comparison

It is essential to prove the effect of the defender’s mixed strategies with other defense methods. The typical defense methods we used for comparison are as follows:

1) ID Defense [25]: In the initial network, the degree of each node is first calculated in the network, and then the vertex is chosen in descending order from the highest vertex to defense. After each attack, the network structure will change, and the degree of each node may also change, but it will not be recalculated. That is to say, the defending strategy uses the initial degree distribution, so we call it the “ID Defense” method.

2) IB Defense [25]: In the initial network, the betweenness of each node is calculated first, and then the vertex is selected for defense according to the descending order of betweenness. Similarly, this defending strategy is also distributed according to the initial mediation degree, so it is called the “IB Defense” method.

3) RA Defense: In the initial network, nodes are randomly selected for defense. In this article, we call it the “RA Defense” method. It should be noted that although random selection seems to be the most convenient way, some key nodes may be selected, which makes the experimental results accidental. In order to avoid the occurrence of the previous situation, we will repeat the process of selecting nodes randomly and calculating the results when carrying out RA Defense. Finally, the average of all the results is calculated as the final result.

4) DCM Defense [26]: In the initial network, nodes are defended by the mixed strategies, where the marginal coverage probability of each vertex is normalized degree centrality. Given the marginal coverage probabilities, the mixed strategies are generated using the comb sampling algorithm.

### 4.2 Attack Methods

Considering the actual situation that attackers may take many kinds of attacks to achieve their goals, it is also important to verify that the defender’s mixed strategy obtained by the approximate algorithm is efficient due to different attacks. Many relative works analyze the robustness of the critical infrastructure networks against malicious attacks. The first class estimates the robustness by removing nodes or edges based on the load capacity [2730]. The second class comes up with removing some nodes or edges based on the degree distribution or betweenness distribution of the networks [10, 28, 29, 25, 13, 31, 32]. The third class develops the method of the tabu search into the network disintegration problem to identify the optimal attack strategy is introduced [33].

So, based on the model and scenario of this study, the attack methods we chose for confrontation are as follows:

1) ID Attack: Attacking nodes based on the initial degree distribution of the network.

2) IB Attack: Attacking nodes based on the initial betweenness distribution of the network.

3) RA Attack: Attacking nodes randomly in the networks.

4) BEST-OA Attack: Attacking nodes with the best attack strategy. We consider the worst case, that is, assuming that the attacker always chooses the most destructive attack method. So, we use mixed-integer linear programming (MILP) to solve the best pure attack strategy for an attacker, and it is called the “BEST-OA Attack” method. The MILP is shown in the following equations:

$max∑D∈DNLCCG−NLCCĜNLCCG⋅xD(15)$
$s.t.∑D∈DxD=1,xD≥0,∀D∈D,(16)$
$∑i=1Nav=RA,av∈VA,av∈0,1,(17)$
$∑i=1Ndv=RD,dv∈VD,dv∈0,1,(18)$
$dv⋅av−dv
$viDA+vjDA−1≤eijDA,viDA∈0,1,eijDA∈0,1,(20)$
$eijDA≤viDA,eijDA≤vjDA,(21)$
$σjkDA−σikDA≥eijDA−1,σijDA∈0,1,(22)$
$NLCCĜ≥∑vi∈VDσijDA,(23)$

where

$viDA=1$

represents the node vi is still in

$Ĝ$

when it is attacked by A under the protection of D; otherwise,

$viDA=0$

.

$eijDA=1$

represents the edge between nodes vi and vj is still in

$Ĝ$

when it is attacked by A under the protection of D; otherwise,

$eijDA=0$

.

$σijDA=1$

represents nodes vi and vj are still in the same connected subgraph when they are attacked by A under the protection of D; otherwise,

$σijDA=0$

. Specifically, σii = 1. Equations 1923 constrain the existence of connected subgraphs after attack. The goal of defenders in best attack oracle is to verify an optimal attack strategy over the entire pure strategy space. Unfortunately, solving best attack oracle turns out to be NP-hard, and the MILP only can be solved on small networks [23].

### 4.3 Solution of the Approximation Algorithm

To verify the performance of the mixed defense strategies, we solve the defender–attacker model by conducting experiments on a small network with 20 nodes first, which is used by Li [20], and then extend to the U.S. air transportation network with 500 nodes [34]. At the same time, the evolution of robustness of networks is analyzed under two topological changes.

##### 4.3.1 Effectiveness of the Mixed Defense Strategies on Small Network

A small network topology structure with 20 nodes is shown in Figure 1. The numbers of attack resources RA and defense resources RD are set to be equal and variable from 0 to 20. To validate the effectiveness of the mixed strategy in small networks, we compare the results with those of some other typical defense strategies under different attack methods. The typical defense strategies for comparison here are ID Defense, IB Defense, RA Defense, DCM Defense, and NO Defense which means RD = 0. The curve of NO Defense is shown as a baseline. And the attack strategies used in this section are ID Attack, IB Attack, RA Attack, and BEST-OA Attack. These comparison defense strategies and attack strategies have been introduced in the previous subsections.

FIGURE 1. Topology structure of a small network with 20 nodes [20].

### • Effectiveness Analysis

As shown in Figures 2A–D, what the curves represent are the defender’s utility, while RD = 4 and RA is variable from 0 to 20 on a small network. The vertical axis represents the defender’s utility, and the horizontal axis represents the number of attack resources. A higher defender utility indicates a lower attacker utility given the zero-sum assumption as well as better performance of the mixed defense strategy. The results show that with the increase of attack resources, the decline rate of defender’s utility is the slowest under the protection of the mixed defense strategy. And no matter in which attack mode, the defender’s utility obtained by the mixed defense strategy is higher than that obtained by other defense methods, especially in the case of RA Attack. Although under IB Attack, the results of IB defense, RA Defense, and mixed strategy defense are close to each other, the mixed strategy is still performing the best (Figure 2B). The results are sufficient enough to indicate the effectiveness of our approximation algorithm in small networks.

• Optimal defense resource number based on unit resource efficiency

FIGURE 2. These are defender’s utility of the mixed defense strategy and other comparison defense methods under different attack methods while RA = 4 on small network with |V| = 20. RD is variable from 0 to 20. (A) is the defender’s utility when playing ID Attack strategy with different defense strategies. (B) is the defender’s utility when playing IB Attack strategy with different defense strategies. (C) is the defender’s utility when playing RA Attack strategy with different defense strategies. (D) is the defender’s utility when playing BEST-AO Attack strategy with different defense strategies.

With the network growing, it is essential to define the optimal defense resource number RD. We define the number of resources per unit as 1 resource, adding one unit of resources per experiment. Then we repeatedly calculate the increment of the defender’s profit after adding the unit resource under different defense and attack methods. Finally, we calculate the defender’s average profit increment. The number of defense resources that maximize the defender’s average profit increment is defined as the optimal defense resources.

For example, Table 1 shows the benefits of the defender when the BEST-OA Attack method confronts the ID Defense method, while RA and RD are from 1 to 10. Table 2 shows the increment of the defender’s profit after each increase of unit resources. And Table 3 shows the average value of the defender’s profit increment. We find that when the number of resources is 4, the average increment of the defender’s utility is the biggest. So, the optimal defense resource number is 4, which is equivalent to

$15$

of the total node number on the network with 20 nodes. Hence, when we expand the experiments to a large network of 500 nodes, the corresponding optimal number of defense resources is 100. It is convenient to find the optimal defense resource number in large networks with the aforementioned method, which also can reflect the significance of the experimental results more clearly and intuitively.

TABLE 1. Utility of the defender when the BEST-OA Attack method confronts the ID Defense method.

TABLE 2. Increment of the defender’s utility.

TABLE 3. Average value of the defender’s utility increment.

##### 4.3.2 Effectiveness of the Mixed Defense Strategies on Real Large-Scale Network

Then to evaluate the solution quality of the approximate algorithm on large-scale networks, we conduct experiments on the U.S. air transportation network with 500 nodes [34], and the defense resource number is set to be RD = 100. We separately analyze the results of the mixed defense strategy and the mixed attack strategy to further test the performance of the mixed defense strategy. The experimental results are shown in Figures 3A–D and Figures 4A–F.

FIGURE 3. These are defender’s utility of the mixed defense strategy and other comparison defense methods under different attack methods while RD = 100 on the air transportation network with |V| = 500. RA is variable from 0 to 500. (A) is the defender’s utility when playing ID Attack strategy with different defense strategies. (B) is the defender’s utility when playing IB Attack strategy with different defense strategies. (C) is the defender’s utility when playing RA Attack strategy with different defense strategies. (D) is the defender’s utility when playing Mixed Attack strategy with different defense strategies.

FIGURE 4. These are defender’s utility of the mixed defense strategy and other comparison defense methods under different defense methods while RD = 100 on the air transportation network with |V| = 500. RA is variable from 0 to 500. (A) is the defender’s utility when playing different attack strategies with no defense. (B) is the defender’s utility when playing ID Defense strategy with different attack strategies. (C) is the defender’s utility when playing IB Defense strategy with different attack strategies. (D) is the defender’s utility when playing RA Defense strategy with different attack strategies. (E) is the defender’s utility when playing Mixed DCM strategy with different attack strategies. (F) is the defender’s utility when playing Mixed Defense strategy with different attack strategies.

In Figures 3A–D, these graphs show the defender’s utility when using the mixed defense strategy and other comparison defense methods under different attack methods while RD = 100 on the real large-scale network. All the steps and comparison defense strategies of the experiments in this subsection are the same as in Subsection 4.3.1. The attack methods for confrontation are changed to ID Attack, IB Attack, RA Attack, and mixed strategy attack. Since the best attack strategy computed by MILP can only be solved in small networks due to its limited solving ability, we compute the mixed attack strategy by solving the approximate algorithm. In particular, we find that under IB Attack, the curves of IB Defense and mixed strategy defense are almost coincident (Figure 3B), which indicates that IB Defense performs well in dealing with IB Attack and also reflects that our approximation algorithm may fall into local optimization. The final result of our approximate algorithm depends in part on its initial solution. Anyway, in most cases, the results can be better than those of other methods. These figures obviously describe that under the mixed strategy defense, the decline rate of defender’s utility is the slowest no matter which attack strategy is used, and the mixed defense strategy can still work well under different attacks in large-scale networks.

Figures 4A–F show the defender’s utility when using the mixed attack strategy and other comparison attack methods confronting different defense strategies while RD = 100 on the same real large-scale network. The comparison attack strategies and defense strategies are all the same. The results clearly show that no matter in which attack strategy, the mixed defense strategy always brings the highest utility to the defender and can make the defender’s utility decline the slowest in the shortest time. Moreover, it is worth mentioning that the defender’s utility obtained by the mixed attack strategy declines the fastest, which also reflects the mixed defense strategy solved by the approximate algorithm can effectively destroy the networks. In summary, these results certainly reflect that the mixed defense strategy performs well in large-scale networks and our approximate algorithm can solve the problem efficiently when scaling up the networks.

## 5 Conclusion

It is a challenge to reasonably design effective defense strategies with limited resources to protect large-scale critical infrastructure networks against malicious attacks. In this study, we first develop an efficient approximation algorithm under the Double Oracle framework to speed up the calculation for computing the mixed defense strategy based on heuristics significantly with given resources. Then we extend the INP problem to a real large-scale infrastructure network to test the performance of the mixed defense strategy. Finally, we conduct extensive experiments on two networks of different sizes by comparing with other defense strategies under various attacks. The experimental results show that our approximation algorithm can ensure a robust enough solution to protect real large-scale networks.

## Data Availability Statement

The original contributions presented in the study are included in the article/Supplementary Material, and further inquiries can be directed to the corresponding author.

## Author Contributions

ZW contributed to the conception of the study. MJ performed the data analyses and wrote the manuscript. YY performed the experiments. LC and HD helped perform the analysis with constructive discussions.

## Funding

This research was supported by the Zhejiang Provincial Natural Science Foundation of China (No. LY20F030012) and National Natural Science Foundation of China (62176080).

## Conflict of Interest

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

## Publisher’s Note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors, and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.