Optimization Online


A covering decomposition algorithm for power grid cyber-network segmentation

Emma S. Johnson(esjohn***at***sandia.gov)
Santanu S. Dey(santanu.dey***at***isye.gatech.edu)
Jonathan Eckstein(jeckstei***at***business.rutgers.edu)
Cynthia A. Phillips(caphill***at***sandia.gov)
John D. Siirola(jdsiiro***at***sandia.gov)

Abstract: We present a trilevel interdiction model for optimally segmenting the Supervisory Control and Data Acquisition (SCADA) network controlling an electric power grid. In this formulation, we decide how to partition nodes of the SCADA network in order to minimize the shedding of load from a worst-case cyberattack, assuming that the grid operator has the opportunity for recourse mitigating attack damage. The model is unique in that it couples the cyber and physical networks, using the physical operation of the grid to inform the cyber network segmentation decisions. This feature leads to two violations of assumptions made in much of the prior literature on trilevel interdiction: first, the network designer does not have the ability to make any components of the SCADA or physical networks invulnerable to attack. Instead, the designer makes some attacks more expensive for the attacker. Second, it is possible for the network designer (first player) to make certain attacker (second player) solutions infeasible because he can make them exceed the attacker's budget. In this paper, we present a solution procedure for our formulation that is an adaptation of a covering decomposition algorithm for bilevel interdiction. We show through an empirical study on grids with up to 2,000 buses that this is the first method capable of solving the network segmentation model on realistically sized power grids.

Keywords: trilevel optimization; interdiction; defender-attacker-defender; mixed-integer programming; power networks; security

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 12/13/2021
Entry Accepted: 12/13/2021
Entry Last Modified: 12/13/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society