Search

Ensuring the security of critical infrastructures is crucial for the society's welfare and prosperity. However, these infrastructure networks are inherently vulnerable to both intentional and unintentional threats. In "Network Inspection for Detecting Strategic Attacks," Dahan, Sela, and Amin study a strategic network inspection problem, formulated as a large-scale bilevel optimization problem, in which a utility seeks to determine an inspection strategy with minimum number of smart detectors that ensures a desirable expected detection performance under worst-case attacks. The authors derive structural properties of optimal solutions and show that the problem can be solved using Nash equilibria of a large-scale zero-sum game. Their analysis leads to a computationally tractable and operationally feasible solution approach with theoretical guarantees based on combinatorial objects that capture the nature of equilibrium inspection and attack strategies. Their computational study indicates that utilities can achieve a high level of protection in large-scale networks by strategically positioning a small number of detectors. This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem (P) as a large-scale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ensures a target expected detection rate under worst-case attacks. We show that optimal solutions of (P) can be obtained from the equilibria of a large-scale zero-sum game. Our equilibrium analysis involves both game-theoretic and combinatorial arguments and leads to a computationally tractable approach to solve (P). First, we construct an approximate solution by using solutions of minimum set cover (MSC) and maximum set packing (MSP) problems and evaluate its detection performance. In fact, this construction generalizes some of the known results in network security games. Second, we leverage properties of the optimal detection rate to iteratively refine our MSC/MSP-based solution through a column generation procedure. Computational results on benchmark water networks demonstrate the scalability, performance, and operational feasibility of our approach. The results indicate that utilities can achieve a high level of protection in large-scale networks by strategically positioning a small number of detectors. [ABSTRACT FROM AUTHOR]

This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset's elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence problem is relevant for the equilibrium characterization of a generic strategic interdiction game on a capacitated flow network. The game involves a routing entity that sends its flow through the network while facing path transportation costs and an interdictor who simultaneously interdicts one or more edges while facing edge interdiction costs. Using our existence result on posets and strict complementary slackness in linear programming, we show that the Nash equilibria of this game can be fully described using primal and dual solutions of a minimum-cost circulation problem. Our analysis provides a new characterization of the critical components in the interdiction game. It also leads to a polynomial-time approach for equilibrium computation. [ABSTRACT FROM AUTHOR]

Over the years, travelers are increasingly relying on navigation services to inform their route choices and save time. How much value—in terms of saved time—can these services indeed provide to their users? The answer is not as simple as one may think because the value of traffic information not only depends on its accuracy, but also on how widely it is shared among travelers. For instance, information on an incident has the highest value for a traveler when the traveler is the only person who knows about it and takes a detour. However, this information becomes less valuable when it is shared with more travelers, who may take the same detour and cause congestion. Our work uses a game-theoretic approach to analyze how the relative value of information provided by different navigation services changes with their market share and how travelers may choose from different available services. We study a routing game in an environment with multiple heterogeneous information systems and an uncertain state that affects edge costs of a congested network. Each information system sends a noisy signal about the state to its subscribed traveler population. Travelers make route choices based on their private beliefs about the state and other populations' signals. The question then arises, "How does the presence of asymmetric and incomplete information affect the travelers' equilibrium route choices and costs?" We develop a systematic approach to characterize the equilibrium structure and determine the effect of population sizes on the relative value of information (i.e., difference in expected traveler costs) between any two populations. This effect can be evaluated using a population-specific size threshold. One population enjoys a strictly positive value of information in comparison with the other if and only if its size is below the corresponding threshold. We also consider the situation when travelers may choose an information system based on its value and characterize the set of equilibrium adoption rates delineating the sizes of subscribed traveler populations. The resulting routing strategies are such that all travelers face an identical expected cost and no traveler has the incentive to change subscriptions. [ABSTRACT FROM AUTHOR]

Large-scale infrastructures are prone to simultaneous faults when struck by a natural or man-made event. The current operating procedure followed by many utilities needs improvement, both in terms of monitoring performance and time to repair. Motivated by the recent technological progress on small Unmanned Aerial Systems (sUAS), we propose a practical framework to integrate the monitoring capabilities of sUAS into standard utility repair operations. A key aspect of our framework is the use of monitoring locations for sUAS-based inspection of failures within a certain spatial zone (called a localization set). This set is defined based on the alerts from fixed sensors or customer calls. The positioning of monitoring locations is subject to several factors such as sUAS platform, network topology, and airspace restrictions. We formulate the problem of minimizing the maximum time to respond to all failures by routing repair vehicles to various localization sets and exploring these sets using sUAS. The formulation admits a natural decomposition into two sub-problems: the sUAS Network Exploration Problem (SNEP); and the Repair Vehicle Routing Problem (RVRP). Standard solvers can be used to solve the RVRP in a scalable manner; however, solving the SNEP for each localization set can be computationally challenging. To address this limitation, we propose a set cover based heuristic to approximately solve the SNEP. We implement the overall framework on a benchmark network. [ABSTRACT FROM AUTHOR]

