A Trilevel Model for Segmentation of the Power Transmission Grid Cyber Network

Network segmentation of a power grid's communication system is one way to make the grid more resilient to cyber attacks. We develop a novel trilevel programming model to optimally segment a grid communication system, taking into account the actions of an information technology (IT) administrator, attacker, and grid operator. The IT administrator is given an allowance to segment existing networks, and the attacker is given a fixed budget to attack the segmented communication system in an attempt to inflict damage on the grid. Finally, the grid operator is allowed to redispatch the grid after the attack in order to minimize damage. The resulting problem is a trilevel interdiction problem, which we solve by leveraging current research in bilevel branch and bound. We demonstrate the benefits of optimal network segmentation through case studies on the 9-bus WSCC system and the 30-bus IEEE system. These examples illustrate that network segmentation can significantly reduce the threat.


E
Security enclaves B Balancing authority entities x e,r Indicates whether or not enclave e ∈ E(S) communicates with relay r y e,f Indicates whether or not enclave e communicates with enclave f q n,e Indicates whether or not enclave e is in entity n t e,n Indicates whether or not enclave e communicates with entity n (in the tier below) Attacker decisions: z e Indicates whether or not the attacker infiltrates enclave e δ r Indicates whether or not relay r is compromised v k Indicates whether or not line k is operational u d Indicates whether or not the load d is online w g Indicates whether or not generator g is operational T HE electric grid, like many infrastructure systems, historically relied on air-gapped and specialized control networks for security. For convenience and cost savings, grid/utility owners are increasingly integrating traditional information technologies (IT) into their control systems. This shift has increased the attack surface for electric grids and has made them more vulnerable to cyber attacks. This was illustrated in the December 2015 cyber attack against the Ukrainian power grid [1]. According to [2], nation-state actors in particular pose a significant threat to cyber-physical systems and also possess the ability to gather the necessary information in advance of attacks. Criminal organizations, terrorists, hackers, and hackivists may also pose a threat to these systems [3].
Network segmentation is one strategy that has been proposed to improve cyber network security [4]. Dividing networks into small segments and restricting communications between segments can limit the scope of attacks and the attackers' ability to pivot within a network. Several governmental and regulatory agencies have provided guidance that motivates segmentation and offer strategies for implementing it [5], [6], [7], [8]. However, as noted in [9], this guidance tends to provide general design principles and architectures, but not specific recommendations or tools for cyber network designers.
Designing segmentation strategies for cyber-physical systems presents a particularly difficult challenge as it requires consideration of two complex interconnected systems. In an IT setting, segmentation decisions can be made based on business functions and the expected consequences of disruptions to these functions (e.g. interruption to payment systems, loss of customer data). In a grid setting, the cyber and physical layers are connected and distributed over wide areas; coordinated attacks create the potential for consequences that are greater than the sum of their parts. A key recommendation in [3] is the need to "evaluate the potential risk of a coordinated cyberattack on geographically distributed targets." In this paper, we explore the use of optimization to identify strategies for segmenting cyber networks. We use an explicit representation of the cyber and grid network layers to capture the interconnected nature of these systems and the resulting impacts of attacks. We also employ trilevel optimization techniques to capture the adaptive nature of and interactions between cyber defenders, attackers, and infrastructure operators. Finally, given the potential capabilities of the attacker, we assume that the attacker has full knowledge of the system when crafting attacks.

