Visible to the public Biblio

Filters: Keyword is Toward a Theory of Resilience in Systems: A Game-Theoretic Approach  [Clear All Filters]
Quanyan Zhu, University of Illinois at Urbana-Champaign, Linda Bushnell, University of Washington, Tamer Başar, University of Illinois at Urbana-Champaign.  2013.  Resilient Distributed Control of Multi-agent Cyber-Physical Systems. Workshop on Control of Cyber-Physical Systems.

Abstract. Multi-agent cyber-physical systems (CPSs) are ubiquitous in modern infrastructure systems, including the future smart grid, transportation networks, and public health systems. Security of these systems are critical for normal operation of our society. In this paper, we focus on physical layer resilient control of these systems subject to cyber attacks and malicious behaviors of physical agents. We establish a cross-layer system model for the investigation of cross-layer coupling and performance interdependencies for CPSs. In addition, we study a twosystem synchronization problem in which one is a malicious agent who intends to mislead the entire system behavior through physical layer interactions. Feedback Nash equilibrium is used as the solution concept for the distributed control in the multi-agent system environment. We corroborate our results with numerical examples, which show the performance interdependencies between two CPSs through cyber and physical interactions.

Bahman Gharesifard, University of Illinois at Urbana-Champaign, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  Resilience in Consensus Dynamics via Competitive Interconnections. 3rd IFAC Workshop on Distributed Estimation and Control Networked Systems.

We show that competitive engagements within the agents of a network can result in resilience in consensus dynamics with respect to the presence of an adversary. We first show that interconnections with an adversary, with linear dynamics, can make the consensus dynamics diverge, or drive its evolution to a state different from the average.We then introduce a second network, interconnected with the original network via an engagement topology. This network has no information about the adversary and each agent in it has only access to partial information about the state of the other network. We introduce a dynamics on the coupled network which corresponds to a saddle-point dynamics of a certain zero-sum game and is distributed over each network, as well as the engagement topology. We show that, by appropriately choosing a design parameter corresponding to the competition between these two networks, the coupled dynamics can be made resilient with respect to the presence of the adversary.Our technical approach combines notions of graph theory and stable perturbations of nonsymmetric matrices.We demonstrate our results on an example of kinematic-based flocking in presence of an adversary.

Quanyan Zhu, University of Illinois at Urbana-Champaign, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  Game-Theoretic Methods for Distributed Management of Energy Resources in the Smart Grid.

The smart grid is an ever-growing complex dynamic system with multiple interleaved layers and a large number of interacting components. In this talk, we discuss how game-theoretic tools can be used as an analytical tool to understand strategic interactions at different layers of the system and between different decision-making entities for distributed management of energy resources. We first investigate the issue of integration of renewable energy resources into the power grid. We establish a game-theoretic framework for modeling the strategic behavior of buses that are connected to renewable energy resources, and study the Nash equilibrium solution of distributed power generation at each bus. Our framework uses a cross-layer approach, taking into account the economic factors as well as system stability issues at the physical layer. In the second part of the talk, we discuss the issue of integration of plug-in electric vehicles (PHEVs) for vehicle-to-grid (V2G) transactions on the smart grid. Electric vehicles will be capable of buying and selling energy from smart parking lots in the future. We propose a multi-resolution and multi-layer stochastic differential game framework to study the dynamic decision-making process among PHEVs. We analyze the stochastic game in a large-population regime and account for the multiple types of interactions in the grid. Using these two settings, we demonstrate that game theory is a versatile tool to address many fundamental and emerging issues in the smart grid.

Presented at the Eighth Annual Carnegie Mellon Conference on the Electricity Industry Data-Driven Sustainable Engergy Systems in Pittsburgh, PA, March 12-14, 2012.

Quanyan Zhu, University of Illinois at Urbana-Champaign, Tamer Başar, University of Illinois at Urbana-Champaign.  2013.  Game-Theoretic Approach to Feedback-Driven Multi-stage Moving Target Defense. 4th International Conference on Decision and Game Theory for Security (GameSec 2013).

