A Strategy to Improve Infrastructure Survivability via Prioritizing Critical Nodes Protection

Abstract

From an engineering point of view, the survivability of a system is defined as its ability to continue to operate despite a natural or human-made disturbance; for example a serious mechanical fault, a human error, or a malicious cyber or physical attack. In the context of critical infrastructures, due to their relevance for the public wellness, it is mandatory to improve the robustness of such systems in order to ensure the availability of essential services such as the distribution of water, gas and electrical power. Nowadays, due to the increasing number of cyber incidents, the definition of protection strategies, able to improve the survivability level of this infrastructure, is at the heart of the scientific debate. In this chapter we propose a procedure based on three steps aimed at improving infrastructure survivability. In the first stage we propose some approaches to identify the criticality degree of each subsystem composing the infrastructure, in the second stage we propose a method to aggregate multiple criticality evaluations performed by subject matter experts by providing a unique holistic indicator. Finally, on the basis of such indicator, we propose a protection strategy to improve the robustness of the entire system.

1. Introduction

The physical and cyber protection of critical infrastructures (CIs) is crucial to ensure the availability of multiple essential services. Concerning the physical security aspects, critical infrastructures are, in most cases, complex and geographically distributed systems hence hard to protect. Regardless of the specific scenario, a CI can be represented as a set of sub-systems able to interact and cooperate in order to provide services that are essential for the economy, society and public wellness. For example, in gas distribution systems, the cooperation of metering and regulation stations is fundamental to guarantee the proper functioning of the entire infrastructure. In power grids and water distribution infrastructures, the availability of electrical power and water, depends respectively on the joint action of singular sub-systems such as bus or water supply stations. Analogously, the correct operation of a plant depends on the right operativeness of several elements as illustrated by the 4STER European project.

Critical infrastructure are characterized by a high level of interconnection and interdependency where the operation of a subsystem is essential for the functioning of others. In such a context, the disruption of a subsystem can easily escalate creating waterfall effect impacting multiple services and geographic areas. Therefore, in order to guarantee the functioning of the entire infrastructure it is necessary to protect adequately each sub-system from fault or exogenous events potentially capable of compromising normal operativity levels. As reported in [1], on the 28th September 2003, in Italy and some areas of Switzerland, about 56 million people lost power due to a storm-tossed tree branch that hit Swiss power lines. About 30,000 people remained trapped in trains, several hundred passengers were stranded on underground transit systems, and there were significant knock-on effects across other critical infrastructures. Similarly, the 2005 Hurricane Katrina [2] caused widespread power outages throughout Louisiana, Mississippi, Alabama, Florida, Kentucky and Tennessee due to the cascading effects initiated by a local event. Another example is the 2011 Great East Japan earthquake [3] and the resulting tsunami: 1.5 million households did not have access to their water supply, 4.4 million households were left without electricity, and all the local railway services were halted, and communications were suspended.

Domino effects over the entire infrastructure due to local fault are not caused only by accidental faults or natural disasters, but could also be intentionally caused by malicious actors. For example, with the increasing reliance of CI on Information & Communication Technology (ICT) malicious actors can perform attacks via cyberspace triggering service disruptions significant economic losses and even kinetic effects. This has been particular concerning in relation to the energetic sector with a significant increase of cyber threats capable of causing outages and blackout in power systems.

The first example of how a cyber attack can affect the operativity of CI causing mechanical damage was provided by the Aurora project [4]. This was a test performed by the Idaho National in which the simulation of a cyberattack led to the destruction of a 27-ton generator. Another Significant example is represented by the Stuxnet worm. The worm was able to modify the rotation speed of particular motors installed inside the centrifuges used for the uranium enrichment in plant in Iran. Similarly, recent blackouts in Ukraine in 2015 and 2016 were respectively caused by Blackenergy3 and CrashOverride, two malware specially designed to cause blackouts via cyber intrusion [5].