A. Literature Review
Several researchers have previously considered applying optimization to cyber security problems that are related to network segmentation. In [10], a heuristic optimization algorithm is used to place the minimum number of intrusion detection systems (IDS) on the nodes of a cyber network while ensuring that no nodes are more than n hops from the nearest detection system. This heuristic approach is also applied by [11] to place trust systems on the smart grid cyber network.
In [12], trust system placement is combined with network segmentation. A mixed-integer linear program (MILP) is used to partition a power system supervisory control and data acquisition (SCADA) network into a collection of enclaves such that a trust node is placed on at least one end of all arcs connecting different enclaves. This ensures that all communications between segments are scanned. The authors also develop a heuristic algorithm for partitioning and placing trust nodes on larger networks.
In [9], simulated annealing is used to identify segmentation strategies for a computer network in an air operations center that supports 40 military missions. An emulation test bed is used to simulate the performance of each segmentation strategy against a "dumb" worm attack that propagates in a manner similar to a disease in a Susceptible-Exposed-Infectious-Recovered (SEIR) model. The quality of each segmentation strategy is based on mission delay and the availability of devices on the network. In [13], this approach is extended to an algorithm that co-evolves the parameters available to the attacker and defender in order to optimize both of their strategies. The attacker still employs a "dumb" worm attack and cannot control how it propagates, but they tune the intensity of the attack to balance the number of components compromised against the probability of detection.
In [14], a heuristic method that uses minimum spanning trees is used to improve performance and scalability for the trust node placement problem on smart grid SCADA systems. Variants of this model are considered in [15] and [16]. These variants account for node centrality and communication latency when deciding where to place trust nodes. In [17], this approach is further expanded to consider both link coverage (the number of links adjacent to a trust node) and path tolerance (the longest path not passing through a trust node) when making placement decisions.
In all of the previously mentioned references that focus on cyber-physical security, only the cyber network is considered, while effects on the underlying physical system it controls are not modeled. There are several examples where segmentation decisions are made based on the underlying physical system managed by the cyber network. In [18], an emulation test bed is used to compare two segmentation strategies developed by subject matter experts (SME's) for SCADA systems in a chemical plant. They demonstrate that in process-flow operations, security and safety gains can be made by separating SCADA devices for in-flow and outflow values. This approach is extended in [19] to include an SME-informed heuristic approach that creates segmentation strategies to separate control of in-flows and out-flows. In [20], network segmentation is used to prevent domino effects in storage tank facilities (e.g. chained explosions of nearby tanks) by an attacker who can attack at most one segment. Belief networks are used to estimate the probability of chained reactions and a graph centrality measure is used to find the segmentation strategy. These works use testbeds to study the effects of network segmentation on the underlying physical system. However, they do not use optimization to make their network segmentation decisions.
Prior research has used bilevel programming to consider the effects on the power grid from an intentional attack, though these model only the physical grid, not the cyber communication system. For example, [21] and [22] formulate and solve a bilevel program that models an attacker with perfect knowledge of the grid and the response of a grid operator. The attacker directly de-energizes power grid components such as transmission lines and generators. The grid operator then responds through generator redispatch and load shed to minimize unmet demand. This attacker-defender model is adapted for a cyber attacker in [23], though still without modeling the cyber network explicitly.
Finally, several authors have employed trilevel programming to preemptively protect the power grid against malicious attacks in [24], [25], [26], and [27]. These works focus on hardening power grid components such as transmission lines, generators, and buses against optimal physical attacks on the grid. However, they do not consider the grid's communication system in modeling these attacks.

B. Contributions and Paper Organization
In this work, we propose segmenting the grid's communication network optimally by explicitly modeling both the cyber network and the physical network. Specifically, we use trilevel optimization to model the interconnected decisions made by an IT administrator segmenting a grid's communication network, a cyber attacker maliciously trying to damage the grid by attacking the segmented network, and a grid operator mitigating damage from the attack. The main contributions of this paper are: • The formulation of a trilevel programming model to identify provably optimal segmentation strategies for a power transmission cyber-physical system which reduce the severity of the worst attack available to a malicious cyber attacker. • The use of an infrastructure model (i.e., a DC optimal power flow (DCOPF) grid model) to inform network segmentation decisions. • A description of how to reformulate the trilevel model as a bilevel program, which can be solved using algorithms from the literature (e.g. bilevel branch-and-bound). • A case study showing network segmentation results for both the 9-bus WSCC and 30-bus IEEE test cases, where segmentation reduces the severity of the worst-case attack by 31% and 56%, respectively. In the remainder of the paper, Sections II and III give a description of the model. Section IV details our solution methodology. Section V presents our case studies on the 9bus and 30-bus IEEE systems. We conclude in Sections VI and VII with ideas for future work and conclusions.

II. CYBER-PHYSICAL NETWORK SEGMENTATION MODEL
We first describe the trilevel network segmentation model at a high level. We give the mathematical formulation in the next section. When we talk about the cyber-physical system, we draw a distinction between entities, the bodies which control the grid, enclaves, the networks that make up an entity's IT infrastructure, and physical components such as the lines, generators, and loads on the physical grid. While our model is more general, in this paper we consider three types of entities: balancing authorities, control centers, and substations.

A. Modeling the Communication Network
For a description of how a power transmission grid communication system network is structured, we refer the reader to [28]. We simplify the communication network to a 3-tier forest where each substation enclave, control center enclave, and balancing authority enclave is represented as a node, and parent-child relationships represent that the parent enclave communicates with the child enclave (i.e., data flows between the parent and child enclave). Every substation enclave is the child of exactly one control center enclave. In turn, every control center enclave is the child of exactly one balancing authority enclave. We show an example of the forest representation of the 9-bus WSCC test system communication network in Fig. 1a. In this example, every entity has only one enclave. The balancing authority enclave communicates with two different control center enclaves. The first of these communicates with three substation enclaves, and the second with six substation enclaves.
The physical power grid is connected to its communication system through relays, which are drawn as the leaves of the tree in Fig. 1a. Individual relays are controlled by exactly one substation enclave and can be used by an attacker to deenergize transmission lines, generators, and loads. In Fig. 1c, each shaded block of grid components is colored to indicate which control center enclave from Fig. 1a ultimately controls it.

B. Modeling Network Segmentation
In the outermost problem of the trilevel model, we model the decisions of an IT administrator segmenting the network in order to minimize the load shed from a worst-case cyber attack. We model network segmentation by allowing the IT administrator to partition any security enclave into two or more security enclaves while still respecting the underlying control structure among the entities. By only subdividing existing assignments, we aim to generate new segmentation strategies that are compatible with the original topology. In the graph representation, segmentation corresponds to expanding the graph by dividing nodes. If a node is divided, the new subnetwork must be assigned to the same entity as the original node. For example, if a substation enclave is divided, both new enclaves are subnetworks of the same substation entity. Edges are added to the expanded graph according to the following rules: 1) A new enclave may only communicate with (i.e., be a child of) a parent enclave if the entities containing the new enclave and the parent enclave communicated in the original graph. As an example, a substation enclave may only communicate with a control center enclave if the corresponding substation and control center originally communicated before segmentation.
(a) The 9-bus system communication network before segmentation: Arcs indicate that the parent component communicates with the child component. The balancing authority, control center, and substation enclaves comprise the communication system, and its control over the relays is shown as the leaves of the tree. (Note that in this example, we include fewer relays than in the 9-bus system used in the case study in Section V-B.) (b) The 9-bus system communication network after segmentation. The balancing authority enclave has been subdivided into two enclaves, each of which communicates with one of the control centers. The contol centers also have two enclaves each, as does Substation 4.  2) After partitioning a substation enclave, that substation's relays must be reassigned so that each relay is controlled by exactly one of the new substation enclaves. The result of this partitioning is that a substation's grid connections are separated by the substation's enclaves, making that substation less vulnerable overall. 3) Every substation enclave must communicate with at least one relay.
Continuing our example, see Fig. 1b for a possible segmentation of the 9-bus network. We see that, after network segmentation, the balancing authority has two enclaves, one for each control center. Both control centers gain a new enclave.
For each control center, the substations it originally controlled are divided between its two new enclaves. Finally, Substation 4 is segmented into two enclaves, each communicating with a separate enclave within Control Center 2. Note that each of the two relays controlled by Substation 4 is assigned to a different enclave. The corresponding diagram of the physical grid is shown in Fig. 1d.

