Biblio

— Recent experimental studies have shown that traf- fic management systems are vulnerable to cyber-attacks on sensor data. This paper studies the vulnerability of fixedtime control of signalized intersections when sensors measuring traffic flow information are compromised and perturbed by an adversary. The problems are formulated by considering three malicious objectives: 1) worst-case network accumulation, which aims to destabilize the overall network as much as possible; 2) worst-case lane accumulation, which aims to cause worstcase accumulation on some target lanes; and 3) risk-averse target accumulation, which aims to reach a target accumulation by making the minimum perturbation to sensor data. The problems are solved using bilevel programming optimization methods. Finally, a case study of a real network is used to illustrate the results.

This paper presents a modeling and operation approach for tree water supply systems. The network control problem is approximated as a geometric programming (GP) problem. The original nonlinear nonconvex network control problem is transformed into a convex optimization problem. The optimization model can be efficiently solved to optimality using state-of-the-art solvers. Two control schemes are presented: (1) operation of network actuators (pumps and valves) and (2) controlled demand shedding allocation between network consumers with limited resources. The dual of the network control problem is formulated and is used to perform sensitivity analysis with respect to hydraulic constraints. The approach is demonstrated on a small branched-topology network and later extended to a medium-size irrigation network. The results demonstrate an intrinsic trade-off between energy costs and demand shedding policy, providing an efficient decision support tool for active management of water systems.

Bug-bounty programs have the potential to harvest the efforts and diverse knowledge of thousands of white hat hackers. As a consequence, they are becoming increasingly popular as a key part of the security culture of organizations. However, bug-bounty programs can be riddled with myriads of invalid vulnerability-report submissions, which are partially the result of misaligned incentives between white hats and organizations. To further improve the effectiveness of bug-bounty programs, we introduce a theoretical model for evaluating approaches for reducing the number of invalid reports. We develop an economic framework and investigate the strengths and weaknesses of existing canonical approaches for effectively incentivizing higher validation efforts by white hats. Finally, we introduce a novel approach, which may improve effi- ciency by enabling different white hats to exert validation effort at their individually optimal levels.

This paper focuses on the optimal sensor placement problem for the identification of pipe failure locations in large-scale urban water systems. The problem involves selecting the minimum number of sensors such that every pipe failure can be uniquely localized. This problem can be viewed as a minimum test cover (MTC) problem, which is NP-hard. We consider two approaches to obtain approximate solutions to this problem. In the first approach, we transform the MTC problem to a minimum set cover (MSC) problem and use the greedy algorithm that exploits the submodularity property of the MSC problem to compute the solution to the MTC problem. In the second approach, we develop a new augmented greedy algorithm for solving the MTC problem. This approach does not require the transformation of the MTC to MSC. Our augmented greedy algorithm provides in a significant computational improvement while guaranteeing the same approximation ratio as the first approach. We propose several metrics to evaluate the performance of the sensor placement designs. Finally, we present detailed computational experiments for a number of real water distribution networks.

Electrical power distribution networks are susceptible to Fault Induced Delayed Voltage Recovery (FIDVR). Such events are usually initiated by faults at substations and lead to sustained low voltages throughout the distribution grid. The mechanism underpinning this phenomenon is known to be the stalling of induction motors in residential air conditioners. It is useful to be able to partition parameter space into parameters that induce motor stalling versus those for which the motors recover for a particular fault. Novel algorithms are presented for numerically computing the border that separates such parameter-space partitions, and for finding the point on the border that is closest to a given point in parameter space. These algorithms are justified by theoretical results which exploit the presence of a special equilibrium point on the state-space stability boundary, called the controlling unstable equilibrium point. The key idea is to vary parameters in order to drive the trajectory to spend a fixed amount of time inside a ball centered at the controlling unstable equilibrium point, and then to maximize the amount of time inside that ball. The algorithms are applied to a modified version of the IEEE 37-bus test feeder.

(No abstract.)

While renewable generation sources provide many economic and environmental benefits for the operation of power systems, their inherent stochastic nature introduces challenges from the perspective of reliability. Existing optimal power flow (OPF) methods must therefore be extended to consider forecast errors to mitigate in an economic manner the uncertainty that renewable generation introduces. This paper presents an AC-QP OPF solution algorithm that has been modified to include wind generation uncertainty. We solve the resulting stochastic optimization problem using a scenario based algorithm that is based on randomized methods that provide probabilistic guarantees of the solution. The proposed method produces an AC-feasible solution while satisfying reasonable reliability criteria. Test cases are included for the IEEE 14-bus network that has been augmented with 2 wind generators. The scalability, optimality and reliability achieved by the proposed method are then assessed.

