Multi-Round Attacks on Structural Controllability Properties for Non-Complete Random Graphs. / Alcaraz, Cristina; Etchevés Miciolino, Estefania; Wolthusen, Stephen D.

Proceedings of the 16th Information Security Conference (ISC 2013). Springer-Verlag, 2013.

Research output: Chapter in Book/Report/Conference proceedingConference contribution



  • Controllability_Attacks

    Rights statement: Copyright held by Springer-Verlag

    Accepted author manuscript, 105 KB, PDF document


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.
Original languageEnglish
Title of host publicationProceedings of the 16th Information Security Conference (ISC 2013)
Number of pages10
Publication statusAccepted/In press - 2013
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 23258891