Plausibly deniable communication solutions built on services popular in Western countries may invite closer scrutiny into the activities of their users in censored countries. This paper investigates the ability of popular single-player games to provide the medium for plausibly deniable communications. We introduce Trilobyte, a system that hides data in game state generated opportunistically during regular game-playing activities, and shares data-hiding state through accounts on gaming platforms. We show that even in the presence of hypothetical censors that inspect game state, Trilobyte can hide up to 5.3 MB of data in game state saved in a one hour gaming session. We investigate the practicality of Trilobyte through surveys with 285 Chinese gamers, and by renting and purchasing thousands of gaming accounts. We find that most investigated games, including games developed in China, allow users to communicate keywords considered sensitive in China, when compressed, encrypted or hidden in game state or chat channels.

Plausibly-deniable (PD) storage systems allow users to securely hide data and plausibly deny its presence when challenged by adversaries who coerce them to provide encryption keys and passwords. However, PD systems need specialized software that renders them detectable by suspicious adversaries questioning the very use of a PD system. To address this fundamental problem, we introduce and formally define the notion of plausible invisibility, preventing adversaries from determining whether a PD system was used in the first place. We develop INVISILINE, a plausibly invisible system resilient against multi-snapshot adversaries that can access the device multiple times. To remain invisible, INVISILINE uses a data layout and encoding that is compatible with the Linux dmcrypt disk encryption subsystem, and stores hidden data in the initialization vectors used by dm-crypt to encrypt public data. INVISILINE ensures that any disk changes that result from changes to the hidden data between adversary snapshots, can be plausibly explained using changes to public data resulting from regular use of dm-crypt. In the presence of adversaries, INVISILINE enables users to access all and only the public data using only dm-crypt. INVISILINE can securely and invisibly hide 19GB on a 1TB disk with no impact on public data I/O, and an average of 4.5MB/s throughput for writing hidden data.

Clients of outsourced databases need Query Authentication (QA) guaranteeing the integrity and authenticity of query results returned by potentially compromised providers. Prior work provides QA assurances for a limited class of queries by deploying several software-based cryptographic constructs. The constructs are often designed assuming read-only or infrequently updated databases. For dynamic datasets, the data owner is required to perform all updates on behalf of clients. Hence, for concurrent updates by multiple clients, such as for OLTP workloads, existing QA solutions are inefficient. We present ConcurDB, a concurrent QA scheme that enables simultaneous updates by multiple clients. To realize concurrent QA, we have designed several new mechanisms. First, we identify and use an important relationship between QA and memory checking to decouple query execution and verification. We allow clients to execute transactions concurrently and perform verifications in parallel using an offline memory checking based protocol. Then, to extend QA to a multi-client scenario, we design new protocols that enable clients to securely exchange a small set of authentication data even when using the untrusted provider as a communication hub. Finally, we overcome provider-side replay attacks. Using ConcurDB, we provide and evaluate concurrent QA for the full TPC-C benchmark. For updates, ConcurDB shows a 4x performance increase over existing solutions.

Clouds and massive-scale computing infrastructures are starting to dominate computing and will likely continue to do so for the foreseeable future. Major cloud operators are now comprising millions of cores hosting substantial fractions of corporate and government IT infrastructure.

Abstract Protecting sensitive data stored on local storage devices e.g., laptops, tablets etc. is essential for privacy. When adversaries are powerful enough to coerce users to reveal encryption keys/passwords, encryption alone becomes insufficient for data protection. Additional mechanisms are required to hide the very presence of sensitive data. Plausibly deniable storage systems (PDS) are designed to defend against such powerful adversaries. Plausible deniability allows a user to deny the existence of certain stored data even when an adversary has access to the storage medium. However, existing plausible deniability solutions leave users at the mercy of adversaries suspicious of their very use. Indeed, it may be difficult to justify the use of a plausible deniability system while claiming that no sensitive data is being hidden. This work introduces INFUSE, a plausibly-deniable file system that hides not only contents but also the evidence that a particular system is being used to hide data. INFUSE is “invisible” (identical layout with standard file system), provides redundancy, handles overwrites, survives data loss, and is secure in the presence of multi-snapshot adversaries. INFUSE is efficient. Public data operations are orders of magnitude faster than existing multi-snapshot resilient PD systems, and only 15% slower than a standard non-PD baseline, and hidden data operations perform comparably to existing systems.

Oblivious RAMs (ORAMs) allow a client to access data from an untrusted storage device without revealing the access patterns. Typically, the ORAM adversary can observe both read and write accesses. Write-only ORAMs target a more practical, multi-snapshot adversary only monitoring client writes – typical for plausible deniability and censorship-resilient systems. This allows write-only ORAMs to achieve significantly-better asymptotic performance. However, these apparent gains do not materialize in real deployments primarily due to the random data placement strategies used to break correlations between logical and physical names-paces, a required property for write access privacy. Random access performs poorly on both rotational disks and SSDs (often increasing wear significantly, and interfering with wear-leveling mechanisms).

