Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Doctoral Dissertations
    • View Item
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Doctoral Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Containing Cascading Failures in Networks: Applications to Epidemics and Cybersecurity

    Thumbnail
    View/Open
    Saha_S_D_2016.pdf (1.408Mb)
    Downloads: 191
    Date
    2016-10-05
    Author
    Saha, Sudip
    Metadata
    Show full item record
    Abstract
    Many real word networks exhibit cascading phenomena, e.g., disease outbreaks in social contact networks, malware propagation in computer networks, failures in cyber-physical systems such as power grids. As they grow in size and complexity, their security becomes increasingly important. In this thesis, we address the problems of controlling cascading failures in various network settings. We address the cascading phenomena which are either natural (e.g., disease outbreaks) or malicious (e.g., cyber attacks). We consider the nodes of a network as being individually or collectively controlled by self-interested autonomous agents and study their strategic decisions in the presence of these failure cascades. There are many models of cascading failures which specify how a node would fail when some neighbors have failed, such as: (i) epidemic spread models in which the cascading can be viewed as a natural and stochastic process and (ii) cyber attack models where the cascade is driven by malicious intents. We present our analyses and algorithms for these models in two parts. Part I focuses on problems of controlling epidemic spread. Epidemic outbreaks are generally modeled as stochastic diffusion processes. In particular, we consider the SIS model on networks. There exist heuristic centralized approaches in the literature for containing epidemic spread in SIS/SIR models; however no rigorous performance bounds are known for these approaches. We develop algorithms with provable approximation guarantees that involve either protective intervention (e.g., vaccination) or link removal (e.g., unfriending). Our approach relies on the characterization of the SIS model in terms of the spectral radius of the network. The centralized approaches, however, are sometimes not feasible in practice. For example, targeted vaccination is often not feasible because of limited compliance to directives. This issue has been addressed in the literature by formulating game theoretic models for the containment of epidemic spread. However they generally assume simplistic propagation models or homogeneous network structures. We develop novel game formulations which rely on the spectral characterization of the SIS model. In these formulations, the failures start from a random set of nodes and propagate through the network links. Each node acts as a self-interested agent and makes strategic intervention decisions (e.g., taking vaccination). Each agent decides its strategy to optimize its payoff (modeled by some payoff function). We analyze the complexity of finding Nash equilibria (NE) and study the structure of NE for different networks in these game settings. Part II focuses on malware spread in networks. In cybersecurity literature malware spreads are often studied in the framework of ``attack graph" models. In these models, a node represents either a physical computing unit or a network configuration and an edge represents a physical or logical vulnerability dependency. A node gets compromised if a certain set of its neighbors are compromised. Attack graphs describe explicit scenarios in which a single vulnerability exploitation cascades further into the network exploiting inherent dependencies among the network components. Attack graphs are used for studying cascading effects in many cybersecurity applications, e.g., component failure in enterprise networks, botnet spreads, advanced persistent attacks. One distinct feature of cyber attack cascades is the stealthy nature of the attack moves. Also, cyber attacks are generally repeated. How to control stealthy and repeated attack cascades is an interesting problem. Dijk et. al.~cite{van2013flipit} first proposed a game framework called ``FlipIt" for reasoning about the stealthy interaction between a defender and an attacker over the control of a system resource. However, in cybersecurity applications, systems generally consists of multiple resources connected by a network. Therefore it is imperative to study the stealthy attack and defense in networked systems. We develop a generalized framework called ``FlipNet" which extends the work of Dijk et. al.~cite{van2013flipit} for network. We present analyses and algorithms for different problems in this framework. On the other hand, if the security of a system is limited to the vulnerabilities and exploitations that are known to the security community, often the objective of the system owner is to take cost-effective steps to minimize potential damage in the network. This problem has been formulated in the cybersecurity literature as hardening attack graphs. Several heuristic approaches have been shown in the litrature so far but no algorithmic analysis have been shown. We analyze the inherent vulnerability of the network and present approximation hardening algorithms.
    URI
    http://hdl.handle.net/10919/82711
    Collections
    • Doctoral Dissertations [13611]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us