In addition, we have to consider impacts on workers’ safety. Power plants, water plants, gas plants can provoke accidents and enormous damages. Seveso plants can be used for the storage of hazardous materials: an attack aimed at these plants can also cause a domino effect. The capability to adjust machine parameters in order to improve performance or simply in order to change behavior can make other people with criminal intent adjust parameters so that workers and others can be put at risk of harm. Example of parameters can be speeds, forces, torques that can be put at dangerous levels. In addition, graphical interfaces used for human-machine interaction can be altered so that people could see a situation not corresponding to reality (not reported error codes or messages, different values of parameters or measures). In order to identify hazards associated to the use of a machine or a set of machines, procedures like HAZOP, HAZID, accident reviews must be taken into consideration. Anyway, security and safety must be considered as part of the normal working processes and not always this happens.

The main common aspect about these cited events is that a local event is able to compromise the functionality of the entire plants due to a domino effect. The identification of the most critical sub-systems is a crucial point for the definition of effective protection strategies able to improve the survivability of the systems. To this end, it is fundamental to identify adequate metrics and indicators to quantify the criticality rate associated to each sub-system, especially in highly heterogeneous contexts.

1.1 Related works

From the literature, one of the typical strategies to obtain such metrics is to simulate the effects of negative events, such as local faults, in order to provide insights on the most critical elements, for which protection needs to be raised. In particular, a well-established approach is to focus on intentional attacks, considering a rational attacker that aims at maximizing the damage while keeping low the effort required for his/her malicious action. Starting from the seminal works of Arulsevan et al. [6] it has become paramount that attacks that take into account the topology of the infrastructure, can select more effectively the target sites, increasing the damage dealt (e.g., in terms of disconnection of large portions of the infrastructure by causing services interruption). In [7, 8, 9, 10] multiple approaches for the identification of critical nodes in infrastructure networks are presented. All these methods consists in optimization problems able to discover the nodes whose removal from the network compromise the connectivity of the entire system. All these approaches requires initial assumptions about the attacker budget and preferences despite this information are not available in general in a real context. Moreover, the results of these approaches are able to highlight the most critical node in a network but not provide a metric capable of quantifying the degree of criticality for each node of the infrastructure. In more details, the approach presented in [7] proposes a method, able to identify the most critical nodes, based on the result of an optimization problem characterized by the presence of assumptions about the strategy of an attacker in terms of available budget and dimension of disconnected components. Similar assumptions are considered also in the approach presented in [8, 9], the authors propose a method which aims at minimizing the attack cost against the infrastructure with constraints about the features of the network. Finally, assumptions about the attacker preferences are also required in the formulation presented in [10]. In general, centrality measures, such as the node degree or betweenness centrality are often adopted as criticality measures, while in [11] the authors propose a critical index for the elements of a CI by analyzing the solutions of a multi objective optimization problem without any assumption about the attacker behaviour. However, the adoption of a unique metric or indicator about the criticality rate of each node of the system is quite unrealistic due to the complex nature of the infrastructures. Two approaches able to consider multiple metrics with the aim to compute a final aggregated criticality holistic indicator are presented in [12, 13]. The proposed approaches take into account multiple indicators based on multiple data source (topology data, field-related data, expert evaluations, etc.) but not provide a final step necessary to define a defensive strategy and evaluate its effectiveness.

1.2 Contribution and outline of the chapter

In this chapter we want to propose a procedure able to define a defensive strategy for CIs based on multiple node criticality measures. In more details, the procedure is based on three steps, as depicted in Figure 1: In the first stage (Section 2) we provide some specific criticality measure for CIs based on the connectivity of the system. The identification of the criticality measures is a fundamental stage in the defensive strategy definition process. In literature, graph centrality measures are often adopted as criticality measures for infrastructure but these approaches (e.g. Node degree or node betweenness) are quite ineffective as proved in [11]. In the second stage (Section 3) a methodology to merge multiple criticality metrics, based on the well-known Analytic Hierarchy Process [14], is described in order to overcome the limit about the application of a single metric in a complex environment. Moreover, such methodology allows considering also the criticality evaluations given for a subset of infrastructure nodes. The definition of the defensive strategy is provided in the last step (Section 4) and its effectiveness is proved by analyzing the global robustness of the network with respect to multiple robustness evaluation methods. Finally, in (Section 5), the application of the three-step procedure is illustrated with respect to the case study network with the aim of proving the effectiveness of the proposed strategy.