Clouds and massive-scale computing infrastructures are starting to dominate computing and will likely continue to do so for the foreseeable future. Major cloud operators are now comprising millions of cores hosting substantial fractions of corporate and government IT infrastructure. CCSW is the world's premier forum bringing together researchers and practitioners in all security aspects of cloud-centric and outsourced computing. CCSW especially encouraged novel paradigms and controversial ideas that are not on the above list. The workshop has historically acted as a fertile ground for creative debate and interaction in security-sensitive areas of computing impacted by clouds. This year marked the 10th anniversary of CCSW. In the past decade, CCSW has had a significant impact in our research community. As of August 2019, in the Google Scholar Metrics entry for ACM CCS (which encompasses CCSW), 20% of the top 20 cited papers come from CCSW. One way to look at it is that authors are as likely or perhaps more likely to have a top-20 paper publishing in CCSW than in CCS! This year, CCSW received 40 submissions out of which 15 full papers (37%) and 2 blitz abstracts were accepted. CCSW Website: https://ccsw.io

Abstract Encryption protects sensitive data from unauthorized access, yet is not sufficient when users are forced to surrender keys under duress. In contrast, plausible deniability enables users to not only encrypt data but also deny its existence when challenged. Most existing plausible deniability work (e.g. the successful and unfortunately now-defunct TrueCrypt) tackles “single snapshot” adversaries, and cannot handle the more realistic scenario of adversaries gaining access to a device at multiple time points. Such “multi-snapshot” adversaries can simply observe modifications between snapshots and detect the existence of hidden data. Existing ideas handling “multi-snapshot” scenarios feature prohibitive overheads when deployed on practically-sized disks. This is mostly due to a lack of data locality inherent in certain standard access-randomization mechanisms, one of the building blocks used to ensure plausible deniability. In this work, we show that such randomization is not necessary for strong plausible deniability. Instead, it can be replaced by a canonical form that permits most of writes to be done sequentially. This has two key advantages: 1) it reduces the impact of seek due to random accesses; 2) it reduces the overall number of physical blocks that need to be written for each logical write. As a result, PD-DM increases I/O throughput by orders of magnitude (10–100× in typical setups) over existing work while maintaining strong plausible deniability against multi-snapshot adversaries. Notably, PD-DM is the first plausible-deniable system getting within reach of the performance of standard encrypted volumes (dm-crypt) for random I/O.

With today's massive jobs spanning thousands of tasks each, cost-optimality has become more important than ever. Modern distributed data processing paradigms can be significantly more sensitive to cost than makespan, especially for long jobs deployed in commercial clouds. This paper posits that minimized dollar costs can not be achieved unless data and tasks are scheduled simultaneously. In this paper, we introduce the problem of cost-efficient co-scheduling for highly data-intensive jobs in cloud, such as MapReduce. We show that while the problem is polynomial in some cases, its general problem is NP-Hard. We propose to tackle the problem by using integer programming techniques coupled with heuristic reduction and optimization to enable a near-realtime solution. AffordHadoop, a pluggable co-scheduler for Hadoop, is implemented as an example of such a co-scheduler. AffordHadoop can save up to 48 percent of the overall dollar costs when compared to existing schedulers and provides significant flexibility in fine-tuning the cost-performance tradeoff.

Today's (predominantly cloud-based) File sharing products leave users at the mercy of providers and nation-state adversaries with subpoena and National Security Letter (NSL) powers. In-transit and provider-side at-rest encryption do little to handle this.Almost-weekly breaches [7-13, 17] and NSL revelations [2] show that the problem becomes only worse with increasingly privacy-unfriendly regulation [14]. We believe it is important to provide hype-free, easy-to-use strongly-secure solutions that protect individual privacy while also defeating cloud breaches and compromises. CipherLocker provides practical, easy-to-use, client-side encrypted File sharing with integrated ranked search. All data and metadata is strongly encrypted before leaving the client. Users can securely store, share, sync, and search. The design does not allow even a compromised or compelled cloud provider to ever access user data or search queries. CipherLocker shows that highly-scalable, fast ranked search on encrypted data is possible without the deployment of expensive and often insecure server-side search-on-encrypted-data cryptography which would require 3-5 orders of magnitude more resources and cannot scale to even thousands of users, or the simplest sharing scenarios without breaking security. CipherLocker is the result of several years of work and it cannot be exhaustively detailed and analyzed in this space. This is the first of a series of papers discussing CipherLocker design, implementation and security properties. The main goal here is to briefly overview and introduce key design decisions and behaviors.

