Biblio

An analytical approach for a dynamic cyber-security problem that captures progressive attacks to a computer network is presented. We formulate the dynamic security problem from the defender’s point of view as a supervisory control problem with imperfect information, modeling the computer network’s operation by a discrete event system. We consider a min-max performance criterion and use dynamic programming to determine, within a restricted set of policies, an optimal policy for the defender. We study and interpret the behavior of this optimal policy as we vary certain parameters of the supervisory control problem.

In the restructured electricity industry, electricity pooling markets are an oligopoly with strategic producers possessing private information (private production cost function). We focus on pooling markets where aggregate demand is represented by a non-strategic agent. We consider demand to be elastic. We propose a market mechanism that has the following features. (F1) It is individually rational. (F2) It is budget balanced. (F3) It is price efficient, that is, at equilibrium the price of electricity is equal to the marginal cost of production. (F4) The energy production profile corresponding to every nonzero Nash equilibrium of the game induced by the mechanism is a solution of the corresponding centralized problem where the objective is the maximization of the sum of the producers' and consumers' utilities. We identify some open problems associated with our approach to electricity pooling markets.

Recent high-profile targeted attacks showed that even the most secure and secluded networks can be compromised by motivated and resourceful attackers, and that such a system compromise may not be immediately detected by the system owner. Researchers at RSA proposed the FlipIt game to study the impact of such stealthy takeovers. In the basic FlipIt game, an attacker and a defender fight over a single resource; in practice, however, systems typically consist of multiple resources that can be targeted. In this paper, we present FlipThem, a generalization of FlipIt to multiple resources. To formulate the players' goals and study their best strategies, we introduce two control models: in the AND model, the attacker has to compromise all resources in order to take over the entire system, while in the OR model, she has to compromise only one. Our analytical and numerical results provide practical recommendations for defenders.

The article by Amin, Schwartz, Cárdenas, and Sastry investigates energy theft in smart utility networks using techniques from game theory and detection theory. The game-theoretic model considers pricing and investment decisions by a distribution utility when it serves a population of strategic customers, and a fraction of customers are fraudulent. Each fraudulent customer chooses to steal electricity after accounting for the probability of fraud detection and the amount of fine that they pay if detected. The probabilistic rate of successful detection depends on the distributor's implementation of a diagnostic scheme and increases with level of investment made by the distributor monitoring fraud. The distributor (leader) chooses the level of investment, the price per unit quantity of billed electricity, and the fine schedule. The customers (followers) make their choices after they learn the distributor's decision. For specific assumptions on customer utilities and a distributor's profit function, this leader-follower game is used to compute equilibrium customer and distributor choices. For two environments, namely an unregulated monopoly and the case of perfect competition, the results provide an estimate of the extent of stealing for different levels of investment (high versus low). These results point toward the need for creating regulatory measures to incentivize investments in security and fraud monitoring.

(No abstract.)

Airports are the most resource-constrained components of the air transportation system. This paper addresses the problems of increased flight delays and aircraft fuel consumption through the integrated control of airport arrival and departure operations. Departure operations are modeled using a network abstraction of the airport surface. Published arrival routes to airports are synthesized in order to form a realistic model of arrival airspace. The proposed control framework calculates the optimal times of departure of aircraft from the gates, as a function of the arrival and departure traffic as well as airport characteristics such as taxiway layout and gate capacity. The integrated control formulation is solved using dynamic programming, which allows calculation of policies for real-time implementation. The advantages of the proposed methodology are illustrated using simulations of Boston's Logan International Airport

This paper studies the effects of the diversification of energy portfolios on the merit order effect in an oligopolistic energy market. The merit order effect describes the negative impact of renewable energy, typically supplied at the low marginal cost, to the electricity market. We show when thermal generators have a diverse energy portfolio, meaning that they also control some or all of the renewable supplies, they offset the price declines due to the merit order effect because they strategically reduce their conventional energy supplies when renewable supply is high. In particular, when all renewable supply generates profits for only thermal power generators this offset is complete — meaning that the merit order effect is totally neutralized. As a consequence, diversified energy portfolios may be welfare reducing. These results are robust to the presence of forward contracts and incomplete information (with or without correlated types). We further use our full model with incomplete information to study the volatility of energy prices in the presence of intermittent and uncertain renewable supplies.