In recent years, we have seen a number of successful attacks against high-profile targets, some of which have even caused severe physical damage. These examples have shown us that resourceful and determined attackers can penetrate virtually any system, even those that are secured by the "air-gap." Consequently, in order to minimize the impact of stealthy attacks, defenders have to focus not only on strengthening the first lines of defense but also on deploying effective intrusion-detection systems. Intrusion-detection systems can play a key role in protecting sensitive computer systems since they give defenders a chance to detect and mitigate attacks before they could cause substantial losses. However, an over-sensitive intrusion-detection system, which produces a large number of false alarms, imposes prohibitively high operational costs on a defender since alarms need to be manually investigated. Thus, defenders have to strike the right balance between maximizing security and minimizing costs. Optimizing the sensitivity of intrusion detection systems is especially challenging in the case when multiple inter-dependent computer systems have to be defended against a strategic attacker, who can target computer systems in order to maximize losses and minimize the probability of detection. We model this scenario as an attacker-defender security game and study the problem of finding optimal intrusion detection thresholds.

We study users’ incentives to become cybercriminals when network security is interdependent. We present a game-theoretic model in which each player (i.e., network user) decides his type, honest or malicious. Honest users represent law-abiding network users, while malicious users represent cybercriminals. After deciding on their types, the users make their security choices. We will follow [29], where breach probabilities for large-scale networks are obtained from a standard interdependent security (IDS) setup. In large-scale IDS networks, the breach probability of each player becomes a function of two variables: the player’s own security action and network security, which is an aggregate characteristic of the network; network security is computed from the security actions of the individual nodes that comprise the network. This allows us to quantify user security choices in networks with IDS even when users have only very limited, aggregate information about security choices of other users of the network.

A novel class of auction-based games is formulated to study coordination problems arising from charging a population of electric vehicles (EVs) over a finite horizon. To compete for energy allocation over the horizon, each individual EV submits a multidimensional bid, with the dimension equal to two times the number of time-steps in the horizon. Use of the progressive second price (PSP) auction mechanism ensures that incentive compatibility holds for the auction games. However, due to the cross elasticity of EVs over the charging horizon, 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 based on 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. An update mechanism for the auction game is designed. A numerical example demonstrates that the auction process converges to an efficient Nash equilibrium. The auction-based charging coordination scheme is adapted to a receding horizon formulation to account for disturbances and forecast uncertainty.

(No abstract.)

Sensor networks monitoring spatially-distributed physical systems often comprise battery-powered sensor devices. To extend lifetime, battery power may be conserved using sleep scheduling: activating and deactivating some of the sensors from time to time. Scheduling sensors with the goal of maximizing average coverage, that is the average fraction of time for which each monitoring target is covered by some active sensor has been studied extensively. However, many applications also require time-critical monitoring in the sense that one has to minimize the average delay until an unpredictable change or event at a monitoring target is detected. In this paper, we study the problem of sleep scheduling sensors to minimize the average delay in detecting such time-critical events in the context of monitoring physical systems that can be modeled using graphs, such as water distribution networks. We provide a game-theoretic solution that computes schedules with near optimal average delays. We illustrate that schedules that optimize average coverage may result in large average detection delays, whereas schedules minimizing average detection delays using our proposed scheme also result in near optimal average coverage.

In networked systems, monitoring devices such as sensors are typically deployed to monitor various target locations. Targets are the points in the physical space at which events of some interest, such as random faults or attacks, can occur. Most often, these devices have limited energy supplies, and they can operate for a limited duration. As a result, energyefficient monitoring of various target locations through a set of monitoring devices with limited energy supplies is a crucial problem in networked systems. In this paper, we study optimal scheduling of monitoring devices to maximize network coverage for detecting and isolating events on targets for a given network lifetime. The monitoring devices considered could remain active only for a fraction of the overall network lifetime. We formulate the problem of scheduling of monitoring devices as a graph labeling problem, which unlike other existing solutions, allows us to directly utilize the underlying network structure to explore the trade-off between coverage and network lifetime. In this direction, first we propose a greedy heuristic to solve the graph labeling problem, and then provide a game-theoretic solution to achieve optimal graph labeling. Moreover, the proposed setup can be used to simultaneously solve the scheduling and placement of monitoring devices, which yields improved performance as compared to separately solving the placement and scheduling problems. Finally, we illustrate our results on various networks, including real-world water distribution networks.