Figure 1.

Flow chart of the proposed three-steps procedure.

1.3 Notation

Let us denote by $\mid X\mid$ the cardinality of a set $X$; moreover, we represent vectors via boldface letters, and we use ${\mathbf{k}}_m$ to indicate a vector in ${\mathbb{R}}^m$ whose components are all equal to $k$, while by $I_n$ we identify the $n\times n$ identity matrix. Finally, we denote the sign of $x\in \mathbb{R}$ by $\mathit{sign}\left(x\right)$ and by $\mathit{sign}\left(X\right)$ the entry-wise sign of a matrix $X$. Let $G=\left\{V,E\right\}$ denote a graph with a finite number $n$ of nodes $v_i\in V$ and $e$ edges $\left(v_i,v_j\right)\in E\subseteq V\times V$, from node $v_i$ to node $v_j$. A graph is said to be undirected if $\left(v_i,v_j\right)\in E$ whenever $\left(v_j,v_i\right)\in E$ (see Figure 2). The adjacency matrix of a graph $G$ is an $n\times n$ matrix $A$ such that $A_{\mathit{ij}}=1$ if $\left(v_j,v_i\right)\in E$ and $A_{\mathit{ij}}=0$ otherwise. A path over an undirected graph $G=\left\{V,E\right\}$, starting at a node $v_i\in V$ and ending at a node $v_j\in V$, is a subset of links in $E$ that connects $v_i$ and $v_j$ without creating loops. An undirected graph $G=\left\{V,E\right\}$ is connected if each node can be reached by each other node by means of the links in $E$.

Figure 2.

Example of a graph $G=\left\{V,E\right\}$ with $\mid n\mid =5$ nodes and $\mid E\mid =6$ edges.

For the sake of clarity, we report here the notation adopted in the rest of the chapter.

$$\begin{array}{lll}{c}_i& & \text{Removal cost for node}{v}_i\\ \mathit{PWC}\left(G\right)& & \text{Pairwise connectivity of}G\\ \mathit{\text{NPWC}}\left(A,x\right)& & \text{Normalized pairwise connectivity for}\mathrm{a}\text{graph with}\\ & & \text{adjacency matrix}A\text{and without considering nodes}{v}_i\mathrm{s}.\mathrm{t}.{\mathbf{x}}_i=0\\ \mathcal{P}& & \text{Pareto Front}\\ {\chi }_i& & \text{Critical index for node}{v}_i\\ P& & \mathrm{Set}\text{of players in the cooperative game}\\ \mathrm{\Gamma }\left(P,g\right)& & \text{Cooperative game for players in}P\\ & & \text{evaluated}\mathrm{via}\text{characteristic function}g\\ {\varphi }_i& & \text{Shapley value for player}i\\ M_i& & i‐\mathrm{th}\text{metric}\\ m& & \text{Number of metrics}\\ r_a^{\left(i\right)}/r_b^{\left(i\right)}& & \text{Relative utility ratio among alternatives}i\text{and}j\text{according to metric}i\\ R_{\mathit{ab}}^i& & \text{Matrix of utility ratios among alternatives}a\text{and}b\text{according to metric}i\\ B& & \text{Defensive\hspace{0.17em}budget}\\ w_i& & \text{Relevance of metric}i\\ \prod & & \text{Global robustness index}\\ & & \end{array}$$

2. Node criticality metrics based on network connectivity

As mentioned above the first step of the proposed approach for the identification of a defensive strategy is the identification of metrics of interests able to evaluate the network criticalities from multiple points of view. Despite in literature this process is often reduced to a simple centrality measure computation, in this section we propose two other applicable approaches, based on the infrastructure connectivity, to compute the criticality of each sub-systems of a CI. For the sake of clarity, in this context we represent the entire infrastructure via undirected graph $G=\left\{V,E\right\}$ where $V$ is the set of $n$ nodes $v_i$, (each node represents a sub-system of the CI) and $E\subseteq V\times V$ is the set of $e$ undirected edges $\left(v_i,v_j\right)$. An edge connects two nodes if a real physical connection exists between the two corresponding sub-systems.