We focus on the question of distributed control of electricity distribution networks in the face of security attacks to Distributed Energy Resources (DERs). Our attack model includes strategic manipulation of DER set-points by an external hacker to induce a sudden compromise of a subset of DERs connected to the network. We approach the distributed control design problem in two stages. In the first stage, we model the attacker-defender interaction as a Stackelberg game. The attacker (leader) disconnects a subset of DERs by sending them wrong set-point signals. The distribution utility (follower) response includes Volt-VAR control of non-compromised DERs and load control. The objective of the attacker (resp. defender) is to maximize (resp. minimize) the weighted sum of the total cost due to loss of frequency regulation and the cost due to loss of voltage regulation. In the second stage, we propose a distributed control (defender response) strategy for each local controller such that, if sudden supply-demand mismatch is detected (for example, due to DER compromises), the local controllers automatically respond based on their respective observations of local fluctuations in voltage and frequency. This strategy aims to achieve diversification of DER functions in the sense that each uncompromised DER node either contributes to voltage regulation (by contributing reactive power) or to frequency regulation (by contributing active power). We illustrate the effectiveness of this control strategy on a benchmark network.

This paper considers a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. This game is strategically equivalent to a zero-sum game. Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. In any equilibrium, both players achieve identical payoffs. While the defender's expected transportation cost decreases in attacker's marginal value of lost flow, the attacker's expected cost of attack increases in defender's marginal value of effective flow. Interestingly, the expected amount of effective flow decreases in both these parameters. These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments.

The defense of computer networks from intruders is becoming a problem of great importance as networks and devices become increasingly connected. We develop an automated approach to defending a network against continuous attacks from intruders, using the notion of Bayesian attack graphs to describe how attackers combine and exploit system vulnerabilities in order to gain access and progress through a network. We assume that the attacker follows a probabilistic spreading process on the attack graph and that the defender can only partially observe the attacker’s capabilities at any given time. This leads to the formulation of the defender’s problem as a partially observable Markov decision process (POMDP). We define and compute optimal defender countermeasure policies, which describe the optimal countermeaSure action to deploy given the current information.

The objective of this work is to develop an efficient and practical sensor placement method for the failure detection and localization in water networks. We formulate the problem as the minimum test cover problem (MTC) with the objective of selecting the minimum number of sensors required to uniquely identify and localize pipe failure events. First, we summarize a single-level sensing model and discuss an efficient fast greedy approach for solving the MTC problem. Simulation results on benchmark test networks demonstrate the efficacy of the fast greedy algorithm. Second, we develop a multi-level sensing model that captures additional physical features of the disturbance event, such as the time lapsed between the occurrence of disturbance and its detection by the sensor. Our sensor placement approach using MTC extends to the multi-level sensing model and an improved identification performance is obtained via reduced number of sensors (in comparison to single-level sensing model). In particular, we investigate the bi-level sensing model to illustrate the efficacy of employing multi-level sensors for the identification of failure events. Finally, we suggest extensions of our approach for the deployment of heterogeneous sensors in water networks by exploring the trade-off between cost and performance (measured in terms of the identification score of pipe/link failures).

(No abstract.)

We analyze a dynamic oligopoly model with strategic sellers and buyers/consumers over a finite horizon. Each seller has private information described by a finite-state Markov process; the Markov processes describing the sellers' information are mutually independent. At the beginning of each time/stage t the sellers simultaneously post the prices for their good; subsequently, consumers make their buying decisions; finally, after the buyers' decisions are made, a public signal, indicating the buyers' consumption experience from each seller's good becomes available and the whole process moves to stage t + 1. The sellers' prices, the buyers' decisions and the signal indicating the buyers' consumption experience are common knowledge among buyers and sellers. This dynamic oligopoly model arises in online shopping and dynamic spectrum sharing markets. The model gives rise to a stochastic dynamic game with asymmetric information. Using ideas from the common information approach, we prove the existence of common information based equilibria. We obtain a sequential decomposition of the game and we provide a backward induction algorithm to determine common information-based equilibria that are perfect Bayesian equilibria. We illustrate our results with an example.

We formulate a sequential (Stackelberg) game for assessing the vulnerability of radial electricity distribution networks to disruptions in Distributed Energy Resources (DERs). In this model, the attacker disrupts a subset of DER nodes by remotely manipulating the set-points of their inverters. The defender (network operator) responds by controlling the noncompromised DERs and by imposing partial load reduction via direct load control. The attacker’s (resp. defender’s) objective is to maximize (resp. minimize) the weighted sum of cost due to the loss of voltage regulation and the cost of load control. For the sequential play game where the attacker (resp. defender) is the leader (resp. follower) and under linear power flow equations, we show that the problem reduces to standard bilevel network interdiction problem. Under our assumptions on the attack model, we obtain a structural insight that the attacker’s optimal strategy is to compromise the downstream DER nodes as opposed to the upstream ones. We present a small case study to demonstrate the applicability of our model for vulnerability assessment of distribution networks.