Renewable generation and energy storage are playing an ever increasing role in power systems. Hence, there is a growing need for integrating these resources into the optimal power flow (OPF) problem. While storage devices are important for mitigating renewable variability, they introduce temporal coupling in the OPF constraints, resulting in a multiperiod OPF formulation. This paper explores a solution method for multiperiod AC OPF that combines a successive quadratic programming approach (AC-QP) with a second-order cone programming (SOCP) relaxation of the OPF problem. The SOCP relaxation’s solution is used to initialize the AC-QP OPF algorithm. Additionally, the lower bound on the objective value obtained from the SOCP relaxation provides a measure of solution quality. This combined method is demonstrated on several test cases with up to 4259 nodes and a time horizon of 8 time steps. A comparison of initialization schemes indicates that the SOCP-based approach offers improved convergence rate, execution time and solution quality.

Enhanced control capabilities are required to coordinate the response of increasingly diverse controllable resources, including FACTS devices, energy storage, demand response and fast-acting generation. Model-predictive control (MPC) has shown great promise for accommodating these devices in a corrective control framework that exploits the thermal overload capability of transmission lines and limits detrimental effects of contingencies. This work expands upon earlier implementations by incorporating voltage magnitudes and reactive power into the system model utilized by MPC. These improvements provide a more accurate prediction of system behavior and enable more effective control decisions. Performance of this enhanced MPC strategy is demonstrated using a model of the Californian power system containing 4259 buses. Sparsity in modelling and control actions must be exploited for implementation on large networks. A method is developed for identifying the set of controls that is most effective for a given contingency. The proposed MPC corrective control algorithm fits naturally within energy management systems where it can provide feedback control or act as a guide for system operators by identifying beneficial control actions across a wide range of devices.

It is common for power system behavior to be expressed in terms of polar voltage coordinates. When applied in optimization settings, loss formulations in polar voltage coordinates typically assume that voltage magnitudes are fixed. In reality, voltage magnitudes vary and may have an appreciable effect on losses. This paper proposes a systematic approach to incorporating the effects of voltage magnitude changes into a linear relaxation of the losses on a transmission line. This approach affords greater accuracy when describing losses around a base voltage condition as compared to previous linear and piecewise linear methods. It also better captures the true behavior of losses at conditions away from the flat voltage profile.

In the restructured electricity industry, Generation Expansion Planning (GEP) is an oligopoly of strategic Generation Companies (GenCos) with private information investing in a highly uncertain environment. Strategic planning and uncertainties can result in market manipulation and underinvestment (short-term planning). We present a forward moving approach to the problem of investment expansion planning in the restructured electricity industry. This approach accounts for technological, political and environmental uncertainties in the problem’s environment and leads to long-term planning. At each step of the approach we present a block investment market mechanism that has the following features. (F1) It is individually rational. (F2) It is budget balanced. (F3) The expansion and production allocations corresponding to the unique Nash Equilibrium (NE) of the game induced by the mechanism are the same as those that maximize the sum of utilities of the producers and the demand. (F4) It is price efficient that is, the price for electricity at equilibrium is equal to the marginal utility of the demand and to the marginal cost of production by producers with free capacity.

Most existing models of Stackelberg security games ignore the underlying topology of the space in which targets and defence resources are located. As a result, allocation of resources is restricted to a discrete collection of exogenously defined targets. However, in many practical security settings, defense resources can be located on a continuous plane. Better defense solutions could therefore be potentially achieved by placing resources in a space outside of actual targets (e.g., between targets). To address this limitation, we propose a model called Security Game on a Plane (SGP) in which targets are distributed on a 2-dimensional plane, and security resources, to be allocated on the same plane, protect targets within a certain effective distance. We investigate the algorithmic aspects of SGP. We find that computing a strong Stackelberg equilibrium of an SGP is NP-hard even for zerosum games, and these are inapproximable in general. On the positive side, we find an exact solution technique for general SGPs based on an existing approach, and develop a PTAS (polynomial-time approximation scheme) for zero-sum SGP to more fundamentally overcome the computational obstacle. Our experiments demonstrate the value of considering SGP and effectiveness of our algorithms.

We study a dataset of billions of program binary files that appeared on 100 million computers over the course of 12 months, discovering that 94% of these files were present on a single machine. Though malware polymorphism is one cause for the large number of singleton files, additional factors also contribute to polymorphism, given that the ratio of benign to malicious singleton files is 80:1. The huge number of benign singletons makes it challenging to reliably identify the minority of malicious singletons. We present a large-scale study of the properties, characteristics, and distribution of benign and malicious singleton files. We leverage the insights from this study to build a classifier based purely on static features to identify 92% of the remaining malicious singletons at a 1.4% percent false positive rate, despite heavy use of obfuscation and packing techniques by most malicious singleton files that we make no attempt to de-obfuscate. Finally, we demonstrate robustness of our classifier to important classes of automated evasion attacks.