C. Attacker-Defender Model
In the inner two problems of the trilevel model, we model a cyber attacker who finds the highest-load-shed attack on the segmented network given that the grid operator can redispatch after their attack in order to minimize load shed. We assume that attacks begin by infiltrating balancing authority enclaves, then progress by gaining access to the control center enclaves followed by substation enclaves, until the attack reaches the relays, where it can produce an effect on the grid. At each step, the attacker can never infiltrate a node in the graph without first infiltrating its parent. We assume the attacker has an upper limit on the number of enclaves that can be compromised, and every time the attacker gains access to a security enclave, exactly one unit of this budget is consumed. In other words, one unit of budget is used for every node in the graph the attacker reaches. When the attacker gains access to a substation enclave, we assume that the attacker will use all relays controlled by that substation enclave to de-energize every accessible grid component. To gain some intuition about the benefits of network segmentation, note for example that originally in Fig. 1, an attacker would need to access three enclaves to gain control of the two relays controlled by Substation 4. After segmentation, the attacker would need to access five enclaves to gain control of the same relays.
Finally, given an attack, the grid operator solves a DCOPF on the remaining components to minimize total load shed.

III. TRILEVEL FORMULATION
We now give a mathematical formulation of the problem described in Section II. Because many constraints involving (parent, child) entity pairs hold at multiple levels -both (balancing authority, control center) and (control center, substation) -we use the set T to denote the set of all three communication network entities and the set Z = {(B, C), (C, S)} to denote adjacent tiers of entities. The trilevel model is: where D is the feasible region of the network designer, A(x, y) is the feasible region of the attacker, given the design decisions x and y, and O(u, v, w) is the DCOPF feasible region given the attack defined by u, v, and w. We model D with the following constraints: q s,e ≤ r∈Rs x e,r , ∀s ∈ S, e ∈ E 1 (S) q s,e ≥ x e,r , ∀s ∈ S, r ∈ R s , e ∈ E 1 (S) Q s,e ≤ r∈Rs x e,r , ∀s ∈ S, e ∈ E 0 (S) Q s,e ≥ x e,r , ∀s ∈ S, r ∈ R s , e ∈ E 0 (S)

