Cristina Alcaraz

Stephen Wolthusen

RECOVERY OF STRUCTURAL CONTROLLABILITY FOR CONTROL SYSTEMS

Keywords: Control systems, structural controllability, power domination, resilience

Fundamental problems in control systems theory are controllability and observability, and designing control systems so that these properties are satisfied or approximated sufficiently. However, it is prudent to assume that an attacker will not only be able to subvert measurements but also control the system. Moreover, an advanced adversary with an understanding of the control system may seek to take over control of the entire system or parts thereof, or deny the legitimate operator this capability. The effectiveness of such attacks has been demonstrated in previous work. Indeed, these attacks cannot be ruled out given the likely existence of unknown vulnerabilities, increasing connectivity of nominally air-gapped systems and supply chain issues. The ability to rapidly recover control after an attack has been initiated and to detect an adversary's presence is, therefore, critical. This paper focuses on the problem of structural controllability, which has recently attracted substantial attention through the equivalent problem of the power dominating set introduced in the context of electrical power network control. However, these problems are known to be N P-hard with poor approximability. Given their relevance to many networks, especially power networks, this paper studies strategies for the efficient restoration of controllability following attacks and attacker-defender interactions in power-law networks.

Introduction

Domination, a central topic in graph theory, is a relevant theme in the design and analysis of control systems because it is an equivalent problem to that of (Kalman) controllability. The motivation comes from the concept of structural controllability introduced by Lin [START_REF] Lin | Structual controllability[END_REF], which is based on control theory as defined by Kalman [START_REF] Kalman | Mathematical description of linear dynamical systems[END_REF]: ẋ(t) = Ax(t) + Bu(t), x(t 0 ) = x 0 .

(1)

In this formulation, x(t) is a vector (x 1 (t), . . . , x n (t)) T representing the current state of a system with n nodes at time t; A is an n × n adjacency matrix specifying the network topology that identifies interaction between nodes; and B is an n × m input matrix, where m ≤ n, identifies the set of nodes controlled by a time-dependent input vector u(t) = (u 1 (t), . . . , u m (t)) that forces the system to a desired state in a finite number of steps. According to Kalman's rank criterion, the system in Equation ( 1) is controllable if and only if: rank[B, AB, A 2 B, . . . , A n-1 B] = n.

(2)

However, this formulation is quite restrictive for large networks (e.g., power networks or similarly large control systems) where there exists an exponential growth of input values as a function of nodes. This is the main reason that our investigations concentrate on structural controllability, where matrix A in Equation ( 1) represents the network topology and matrix B contains the set of nodes with the capacity to drive control [START_REF] Mayeda | On structural controllability theorem[END_REF].

Lin [START_REF] Lin | Structual controllability[END_REF] defines G(A, B) = (V, E) as a digraph where V = V A ∪ V B is the set of vertices and E = E A ∪ E B is the set of edges. In this representation, V B comprises the nodes capable of injecting control signals into the entire network, also known as driver nodes (denoted as n d ) corresponding to input vector u in Equation [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF]. The identification of these nodes has so far been studied in relation to general networks. This paper concentrates on power-law networks, most pertinent to a number of large-scale infrastructure networks. To identify the minimum driver node subsets N D , we follow the approach based on the power dominating set (PDS) problem, which is described in more detail in [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF][START_REF] Alcaraz | Multi-round attacks on structural controllability properties for non-complete random graphs[END_REF]. This interest is primarily because PDS-based networks have similar logical structures as real-world monitoring systems, where driver nodes can represent, for example, remote terminal units that control industrial sensors and actuators. In fact, the PDS problem was originally introduced as an extension of the dominating set (DS) by Haynes, et al. [START_REF] Haynes | Domination in graphs applied to electric power networks[END_REF], mainly motivated by the structure of electric power networks and the need to efficiently monitor the networks.

Building on previous work [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF][START_REF] Alcaraz | Multi-round attacks on structural controllability properties for non-complete random graphs[END_REF], this paper proposes several restoration strategies for controlling a network after N D has been perturbed. Different attack patterns that compromise nodes and the effects of the attacks have been considered extensively in [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF][START_REF] Alcaraz | Multi-round attacks on structural controllability properties for non-complete random graphs[END_REF], in particular, the analysis and evaluation of interactive and non-interactive attacks, including multiple rounds between attackers and defenders, respectively. However, it is clearly undesirable to restore overall controllability through complete re-computation if the PDS properties are only partially violated -where this is possible given the constraints imposed by compromised nodes -because the PDS problem is known to be N P-complete for general graphs as well as for bipartite and chordal graphs as shown by Haynes, et al. [START_REF] Haynes | Domination in graphs applied to electric power networks[END_REF].

Subsequent research by Guo, et al. [START_REF] Guo | Improved algorithms and complexity results for power domination in graphs[END_REF] extended N P-completeness proofs to planar, circle and split graphs, with the exception of partial k-tree graphs with k ≥ 1 and parameterized using N D , in which the DS and PDS problems can become tractable in linear-time, while the parameterized intractability can result in W [2]-hardness [START_REF] Downey | Parameterized Complexity[END_REF]. Pai, et al. [START_REF] Pai | Restricted power domination and faulttolerant power domination on grids[END_REF] have provided results for grid graphs while Atkins, et al. [START_REF] Atkins | Placing monitoring devices in electric power networks modeled by block graphs[END_REF] have studied block graphs. There are other approaches that address PDS for specific cases [START_REF] Brueni | The PMU placement problem[END_REF][START_REF] Dorfling | A note on power domination in grid graphs[END_REF], but none of them focus on efficient solutions for the restoration of the PDS problem following perturbations, i.e., where a PDS of the original graph G is known along with the changes induced on G.

The restoration strategies defined in this paper center on general power-law and scale-free distributions by offering similar characteristics to real power networks. In particular, three strategies are defined to determine the complexity of restoration. To evaluate the complexity, this paper considers: (i) a strategy without any type of constraint for restoration; (ii) a strategy based on the graph diameter to minimize the intrinsic problem of the non-locality of PDS; and (iii) a strategy based on backup instances of driver nodes. The paper shows that this offers a gain in efficiency over re-computation while resulting in acceptable deviations from an optimal (i.e., minimal |N D |) PDS. Because many critical infrastructures require timely or even real-time bounded restoration to ensure resilience and continued operation, the ability to restore controllability rapidly is essential and, of course, highly desirable.

Conditions for the Analysis

This section discusses the initial assumptions and conditions used to restore the structural controllability when nodes are attacked from within a network. Let G(V, E) be a directed acyclic graph (DAG) based on an arbitrary set of nodes V and a set of edges E, where each vertex v i ∈ V can be linked to other v j ∈ V such that (v i , v j ) ∈ E, without producing loops or self-loops (i.e., v i ̸ = v j ).

Assumptions for Perturbation

The first assumption we consider here is that one or several vertices can be targeted by one or several attackers, knowing the structure or probability distribution of edges of the graph, its topology, and the identities of the current driver nodes N D (note that N D is not necessarily unique). These driver nodes that also belong to V satisfy the two observation rules for controllability, which were simplified by Kneis, et al. [START_REF] Kneis | Parameterized power domination complexity[END_REF] from the original formulation specified by Haynes, et al. [START_REF] Haynes | Domination in graphs applied to electric power networks[END_REF]. The two rules and their algorithms are detailed in [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF][START_REF] Alcaraz | Multi-round attacks on structural controllability properties for non-complete random graphs[END_REF] and below: OR1: A vertex in N D observes itself and all its neighbors. OR2: If an observed vertex v of degree d ≥ 2 is adjacent to d-1 observed vertices, the remaining unobserved vertex becomes observed as well.

Note that the omission of OR2 already results in the N P-complete DS problem with a polynomial-time approximation factor of Θ(log n) [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF]. The following condition is that the construction of N D is arbitrary and depends on the selection of vertices satisfying OR1, allowing the customizable selection of controllability generation strategies as specified in [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF]. After N D has been obtained, we evaluate two different scenarios concentrating on attacks against either node or edge (communications link) availability [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF][START_REF] Alcaraz | Multi-round attacks on structural controllability properties for non-complete random graphs[END_REF]: SCN-1: Randomly remove some (not all) edges of one or several vertices, which may compromise the controllability of dependent nodes or disconnect parts of the control graph and underlying network. SCN-2: Randomly isolate one or several vertices from the network by intentionally deleting all their links (i.e., this attack may result in the complete isolation of nodes from the network).

As detailed in [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF][START_REF] Alcaraz | Multi-round attacks on structural controllability properties for non-complete random graphs[END_REF], either attack scenario may result in a degradation of the control of a network and a significant reduction in observability (including partial observability). To address this aspect, we identify two classes of nodes:

U-1: The node u is not observed by an n d , but belongs to N D and is part of the control node set.

U-2:

The node u is not observed by an n d and does not belong to N D . This means that u is part of the set of observed nodes, denoted as O,

such that O = V -N D .
When such a node is not being observed by a member of N D , the set of unobserved nodes U has to be updated so that each node u ∈ U can be again observed by at least one member of N D .

Assumptions for Restoration

We assume that the restoration of structural controllability N D is initially based on searching driver nodes in N D that offer the coverage of unobserved nodes in U with dependence on attacked nodes in A. The term coverage refers to the ability of a new link to be established between the best candidate in N D and an unobserved node in U such that the two observation rules OR1 and OR2 specified above are satisfied. For this, the candidates for restoring the controllability must have the following properties: Satisfy the conditions of OR1, i.e., select an n d ∈ N D capable of observing itself and an unobserved u

