Persistent and zero-day attacks have increased considerably in the recent past in terms of scale and impact. Security experts can no longer rely only on known defenses and thereby protect their resources permanently. It is increasingly common now to observe attackers being able to repeatedly break systems exploiting new vulnerabilities and defenders hardening systems with new measures. To model this phenomenon of the repeated takeover of the computing resources by system administrators and malicious attackers, a novel game framework, FlipIt, has been proposed by (Van Dijk et al. 2013) for a system consisting of a single resource. In this paper, we extend this and develop FlipNet, which is a repeated game framework for a networked system of multiple resources. This game involves two players-a defender and an attacker. Each player's objective is to maximize its gain (i.e., its control over the nodes in the network with stealthy moves), while minimizing the cost for making those moves. This leads to a novel and natural game formulation, with a very complex strategy space, that depends on the network structure. We show that finding the best response strategy for both the defender and attacker is NP-hard. In a key result in this study, we show that the attacker's gain for an instance of the game has a type of diminishing marginal return property, which leads to a near-optimal algorithm for maximizingthe attacker's gain. We examine the impact of network structure on the strategy space using simulations.

Given a network with groups, such as a contact-network grouped by ages, which are the best groups to immunize to control the epidemic? Equivalently, how to choose best communities in social media like Facebook to stop rumors from spreading? Immunization is an important problem in multiple different domains like epidemiology, public health, cyber security, and social media. Additionally, clearly immunization at group scale (like schools and communities) is more realistic due to constraints in implementations and compliance (e.g., it is hard to ensure specific individuals take the adequate vaccine). Hence, efficient algorithms for such a “group-based” problem can help public-health experts take more practical decisions. However, most prior work has looked into individual-scale immunization. In this paper, we study the problem of controlling propagation at group scale. We formulate a set of novel Group Immunization problems for multiple natural settings (for both threshold and cascade-based contagion models under both node-level and edge-level interventions) and develop multiple efficient algorithms, including provably approximate solutions. Finally, we show the effectiveness of our methods via extensive experiments on real and synthetic datasets.

The largest eigenvalue of the adjacency matrix of a network (referred to as the spectral radius) is an important metric in its own right. Further, for several models of epidemic spread on networks (e.g., the ‘flu-like’ SIS model), it has been shown that an epidemic dies out quickly if the spectral radius of the graph is below a certain threshold that depends on the model parameters. This motivates a strategy to control epidemic spread by reducing the spectral radius of the underlying network. In this paper, we develop a suite of provable approximation algorithms for reducing the spectral radius by removing the minimum cost set of edges (modeling quarantining) or nodes (modeling vaccinations), with different time and quality tradeoffs. Our main algorithm, GREEDYWALK, is based on the idea of hitting closed walks of a given length, and gives an O(log2 n)-approximation, where n denotes the number of nodes; it also performs much better in practice compared to all prior heuristics proposed for this problem. We further present a novel sparsification method to improve its running time. In addition, we give a new primal-dual based algorithm with an even better approximation guarantee (O(log n)), albeit with slower running time. We also give lower bounds on the worst-case performance of some of the popular heuristics. Finally we demonstrate the applicability of our algorithms and the properties of our solutions via extensive experiments on multiple synthetic and real networks.

The spread of epidemics and malware is commonly modeled by diffusion processes on networks. Protective interventions such as vaccinations or installing anti-virus software are used to contain their spread. Typically, each node in the network has to decide its own strategy of securing itself, and its benefit depends on which other nodes are secure, making this a natural game-theoretic setting. There has been a lot of work on network security game models, but most of the focus has been either on simplified epidemic models or homogeneous network structure. We develop a new formulation for an epidemic containment game, which relies on the characterization of the SIS model in terms of the spectral radius of the network. We show in this model that pure Nash equilibria (NE) always exist, and can be found by a best response strategy. We analyze the complexity of finding NE, and derive rigorous bounds on their costs and the Price of Anarchy or PoA (the ratio of the cost of the worst NE to the optimum social cost) in general graphs as well as in random graph models. In particular, for arbitrary power-law graphs with exponent $\beta>2$, we show that the PoA is bounded by $O(T^{2(\beta-1)})$, where $T=\gamma/\alpha$ is the ratio of the recovery rate to the transmission rate in the SIS model. We prove that this bound is tight up to a constant factor for the Chung-Lu random power-law graph model. We study the characteristics of Nash equilibria empirically in different real communication and infrastructure networks, and find that our analytical results can help explain some of the empirical observations.

We describe a first principles based integrated modeling environment to study urban socio-communication networks which represent not just the physical cellular communication network, but also urban populations carrying digital devices interacting with the cellular network. The modeling environment is designed specifically to understand spectrum demand and dynamic cellular network traffic. One of its key features is its ability to support individual-based models at highly resolved spatial and temporal scales. We have instantiated the modeling environment by developing detailed models of population mobility, device ownership, calling patterns and call network. By composing these models using an appropriate in-built workflow, we obtain an integrated model that represents a dynamic socio-communication network for an entire urban region. In contrast with earlier papers that typically use proprietary data, these models use open source and commercial data sets. The dynamic model represents for a normative day, every individual in an entire region, with detailed demographics, a minute-by-minute schedule of each person's activities, the locations where these activities take place, and calling behavior of every individual. As an illustration of the applicability of the modeling environment, we have developed such a dynamic model for Portland, Oregon comprising of approximately 1.6 million individuals. We highlight the unique features of the models and the modeling environment by describing three realistic case studies.

Attackers, in particular botnet controllers, use stealthy messaging systems to set up large-scale command and control. To systematically understand the potential capability of attackers, we investigate the feasibility of using domain name service (DNS) as a stealthy botnet command-and-control channel. We describe and quantitatively analyze several techniques that can be used to effectively hide malicious DNS activities at the network level. Our experimental evaluation makes use of a two-month-long 4.6-GB campus network data set and 1 million domain names obtained from alexa.com. We conclude that the DNS-based stealthy command-and-control channel (in particular, the codeword mode) can be very powerful for attackers, showing the need for further research by defenders in this direction. The statistical analysis of DNS payload as a countermeasure has practical limitations inhibiting its large-scale deployment.

Hidden stop codons are nucleotide triples TAA, TAG, and TGA that appear in the second and third reading frames of a protein coding gene. Recent studies reported biological evidence suggesting that hidden stop codons are important in preventing misread of mRNA, which is often detrimental to the cell. We study the problem of designing protein-encoding genes with large number of hidden stop codons under biological constraints including GC content and codon usage of individual organism. In simpler models, we obtained provably optimal results. In more complex models, the designed genes have many more hidden stop codons than wild-type genes do, as observed in an experiment with 8 genomes with a wide range of GC content and codon usage.