e∈E(A)
y e,f = 1, n∈T q n,e = 1, ∀T ∈ T , e ∈ E 1 (T ) y e,f q n,f , t e,n ≥ y e,f Q n,f , t e,n ≥ y e,f q n,f , ∀(A, B) ∈ Z, e ∈ E(A), t e,n ≤ Q m,e , ∀(A, B) ∈ Z, e ∈ E 0 (A), t e,n ≤ q m,e , ∀(A, B) ∈ Z, e ∈ E 1 (A), y e,f ∈ {0, 1}, ∀(e, f ) ∈ (E(C) × E(S)) ∪ (E(B) × E(C)) (15) x e,r ∈ {0, 1}, e ∈ E(S), ∀r ∈ R t e,n ∈ {0, 1}, ∀(e, n) ∈ (E(C) × S) ∪ (E(B) × C) (18) In (2), we require that every substation enclave controls at least one relay, and in (3) we enforce that every relay is controlled by exactly one substation enclave. Referring back to the graph in Fig. 1, the x r,e variables represent whether or not there is an arc from enclave e in the substation tier to relay r. Constraints (4)-(7) enforce that an enclave e is assigned to a substation if and only if some relay controlled by that substation is controlled via e.
In (8), we require that, between any two adjacent tiers, every enclave in the tier below is controlled by exactly one enclave in the tier above. Since y e,f determines whether or not there is an arc from enclave e to enclave f , these constraints enforce that substation enclaves and control center enclaves have exactly one parent.
Constraints (9) guarantee that, for each of the tiers of the communication network, every new enclave is assigned to exactly one entity (substation, control center, or balancing authority depending on the tier). Constraints (10)-(12) enforce that enclave e communicates with entity n in the layer below e if and only if entity n has an enclave f that communicates with e. Returning to the graphs in Fig. 1, t e,n is an indicator of whether enclave e is a parent of some enclave assigned to entity n. Constraints (13)- (14) enforce that if enclave e communicates with entity n in the network layer below it, then e must be assigned to an entity m which controls n. Note that B m is an instance of the set T n with T = B and n = m. Finally, (15)- (18) give variable domains.
Note that (10) and (12) contain bilinear terms. Since all variables in these products are binaries, they can be reformulated linearly with the introduction of one new binary variable per bilinear term. That is, we introduce β e,f,n ∈ {0, 1} for all (A, B) ∈ Z, e ∈ E(A), f ∈ E 1 (B), n ∈ B and the constraints β e,f,n ≤ y e,f , ∀(A, B) ∈ Z, e ∈ E(A), β e,f,n ≤ q n,f , ∀(A, B) ∈ Z, e ∈ E(A), β e,f,n ≥ y e,f + q n,f − 1, ∀(A, B) ∈ Z, e ∈ E(A), and replace the y e,f q n,f terms in (10) and (12) with β e,f,n For fixed network design decisions x and y, A(x, y) is defined by: x e,r z e , ∀r ∈ R Constraint (22) enforces the attacker's budget. Constraint (23) requires that the attacker can only access enclaves which are controlled by already-accessed enclaves. That is, with respect to the graphs in Fig. 1, the attack must begin at a balancing authority enclave, and no child can be accessed if its parent was not. Constraint (24) enforces that a relay is compromised when the enclave that controls it has been accessed by the attacker. Constraints (23) and (24) contain bilinear terms that can be linearized using the same technique that linearizes (10) and (12).

