Large scale distributed systems typically have interactions among different services that create an avenue for propagation of a failure from one service to another. The failures being considered may be the result of natural failures or malicious activity, collectively called disruptions. To make these systems tolerant to failures it is necessary to contain the spread of the occurrence automatically once it is detected. The objective is to allow certain parts of the system to continue to provide partial functionality in the system in the face of failures. Real world situations impose several constraints on the design of such a disruption tolerant system of which we consider the following - the alarms may have type I or type II errors;  it may not be possible to change the service itself even though the interaction may be changed; attacks may use steps that are not anticipated a priori; and there may be bursts of concurrent alarms.  We present the design and implementation of a system named ADEPTS as the realization of such a disruption tolerant system. ADEPTS uses a directed graph representation to model the spread of the failure through the system, presents algorithms for determining appropriate responses and monitoring their effectiveness, and quantifies the effect of disruptions through a high level survivability metric. ADEPTS is demonstrated on a real e-commerce testbed with actual attack patterns injected into it.

Self-propagating codes, called worms, such as Code Red, Nimda, and Slammer, have drawn significant attention due to their enormous adverse impact on the Internet. There is a great interest in the research community in modeling the spread of worms and in providing adequate defense mechanisms against them.  In this paper, we present a (stochastic) branching process model for characterizing the propagation of Internet worms. This model leads to the development of an automatic worm containment strategy that prevents the spread of worms beyond its early stages. Specifically, using the branching process model, we are able to (1) provide a precise condition that determines whether the worm will eventually die out and (2) provdide the probability that the total number of hosts that the worm infects will be below a certain level. We use these insights to develop a simple automatic worm containment scheme, which is demonstrated, through simulations and real trace data, to be both effective and non-intrusive.

Since sensor data gathering is the primary functionality of sensor networks, it is important to provide a fault tolerant method for reasoning about sensed events in the face of arbitrary failures of nodes sending in the event reports. In this paper, we propose a protocol called TIBFIT to diagnose and mask arbitrary node failures in an event-driven wireless sensor network. In our system model, sensor nodes are organized into clusters with rotating cluster heads. The nodes, including the cluster head, can fail in an arbitrary manner generating missed event reports, false reports, or wrong location reports. Correct nodes are also allowed to make occasional natural errors. Each node is assigned a trust index to indicate its track record in reporting past events correctly. The cluster head analyzes the event reports using the trust index and makes event decisions. TIBFIT is analyzed and simulated using the network simulator ns-2 and its coverage is evaluated with a varying number and varying intelligence of malicious nodes. We show that once TIBFIT gathers enough system state, accurate event detection is possible even if more than 50% of the network nodes are compromised.

In multihop wireless systems, such as ad-hoc and sensor networks, the need for cooperation among nodes to relay each other

With the development of location aware sensor applications, location determination has become an increasingly important middleware technology.  Numerous current technologies for location determination of sensor nodes use the received signal strength from sensor nodes using omni-directional antennas. However, an increasing number of sensor systems are now deploying directional antennas due to their advantages like energy conservation and better bandwidth utilization.  In this paper, we present techniques for location determination in a sensor network with directional antennas under different kinds of deployment of the nodes. We show how the location estimation problem can be solved by measuring the received signal strength from just one or two anchors in a 2D plane with directional antennas.  We implement our technique using Berkeley MICA2 sensor motes and show that it is up to three times more accurate than triangulation using omni-directional antennas. We also perform Matlab simulations that show the accuracy of location determination with increasing node density.

A large class of sensor networks is used for data collection and aggregation of sensory data about the physical environment. Since sensor nodes are often powered by limited energy sources, such as battery which may be difficult to replace, energy saving is an important criterion in any activity. Some deployments of sensor networks have passive mobile nodes, that is, nodes that are mobile without their own control. For example, a node mounted on an animal for bio-habitat monitoring, or a light-weight node dropped into a river for water quality monitoring. Passive mobility makes the activity of data gathering challenging since the positions of the nodes can change arbitrarily. As a result the nodes may move too far from the data aggregation point, such as a base station, making the data transmission extremely energy intensive. In extreme cases, the nodes may become disconnected from the rest of the network making them unusable. We propose a sensor network architecture with some nodes capable of controlled mobility to solve this problem. Controlled mobility implies the nodes can be moved in a controlled manner in response to commands, with a determined direction, speed, etc.. We present the different categories of nodes in our architecture and mobility algorithms for the two classes, called collector and locator, that have controlled mobility. It is well accepted that efficient data gathering benefits from the knowledge of locations of nodes. Passive mobile nodes makes location determination (i.e. localization) a crucial problem. We propose the use of the locators for this through a novel scheme based on triangulation. We provide theoretical and simulation based analysis of the mobility algorithms with respect to the metrics of energy, latency, and buffer space requirement.