The static nature of computer networks allows malicious attackers to easily gather useful information about the network using network scanning and packet sniffing. The employment of secure perimeter firewalls and intrusion detection systems cannot fully protect the network from sophisticated attacks. As an alternative to the expensive and imperfect detection of attacks, it is possible to improve network security by manipulating the attack surface of the network in order to create a moving target defense. In this paper, we introduce a proactive defense scheme that dynamically alters the attack surface of the network to make it difficult for attackers to gather system information by increasing complexity and reducing its signatures. We use concepts from systems and control literature to design an optimal and efficient multi-stage defense mechanism based on a feedback information structure. The change of
attack surface involves a reconfiguration cost and a utility gain resulting from risk reduction. We use information- and control-theoretic tools to provide closed-form optimal randomization strategies. The results are corroborated by a case study and several numerical examples.

Andrew Clark, University of Washington, Quanyan Zhu, University of Illinois at Urbana-Champaign, Radha Poovendran, University of Washington, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  Deceptive Routing in Relay Networks. Conference on Decision and Game Theory for Security.

Physical-layer and MAC-layer defense mechanisms against jamming attacks are often inherently reactive to experienced delay and loss of throughput after being attacked. In this paper, we study a proactive defense mechanism against jamming in multi-hop relay networks, in which one or more network sources introduce a deceptive network flow along a disjoint routing path. The deceptive mechanism leverages strategic jamming behaviors, causing the attacker to expend resources on targeting deceptive flows and thereby reducing the impact on real network trac. We use a two-stage game model to obtain deception strategies at Stackelberg equilibrium for sel sh and altruistic nodes. The equilibrium solutions are illustrated and corroborated through a simulation study.

Alejandro Domininguez-Garcia, University of Illinois at Urbana-Champaign, Bahman Gharesifard, University of Illinois at Urbana-Champaign, Tamer Başar, University of Illinois at Urbana-Champaign.  2013.  A Price-Based Approach to Control of Networked Distributed Energy Resources.

We introduce a framework for controlling the energy provided or absorbed by distributed energy resources (DERs) in power distribution networks. In this framework, there is a set of agents referred to as aggregators that interact with the wholesale electricity market, and through some market-clearing mechanism, are requested (and will be compensated for) to provide (or absorb) certain amount of active (or reactive) power over some period of time. In order to fulfill the request, each aggregator interacts with a set of DERs and offers them some price per unit of active (or reactive) power they provide (or absorb); the objective is for the aggregator to design a pricing strategy for incentivizing DERs to change its active (or reactive) power consumption (or production) so as they collectively provide the amount that the aggregator has been asked for. In order to make a decision, each DER uses the price information provided by the aggregator and some estimate of the average active (or reactive) power that neighboring DERs can provide computed through some exchange of information among them; this exchange is described by a connected undirected graph. The focus is on the DER strategic decision-making process, which we cast as a game. In this context, we provide sufficient conditions on the aggregator's pricing strategy under which this game has a unique Nash equilibrium. Then, we propose a distributed iterative algorithm that adheres to the graph that describes the exchange of information between DERs that allows them to seek for this Nash equilibrium. We illustrate our results through several numerical simulations.

Presented as part of the DIMACS Workshop on Energy Infrastructure: Designing for Stability and Resilience, Rutgers University, Piscataway, NJ, February 20-22, 2013

Mohammad Hossein Manshaei, Isfahan University of Technology, Quanyan Zhu, University of Illinois at Urbana-Champaign, Tansu Alpcan, University of Melbourne, Tamer Başar, University of Illinois at Urbana-Champaign, Jean-Pierre Hubaux, Ecole Polytechnique Federal de Lausanne.  2013.  Game Theory Meets Network Security and Privacy. ACM Computing Surveys. 45(3):06/2013.

This survey provides a structured and comprehensive overview of research on security and privacy in computer and communication networks that use game-theoretic approaches. We present a selected set of works to highlight the application of game theory in addressing different forms of security and privacy problems in computer networks and mobile applications. We organize the presented works in six main categories: security of the physical and MAC layers, security of self-organizing networks, intrusion detection systems, anonymity and privacy, economics of network security, and cryptography. In each category, we identify security problems, players, and game models. We summarize the main results of selected works, such as equilibrium analysis and security mechanism designs. In addition, we provide a discussion on the advantages, drawbacks, and future direction of using game theory in this field. In this survey, our goal is to instill in the reader an enhanced understanding of different research approaches in applying gametheoretic methods to network security. This survey can also help researchers from various fields develop game-theoretic solutions to current and emerging security problems in computer networking.

