Cloud service providers enable tenants to elastically scale resources to meet their demands. While running cloud applications, a tenant aiming to minimize cost is often challenged with crucial tradeoffs. For instance, upon each arrival of a query, a Web application can either choose to pay for CPU to compute the response fresh, or pay for cache storage to store the response to reduce future compute costs. The Ski-Rental problem abstracts such scenarios where a tenant is faced with a to-rent-or-to-buy tradeoff; in its basic form, a skier should choose between renting or buying a set of skis without knowing the number of days she will be skiing. In the multislope version of the Ski-Rental problem, the skier can choose among multiple services that differ in their buying and renting prices. In this paper, we introduce a variant of the classical Ski-Rental problem in which we assume that the skier knows the first (or second) moment of the distribution of the number of ski days in a season. We also extend the classical multislope Ski-Rental problem, where the skier can choose among multiple services, to this setting. We demonstrate that utilizing this information leads to achieving the best worst-case expected competitive ratio performance. Our method yields a new class of randomized algorithms that provide arrivals-distribution-free performance guarantees. Simulations illustrate that our scheme exhibits robust average-cost performance that combines the best of the well-known deterministic and randomized schemes previously proposed to tackle the Ski-Rental problem.

Using geosocial applications, such as FourSquare, millions of people interact with their surroundings through their friends and their recommendations. Without adequate privacy protection, however, these systems can be easily misused, for example, to track users or target them for home invasion. In this paper, we introduce LocX, a novel alternative that provides significantly improved location privacy without adding uncertainty into query results or relying on strong assumptions about server security. Our key insight is to apply secure user-specific, distance-preserving coordinate transformations to all location data shared with the server. The friends of a user share this user's secrets so they can apply the same transformation. This allows all location queries to be evaluated correctly by the server, but our privacy mechanisms guarantee that servers are unable to see or infer the actual location data from the transformed data or from the data access. We show that LocX provides privacy even against a powerful adversary model, and we use prototype measurements to show that it provides privacy with very little performance overhead, making it suitable for today's mobile devices.

Preventing flow of confidential data out of a network is a fundamental problem faced by network operators. This problem gets even more complex in the context of Cloud Computing, where multiple distrusting customers share the same underlying infrastructure, and data is often replicated and moved across regions. Despite the significance of this problem, existing solutions are based on generic search for keywords in outgoing data, and hence severely lack the ability to control data flow at a fine granularity with low false positives. In this paper, we advocate a fine-grained approach to prevent confidential data from leaking out of the cloud. We propose a solution using document-level fingerprint checks. We show via analysis and experiments that our algorithm for checking the fingerprints on-the-fly scale to a large amount of documents at very low cost. For example, for one TB of documents, our solution only requires 340 MB memory to achieve worst case expected detection lag (i.e. leakage length) of 1000 bytes.

Cloud service providers (CSPs) enable tenants to elastically scale their resources to meet their demands. In fact, there are various types of resources offered at various price points. While running applications on the cloud, a tenant aiming to minimize cost is often faced with crucial trade-off considerations. For instance, upon each arrival of a query, a web application can either choose to pay for CPU to compute the response fresh, or pay for cache storage to store the response so as to reduce the compute costs of future requests. The SkiRental problem abstracts such scenarios where a tenant is faced with a to-rent-or-to-buy trade-off; in its basic form, a skier should choose between renting or buying a set of skis without knowing the number of days she will be skiing. In this paper, we introduce a variant of the classical SkiRental problem in which we assume that the skier knows the first (or second) moment of the distribution of the number of ski days in a season. We demonstrate that utilizing this information leads to achieving the best worst-case expected competitive ratio (CR) performance. Our method yields a new class of randomized algorithms that provide arrivals-distribution-free performance guarantees. Further, we apply our solution to a cloud file system and demonstrate the cost savings obtained in comparison to other competing schemes. Simulations illustrate that our scheme exhibits robust average-cost performance that combines the best of the well-known deterministic and randomized schemes previously proposed to tackle the Ski-Rental problem.

Geographically distributed storage is an important method of ensuring high data availability in cloud computing and storage systems. With the increasing demand for moving file systems to the cloud, current methods of providing such enterprise-grade resiliency are very inefficient. For example, replication based methods incur large storage cost though they provide low access latencies. While erasure coded schemes reduce storage cost, they are associated with large access latencies and high bandwidth cost. In this paper, we propose a novel scheme named CAROM, an ensemble of replication and erasure codes, to provide resiliency in cloud file systems with high efficiency. While maintaining the same consistency semantics seen in today's cloud file systems, CAROM provides the benefit of low bandwidth cost, low storage cost, and low access latencies. We perform a large-scale evaluation using real-world file system traces and demonstrate that CAROM outperforms replication based schemes in storage cost by up to 60% and erasure coded schemes in bandwidth cost by up to 43%, while maintaining low access latencies close to those in replication based schemes.

