We consider a strategic network monitoring problem involving the operator of a networked system and an attacker. The operator aims to randomize the placement of multiple protected sensors to monitor and protect components that are vulnerable to attacks. We account for the heterogeneity in the components' security levels and formulate a large-scale maximin optimization problem. After analyzing its structure, we propose a three-step approach to approximately solve the problem. First, we solve a generalized covering set problem and run a combinatorial algorithm to compute an approximate solution. Then, we compute approximation bounds by solving a nonlinear set packing problem. To evaluate our solution approach, we implement two classical solution methods based on column generation and multiplicative weights updates, and test them on real-world water distribution and power systems. Our numerical analysis shows that our solution method outperforms the classical methods on large-scale networks, as it efficiently generates solutions that achieve a close to optimal performance and that are simple to implement in practice.

The notion of security index quantifies the least effort involved in conducting perfectly undetectable attacks. Thus, the security index enables a systems operator to assess the vulnerability of a component, informs sensor placement strategies, and helps in deciding the feasibility of secure estimators and fault detectors. In this paper, we investigate the (possible) variation in this index as a consequence of variation in the system parameters. To this end, we adopt a structured systems approach, typically represented by a directed graph, with the edges of the said graph being in one-to-one correspondence with the system parameters. We first show that the security index is generic. That is, for almost all choices of edge weights, the security index of a component remains the same. We refer to such an index as the generic security index. Secondly, we derive graph-theoretic conditions (and based on those an algorithm) for computing the generic security index. Third, we provide graph-theoretic conditions for computing lower (resp. upper) bounds on the values that the security index of a component can take for all nonzero choices of the edge weights of the directed graph. Finally, we provide a brute force search method for calculating the said bounds.

Given a network with a set of vulnerable actuators (and sensors), the security index of an actuator equals the minimum number of sensors and actuators that needs to be compromised so as to conduct a perfectly undetectable attack using the said actuator. This paper deals with the problem of computing actuator security indices for discrete-time LTI network systems, using a structured systems framework. We show that the actuator security index is generic, that is for almost all realizations the actuator security index remains the same. We refer to such an index as generic security index (generic index) of an actuator. Given that the security index quantifies the vulnerability of a network, the generic index is quite valuable for large scale energy systems. Our second contribution is to provide graph-theoretic conditions for computing the generic index. The said conditions are in terms of existence of linkings on appropriately-defined directed (sub)graphs. Based on these conditions, we present an algorithm for computing the generic index.

We propose an actuator security index that can be used to localize and protect vulnerable actuators in a networked control system. Particularly, the security index of an actuator equals to the minimum number of sensors and actuators that need to be compromised, such that a perfectly undetectable attack against that actuator can be conducted. We derive a method for computing the index in small-scale systems and show that the index can potentially be increased by placing additional sensors. The difficulties that appear once the system is of a large-scale are then outlined: The index is NP-hard to compute, sensitive with respect to system variations, and based on the assumption that the attacker knows the entire system model. To overcome these difficulties, a robust security index is introduced. The robust index can characterize actuators vulnerable in any system realization, can be calculated in polynomial time, and can be related to limited model knowledge attackers. Additionally, we analyze two sensor placement problems with the objective to increase the robust indices. We show that the problems have submodular structures, so their suboptimal solutions with performance guarantees can be computed in polynomial time. Finally, we illustrate the theoretical developments through examples.

Risk assessment is an inevitable step in implementation of a cyber-defense strategy. An important part of this assessment is to reason about the impact of possible attacks. In this paper, we study the problem of estimating the impact of cyber-attacks in stochastic linear networked control systems. For the stealthiness constraint, we adopt the Kullback-Leibler divergence between attacked and nonattacked residual sequences. Two impact metrics are considered: the probability that some of the critical states leave a safety region and the expected value of the infinity norm of the critical states. For the first metric, we prove that the optimal value of the impact estimation problem can be calculated by solving a set of convex problems. For the second, we derive efficiency to calculate lower and upper bounds. Finally, we show compatibility of our framework with a number of attack strategies proposed in the literature and demonstrate how it can be used for risk assessment in an example.

Actuator security indices are developed for risk assessment purposes. Particularly, these indices can tell a system operator which of the actuators in a critical infrastructure network are the most vulnerable to cyber-attacks. Once the operator has this information, he/she can focus the security budget to protect these actuators. In this short paper, we first revisit one existing definition of an actuator security index, and then discuss possible directions for future research.

To protect industrial control systems from cyberattacks, multiple layers of security measures need to be allocated to prevent critical security vulnerabilities. However, both finding the critical vulnerabilities and then allocating security measures in a cost‐efficient way become challenging when the number of vulnerabilities and measures is large. This paper proposes a framework that can be used once this is the case. In our framework, the attacker exploits security vulnerabilities to gain control over some of the sensors and actuators. The critical vulnerabilities are those that are not complex to exploit and can lead to a large impact on the physical world through the compromised sensors and actuators. To find these vulnerabilities efficiently, we propose an algorithm that uses the nondecreasing properties of the impact and complexity functions and properties of the security measure allocation problem to speed up the search. Once the critical vulnerabilities are located, the security measure allocation problem reduces to an integer linear program. Since integer linear programs are NP‐hard in general, we reformulate this problem as a problem of minimizing a linear set function subject to a submodular constraint. A polynomial time greedy algorithm can then be applied to obtain a solution with guaranteed approximation bound. The applicability of our framework is demonstrated on a control system used for regulation of temperature within a building.

We consider an attacker-operator game for monitoring a large-scale network that is comprised of components that differ in their criticality levels. In this zero-sum game, the operator seeks to position a limited number of sensors to monitor the network against the attacker who strategically targets a network component. The operator (resp. attacker) seeks to minimize (resp. maximize) the network loss. To study the properties of mixed-strategy Nash Equilibria of this game, we first study two simple instances: When component sets monitored from individual sensor locations are mutually disjoint; When only a single sensor is positioned, but with possibly overlapping monitoring component sets. Our analysis reveals new insights on how criticality levels impact the players equilibrium strategies. Next, we extend a previously developed approach to obtain an approximate Nash equilibrium in the general case. This approach uses solutions to minimum set cover and maximum set packing problems to construct an approximate Nash equilibrium. Finally, we implement a column generation procedure to improve this solution and numerically evaluate the performance of our approach. 

A novel security index based on the definition of perfect undetectability is proposed. The index is a tool that can help a control system operator to localize the most vulnerable actuators in the network. In particular, the security index of actuator i represents the minimal number of sensors and actuators that needs to be compromised in addition to i, such that a perfectly undetectable attack is possible. A method for computing this index for small scale systems is derived, and difficulties with the index once the system is of large scale are outlined. An upper bound for the index that overcomes these difficulties is then proposed. The theoretical developments are illustrated on a numerical example.