To penetrate sensitive computer networks, attackers can use spear phishing to sidestep technical security mechanisms by exploiting the privileges of careless users. In order to maximize their success probability, attackers have to target the users that constitute the weakest links of the system. The optimal selection of these target users takes into account both the damage that can be caused by a user and the probability of a malicious e-mail being delivered to and opened by a user. Since attackers select their targets in a strategic way, the optimal mitigation of these attacks requires the defender to also personalize the e-mail filters by taking into account the users' properties. In this paper, we assume that a learned classifier is given and propose strategic per-user filtering thresholds for mitigating spear-phishing attacks. We formulate the problem of filtering targeted and non-targeted malicious e-mails as a Stackelberg security game. We characterize the optimal filtering strategies and show how to compute them in practice. Finally, we evaluate our results using two real-world datasets and demonstrate that the proposed thresholds lead to lower losses than non-strategic thresholds.

Assuring communication integrity is a central problem in security. However, overhead costs associated with cryptographic primitives used towards this end introduce significant practical implementation challenges for resource-bounded systems, such as cyber-physical systems. For example, many control systems are built on legacy components which are computationally limited but have strict timing constraints. If integrity protection is a binary decision, it may simply be infeasible to introduce into such systems; without it, however, an adversary can forge malicious messages, which can cause significant physical or financial harm. We propose a formal game-theoretic framework for optimal stochastic message authentication, providing provable integrity guarantees for resource-bounded systems based on an existing MAC scheme. We use our framework to investigate attacker deterrence, as well as optimal design of stochastic message authentication schemes when deterrence is impossible. Finally, we provide experimental results on the computational performance of our framework in practice.

In the Internet-of-Things (IoT), users might share part of their data with different IoT prosumers, which offer applications or services. Within this open environment, the existence of an adversary introduces security risks. These can be related, for instance, to the theft of user data, and they vary depending on the security controls that each IoT prosumer has put in place. To minimize such risks, users might seek an "optimal" set of prosumers. However, assuming the adversary has the same information as the users about the existing security measures, he can then devise which prosumers will be preferable (e.g., with the highest security levels) and attack them more intensively. This paper proposes a decision-support approach that minimizes security risks in the above scenario. We propose a non-cooperative, two-player game entitled Prosumers Selection Game (PSG). The Nash Equilibria of PSG determine subsets of prosumers that optimize users' payoffs. We refer to any game solution as the Nash Prosumers Selection (NPS), which is a vector of probabilities over subsets of prosumers. We show that when using NPS, a user faces the least expected damages. Additionally, we show that according to NPS every prosumer, even the least secure one, is selected with some non-zero probability. We have also performed simulations to compare NPS against two different heuristic selection algorithms. The former is proven to be approximately 38% more effective in terms of security-risk mitigation.

An auction-based game is formulated for coordinating the charging of a population of electric vehicles (EVs) over a finite horizon. The proposed auction requires individual EVs to submit bid profiles that have dimension equal to two times the number of time-steps in the horizon. They compete for energy allocation at each time-step. Use of the progressive second price (PSP) auction mechanism ensures that incentive compatibility holds for the auction game. However, due to cross-elasticity between the charging time-steps, the marginal valuation of an individual EV at a particular time is determined by both the demand at that time and the total demand over the entire horizon. This difficulty is addressed by partitioning the allowable set of bid profiles according to the total desired energy over the entire horizon. It is shown that the efficient bid profile over the charging horizon is a Nash equilibrium of the underlying auction game. A dynamic update mechanism for the auction game is designed. A numerical example demonstrates that the auction system converges to the efficient Nash equilibrium.

(No abstract.)

The runway configuration is the set of the runways at an airport that are used for arrivals and departures at any time. While many factors, including weather, expected demand, environmental considerations, and coordination of flows with neighboring airports, influence the choice of runway configuration, the actual selection decision is made by air traffic controllers in the airport tower. As a result, the capacity of an airport at any time is dependent on the behavior of human decision makers. This paper develops a statistical model to characterize the configuration selection decision process using empirical observations. The proposed approach, based on the discrete-choicemodeling framework, identifies the influence of various factors in terms of the utility function of the decision maker. The parameters of the utility functions are estimated through likelihood maximization. Correlations between different alternatives are captured using a multinomial nested logit model. A key novelty of this study is the quantitative assessment of the effect of inertia, or the resistance to configuration changes, on the configuration selection process. The developed models are used to predict the runway configuration 3 h ahead of time, given operating conditions such as wind, visibility, and demand. Case studies based on data from Newark (EWR) and La-Guardia (LGA) airports show that the proposed model predicts runway configuration choices significantly better than a baseline model that only considers the historical frequencies of occurrence of different configurations.