Abstract Sensitive information is present on our phones, disks, watches and computers. Its protection is essential. Plausible deniability of stored data allows individuals to deny that their device contains a piece of sensitive information. This constitutes a key tool in the fight against oppressive governments and censorship. Unfortunately, existing solutions, such as the now defunct TrueCrypt [5], can defend only against an adversary that can access a user’s device at most once (“single-snapshot adversary”). Recent solutions have traded significant performance overheads for the ability to handle more powerful adversaries able to access the device at multiple points in time (“multi-snapshot adversary”). In this paper we show that this sacrifice is not necessary. We introduce and build DataLair1, a practical plausible deniability mechanism. When compared with existing approaches, DataLair is two orders of magnitude faster for public data accesses, and 5 times faster for hidden data accesses. An important component in DataLair is a new write-only ORAM construction which improves on the complexity of the state of the art write-only ORAM by a factor ofO(logN), where N denotes the underlying storage disk size.

Sensitive information is present on our phones, disks, watches and computers. Its protection is essential. Plausible deniability of stored data allows individuals to deny that their device contains a piece of sensitive information. This constitutes a key tool in the fight against oppressive governments and censorship.

Oblivious RAM (ORAM) mechanisms have improved rapidly in recent years as increasing amounts of data are outsourced. Although several tree-based ORAMs such as PathORAM [8] and RingORAM [6] have achieved near-optimal bandwidth for single client scenarios, their low overall throughput due to high latency of access -- as clients need to wait for or know about and coordinate with each other, lest privacy is lost -- reduces their applicability for multi-client scenarios.

Kernel rootkits often hide associated malicious processes by altering reported task struct information to upper layers and applications such as ps and top. Virtualized settings offer a unique opportunity to mitigate this behavior using dynamic virtual machine introspection (VMI). For known kernels, VMI can be deployed to search for kernel objects and identify them by using unique data structure "signatures".

Smartphones are becoming the main data sharing and storage devices in both our personal and professional lives, as companies now allow employees to share the same device for both purposes, provided the company's confidential information can be protected. However, as history has shown, systems relying on security policies or rules to protect user data are not airtight. Any flaw in the constructed rules or in the code of privileged applications can lead to complete compromise. In addition, we can not rely only on TrustZone[6] world separation to isolate confidential data from unauthorized access, because in addition to severe limitations in terms of both communication and memory space, there is a very low limit on the number of applications that can be installed in the secure world before we can start questioning its security, especially when considering code originating from multiple sources. Thus, the solutions currently available for TrustZone devices are not perfect and the data confidentiality can not be guaranteed. We propose an alternative approach, which involves providing the majority of secure world application advantages to a set of normal world applications, with almost none of the drawbacks by relying only on the TrustZone world separation and the TZ-RKP[2] kernel protection scheme.

The way data structures organize data is often a function of the sequence of past operations. The organization of data is referred to as the data structure's state, and the sequence of past operations constitutes the data structure's history. A data structure state can, therefore, be used as an oracle to derive information about its history. For history-sensitive applications, such as privacy in e-voting, it is imperative to conceal historical information contained within data structure states. Data structure history can be hidden by making data structures history independent. In this paper, we explore how to achieve history independence (HI). We observe that the current HI notions are significantly limited in number and scope. There are two existing notions of HI: 1) weak HI (WHI) and 2) strong HI (SHI). WHI does not protect against insider adversaries, and SHI mandates canonical representations, resulting in inefficiency. We postulate the need for a broad, encompassing notion of HI, which can capture WHI, SHI, and a broad spectrum of new HI notions. To this end, we introduce AHI, a generic game-based framework that is malleable enough to accommodate the existing and new HI notions. As an essential step toward formalizing AHI, we explore the concepts of abstract data types, data structures, machine models, memory representations, and HI. Finally, to bridge the gap between theory and practice, we outline a general recipe for building end-to-end, history-independent systems and demonstrate the use of the recipe in designing two historyindependent file systems.

"Green" and its "low power" cousin are the new hot spots in computing. In cloud data centers, at scale, ideas of deploying low-power ARM architectures or even large numbers of extremely "wimpy" nodes [1, 2] seem increasingly appealing. Skeptics on the other hand maintain that we cannot get more than what we pay for and no free lunches can be had. In this paper we explore these theses and provide insights into the power-performance trade-off at scale for "wimpy", back-to basics, power-efficient RISC architectures. We use ARM as modern proxy for these and quantify the cost/performance ratio precisely-enough to allow for a broader conclusion. We then offer an intuition as to why this may still hold in 2030.