Both the approaches for the critical node identification, presented in this section are based on the concept of connectivity. In our models, when a node is attacked and is unable to operate, we remove the node and the incident edges from the graph. The deletion of particular critical nodes could compromise the connectivity of the other elements of the network. Notice that, for each node $v_i$ we consider a removal cost $c_i>0$. With the aim to measure the degree of connectivity of the graph $G$, we adopt the Pairwise Connectivity (PWC), it is an index that captures the overall degree of connectivity of a graph on the basis of the couples of nodes connected by means of edges in $G$.

$$\mathit{PWC}\left(G\right)=\sum _{\left(v_i,v_j\right)\in V\times V,v_i\ne v_j}p\left(v_i,v_j\right),$$E1

where $p\left(v_i,v_j\right)$ is 1 if the pair $\left(v_i,v_j\right)$ is connected via a path in $G$, and is zero otherwise. Noting that the maximum number of couples of nodes in a graph with $n$ nodes is $\frac{n\left(n-1\right)}{2}$, the normalized pairwise connectivity (NPWC) is defined as:

$$\mathit{\text{NPWC}}\left(G\right)=\frac{2\mathit{PWC}\left(G\right)}{n\left(n-1\right)}\in \left[0,1\right].$$E2

Remark 1$\mathit{\text{NPWC}}\left(G\right)$ is a measure of connectivity of the graph $G$, in fact, it is easy to note that

$$G\text{connected}\iff \mathit{\text{NPWC}}\left(G\right)=1.$$E3

When $\mathit{\text{NPWC}}\left(G\right)<1$, the graph is not connected, but the larger $\mathit{\text{NPWC}}\left(G\right)$ is, the more $G$ is “close” to be a connected graph. □

We now provide a more descriptive definition of a NPWC by taking into account a subset of attacked nodes. Let $A$ be the adjacency matrix of an undirected graph $G=\left\{V,E\right\}$ and let $\mathbf{x}\in {\mathbb{R}}^n$ be a column vector whose entries $x_i$ = 0 if the $i$-th node has been removed due to an attack or a fault and $x_i$ = 1 otherwise, we define the connectivity as:

$$\mathit{\text{NPWC}}\left(A,\mathbf{x}\right)=\frac{{\mathbf{1}}_n^T\left[\mathit{sign}\left({\sum }_{i=0}^{n-1}{\widehat{A}}^i\right)-I_n\right]{\mathbf{1}}_n}{n\left(n-1\right)}$$E4

where ${\widehat{A}}_{\mathit{ij}}=A_{\mathit{ij}}{x}_i{x}_j$, ${\mathbf{1}}_n$ is a column vector composed by $n$ entries equal to 1.

2.1 A critical index based on optimization problem

The definition of the Critical Index ${\chi }_i$ for a node $v_i$, come directly from the solutions of a multi-objective problem defined by assuming the point of view of a malicious attacker.

In Eq. (5) the behavior of an attacker is defined as a multi-objective optimization problem characterized by two conflicting objectives: the reduction of the connectivity in terms of NPWC and the simultaneous minimization of the required attack effort in terms of removal cost. We reiterate that if an attacker want to disconnect a node $v_i$ from the graph then (s)he must pay a cost $c_i$.

Problem 1

$$\begin{array}{lll}& minf\left(\mathbf{x}\right)=& min{\left[f_1\left(\mathbf{x}\right),f_2\left(x\right)\right]}^T,\\ & \mathbf{x}\in {\left\{0,1\right\}}^n& \end{array}$$E5

where x represents the vector of decision variables, whose entries $x_i$ are equal to 0 if the node $v_i$ is involved in the attack, 1 otherwise and where

$$f_1=\mathit{\text{NPWC}}\left(A,\mathbf{x}\right)$$E6

and

$$f_2=\frac{{\mathbf{c}}^T\left({\mathbf{1}}_n-\mathbf{x}\right)}{{\mathbf{1}}^T\mathbf{c}}$$E7

where $\mathbf{c}={\left[c_1\dots c_n\right]}^T$ is the vector whose entries represent the cost necessary to remove each node from the graph.