Mobile data traffic has been steadily rising in the past years. This has generated a significant interest in the deployment of incentive mechanisms to reduce peak-time congestion. Typically, the design of these mechanisms requires information about user demand and sensitivity to prices. Such information is naturally imperfect. In this paper, we propose a fixed-budget rebate mechanism that gives each user a reward proportional to his percentage contribution to the aggregate reduction in peak-time demand. For comparison, we also study a time-of-day pricing mechanism that gives each user a fixed reward per unit reduction of his peak-time demand. To evaluate the two mechanisms, we introduce a game-theoretic model that captures the public good nature of decongestion. For each mechanism, we demonstrate that the socially optimal level of decongestion is achievable for a specific choice of the mechanism's parameter. We then investigate how imperfect information about user demand affects the mechanisms' effectiveness. From our results, the fixed-budget rebate pricing is more robust when the users' sensitivity to congestion is “sufficiently” convex. This feature of the fixed-budget rebate mechanism is attractive for many situations of interest and is driven by its closed-loop property, i.e., the unit reward decreases as the peak-time demand decreases . [ABSTRACT FROM AUTHOR]

This paper investigates the problem of detection and isolation of attacks on a water distribution network comprised of cascaded canal pools. The proposed approach employs a bank of delay-differential observer systems. The observers are based on an analytically approximate model of canal hydrodynamics. Each observer is insensitive to one fault/attack mode and sensitive to other modes. The design of the observers is achieved by using a delay-dependent linear matrix inequality method. The performance of our model-based diagnostic scheme is tested on a class of adversarial scenarios based on a generalized fault/attack model. This model represents both classical sensor-actuator faults and communication network-induced deception attacks. Our particular focus is on stealthy deception attacks in which the attacker's goal is to pilfer water through canal offtakes. Our analysis reveals the benefits of accurate hydrodynamic models in detecting physical faults and cyber attacks to automated canal systems. We also comment on the criticality of sensor measurements for the purpose of detection. Finally, we discuss the knowledge and effort required for a successful deception attack. [ABSTRACT FROM AUTHOR]

This brief aims to perform security threat assessment of networked control systems with regulatory and supervisory control layers. We analyze the performance of a proportional-integral controller (regulatory layer) and a model-based diagnostic scheme (supervisory layer) under a class of deception attacks. We adopt a conservative approach by assuming that the attacker has knowledge of: 1) the system dynamics; 2) the parameters of the diagnostic scheme; and 3) the sensor-control signals. The deception attack presented here can enable remote water pilfering from automated canal systems. We also report a field-operational test attack on the Gignac canal system located in Southern France. [ABSTRACT FROM AUTHOR]

Abstract: This article studies security decisions of identical plant-controller systems, when their security is interdependent due to network induced risks. Each plant is modeled by a discrete-time stochastic linear system, with the systems controlled over a shared communication network. We formulate the problem of security choices of the individual system operators (also called players) as a non-cooperative game. We consider a two-stage game, in which on the first stage the players decide whether to invest in security or not; and on the second stage, they apply control inputs to minimize the average operational costs. We characterize the equilibria of the game, which includes the determination of the individually optimal security levels. Next, we solve the problem of finding the socially optimal security levels. The presence of interdependent security causes a negative externality, and the individual players tend to under invest in security relative to the social optimum. This leads to a gap between the individual and the socially optimal security levels for a wide range of security costs. From our results, regulatory impositions to incentivize higher security investments are desirable. [Copyright &y& Elsevier]

We present a generic yet practical framework for assessing security risks to cyberphysical systems (CPSs). Our framework can be used to benchmark security risks when information is less than perfect, and interdependencies of physical and computational components may result in correlated failures. Such environments are prone to externalities, and can cause huge societal losses. We focus on the risks that arise from interdependent reliability failures (faults) and security failures (attacks). We advocate that a sound assessment of these risks requires explicit modeling of the effects of both technology-based defenses and institutions necessary for supporting them. Thus, we consider technology-based security defenses grounded in information security tools and fault-tolerant control in conjunction with institutional structures. Our game-theoretic approach to estimating security risks facilitates more effective defenses, especially against correlated failures. [ABSTRACT FROM PUBLISHER]