We are witnessing an exponential growth in the use of mobile computing devices such as laptops, PDAs and mobile phones, accessing critical data while on the move. The need to safeguard against unauthorized access to data in a mobile world is a pressing requirement.  Access to critical data depends on users’ identity as well as environmental parameters such as time and location. While temporal based access control models are well suited for enforcing access control decisions on fixed users, they loose their effectiveness when users employing mobile computing devices are not fixed in space and are moving from a secure locale to an insecure one, or vice versa.  Issues of location as a context parameter for access control have been addressed by a number of researchers but definition of rich spatial constraints which effectively capture semantics and relationship of physical and virtual (e.g. membership to an IP group) locales is still missing. The inclusion of multiple constraints (temporal and spatial) to the access control policy exposes the need to be able to compose a policy which is verifiable for consistency and structural integrity.  Further, the access control policy is expected to evolve over time and inclusion of new constraints, permissions or user rights may conflict with the existing ones. In this regard, we draw upon techniques developed for software engineering and use them for policy specification modeling and conflict resolution. The first contribution in this paper is the development of the Generalized Spatio-Temporal Role Based Access Control (GST-RBAC) model, by proposing a formal framework for composition of complex spatial constraints exploiting topological relationship between physical and virtual locales. Spatial constraints are defined for spatial role enabling, spatial user-role assignment, spatial role-permission assignment and spatial activation of roles. The notion of spatial separation of duty is also developed whereby a user is not permitted to activate two roles simultaneously if the roles are being activated from specific locales. Another feature of the proposed GST-RBAC is the spatial role hierarchy, which allows inheritance of permissions between roles, contingent upon roles being activated from predefined locales. The second contribution in this paper is GST-RBAC policy specification framework using light weight formal modeling language, Alloy and, analysis of access control policy model using the accompanying constraint analyzer. In addition, for consistent evolution of access control policy, the policy administrator can specify additional policy fragments in the policy model and can verify consistency of the overall policy for conflict free composition of the actual policy.

An efficient recovery protocol for lost messages is crucial for supporting reliable multicasting. The tree-  based recovery protocols group nodes into recovery regions and designate a recovery node per region for buffering and retransmitting lost messages. In these protocols, the recovery host may get overloaded during periods of large message losses and costly remote recovery may be initiated even though a peer node has the lost message. To address these drawbacks, the Randomized Reliable Multicast Protocol (RRMP) was proposed which distributes the responsibility of error recovery among all members in a group. The pressure on the buffer and computational resources on the intermediate nodes is increasing due to the wide distribution of multicast participants with widely varying reception rates and periodic disconnections. In this paper, we propose the Lightweight Randomized Reliable Multicast (LRRM) protocol that optimizes the amount of buffer space by providing an efficient mechanism based on best-effort multicast for retrieving a lost message. A theoretical analysis and a simulation based study of two realistic topologies indicate that LRRM provides comparable recovery latency to RRMP for lower buffer space usage. While presented in the context of RRMP, LRRM can also benefit other tree-  based reliable multicast protocols.

Sensor networks enable a wide range of applications in both military and civilian domains. However, the deployment scenarios, the functionality requirements,  and the limited capabilities of these networks expose them to a wide-range of attacks against control traffic (such as wormholes, Sybil attacks, rushing attacks,  etc). In this paper we propose a lightweight protocol called DICAS that mitigates these attacks by detecting,  diagnosing, and isolating the malicious nodes. DICAS uses as a fundamental building block the ability of a node to oversee its neighboring nodes