∈ U through a new link (n d , u) ∈ E such that | N D | ≥ 1.
None of the new restoration links must violate the out-degree distribution of a power-law network and must not introduce cycles.

Satisfy the conditions of OR2, i.e., verify that ∀ n d ∈ N D of degree d ≥ 2, OR2 is not infringed. This can involve the inclusion of one or several new members in

N D such that | N D | ≤ | V |.
At the end of the algorithm, the restored set N D can increase the initial number of driver nodes such that U = ⊘ (note that | N D |=| V | in degenerate cases). However, and unfortunately, we must also consider the handicap of non-locality of PDS and the N P-complete property demonstrated by Haynes, et al. [START_REF] Haynes | Domination in graphs applied to electric power networks[END_REF].

Our heuristic approach is based on ensuring that the hard constraints, i.e., observation rules, are satisfied primarily and that, as a secondary constraint, the out-degree distribution property of the underlying power-law network remains unaltered. This strategy also depends on the approaches taken for each restoration strategy defined in the remainder of the paper. In this case, the study is based on two main approaches:

APPR-1: Find an n d ∈ N D to re-link it to an unobserved node u ∈ U .
APPR-2: Find an n d bl belonging to a backup list of driver nodes such that there is an edge between n d bl and unobserved node u ∈ U .

Likewise, each restoration strategy has to consider some of the following "restoration rules" (heuristics):

RR1: If u is a U-1,
then it is necessary to ensure that u still satisfies OR1.

RR2: If u is a U-2, and the restoration strategy follows the APPR-1 approach, it is necessary to first find the driver node n d ∈ N D with out-degree equal to zero, or find a vertex

n d ∈ N D of out-degree d ≥ 2 such that |children(n d ) -N D | ≥ 1 where children(n d
) is a function that obtains the set of child nodes corresponding to the out-degree of n d . In this way, the violation of OR2 after the link is avoided.

RR3: If u is a U-2 and the restoration strategy follows the APPR-2 approach, it is necessary to first find the driver node n d bl of a given backup list with out-degree equal to one (pointing out to itself), or find an n d bl in the backup list of out-degree d ≥ 2 such that |children(n d bl ) -N D | > 1 to avoid violating OR2.

Restoration of Structural Controllability

The three restoration rules given in Section 2.1 are the basic constraints to address the following three restoration strategies:

Algorithm 1 : Basic Re-Link(G(V, E), ND, U, A). output ND local S1, u, n d , or2; or2 ← false; while U ̸ = ⊘ do (⋆) Randomly choose a vertex u ∈ U ; if u / ∈ ND then (⋆) (S1 ← ∀ n d ∈ ND -A with maximum in degree) and ((n d , u) ∈ E is DAG); (⋆) Common Relink(G(V, E), ND, S1, u, U, A, or2); end if U ← U \ {u}; end while return (⋆) verif yOR2(G(V, E), ND, A, or2); STG-1: No constraints through APPR-1.
STG-2: Parameterization using the network diameter and APPR-1.

STG-3:

A backup list of driver nodes through APPR-2.

This section develops and analyzes the three associated algorithms, considering in addition the parameters and functions described above.

STG-1: Restoration Algorithm and Analysis

For any attack scenario (SCN-1 and SCN-2), the approach involves finding the candidates in N D that can provide coverage to each vertex contained in U through a new edge. This approach is specified by Algorithm 1, where the symbol (⋆) is an indication for the complexity analysis given in Section 4.

We briefly outline the semantics of Algorithm 1. For each unobserved node, the first step is to verify that it is part of N D . If a vertex u ∈ U is an n d by itself (U-1), then it is not necessary to find a member of N D to establish the link because such a node observes itself, satisfying the first restoration condition (RR1) given in Section 2.2. Otherwise, a non-attacked n d is randomly chosen to proceed with link restoration. However, because this new link (generated by Algorithm 2) can change the power-law distribution given in G(V, E), only the candidates with the highest in-degree (≥ 0) are chosen so as not to skew the degree distribution, effectively obtaining a preferential attachment process [START_REF] Barabasi | Scale-free characteristics of random networks: The topology of the world-wide web[END_REF]. From these candidates, those that do not produce cycles after the attachment are selected in order to comply with the second assumption given in Section 2.2.

Regardless of the type of restoration strategy (STG-1, STG-2, STG-3) and the state of U , the verification of the existence of nodes in G(V, E) that violate OR2 after a perturbation is always required. To be more concise, the analysis is reduced to a subset of nodes instead of the entire graph; this subset contains the nodes related to the set of A. Moreover, depending on the target (TG) that is attacked, the analysis can vary:

Algorithm 2 : Common Re-Link(G(V, E), ND, S1, u, U, A, or2). output G(V, E), ND, or2 local S2, n d ; if S1 ̸ = ⊘ then (⋆) S2 ← ∀ n d ∈ S1/ (out degree == 0) or (| children(n d ) -ND | ≥ 1); if S2 ̸ = ⊘ then Randomly choose a n d ∈ S2; else (⋆) Randomly choose a n d ∈ S1; (⋆) ND ← ND ∪ {n d }; (⋆) or2 ← true; end if Establish a link between n d and u, such that (n d , u) ∈ E; else ND ← ND ∪ {u}; or2 ← true; end if
TG-1: An n d has been attacked, so OR2 is performed for each n d in A. However, the verification process is only effective for scenarios SCN-1 in which the state of each child of an affected node has to be evaluated. This process is disrupted when there is an

n d ∈ A of degree ≥ 2 with | children(n d ) -N D |= 1.

TG-2:

A node v ∈ O has been attacked, so OR2 is applied for each v ∈ A. However, the analysis is only effective for scenarios SCN-1 where the algorithm is applied to the father nodes n d fv related to v and n d fv ∈ N D . Because of TG-1, the proof may be interrupted when there is an n d fv of degree ≥ 2 with | children(n d fv ) -N D |= 1. The set of driver fathers is obtained through the function fathers(v) corresponding to the in-degree of v.

As stated in Algorithm 3, the breach of OR2 involves an update of N D and the execution of Algorithm OR2, which is detailed in [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF]. On the other hand, the correctness proof of STG-1 involves induction:

Precondition: A ̸ = ⊘ such that | N D -A | ≥ 1.
Postcondition: U = ⊘, and OR1 and OR2 are fulfilled.

Case 1: U = ⊘ after perturbation (SCN-1 or SCN-2). Although the while loop in Algorithm 1 is not processed, Algorithm 3 must be executed to verify the fulfillment of OR2. Depending on the attack scenario, the resolution of Algorithm 3 changes. For scenarios SCN-1, the loops for the sets attacked N D and attacked O must be launched to detect the existence of one driver node (∈ attacked N D ) or parent drivers (∈ attacked O) that violate the second controllability rule. In contrast, such sets are not considered for SCN-2 scenarios because the affected nodes are completely isolated, without children and parent vertices, satisfying OR2 through out degree = 0. Case 2: U ̸ = ⊘ after perturbation, being | U |= 1. In these circumstances, two cases must be distinguished:

Algorithm 3 : Common VerifyOR2(G(V, E), ND, A, or2
(i) If u is U-1, the condition RR is met. (ii) If u is U-2,
it is necessary to explore the existence of one or several candidates {n d1 , . . . , n dn } with maximum in-degree (≥ 0) and with the capability to cover u without producing cycles and complying with RR2. If this is the case, we ensure that ∃ an n d ∈ N D for coverage, and u therefore becomes part of O, guaranteeing that U is null for next iteration. If not, N D is updated with N D ∪ {u} to be observed at least by itself, where U = ⊘ in the next iteration. However, this updating involves performing a verification process of OR2 [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF] to determine the observation degree of the entire network after the loop of Algorithm 1.

Induction: Assuming that we are in step k

(k > 1) with U ̸ = ⊘, k =| U | and | N D |≥ 1,
we randomly select a node u ∈ U in each iteration of the while loop. When selecting a node, two cases can arise depending on u (U-1 or U-2), which pursue the same goals as Case 2 (but with | U |> 1). At the end of Algorithm 1, the set U and k are always updated through U = U \ {u} (see Case 2). In the next state, with k -1, the procedure adopted is still valid, which means that the postcondition U = ⊘ is not met and the loop must be run again for the next state k until k = 0.

Algorithm 4 : Diameter-Based Relinking(G(V, E), ND, U, A).

output ND local S d 1 , S d 2 , S1, u, n d , or2; or2 ← false; while U ̸ = ⊘ do (⋆) Randomly choose a vertex u ∈ U ; if u / ∈ ND then (⋆) S d 1 ← BF S(G(V, E)); (⋆) S d 2 ← ∀ n d ∈ ND -A with minimum diameter ∈ S d 1 and (n d , u) ∈ E is DAG; if S d 2 ̸ = ⊘ then (⋆) S1 ← ∀ n d ∈ S d 2 with maximum in degree(n d ); (⋆) Common Relink(G(V, E), ND, S1, u, U, A, or2); else ND ← ND ∪ {u}; or2 ← true; end if end if U ← U \ {u}; end while return (⋆) verif yOR2(G(V, E), ND, A, or2);
When k = 0, Case 1 occurs, and therefore the postcondition is true and Algorithm 1 terminates.

STG-2: Restoration Algorithm and Analysis

One extension of STG-1 is to consider the network diameter as described in Algorithm 4. By induction, the proof of STG-1 can be expanded by taking into account the initial and final conditions and base cases. For each iteration k (k > 1) with U ̸ = ⊘ and | N D |≥ 1, a node u ∈ U is selected randomly. As in the previous proof, we distinguish two types of affected nodes. If the node is U-1, then RR1 is still satisfied. However, if the node is U-2, then ∀ n d ∈ N D -A nodes with the minimum diameter are selected to ensure acyclic graphs after repair. Because the graph is unweighted, breadth-first search is used to obtain a list of nodes together with their diameters, and through this list the n d with minimum diameter (≥ 0) with respect to the entire graph are obtained.

In the case where there does not exist a candidate node that satisfies all the constraints, the unobserved node becomes part of the N D to guarantee at least OR1; otherwise, the inductive proof of STG-1 can be employed. At the end of the loop, the precondition | U |= k is updated in each stage k by computing U = U \ {u} until k = 0. As a result of the proof of STG-1, the postcondition is true and Algorithm 4 terminates when Case 1 as defined in STG-1 is finally reached.

STG-3: Restoration Algorithm and Analysis

This strategy requires initial pre-processing before the generation of backup instances composed of driver nodes in G(V, E). These instances have to be organized into a tree-like structure based on the concept of "nice tree decomposition." To do this, a previous construction of a tree decomposition must be built, taking into account the network diameter for later transformation into a nice tree decomposition. A tree decomposition is a tree T of G(V, E) with I nodes, where each node in T is a bag containing a set of n d ⊆ N D satisfying the following properties [START_REF] Guo | Improved algorithms and complexity results for power domination in graphs[END_REF]:

Property 1: i∈T bag i = N D . Property 2: ∀ (n d blw , n d blz ) ∈ E with diameter ≥ 0, there exists a bag i in T such that (n d blw , n d blz ) ⊆ bag i . Property 3: ∀ bag i , bag j , bag z ∈ T , if bag j is on the path from bag i to bag z in T , then bag i ∩ bag z ⊆ bag j .
The tree width corresponds to the minimum width w over all tree decompositions of G(V, E), where w = max i∈I (| bag i |∈ T ) -1 and w ≥ 1. This means that a tree decomposition T of width w with | N D | driver nodes can be turned into a nice tree decomposition of width w, but subject to the diameter associated with each driver node within the network [START_REF] Dourisboure | Tree-decompositions with bags of small diameter[END_REF]. In this way, bags containing driver nodes with smaller diameters are the leaves of T while driver nodes with higher diameters are located closer to the root.

For transformation to a nice tree decomposition, each node i in the tree T has at most two children (j, z) complying with two additional conditions: (i) nodes with two children bag j and bag z , bag i = bag j = bag z (bag i as a join node); and (ii) nodes with a single child bag j such that bag i = bag j ∪ {n d } (bag i as an introduce node) or bag i = bag j -{n d } (bag i as a forget node). In practice, these trees are constructed using tables with at least three columns (i, j, z), where each entry i contains those subsets of n d in relation to i. However, this data structure also takes into account the maximum diameter associated with each bag because the approach does not focus on re-linking (APPR-1), the value of which remains constant throughout the restoration process. Therefore, the spatial overhead for such a table may become 3 × 2 w+1 = O(2 w+1 ) entries [START_REF] Guo | Exact algorithms and applications for treelike weighted set cover[END_REF].

Algorithm 5 describes the behavior of the restoration strategy with one or several nice tree decompositions T bk as the main input parameter with a stor-

age cost of O( M bk=1 2 w+1
). The idea is to process this parameter in a bottom-up fashion to find the driver nodes with minimum diameter that ensure the fulfillment of RR3 specified in Section 2.2. The inductive proof begins by defining the initial and final conditions, and the base cases:

Precondition: A ̸ = ⊘ with at least one T bkj with M ≥ j ≥ 1.
Postcondition: U = ⊘, and OR1 and OR2 are fulfilled.

at least one member in N D and the set O is updated, guaranteeing that U is empty in the next iteration. In contrast, if there is no perfect candidate (as above) in N D and S2 ̸ = ⊘, we also guarantee the existence of an n d bl ∈ T bkj with the ability to cover u, and hence O = O ∪ {u} and U = ⊘ for the next iteration. However, N D must be updated with N D ∪ {n d bl }, requiring Algorithm 5 to verify the observation degree of the entire network when the loop finishes. This verification process, described in detail in Section 3.1, may also be performed when there is no perfect candidate (S 1 = ⊘ and S 2 = ⊘) to cover u. In this case, u becomes part of N D to comply with OR1, and hence U = ⊘ in the next iteration. When U = ⊘ and the rule OR2 is satisfied, the postcondition is true.

Induction: In step k (k > 1) with U ̸ = ⊘, k =| U | and | N D |≥ 1,
we randomly select a node u ∈ U in each iteration of the loop. When selecting a node, two situations can occur depending on u: U-1 or U-2, and both following the same goals set out for Case 2 (of this proof), but with | U |> 1. At the end of the algorithm, the set U and k are always updated through U = U \ {u}. In the next state, with k -1, the procedure adopted is still valid, which means that the postcondition U = ⊘ is not met and the loop must be run up again for the next state k until k = 0. When this happens, Case 1 of the STG-1 proof must be verified to conclude that the postcondition is true, and therefore Algorithm 4 terminates.

Complexity Analysis and Discussion

This section analyzes the computational complexity of the three restoration algorithms, Algorithm 1, Algorithm 4 and Algorithm 5. In the case of STG-1, it is required to process the entire U set k times where k =| U |. For these k iterations, the algorithm must also find the best candidates in N D -A with the highest in-degree to ensure the fulfillment of RR2 in the best scenario, or increase N D , at least, by one unit in the worst case.

For simplicity, we denote

| V |= n, | E |= e, | A |= a (= 1), | N D |= nd and f = f athers(n d )
; and we study the upper bounds for SCN-1 and SCN-2. To evaluate the worst scenario of each SCN-x (x = {1, 2}), we assume that nd ≈ n and the adversarial scenario is non-interactive (a single target TG-x (x = {1, 2})), so that if A ⊆ N D , then nda ≈ n as well. In addition, we must also select the longest trace of Algorithm 1 that includes Algorithm 3, following the indication given by ⋆ -note that both the assignment and if instructions have constant complexity O(i) and can be neglected. To address this aspect, we first evaluate the upper bound needed to find the non-attacked driver nodes (N D -A) with maximum in-degree (≥ 0) that satisfy the directed acyclic test after repair and RR2. The computation time of this entire process may become O(kn 2 ) if nd ≈ n.

Depending on SCN-x and the targeted node TG-x, the computational complexity of Algorithm 3 can become variable as described in Section 3.1: TG-1 in SCN-1: In this case, it is necessary to verify OR2 for each attacked driver node in attacked N D with a cost of O(a + e). As we are evaluating the worst scenario, we must observe that after computing all the nodes in attacked N D , there exists an n d that infringes OR2, which forces Algorithm 3 to compute Algorithm OR2 given in [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF] with an overhead of O(nd(nd + e)) = O(n 2 ). Therefore, the total complexity for this scenario is O(kn 2 + ((a + e) + n 2 )) = O(kn 2 ). ) if nd ≈ n. The rest of the analysis follows the same steps as for SCN-x and TG-x stated above, with the results summarized in Table 1.

With regard to strategy STG-3, we simplify the study considering b = w + 1 (largest bag in T bkj ) and the worst case with n d ≈ n. To compute a bag bag i of T bkj with j ≤ M , Algorithm 5 must identify the existence of an n d bl that complies with RR3, which yields a cost of O(b + e). To obtain the best candidates of each backup instance T bkj stored in memory, the algorithm needs to process each tree with a computational cost of O( M bk=1 2 w+1 (b + e)). The second part of the approach follows the same approach described above for Algorithm 3, which is summarized below and in Table 1: Therefore, the computational cost of STG-3 depends on the width w + 1 of T bkj , whose cost can become undesirable for critical scenarios where the control has to be resolved in linear time. However, this study concentrates on the worst cases where nd ≈ n, without considering the ability of the approach to prepare each backup instance using the diameter in the best cases. Similarly, STG-1 can also be an inadequate strategy with respect to STG-2 because the diameter computed in STG-2 benefits the fulfillment of RR2 (out degree = 0), reducing the computational costs and the expansion of N D in each iteration. On the other hand, STG-1 and STG-2 have to transverse the entire network to search for the best candidates that satisfy conditions RR1 and RR2 (explicitly taking into account non-locality); while STG-3 must go over each backup instance to obtain the best candidates that satisfy condition RR3. Nevertheless, the dynamic computation of the diameter in STG-2 again highlights the benefit of the strategy to mitigate the non-locality problem of PDS inherent in the strategies by pre-computation.