Lack of energy proportionality in server systems results in significant waste of energy when operating at low utilization, a common scenario in today's data centers. We propose DIMMer, an approach to eliminate the idle power consumption of unused system components, motivated by two key observations. First, even in their lowest-power states, the power consumption of server components remains significant. Second, unused components can be powered off entirely without sacrificing server availability. We demonstrate that unused memory capacity can be powered off, eliminating the energy waste of self-refresh for unallocated memory, while still allowing for all capacity to be available on a moment's notice. Similarly, only one CPU socket must remain powered on, allowing unused CPUs and attached memory to be powered off entirely. The DIMMer vision can improve energy proportionality and achieve energy savings. Using a Google cluster trace as well as in-house experiments, we estimate up to 50% savings on DRAM and 18.8% on CPU background energy. At $0.10/kWh, this corresponds to 0.6% of total data center cost.

Government and commercial enterprises are increasingly considering cloud adoption. Clouds improve overall efficiency by consolidating a number of different clients' software virtual machines onto a smaller set of hardware resources. Unfortunately, this shared hardware also creates inherent side-channel vulnerabilities, which an attacker can use to leak information from a victim VM. Side-channel vulnerabilities are especially concerning when different principals are constrained by regulations. A classic example of these regulations are Chinese Wall policies for financial companies, which aim to protect the financial system from illicit manipulation by separating portions of the business with conflicting interests. Although efficient prevention of side channels is difficult within a single node, there is a unique opportunity within a cloud. This paper proposes a low-overhead approach to cloud wide information flow policy enforcement: identifying side channels which could potentially be used to violate a security policy through run-time introspection, and reactively migrating virtual machines to eliminate node-level side-channels. In this paper we describe CloudFlow-an information flow control extension for OpenStack. CloudFlow includes a novel, virtual machine introspection mechanism that is orders of magnitude faster than previous approaches. CloudFlow efficiently and transparently enforces information flow policies cloud-wide, including information leaks through undesirable side-channels. Additionally, CloudFlow has potential uses for cloud management and resource-efficient virtual machine scheduling.

An essential goal of Virtual Machine Introspection (VMI) is assuring security policy enforcement and overall functionality in the presence of an untrustworthy OS. A fundamental obstacle to this goal is the difficulty in accurately extracting semantic meaning from the hypervisor's hardware level view of a guest OS, called the semantic gap. Over the twelve years since the semantic gap was identified, immense progress has been made in developing powerful VMI tools. Unfortunately, much of this progress has been made at the cost of reintroducing trust into the guest OS, often in direct contradiction to the underlying threat model motivating the introspection. Although this choice is reasonable in some contexts and has facilitated progress, the ultimate goal of reducing the trusted computing base of software systems is best served by a fresh look at the VMI design space. This paper organizes previous work based on the essential design considerations when building a VMI system, and then explains how these design choices dictate the trust model and security properties of the overall system. The paper then observes portions of the VMI design space which have been under-explored, as well as potential adaptations of existing techniques to bridge the semantic gap without trusting the guest OS. Overall, this paper aims to create an essential checkpoint in the broader quest for meaningful trust in virtualized environments through VM introspection.

Traditionally, as soon as confidentiality becomes a concern, data are encrypted before outsourcing to a service provider. Any software-based cryptographic constructs then deployed, for server-side query processing on the encrypted data, inherently limit query expressiveness. Here, we introduce TrustedDB, an outsourced database prototype that allows clients to execute SQL queries with privacy and under regulatory compliance constraints by leveraging server-hosted, tamper-proof trusted hardware in critical query processing stages, thereby removing any limitations on the type of supported queries. Despite the cost overhead and performance limitations of trusted hardware, we show that the costs per query are orders of magnitude lower than any (existing or) potential future software-only mechanisms. TrustedDB is built and runs on actual hardware, and its performance and costs are evaluated here.

Geosocial networks (GSNs) extend classic online social networks with the concept of location. Users can report their presence at venues through “check-ins” and, when certain check-in sequences are satisfied, users acquire special status in the form of “badges”. We first show that this innovative functionality is popular in Foursquare, a prominent GSN. Furthermore, we address the apparent tension between privacy and correctness, where users are unable to prove having satisfied badge conditions without revealing the corresponding time and location of their check-in sequences. To this end, we propose several privacy preserving protocols that enable users to prove having satisfied the conditions of several badge types. Specifically, we introduce (i) GeoBadge and T-Badge, solutions for acquiring location badges, (ii) FreqBadge, for mayorship badges, (iii) e-Badge, for proving various expertise levels and (iv) MPBadge, for accumulating multi-player badges. We show that a Google Nexus One smartphone is able to perform tens of badge proofs per minute while a provider can support hundreds of million of check-ins and badge verifications per day.

