## Abstract

Controllability, or informally the ability to force a system

into a desired state in a finite time or number of steps, is a fundamental

problem studied extensively in control systems theory with structural

controllability recently gaining renewed interest. In distributed control

systems, possible control relations are limited by the underlying network

(graph) transmitting the control signals from a single controller or set of

controllers. Attackers may seek to disrupt these relations or compromise

intermediate nodes, thereby gaining partial or total control.

For a defender to re-gain full or partial control, it is therefore critical to

rapidly reconstruct the control graph as far as possible. Failing to achieve

this may allow the attacker to cause further disruptions, and may - as

in the case of electric power networks - also violate real-time constraints

leading to catastrophic loss of control. However, as this problem is known

to be computationally hard, approximations are required particularly

for larger graphs. We therefore propose a reconstruction algorithm for

(directed) control in Erdöos-Rényi random graphs to reduce the averagecase

complexity through partial re-use of PDS based on the formulation

of our recent work presented as an extended abstract

into a desired state in a finite time or number of steps, is a fundamental

problem studied extensively in control systems theory with structural

controllability recently gaining renewed interest. In distributed control

systems, possible control relations are limited by the underlying network

(graph) transmitting the control signals from a single controller or set of

controllers. Attackers may seek to disrupt these relations or compromise

intermediate nodes, thereby gaining partial or total control.

For a defender to re-gain full or partial control, it is therefore critical to

rapidly reconstruct the control graph as far as possible. Failing to achieve

this may allow the attacker to cause further disruptions, and may - as

in the case of electric power networks - also violate real-time constraints

leading to catastrophic loss of control. However, as this problem is known

to be computationally hard, approximations are required particularly

for larger graphs. We therefore propose a reconstruction algorithm for

(directed) control in Erdöos-Rényi random graphs to reduce the averagecase

complexity through partial re-use of PDS based on the formulation

of our recent work presented as an extended abstract

Original language | English |
---|---|

Title of host publication | Proceedings of the 9th International Conference on Critical Information Infrastructures Security (CRITIS 2014) |

Publisher | Springer-Verlag |

Pages | 293-307 |

ISBN (Electronic) | 978-3-319-31664-2 |

ISBN (Print) | 978-3-319-31663-5 |

DOIs | |

Publication status | Published - 2014 |

## Keywords

- Structural Controllability, Power Dominating Sets, Recovery from Attacks