Although the k-anonymity and l-diversity models have led to a number of valuable privacy-protecting techniques and algorithms, the existing solutions are currently limited to static data release. That is, it is assumed that a complete dataset is available at the time of data release. This assumption implies a significant shortcoming, as in many applications data collection is rather a continual process. Moreover, the assumption entails ``one-time’’ data dissemination; thus, it does not adequately address today’s strong demand for immediate and up-to-date information. In this paper, we consider incremental data dissemination, where a dataset is continuously incremented with new data. The key issue here is that the same data may be anonymized and published multiple times, each of the time in a different form. Thus, static anonymization (i.e., anonymization which does not consider previously released data) may enable various types of inference. In this paper, we identify such inference issues and discuss some prevention methods.

With a widespread growth in the potential applications of Wireless Sensor Networks (WSN), the need for reliable security mechanisms for them has increased manifold. Security protocols in WSNs, unlike the traditional mechanisms, need special efforts and issues to be addressed. This is attributed to the inherent computational and communicational constraints in these tiny embedded system devices. Another reason which distinguishes them from traditional network security mechanisms, is their usage in extremely hostile and unattended environments. The sensitivity of the data sensed by these devices also pose ever-increasing challenges. We present a layer based classification of WSN security threats and defenses proposed in the literature, with special focus on physical, link and network layer issues.

Li, Zhihong. Ph.D., Purdue University, December, 2006. Elliptic Curve Factoring Method via FFTs with Division Polynomials. Major Professor: Samuel S. Wagstaff, Jr.. In 1985, H. W. Lenstra, Jr. discovered a new factoring method, the Elliptic Curve Method (ECM), which efficiently finds 20- to 30- digit prime factors. On January 15, 2001, C. P. Schnorr proposed an idea to apply division polynomials for ECM. In this thesis, we modify and implement the idea in detail, analyze the complexity of the algorithm and the probability of success. We first extend the concept of division polynomial to a univariate case with the parameter a in the Weierstrass form y2 = x3 +ax+b as the variable. We generalize a result about the degree of this implied univariate division polynomial. Then we discover an algorithm to efficiently generate the m-th univariate division polynomial and determine the complexity of the algorithm. We then present the main algorithm of this thesis, which is the main result of the thesis as well. We demonstrate in both algebraic and geometric ways the sufficient conditions for the algorithm to be successful. We analyze the probability of success and prove the related results. To demonstrate the structure of the main algorithm, we divide it to several parts and introduce every part in detail. Then we propose and prove a theorem about the complexity of the main algorithm. We also present an optimization of the main algorithm for a family of numbers with specific form. This family is of great interest as well. We show that for this family, the optimal algorithm can factor numbers even faster and also remove the memory restriction of the multiple m of the point on the elliptic curves, which is also the index of the implied division polynomial being used. vii At the end, we address some issues related to the implementation of the algorithm. With the algorithm, we can find some 40-digit primes on a 1.86GHz 1066FBS PC with 4GB DDR2 SDRAM at 533MHz. It also finds some 50-digit primes. Now we are trying the algorithm on 60-digit primes and we hope that the algorithm will find some 70-digit primes.

Koglin, Yunhua Ph.D., Purdue University, December, 2006. Security Mechanisms for Content Distribution Networks. Major Professor: Elisa Bertino. Securing data is becoming a crucial need for most internet-based applications. In this research, we investigate security mechanisms for content distribution networks. We address the problem of how to ensure that data, when moving among di erent parties, are modi ed only according to the stated policies. We cast our solution in supporting parallel and distributed secure updates to XML documents. The approach, based on the use of a security region-object parallel ow (S-RPF) graph protocol, allows di erent users to simultaneously update di erent portions of the same document, according to the speci ed access control policies. It ensures data con dentiality and integrity. Additionally, it supports a decentralized management of update operations in that a subject can exercise its privileges and verify the correctness of the operations performed so far on the document without interacting, in most of the cases, with the document server. We then extend our document update application into Byzantine and failure prone systems by removing the trusted party which is responsible for recovery of the document. We have developed an approach which uses a group of delegates for recovering documents. Many optimizations have been provided. We improve previous solutions by proposing a scalable distributed protocol which uses cryptographic techniques to provide dynamic group communications, participating anonymity and completeness, and privacy on access privileges. Other security problems such as con dentiality and availability are also investigated in the application of content-based publish/subscribe (pub/sub) systems. We propose a hierarchical event forwarding scheme which increases system availability by x
tolerating some broker failures. Our approach can e ciently determine the subscription groups to which an event must be delivered by exploiting locality. Moreover, we propose an e cient encryption scheme, under which a broker encrypts an event only once. The encryption key can be e ciently derive