1 Introduction

Critical infrastructures (CIs) are systems that provide vital services to society, such as the supply of drinking water, electricity, or transportation. Any significant disruption of these services directly threatens the security and the economic system of a society, public health and safety, or any combination of the above [5]. Even small disruptions and component failures can strongly reduce performance and cause major economic damage. Hence, a physical or cyber-attack on a CI generates massive negative externalities, especially because of the increasing interdependency and technical interconnectedness of different CIs. Particularly, the cascading effect of failures among CIs could pose a serious threat to society [2, 10]. Therefore, CIs are an ideal target for terrorist, politically motivated, or criminal attacks.

Such attacks constitute the most dangerous asymmetric threat CIs have to face today and in the future [5]. Hence, there is the need to develop applied models that can evaluate the costs and consequences of intentional attacks on CIs. In this work, infrastructure networks are investigated, and a specific method for evaluating the cost of attacks on CIs is presented. A generic theoretical model is suggested that can account for different network types and attack patterns. The practical application of the model allows the reader to identify weak spots within the network.

2 Background

The model is grounded in solid scientific work from the operations research domain. The model builds on prior work by Brown et al. [6], Golany et al. [9], and Alderson et al. [3] who have all modeled and evaluated attacks on CIs. It employs linear programming and network flow theory [1, 8] and applies prior research on network interdiction [7]. To date, this research resonates little in the communities of experts responsible for CI protection. Attempts to prioritize efforts for critical infrastructure protection typically produce descriptive lists and planning instruments. For instance, both the Swiss Federal Office for Civil Protection, the U.S. Department of Defense, and the U.S. Department of Homeland Security have all prioritized critical infrastructure elements in an attempt to produce comprehensive protection. However, this practice is questionable from a scientific perspective since particular components cannot be prioritized by criticality [2]. The model in this chapter is proposed as an alternative.

3 Methods

3.1 Operator Model

The model assumes that a homogeneous good or service is transported across a network. The network contains supply nodes that provide the good or service, demand nodes that consume it, and transit nodes that transfer it to other nodes.

In order to graphically represent the model, a simple directed graph G = (V, E) is given, where V  represents a set of nodes (the circles in Fig. 1 and all following figures), and E a set of arcs (the arrows in Fig. 1 and all following figures). The set of nodes is partitioned into V = V A ∪ V N ∪ V T, where V A is the set of “supply nodes”, V N the set of “demand nodes” and V T the set of “transit nodes”. The set of arcs E represents the connections between the objects. In this paper, an arc e ∈ E is either indicated as e or by its end nodes e = (v, w).

Fig. 1
figure 1

A small operator network with five nodes

Full size image

For each node v ∈ V , if v ∈ V A, it can provide a (non-negative) supply a v, and if v ∈ V N, it has a (non-negative) demand n v. Each arc e ∈ E has an arc capacity u e, which is the maximal flow of a good or service through the arc (for a given time span), and cost c e for each unit of the good or service transported by this arc.

Figure 1 illustrates this setting for a system with five nodes. In this specific example, node 1 is a supply node with a supply of a v = 7 and node 5 is a demand node with a demand of n v = 5. All other nodes are transit nodes. Each arc e ∈ E is represented by an arrow and a pair of numbers u e;c e which indicate the capacity and the unit cost of the arc.

A solution is sought for a feasible flow \(x \in \mathrm {I\!R}^{E}\) that minimizes total cost (a so-called cost-optimal flow). Thus, a respective flow x e has to be found for every arc e ∈ E. For a given node v ∈ V  the net inflow f x(v) is defined as total inflow less total outflow, formally:

$$\displaystyle \begin{aligned} f_{x}(v)=\sum_{w :(w, v) \in E} x_{w v}-\sum_{w :(v, w) \in E} x_{v w} \end{aligned} $$

A flow is feasible if the flow constraints as well as the capacity constraints are satisfied. The flow constraints state that a supply node cannot provide more than its supply, a demand node must satisfy demand, and a transit node has to relay the flow without losses:

$$\displaystyle \begin{aligned} f_{x}(v) & \leq a_{v} \text{ for all } v \in V_{A}, \end{aligned} $$
$$\displaystyle \begin{aligned} f_{x}(v) &=n_{v} \text{ for all } v \in V_{N}, \end{aligned} $$
$$\displaystyle \begin{aligned} f_{x}(v) &=0 \text{ for all } v \in V_{T}. \end{aligned} $$

The capacity constraints guarantee that the capacity of the arcs is not exceeded:

$$\displaystyle \begin{aligned} 0 \leq x_{e} \leq u_{e} \text{ for all } e \in E. \end{aligned} $$

Among all feasible flows, we seek to find a minimum-cost flow x, i.e. \(\sum _{e \in E}^{ } c_{e}x_{e}\). Together, these conditions yield the following minimum-cost flow problem (P1):

$$\displaystyle \begin{aligned} \min \sum_{e \in E} c_{e} x_{e} \end{aligned} $$

subject to:

$$\displaystyle \begin{aligned} &f_{x}(v) \leq a_{v} \text{ for all } v \in V_{A}, {} \\ &f_{x}(v) =n_{v} \text{ for all } v \in V_{N}, \\ &f_{x}(v) =0 \text{ for all } v \in V_{T}, \\ &0 \leq x_{e} \leq u_{e} \text{ for all } e \in E. \end{aligned} $$
(P1)

Figure 2 gives an optimal solution for the example specified by Fig. 1. For each arc with a positive flow, the calculated flow value is given next to the arc and before the slash. For example, the flow from node 1 to node 2 equals x 12 = 1. In this example, the total cost of this optimal solution is 12.

Fig. 2
figure 2

Cost optimal flow for the network given by Fig. 1

Full size image

3.2 Inclusion of Shortage and Formulation in Standard Form

The above model is now extended and applied to a situation where the network cannot or not completely satisfy all demands. This is done by assigning a penalty cost p v to each demand node v ∈ V . Additionally, all flow constraints are now described by equations in order to formulate the problem in a standard form. Hence, the following elements are added to graph G = (V, E):

  1. (a)

    A pseudo supply node v a with supply \(a_{v_{a}}=\sum _{v \in V_{N}}^{ } n_{v}\)

  2. (b)

    For every demand node v ∈ V N, an arc (v a, v) with cost p v and capacity n v

  3. (c)

    A pseudo demand node v n with demand \(n_{v_{n}}=\sum _{v \in V_{A}}^{ } a_{v}\)

  4. (d)

    For every supply node v ∈ V A ∪{v a}, an arc (v, v n) with zero cost and capacity a v

The pseudo supply node can deliver missing units to demand nodes at penalty cost p v. The resulting graph is denoted by G′ = (V ′, E′). For every node v′∈ V ′ the demand b v is defined as:

$$\displaystyle \begin{aligned} b_{v}=\left\{ \begin{array} {ll}{-a_{v}} & {\text{ if } v \in V_{A} \cup\left\{v_{a}\right\}} \\ {n_{v}} & {\text{ if } v \in V_{N} \cup\left\{v_{n}\right\}} \\ {0} & {\text{ else. }} \end{array}\right. \end{aligned}$$

Figure 3 illustrates these modifications for a unit penalty cost of 100.

Fig. 3
figure 3

Modified model in standard form

Full size image

This extended problem can now be described as follows in G′ = (V ′, E′):

$$\displaystyle \begin{aligned} z=min \sum_{e \in E'}^{ } c_{e}x_{e} \end{aligned}$$

subject to:

$$\displaystyle \begin{aligned} &f_{x}(v) = b_{v} \text{ for all } v \in V^{\prime}, {} \end{aligned} $$
(P2)
$$\displaystyle \begin{aligned} &0 \leq x_{e} \leq u_{e} \text{ for all } e \in E^{\prime}. \end{aligned} $$

It is assumed that the operator runs the network at optimal cost. In this case the value of the optimized solution of the following model simply indicates the “regular” operating costs.

3.3 Modeling an Attack Scenario

It is assumed that an attack on a network can target both nodes and arcs. If an arc is attacked, it becomes inoperative, i.e. its capacity is reduced to zero. If a node is attacked, it cannot deliver supply nor serve as a transit node, but its demand remains unchanged. This situation is modeled by reducing the capacity of all arcs interrupted as a consequence of the attack to zero.

An attack scenario U = (V u, E u) is defined by the sets of attacked nodes V u ⊆ V  and arcs E u ⊆ E. Pseudo nodes and pseudo arcs cannot be attacked. A valid solution for this attack scenario must satisfy the following constraints:

$$\displaystyle \begin{aligned} \begin{aligned} x_{e} &=0 \text{ for all } e \in E_{u}, \\ x_{v w} &=0 \text{ for all } v \in V_{u}, \\ x_{v w} &=0 \text{ for all } w \in V_{u}. \end{aligned} \end{aligned}$$

Once these constraints are added to the model, a given attack scenario U = (V u, E u) can be described as:

$$\displaystyle \begin{aligned} z_{U}=min \sum_{e \in E'}^{ } c_{e}x_{e} \end{aligned}$$

subject to:

$$\displaystyle \begin{aligned} f_{x}(v) &=b_{v} \text{ for all } v \in V^{\prime}, {} \end{aligned} $$
(P3)
$$\displaystyle \begin{aligned} 0 \leq x_{e} & \leq u_{e} \text{ for all } e \in E^{\prime}, \end{aligned} $$
$$\displaystyle \begin{aligned} x_{e}&=0 \text{ for all } e \in E_{u}, \end{aligned} $$
$$\displaystyle \begin{aligned} x_{v w} &=0 \text{ for all } v \in V_{u}, \end{aligned} $$
$$\displaystyle \begin{aligned} x_{v w} &=0 \text{ for all } w \in V_{u}. \end{aligned} $$

If \(V_u = \varnothing \) and \(E_{u} = \varnothing \) then (P3) is equivalent to (P2). Problem (P3) is also a minimum cost flow problem, implying that it can be solved efficiently and that integer input vectors b and u yield integer solutions. This is an important characteristic of network flow problems.

Again, it is assumed that the network is run at optimal cost after an attack. Hence, the target variable z U of an optimal solution of (P3) indicates the operating cost after an attack U = (V u, E u). For every attack U the costs K U are defined as:

$$\displaystyle \begin{aligned} K_{U}=z_{u}-z. \end{aligned}$$

Hence, the operating costs after an attack exceed those of normal operations, i.e. z U ≥ z and hence K U ≥ 0 for any attack U. Figure 4 illustrates an attack scenario U = (V u, E u) with V u = {4} and E u = {(1, 3)}. Only graph G instead of G′ is shown. Dashed arcs are unavailable after the attack. Arcs with a positive flow are underlined. The demand of node 5 can still be met. Total operating cost after the attack is 27, implying the cost K U of the attack is K U = 27 − 12 = 15.

Fig. 4
figure 4

Modified model with an attack on node 4

Full size image

Figure 5 illustrates an attack scenario where only node 2 is attacked, i.e. \(U_2 = (V_{u_{2}},E_{u_{2}})\) with \(V_{u_{2}} =\{2\} \text{ and } E_{u_{2}}=\varnothing \):

Fig. 5
figure 5

Modified model with an attack on node 2

Full size image

The demand at node 5 cannot be fully satisfied. One unit cannot be delivered, implying a penalty cost of 100. The total operating cost of the network is now 106, such that attack has caused a damage of 106 − 12 = 94 monetary units.

3.4 The Attacker-Defender Model

While the CI operators may not know how exactly the network will be attacked in the future, they can assume that a well-informed attacker will likely attempt to maximize any damage, i.e. to maximize the network’s total operating cost. In the following, the model is modified further to reflect this intention. An attacker has a given budget B. Every element of the network has a certain strength, which represents the resources an attacker must invest to disable this element. Specifically, the attacker incurs a cost of p v units for an attack on any node v ∈ V , and a cost of p e units for an attack on any arc e ∈ E. The following decision variables are introduced to model the attack decision:

$$\displaystyle \begin{aligned} &y_{e} \text{ for all } e \in E: y_{e} \text{ is 1 if arc } e \text{ is attacked and 0 otherwise,}\\ &y_{v} \text{ for all } v \in V: y_{v} \text{ is 1 if node } v \text{ is attacked and 0 otherwise.} \end{aligned} $$

Further, the attacker is subject to the budget constraint:

$$\displaystyle \begin{aligned} \sum_{e \in E}^{ } p_{e}y_{e}+\sum_{v \in V}^{ } p_{v}y_{v} \leq B. \end{aligned}$$

In a first step, the attack is modeled by adjusting the arc capacities:

$$\displaystyle \begin{aligned} 0 &\leq x_{e} \leq u_{e} \text{ for all } e \in E^{\prime}-E, \end{aligned} $$
$$\displaystyle \begin{aligned} 0 &\leq x_{e} \leq u_{e}\left(1-y_{e}\right) \text{ for all } e \in E, \end{aligned} $$
$$\displaystyle \begin{aligned} 0 &\leq x_{v w} \leq u_{v w}\left(1-y_{v}\right) \text{ for all }(v, w) \in E, \end{aligned} $$
$$\displaystyle \begin{aligned} 0 &\leq x_{v w} \leq u_{v w}\left(1-y_{w}\right) \text{ for all }(v, w) \in E. \end{aligned} $$

The constraints in the first line address those pseudo arcs whose capacities remain unchanged. For an arc e = (v, w) ∈ E, the capacity is u e unless either arc e or node v or w are attacked. In any of these cases, the constraints in lines 2 to 4 specify that the capacity of any such node or arc is reduced to zero. Hence, the following model results:

$$\displaystyle \begin{aligned} \max_{y} \min_{x} \sum_{e \in E'}^{ } c_{e}x_{e} \end{aligned}$$

subject to:

$$\displaystyle \begin{aligned} &f_{x}(v)=b_{v} \text{ for all } v \in V^{\prime}, {} \end{aligned} $$
(P4)
$$\displaystyle \begin{aligned} &0 \leq x_{e} \leq u_{e} \text{ for all } e \in E^{\prime}-E, \end{aligned} $$
$$\displaystyle \begin{aligned} &0 \leq x_{e} \leq u_{e}\left(1-y_{e}\right) \text{ for all } e \in E, \end{aligned} $$
$$\displaystyle \begin{aligned} &0 \leq x_{v w} \leq u_{v w}\left(1-y_{v}\right) \text{ for all }(v, w) \in E, \end{aligned} $$
$$\displaystyle \begin{aligned} &0 \leq x_{v w} \leq u_{v w}\left(1-y_{w}\right) \text{ for all }(v, w) \in E, \end{aligned} $$
$$\displaystyle \begin{aligned} \sum_{e \in E} p_{e} y_{e}+\sum_{v \in V} p_{v} y_{v} \leq B, \end{aligned}$$
$$\displaystyle \begin{aligned} \begin{array} {l}{y_{e} \in\{0,1\} \text{ for all } e \in E}, \\ {y_{v} \in\{0,1\} \text{ for all } v \in V}. \end{array} \end{aligned}$$

Problem (P4) is a bi-level optimization problem to which standard mathematical solvers such as CPLEX or Gurobi cannot be applied directly. To transform this bi-level into a single-level optimization problem, (P4) is reformulated by following the approach described in Brown et al. [6]. Flows over attacked arcs are penalized, letting M denote a sufficiently high penalty cost. Hence, (P4) can be rewritten as:

$$\displaystyle \begin{aligned} \max _{y} \min _{x} \sum_{e \in E^{\prime}-E} c_{e} x_{e}+\sum_{e=(v, w) \in E}\left(c_{e}+M\left(y_{e}+y_{v}+y_{w}\right)\right) x_{e} \end{aligned}$$

subject to:

$$\displaystyle \begin{aligned} &f_{x}(v)=b_{v} \text{ for all } v \in V^{\prime}, {} \end{aligned} $$
(P5)
$$\displaystyle \begin{aligned} &0 \leq x_{e} \leq u_{e} \text{ for all } e \in E^{\prime}, \end{aligned} $$
$$\displaystyle \begin{aligned} &\sum_{e \in E} p_{e} y_{e}+\sum_{v \in V} p_{v} y_{v} \leq B, \end{aligned} $$
$$\displaystyle \begin{aligned} &y_{e} \in\{0,1\} \text{ for all } e \in E \end{aligned} $$
$$\displaystyle \begin{aligned} &y_{v} \in\{0,1\} \text{ for all } v \in V. \end{aligned} $$

The solution spaces of (P4) and (P5) are not identical but if M is chosen correctly, the optimal solutions and the optimal objective values are the same in both problems. (P5) is still a bi-level optimization problem, but the inner optimization problem can be transformed using duality theory [8]. Informally speaking, the inner optimization problem (P5) is transformed into a maximization problem while the value of the optimal solution stays the same. Two types of dual variables are introduced: α v for each flow constraint of node v ∈ V ′ in (P5) and β vw for each capacity constraint of arc (v, w) ∈ E′ in (P5). Developing the corresponding dual constraints for all primal variables and the dual objective function, the following dual problem is obtained:

$$\displaystyle \begin{aligned} \max \sum_{v \in V'}^{ } b_{v}\alpha_{v}-\sum_{e \in E'}^{ } u_{e}\beta_{e} \end{aligned}$$

subject to:

$$\displaystyle \begin{aligned} \alpha_{w}-\alpha_{v}+\beta_{v w} & \leq c_{v w} \text{ for all }(v, w) \in E^{\prime}-E, {} \end{aligned} $$
(P6)
$$\displaystyle \begin{aligned} \alpha_{w}-\alpha_{v}+\beta_{v w} & \leq c_{v w}+M\left(y_{e}+y_{v}+y_{w}\right) \text{ for all } e=(v, w) \in E, \end{aligned} $$
$$\displaystyle \begin{aligned} \beta_{e} & \geq 0 \text{ for all } e \in E^{\prime}. \end{aligned} $$

The inner optimization problem of (P5) always has a solution and the optimum is limited since all cost factors c e are positive. In this case, the objective value of the optimal solution of (P6) equals the objective value of (P5). Hence, the inner optimization problem (P5) can be replaced by (P6), which yields the following re-formulation of (P5):

$$\displaystyle \begin{aligned} \max \sum_{v \in V'}^{ } b_{v}\alpha_{v}-\sum_{e \in E'}^{ } u_{e}\beta_{e} \end{aligned}$$

subject to:

$$\displaystyle \begin{aligned} \alpha_{w}-\alpha_{v}+\beta_{v w} &\leq c_{v w} \text{ for all }(v, w) \in E^{\prime}-E, {} \end{aligned} $$
(P7)
$$\displaystyle \begin{aligned} \alpha_{w}-\alpha_{v}+\beta_{v w} &\leq c_{v w}+M\left(y_{e}+y_{v}+y_{w}\right) \text{ for all } e=(v, w) \in E, \end{aligned} $$
$$\displaystyle \begin{aligned} \beta_{e} &\geq 0 \text{ for all } e \in E^{\prime}, \end{aligned} $$
$$\displaystyle \begin{aligned} &\sum_{e \in E} p_{e} y_{e}+\sum_{v \in V} p_{v} y_{v} \leq B, \end{aligned} $$
$$\displaystyle \begin{aligned} &y_{e} \in\{0,1\} \text{ for all } e \in E, \end{aligned} $$
$$\displaystyle \begin{aligned} &y_{v} \in\{0,1\} \text{ for all } v \in V. \end{aligned} $$

Problem (P7) is a mixed-integer linear program. While we specify this problem here, we also note that current optimization solvers, such as CPLEX and GUROBI, are not able to find optimal solutions for large-size instances of this problem in acceptable computation time. Future research may focus on improving the numerical analysis and compatibility of this linear program.

3.5 Application to a Small Example

The attacker-defender model is now applied to the operator network example. The strength p e of each arc e ∈ E is indicated at the third position of the respective data lines next to the arcs. Nodes are considered infinitely resilient, i.e. p v = ∞ for all v ∈ V :

Table 1 below gives optimal attack strategies for different attack budgets B. It demonstrates that there is no straightforward correlation between the attack budget and the number of attacked arcs.

Table 1 Optimal attacks and cost of these attacks for all attack budgets
Full size table

To illustrate this fact, Figs. 6, 7 and 8 give the respective graphs for attack budgets of B = 1 and B = 13. Although the cost of the attack increases by a factor of more than 81 in the latter scenario, only two more arcs are attacked.

Fig. 6
figure 6

Application of the model to an attack on arcs

Full size image
Fig. 7
figure 7

Optimal attack strategy for B = 1

Full size image
Fig. 8
figure 8

Optimal attack strategy for B = 13

Full size image

Further, a particular arc need not constitute an attractive target in an optimal strategy anymore as the attack budget increases. This effect shows as B is increased from 1 to 2 and from 9 to 10.

Hence, optimal attacking strategies are not nested with respect to an increase in B. This implies that network elements cannot be prioritized by criticality, which confirms the initial criticism of [3].

3.6 Application to the Anytown Network

The Anytown Network is a modeling tool for diverse problems in network design. To apply it, I used data from the University of Exeter Centre for Water Systems.Footnote 1 In all following diagrams, nodes T41 and T42 are water reservoirs whose analysis is not required for the purposes of our model.

The model allows for bidirectional flows and hence specifies bidirectional arcs whose capacity is identical. All arcs have unit cost 1 and the penalty cost for all demand nodes is 1000 per missing unit. It is assumed that all nodes and arcs incident to node 1 cannot be attacked, while all other arcs have a strength of 1. We calculated models and generated their corresponding graphs for all attack budgets. For reasons of space only a selection of the results is discussed here. The full set of graphs is available on request.

Figure 9 shows the results of an attack on the network for B = 3. A subsection of the graph (nodes 5, 6 and 7) is cut off from both the remaining nodes and from the source, as illustrated by the bold dashed line.

Fig. 9
figure 9

Attack on the Anytown network for B = 3

Full size image

Figure 10 illustrates an attack for B = 7. While the graph remains strongly-connected, several central elements are attacked, and bidirectional flow is significantly reduced, implying a significant increase in operating cost.

Fig. 10
figure 10

Attack on the Anytown network for B = 7

Full size image

Figure 11 shows the results for an attack budget of B = 9. The graph is split into two sub-graphs, and no other nodes than those directly linked to node 1 can be operated.

Fig. 11
figure 11

Attack on the Anytown network for B = 9

Full size image

4 Conclusion and Outlook

In this chapter, the cost of an attack on critical infrastructure networks was assessed with a generic model. This model was implemented as a mixed-integer linear program and applied to several small-scale examples. Future work could use this operationalization to analyze actual infrastructures, such as energy or drinking water networks. While the challenges of modeling such real networks are anything but trivial, related work may draw on some of the ideas presented here.

Further, the attacker-defender model considered here could be extended to scenarios where the operator attempts to protect the infrastructure in question by investing into the strength of the network. Such an operator would use a particular defence budget to invest in measures that minimize the maximum costs of an attack (e.g., by increasing the robustness or redundancy of critical components). Future work may analyze optimal investment strategies for this defence budget. While the analysis of such defender-attacker-defender models [4, 6] builds on the basic scenarios we have illustrated here, it is significantly more complex.