Craig Rieger, Idaho Naitonal Laboratory, Quanyan Zhu, University of Illinois at Urbana-Champaign, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  Agent-Based Cyber Control Strategy Design for Resilient Control Systems: Concepts, Architecure and Methodologies. 2012 5th International Sympsoium on Resilient Control Systems (ISRCS 2012).

The implementation of automated regulatory control has been around since the middle of the last century through analog means. It has allowed engineers to operate the plant more consistently by focusing on overall operations and settings instead of individual monitoring of local instruments (inside and outside of a control room). A similar approach is proposed for cyber security, where current border-protection designs have been inherited from information technology developments that lack consideration of the high-reliability, high consequence nature of industrial control systems. Instead of an independent development, however, an integrated approach is taken to develop a holistic understanding of performance. This performance takes shape inside a multiagent design, which provides a notional context to model highly decentralized and complex industrial process control systems, the nervous system of critical infrastructure. The resulting strategy will provide a framework for researching solutions to security and unrecognized interdependency concerns with industrial control systems.

Yuan Yuan, Tsinghua University, Quanyan Zhu, University of Illinois at Urbana-Champaign, Fuchun Sun, Tsinghua University, Qinyi Wang, Beihang University, Tamer Başar, University of Illinois at Urbana-Champaign.  2013.  Resilient Control of Cyber-Physical Systems against Denial-of-Service Attacks. 6th International Symposium on Resilient Control Systems.

The integration of control systems with modern information technologies has posed potential security threats for critical infrastructures. The communication channels of the control system are vulnerable to malicious jamming and Denial-of-Service (DoS) attacks, which lead to severe timedelays and degradation of control performances. In this paper, we design resilient controllers for cyber-physical control systems under DoS attacks. We establish a coupled design framework which incorporates the cyber configuration policy of Intrusion Detection Systems (IDSs) and the robust control of dynamical system. We propose design algorithms based on value iteration methods and linear matrix inequalities for computing the optimal cyber security policy and control laws. We illustrate the design principle with an example from power systems. The results are corroborated by numerical examples and simulations.

Bahman Gharesifard, University of Illinois at Urbana-Champaign, Tamer Başar, University of Illinois at Urbana-Champaign, Alejandro D. Domínguez-García, University of Illinois at Urbana-Champaign.  2013.  Price-based Distributed Control for Networked Plug-in Electric Eehicles. 2013 American Control Conference.

We introduce a framework for controlling the charging and discharging processes of plug-in electric vehicles (PEVs) via pricing strategies. Our framework consists of a hierarchical decision-making setting with two layers, which we refer to as aggregator layer and retail market layer. In the aggregator layer, there is a set of aggregators that are requested (and will be compensated for) to provide certain amount of energy over a period of time. In the retail market layer, the aggregator offers some price for the energy that PEVs may provide; the objective is to choose a pricing strategy to incentivize the PEVs so as they collectively provide the amount of energy that the aggregator has been asked for. The focus of this paper is on the decision-making process that takes places in the retail market layer, where we assume that each individual PEV is a price-anticipating decision-maker. We cast this decision-making process as a game, and provide conditions on the pricing strategy of the aggregator under which this game has a unique Nash equilibrium. We propose a distributed consensus-based iterative algorithm through which the PEVs can seek for this Nash equilibrium. Numerical simulations are included to illustrate our results.

Quanyan Zhu, University of Illinois at Urbana-Champaign, Carol Fung, Raouf Boutaba, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  GUIDEX: A Game-Theoretic Incentive-Based Mechanism for Intrusion Detection Networks. IEEE Journal on Selected Areas in Communications. 30(11)