Ensuring complete irrecoverability of deleted data is difficult to achieve in modern systems. Simply overwriting data or deploying encryption with ephemeral keys is not sufficient. The mere (previous) existence of deleted records impacts the current system state implicitly at all layers. This can be used as an oracle to derive information about the past existence of deleted records.

We introduce LiPS, a new cost-efficient data and task co-scheduler for MapReduce in a cloud environment. By using linear programming to simultaneously co-schedule data and tasks, LiPS helps to achieve minimized dollar cost globally. We evaluated LiPS both analytically and on Amazon EC2 in order to measure actual dollar charges. The results were significant; LiPS saved 62–81% of the dollar costs when compared with the Hadoop default scheduler and the delay scheduler, while also allowing users to fine-tune the cost-performance tradeoff.

It has become apparent that in the digital world data once stored is never truly deleted even when such an expunction is desired either as a normal system function or for regulatory compliance purposes. Forensic Analysis techniques on systems are often successful at recovering information said to have been deleted in the past. Efforts aimed at thwarting such forensic analysis of systems have either focused on (i) identifying the system components where deleted data lingers and performing a secure delete operation over these remnants, or (ii) designing history independent data structures that hide information about past operations which result in the current system state. Yet, new data is constantly derived by processing existing (input) data which makes it increasingly difficult to remove all traces of this existing data, i.e., for regulatory compliance purposes. Even after deletion, significant information can linger in and be recoverable from the side effects the deleted data records left on the currently available state. In this paper we address this aspect in the context of a relational database, such that when combined with (i) & (ii), complete erasure of data and its effects can be achieved (“un-traceable deletion”). We introduce Ficklebase - a relational database wherein once a tuple has been “expired” - any and all its side-effects are removed, thereby eliminating all its traces, rendering it unrecoverable, and also guaranteeing that the deletion itself is undetectable. We present the design and evaluation of Ficklebase, and then discuss several of the fundamental functional implications of un-traceable deletion.

Clients of outsourced databases need Query Authentication (QA) guaranteeing the integrity (correctness and completeness), and authenticity of the query results returned by potentially compromised providers. Existing results provide QA assurances for a limited class of queries by deploying several software cryptographic constructs. Here, we show that, to achieve QA, however, it is significantly cheaper and more practical to deploy server-hosted, tamper-proof co-processors, despite their higher acquisition costs. Further, this provides the ability to handle arbitrary queries. To reach this insight, we extensively survey existing QA work and identify interdependencies and efficiency relationships. We then introduce CorrectDB, a new DBMS with full QA assurances, leveraging server-hosted, tamper-proof, trusted hardware in close proximity to the outsourced data.

We introduce a new practical mechanism for remote data storage with access pattern privacy and correctness . A storage client can deploy this mechanism to issue encrypted reads, writes, and inserts to a potentially curious and malicious storage service provider, without revealing information or access patterns. The provider is unable to establish any correlation between successive accesses, or even to distinguish between a read and a write. Moreover, the client is provided with strong correctness assurances for its operations—illicit provider behavior does not go undetected. We describe a practical system that can execute an unprecedented several queries per second on terabyte-plus databases while maintaining full computational privacy and correctness.

We present SR-ORAM1, the first single-round-trip polylogarithmic time Oblivious RAM that requires only logarithmic client storage. Taking only a single round trip to perform a query, SR-ORAM has an online communication / computation cost of O(log n log log n), and an offline, overall amortized per-query communication cost of O(log2 n log log n), requiring under 2 round trips. The client folds an entire interactive sequence of Oblivious RAM requests into a single query object that the server can unlock incrementally, to satisfy a query without learning its result. This results in an Oblivious RAM secure against an actively malicious adversary, with unprecedented speeds in accessing large data sets over high-latency links. We show this to be the most efficient storage-free-client Oblivious RAM to date for today's Internet-scale network latencies.

PrivateFS is an oblivious file system that enables access to remote storage, while keeping both the file contents and client access patterns secret. PrivateFS is based on a new parallel Oblivious RAM mechanism (PD-ORAM)---instead of waiting for the completion of all ongoing client-server transactions, client threads can now engage a server in parallel without loss of privacy.

We design and analyze the first practical anonymous payment mechanisms for network services. We start by reporting on our experience with the implementation of a routing micropayment solution for Tor. We then propose micropayment protocols of increasingly complex requirements for networked services, such as P2P or cloud-hosted services. The solutions are efficient, with bandwidth and latency overheads of under 4% and 0.9 ms, respectively, in the ORPay implementation, provide full anonymity (for both payers and payees), and support thousands of transactions per second.