Cloud service providers (CSP) of today operate multiple data centers, over which they provide resilient infrastructure, data storage and compute services. The links between data centers have very high capacity, and are typically purchased by the CSPs using established billing practices, such as 95-thpercentile billing or average-usage billing. These links are used to serve both client traffic as well as CSP-specific bulk data traffic, such as backup jobs, etc. Past studies have shown a diurnal pattern of traffic over such links. However, CSPs pay for the peak bandwidth, which implies that they are under-utilizing the capacity for which they have paid for. We propose a scheduling framework that considers various classes of jobs that are encountered over such links, and propose GRESE, an algorithm that attempts to minimize overall bandwidth costs to the CSP, by leveraging the flexible nature of the deadlines of these bulk data jobs. We demonstrate the problem is not a simple extension of any well-known scheduling problems, and show how the GRESE algorithm is effective in curtailing CSP bandwidth costs.

Enterprises are moving their IT infrastructure to cloud service providers with the goal of saving costs and simplifying management overhead. One of the critical services for any enterprise is its file system, where users require real-time access to files. Cloud service providers provide several building blocks such as Amazon EBS, or Azure Cache, each with very different pricing structures that differ on the basis of storage, access and bandwidth costs. Moving an entire file system to the cloud using such services is not cost-optimal if we rely on only one of these services. In this paper, we propose FCFS, a storage solution that drastically reduces the cost of operating a file system in the cloud. Our solution integrates multiple storage services and dynamically adapts the storage volume sizes of each service to provide a cost-efficient solution with provable performance bounds. Using real-world large scale data sets spanning a variety of work loads from an enterprise data center, we show that FCFS can reduce file storage and access costs in current cloud services by a factor of two or more, while allowing users to utilize the benefits of the various cloud storage services.

Social networks are popular platforms for interaction, communication, and collaboration between friends. Researchers have recently proposed an emerging class of applications that leverage relationships from social networks to improve security and performance in applications such as email, Web browsing, and overlay routing. While these applications often cite social network connectivity statistics to support their designs, researchers in psychology and sociology have repeatedly cast doubt on the practice of inferring meaningful relationships from social network connections alone. This leads to the question: “Are social links valid indicators of real user interaction? If not, then how can we quantify these factors to form a more accurate model for evaluating socially enhanced applications?” In this article, we address this question through a detailed study of user interactions in the Facebook social network. We propose the use of “interaction graphs” to impart meaning to online social links by quantifying user interactions. We analyze interaction graphs derived from Facebook user traces and show that they exhibit significantly lower levels of the “small-world” properties present in their social graph counterparts. This means that these graphs have fewer “supernodes” with extremely high degree, and overall graph diameter increases significantly as a result. To quantify the impact of our observations, we use both types of graphs to validate several well-known social-based applications that rely on graph properties to infuse new functionality into Internet applications, including Reliable Email (RE), SybilGuard, and the weighted cascade influence maximization algorithm. The results reveal new insights into each of these systems, and confirm our hypothesis that to obtain realistic and accurate results, ongoing research on social network applications studies of social applications should use real indicators of user interactions in lieu of social graphs.

By offering high availability and elastic access to resources, third-party cloud infrastructures such as Amazon EC2 are revolutionizing the way today's businesses operate. Unfortunately, taking advantage of their benefits requires businesses to accept a number of serious risks to data security. Factors such as software bugs, operator errors and external attacks can all compromise the confidentiality of sensitive application data on external clouds, by making them vulnerable to unauthorized access by malicious parties.

We ask the question: can network problems experienced by applications be identified based on symptoms contained in a network packet trace? An answer in the affirmative would open the doors to many opportunities, including non-intrusive monitoring of such problems on the network and matching a problem with past instances of the same problem.

Docx2Go is a new framework to support editing of shared documents on mobile devices. Three high-level requirements influenced its design -- namely, the need to adapt content, especially textual content, on the fly according to the quality of the network connection and the form factor of each device; support for concurrent, uncoordinated editing on different devices, whose effects will later be merged on all devices in a convergent and consistent manner without sacrificing the semantics of the edits; and a flexible replication architecture that accommodates both device-to-device and cloud-mediated synchronization. Docx2Go supports on-the-go editing for XML documents, such as documents in Microsoft Word and other commonly used formats. It combines the best practices from content adaptation systems, weakly consistent replication systems, and collaborative editing systems, while extending the state of the art in each of these fields. The implementation of Docx2Go has been evaluated based on a workload drawn from Wikipedia.

