Search

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.

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.

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.

We investigate efficient security control methods for protecting against vulnerabilities in networked systems. A large number of interdependent vulnerabilities typically exist in the computing nodes of a cyber-system; as vulnerabilities get exploited, starting from low level ones, they open up the doors to more critical vulnerabilities. These cannot be understood just by a topological analysis of the network, and we use the attack graph abstraction of [1] to study these problems. In contrast to earlier approaches based on heuristics and evolutionary algorithms, we study rigorous methods for quantifying the inherent vulnerability and hardening cost for the system. We develop algorithms with provable approximation guarantees, and evaluate them for real and synthetic attack graphs.

Representation and propagation of uncertainty in cyber attacker payoffs is a key aspect of security games. Past research has primarily focused on representing the defender's beliefs about attacker payoffs as point utility estimates. More recently, within the physical security domain, attacker payoff uncertainties have been represented as Uniform and Gaussian probability distributions, and intervals. Within cyber-settings, continuous probability distributions may still be appropriate for addressing statistical (aleatory) uncertainties where the defender may assume that the attacker's payoffs differ over time. However, systematic (epistemic) uncertainties may exist, where the defender may not have sufficient knowledge or there is insufficient information about the attacker's payoff generation mechanism. Such epistemic uncertainties are more suitably represented as probability boxes with intervals. In this study, we explore the mathematical treatment of such mixed payoff uncertainties.

Market based spectrum allocation should be competitive and economically efficient to effectively use the spectrum. Yet infrastructure markets have a tendency to become natural monopolies or oligopoly due to the high fixed costs and inherent economies of scale. Instruments such as set-asides, bidding credits, spectrum caps, band plan and auction designs are some of the market-based solutions that can enhance competition by incentivizing new entrants in these types of markets. In this paper, we focus on the “set-aside” instrument and study its role as a policy instrument to promote competition and encourage entry of new enterprenuers. The experimental results show that “set-aside” can be a powerful instrument and its impact depends upon the number of licenses that are set-aside versus the number of new entrants in the market as well as the level of competitiveness of the new entrants. We use a three factorial experimental design and find that contrary to our expectation, the total revenue generated by FCC does not necessarily decrease by having set-asides. As the number of new entrants increase and the set-asides decrease, the average total revenue raised through the sale of licenses can be more than the base case.

Improving spectrum utilization is essential to meet the ever growing demand for wireless spectrum. FCC currently sells licenses for spectrum bands in the “primary market” on a long term basis, and over large regions; these can lead to localized surpluses and deficits, and “secondary markets” have been proposed for trading them. Such trading can be done at different spatial and temporal granularity, and the trading in the primary and secondary markets can have significant influence on each other. This makes the task of designing effective trading schemes and evaluating their effectiveness very challenging. In this paper, we develop an integrated framework for primary and secondary markets, and use it to study dynamic spectrum access for large urban regions; our framework gives a systematic approach to couple the two markets, and study interaction between them. We use this to study the extent to which finer spatial and temporal partitioning at the secondary market level helps in increasing the spectrum utilization. We find that, in general, the spectrum utilization improves and the total cost reduces with the granularity of partitioning, but the gains depend on the particular interference model.

In this paper, we conduct a systematic study of human-initiated cascading failures in three critical inter-dependent societal infrastructures due to behavioral adaptations in response to a crisis. We focus on three closely coupled socio-technical networks here: (i) cellular and mesh networks, (ii) transportation networks and (iii) mobile call networks. In crises, changes in individual behaviors lead to altered travel, activity and calling patterns, which influence the transport network and the loads on wireless networks. The interaction between these systems and their co-evolution poses significant technical challenges for representing and reasoning about these systems. In contrast to system dynamics models for studying these interacting infrastructures, we develop interaction-based models in which individuals and infrastructure elements are represented in detail and are placed in a common geographic coordinate system. Using the detailed representation, we study the impact of a chemical plume that has been released in a densely populated urban region. Authorities order evacuation of the affected area, and this leads to individual behavioral adaptation wherein individuals drop their scheduled activities and drive to home or pre-specified evacuation shelters as appropriate. They also revise their calling behavior to communicate and coordinate among family members. These two behavioral adaptations cause flash-congestion in the urban transport network and the wireless network. The problem is exacerbated with a few, already occurring, road closures. We analyze how extended periods of unanticipated road congestion can result in failure of infrastructures, starting with the servicing base stations in the congested area. A sensitivity analysis on the compliance rate of evacuees shows non-intuitive effect on the spatial distribution of people and on the loading of the base stations. For example, an evacuation compliance rate of 70% results in higher number of overloaded base stations than the evacuation compliance rate of 90%.

This research examines the impact of demand bids which account for geographic complementarity in spectrum demand, on the allocation and pricing of wireless spectrum licenses. Using an individual based simulation environment and a model of spectrum demand for the region of Portland, OR, we study a primary market to allocate spectrum licenses to wireless service providers. A truthful and efficient market clearing mechanism is used to sell the available licenses. A demand estimation model creates spatial and temporal demand estimates for each of the service providers. A valuation system determines the marginal value of each license which is further used in the bidding process. Three different scenarios are considered. First, the entire city of Portland is considered as one region and the estimated demand for this region is used to construct bids. The auction determines the clearing price for each license and the winner of the licenses based on the marginal valuations. After the market clearing is done and license allocations are made, we measure the total cost of licenses to the providers, the amount of unused capacity, and the number of unserved calls. In the second scenario, the city is divided into 2 regions in such a way that the number of call pairs are minimized across regions. Each region is auctioned separately. The providers can now decide their valuations sequentially for each region, so that they can use information on the allocations of the first region to optimally bid in the second region. The same set of measurements are taken again to understand the social impact of this scenario in comparison to the fist one. Finally a third scenario is run which is just like the second scenario but the city is now split into 2 regions in such a way that the call density and population is split evenly between regions. Results from the three scenarios are compared and analyzed to determine the impact of geographically complementary demand bids on the social cost and capacity used.

The purpose of an authentication system is to identify and verify incoming authentication requests comparing with some form of (stored) user identity. This stored user profile is at risk of being hacked and exploited by the attackers. The Negative Filtering or Negative Authentication (NA) approach utilizes a form of complement profiles which resembles the censoring and maturation process of T-cells in the immune system. The scope and applicability issues of this approach in the context of existing (positive) authentication systems have been discussed. The negative authentication is implemented using a real-valued negative selection algorithm [1]. The performance of the technique along with security considerations has been analyzed and feasible configuration settings are reported.

Password authentication is very critical for secure access to computing systems/servers as it verifies the identity of users and processes. Most authentication systems use some form of Positive Authentication (PA) to identify legitimate users. Specifically, these systems use a password profile containing all of the user passwords that are authorized to access the system (or the server). The negative counterpart (non-self/anti-password space) represents strings that are not in the password file (which can possibly be exploited by hackers using password guessing or cracking tools). This paper describes a biologically-inspired authentication technique based on the negative (anti-password) concept. The goal is to keep the anti-password checking as the first line of authentication (invisible to users) and be kept in a separate machine (probably outside the secure perimeter), while the PA system should be inside the highly secure region.