We introduce a Write-Once Read-Many (WORM) storage system providing strong assurances of data retention and compliant migration, by leveraging trusted secure hardware in close data proximity. This is important because existing compliance storage products and research prototypes are fundamentally vulnerable to faulty or malicious behavior, as they rely on simple enforcement primitives that are ill-suited for their threat model. This is hard because tamper-proof processing elements are significantly constrained in both computation ability and memory capacity-as heat dissipation concerns under tamper-resistant requirements limit their maximum allowable spatial gate-density. We achieve efficiency by 1) ensuring the secure hardware is accessed sparsely, minimizing the associated overhead for expected transaction loads, and 2) using adaptive overhead-amortized constructs to enforce WORM semantics at the throughput rate of the storage server's ordinary processors during burst periods. With a single secure coprocessor, on commodity x86 hardware, the architecture can support unlimited read throughputs and over 2500 write transactions per second.

In an outsourced database framework, clients place data management responsibilities with specialized service providers. Of essential concern in such frameworks is data privacy. Potential clients are reluctant to outsource sensitive data to a foreign party without strong privacy assurances beyond policy “fine prints.” In this paper, we introduce a mechanism for executing general binary JOIN operations (for predicates that satisfy certain properties) in an outsourced relational database framework with computational privacy and low overhead—the first, to the best of our knowledge. We illustrate via a set of relevant instances of JOIN predicates, including: range and equality (e.g., for geographical data), Hamming distance (e.g., for DNA matching), and semantics (i.e., in health-care scenarios—mapping antibiotics to bacteria). We experimentally evaluate the main overhead components and show they are reasonable. The initial client computation overhead for 100,000 data items is around 5 minutes and our privacy mechanisms can sustain theoretical throughputs of several million predicate evaluations per second, even for an unoptimized OpenSSL-based implementation.

In this paper we aim to understand the types of applications for which cloud computing is economically tenable, i.e., for which the cost savings associated with cloud placement outweigh any associated deployment costs.

Location based social or geosocial networks (GSNs) have recently emerged as a natural combination of location based services with online social networks: users register their location and activities, share it with friends and achieve special status (e.g., "mayorship" badges) based on aggregate location predicates. Boasting millions of users and tens of daily check-ins, such services pose significant privacy threats: user location information may be tracked and leaked to third parties. Conversely, a solution enabling location privacy may provide cheating capabilities to users wanting to claim special location status. In this paper we introduce new mechanisms that allow users to (inter)act privately in today's geosocial networks while simultaneously ensuring honest behaviors. We show that our solutions are efficient both on the provider and the client side.

As the trends move towards data outsourcing and cloud computing, the efficiency of distributed data centers increases in importance. Cloud-based services such as Amazon's EC2 rely on virtual machines (VMs) to host MapReduce clusters for large data processing. However, current VM scheduling does not provide adequate support for MapReduce workloads, resulting in degraded overall performance. For example, when multiple MapReduce clusters run on a single physical machine, the existing VMMscheduler does not guarantee fairness across clusters.

TrustedDB is an outsourced database prototype that allows clients to execute SQL queries with privacy and under regulatory compliance constraints without having to trust the service provider. TrustedDB achieves this by leveraging server-hosted tamper-proof trusted hardware in critical query processing stages.TrustedDB does not limit the query expressiveness of supported queries. And, despite the cost overhead and performance limitations of trusted hardware, the costs per query are orders of magnitude lower than any (existing or) potential future software-only mechanisms. TrustedDB is built and runs on actual hardware, and its performance and costs are evaluated here.

We introduce WORM-ORAM, a first mechanism that combines Oblivious RAM (ORAM) access privacy and data confidentiality with Write-Once Read-Many (WORM) regulatory data retention guarantees. Clients can outsource their database to a server with full confidentiality and data access privacy, and, for data retention, the server ensures client access WORM semantics. In general simple confidentiality and WORM assurances are easily achievable, e.g., via an encrypted outsourced data repository with server-enforced read-only access to existing records (albeit encrypted). However, this becomes hard when also access privacy is to be ensured-when client access patterns are necessarily hidden and the server cannot enforce access control directly. WORM-ORAM overcomes this by deploying a set of zero-knowledge proofs to convince the server that all stages of the protocol are WORM-compliant.

In this article we introduce a technique, guaranteeing access pattern privacy against a computationally bounded adversary, in outsourced data storage, with communication and computation overheads orders of magnitude better than existing approaches. In the presence of a small amount of temporary storage (enough to store O (√ n log n ) items and IDs, where n is the number of items in the database), we can achieve access pattern privacy with computational complexity of less than O (log 2 n ) per query (as compared to, for instance, O (log 4 n ) for existing approaches). We achieve these novel results by applying new insights based on probabilistic analyses of data shuffling algorithms to Oblivious RAM, allowing us to significantly improve its asymptotic complexity. This results in a protocol crossing the boundary between theory and practice and becoming generally applicable for access pattern privacy. We show that on off-the-shelf hardware, large data sets can be queried obliviously orders of magnitude faster than in existing work.