Traditional intrusion detection systems (IDSs) work in isolation and can be easily compromised by unknown threats. An intrusion detection network (IDN) is a collaborative IDS network intended to overcome this weakness by allowing IDS peers to share detection knowledge and experience, and hence improve the overall accuracy of intrusion assessment. In this work, we design an IDN system, called GUIDEX, using gametheoretic modeling and trust management for peers to collaborate truthfully and actively. We first describe the system architecture and its individual components, and then establish a gametheoretic framework for the resource management component of GUIDEX. We establish the existence and uniqueness of a Nash equilibrium under which peers can communicate in a reciprocal incentive compatible manner. Based on the duality of the problem, we develop an iterative algorithm that converges geometrically to the equilibrium. Our numerical experiments and discrete event simulation demonstrate the convergence to the Nash equilibrium and the security features of GUIDEX against free riders, dishonest insiders and DoS attacks

Quanyan Zhu, University of Illinois at Urbana-Champaign, Linda Bushnell, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  Game-Theoretic Analysis of Node Capture and Cloning Attack with Multiple Attackers in Wireless Sensor Networks. 51st IEEE Conference on Decision and Control.

Wireless sensor networks are subject to attacks such as node capture and cloning, where an attacker physically captures sensor nodes, replicates the nodes, which are deployed into the network, and proceeds to take over the network. In this paper, we develop models for such an attack when there are multiple attackers in a network, and formulate multi-player games to model the noncooperative strategic behavior between the attackers and the network. We consider two cases: a static case where the attackers’ node capture rates are time-invariant and the network’s clone detection/revocation rate is a linear function of the state, and a dynamic case where the rates are general functions of time. We characterize Nash equilibrium solutions for both cases and derive equilibrium strategies for the players. In the static case, we study both the single-attacker and the multi-attacker games within an optimization framework, provide conditions for the existence of Nash equilibria and characterize them in closed forms. In the dynamic case, we study the underlying multi-person differential game under an open-loop information structure and provide a set of conditions to characterize the open-loop Nash equilibrium. We show the equivalence of the Nash equilibrium for the multi-person game to the saddle-point equilibrium between the network and the attackers as a team. We illustrate our results with numerical examples.

Bahman Gharesifard, Behrouz Touri, Tamer Başar, University of Illinois at Urbana-Champaign, Cedric Langbort, University of Illinois at Urbana-Champaign.  2013.  Distributed Optimization by Myopic Strategic Interactions and the Price of Heterogeneity. 52nd Conference on Decision and Control.

This paper is concerned with the tradeoffs between low-cost heterogenous designs and optimality. We study a class of constrained myopic strategic games on networks which approximate the solutions to a constrained quadratic optimization problem; the Nash equilibria of these games can be found using best-response dynamical systems, which only use local information. The notion of price of heterogeneity captures the quality of our approximations. This notion relies on the structure and the strength of the interconnections between agents. We study the stability properties of these dynamical systems and demonstrate their complex characteristics, including abundance of equilibria on graphs with high sparsity and heterogeneity. We also introduce the novel notions of social equivalence and social dominance, and show some of their interesting implications, including their correspondence to consensus. Finally, using a classical result of Hirsch [1], we fully characterize the stability of these dynamical systems for the case of star graphs with asymmetric interactions. Various examples illustrate our results.

Quanyan Zhu, University of Illinois at Urbana-Champaign, Andrew Clark, Radha Poovendran, Tamer Başar, University of Illinois at Urbana-Champaign.  2013.  Deployment and Exploitation of Deceptive Honeybots in Social Networks. 52nd Conference on Decision and Control.

As social networking sites such as Facebook and Twitter are becoming increasingly popular, a growing number of malicious attacks, such as phishing and malware, are exploiting them. Among these attacks, social botnets have sophisticated infrastructure that leverages compromised user accounts, known as bots, to automate the creation of new social networking accounts for spamming and malware propagation. Traditional defense mechanisms are often passive and reactive to non-zero-day attacks. In this paper, we adopt a proactive approach for enhancing security in social networks by infiltrating botnets with honeybots. We propose an integrated system named SODEXO which can be interfaced with social networking sites for creating deceptive honeybots and leveraging them for gaining information from botnets. We establish a Stackelberg game framework to capture strategic interactions between honeybots and botnets, and use quantitative methods to understand the tradeoffs of honeybots for their deployment and exploitation in social networks. We design a protection and alert system that integrates both microscopic and macroscopic models of honeybots and optimally determines the security strategies for honeybots. We corroborate the proposed mechanism with extensive simulations and comparisons with passive defenses.