On the other hand, we have implemented the three strategies over a powerlaw distribution called PLOD [START_REF] Palmer | Generating network topologies that obey power laws[END_REF], which is analyzed in [START_REF] Alcaraz | Structural controllability of networks for non-interactive adversarial vertex removal[END_REF]. The developments are based on Matlab with a low connectivity probability to produce a more realistic critical scenario with sparse distributions, using y α with α = 0.2 and networks with medium (≤ 1,000) and large (≤ 3,100) numbers of nodes. For each network produced, we have analyzed the resulting effect that can cause an attack of the types SCN-1 and SCN-2 in one arbitrary node (either a TG-1 or a TG-2) or in a subset of "nodes/2" arbitrary nodes that are either TG-1 or TG-2. The results of the simulations are shown in Table 2, which depicts the efficiency of the three strategies with regard to the changes caused on the size of N D after perturbation. It can be deduced from the table that the variation of the set of driver nodes does not become significant with respect to the number of attacked nodes. In addition, it is important to note that 99% of the observation rate (for U-1 and U-2 nodes) were completely lost for all cases after perturbation. Despite this, we also observed that the networks were equally able to retake 100% of the control after recovery without significant changes in the majority of the cases, and especially for STG-2 partly due to the use of the network diameter.

Conclusions

Structural controllability offers a powerful abstraction for understanding the properties of critical nodes in a control network, which is vital to restoring control following node or link failures and, in particular, deliberate attacks. This helps minimize the period during which a control system is held by an adversary. Also, it helps minimize the period during which the system may reach undesirable states -in the case of electrical power systems and networks, this period can be in the order of seconds or less before severe effects occur.

The main contributions of this paper are the three repair strategies for controllability in control graphs using the structural controllability abstraction, and relying on the PDS formulation to gain a clearer understanding of the effects of topology constraints on the repair strategies. These include re-linking without restrictions, re-linking with constrained network diameter and the use of pre-computed instances of driver nodes. In this way, controllability powerlaw networks can be restored more efficiently than by re-computing the controlling nodes when their links have been perturbed by attacks on availability. The three strategies have been analyzed formally and subjected to a complexity analysis. The results highlight that the use of a network diameter can be a suitable option to establish control with low computational and storage costs.

Our future work will focus on extending the analysis to explore the possibility of restoring control subgraphs instead of the entire network while retaining acceptable control graph parameters (primarily the number of nodes, maximum out-degree and diameter), thereby improving the respective approaches and their complexity. Another topic involves the renewed study of power-law networks and optimizing approximation mechanisms for controllability that give satisfactory average-time complexity. Finally, our research will also investigate new attack models, especially those involving interactions between attackers and defenders.

TG- 1

 1 in SCN-2: The verification of OR2 is not possible because of the complete isolation of the nodes in attacked N D ; hence O(kn 2 + (a + e)) = O(kn 2 ). TG-2 in SCN-1: This attack scenario requires Algorithm 3 to explore the existence of a parent n d fv related to v ∈ attacked O that does not comply with OR2. This entails an upper bound of O(kn 2 + (a(f + e) + n 2 )) = O(kn 2 ). TG-2 in SCN-2: This case is similar to TG-1 in the SCN-2 proof. The extension of N D can be influenced according to: TG-x in SCN-1: An increase of at least two new n d in N D . TG-x in SCN-2: An increase of one unit in N D in the worst case. The computational cost of Algorithm 4 is analogous to that of restoration strategy STG-1 (Algorithm 1), but this time it is necessary to consider the overhead involved in the best-first search (O(n + e)) to compute the diameter of the entire network. After the list with diameter values is obtained, the driver nodes related to N D -A are extracted in order to validate them with an acyclicity test (O((nda)(n + e)) = O(n 2 )) and to subsequently obtain the driver nodes with the highest in-degree (O(nda) = O(n)) that comply with RR2 (O((nda) + e) = O(n + e)). The overhead of the first part is so far O(k((n + e) + n 2 + n + (n + e))) = O(kn 2

M P bk=1 ( 2 ( 2 ( 2 ( 2 ( 2

 bk=122222 w+1 (b + e)))) nd + 2 O(k( w+1 (b + e)))) nd + 1 TG-x in SCN-1: O(k( M bk=1 w+1 (b + e)))) + O((a + e) + n 2 ), resulting in O(k( M bk=1 w+1 (b + e)))), where N D increases its value at least in two nodes in the worst case. TG-x in SCN-2: O(k( M bk=1 w+1 (b + e)))) + O(n 2 ) = O(k( e)))), where N D increases its value at least in one node.

  ). output ND local n d , attacked ND, attacked O, or2, i; attacked ND ← ND ∩ A; attacked O ← A -ND; if (attacked ND / ∈ ⊘) and (or2 == false) then if ∃ a n d ∈ attacked ND that breaks OR2 then ND ← ND ∪ {children(n d ) -ND}; or2 ← true;

	end if
	end if
	if (attacked O / ∈ ⊘) and (or2 == false) then i ← 1; while (i ≤| attacked O |) and (or2 == false) do S1 ← fathers(attacked O[i]); if ∃ a s1 ∈ S1 that breaks OR2 then ND ← ND ∪ {children(s1) -ND}; or2 ← true; end if
	i ← i + 1; end while
	end if
	if or2 then
	Execute OR2 def ined in [1];
	end if
	return (⋆) ND;