Mobile devices often store data in reduced resolutions or custom formats in order to accommodate resource constraints and tailor-made software. The Polyjuz framework enables sharing and synchronization of data across a collection of personal devices that use formats of different fidelity. Layered transparently between the application and an off-the-shelf replication platform, Polyjuz bridges the isolated worlds of different data formats. With Polyjuz, data items created or updated on high-fidelity devices-such as laptops and desktops-are automatically replicated onto low-fidelity, mobile devices. Similarly, data items updated on low-fidelity devices are reintegrated with their high-fidelity counterparts when possible. Polyjuz performs these fidelity reductions and reintegrations as devices exchange data in a peer-to-peer manner, ultimately extending the eventual-consistency guarantee of the underlying replication platform to the multifidelity universe. In this paper, we present the design and implementation of Polyjuz and demonstrate its benefits for fidelity-aware contacts management and picture sharing applications.

Building on the popularity of online social networks (OSNs) such as Facebook, social content-sharing applications allow users to form communities around shared interests. Millions of users worldwide use them to share recommendations on everything from music and books to resources on the web. However, their increasing popularity is beginning to attract the attention of malicious attackers. As social network credentials become valued targets of phishing attacks and social worms, attackers look to leverage compromised accounts for further financial gain.

Social networks are popular platforms for interaction, communication and collaboration between friends. Researchers have recently proposed an emerging class of applications that leverage relationships from social networks to improve security and performance in applications such as email, web browsing and overlay routing. While these applications often cite social network connectivity statistics to support their designs, researchers in psychology and sociology have repeatedly cast doubt on the practice of inferring meaningful relationships from social network connections alone.

Deployed anonymous networks such as Tor focus on delivering messages through end-to-end paths with high anonymity. Selection of routers in the anonymous path construction is either performed randomly, or relies on self-described resource availability at routers, making systems vulnerable to low-resource attacks. In this paper, we investigate an alternative router and path selection mechanism for constructing efficient end-to-end paths with low loss of path anonymity. We propose a novel construct called a "route mesh," and a dynamic programming algorithm that determines optimal-latency paths from many random samples using only a small number of end-to-end measurements. We prove analytically that our path search algorithm finds the optimal path, and requires exponentially lower number of measurements compared to a standard measurement approach. In addition, our analysis shows that route meshes incur only a small loss in anonymity for its users.

Structured overlay networks can greatly simplify data storage and management for a variety of distributed applications. Despite their attractive features, these overlays remain vulnerable to the Identity attack, where malicious nodes assume control of application components by intercepting and hijacking key-based routing requests. Attackers can assume arbitrary application roles such as storage node for a given file, or return falsified contents of an online shopper's shopping cart. In this paper, we define a generalized form of the Identity attack, and propose a lightweight detection and tracking system that protects applications by redirecting traffic away from attackers. We describe how this attack can be amplified by a Sybil or Eclipse attack, and analyze the costs of performing such an attack. Finally, we present measurements of a deployed overlay that show our techniques to be significantly more lightweight than prior techniques, and highly effective at detecting and avoiding both single node and colluding attacks under a variety of conditions.

Peer-to-peer anonymous networks offer the resources to support todaypsilas Internet applications. In todaypsilas dynamic networks, the key challenge to these systems arises from node dynamics and failures that disrupt anonymous routing paths, forcing them to be frequently rebuilt. Not only do these path rebuilds interrupt application sessions, but they also leak information to logging attacks such as the predecessor attack, leading to significant degradation of anonymity over long sessions. In this paper, we propose Bluemoon, a new anonymous protocol that provides strong resilience against the predecessor attack through the use of persistent anonymous links called hooks. When chained together, these links create robust anonymous paths that avoid path disruptions and rebuilds across node failures. Through detailed analysis, we show that relative to prior approaches, Bluemoon provides significantly stronger resistance against predecessor attacks. Finally, we implement and deploy a prototype on both local and Internet-scale network testbeds, and show that it provides high throughput even in high-load environments such as PlanetLab.

Searching for objects is a fundamental problem for popular peer-to-peer file-sharing networks that contribute to much of the traffic on today's Internet. While existing protocols can effectively locate highly popular files, studies show that they fail to locate a significant portion of existing files in the network. High recall for these "rare" objects would drastically improve the user experience, and make these networks the ideal distribution infrastructure for user-generated content such as home videos and photo albums. In this paper, we examine simple techniques that can improve search recall for rare objects while minimizing the overhead incurred by participating peers. We propose several strategies for multi-hop index replication, and demonstrate their effectiveness and efficiency through both analysis and simulation. We further evaluate our simple techniques using detailed traces from a real Gnutella network, and show that they improve the performance of these overlays by orders of magnitude in both lookup success and overhead.