Optimal Software Patching Plan for PMUs

Teklemariam Tesfay, Jean‐Yves Le Boudec, Ola Svensson

Abstract Phasor measurement units (PMUs) deployed to monitor the state of an electrical grid need to be patched from time to time to prevent attacks that exploit vulnerabilities in the software. Applying some of these patches requires a PMU reboot, which takes the PMU offline for some time. If the PMU placement provides enough redundancy, it is possible to patch a set of PMUs at a time while maintaining full system observability. The challenge is then to find a patching plan that guarantees that the patch is rolled out to all PMUs in the smallest number of rounds possible while full system observability is maintained at all times. We show that this problem can be formulated as a sensor patching problem, which we demonstrate to be NP-complete. However, if the grid forms a tree, we show that the minimum number of rounds is two and we provide a polynomial-time algorithm that finds an optimal patching plan. For the non-tree case, we formulate the problem as a binary integer linear programming problem and solve it using an integer linear programming (ILP)-solver. We also propose a heuristic algorithm to find an approximate solution to the patching problem for grids that are too large to be solved by an ILP-solver. Through simulation, we compare the performance of the ILP-solver and the heuristic algorithm over different bus systems.

Introduction

Phasor Measurement Units (PMUs) are critical components of modern power grids, providing high-speed, time-synchronized data essential for real-time state estimation. Like any networked computer system, PMUs run software that may contain vulnerabilities (e.g., the Heartbleed bug), necessitating periodic security patches. However, applying these patches typically requires a device reboot, rendering the PMU temporarily offline.

If a utility were to patch all PMUs simultaneously, the grid would lose observability, effectively going "blind." Conversely, patching devices one by one is inefficient and extends the window of vulnerability, allowing attackers to potentially exploit unpatched devices. The objective is to develop a patching plan that partitions PMUs into the minimum number of rounds such that the grid remains fully observable during every stage of the rollout.

Methodology and Topology Transformation

The authors define this challenge as the Sensor Patching Problem (SPP). A fundamental step in solving SPP involves analyzing and transforming the grid's physical topology to account for redundancy and specific bus types, such as zero-injection buses (buses with no power generation or load).

Grid topology transformation and PMU mapping.

By transforming the original topology into a simplified representation, the researchers can more effectively map PMU locations to the buses they observe. This transformation facilitates the formulation of the problem as a mathematical optimization task, specifically identifying which sets of PMUs can be taken offline without violating observability constraints.

The Two-Round Solution for Tree Networks

For grids that follow a radial or tree-like structure—common in distribution networks—the problem is significantly more manageable. The researchers proved that any tree-structured grid can be patched in exactly two rounds while maintaining full observability, regardless of the network's size.

Iterative coloring process for optimal 2-round patching in tree topologies.

They developed a polynomial-time algorithm that uses an iterative coloring process to partition PMUs. By assigning PMUs to one of two sets (represented by red and blue colors), the algorithm ensures that even when one set is offline for patching, the remaining online set provides sufficient coverage to monitor every bus in the tree.

Scaling to Mesh Grids

In more complex mesh (non-radial) grids, the problem becomes NP-complete, meaning no fast, perfect algorithm exists for all cases. The study employs two distinct strategies for these networks:

  1. Binary Integer Linear Programming (BILP): For small to medium-sized systems, BILP solvers can find the mathematically optimal (minimum) number of rounds. For example, while many systems require only two rounds, the IEEE 57-bus system was found to require at least three.
  2. Greedy Heuristic Algorithm: For massive networks where BILP solvers face computational limits, a greedy heuristic is used. This approach leverages the mathematical property of "submodularity" to find high-quality solutions rapidly.

Experimental Results

The algorithms were tested across various standard models, including IEEE bus systems and a massive 4,941-bus model of the Western US Power Grid.

  • Efficiency: In the IEEE 14-bus system, the ILP solver identified a 2-round plan in 0.014 seconds. The greedy heuristic required 3 rounds but was significantly faster (0.004s).
  • Scalability: The ILP solver could not process the 4,941-bus system due to memory constraints. However, the greedy heuristic successfully partitioned the 3,468 PMUs in this massive network into 4 rounds in approximately 2.1 hours.

Conclusion

This research demonstrates that existing hardware redundancy, typically intended for physical contingency planning, can be repurposed to facilitate rapid cyber-maintenance. By minimizing the number of patching rounds, utilities can significantly reduce the time the grid remains exposed to known software vulnerabilities. Future work may involve adapting these plans for dynamic grid topologies where line switching or other maintenance activities occur simultaneously with the software rollout.

Summary updated

Abstract

Phasor measurement units (PMUs) deployed to monitor the state of an electrical grid need to be patched from time to time to prevent attacks that exploit vulnerabilities in the software. Applying some of these patches requires a PMU reboot, which takes the PMU offline for some time. If the PMU placement provides enough redundancy, it is possible to patch a set of PMUs at a time while maintaining full system observability. The challenge is then to find a patching plan that guarantees that the patch is rolled out to all PMUs in the smallest number of rounds possible while full system observability is maintained at all times. We show that this problem can be formulated as a sensor patching problem, which we demonstrate to be NP-complete. However, if the grid forms a tree, we show that the minimum number of rounds is two and we provide a polynomial-time algorithm that finds an optimal patching plan. For the non-tree case, we formulate the problem as a binary integer linear programming problem and solve it using an integer linear programming (ILP)-solver. We also propose a heuristic algorithm to find an approximate solution to the patching problem for grids that are too large to be solved by an ILP-solver. Through simulation, we compare the performance of the ILP-solver and the heuristic algorithm over different bus systems.
BibTeX
@article{tesfay2017optimal,
  author = {Teklemariam Tesfay and Jean‐Yves Le Boudec and Ola Svensson},
  title = {{Optimal Software Patching Plan for PMUs}},
  journal = {IEEE Transactions on Smart Grid},
  year = {2017},
  doi = {10.1109/tsg.2017.2714204},
}
Figure