Table 1 .

 1 Complexity of the three restoration strategies.

			Threat Scenarios
		SCN-1 -TG-x		SCN-2 -TG-x
		Time	ND	Time	ND
	STG-1	O(kn 2 )	nd + 2	O(kn 2 )	nd + 1
	STG-2	O(kn 2 )	nd + 2	O(kn 2 )	nd + 1
	STG-3 O(k(

Table 2 .

 2 Changes in ND when one or n/2 random nodes are targeted.

Acknowledgements

This research was partially funded by the Marie Curie COFUND Programme U-Mobility supported by the University of Malaga, by the EC FP7 Project under GA No. 246550, and by the Ministerio de Economia y Competitividad (COFUND2013-40259). This research was also partially funded by the EU FP7 ARTEMIS Project under GA No. 269374 and by the Spanish Ministry of Science and Innovation under the ARES Project (CSD2007-00004).

Case 1: Analogous to Case 1 of the STG-1 proof in Section 3.1.

Case 2: U ̸ = ⊘ after perturbation, being | U |= 1. As in Case 2 of the STG-1 proof, two sub-cases must be distinguished:

then Algorithm 5 needs to traverse all trees T bkj from the bottom to locate the bags in T bkj that contain the best driver candidates to cover u. This process involves the verification of the existence of an n d bl ∈ bags i -A such that (n d bl , u) ∈ E with minimum diameter in which RR3 is fulfilled. During this process, we also explore if such an n d bl belongs to N D to avoid increasing N D . If so, the set S 1 is updated through S 1 ∪ {n d bl }; otherwise, S 2 is updated. In the case where S 1 ̸ = ⊘, we ensure that u is covered by


Haihui Gao

Yong Peng

Zhonghua Dai

Ting Wang

Xuefeng Han

Hanjing Li

AN INDUSTRIAL CONTROL SYSTEM TESTBED BASED ON EMULATION, PHYSICAL DEVICES AND SIMULATION

Keywords: Industrial control systems, cyber security, testbed, simulation

This paper demonstrates the utility of an industrial control system testbed that incorporates a universal, realistic, measurable, controllable and reusable experimental platform for cyber security research and testing. The testbed has a layered architecture that leverages physical devices and emulation and simulation technologies. The testbed enables researchers to create experiments of varying levels of fidelity for vulnerability discovery, product evaluation and system certification. The utility of the testbed is demonstrated via a case study involving an industrial boiler control system.

Introduction

Industrial control systems (ICSs) monitor and control processes in critical infrastructure assets [START_REF] Stouffer | Guide to Industrial Control Systems (ICS) Security[END_REF]. Due to their increased connectivity with corporate networks and the Internet, industrial control systems are no longer immune to cyber attacks. Indeed, in 2010, the Stuxnet worm demonstrated to the world the seriousness of industrial control system vulnerabilities and the potential threats [START_REF] Queiroz | Building a SCADA security testbed[END_REF].

In order to protect industrial control systems, it is important to conduct cyber security research and testing to identify and mitigate existing vulnerabilities [START_REF] Brandle | Security for process control systems: An overview[END_REF][START_REF] Bessani | The CRUTIAL way of critical infrastructure protection[END_REF]. However, testing and evaluation of actual industrial control systems are difficult to perform due to the uptime requirements and the risk of damage to operational systems. Therefore, it is necessary to build suitable experimental platforms to develop and test cyber security solutions for industrial control systems [START_REF] Queiroz | Building a SCADA security testbed[END_REF]. The emulation, physical devices and simulation for industrial control systems (EPS-ICS) testbed presented in this paper seeks to address this problem. The testbed provides configurable fidelity using physical devices for core system components, while emulating or simulating the other components. The proposed solution is an inexpensive, albeit useful, approximation of an industrial control system environment. Indeed, the EPS-ICS testbed strikes the right balance between research requirements and construction costs.

Architecture

Figure 1 shows an example industrial control system reference model that conforms to the ANSI/ISA-99 standard [START_REF]International Society of Automation, Security for Industrial Automation and Control Systems, Part 1: Terminology, Concepts and Models[END_REF]. The architecture is segmented into four levels: (i) corporate network; (ii) supervisory control local area network (LAN); (iii) control network; and (iv) input/output (I/O) network.

In the ANSI/ISA-99 standard, the corporate network level (Level 3) is responsible for management and related activities (e.g., production scheduling, operations management and financial transactions) [START_REF] Schwartz | Control System Devices: Architectures and Supply Channels Overview[END_REF]. This level is consistent with traditional information technology, including the general deployment of services and systems such as FTP, websites, mail servers, enterprise resource planning (ERP) systems and office automation systems. The supervisory control LAN level (Level 2) includes the functions involved in monitoring and controlling physical processes and the general deployment of systems such as human-machine interfaces (HMIs), engineering workstations and historians. The control network level (Level 1) includes the functions involved in sensing and manipulating physical processes. Typical devices at this level are programmable logic controllers (PLCs), distributed control systems, safety instrumented systems and remote terminal units (RTUs). The I/O network level (Level 0) includes the actual physical processes and sensors and actuators that are directly connected to process equipment.

Testbed Construction

Industrial control system testbeds may be categorized as:

Physical testbeds that are constructed using replication methodologies.

Software (virtual) testbeds that are constructed using modeling methodologies.

Hybrid testbeds that are constructed using replication and modeling methodologies.

A replicated testbed is a copy of a real system with the same physical devices and information systems. An example is the National SCADA Testbed (NSTB) of the U.S. Department of Energy [8]. Although a replicated architecture provides the highest fidelity, building an identical replica of a real-world system is usually cost prohibitive.

A software testbed uses modeling methodologies instead of actual physical devices; it typically includes a physical process simulator, network simulator and attack simulator. Such a testbed is a low cost solution for research focused on attacks on industrial control systems and the development of security strategies. However, due to the absence of real components and devices, the architecture provides low fidelity.

A hybrid testbed incorporates replicated devices and systems as well as software models. The architecture provides a high degree of fidelity and is also cost effective. The EPS-ICS testbed described in this paper is based on a hybrid architecture.

EPS-ICS Testbed Architecture

Figure 2 shows the EPS-ICS testbed architecture. The architecture has four types of components: (i) emulated components; (ii) physical components; (iii) simulated components; and (iv) interface components. The industrial control system of interest is modeled as a single testbed comprising emulated, physical and simulated devices. Levels 2 and 3 of the ANSI/ISA-99 industrial control system reference model are implemented using emulation technologies similar to Emulab [START_REF]Emulab, Total Network Testbed[END_REF]. Level 1 of the reference model is implemented by replicating physical devices while Level 0 is implemented using simulated mathematical models of controlled processes developed with Matlab/Simulink.

Figure 3 shows the EPS-ICS network architecture. It is a dynamically controlled construct, consisting of a measurable and reusable experimental environment with switches, servers and other physical resources. The hardware includes wired and wireless nodes. Note that the testbed effectively models a corporate network (Level 3) and supervisory control LAN (Level 2).

The Level 1 control network is the core of the industrial control system reference model. The EPS-ICS testbed incorporates physical devices in Level 1 to achieve high fidelity for research and testing requirements. The testbed uses Matlab/Simulink to construct Level 0 models in order to reduce costs and reuse I/O layer components. This flexibility enables the testbed to model a variety of controlled processes (e.g., steam boiler, storage tank and heat exchanger).

The EPS-ICS testbed effectively replicates the interactions between industrial control system components. Industrial control system components, such as the corporate network and supervisory control LAN, may be implemented as emulations or as physical components using the testbed interface. Thus, the EPS-ICS testbed can provide varying levels of fidelity to meet diverse research and testing objectives. Interfaces between emulated and physical devices implement communications using IP routing (e.g., routers, layer-three switches and wired/wireless networks). Figure 4 shows interface communications between physical and simulated devices; special hardware between the devices enables data exchange. Peripheral component interconnect (PCI) modules support full communications between Matlab/Simulink models and external controllers.

Experimental Setup and Results

This section shows how an industrial boiler control system is constructed using the EPS-ICS testbed.

Corporate and Control Networks

Figure 5 shows the experimental industrial boiler control system. The computers in the corporate zone are used to simulate daily office activities and internal security testing. The Internet zone is used for external security testing. Web servers and external DNS servers are deployed in the demilitarized zone (DMZ) for external communications (e.g., Internet connectivity). HMI servers, SCADA servers and other production systems are deployed in the process control zone; they interact with field devices (e.g., PLCs). The process control functionality is represented by physical and simulated devices corresponding to the boiler system.

Industrial Boiler Control System Model

A Matlab/Simulink simulation model was developed by performing a comprehensive engineering analysis of an industrial oil-fired boiler. The control of the oil-fired boiler simulation model is achieved by integrating PLCs and RTUs in the industrial control network. The following sections describe the mathematical models of the furnace, boiler drum, riser, downcomer and superheater [START_REF] Flynn | A drum boiler model for long term power system dynamic simulation[END_REF][START_REF] Gan | Development of main boiler simulation system for LNG ship[END_REF][START_REF] Rusinowski | Mathematical model of the CFB boiler co-fired with coal and biomass[END_REF].

Furnace Model. The mass balance, energy balance and furnace radiation heat transfer equations are:

ṁf + ṁa -ṁg = V f d dt (ρ g ) ( 1 )
ṁf

Q f + ṁa h a -ṁg h g -Q rht = V f d dt (ρ g h g ) ( 2 )
Q rht = α hd σψF l T 4 g ξ (3)
where ṁf is the fuel flow into the furnace, Q f is the fuel heat, ṁa is the air flow into the furnace, h a is the air enthalpy, ṁg is the gas flow out of the furnace, h g is the gas enthalpy, Q rht is the radiation heat transfer, V f is the furnace volume, ρ g is the gas density, σ is the Boltzmann black body radiation constant, α hd is the furnace emissivity, ψ is the furnace water degree, ξ is the fouling factor, T g is the gas temperature and F l is the furnace area.

Boiler Drum Model. The upper section of the boiler drum contains steam and the bottom section contains water. The liquid zone mass conservation, vapor zone mass conservation, drum energy balance and drum liquid level equations are:

ṁw + (1 -x) ṁrc -ṁdcin -ṁpw -ṁec = d dt (ρ w V w d ) ( 4 ) ṁrc x -ṁs + ṁec = d dt (ρ s V s d ) ( 5
)
ṁw h w + (1 -x) ṁrc h w + x ṁrc h s -ṁdcin h w -ṁs h s -ṁpw h w = d dt (ρ s V s d h s + ρ w V s d h w + M dm C dm T d ) -JV d d dt (P d ) + ṁec h s (6) V w d = 1 3 πL 2 v (3r -L v ) + 1 2 (L -2r)r 2 (θ -sin θ) ( 7 )
θ = 2cos -1 ( r -L r ) ( 8
)
where ṁw is the feed water flow from the economizer, x is the steam dryness, ṁrc is the steam-water flow in the riser, ṁdcin is the downcomer inlet flow, ṁpw is the blow-down flow, ṁec is the dynamic evaporation flow, ρ w is the saturated water density, V w d is the drum liquid zone volume, ṁs is the steam discharge capacity, ρ s is the steam density, V s d is the drum vapor zone volume, h w is the feed water enthalpy from the economizer, h s is the steam enthalpy, M dm is the drum metal quality, C dm is the drum metal specific heat capacity, T d is the drum temperature, J is the unit conversion factor, V d is the drum volume, P d is the drum pressure, L is the drum length, r is the drum radius and

L v = f -1 (V w d ) is the drum liquid level.
Riser Model. The riser contains both liquid and vapor. The liquid zone mass conservation, vapor zone mass conservation, energy balance, metal energy balance, average ratio of vapor per cross-sectional area in the vapor zone, liquid zone accounted for in the riser length ratio, and steam volume in the riser equations are:

ṁdcout -(1 -x) ṁrc -ṁevp -ṁecl = d dt (ρ w V w rc ) ( 9 ) ṁecl + ṁevp -x ṁrc = d dt (ρ s V s rc ) ( 1 0 ) ṁdcout h dcout -(1 -x) ṁrc h w -x ṁrc h s + Q rc = d dt (ρ s V s rc h s + ρ w V w rc h w ) -JV rc d dt (P d ) ( 1 1 )
Q rht -Q rc = M mrc C mrc d dt (T mrc ) ( 1 2
)

ϕ rc = k 1 + ρs ρw ( 1 xs -1) (13)
γ rc = ṁdcout (h w -h dcout ) Q rc (14) V s rc = V rc (1 -γ rc )ϕ rc ( 15
)
where ṁdcout is the downcomer outlet water flow, ṁevp is the evaporation generated by heat absorption, ṁecl is the dynamic evaporation flow, V w rc is the water volume in the riser, Q rc is the medium heat in the riser, h dcout is the medium enthalpy at the downcomer outlet, V s rc is the steam volume in the riser, V rc is the riser volume, M mrc is the riser metal mass, C mrc is the riser metal specific heat capacity, T mrc is the riser metal temperature, ϕ rc is the liquid zone steam section ratio in the ascending pipe and x s is the average steam dryness in the vapor zone. Downcomer Model. The downcomer preheats the water supply and returns cool water to the bottom of the drum. The energy balance equation is:

ṁdcin h dcin -ṁdcout h dcout = d dt (ρ w V dc h dcout + M mdc C mdc T mdc ) (16)
where ṁdcin is the inlet water flow, ṁdcout is the outlet water flow, h dcin is the inlet water enthalpy, h dcout is the outlet water enthalpy, V dc is the volume, M mdc is the metal quality, C mdc is the metal specific heat capacity and T mdc is the metal temperature at the downcomer.

Superheater Model. The superheater increases the thermal energy. The mass balance and energy balance equations are:

ṁsin -ṁsout = V sh • dρ s dt (17) Q g -M msh • C msh • dT msh dt + ṁsin • h sin -ṁsout • h sout = V sh • d(ρ s • hs ) dt ( 18
)
where ṁsin is the inlet steam flow, ṁsout is the outlet steam flow, V sh is the superheater volume, ρs is the inlet and outlet average steam density, Q g is the heat release of the gas, M msh is the superheater metal mass, C msh is the superheater metal specific heat capacity, T msh is the superheater metal temperature, h sin is the inlet steam enthalpy, h sout is the outlet steam enthalpy and hs is the inlet and outlet average steam enthalpy.

Figure 6 shows the oil-fired boiler simulation model implemented using Matlab/Simulink. The boiler simulation model interacts with external controllers. The resulting EPS-ICS testbed can be used for cyber security research and testing.

Device Evaluation and Certification

Devices that are to be evaluated and certified interact with the EPS-ICS testbed via a network interface or TAP device using Layer 2 access. Table 1 shows some common testing devices that can interact with the EPS-ICS testbed [START_REF] Zhao | Security testing methods and techniques of industrial control devices[END_REF].

Researchers can select three EPS-ICS access points for testing: (i) Internet zone; (ii) corporate zone; and (iii) process control zone. Figure 7 shows an example attack path that includes man-in-the-middle, denial-of-service and replay attacks. Table 2 lists the potential outcomes of and assessment [START_REF] Kube | Automated testing of industrial control devices: The Delphi database[END_REF]. The first step in the assessment is system discovery, which identifies information assets, operating system types, service ports and running applications. The second step involves a man-in-the-middle attack that tampers with the data transmitted between host computers and end devices. The third step involves a denial-of-service (SYN flood) attack that consumes end device resources. The fourth step involves a replay attack that bypasses password protection, uploads and modifies an end device program and disrupts system execution. Figure 8 shows the results of the assessment.

Conclusions

The EPS-ICS testbed presented in this paper is designed specifically for industrial control system security research and testing. It seamlessly integrates emulation, physical device and simulation technologies to strike the right balance between fidelity and construction costs. The industrial boiler control system case study demonstrates the application and utility of the EPS-ICS testbed for industrial control system evaluation and certification. Future research will focus on the continued refinement of the EPS-ICS testbed, which will involve developing new monitoring and analysis techniques, expanding the applicability of the testbed and constructing a complementary cyber-physical testbed.

Figure 1 .

 1 Figure 1. Industrial control system reference model.

Figure 2 .

 2 Figure 2. EPS-ICS testbed architecture.

Figure 3 .

 3 Figure 3. EPS-ICS network architecture.

Figure 4 .

 4 Figure 4. Interfaces between physical and simulated devices.

Figure 5 .

 5 Figure 5. Industrial boiler control system based on the EPS-ICS testbed.

Figure 6 .

 6 Figure 6. Simulation model of the oil-fired boiler.

Figure 8 .

 8 Figure 8. Assessment results.

Table 1 .

 1 Common testing devices[START_REF] Zhao | Security testing methods and techniques of industrial control devices[END_REF].

	Tool	Availability Certification	Critical Techniques
	Achilles	Commercial	Achilles Certification Fuzzing, Storm, Monitor
	Mu-8000	Commercial	MUSIC Certification Fuzzing, Monitor
	Defensics	Commercial	None	Fuzzing
	BreakPoint Commercial	None	Fuzzing, Storm
	beSTORM	Commercial	None	Fuzzing
	Sully	Free	None	Fuzzing
		LoV	LoC	PLoV+PLoC
		System	DoS-SYN	Replay
		Enumeration	Flood	Testing
		Man-in-the-
		Middle Testing
		Figure 7. Test procedures and results.

Table 2 .

 2 Description of vulnerabilities[START_REF] Kube | Automated testing of industrial control devices: The Delphi database[END_REF].

	Terms	Device Under Test (DUT)
	Loss of View	DUT network stack no longer sends or
	(LoV)	processes legitimate network traffic
	Loss of Control	DUT process control functionality is
	(LoC)	disrupted
	Permanent Loss of View	Loss of view persists; manual intervention
	(PLoV)	is required to return DUT to normal state
	Permanent Loss of Control Loss of control persists; manual intervention
	(PLoC)	is required to return DUT to normal state


Mohammad Ababneh

Malek Athamnah

Duminda Wijesekera

Paulo Costa

AN AUTOMATED DIALOG SYSTEM FOR CONDUCTING SECURITY INTERVIEWS FOR ACCESS CONTROL

Keywords: Automated dialog system, security interviews, border control

Visa, border entry and security clearance interviews are critical homeland security activities that provide access privileges to the geographical United States or to classified information. The person conducting such an interview may not be an expert in the subject area or could be deceived by a manipulative interviewee, resulting in negative security consequences. This paper demonstrates how an interactive voice response system can be used to generate context-sensitive, yet randomized, dialogs that provide confidence in the trustworthiness of an interviewee based on his/her ability to answer questions. The system uses contextual reasoning and ontological inference to derive new facts dynamically. Item response theory is employed to create relevant questions based on social, environmental, relational and historical attributes related to interviewees who seek access to controlled areas or sensitive information.

Introduction

Security mechanisms such as guarded gates, border control points and visa issuance counters are implemented to allow access to individuals upon proper authentication and authorization. Legitimacy is usually determined by rules, regulations and/or policies applied by entry control personnel who attempt to ensure that the entry requirements are enforced. Correctly identifying a person may require an examination of an electronic passport, identity card and paper documents in addition to asking the person questions about information contained in the documents.

In order to perform authentication and authorization, an official often conducts an interview in which the aspiring entrant is asked a series of questions based on the specific situation. Ideally, these questions should be relevant, of a reasonable level of difficulty (i.e., neither too difficult nor common knowledge) and should not have been asked previously in similar venues.

The success of interactive voice response (IVR) in auto attendants, satellite navigation devices, personal assistants and mobile applications supported by Apple's Siri, Google Voice and Microsoft's Speech has motivated this research on using interactive voice response systems for access control in visa interviews, entry point interviews, biometric enrollment interviews, resetting passwords and granting access to sensitive resources. Indeed, the goal is to leverage voice technology in automating dialogs used for access control determination.

The use of interactive voice response systems for access control has some limitations. First, most interactive voice response systems have a finite number of pre-programmed conversations. Therefore, the set of questions generated by such a system is the same for every conversation. This may expose the set of questions so that aspiring entrants may arrive with prepared answers. A second limitation is that using a set of random questions from a large pool (typically done to prevent an individual from obtaining the entire knowledge set) may not have the adequate level of difficulty to challenge the aspiring entrant appropriately to determine his/her trustworthiness. A third limitation is that current interactive voice response systems are incapable of discriminating between an individual who knows the subject matter from an individual who correctly guesses the answers. Finally, current interactive voice response technology cannot generate a semantically-coherent sequence of questions that is relevant to the sub-domain that is the focus of the interrogation.

To address the above limitations, this paper proposes an ontological inference-based interactive voice response system that uses item response theory (IRT) to select relevant questions and evaluate trustworthiness. The system uses the access control markup language (XACML) to specify attributes of eligible subjects in the form of an access policy. The proposed system uses an ontology to generate the terms in the access control policy to produce questions. By using an inference engine, a large number of previously-unknown facts about the policy, its attributes and relevant facts are obtained; this provides a large random sample of potential questions [START_REF] Ababneh | Dynamically generating policy compliant dialogs for physical access control[END_REF]. Because the system does not need to store inferred information or save previous question-answer pairs, it can defend against the primary misuse case of human replay attacks. Item response theory is employed to overcome the limitation of selecting relevant questions with acceptable levels of difficulty by creating questions from a large number of attributes present in the policy and ontology.

Background

This section describes the theory and technology underlying the interactive voice response system.

Semantic Web and Ontologies

Mature semantic web technologies, including the Ontology Web Language (OWL), reasoners, repositories and the Simple Protocol and RDF Query Language (SPARQL), are used to model, query and infer information about subjects, objects, relations and attributes [START_REF]OWL 2 Web Ontology Language Primer[END_REF]. The core facts represented by triples extracted from policy rules and formal sources of information (e.g., law enforcement, Department of State and Department of Homeland Security databases) are stored as an ontology. The representation enables a common and standard format for data usage and sharing. Note that this paper uses a homeland security ontology for demonstration purposes.

The primary advantage of an ontology is the ability to use reasoners [START_REF]HermiT OWL Reasoner[END_REF]. Reasoners are key components of semantic web technologies that can infer implicit facts from existing ones and provide explanations about relationships.

A context-aware application takes into account the context, which includes social, physiological, biometric, environmental, hardware, computational, temporal, activity, identity and location factors [START_REF] Beamon | HyCoRE: Towards a generalized hierarchical hybrid context reasoning engine[END_REF]. Contextual reasoning involves the inference of contextual information using ontological reasoners. The selection of questions based on item response theory parameters (e.g., difficulty) ensures that the selected questions align within a semantic context. Note that the modeling context enables a reasoner to infer facts relevant to the subject being questioned.

Item Response Theory

Item response theory, sometimes called latent trait theory, is used by psychometricians to test individuals. An item response theory score assigned to an individual is said to measure the individual's latent trait or ability. Mathematically, item response theory provides a characterization of what happens when an individual meets an item such as an exam or an interview. In item response theory, each individual is characterized by a proficiency parameter θ that represents the individual's ability. Each item is characterized by a collection of parameters: discrimination (a), difficulty (b) and guessing factor (c). When an individual (examinee) answers a question, item response theory uses the examinee's proficiency level and the item parameters to predict the probability that the examinee answered the item correctly. The probability of answering a question correctly in a three-parameter model is given by [START_REF] Baker | The Basics of Item Response Theory[END_REF]:

P = c + (1 -c) 1 + e -a(θ-b) ( 1
)
where e is the Euler number.

In order to determine the discrimination and difficulty parameters of a test item, item response theory uses Bayesian estimation, maximum likelihood estimation (MLE) and other similar methods [START_REF] Wainer | Computerized Adaptive Testing: A Primer[END_REF][START_REF] Weiss | Application of computerized adaptive testing to educational problems[END_REF]. To estimate the examinee's ability, item response theory utilizes an iterative maximum likelihood estimation process involving an a priori value of the ability, item parameters and response vector:

θs+1 = θs + N i=1 -a i [u i -P i ( θs )] N i=1 a 2 i P i ( θs )Q i ( θs ) ( 2
)
where θs is the estimated ability in iteration s; a i is the discrimination parameter of item i (i = 1, 2, • • • , N); u i is the response of the examinee (one for correct or zero for incorrect); P i ( θs ) is the probability of correct response according to Equation (1); and Q i ( θs ) is the probability of incorrect response.

Access Control and XACML

Access control policies specify the resources that a subject may access and the conditions under which the access may be granted. This work uses the OASIS XML-based Extensible Access Control Markup Language (XACML) to specify access control policies. In particular, XACML specifies subjects, objects and resources using defined attributes (e.g., verified (ID, password) pair as a subject/object attribute). Figure 1 shows a sample policy rule for the homeland security ontology that allows a person whose subject-id attribute value is "DiasKadyrbayev" to enter the United States.

Interactive Voice Response

Dialog systems provide the means for humans to interact with computer systems. A dialog system uses text, voice and other means to carry out a conversation with a human in order to achieve some objective. Most dialog systems are created with specific objectives in mind and generally involve preprogrammed conversations. An interactive voice response environment incorporates a markup language to specify voice dialogs, a voice recognition engine, a voice browser and auxiliary services that allow a computer to interact with humans using voice and dual tone multi-frequency (DTMF) tones via a keypad [START_REF]OWL 2 Web Ontology Language Primer[END_REF]. VoiceXML is a voice markup language used to create audio dialogs that feature synthesized speech, digitized audio, recognition of spoken and DTMF inputs, recording of spoken input, telephony and mixed initiative conversations.

System Architecture

Figure 2 shows the overall architecture of the ontology-based interactive voice response system. Axiomatic and derived facts from the ontology are used to create questions asked by the system. Given that a large number of facts can be derived from a context-sensitive ontology, but only a few questions can be asked during an interview, item response theory is used to select the facts that are used to generate questions.

The item response theory module transforms a question into VoiceXML and plays it to the user. The system then waits for the user's response and the system's voice recognition software attempts to recognize the input and check the correctness of the answer. Based on the answer, the item response theory estimation procedure either increases or decreases the a priori ability score.

The system uses item response theory to manage and control dialog questions generated from a large pool of ontologically-derived facts in a manner that shortens the length of a dialog while maintaining the maximum accuracy in estimating the user's trustworthiness. When item response theory is not employed, the dialogs tend to be very long or are randomly generated with the possibility of repeated questions.

Another key characteristic of the system is its use of the OWL annotation property to assign item response theory parameters to axioms. Annotations were selected in order to keep the semantics of the original ontology and structure intact. Every asserted axiom in the ontology is annotated with three item response theory parameters, namely discrimination (a), difficulty (b) and guessing (c). Currently, it is assumed that all the asserted axioms have the same default degree of difficulty and a discrimination value of one.

The most important characteristic of the system is that weights are assigned to questions and their answers according to the lengths of the inference or explanation paths. The lengths of the paths are then translated to item response theory difficulty values. Table 1 shows the difficulty value assignment scheme used by the system.

Higher values or weights are assigned according to the number of explanation axioms used to infer a fact. Consequently, such questions are considered to be more difficult than those generated from asserted facts. The item response theory based solution algorithm uses the two-parameter model that relies on the difficulty and discrimination parameters. Figure 3 shows the algorithm used for ability estimation.

After every interactive iteration involving question generation and answering, the item response theory algorithm estimates the ability of the user before selecting and asking the next question. When the ability estimation reaches a predefined threshold, the system concludes the dialog and conveys the decision. Consequently, the decision is based on the item response theory characteristics of the axioms, not on the percentage of correctly-answered questions as in traditional testing.

Involving Context in Dialog Management

This section describes contextual reasoning strategies for selecting questions based on the current context or a previous context. According to the selection criteria, an item is determined only by the item response theory parameters, which have to be in a range of values close to the interim ability estimation θ. This can result in questions that are non-homogeneous and unrelated. For example, one question could be: [is it true (a isBrotherOf b)? ] while the next question could be: [is it true (Obama isPresidentOf United States)? ].

Contextual reasoning expands item selection by asking related questions. The concern is not only about the item response theory parameters of a question rendered from an annotated ontology axiom, but also an attempt to continue to ask questions that are related to each other in order to test the user on a branch of knowledge. Compared with the example above, a more relevant series of questions might be [is it true (a isBrotherOf c)] followed by [is it true (b isFriendOf c)]. Note that the two relations isBrotherOf and isFriendOf are contextually related by a social relationship context between two people. In order to capture these notions of context, the subject of a previous question is used to generate the next question. Multiple strategies can be used to achieve this objective, such as selecting the next question based solely on subject, solely on property, solely on object or a combination of the three.

A reasoner is used to execute queries in the selection algorithm. A reasoner query using the subject, property or object of a question/axiom is executed to further filter the axioms in the item bank. A contextual reasoning module is incorporated in the architecture to select the axiom elements of the current axiom/question and execute a reasoner query. The addition of this query fur-ther filters the triple (subject, property, object) that was previously asserted or inferred by the reasoner. The next axiom/question are determined based on a component of the triple.

The axiom parameters of the current question are examined while the voice rendering loop is executing. Subsequently, a query is passed to the reasoner that returns axioms based on the current context. The next question is generated from the newly executed query result and the item response theory parameters that satisfy the item selection criteria for ability estimation and identification.

In the case of historical contextual reasoning, the current context is expanded by saving the user's session questions and answers in an ontology. A reasoner is executed over the closure of the session with the axioms in the item bank ontology. As a result, questions can be asked in subsequent sessions that are related to the questions posed in previous sessions. Selection strategies for multiple sessions include: Asking a question related to a question that a user answered incorrectly in a previous session.

Asking a question requiring deeper knowledge than a correctly-answered question in a previous session.

Asking a question about personal relationships related to a previous session (e.g., about co-workers, family members or friends).

This capability provides benefits when evaluating an individual multiple times or a group of related people. For example, related attributes are very likely to be encountered during immigration and security clearance interviews. They also provide the ability to detect abnormal changes in user behavior and personality.

Context Ontology

Historical context is modeled using an ontology that supports reasoning. Figure 4 shows a context ontology developed with the following classes:

Item: Defines a question generated from an axiom triple (subject, property, object) with respect to difficulty annotation and ID annotation.

Session: Defines an interaction session between the user and the interactive voice response system. The session ID is extracted from the interactive voice response.

User: Defines a user. In our application, the user is the "sameAs" an individual in the item bank ontology. such axioms makes context-aware reasoning possible. Queries related to questions posed to the current user or to previous users can be executed. This makes it possible to select questions that were previously asked to another user who has a relationship with the current user.

Contextual Reasoning for Item Selection

The work presented to this point focuses on formal types of policy and knowledge. The axioms must be retained in documents and records. This section discusses how the access control system can be enhanced using knowledge and rules that exist in informal data representations such as social networks (e.g., Facebook, Twitter, LinkedIn and Google+). This is based on the observation that trails, properties, links and photographs contained in social network accounts can be converted to and interfaced with using an ontology to create dialogs used for authentication and authorization. Examples include: Twitter -A isFollowing B; Facebook -B likesPost C; and LinkedIn -C hasContact B and A isGroupMember InformationSecurity.

In the system enhancement, the ontology-based and item-response-theorysupported interactive voice response functionality is augmented with social network information. For example, the system uses Twitter4J APIs [START_REF][END_REF] associated with Twitter. Information extracted from the informal and social knowledge web service is used to populate the context ontology. Figure 5 shows a code snippet and its results, which include the Twitter followers of a specific user and the status of the user. The method twitter.getFollowersIDs returns the IDs and the method twitter.updateStatus returns the status and location. Axioms such as [User 0001 isFollowing 1162907539], [81382232 isLocate-dIn "Fairfax, VA"] and [User 0004 isSameIndividualAs 383575552] are added to the context ontology.

Leveraging the informal data clearly enhances the questions asked by the system. Indeed, questions can be asked about facts collected from formal interviews, official forms, previous sessions as well as social network attributes.

Implementation

This section describes the implementation and the performance characteristics of contextual queries.

Integrating IVR, Ontology, IRT and Context

The interview begins with a VoiceXML menu hosted on a Voxeo Prophecy web server. The voice browser connects to the web server and converts text- to-speech and speech-to-text. Figure 6 shows the algorithm, which integrates interactive voice response, ontology and context. The main steps of the algorithm are:

Line 1: Load and parse the ontology into a Document Object Model (DOM) document.

Lines 2-7: Extract the axiom triple (subject, property, object) and axiom difficulty from axioms and annotations and build separate arrays.

Lines 8-17: Establish a for loop to generate a number of questions synthesized from the axiom triple arrays (subject, property, object and difficulty) generated in Lines 2-7. An auxiliary verb such as "is" precedes the triples to indicate a true/false question. VoiceXML and JSP are used to render the format.

Lines 10-15: Obtain the user's response, which is yes/no or true/false. Convert the response to text (0 or 1) and build the response array (vector) used to calculate the ability (theta).

Line 16: Generate questions by contextual reasoning. In addition to the asserted and inferred axioms from the original ontology, a separate context ontology may be used as the target of a reasoner's query in order to ask the next related question. The reasoner's query method uses one of the (subject, property, object) triples as a parameter combined with the context ontology to extract the next related axiom/question.

Line 18: Invoke Algorithm 1 to calculate an estimate of the a posteriori θ from the a priori θ, which represents the ability or trust.

Lines 19-22: The last a posteriori θ is an estimate of the user's ability and is compared with a threshold value set by an administrator. Access is granted if θ is greater than the threshold; otherwise, access is denied.

Context Performance

Using a context for question generation requires frequent querying of the ontology. To evaluate the performance of question generation, a notional experiment was conducted using synthetic ontology samples that were generated via Java and OWLAPI. SPARQL queries were then executed to return relevant axioms related to specific subjects.

Ontologies were generated for various numbers of students and axioms from a foreign student database. Axioms such as [Student (randomNumber) isA Student], [Student (randomNumber) hasVisa F-1] and [Student (randomNumber) isFromCountry Country (randomNumber)] were added to produce attributes representative of the Lehigh University Bench Mark (LUBM) ontology [START_REF]Semantic Web and Agent Technologies Laboratory[END_REF]. Specifically, an ontology has the following structure:

There are a number of student individuals of type Student.

There are 200 countries.

There are two types of student visas, F-1 and J-1.

Every student in the ontology has a visa, either F-1 or J-1.

Every student is a national of one of the 200 countries.

Every student has a random number of friends (one to twenty) who are also students. Every student has participated in a random number of sessions with the system (one to twenty).

Table 2 presents the sample statistics, including the numbers of axioms and their sizes.

To test the performance of contextual reasoning queries, three contextual SPARQL queries were created and executed on the data set. Additionally, two baseline queries were developed for comparison.

Query15 returns all the predicates and objects participating in an axiom with a designated subject.

Query16 returns all the predicates and subjects participating in an axiom with a designated object.

Query17 returns the union of the results of Query15 and Query16.

Query18 returns all the axioms to provide a baseline for comparison with Query15, Query16 and Query17.

Query18 100 is a version of Query18 that limits the retrieval of results to 100. intent is to show the correctness of the queries. As expected, Query17 shows the union of Query15 and Query16, which is a subset of the total number of axioms returned by Query18. Table 4 shows the SPARQL query execution time. For a data set containing 10,000 students, Query18 takes approximately twelve seconds to retrieve the results. However, Query15, Query16 and Query17 all require less than 10 milliseconds.

Overall, the three contextual queries perform adequately, returning the expected results in an acceptable period of time. Indeed, the findings suggest that the contextual reasoning queries are executed efficiently and are not expected to cause recognizable delays in question generation that could affect the overall quality of the dialog during an interview.

Conclusions

The implementation of an interview system using ontologies, item response theory and contextual reasoning is certainly feasible. The use of ontologies and reasoning is critical to developing dialogs with items that are differentiated quantitatively. Item response theory provides a means to quantitatively characterize dialog items and to measure user trustworthiness and ability. Contextual reasoning provides the means to select the most appropriate questions quantitatively as well as questions that are semantically-relevant to the domain and subject of focus. The enhancement of contextual reasoning with social media information effectively supplements policy and ontology formal attributes with static and dynamic social attributes.

The paper also demonstrates that social media information is very useful for driving dialogs in interviews. However, the information was used without any analysis. Sentiment analysis is a growing area of research that attempts to predict trends in the inclinations or feelings of groups of people towards life issues. By leveraging social media, it is possible to deduce an individual's sentiments about a variety of issues, especially those related to national security. Our future research will focus on implementing a sentiment analysis module that builds on the social attributes module. The use of social media raises some legal concerns. At this time, we assume that individuals provide consent to use public social media information; however, a comprehensive evaluation of the legal ramifications is required before social media can be used in real interviews of individuals who seek access to controlled areas or sensitive information.

Figure 1 .

 1 Figure 1. Sample XACML policy rule.

Figure 2 .

 2 Figure 2. System architecture.

Figure 3 .

 3 Figure 3. Algorithm for ability estimation using item response theory.

For

  each question asked, a set of axioms is added to the context ontology. Some examples are: [User 0001 hasQuestion item 0002]; [Item 0001 wasOf-feredIn Session dd552fcdc5fccef412f96d38818a1c25] and [Session dd552fcdc5f-ccef412f96d38818a1c25 timeDateIs Jun 30, 2009 7:03:47 AM]. The existence of

Figure 4 .

 4 Figure 4. Contextual reasoning ontology.

Figure 5 .

 5 Figure 5. Twitter API code and results.

Table 1 .

 1 Difficulty assignment based on proof path depth.

	Explanations IRT Difficulty Level
	1	0	E a s y
	2-3	1
	4-5	1.5	Moderate
	6-7	2
	8-9	2.5
	≥ 10	3	Hard

  Algorithm 1: IRT Ability Estimation.

	Input: difficultyVector, answerVector, aprioritheta
	Output: aposterioritheta
	/* calculate theta and standard error */
	1: for (counter < items.length) do
	2:	itemDifficulty = parseFloat(difficultyVector[i]);
	3:	itemDiscrimination = "1";	//neutral value
	4:	answer=parseFloat(answerVector[i]);
	5:	probtheta=calculateProbability(itemDifficulty,
		itemDiscrimination, aprioritheta);	// equation 1
	6:	thetaSplus1 = thetaSplus1 + MLE(answer, probtheta);
			// equation 2
	7: endfor;
	8: aposterioritheta = thetaSplus1;
	9: return aposterioritheta;

  Algorithm 2: Dialog Access Decision Evaluation.

	Input: ontology, contextOntology, user_response,
		difficultyVector, answerVector, aprioritheta
	Output: access control decision
	/* make access control decision from dialog generated */
	/* from ontologies */
	1: domDocument = parse(ontology);
	2: do
	3:	subjectArray = getAxiomSubject(domDocument.axiom[i]);
	4:	propertyArray = getAxiomProperty(domDocument.axiom[i]);
	5:	objectArray = getAxiomObject(domDocument.axiom[i]);
	6:	difficultyVector = getAxiomDifficulty(domDocument.axiom[i]);
	7: while (no_more_axioms)
	/* use voiceXML and JSP to generate the dialog */
	8: for (counter < items.length) do
	9:	<vxml:Prompt> = "auxiliary verb" + propertyArray[i] + " " +
		objectArray[i] + " " + subjectArray[i];
	10:	<vxml:Field> = user_response;
	11:	response[i] = Field.voiceRecognition(user_response);
	12:	if response[i] = "yes" or "true"
	13: answerVector[i] = 1;
	14:	else
	15:	answerVector[i] = 0;
	/* contextual reasoning */
	16:	Reasoner.Query([subject][object][property], contextOntology);
	17: endfor;
	18: theta = IRT_Algorithm(difficultyVector, answerVector,
		aprioritheta);
	19: if theta > thetaThreshold
	20:	permit;
	21: else
	22:	deny;
		Figure 6. Ontology-IVR algorithm with IRT and context.

Table 2 .

 2 Synthetic homeland security ontology statistics.

		HS 100	HS 1k	HS 5k	HS 10K HS 50K
	No. Students	0.1K	1K	5K	10K	50K
	No. Axioms	2.5K	23K	0.1M	0.2M	1.1M
	(approx.)
		HS 75K HS 100K HS 200K HS 250K
	No. Students	75K	100K	200K	250K
	No. Axioms	1.7M	2.2M	4.6M	5.7M
	(approx.)

Table 3 .

 3 SPARQL query execution results.

	Query	HS 100 HS 1k HS 5k HS 10K HS 50K HS 75K HS 100K
	Query15	21	21	44	27	30	29	27
	Query16	0	0	9	7	16	2	3
	Query17	21	21	53	34	46	31	30
	Query18	835	3,018	24,535	239,566 1,199,949	NA	NA

Table 3

 3 shows the SPARQL query execution results after each successful execution. Note that Query18 100 is not included in the table because the

Table 4 .

 4 SPARQL query execution time (milliseconds).

	Query	HS 100 HS 1k HS 5k HS 10K HS 50K HS 75K HS 100K
	Query15	8	7	13	9	9	10	10
	Query16	6	3	8	7	6	7	8
	Query17	9	7	10	9	10	9	8
	Query18	66	142	1,353	12,133	58,918	NA	NA
	Query18 100	20	19	17	18	21	18	23