Constraints (25)-(26) enforce that the line k is opened if and only if some relay that controls it is compromised. Constraints (27)-(30) do the same for generators and loads.
Finally, given the attack decision, we define O(u, v, w), the operator's DCOPF feasible region: Equation (31) enforces flow balance at each substation, while the line power flow approximation is enforced in (32). We linearize (32) by replacing it with: Constraints (33) and (34) enforce thermal limits and maximum generation capacity, forcing flow or generation to 0 if the component is compromised. Note that we can drop (33) after adding (39). Also note that in (34), we assume the minimum generation capacity for all generators is 0. While this is not accurate, it is necessary in order to make (31)-(36) feasible for all possible values of u, v, and w, the importance of which we describe in Section IV. In (35), we upper bound load shed by the total load and require that we shed all compromised loads. Bounds on the phase angles are enforced in (36).

IV. SOLUTION METHODOLOGY
Because the grid operator's problem is linear and has an objective opposite the attacker's objective, we can take its dual and linearize the bilinearities that appear in the dual objective function in order to reformulate the inner two levels as one mixed integer linear program (MILP). For details on this procedure, see [22]. Note that the linearization requires upper bounds on the dual variables. The authors of [29] show that verifying the correctness of these dual bounds is as hard as solving the original bilevel problem. Thus, we adopt the heuristic commonly used in prior literature, which is to assume that the duals are bounded above by the power capacity of the component corresponding to their index [21]. After this reformulation, where we take the dual of the linear program which minimizes d∈L l d over the set {(θ, f, p, l) : (31), (34)-(36), (37)-(39)} and combine the resulting maximization problem with the attacker problem, we have a bilevel problem with integer leader and mixed integer follower: where X = (δ, z, u, v, w, f, p, d, θ, µ, ξ + , ξ − , and A D (x, y) is defined by: where µ is the dual of the balance constraint (31), ξ − and ξ + are the duals of (37) and (38) respectively, λ + and λ − are the duals of (33), γ is the dual of the upper bound in (34), α + and α − are the duals of (35), and β + and β − are the duals of (36 where we are assuming that α + d is bounded above by the total demand at load d. Note that for every outer-problem solution (x, y, q, t, β) ∈ D, problem (40) has a finite objective value. That is, A D (x, y) = ∅. This is because, regardless of the network segmentation and the attack, it is always possible to prevent infeasibility by shedding load or turning off generators. We refer to this property as relatively complete recourse. Note that it is because the generator dispatch lower bounds are 0 that we have this property.
Problem (40) is a mixed-integer bilevel model, which we solve using the bilevel branch and bound algorithm from [30]. In [31], [32], and [30], callbacks within the IBM CPLEX solver [33] are used to create a bilevel branch-and-cut solver. The authors make their software available for academic use at [34]. To easily generate the required MPS file for the bilevel branch and bound solver, we formulated our model with Pyomo [35] and [36].

A. An Equivalent Solution Methodology
We found that, when solving (40) with the solver from [34], the solver could not close the gap within a time limit of 72 hours. We suspect this may be a symptom of numerical issues in the cuts. To overcome this, we solved a slightly modified problem, in which the variable β and the constraints it appears in are moved to the inner problem of (40). Formally, the formulation is as follows: Note that, in (49), we have lost the relatively complete recourse property: Fixing the outer level problem's choice of y and q, it is possible to choose β in order to make one or more of (19)- (21) infeasible. However, because the solver from [34] uses the high-point relaxation of (49) to get a lower bound, it assumes the outer problem will not choose to make the inner problem infeasible. That is, we are actually solving the problem: where Essentially, there is an implicit constraint added to the outer problem that its solution is in the projection of the inner problem's feasible region onto the outer problem variables. We therefore show that (50) is equivalent to (40). We first show that the optimal objective value of (50) is a lower bound to that of (40). Note first that P equals the projection of D onto the (x, y, q, t) variables. This follows from the relatively complete recourse property of (40). We can rewrite P as Next, note that the projection of A D (x, y, q) onto the space of the X variables is a restriction of A D (x, y) (since constraints (19)- (21) have been moved to the inner problem). Since, in projected space, we have an equivalent outer problem region and a restricted inner problem region, we have a lower bound. Next, we show that this bound is achieved. To see this, consider a solution (x, y, q, t, β, X) to (50). Then, by our argument above, (x, y, q, t, β) ∈ D, and by the definition of A D (x, y, q), X ∈ A D (x, y). Thus, this solution is feasible in (40). This completes the argument: When using the branch and bound solver from [34] to solve (49), we are solving (40) exactly.

V. RESULTS
We present a case study on the 9-bus WSCC and 30-bus IEEE systems [37] using the methodology given in Section IV-A. Note that, as we have formulated the network segmentation problem, the network designer is forced to use their entire budget, regardless of if every enclave in the budget is necessary to reduce that load shed the attacker can cause. While it would be possible to reformulate the problem to avoid this, it would be necessary to use the network designer's objective to motivate them to be frugal with their budget. This is no longer an interdiction problem, and is in essence a multiobjective variant. For simplicity, we leave this as future work, and instead suggest solving the proposed model for a variety of network designer budgets in order to find a minimal one which achieves a satisfactory reduction in load shed. We will show an example of this process for the 9-bus system.

A. Hardware and Software Specification
We ran our experiments on a Linux server with two Intel® Xeon® Silver 4210 CPU @ 2.20GHz processors and 256 GB RAM. For the CPLEX-based solver from [34], we used CPLEX 12.9.0 with two threads.

B. 9-bus WSCC System
To create intuitive results that are easy to validate, we first use the 3-generator 9-bus WSCC test system [37]. We use a simple communication network consisting of a single balancing authority and two control centers. The three substations with generators are assigned to one control center and the remaining six substations are assigned to the other control center. There is exactly one security enclave at each substation and each grid component at that substation is controlled through a relay hosted by its substation's security enclave. See Fig. 2a for a depiction of this cyber-physical system before segmentation. Note that this starting topology does not correspond exactly to the communication network we showed in Fig. 1. In Fig. 1, we reduced the number of relays in the system for the sake of readability.
We do two case studies on this network: The first defends against an attacker with a budget of 5 and the second defends against an attacker with a budget of 8. We begin with the case where the budget is 5. Before network segmentation, the attacker can cause a complete blackout by pivoting from (a) The 9-bus system before segmentation. The worst-case attack with budget 5 is marked with a skull-and-crossbones on each enclave and component which is compromised. The attacker infiltrates the Balancing Authority enclave, the Control Center 2 enclave, and the three substation enclaves whose relays control the loads and lines at Buses 5, 6, and 8.
(b) The 9-bus system after segmentation, where the network designer was allowed a budget of two control center enclaves and the attacker had a budget of five enclaves. After segmentation, the attacker spends three units of budgets to infiltrate the balancing authority enclave and both the Control Center 2 enclaves. They only have two units of budget remaining, so they infiltrate buses 4 and 7, which islands the two largest generators, resulting in 225 MW of load shed. Note that the attack on the second yellow Control Center 2 enclave does not cause any load shed; it only allows the attacker to use the full attack budget.  the balancing authority, through the second control center, to Substations 5, 6, and 8. These substations contain all of the system's load of 315 MW. See Fig. 2a for a visualization of this attack. Note that the attacker has multiple optimal solutions: For example, they could alternatively pivot from the balancing authority to Control Center 1, and then compromise Substations 1, 2, and 3. This allows them to shut down all the generators, also resulting in 315 MW of load shed.
In Table I, we present results on a partial parameter sweep of network designer budgets for this problem. We see that two enclaves at either the balancing authority or control center level are necessary to prevent any load shed. Furthermore, two enclaves at the balancing authority level prevent 35 MW more load shed than two enclaves at the control center level. Figure 2b displays the optimal network segmentation for a budget of two control center enclaves. The model segments both the control center networks into two enclaves, and reallocates the substations so that it is no longer possible to compromise all three generators or all three loads. After network segmentation, one worst-case attack infiltrates both enclaves in Control Center 2. The attacker can then only access two substations. They choose Substations 4 and 7 to cause a load shed of 225 MW, reducing the load shed possible in the unsegmented network by 28.6%. Note that the attack on the solid yellow right enclave of Control Center 2 is unnecessary. However, due to the segmentation, there is nothing productive for the attacker to do with this last unit of budget.
In the second case study, we decide an optimal network segmentation to protect against an attacker with a budget of 8 enclaves. Clearly, since the attacker with budget 5 was able to shed all the load (see Figure 2a), in the unsegmented case with budget 8, the attacker sheds 315 MW of load also. Using a process similar to what we showed in Table I, we select a network designer budget of two balancing authority enclaves and four control center enclaves. The resulting segmentation is visualized in Fig. 3. The balancing authority is divided into three enclaves, each of which communicates with two control center enclaves. No load bus or generator bus is on the same control center enclave, so, to remove all the loads or all the generators, the attacker would need to spend three units of budget at the substation level and three at the control center level. However, this leaves them only two at the balancing authority level. Because each balancing authority enclave is mapped to one Control Center 1 enclave and one Control Center 2 enclave, they would need nine or more units of budget to attack enough enclaves to cause a complete blackout. Thus, they cannot shed all the load, and 90 MW (the smallest load) is served. Again, network segmentation reduced the load shed by 28.6%. Note in the attack shown in Fig. 3, the attacker wastes two units of budget: Similarly to the budget-5 case, the attacks on the blue balancing authority enclave and the purple control center enclaves are unproductive, but they cannot be reassigned so that the attack increases the load shed.
Both of these examples illustrate that optimal network segmentation isolates the most critical infrastructure in a way that drastically reduces the damage caused by the worst-case attack.

C. 30-bus System
The 30-bus IEEE system provides a larger example with a more complex topology. For this system, we use the voltage levels to create a fictitious communication network. All highvoltage grid components communicate with a single control center and balancing authority. The lower-voltage grid components are split between two control centers. Both these control centers communicate with a second balancing authority. This network is depicted in Fig. 4a. Balancing Authority 1 and Control Center 1 control the high-voltage grid components, and the remaining two control centers and Balancing Authority 2 control the low-voltage components.
In this case study, we consider an attack budget of six enclaves. We again search the results for a range of network designer budgets, trying to find a minimal one with satisfactory reduction of load shed. We present results where we allow two extra balancing authority enclaves, one extra control center enclave, and one extra substation enclave. Our model segments both balancing authorities into two security enclaves each and divides Control Center 1 into two enclaves. Because substations controlled by Control Center 1 have the largest loads and generation, the model assigns substations to the two enclaves in Control Center 1 so that the largest loads communicate with only one control center enclave. Control Centers 2 and 3 are each assigned to their own enclave in Balancing Authority 2. Finally, the substation enclave is used (a) The 30-bus system before segmentation: The network is controlled by two balancing authorities and 3 control centers, each with only one security enclave. The worst-case attack with budget 6 compromises Balancing Authority 1, Control Center 1, and four substation enclaves controlling buses Blaine, Claytor, Kumis, and Reusens.
(b) The 30-bus system after segmentation: Balancing Authority 1 and Control Center 1 have two enclaves each, meaning the attacker would require 4 units of budget to gain access to the same substations. In lieu of this, they attack only the green control center enclave, compromising Blaine, Fieldale, and Reusens. While it is possible for them to also attack Glen Lyn or Cloverdl, the resulting load shed is not higher. Before network segmentation, the attacker can cause a load shed of 119.2 MW, or 63.1% of the total load, by pivoting from the first balancing authority, through its control center, to substations Kumis, Claytor, Blaine, and Reusens. See Fig. 4a. After network segmentation, the worst-case attack uses two units of budget to give the attacker access to the substations controlled by the green control center enclave. This allows them to attack substations Blaine, Fieldale, and Reusens, causing a total load shed of 52.8 MW, or 27.9% of the total demand. This means that network segmentation reduced the worst-case load shed by 55.7%. See Fig 4b for a depiction. Note that the attack on the blue balancing authority enclave is wasted. In fact, the attack on Fieldale is also not necessary: All of the load shed stems from directly compromising the loads at Blaine and Reusens, and the generators at Glen Lyn and Fieldale are not necessary for serving the remaining load.
This case study illustrates an intuitive network segmentation strategy. The largest loads are connected to substations Blaine and Reusens, so an attacker will expend all resources to infiltrate those substations. However, this network segmentation strategy ensures that the attacker will not be able to shed any further load. While it may seem intuitive to put Blaine and Reusens on separate control center enclaves, note that the attacker still has enough budget to access both, expending four units of budget to attack both Balancing Authority 1 enclaves and both Control Center 1 enclaves, then using the remaining two units to attack Blaine and Reusens. The segmentation therefore limits the attacker's ability to compromise additional enclaves.
Finally, we note that the segmentation of Balancing Authority 2 and of the Hancock substation are indeed necessary in this example. Without segmenting Balancing Authority 2, there is an attack on 6 enclaves which sheds 104.7 MW of load by compromising the Balancing Authority 2 enclave, the enclaves in Control Centers 1 and 2, the Roanoke substation with the 6 MW load, and the Cloverdl substation under Control Center 3. By segmenting Balancing Authority 2, this attack is prevented since it takes an additional unit of budget to gain access to both control centers. With only this segmentation and not the extra substation enclave at Hancock, there still exists an attack which shed 53 MW of load, targeting the yellow Balancing Authority 2 enclave, Control Center 2, the Hancock substation with the 11 MW load, Bus 15, Bus 17, and Bus 20. Including the new Hancock substation enclave, the worst attack on the low-voltage side of the network is reduced to 51.7 MW, compromising the red Balancing Authority 2 enclave, Control Center 3, the Roanoke substation with the 6 MW load, Bus 23, and the accessible Cloverdl substation.
This case study shows that even moderate budgets of additional enclaves can greatly decrease the possible load shed achievable by a cyber attacker, in this case reducing it by more than half.
VI. FUTURE WORK The network segmentation model we develop can be improved and extended in several ways. More details from the communication network presented in [28] can be included to result in a more realistic network. The attacker model can be made more realistic by adding more complex movement throughout the network, using enclave access fees based on real data, and adding context to the attacker's budget. For example, an IT administrator could perform analysis to determine the maximum number of enclaves that could likely be comprised before the IDS systems on the network would generate an alert, and use that as the basis for making segmentation decisions. We use the simplest grid operator model available. Future work can focus on using a higher-fidelity power flow model and allowing grid operator transmission switching. In addition, solution strategies that would allow solving the model on realistically-sized networks would be of interest.
VII. CONCLUSION Segmentation is a cyber defense strategy that has been proposed for improving network security. However, specific strategies for optimally implementing these recommendations, while accounting for the underlying system being protected, are lacking. To address this, we develop a trilevel cyber-physical power-transmission-system networksegmentation model that is the first of its kind. It models an IT administrator who must decide how to preemptively segment the power transmission system communication network in preparation for an attacker with perfect information of the whole system. We use an attacker model where a malicious actor must move from balancing authorities through control centers to substations in order to disable grid components through relays. The attacker anticipates how the grid operator will use a DCOPF to redispatch the generators after the attack is executed. We reformulate our model to a mixed-integer bilevel problem and use bilevel branch-and-cut to solve it. Finally, we present network segmentation results on the 9bus WSCC and 30-bus IEEE test systems, demonstrating the benefit of optimal network segmentation in terms of reducing the worst-case load shed the attacker can achieve.

VIII. ACKNOWLEDGMENTS
We would like to thank Santanu Dey for his help in showing the correctness of the methodology in Section IV-A.