Recommendation and collaborative filtering systems are important in modern information and e-commerce applications. As these systems are becoming increasingly popular in the industry, their outputs could affect business decision making, introducing incentives for an adversarial party to compromise the availability or integrity of such systems. We introduce a data poisoning attack on collaborative filtering systems. We demonstrate how a powerful attacker with full knowledge of the learner can generate malicious data so as to maximize his/her malicious objectives, while at the same time mimicking normal user behavior to avoid being detected. While the complete knowledge assumption seems extreme, it enables a robust assessment of the vulnerability of collaborative filtering schemes to highly motivated attacks. We present efficient solutions for two popular factorization-based collaborative filtering algorithms: the alternative minimization formulation and the nuclear norm minimization method. Finally, we test the effectiveness of our proposed algorithms on real-world data and discuss potential defensive strategies.

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 cyberphysical 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. To bridge the gap between such binary decisions, we propose a stochastic message authentication approach that can explicitly trade computational cost off for security. We introduce a formal game-theoretic framework for optimal stochastic message authentication, providing provable guarantees for resource-bounded systems based on an existing message authentication scheme. We use our framework to investigate attacker deterrence, as well as optimal stochastic message authentication when deterrence is impossible, in both short-term and long-term equilibria. Additionally, we propose two schemes for implementing stochastic message authentication in practice, one for saving computation only at the receiver and one for saving computation at both ends, and demonstrate the associated computational savings using an actual implementation.

(No abstract.)

The quantity of information that is collected and stored in computer systems continues to grow rapidly. At the same time, the sensitivity of such information (e.g., detailed medical records) often makes such information valuable to both external attackers, who may obtain information by compromising a system, and malicious insiders, who may misuse information by exercising their authorization. To mitigate compromises and deter misuse, the security administrators of these resources often deploy various types of intrusion and misuse detection systems, which provide alerts of suspicious events that are worthy of follow-up review. However, in practice, these systems may generate a large number of false alerts, wasting the time of investigators. Given that security administrators have limited budget for investigating alerts, they must prioritize certain types of alerts over others. An important challenge in alert prioritization is that adversaries may take advantage of such behavior to evade detection - specifically by mounting attacks that trigger alerts that are less likely to be investigated. In this paper, we model alert prioritization with adaptive adversaries using a Stackelberg game and introduce an approach to compute the optimal prioritization of alert types. We evaluate our approach using both synthetic data and a real-world dataset of alerts generated from the audit logs of an electronic medical record system in use at a large academic medical center.

Smart water networks can provide great benefits to our society in terms of efficiency and sustainability. However, smart capabilities and connectivity also expose these systems to a wide range of cyber attacks, which enable cyber-terrorists and hostile nation states to mount cyber-physical attacks. Cyber-physical attacks against critical infrastructure, such as water treatment and distribution systems, pose a serious threat to public safety and health. Consequently, it is imperative that we improve the resilience of smart water networks. We consider three approaches for improving resilience: redundancy, diversity, and hardening. Even though each one of these “canonical” approaches has been thoroughly studied in prior work, a unified theory on how to combine them in the most efficient way has not yet been established. In this paper, we address this problem by studying the synergy of these approaches in the context of protecting smart water networks from cyber-physical contamination attacks.

Participatory sensing enables individuals, each with limited sensing capability, to share measurements and contribute towards developing a complete knowledge of their environment. The success of a participatory sensing application is often measured in terms of the number of users participating. In most cases, an individual’s eagerness to participate depends on the group of users who already participate. For instance, when users share data with their peers in a social network, the engagement of an individual depends on its peers. Such engagement rules have been studied in the context of social networks using the concept of k-core, which assumes that participation is determined solely by network topology. However, in participatory sensing, engagement rules must also consider user heterogeneity, such as differences in sensing capabilities and physical location. To account for heterogeneity, we introduce the concept of (r,s)-core to model the set of participating users. We formulate the problem of maximizing the size of the (r,s)-core using 1) anchor users, who are incentivized to participate regardless of their peers, and by 2) assigning capabilities to users. Since these problems are computationally challenging, we study heuristic algorithms for solving them. Based on real-world social networks as well as random graphs, we provide numerical results showing significant improvement compared to random selection of anchor nodes and label assignments.