Sabita Maharjan, Quanyan Zhu, University of Illinois at Urbana-Champaign, Yan Zhang, Stein Gjessing, Tamer Başar, University of Illinois at Urbana-Champaign.  2013.  Dependable Demand Response Management in Smart Grid: A Stackelberg Game Approach. IEEE Transactions on Smart Grid. 4(1)

Demand ResponseManagement (DRM) is a key component in the smart grid to effectively reduce power generation costs and user bills. However, it has been an open issue to address the DRM problem in a network of multiple utility companies and consumers where every entity is concerned about maximizing its own benefit. In this paper, we propose a Stackelberg game between utility companies and end-users to maximize the revenue of each utility company and the payoff of each user. We derive analytical results for the Stackelberg equilibrium of the game and prove that a unique solution exists.We develop a distributed algorithm which converges to the equilibrium with only local information available for both utility companies and end-users. Though DRM helps to facilitate the reliability of power supply, the smart grid can be succeptible to privacy and security issues because of communication links between the utility companies and the consumers. We study the impact of an attacker who can manipulate the price information from the utility companies.We also propose a scheme based on the concept of shared reserve power to improve the grid reliability and ensure its dependability.

Quanyan Zhu, University of Illinois at Urbana-Champaign, Andrew Clark, Radha Poovendran, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  Deceptive Routing Games. 51st IEEE Conference on Decision and Control.

The use of a shared medium leaves wireless networks, including mobile ad hoc and sensor networks, vulnerable to jamming attacks. In this paper, we introduce a jamming defense mechanism for multiple-path routing networks based on maintaining deceptive flows, consisting of fake packets, between a source and a destination. An adversary observing a deceptive flow will expend energy on disrupting the fake packets, allowing the real data packets to arrive at the destination unharmed. We model this deceptive flow-based defense within a multi-stage stochastic game framework between the network nodes, which choose a routing path and flow rates for the real and fake data, and an adversary, which chooses which fraction of each flow to target at each hop. We develop an efficient, distributed procedure for computing the optimal routing at each hop and the optimal flow allocation at the destination. Furthermore, by studying the equilibria of the game, we quantify the benefit arising from deception, as reflected in an increase in the valid throughput. Our results are demonstrated via a simulation study.

Andrew Clark, Quanyan Zhu, University of Illinois at Urbana-Champaign, Radha Poovendran, Tamer Başar, University of Illinois at Urbana-Champaign.  2013.  An Impact-Aware Defense against Stuxnet. IFAC American Control Conference (ACC 2013).

The Stuxnet worm is a sophisticated malware designed to sabotage industrial control systems (ICSs). It exploits vulnerabilities in removable drives, local area communication networks, and programmable logic controllers (PLCs) to penetrate the process control network (PCN) and the control system network (CSN). Stuxnet was successful in penetrating the control system network and sabotaging industrial control processes since the targeted control systems lacked security mechanisms for verifying message integrity and source authentication. In this work, we propose a novel proactive defense system framework, in which commands from the system operator to the PLC are authenticated using a randomized set of cryptographic keys. The framework leverages cryptographic analysis and controland game-theoretic methods to quantify the impact of malicious commands on the performance of the physical plant. We derive the worst-case optimal randomization strategy as a saddle-point equilibrium of a game between an adversary attempting to insert commands and the system operator, and show that the proposed scheme can achieve arbitrarily low adversary success probability for a sufficiently large number of keys. We evaluate our proposed scheme, using a linear-quadratic regulator (LQR) as a case study, through theoretical and numerical analysis.

Quanyan Zhu, University of Illinois at Urbana-Champaign, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  A Dynamic Game-Theoretic Approach to Resilient Control System Design for Cascading Failures. International Conference on High Confidence Networked Systems.

The migration of many current critical infrastructures, such as power grids and transportations systems, into open publicnetworks has posed many challenges in control systems. Modern control systems face uncertainties not only from the physical world but also from the cyber space. In this paper, we propose a hybrid game-theoretic approach to investigate the coupling between cyber security policy and robust control design. We study in detail the case of cascading failures in industrial control systems and provide a set of coupled optimality criteria in the linear-quadratic case. This approach can be further extended to more general cases of parallel cascading failures.