As described in [11], in general, a multi-objective problem is characterized by the presence of multiple optimal solutions ${\mathbf{x}}^{\left(j\right)}$ collected in the Pareto front set $\mathcal{P}$. Each solution is associated to a couple of values $\left[f_1\left({\mathbf{x}}^{\left(j\right)}\right),f_2\left({\mathbf{x}}^{\left(j\right)}\right)\right]$ according to the two objective functions. In other words, each optimal solution ${\mathbf{x}}^{\left(j\right)}$ represents a different attack strategy with damages caused on the network $f_1\left({\mathbf{x}}^{\left(j\right)}\right)$ and different attack effort $f_2\left({\mathbf{x}}^{\left(j\right)}\right)$ as depicted in Figure 3.

Figure 3.

Pareto front: the optimal solutions set for multi-objective optimization problem.

In [11], the Critical Index ${\chi }_i$ is defined as in Eq. (8):

$${\chi }_i=\frac{{\sum }_{\forall {\mathbf{x}}^{\left(j\right)}\in \mathcal{P}}{\mathbf{x}}_i^{\left(j\right)}}{\mid \mathcal{P}\mid }$$E8

where $\mid \mathcal{P}\mid$ represents the number of solutions in the Pareto front. In other words it is defined as the ratio between the frequency with which a node $v_i$ is involved in the attacks listed in the Pareto front and its cardinality. If the critical index ${\chi }_i$ is close to 0 this implies that the node is rarely involved in attack plans, instead, the closer it is to 1, more frequently the node is involved in optimal attack strategies.

2.2 A critical index based on a cooperative game

An alternative approach for the identification of the most critical nodes in a network is presented in [15]. Analogously to the critical index based on the results of the multi-objective optimization problem, the proposed method is based on the concept of NPWC. Differently from the previous critical index, this measure come from the game theory and is based on the solution of a cooperative game.

A cooperative game, sometimes called a value game or a profit game, is a competition among groups of players. Formally, a cooperative game is defined by a set of players $P$ and a characteristic function $v:2^N\Rightarrow {\mathbb{R}}^{+}$ which associate to all possible coalitions of players a utility rate. The function describes how much collective payoff a set of players can gain by forming a coalition.

Let $P$ be the set of players, and $g:2^P\Rightarrow {\mathbb{R}}^{+}$ a function that satisfies the following properties:

• $g\left(\varnothing \right)=0$

• Superadditive property: if $S,T\in 2^{P}s.t.S\cap T=\varnothing ,$ then $v\left(S\cup T\right)\ge g\left(S\right)+g\left(T\right)$

The cooperative game $\mathrm{\Gamma }\left(P,g\right)$ is defined by the couple $\left(P,g\right)$ where the elements of $P$ are the players of the game and the characteristic function of the game $g\left(S\right)$ estimates the utility of each coalition $S\in 2^P$.

Cooperative games can be solved via multiple approaches, the Shapley value [16] is one of the possible concepts of solution. The Shapley value assigns to each player $i\in P$, a reward ${\varphi }_i$. The larger is the contribution given by $i$ in all the possible coalitions of players, based on the function $g$, the larger is the reward ${\varphi }_i$ for the player $i$.

The Shapley value is a column vector $\mathrm{\Phi }$ whose entries are ${\varphi }_i$ are defined according to Eq. (9).

$${\varphi }_i=\frac{1}{n!}\sum _{S\subseteq P\left\{i\right\}}\mid S\mid !\left(n-|S|-1\right)!\left(g\left(S\cup \left\{i\right\}\right)-g\left(S\right)\right)$$E9

With the aim to adopt these concepts to provide a critical index able to quantify the criticality of each node of the network, a cooperative game $\mathrm{\Gamma }\left(N,\mathit{\text{nPWC}}\right)$ is defined. The set of players is represented by the set of nodes $N$ while the characteristic function $g$ is $\mathit{\text{NPWC}}$ (Eq. (3)). Notice that, in [15], it is demonstrated that the NPWC satisfy the two fundamental properties of a characteristic function.