Location information is of essential importance in sensor networks deployed for generating location-specific event reports. When such networks operate in hostile environments, it becomes imperative to guarantee the correctness of event location claims. In this article we address the problem of assessing location claims of untrusted (potentially compromised) nodes. The mechanisms introduced here prevent a compromised node from generating illicit event reports for locations other than its own. This is important because by compromising “easy target” sensors (say, sensors on the perimeter of the field that's easier to access), the adversary should not be able to impact data flows associated with other (“premium target”) regions of the network. To achieve this goal, in a process we call location certification , data routed through the network is “tagged” by participating nodes with “belief” ratings, collaboratively assessing the probability that the claimed source location is indeed correct. The effectiveness of our solution relies on the joint knowledge of participating nodes to assess the truthfulness of claimed locations. By collaboratively generating and propagating a set of “belief” ratings with transmitted data and event reports, the network allows authorized parties (e.g., final data sinks) to evaluate a metric of trust for the claimed location of such reports. Belief ratings are derived from a data model of observed past routing activity. The solution is shown to feature a strong ability to detect false location claims and compromised nodes. For example, incorrect claims as small as 2 hops (from the actual location) are detected with over 90% accuracy. Finally, these new location certification mechanisms can be deployed in tandem with traditional secure localization, yet do not require it, and, in a sense, can serve to minimize the need thereof.

As increasing amounts of valuable information are produced and persist digitally, the ability to determine the origin of data becomes important. In science, medicine, commerce, and government, data provenance tracking is essential for rights protection, regulatory compliance, management of intelligence and medical data, and authentication of information as it flows through workplace tasks. While significant research has been conducted in this area, the associated security and privacy issues have not been explored, leaving provenance information vulnerable to illicit alteration as it passes through untrusted environments. In this article, we show how to provide strong integrity and confidentiality assurances for data provenance information at the kernel, file system, or application layer. We describe Sprov, our provenance-aware system prototype that implements provenance tracking of data writes at the application layer, which makes Sprov extremely easy to deploy. We present empirical results that show that, for real-life workloads, the runtime overhead of Sprov for recording provenance with confidentiality and integrity guarantees ranges from 1% to 13%, when all file modifications are recorded, and from 12% to 16%, when all file read and modifications are tracked.

We introduce a new practical mechanism for remote data storage with efficient access pattern privacy and correctness. A storage client can deploy this mechanism to issue encrypted reads, writes, and inserts to a potentially curious and malicious storage service provider, without revealing information or access patterns. The provider is unable to establish any correlation between successive accesses, or even to distinguish between a read and a write. Moreover, the client is provided with strong correctness assurances for its operations -- illicit provider behavior does not go undetected. We built a first practical system -- orders of magnitude faster than existing implementations -- that can execute over several queries per second on 1Tbyte+ databases with full computational privacy and correctness.

We introduce a Write-Once Read-Many (WORM) storage system providing strong assurances of data retention and compliant migration, by leveraging trusted secure hardware in close data proximity. This is important because existing compliance storage products and research prototypes are fundamentally vulnerable to faulty or malicious behavior, as they rely on simple enforcement primitives ill-suited for their threat model. This is hard because tamper-proof processing elements are significantly constrained in both computation ability and memory capacity - as heat dissipation concerns under tamper-resistant requirements limit their maximum allowable spatial gate-density. We achieve efficiency by (i) ensuring the secure hardware is accessed sparsely, minimizing the associated overhead for expected transaction loads, and (ii) using adaptive overhead-amortized constructs to enforce WORM semantics at the throughput rate of the storage servers ordinary processors during burst periods. With a single secure co-processor, on single-CPU commodity x86 hardware, our architecture can support over 2500 transactions per second.

Today's world of increasingly dynamic environments naturally results in more and more data being available as fast streams. Applications such as stock market analysis, environmental sensing, Web clicks, and intrusion detection are just a few of the examples where valuable data is streamed. Often, streaming information is offered on the basis of a nonexclusive, single-use customer license. One major concern, especially given the digital nature of the valuable stream, is the ability to easily record and potentially "replay" parts of it in the future. If there is value associated with such future replays, it could constitute enough incentive for a malicious customer (Mallory) to record and duplicate data segments, subsequently reselling them for profit. Being able to protect against such infringements becomes a necessity. In this work, we introduce the issue of rights protection for discrete streaming data through watermarking. This is a novel problem with many associated challenges including: operating in a finite window, single-pass, (possibly) high-speed streaming model, and surviving natural domain specific transforms and attacks (e.g., extreme sparse sampling and summarizations), while at the same time keeping data alterations within allowable bounds. We propose a solution and analyze its resilience to various types of attacks as well as some of the important expected domain-specific transforms, such as sampling and summarization. We implement a proof of concept software (wms.*) and perform experiments on real sensor data from the NASA Infrared Telescope Facility at the University of Hawaii, to assess encoding resilience levels in practice. Our solution proves to be well suited for this new domain. For example, we can recover an over 97 percent confidence watermark from a highly down-sampled (e.g., less than 8 percent) stream or survive stream summarization (e.g., 20 percent) and random alteration attacks with very high confidence levels, often above 99 percent.

In this paper we propose a solution for optimizing (Web service) business workflow response times through dynamic resource allocation. On-the-fly monitoring is combined with a novel workflow modeling algorithm that discovers critical execution paths and builds "dynamic" stochastic models in the associated "critical graph". One novel contribution of this work is the ability to naturally handle parallel workflow execution paths. This is essential in applications where workflows include multiple concurrent service calls/paths that need to be "joined" at a later point in time. We discuss the automatic deployment of on-the-fly monitoring mechanisms within the resource management mechanisms. We implement, deploy and experiment with a proof of concept within a generalized Web services business process (BPEL4WS/SOAP) framework. In the experimental setup we explore and show the natural adaptation to changing workflow conditions and appropriate automatic re-allocation of resources to reduce execution times.

A novel method of rights protection for categorical data through watermarking is introduced in this paper. New watermark embedding channels are discovered and associated novel watermark encoding algorithms are proposed. While preserving data quality requirements, the introduced solution is designed to survive important attacks, such as subset selection and random alterations. Mark detection is fully "blind" in that it doesn't require the original data, an important characteristic, especially in the case of massive data. Various improvements and alternative encoding methods are proposed and validation experiments on real-life data are performed. Important theoretical bounds including mark vulnerability are analyzed. The method is proved (experimentally and by analysis) to be extremely resilient to both alteration and data loss attacks, for example, tolerating up to 80 percent data loss with a watermark alteration of only 25 percent.

This paper introduces a novel method of rights protection for categorical data through watermarking. We discover new watermark embedding channels for relational data with categorical types. We design novel watermark encoding algorithms and analyze important theoretical bounds including mark vulnerability. While fully preserving data quality requirements, our solution survives important attacks, such as subset selection and random alterations. Mark detection is fully "blind" in that it doesn't require the original data, an important characteristic especially in the case of massive data. We propose various improvements and alternative encoding methods. We perform validation experiments by watermarking the outsourced Wal-Mart sales data available at our institute. We prove (experimentally and by analysis) our solution to be extremely resilient to both alteration and data loss attacks, for example tolerating up to 80% data loss with a watermark alteration of only 25%.

We introduce wmdb.*, a solution for numeric relational data rights protection through watermarking. Rights protection for relational data is important in areas where sensitive, valuable content is to be outsourced. A good example is a data mining application, where data is sold in pieces to parties specialized in mining it. We show how various higher level semantic constraints such as classification preservation and maximum absolute change bounds are naturally handled and how random alteration attacks are well survived.

we introduce a solution for relational database content rights protection through watermarking. Rights protection for relational data is of ever-increasing interest, especially considering areas where sensitive, valuable content is to be outsourced. A good example is a data mining application, where data is sold in pieces to parties specialized in mining it. Different avenues are available, each with its own advantages and drawbacks. Enforcement by legal means is usually ineffective in preventing theft of copyrighted works, unless augmented by a digital counterpart, for example, watermarking. While being able to handle higher level semantic constraints, such as classification preservation, our solution also addresses important attacks, such as subset selection and random and linear data changes. We introduce wmdb., a proof-of-concept implementation and its application to real-life data, namely, in watermarking the outsourced Wal-Mart sales data that we have available at our institute.

Protecting rights over relational data is of ever increasing interest, especially considering areas where sensitive, valuable content is to be outsourced. A good example is a data mining application, where data is sold in pieces to parties specialized in mining it.Different avenues for rights protection are available, each with its own advantages and drawbacks. Enforcement by legal means is usually ineffective in preventing theft of copyrighted works, unless augmented by a digital counter-part, for example watermarking.Recent research of the authors introduces the issue of digital watermarking for generic number sets. In the present paper we expand on this foundation and introduce a solution for relational database content rights protection through watermarking.Our solution addresses important attacks, such as data re-sorting, subset selection, linear data changes (applying a linear transformation on arbitrary subsets of the data). Our watermark also survives up to 50% and above data loss.Finally we present wmdb.*, a proof-of-concept implementation of our algorithm and its application to real life data, namely in watermarking the outsourced Wal-Mart sales data that we have available at our institute.