Controllability under Adversarial Influence in Critical Information Infrastructures

Marie Curie COFUND programme “U-Mobility”. Seventh Framework Programme, Grant Agreement No. 246550
Duration: 01/08/2012 to 31/08/2015

Project Overview: 

CAIN is a research project for the development of a Marie-Curie fellowship. Its goal is to offer the means necessaries to investigate the problem of identifying dynamic subsets of the control network, which can override adversary behaviour whilst minimising the magnitude of control inputs. So far, this topic has been widely studied through complete and partial matching algorithms, where it is required finding the minimum set of driver nodes in charge of controlling the entire network. However, our proposal goes a little further beyond of the matching theory by finding the minimum set of driver nodes through the Power Dominating Set (PDS). It is an alternative to the matching but focused on the structure of electric power networks and its monitoring networks (e.g., SCADA systems).

Based on these studies, our aim has been to analyse the network behaviour under adversarial actions, in which a set of attack models have been designed for non-iterative [1] and multi-interactive [2] scenarios. These analyses have been keys to provide efficient recovery algorithms of "structural controllability" based on the network topology knowledge and the implicit vulnerabilities of the system. We have particularly provided recovery mechanisms both for global and distributed cases, in which graphs (representing networks of the real word and following theoretical models) may be partitioned but at the same time re-established to restore the structural controllability [3][4][5][6].

In order to offer important progresses in the energy and control sector, these studies have been focused on interconnected electrical networks (under specific assumptions and thereotical networks - power-law based distributions) deployed  within Smart Grid systems. 


  1. C. Alcaraz, E. Etcheves Miciolino, and S. Wolthusen, "Structural Controllability of Networks for Non-Interactive Adversarial Vertex Removal",
    8th International Conference on Critical Information Infrastructures Security, vol. 8328, Springer, pp. 120-132, 2013. DOI More..


    The problem of controllability of networks arises in a number of different domains, including in critical infrastructure systems where control must be maintained continuously. Recent work by Liu et al. has renewed interest in the seminal work by Lin on structural controllability, providing a graph-theoretical interpretation. This allows the identification of driver nodes capable of forcing the system into a desired state, which implies an obvious target for attackers wishing to disrupt the network control. Several methods for identifying driver nodes exist, but require undesirable computational complexity. In this paper, we therefore investigate the ability to regain or maintain controllability in the presence of adversaries able to remove vertices and implicit edges of the controllability graph. For this we rely on the POWER DOMINATING SET (PDS) formulation for identifying the control structure and study different attack strategies for multiple network models. As the construction of a PDS for a given graph is not unique, we further investigate different strategies for PDS construction, and provide a simulative evaluation.

  2. C. Alcaraz, E. Etcheves Miciolino, and S. Wolthusen, "Multi-Round Attacks on Structural Controllability Properties for Non-Complete Random Graphs",
    The 16th Information Security Conference (ISC), vol. 7807, Springer, pp. 140–151, 09/2015. DOI More..


     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 aW[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.

  3. C. Alcaraz, and S. Wolthusen, "Recovery of Structural Controllability for Control Systems",
    Eighth IFIP WG 11.10 International Conference on Critical Infrastructure Protection, SRI International, Arlington, Virginia, USA , vol. 441, Springer, pp. 47-63, 2014. DOI More..


    Fundamental problems in control systems theory are controllability and observability, and designing control systems so that these properties are satisfied or approximated sufficiently. However, it is prudent to as- sume that an attacker will not only be able to subvert measurements but also control the system. Moreover, an advanced adversary with an understanding of the control system may seek to take over control of the entire system or parts thereof, or deny the legitimate operator this capability. The effectiveness of such attacks has been demonstrated in previous work. Indeed, these attacks cannot be ruled out given the likely existence of unknown vulnerabilities, increasing connectivity of nominally air-gapped systems and supply chain issues. The ability to rapidly recover control after an attack has been initiated and to detect an adversary’s presence is, therefore, critical. This paper focuses on the problem of structural controllability, which has recently attracted substantial attention through the equivalent problem of the power dom- inating set introduced in the context of electrical power network control. However, these problems are known to be NP-hard with poor approx- imability. Given their relevance to many networks, especially power networks, this paper studies strategies for the efficient restoration of controllability following attacks and attacker-defender interactions in power-law networks. 

  4. C. Alcaraz, and J. Lopez, "A Cyber-Physical Systems-Based Checkpoint Model for Structural Controllability",
    IEEE Systems Journal, vol. 12, issue 4, IEEE, pp. 3543-3554, 12/2018. DOI (I.F.: 4.463)More..


    The protection of critical user-centric applications, such as Smart Grids and their monitoring systems, has become one of the most cutting-edge research areas in recent years. The dynamic complexity of their cyber-physical systems (CPSs) and their strong inter-dependencies with power systems, are bringing about a significant increase in security problems that may be exploited by attackers. These security holes may, for example, trigger the disintegration of the structural controllability properties due to the problem of non-locality, affecting, sooner or later, the provision of the essential services to end-users. One way to address these situations could be through automatic checkpoints in charge of inspecting the healthy status of the control network and its critical nature. This inspection can be subject to special mechanisms composed of trustworthy cyberphysical elements capable of detecting structural changes in the control and activating restoration procedures with support for warning. This is precisely the aim of this paper, which presents a CPSs-based checkpoint model with the capacity to manage heterogeneous replications that help ensure data redundancy, thereby guaranteeing the validity of the checkpoints. As a support to this study, a theoretical and practical analysis is addressed to show the functionality of the approach in real contexts.

    Impact Factor: 4.463
    Journal Citation Reports® Science Edition (Thomson Reuters, 2018)

  5. C. Alcaraz, "Cloud-Assisted Dynamic Resilience for Cyber-Physical Control Systems",
    IEEE Wireless Communications, vol. 25, no. 1, IEEE, pp. 76-82, 02/2018. DOI (I.F.: 11)More..
    Impact Factor: 11
    Journal Citation Reports® Science Edition (Thomson Reuters, 2018)

  6. C. Alcaraz, "Resilient Industrial Control Systems based on Multiple Redundancy",
    International Journal of Critical Infrastructures (IJCIS), vol. 13, no. 2/3, Inderscience Publisher, pp. 278 - 295, 11/2017. DOI More..


    The incessant search for cost-effective recovery solutions for structural controllability has led to one of the most challenging research areas within the field of critical infrastructure protection. The resilience of large heterogeneous distributions, like industrial control scenarios, is proving to be a complicated mission due to the inherent non-locality problems of structural controllability and its susceptibility to advanced threats. To address these issues, this paper proposes a new repair approach based on multiple redundant pathways and the lessons learnt from the work presented in [1]. From [1], we have adapted the local measures, to combine them with each of the five strategies of remote reconnection described in this paper. To validate the sustainability of the combined approaches, two practical case studies are presented here, showing that a local dependence on a brother driver node together with remote dependence is enough to reach optimal states in linear times.