Insurance is based on the diversifiability of individual risks: if an insurance provider maintains a large portfolio of customers, the probability of an event involving a large portion of the customers is negligible. However, in the case of cyber-insurance, not all risks are diversifiable due to software monocultures. If a vulnerability is discovered in a widely used software product, it can be used to compromise a multitude of targets until it is eventually patched, leading to a catastrophic event for the insurance provider. To lower their exposure to non-diversifiable risks, insurance providers may try to influence the security of widely used software products in their customer population, for example, through vulnerability reward programs. We explore the proposal that insurance providers should take a proactive role in improving software security, and provide evidence that this approach is viable for a monopolistic provider. We develop a model which captures the supply and demand sides of insurance, provide computational complexity results on the provider's investment decisions, and propose different heuristic investment strategies. We demonstrate that investments can reduce non-diversifiable risks and can lead to a more profitable cyber-insurance market. Finally, we detail the relative merits of the different heuristic strategies with numerical results.

In order to be resilient to attacks, a cyber-physical system (CPS) must be able to detect attacks before they can cause significant damage. To achieve this, intrusion detection systems (IDS) may be deployed, which can detect attacks and alert human operators, who can then intervene. However, the resource-constrained nature of many CPS poses a challenge, since reliable IDS can be computationally expensive. Consequently, computational nodes may not be able to perform intrusion detection continuously, which means that we have to devise a schedule for performing intrusion detection. While a uniformly random schedule may be optimal in a purely cyber system, an optimal schedule for protecting CPS must also take into account the physical properties of the system, since the set of adversarial actions and their consequences depend on the physical systems. Here, in the context of water distribution networks, we study IDS scheduling problems in two settings and under the constraints on the available battery supplies. In the first problem, the objective is to design, for a given duration of time, scheduling schemes for IDS so that the probability of detecting an attack is maximized within that duration. We propose efficient heuristic algorithms for this general problem and evaluate them on various networks. In the second problem, our objective is to design scheduling schemes for IDS so that the overall lifetime of the network is maximized while ensuring that an intruder attack is always detected. Various strategies to deal with this problem are presented and evaluated for various networks.

Starting with the seminal work by Kempe et al., a broad variety of problems, such as targeted marketing and the spread of viruses and malware, have been modeled as selecting a subset of nodes to maximize diffusion through a network. In cyber-security applications, however, a key consideration largely ignored in this literature is stealth. In particular, an attacker often has a specific target in mind, but succeeds only if the target is reached (e.g., by malware) before the malicious payload is detected and corresponding countermeasures deployed. The dual side of this problem is deployment of a limited number of monitoring units, such as cyber-forensics specialists, so as to limit the likelihood of such targeted and stealthy diffusion processes reaching their intended targets. We investigate the problem of optimal monitoring of targeted stealthy diffusion processes, and show that a number of natural variants of this problem are NP-hard to approximate. On the positive side, we show that if stealthy diffusion starts from randomly selected nodes, the defender's objective is submodular, and a fast greedy algorithm has provable approximation guarantees. In addition, we present approximation algorithms for the setting in which an attacker optimally responds to the placement of monitoring nodes by adaptively selecting the starting nodes for the diffusion process. Our experimental results show that the proposed algorithms are highly effective and scalable.

Increasing concern about insider threats, cyber-espionage, and other types of attacks which involve a high degree of stealthiness has renewed the desire to better understand the timing of actions to audit, clean, or otherwise mitigate such attacks. However, to the best of our knowledge, the modern literature on games shares a common limitation: the assumption that the cost and effectiveness of the players' actions are time-independent. In practice, however, the cost and success probability of attacks typically vary with time, and adversaries may only attack when an opportunity is present (e.g., when a vulnerability has been discovered). In this paper, we propose and study a model which captures dynamic environments. More specifically, we study the problem faced by a defender who has deployed a new service or resource, which must be protected against cyber-attacks. We assume that adversaries discover vulnerabilities according to a given vulnerability-discovery process which is modeled as an arbitrary function of time. Attackers and defenders know that each found vulnerability has a basic lifetime, i.e., the likelihood that a vulnerability is still exploitable at a later date is subject to the efforts by ethical hackers who may rediscover the vulnerability and render it useless for attackers. At the same time, the defender may invest in mitigation efforts to lower the impact of an exploited vulnerability. Attackers therefore face the dilemma to either exploit a vulnerability immediately, or wait for the defender to let its guard down. The latter choice leaves the risk to come away empty-handed. We develop two versions of our model, i.e., a continuous-time and a discrete-time model, and conduct an analytic and numeric analysis to take first steps towards actionable guidelines for sound security investments in dynamic contested environments.

(No abstract.)