## Abstract

The notion of controllability, informally the ability to force a system

into a desired state in a finite time or number of steps, is most closely associated

with control systems such as those used to maintain power networks and

other critical infrastructures, but has wider relevance in distributed systems. It

is clearly highly desirable to understand under which conditions attackers may

be able to disrupt legitimate control, or to force overriding controllability themselves.

Following recent results by Liu et al., there has been considerable interest

also in graph-theoretical interpretation of Kalman controllability originally introduced

by Lin, structural controllability. This permits the identification of sets of

driver nodes with the desired state-forcing property, but determining such nodes

is a W[2]-hard problem. To extract these nodes and represent the control relation,

here we apply the POWER DOMINATING SET problem and investigate the effects

of targeted iterative multiple-vertex removal. We report the impact that different

attack strategies with multiple edge and vertex removal will have, based on underlying

non-complete graphs, with an emphasis on power-law random graphs

with different degree sequences.

into a desired state in a finite time or number of steps, is most closely associated

with control systems such as those used to maintain power networks and

other critical infrastructures, but has wider relevance in distributed systems. It

is clearly highly desirable to understand under which conditions attackers may

be able to disrupt legitimate control, or to force overriding controllability themselves.

Following recent results by Liu et al., there has been considerable interest

also in graph-theoretical interpretation of Kalman controllability originally introduced

by Lin, structural controllability. This permits the identification of sets of

driver nodes with the desired state-forcing property, but determining such nodes

is a W[2]-hard problem. To extract these nodes and represent the control relation,

here we apply the POWER DOMINATING SET problem and investigate the effects

of targeted iterative multiple-vertex removal. We report the impact that different

attack strategies with multiple edge and vertex removal will have, based on underlying

non-complete graphs, with an emphasis on power-law random graphs

with different degree sequences.

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

Title of host publication | Proceedings of the 16th Information Security Conference (ISC 2013) |

Publisher | Springer-Verlag |

Number of pages | 10 |

Publication status | Accepted/In press - 2013 |