The solution of the proposed game will assign a reward to each node in $V$ proportional to its contribution to the connectivity expressed in terms of $\mathit{\text{NPWC}}$, hence the Shapley value can be considered a valid node criticality metric.

3. A multi-criteria vulnerability detection index

As briefly introduced in Section 1, a research of the most critical nodes based on a single metric is practically worthless and extremely simplistic. In this section we propose an approach able to provide a holistic indicator able to take into account multiple criticality evaluations based on multiple metrics also in presence of incomplete data. The proposed method is based on the well-known Analytic Hierarchy Process (AHP) introduced by Saaty [17]. For a given set of $m$ alternatives, relative utility ratios $r_i/r_j$ are defined by experts. Such a setting is typical in contexts involving human decision-makers, which are usually more comfortable providing relative comparisons among the utilities of the different alternatives (e.g., “Alternative $i$ is twice better than alternative $j$”), rather than directly assessing an absolute utility value of each alternative (i.e, “The value of alternative $i$ is …”). The AHP is a procedure able to estimate the absolute utilities $r_i$ starting from the given utility ratios $r_i/r_j$. See [17] for additional notions about the AHP.

We now suppose to have $m$ different metrics $M_1\dots M_m$. According to these metrics, the entries of the column vectors ${\mathbf{r}}^{\left(1\right)}\dots {\mathbf{r}}^{\left(m\right)}$ represents the criticality rate of each node of the graph. Notice that the method is applicable also if for some metrics the criticality ratio of some node is not available [12]. Finally, let $w_1\dots w_m$ be positive weights defined by subject-matter experts (SMEs) representing the relevance of each metric. The larger is the weight associated to the $i$-th metric, the larger the influence of such metric in the final holistic indicator. Such weights can be obtained also resolving AHP on the basis of pair-wise comparisons between the different metrics.

For each metric we define the $n\times n$ matrix $R^{\left(i\right)}$ whose entries are defined as follows:

$$R_{\mathit{ab}}^{\left(i\right)}=\left\{\begin{array}{ll}{r}_a^{\left(i\right)}/r_b^{\left(i\right)}\text{if\hspace{0.17em}both}{r}_a^{\left(i\right)}\text{and}{r}_b^{\left(i\right)}\mathrm{are}\text{defined}& \\ 0\mathit{\text{otherwise}}& \end{array}\right.$$E10

In other words, the matrix $R^{\left(i\right)}$ collects the relative utility ratios between the $a$-th and $b$-th nodes according to the $i$-th metric if both the evaluation are available. Notice that some ratio $r_a^{\left(i\right)}/r_b^{\left(i\right)}$ might be undefined if $r_b^{\left(i\right)}=0$, due to this reason, we treat zero-valued entries as not available data.

By considering the matrices $R^{\left(i\right)}$, we aim at finding the aggregated holistic indicator ${\mathbf{r}}^{\ast }\in {\mathbb{R}}^n$ that solves the following problem.

Problem 2 Find ${\mathbf{r}}^{\ast }\in {\mathbb{R}}^n$that solves

$${\mathbf{r}}^{\ast }=\underset{\mathbf{r}\in {\mathbb{R}}_{+}^n}{argmin}f\left(\mathbf{r}\right)=\sum _{i=1}^m{w}_i\sum _{a=1}^n\sum _{b\mid R_{\mathit{ab}}^{\left(i\right)}\ne 0}{\left(ln\left(R_{\mathit{ab}}^{\left(i\right)}\right)-\mathit{log}\left(r_a\right)+\mathit{log}\left(r_b\right)\right)}^2$$E11

The holistic indicator ${\mathbf{r}}^{\ast }$ is a new node criticality measure that represents a compromise between the $m$ initial metrics $M_1\dots M_m$ by taking into account the SMEs preferences $w_i$. In other words, Problem 2 aims at finding the criticality indicator ${\mathbf{r}}_a^{\ast }$, assigned to the $a$-th node, such that the ratios ${\mathbf{r}}_a^{\ast }/{\mathbf{r}}_b^{\ast }$ minimize the deviation from the ratios $R^{\left(i\right)}$ for the $m$ considered metrics.

4. Defensive strategy definition and evaluation

In this section we propose a methodology to define a defensive strategy able to improve the survivability of the network with a focus on the connectivity maintenance with respect to nodes deletion. As introduced in Section 2, an attack cost $c_i$ is associated to each node $v_i$. Our aim is the definition of a new distribution of the budget in order to minimize the loss of connectivity in case of malicious attacks.

Let $B={\sum }_{i=1}^n{c}_i$ the defensive budget computed on the basis of the initial removal costs. We propose a new allocation of the budget by defining the removal cost proportionally to the holistic indicator ${\mathbf{r}}^{\ast }$ described in Section 3. Hence, we define the new removal costs ${\widehat{c}}_i$ as follows:

$${\widehat{c}}_i=\frac{1}{B}\frac{{{\mathbf{r}}^{\ast }}_i}{{{\mathbf{1}}_{\mathbf{n}}}^T{\mathbf{r}}^{\ast }}.$$E12

It is now necessary evaluate the robustness of a network with a particular defensive strategy. As introduced in Section 2.1, due to its multi-objective nature, Problem 1 is characterized by the presence of multiple optimal solutions collected in the Pareto front $\mathcal{P}$. Each optimal solution ${\mathbf{x}}^{\left(j\right)}$ is associated to a couple of values: a particular connectivity value $f_1\left({\mathbf{x}}^{\left(j\right)}\right)$ and an attack cost $f_2\left({\mathbf{x}}^{\left(j\right)}\right)$, where $f_1$ and $f_2$ represent the two objective function of Problem 1.

In [11], the global robustness index $\prod$ is defined as the area under the polygonal chain connecting the points ($f_1\left({\mathbf{x}}^{\left(j\right)}\right)$,$f_2\left({\mathbf{x}}^{\left(j\right)}\right)$) in the Pareto front using trapezoidal rule for numerical integration.

As depicted in Figure 3, $\prod$ is a measure of the overall robustness of the network. In fact, the larger is the area, the higher is the value of the objectives associated to the solutions in the Pareto front; hence, high values of the global robustness index correspond to networks where the attacker is not able to deal large damage, or deals large damage only for large effort.

5. Case study

In this section we prove the effectiveness of the proposed three-stage methodology able to improve the network survivability via critical nodes protection. The proposed strategy is tested on the CI represented by the network depicted in Figure 4. Notice that the case study is based on a network that does not represents a real infrastructure. The network is composed by $n=15$ nodes and $e=35$ edges. As discussed in Section 2, the first step of the methodology is devoted to the identification of criticality measures able to take into account the effects about the disconnection of a node from the graph by evaluating the loss of connectivity of the entire infrastructure. Notice that, the removal costs $c_i$ are set to 1 for each node of the infrastructure.

Figure 4.

Case study network. The node color depends on the holistic criticality rate computed via Eq. (7).

The first columns in Table 1 collect the metrics defined by Eqs. 5 and 6 respectively. Concerning the distribution of the critical indices ${\chi }_i$, the largest value are associated to the nodes 10 and 3. Notice that, the deletion of such nodes divides the nodes in two partitions, hence it strongly compromises the connectivity of the network in terms of nPWC.

Node	Critical Index ${\chi }_i$^a	Shapley Value ${\varphi }_i$^b	Degree	Betweenness	Holistic Indicator ${{\mathbf{r}}_{\mathbf{i}}}^{\ast }$^c
1	0.1111	0.0354	2	0	0.0360
2	0.1852	0.0493	4	0	0.0587
3	0.2863	0.0952	4	24	0.1003
4	0.2593	0.1465	3	45	0.1143
5	0.0370	0.0354	2	0	0.0238
6	0.1111	0.0493	4	0	0.0484
7	0.1111	0.0521	6	3.5	0.0491
8	0.2593	0.0547	7	2	0.0618
9	0.1481	0.0515	3	15	0.0580
10	0.2963	0.1635	5	48	0.1389
11	0.0741	0.0515	3	15	0.0465
12	0.1852	0.0521	6	3.5	0.0577
13	0.1852	0.0521	6	3.5	0.0577
14	0.2222	0.0567	8	19.5	0.0871
15	0.2593	0.0547	7	2	0.0618

Table 1.

Criticality evaluations based on four different metrics and computed holistic indicator.

^a

Criticality measure based on Eq. (5).

^b

Criticality measure based on Eq. (6).

^c

Holistic Indicator based on Eq. (7).

Similar results are obtained by considering the computation of the Shapley value in order to solve the cooperative game as described in Section 2.2. We remark that this approach assigns a reward to each node of the network according to their contribution to the connectivity of the entire network by considering all the possible partitions of nodes. Notice that, the results computed via Shapley not consider the removal cost $c_i$ while the results of Problem 1 take into account also this aspect, moreover, in this case study all the removal costs $c_i$ are set to 1.

Finally, the fourth and fifth columns of Table 1 collect the node degree and the betweenness centrality [18] for each node in the graph.

In the last column of Table 1, we show the criticality rate for each node according to the new holistic indicator computed as in Eq. (7) considering $m$=4 metrics (i.e. the critical index, the Shapley Value, the node Degree and the Betweenness centrality). According to the procedure defined in Section 3, we have set the metric relevance as follows: $w_1=0.3$, $w_2=0.3$, $w_3=0.2$, and $w_4=0.2$ in order to emphasize the criticality metrics based on the concept of PWC.

The nodes color in Figure 4 depends on the aggregated criticality values, according to the colormap. On the basis of this new indicator, the node 10 is the most critical node of the graph, in fact the deletion of this node strongly compromise the connectivity of the network and the creation of two disconnected partitions. Due to the same reason, a high criticality rate is also assigned to the nodes 4 and 3. Despite the node 14 is not essential for the connectivity, this node is characterized by a high node degree, in fact it is considered, according to the holistic indicator, as the fourth most critical node in the network.

Starting from the results obtained by computing the holistic indicator ${\mathbf{r}}^{\ast }$, we adopt a defensive strategy by defining a new attack cost ${\widehat{c}}_i$, for each node, proportional to its holistic criticality rate as defined in Eq. (8). Notice that the defensive budget $B={\sum }_{i=1}^n{c}_i=15$.

The effectiveness of the proposed defensive strategy is proved by considering the global robustness index $\prod$, we remark that it came from the solution of Problem 1 and it is defined as the area under the Pareto front. As depicted in Figure 5, the new allocation of the defensive budget $B$ is very effective to contrast an attacker especially with limited budget. In more details, in case of uniform defensive strategy (i.e. all the attack costs set to 1) the area under the Pareto front is equal to $\prod =0.1229$, while the new budget allocation (Eq. (8)) based on the holistic indicator ${\mathbf{r}}^{\ast }$ improves the network robustness by increasing the area to $\prod =0.1591$.

Figure 5.

Results of problem 1. Pareto fronts obtained by applying defensive strategies based on the holistic indicator (blue line), and uniform attack costs (red line).

6. Conclusions

In this chapter we provide a methodology for the definition of a defensive strategy via prioritizing the critical nodes of the network. Due to the complexity of a CI, the adoption of a unique metric for the identification of the node criticality is simplistic, to this end we propose a strategy, based on the AHP, able to merge multiple metrics which take into different aspects of the network. Moreover, the proposed aggregation procedure is applicable also in case of incomplete data. Among the multiple metrics applicable in the merging process, in this chapter we propose two metrics characterized by a focus on the network connectivity. In the one hand the critical index is computed on the basis of a multi objective optimization problem. Assuming an attacker perspective and knowing the topology of the network, the problems aims at identifying the nodes whose removal compromise the connectivity of the entire system. On the other hand, we propose the adoption of the Shapley value as a criticality evaluation by defining a cooperative game among the nodes of the network. Finally, we propose the definition of a defensive strategy that assigns to each node a removal cost proportional to the holistic indicator. Future improvement will be devoted to the inclusion of a final check able to include a final validation based on expert opinions. One of the possible validity check is based on the well-known face validity approach [19], it refers to the transparency or relevance of a test as it appears to test participants.

Acknowledgments

This work was supported by INAIL via the European Saf€ra project “Integrated Management of Safety and Security Synergies in Seveso Plants” (Saf€ra 4STER).