Single-factor authentication (1FA) and two-factor authentication (2FA) for secure and reliable website account access have become everyday tasks for most users. However, the complexity of integrating 1FA, 2FA, and password reset mechanisms makes real-world deployments challenging to navigate, leaving key questions about their implications for account security and accessibility unanswered. In this paper, we present a comprehensive investigation into the deployment of 1FA, 2FA, and password reset mechanisms across 50 major websites in six industries. By formally modeling account access and password reset patterns and applying Karnaugh maps for logical optimization, we uncover surprising consequences of current integrations of authentication mechanisms. We present key findings on the implications of modern authentication integrations for account security and accessibility, highlighting both the overestimated strengths and overlooked weaknesses of current deployments. Our research aims to provide a valuable and practical understanding of real-world authentication deployments for advancing web authentication practices.

Cryptocurrency introduces usability challenges by requiring users to manage signing keys. Popular signing key management services (e.g., custodial wallets), however, either introduce a trusted party or burden users with managing signing key shares, posing the same usability challenges. TEE (Trusted Execution Environment) is a promising technology to avoid both, but practical implementations of TEEs suffer from various side-channel attacks that have proven hard to eliminate. This paper explores a new approach to side-channel mitigation through economic incentives for TEE-based cryptocurrency wallet solutions. By taking the cost and profit of side-channel attacks into consideration, we designed a Stick-and-Carrot-based cryptocurrency wallet, CrudiTEE, that leverages penalties (the stick) and rewards (the carrot) to disincentivize attackers from exfiltrating signing keys in the first place. We model the attacker’s behavior using a Markov Decision Process (MDP) to evaluate the effectiveness of the bounty and enable the service provider to adjust the parameters of the bounty’s reward function accordingly.

Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. Numerous applications across the blockchain space have led to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon systems rely on threshold cryptographic setups or exhibit high computational costs, while others expect the network to be partial or bounded synchronous. To overcome these limitations, we propose HashRand, a computation and communication-efficient asynchronous random beacon protocol that only demands secure hash and pairwise secure channels to generate beacons. HashRand has a per-node amortized communication complexity of O (λn log(n)) bits per beacon. The computational efficiency of HashRand is attributed to the two orders of magnitude lower time of a one-way Hash computation compared to discrete log exponentiation. Interestingly, besides reduced overhead, HashRand achieves Post-Quantum security by leveraging the secure Hash function against quantum adversaries, setting it apart from other random beacon protocols that use discrete log cryptography. In a geo-distributed testbed of n = 136 nodes, HashRand produces 78 beacons per minute, which is at least 5× higher than Spurt [IEEE S&P'22]. We also demonstrate the practical utility of HashRand by implementing a Post-Quantum secure Asynchronous SMR protocol, which has a response rate of over 135k transactions per second at a latency of 2.3 seconds over a WAN for n = 16 nodes.

Auditing the use of data in training machine-learning (ML) models is an increasingly pressing challenge, as myriad ML practitioners routinely leverage the effort of content creators to train models without their permission. In this paper, we propose a general method to audit an ML model for the use of a data-owner's data in training, without prior knowledge of the ML task for which the data might be used. Our method leverages any existing black-box membership inference method, together with a sequential hypothesis test of our own design, to detect data use with a quantifiable, tunable false-detection rate. We show the effectiveness of our proposed framework by applying it to audit data use in two types of ML models, namely image classifiers and foundation models.

We design and implement PG, a Byzantine fault-tolerant and privacy-preserving multi-sensor fusion system. PG is flexible and extensible, supporting a variety of fusion algorithms and application scenarios.

Machine-learning (ML) classifiers are increasingly used to distinguish malware from benign binaries. Recent work has shown that ML-based detectors can be evaded by adversarial examples, but also that one may defend against such attacks via adversarial training. However, adversarial training, and subsequent robustness evaluation, is computationally expensive in the raw-binary malware-detection domain because it requires producing many adversarial examples for both training and evaluation. Prior work found that Greedy-training, a faster robust training technique that forgoes using adversarial examples, showed some promise in producing robust malware detectors. However, Greedy-training was far less effective in inducing robustness than the more expensive adversarial training, and it also severely hurt natural accuracy (i.e., accuracy on the original data). To faster train models, this work presents GreedyBlock-training, an enhanced version of Greedy-training that we empirically show achieves not only state-of-the-art robustness in malware detectors, exceeding even adversarial training, but also retains natural accuracy better than adversarial training. Furthermore, as it does not require creating adversarial (or functional) examples, GreedyBlock-training is significantly faster than adversarial training. Specifically, we show that GreedyBlock-training can produce more robust (+54% on average), more naturally accurate (+7% on average), and more efficiently trained (-91% average computation) malware detectors than prior work. To faster evaluate models, we also develop methods to faster gauge the robustness of ML-based raw-binary malware detectors by introducing robustness proxies, which can be used either to predict which models are likely to be the most robust, thus helping prioritize which detectors to evaluate with expensive attacks, or aiding in deciding which detectors are worthwhile to continue training. Experimentally, we show these proxy measures can find the most robust detector in a pool of detectors while using only ~20-50% of the computation that would otherwise be required.

Agreement protocols are crucial in various emerging applications, spanning from distributed (blockchains) oracles to fault-tolerant cyber-physical systems. In scenarios where sensor/oracle nodes measure a common source, maintaining output within the convex range of correct inputs, known as convex validity, is imperative. Present asynchronous convex agreement protocols employ either randomization, incurring substantial computation overhead, or approximate agreement techniques, leading to high$\tilde{\mathcal{O}(n^{3})}$communication for an$n$-node system. This paper introduces Delphi, a deterministic protocol with$\tilde{\mathcal{O}(n^{2})}$communication and minimal computation overhead. Delphi assumes that honest inputs are bounded, except with negligible probability, and integrates agreement primitives from literature with a novel weighted averaging technique. Experimental results highlight Delphi's superior performance, showcasing a significantly lower latency compared to state-of-the-art protocols. Specifically, for an$n$= 160-node system, Delphi achieves an 8x and 3x improvement in latency within CPS and AWS environments, respectively.

The target localization primitive is used for detecting and locating an adverse event called a target in a geographic area. This versatile primitive is applicable in the physical security domain (e.g., detecting intruders in an area) or for disaster preemption, such as detecting ignition events of forest fires. Prior systems implemented this primitive over large areas by deploying a network of sensor devices, which detect changes in a specific physical parameter like pressure or temperature induced by a target. However, these systems are not designed for use in adverse environments where one or more sensors can behave in a faulty manner. While many algorithms in the distributed systems literature can be naively used to implement target localization in a fault-tolerant manner, these approaches are energy-intensive as they use computationally expensive cryptographic operations not appropriate for resource-constrained sensors. We present SENSORBFT, an energy-efficient, fault-tolerant approach for target localization. SENSORBFT uses a novel asynchronous approximate agreement protocol that enables correct sensors to achieve an approximate consensus in the presence of faulty sensors. Sensors fulfill their energy budgets by tuning the precision and accuracy of localization, where precision is the difference between honest sensors' outputs and accuracy is the difference between an honest sensor's output and the target's true location. In optimal scenarios, this protocol reduces communication from$O$($n$3) to$O$($n$2) messages per round, where$n$is the number of sensors sharing coverage over a piece of area. In a sensor testbed with$n$= 19 sensors, SENSORBFT consumes 2/5 th the energy consumed by existing solutions for a minor 2% loss in accuracy, significantly enhancing efficiency and coverage.

Defending an enterprise network requires making prioritization decisions daily; one is deciding which compromised hosts to remediate (reimage). We study the utility of endpoint monitoring data to perform this prioritization, with the driving goal being to minimize “regret” as measured by future (next-week) malware execution on hosts whose remediation was deprioritized. Leveraging data gathered by the vendor of a major endpoint protection product, we show that it is possible to prioritize remediation by training a classifier that predicts imminent malware execution. Perhaps surprisingly, while it might seem essential to maximize the amount of training data by collecting across an array of enterprises to which endpoint protection is deployed, at least in the case of the endpoint protection vendor (itself a major, worldwide company), predictive performance for a single enterprise can remain excellent when training is restricted to the enterprise itself. One advantage of single-enterprise training is the ease of combining different views of the hosts, such as via file-based and network-based monitoring. In the cases studied, although an exact comparison was impossible due to a time gap, the single-enterprise dataset with richer features resulted in superior prediction of malware execution compared to the multi-enterprise dataset.

Despite long-ago predictions [1] that other user-authentication technologies would replace passwords, passwords remain pervasive and are likely to continue to be so [2]. This talk will describe our research on methods to tackle three key ingredients of account takeovers for password-protected accounts today: (i) site database breaches, which is the largest source of stolen passwords for internet sites; (ii) the tendency of users to reuse the same or similar passwords across sites; and (iii) credential stuffing, in which attackers submit breached credentials for one site in login attempts for the same accounts at another. A central theme of our research is that these factors are most effectively addressed by coordinating across sites, in contrast to today's practice of each site defending alone. We summarize algorithms to drive this coordination; the efficacy and security of our proposals; and the scalability of our designs through working implementations.

Among the most challenging traffic-analysis attacks to confound are those leveraging the sizes of objects downloaded over the network. In this paper we systematically analyze this problem under realistic constraints regarding the padding overhead that the object store is willing to incur. We give algorithms to compute privacy-optimal padding schemes—specifically that minimize the network observer's information gain from a downloaded object's padded size—in several scenarios of interest: per-object padding, in which the object store responds to each request for an object with the same padded copy; per-request padding, in which the object store pads an object anew each time it serves that object; and a scenario unlike the previous ones in that the object store is unable to leverage a known distribution over the object queries. We provide constructions for privacy-optimal padding in each case, compare them to recent contenders in the research literature, and evaluate their performance on practical datasets.

Advances in computer vision have made it possible to accurately map objects as regions in 3-dimensional space using LIDAR point clouds. These systems are key building blocks of several emerging technologies including autonomous vehicles. Comparing and validating the output of sensors at different vantage points observing the same scenery can enable these systems to detect faults, identify common obstacles, and improve decision making. However sharing sensor outputs among mutually untrusting parties can leak unwanted information, e.g., model parameters or relative location of the sensors. This work initiates the study of cryptographic protocols that enable two parties observing regions (or objects) in an arbitrary-dimension Euclidean space to privately detect if the regions overlap and approximate the volume of the overlapping region. The protocols rely only on cheap symmetric-key primitives and feature reasonable communication costs and compute times. As applications, the protocols have been benchmarked on data generated from the CARLA autonomous driving simulator and the ScanNet 3D image dataset; they outperform a 2PC garbled-circuit baseline in communication volume and compute time. For instance it takes roughly 0.5 seconds to approximate the volume of the overlapping region of two 3D boxes with low error probability.

Network function (NF) migration alongside (and possibly because of) routing policy updates is a delicate task, making it difficult to ensure that all traffic is processed by its required network functions, in order. Indeed, all previous solutions to this problem adapt routing policy only after NFs have been migrated, in a serial fashion. This paper proposes a design called Nimble for interleaving these tasks to complete both more efficiently while ensuring complete processing of traffic by the required NFs, provided that the route-update protocol enforces a specific property that we define. We demonstrate the benefits of the Nimble design using an implementation in Open vSwitch and the Ryu controller, building on both known routing update protocols and a new protocol of our design that implements specifically the needed property.

Modern Byzantine Fault-Tolerant State Machine Replication (BFT-SMR) solutions focus on reducing communication complexity, improving throughput, or lowering latency. This work explores the energy efficiency of BFT-SMR protocols. First, we propose a novel SMR protocol that optimizes for the steady state, i.e., when the leader is correct. This is done by reducing the number of required signatures per consensus unit and the communication complexity by order of the number of nodes n compared to the state-of-the-art BFT-SMR solutions. Concretely, we employ the idea that a quorum (collection) of signatures on a proposed value is avoidable during the failure-free runs. Second, we model and analyze the energy efficiency of protocols and argue why the steady-state needs to be optimized. Third, we present an application in the cyber-physical system (CPS) setting, where we consider a partially connected system by optionally leveraging wireless multicasts among neighbors. We analytically determine the parameter ranges for when our proposed protocol offers better energy efficiency than communicating with a baseline protocol utilizing an external trusted node. We present a hypergraph-based network model and generalize previous fault tolerance results to the model. Finally, we demonstrate our approach's practicality by analyzing our protocol's energy efficiency through experiments on a CPS test bed. In particular, we observe as high as 64% energy savings when compared to the state-of-the-art SMR solution for n = 10 settings using BLE.

A growing body of work in game theory extends the traditional Stackelberg game to settings with one leader and multiple followers who play a Nash equilibrium. Standard approaches for computing equilibria in these games reformulate the followers' best response as constraints in the leader's optimization problem. These reformulation approaches can sometimes be effective, but make limiting assumptions on the followers' objectives and the equilibrium reached by followers, e.g., uniqueness, optimism, or pessimism. To overcome these limitations, we run gradient descent to update the leader's strategy by differentiating through the equilibrium reached by followers. Our approach generalizes to any stochastic equilibrium selection procedure that chooses from multiple equilibria, where we compute the stochastic gradient by back-propagating through a sampled Nash equilibrium using the solution to a partial differential equation to establish the unbiasedness of the stochastic gradient. Using the unbiased gradient estimate, we implement the gradient-based approach to solve three Stackelberg problems with multiple followers. Our approach consistently outperforms existing baselines to achieve higher utility for the leader.

This paper presents the first critical analysis of building highly secure, performant, and confidential Byzantine fault-tolerant (BFT) consensus by integrating off-the-shelf crash fault-tolerant (CFT) protocols with trusted execution environments (TEEs). TEEs, like Intel SGX, are CPU extensions that offer applications a secure execution environment with strong integrity and confidentiality guarantees, by leveraging techniques like hardware-assisted isolation, memory encryption, and remote attestation. It has been speculated that when implementing a CFT protocol inside Intel SGX, one would achieve security properties similar to BFT. However, we show in this work that simply combining CFT with SGX does not directly yield a secure BFT protocol, given the wide range of attack vectors on SGX. We systematically study the fallacies in such a strawman design by performing model checking, and propose solutions to enforce safety and liveness. We also present ENGRAFT, a secure enclave-guarded Raft implementation that, firstly, achieves consensus on a cluster of 2f+1 machines tolerating up to f nodes exhibiting Byzantine-fault behavior (but well-behaved enclaves); secondly, offers a new abstraction of confidential consensus for privacy-preserving state machine replication; and finally, allows the reuse of a production-quality Raft implementation, BRaft, in the development of a highly performant BFT system.

We propose new, more efficient targeted white-box attacks against deep neural networks. Our attacks better align with the attacker’s goal: (1) tricking a model to assign higher probability to the target class than to any other class, while (2) staying within an $\epsilon$-distance of the attacked input. First, we demonstrate a loss function that explicitly encodes (1) and show that Auto-PGD finds more attacks with it. Second, we propose a new attack method, Constrained Gradient Descent (CGD), using a refinement of our loss function that captures both (1) and (2). CGD seeks to satisfy both attacker objectives—misclassification and bounded $\ell_{p}$-norm—in a principled manner, as part of the optimization, instead of via ad hoc post-processing techniques (e.g., projection or clipping). We show that CGD is more successful on CIFAR10 (0.9–4.2%) and ImageNet (8.6–13.6%) than state-of-the-art attacks while consuming less time (11.4–18.8%). Statistical tests confirm that our attack outperforms others against leading defenses on different datasets and values of $\epsilon$.

A smart contract on a blockchain cannot keep a secret because its data is replicated on all nodes in a network. To remedy this problem, it has been suggested to combine blockchains with trusted execution environments (TEEs), such as Intel SGX, for executing applications that demand privacy. Untrusted blockchain nodes cannot get access to the data and computations inside the TEE. This paper first explores some pitfalls that arise from the combination of TEEs with blockchains. Since TEEs are, in principle, stateless they are susceptible to rollback attacks, which should be prevented to maintain privacy for the application. However, in blockchains with non-final consensus protocols, such as the proof-of-work in Ethereum and others, the contract execution must handle rollbacks by design. This implies that TEEs for securing blockchain execution cannot be directly used for such blockchains; this approach works only when the consensus decisions are final. Second, this work introduces an architecture and a prototype for smart-contract execution within Intel SGX technology for Hyperledger Fabric, a prominent platform for enterprise blockchain applications. Our system resolves difficulties posed by the execute-order-validate architecture of Fabric and prevents rollback attacks on TEE-based execution as far as possible. For increasing security, our design encapsulates each application on the blockchain within its own enclave that shields it from the host system. An evaluation shows that the overhead moving execution into SGX is within 10%-20% for a sealed-bid auction application.

Motivated by the transformative impact of deep neural networks (DNNs) in various domains, researchers and anti-virus vendors have proposed DNNs for malware detection from raw bytes that do not require manual feature engineering. In this work, we propose an attack that interweaves binary-diversification techniques and optimization frameworks to mislead such DNNs while preserving the functionality of binaries. Unlike prior attacks, ours manipulates instructions that are a functional part of the binary, which makes it particularly challenging to defend against. We evaluated our attack against three DNNs in white- and black-box settings, and found that it often achieved success rates near 100%. Moreover, we found that our attack can fool some commercial anti-viruses, in certain cases with a success rate of 85%. We explored several defenses, both new and old, and identified some that can foil over 80% of our evasion attempts. However, these defenses may still be susceptible to evasion by attacks, and so we advocate for augmenting malware-detection systems with methods that do not rely on machine learning.

Historically, enterprise network reconnaissance is an active process, often involving port scanning. However, as routers and switches become more complex, they also become more susceptible to compromise. From this vantage point, an attacker can passively identify high-value hosts such as the workstations of IT administrators, C-suite executives, and finance personnel. The goal of this paper is to develop a technique to deceive and dissuade such adversaries. We propose HoneyRoles, which uses honey connections to build metaphorical haystacks around the network traffic of client hosts belonging to high-value organizational roles. The honey connections also act as network canaries to signal network compromise, thereby dissuading the adversary from acting on information observed in network flows. We design a prototype implementation of HoneyRoles an OpenFlow SDN controller and evaluate its security using the PRISM probabilistic model checker. Our performance evaluation shows that HoneyRoles has a small effect on network request completion time, and security analysis demonstrates that once an alert is raised, HoneyRoles can quickly identify the compromised switch with high probability. In doing so, we show that role-based network deception is a promising approach for defending against adversaries in compromised network devices.

Intel Software Guard Extensions (SGX) provides a trusted execution environment (TEE) to run code and operate sensitive data. SGX provides runtime hardware protection where both code and data are protected even if other code components are malicious. However, recently many attacks targeting SGX have been identified and introduced that can thwart the hardware defence provided by SGX. In this paper we present a survey of all attacks specifically targeting Intel SGX that are known to the authors, to date. We categorized the attacks based on their implementation details into 7 different categories. We also look into the available defence mechanisms against identified attacks and categorize the available types of mitigations for each presented attack.

Web servers are a popular target for adversaries as they are publicly accessible and often vulnerable to compromise. Compromises can go unnoticed for months, if not years, and recovery often involves a complete system rebuild. In this paper, we propose n-m-Variant Systems, an adversarial-resistant software rejuvenation framework for cloud-based web applications. We improve the state-of-the-art by introducing a variable m that provides a knob for administrators to tune an environment to balance resource usage, performance overhead, and security guarantees. Using m, security guarantees can be tuned for seconds, minutes, days, or complete resistance. We design and implement an n-m-Variant System prototype to protect a Mediawiki PHP application serving dynamic content from an external SQL persistent storage. Our performance evaluation shows a throughput reduction of 65% for 108 seconds of resistance and 83% for 12 days of resistance to sophisticated adversaries, given appropriate resource allocation. Furthermore, we use theoretical analysis and simulation to characterize the impact of system parameters on resilience to adversaries. Through these efforts, our work demonstrates how properties of cloud-based servers can enhance the integrity of Web servers.

In this work we develop a novel Bayesian neural network methodology to achieve strong adversarial robustness without the need for online adversarial training. Unlike previous efforts in this direction, we do not rely solely on the stochasticity of network weights by minimizing the divergence between the learned parameter distribution and a prior. Instead, we additionally require that the model maintain some expected uncertainty with respect to all input covariates. We demonstrate that by encouraging the network to distribute evenly across inputs, the network becomes less susceptible to localized, brittle features which imparts a natural robustness to targeted perturbations. We show empirical robustness on several benchmark datasets.

A long-standing technique to interfere with theft of sensitive data by its intended users is permitting these insiders only remote access to the data via a thin client. Even allowing only remote access is inadequate, however, to counter an insider willing to reconstruct the data from the graphical output, in the limit by photographing the data on-screen and applying automatic character recognition to these photographs offline. In this paper we propose and evaluate a system, called Snowman, that accurately monitors the amount of sensitive data output to a client. To conduct this monitoring without slowing the interactive user session, leakage is concurrently tracked in a replica of the application execution. This, in turn, introduces a key technical challenge that Snowman solves, namely identically replicating execution of an unmodified Linux binary while also performing efficient multi-label taint-tracking on it. We show through empirical measurements with a word processor, a spreadsheet program, and a code editor that Snowman induces little overhead on interactive user sessions and easily differentiates data-access patterns induced by normal usage and sufficiently aggressive data theft with reasonable responsiveness.

In this paper, We present a new technique that offers lightweight, general, and elastic protection against Crum (Cross-VM runtime monitoring) attacks. Our protection, called Crease (CPU Resource Elasticity as a Service), enables a VM (called principal) to purchase a higher clock rate from the cloud, through lowering the frequency of a malicious VM (called peer), to support its security-critical operations within a short period. During that period, the weakened peer becomes unable to catch up with the pace of the strengthened principal, therefore losing the capability to effectively collect its sensitive information. In the meantime, our approach can also make up for the performance impact on the peer through refunding schedule credits or service credits, in line with the service level agreement of today's cloud. At the center of our design is the novel application of on-demand frequency scaling and schedule quantum randomization, together with a situation-awareness mechanism that dynamically assesses the security risk posed by the peer. We analyzed the security guarantee of our design, implemented a prototype and evaluated it on a well-known Crum attack (an LLC side-channel attack) and various workloads. Our study shows that Crease is effective at protecting the principal, with only a small impact on the peer's operations.

Byzantine fault tolerant state machine replication (SMR) provides powerful integrity guarantees, but fails to provide any privacy guarantee whatsoever. A natural way to add such privacy guarantees is to secret-share state instead of fully replicating it. Such a com- bination would enable simple solutions to difficult problems, such as a fair exchange or a distributed certification authority. However, incorporating secret shared state into traditional Byzantine fault tolerant (BFT) SMR protocols presents unique challenges. BFT protocols often use a network model that has some degree of asynchrony, making verifiable secret sharing (VSS) unsuitable. However, full asynchronous VSS (AVSS) is unnecessary as well since the BFT algorithm provides a broadcast channel. We first present the VSS with share recovery problem, which is the subproblem of AVSS required to incorporate secret shared state into a BFT engine. Then, we provide the first VSS with share recovery solution, KZG-VSSR, in which a failure-free sharing incurs only a constant number of cryptographic operations per replica. Finally, we show how to efficiently integrate any instantiation of VSSR into a BFT replication protocol while incurring only constant overhead. Instantiating VSSR with prior AVSS protocols would require a quadratic communication cost for a single shared value and incur a linear overhead when incorporated into BFT replication. We demonstrate our end-to-end solution via a a private key-value store built using BFT replication and two instantiations of VSSR, KZG-VSSR and Ped-VSSR, and present its evaluation.

SBFT is a state of the art Byzantine fault tolerant state machine replication system that addresses the challenges of scalability, decentralization and global geo-replication. SBFT is optimized for decentralization and is experimentally evaluated on a deployment of more than 200 active replicas withstanding a malicious adversary controlling f=64 replicas. Our experiments show how the different algorithmic ingredients of SBFT contribute to its performance and scalability. The results show that SBFT simultaneously provides almost 2x better throughput and about 1.5x better latency relative to a highly optimized system that implements the PBFT protocol. To achieve this performance improvement, SBFT uses a combination of four ingredients: using collectors and threshold signatures to reduce communication to linear, using an optimistic fast path, reducing client communication and utilizing redundant servers for the fast path. SBFT is the first system to implement a correct dual-mode view change protocol that allows to efficiently run either an optimistic fast path or a fallback slow path without incurring a view change to switch between modes.

Though centrally managed by a controller, a software-defined network (SDN) can still encounter routing inconsistencies among its switches due to the non-atomic updates to their forwarding tables. In this paper, we propose a new method to rectify these inconsistencies that is inspired by causal consistency, a consistency model for shared-memory systems. Applied to SDNs, causal consistency would imply that once a packet is matched to ("reads") a forwarding rule in a switch, it can be matched in downstream switches only to rules that are equally or more up-to-date. We propose and analyze a relaxed but functionally equivalent version of this property called suffix causal consistency (SCC) and evaluate an implementation of SCC in Open vSwitch and P4 switches, in conjunction with the Ryu and P4Runtime controllers. Our results show that SCC provides greater efficiency than competing consistent-update alternatives while offering consistency that is strong enough to ensure high-level routing properties (black-hole freedom, bounded looping, etc.).

We present HotStuff, a leader-based Byzantine fault-tolerant replication protocol for the partially synchronous model. Once network communication becomes synchronous, HotStuff enables a correct leader to drive the protocol to consensus at the pace of actual (vs. maximum) network delay--a property called responsiveness---and with communication complexity that is linear in the number of replicas. To our knowledge, HotStuff is the first partially synchronous BFT replication protocol exhibiting these combined properties. Its simplicity enables it to be further pipelined and simplified into a practical, concise protocol for building large-scale replication services.

Images perturbed subtly to be misclassified by neural networks, calledadversarial examples, have emerged as a technically deep challenge and an important concern for several application domains. Most research on adversarial examples takes as its only constraint that the perturbed images are similar to the originals. However, real-world application of these ideas often requires the examples to satisfy additional objectives, which are typically enforced through custom modifications of the perturbation process. In this article, we proposeadversarial generative nets(AGNs), a general methodology to train ageneratorneural network to emit adversarial examples satisfying desired objectives. We demonstrate the ability of AGNs to accommodate a wide range of objectives, including imprecise ones difficult to model, in two application domains. In particular, we demonstratephysicaladversarial examples—eyeglass frames designed to fool face recognition—with better robustness, inconspicuousness, and scalability than previous approaches, as well as a new attack to fool a handwritten-digit classifier.

We present BEAT, a set of practical Byzantine fault-tolerant (BFT) protocols for completely asynchronous environments. BEAT is flexible, versatile, and extensible, consisting of five asynchronous BFT protocols that are designed to meet different goals (e.g., different performance metrics, different application scenarios). Due to modularity in its design, features of these protocols can be mixed to achieve even more meaningful trade-offs between functionality and performance for various applications. Through a 92-instance, five-continent deployment of BEAT on Amazon EC2, we show that BEAT is efficient: roughly, all our BEAT instances significantly outperform, in terms of both latency and throughput, HoneyBadgerBFT, the most efficient asynchronous BFT known.

As software-defined networking deployments mature, operators need to manage and compose multiple resource-management applications, such as traffic engineering and service chaining. Today such applications' resource management algorithms run separately and composition approaches are output-driven, e.g., running each application on a statically provisioned slice of the network and then combining the flow rules output for each slice. Such approaches result in inefficient resource utilization and unfairness. Instead, we argue for intent-driven composition, where a unified resource optimization formulation is composed from applications' high-level intents and the solution to this problem formulation is realized in the network. We design Chopin1, an intent-driven framework for composing SDN resource-management applications. Chopin's design addresses key robustness challenges with regard to efficiency and fairness that arise in realizing such an intent-driven approach. We have integrated Chopin with the ONOS controller and show that it substantially improves efficiency and fairness over existing composition approaches.

Searchable encryption enables searches to be performed on encrypted documents stored on an untrusted server without exposing the documents or the search terms to the server. Nevertheless, the server typically learns which encrypted documents match the query-the so-called access pattern-since the server must return those documents. Recent studies have demonstrated that access patterns can be used to infer the search terms in some scenarios. In this paper, we propose a framework to protect systems using searchable symmetric encryption from access-pattern leakage. Our technique is based on d-privacy, a generalized version of differential privacy that provides provable security guarantees against adversaries with arbitrary background knowledge.

Noninterference is a definition of security for secret values provided to a procedure, which informally is met when attacker-observable outputs are insensitive to the value of the secret inputs or, in other words, the secret inputs do not "interfere" with those outputs. This paper describes a static analysis method to measure interference in software. In this approach, interference is assessed using the extent to which different secret inputs are consistent with different attacker-controlled inputs and attacker-observable outputs, which can be measured using a technique called model counting. Leveraging this insight, we develop a flexible interference assessment technique for which the assessment accuracy quantifiably grows with the computational effort invested in the analysis. This paper demonstrates the effectiveness of this technique through application to several case studies, including leakage of: search-engine queries through auto-complete response sizes; secrets subjected to compression together with attacker-controlled inputs; and TCP sequence numbers from shared counters.

Intel Software Guard Extension (SGX) protects the confidentiality and integrity of an unprivileged program running inside a secure enclave from a privileged attacker who has full control of the entire operating system (OS). Program execution inside this enclave is therefore referred to as shielded. Unfortunately, shielded execution does not protect programs from side-channel attacks by a privileged attacker. For instance, it has been shown that by changing page table entries of memory pages used by shielded execution, a malicious OS kernel could observe memory page accesses from the execution and hence infer a wide range of sensitive information about it. In fact, this page-fault side channel is only an instance of a category of side-channel attacks, here called privileged side-channel attacks, in which privileged attackers frequently preempt the shielded execution to obtain fine-grained side-channel observations. In this paper, we present Deja Vu, a software framework that enables a shielded execution to detect such privileged side-channel attacks. Specifically, we build into shielded execution the ability to check program execution time at the granularity of paths in its control-flow graph. To provide a trustworthy source of time measurement, Deja Vu implements a novel software reference clock that is protected by Intel Transactional Synchronization Extensions (TSX), a hardware implementation of transactional memory. Evaluations show that Deja Vu effectively detects side-channel attacks against shielded execution and against the reference clock itself.

We revisit the problem of preserving causality in Byzantine fault-tolerant (BFT) atomic broadcast protocols, a requirement first proposed by Reiter and Birman (TOPLAS 1994). While over the past three decades, this requirement has been met through the deployment of expensive public-key threshold cryptosystems, we propose three novel, secure causal BFT protocols without using public-key cryptography. We implement and evaluate these protocols, showing that they significantly outperform existing constructions that use threshold cryptosystems.

When encountering a packet for which it has no matching forwarding rule, a software-defined networking (SDN) switch requests an appropriate rule from its controller; this request delays the routing of the flow until the controller responds. We show that this delay gives rise to a timing side channel in which an attacker can test for the recent occurrence of a target flow by judiciously probing the switch with forged flows and using the delays they encounter to discern whether covering rules were previously installed in the switch. We develop a Markov model of an SDN switch to permit the attacker to select the best probe (or probes) to infer whether a target flow has recently occurred. Our model captures practical challenges related to rule evictions to make room for other rules; rule timeouts due to inactivity; the presence of multiple rules that apply to overlapping sets of flows; and rule priorities. We show that our model enables detection of target flows with considerable accuracy in many cases.

Abstract Millions of apps available to smartphone owners request various permissions to resources on the devices including sensitive data such as location and contact information. Disabling permissions for sensitive resources could improve privacy but can also impact the usability of apps in ways users may not be able to predict. We study an efficient approach that ascertains the impact of disabling permissions on the usability of apps through large-scale, crowdsourced user testing with the ultimate goal of making recommendations to users about which permissions can be disabled for improved privacy without sacrificing usability. We replicate and significantly extend previous analysis that showed the promise of a crowdsourcing approach where crowd workers test and report back on various configurations of an app. Through a large, between-subjects user experiment, our work provides insight into the impact of removing permissions within and across different apps (our participants tested three apps: Facebook Messenger (N=218), Instagram (N=227), and Twitter (N=110)). We study the impact of removing various permissions within and across apps, and we discover that it is possible to increase user privacy by disabling app permissions while also maintaining app usability.

Abstract A considerable and growing fraction of servers, especially of web servers, is hosted in compute clouds. In this paper we opportunistically leverage this trend to improve privacy of clients from network attackers residing between the clients and the cloud: We design a system that can be deployed by the cloud operator to prevent a network adversary from determining which of the cloud’s tenant servers a client is accessing. The core innovation in our design is a PoPSiCl (pronounced “popsicle”), a persistent pseudonym for a tenant server that can be used by a single client to access the server, whose real identity is protected by the cloud from both passive and active network attackers. When instantiated for TLS-based access to web servers, our design works with all major browsers and requires no additional client-side software and minimal changes to the client user experience. Moreover, changes to tenant servers can be hidden in supporting software (operating systems and web-programming frameworks) without imposing on web-content development. Perhaps most notably, our system boosts privacy with minimal impact to web-browsing performance, after some initial setup during a user’s first access to each web server.

Cloud computing is a dominant trend in computing for the foreseeable future; e.g., major cloud operators are now estimated to house over a million machines each and to host substantial (and growing) fractions of our IT and web infrastructure. CCSW is a forum for bringing together researchers and practitioners to discuss the implications of this trend to the security of cloud operators, tenants, and the larger Internet community. CCSW welcomes submissions on new threats, countermeasures, and opportunities brought about by the move to cloud computing, with a preference for unconventional approaches, as well as measurement studies and case studies that shed light on the security implications of clouds.

Machine learning is enabling a myriad innovations, including new algorithms for cancer diagnosis and self-driving cars. The broad use of machine learning makes it important to understand the extent to which machine-learning algorithms are subject to attack, particularly when used in applications where physical security or safety is at risk.

We present a software approach to mitigate access-driven side-channel attacks that leverage last-level caches (LLCs) shared across cores to leak information between security domains (e.g., tenants in a cloud). Our approach dynamically manages physical memory pages shared between security domains to disable sharing of LLC lines, thus preventing "Flush-Reload" side channels via LLCs. It also manages cacheability of memory pages to thwart cross-tenant "Prime-Probe" attacks in LLCs. We have implemented our approach as a memory management subsystem called CacheBar within the Linux kernel to intervene on such side channels across container boundaries, as containers are a common method for enforcing tenant isolation in Platform-as-a-Service (PaaS) clouds. Through formal verification, principled analysis, and empirical evaluation, we show that CacheBar achieves strong security with small performance overheads for PaaS workloads.

Modern Internet applications are being disaggregated into a microservice-based architecture, with services being updated and deployed hundreds of times a day. The accelerated software life cycle and heterogeneity of language runtimes in a single application necessitates a new approach for testing the resiliency of these applications in production infrastructures. We present Gremlin, a framework for systematically testing the failure-handling capabilities of microservices. Gremlin is based on the observation that microservices are loosely coupled and thus rely on standard message-exchange patterns over the network. Gremlin allows the operator to easily design tests and executes them by manipulating inter-service messages at the network layer. We show how to use Gremlin to express common failure scenarios and how developers of an enterprise application were able to discover previously unknown bugs in their failure-handling code without modifying the application.

We have developed education modules for topics in networking, security, and cloud computing. A networking instructor could use our modules to enhance the teaching of basic concepts by demonstrating these concepts with real experiments on GENI testbeds. Any systems instructor could use our security or cloud computing modules to begin teaching new topics, or enhance existing topics by adding hands-on experiments on GENI and CloudLab testbeds. Our NSF funded projects to develop these curricular modules have been successfully used by several instructors. Attendees at SIGCSE would comprise exactly the kind of audience, from varied institutions and dedicated to enhancing their curriculum, for whom we've built these modules. Our modules are freely available, and we are committed to helping instructors use our modules in their courses. The underlying testbeds, GENI and CloudLab, are also NSF-funded and thus freely available for instructors to use. Attendees will be provided a handout that contains relevant information, including contact for help, as they go back and begin using our education modules in their curriculum.

In response to the critical challenges of the current Internet architecture and its protocols, a set of so-called clean slate designs has been proposed. Common among them is an addressing scheme that separates location and identity with self-certifying, flat and non-aggregatable address components. Each component is long, reaching a few kilobits, and would consume an amount of fast memory in data plane devices (e.g., routers) that is far beyond existing capacities. To address this challenge, we present Caesar, a high-speed and length-agnostic forwarding engine for future border routers, performing most of the lookups within three fast memory accesses. To compress forwarding states, Caesar constructs scalable and reliable Bloom filters in Ternary Content Addressable Memory (TCAM). To guarantee correctness, Caesar detects false positives at high speed and develops a blacklisting approach to handling them. In addition, we optimize our design by introducing a hashing scheme that reduces the number of hash computations from k to log(k) per lookup based on hash coding theory. We handle routing updates while keeping filters highly utilized in address removals. We perform extensive analysis and simulations using real traffic and routing traces to demonstrate the benefits of our design. Our evaluation shows that Caesar is more energy-efficient and less expensive (in terms of total cost) compared to optimized IPv6 TCAM-based solutions by up to 67% and 43% respectively. In addition, the total cost of our design is approximately the same for various address lengths.

Recent studies have shown a range of co-residency side channels that can be used to extract private information from cloud clients. Unfortunately, addressing these side channels often requires detailed attack-specific fixes that require significant modifications to hardware, client virtual machines (VM), or hypervisors. Furthermore, these solutions cannot be generalized to future side channels. Barring extreme solutions such as single tenancy which sacrifices the multiplexing benefits of cloud computing, such side channels will continue to affect critical services. In this work, we present Nomad, a system that offers vector-agnostic defense against known and future side channels. Nomad envisions a provider-assisted VM migration service, applying the moving target defense philosophy to bound the information leakage due to side channels. In designing Nomad, we make four key contributions: (1) a formal model to capture information leakage via side channels in shared cloud deployments; (2) identifying provider-assisted VM migration as a robust defense for arbitrary side channels; (3) a scalable online VM migration heuristic that can handle large datacenter workloads; and (4) a practical implementation in OpenStack. We show that Nomad is scalable to large cloud deployments, achieves near-optimal information leakage subject to constraints on migration overhead, and imposes minimal performance degradation for typical cloud applications such as web services and Hadoop MapReduce.

A storage side channel occurs when an adversary accesses data objects influenced by another, victim computation and infers information about the victim that it is not permitted to learn directly. We bring advances in privacy for statistical databases to bear on storage side-channel defense, and specifically demonstrate the feasibility of applying differentially private mechanisms to mitigate storage side channels in procfs, a pseudo file system broadly used in Linux and Android kernels. Using a principled design with quantifiable security, our approach injects noise into kernel data-structure values that are used to generate procfs contents, but also reestablishes invariants on these noised values so as to not violate assumptions on which procfs or its clients depend. We show that our modifications to procfs can be configured to mitigate known storage side channels while preserving its utility for monitoring and diagnosis.

Smartphone apps today request permission to access a multitude of sensitive resources, which users must accept completely during installation (e.g., on Android) or selectively configure after installation (e.g., on iOS, but also planned for Android). Everyday users, however, do not have the ability to make informed decisions about which permissions are essential for their usage. For enhanced privacy, we seek to leverage crowdsourcing to find minimal sets of permissions that will preserve the usability of the app for diverse users. We advocate an efficient 'lattice-based' crowd-management strategy to explore the space of permissions sets. We conducted a user study (N = 26) in which participants explored different permission sets for the popular Instagram app. This study validates our efficient crowd management strategy and shows that usability scores for diverse users can be predicted accurately, enabling suitable recommendations.

We explore the problem of placing object replicas on nodes in a distributed system to maximize the number of objects that remain available when node failures occur. In our model, failing (the nodes hosting) a given threshold of replicas is sufficient to disable each object, and the adversary selects which nodes to fail to minimize the number of objects that remain available. We specifically explore placement strategies based on combinatorial structures called t-packings, provide a lower bound for the object availability they offer, show that these placements offer availability that is c-competitive with optimal, propose an efficient algorithm for computing combinations of t-packings that maximize their availability lower bound, and provide parameter selection strategies to concretely instantiate our schemes for different system sizes. We compare the availability offered by our approach to that of random replica placement, owing to the popularity of the latter approach in previous work. After quantifying the availability offered by random replica placement in our model, we show that our combinatorial strategy yields placements with better availability than random replica placement for many realistic parameter values.

We present an epidemiological study of malware encounters in a large, multi-national enterprise. Our data sets allow us to observe or infer not only malware presence on enterprise computers, but also malware entry points, network locations of the computers (i.e., inside the enterprise network or outside) when the malware were encountered, and for some web-based malware encounters, web activities that gave rise to them. By coupling this data with demographic information for each host's primary user, such as his or her job title and level in the management hierarchy, we are able to paint a reasonably comprehensive picture of malware encounters for this enterprise. We use this analysis to build a logistic regression model for inferring the risk of hosts encountering malware; those ranked highly by our model have a >3x higher rate of encountering malware than the base rate. We also discuss where our study confirms or refutes other studies and guidance that our results suggest.

We present a new attack framework for conducting cache-based side-channel attacks and demonstrate this framework in attacks between tenants on commercial Platform-as-a-Service (PaaS) clouds. Our framework uses the FLUSH-RELOAD attack of Gullasch et al. as a primitive, and extends this work by leveraging it within an automaton-driven strategy for tracing a victim's execution. We leverage our framework first to confirm co-location of tenants and then to extract secrets across tenant boundaries. We specifically demonstrate attacks to collect potentially sensitive application data (e.g., the number of items in a shopping cart), to hijack user accounts, and to break SAML single sign-on. To the best of our knowledge, our attacks are the first granular, cross-tenant, side-channel attacks successfully demonstrated on state-of-the-art commercial clouds, PaaS or otherwise.

People increasingly rely on mobile phones for storing sensitive information and credentials for access to services. Because these devices are vulnerable to theft, security of this data is put at higher risk - once the attacker is in physical possession of the device, recovering these credentials and

OBJECTIVE: Record linkage to integrate uncoordinated databases is critical in biomedical research using Big Data. Balancing privacy protection against the need for high quality record linkage requires a human-machine hybrid system to safely manage uncertainty in the ever changing streams of chaotic Big Data. METHODS: In the computer science literature, private record linkage is the most published area. It investigates how to apply a known linkage function safely when linking two tables. However, in practice, the linkage function is rarely known. Thus, there are many data linkage centers whose main role is to be the trusted third party to determine the linkage function manually and link data for research via a master population list for a designated region. Recently, a more flexible computerized third-party linkage platform, Secure Decoupled Linkage (SDLink), has been proposed based on: (1) decoupling data via encryption, (2) obfuscation via chaffing (adding fake data) and universe manipulation; and (3) minimum information disclosure via recoding. RESULTS: We synthesize this literature to formalize a new framework for privacy preserving interactive record linkage (PPIRL) with tractable privacy and utility properties and then analyze the literature using this framework. CONCLUSIONS: Human-based third-party linkage centers for privacy preserving record linkage are the accepted norm internationally. We find that a computer-based third-party platform that can precisely control the information disclosed at the micro level and allow frequent human interaction during the linkage process, is an effective human-machine hybrid system that significantly improves on the linkage center model both in terms of privacy and utility.

This article presents StopWatch, a system that defends against timing-based side-channel attacks that arise from coresidency of victims and attackers in infrastructure-as-a-service clouds. StopWatch triplicates each cloud-resident guest virtual machine (VM) and places replicas so that the three replicas of a guest VM are coresident with nonoverlapping sets of (replicas of) other VMs. StopWatch uses the timing of I/O events at a VM’s replicas collectively to determine the timings observed by each one or by an external observer, so that observable timing behaviors are similarly likely in the absence of any other individual, coresident VMs. We detail the design and implementation of StopWatch in Xen, evaluate the factors that influence its performance, demonstrate its advantages relative to alternative defenses against timing side channels with commodity hardware, and address the problem of placing VM replicas in a cloud under the constraints of StopWatch so as to still enable adequate cloud utilization.

Population informatics is the systematic study of populations via secondary analysis of massive data collections about people, called the social genome. A major challenge in building the social genome is the difficulty in data integration of heterogeneous and uncoordinated data while protecting the confidentiality of the data subjects. Here, we present our work in designing a flexible computerized third party linkage platform, Secure Decoupled Linkage (SDLink), which can provide both privacy protection and accurate high quality integrated data using a hybrid human-machine data integration system. Our evaluation results show that chaffing used in combination with universe manipulation is very effective in blocking inferences during the clerical review process.

This paper presents the design, implementation and evaluation of a system called Düppel that enables a tenant virtual machine to defend itself from cache-based side-channel attacks in public clouds. Düppel includes defenses for time-shared caches such as per-core L1 and L2 caches. Experiments in the lab and on public clouds show that Düppel effectively obfuscates timing signals available to an attacker VM via these caches and incurs modest performance overheads (at most 7% and usually much less) in the common case of no side-channel attacks. Moreover, Düppel requires no changes to hypervisors or support from cloud operators.

This paper presents StopWatch , a system that defends against timing-based side-channel attacks that arise from coresidency of victims and attackers in infrastructure-as-a-service clouds. StopWatch triplicates each cloud-resident guest virtual machine (VM) and places replicas so that the three replicas of a guest VM are coresident with nonoverlapping sets of (replicas of) other VMs. StopWatch uses the timing of I/O events at a VM's replicas collectively to determine the timings observed by each one or by an external observer, so that observable timing behaviors are similarly likely in the absence of any other individual, coresident VM. We detail the design and implementation of StopWatch in Xen, evaluate the factors that influence its performance, and address the problem of placing VM replicas in a cloud under the constraints of StopWatch so as to still enable adequate cloud utilization.

This paper details the construction of an access-driven side-channel attack by which a malicious virtual machine (VM) extracts fine-grained information from a victim VM running on the same physical computer. This attack is the first such attack demonstrated on a symmetric multiprocessing system virtualized using a modern VMM (Xen). Such systems are very common today, ranging from desktops that use virtualization to sandbox application or OS compromises, to clouds that co-locate the workloads of mutually distrustful customers. Constructing such a side-channel requires overcoming challenges including core migration, numerous sources of channel noise, and the difficulty of preempting the victim with sufficient frequency to extract fine-grained information from it. This paper addresses these challenges and demonstrates the attack in a lab setting by extracting an ElGamal decryption key from a victim using the most recent version of the libgcrypt cryptographic library.

Users often have rich and complex photo-sharing preferences, but properly configuring access control can be difficult and time-consuming. In an 18-participant laboratory study, we explore whether the keywords and captions with which users tag their photos can be used to help users more intuitively create and maintain access-control policies. We find that (a) tags created for organizational purposes can be repurposed to create efficient and reasonably accurate access-control rules; (b) users tagging with access control in mind develop coherent strategies that lead to significantly more accurate rules than those associated with organizational tags alone; and (c) participants can understand and actively engage with the concept of tag-based access control.

Accesses that are not permitted by implemented policy but that share similarities with accesses that have been allowed, may be indicative of access-control policy misconfigurations. Identifying such misconfigurations allows administrators to resolve them before they interfere with the use of the system. We improve upon prior work in identifying such misconfigurations in two main ways. First, we develop a new methodology for evaluating misconfiguration prediction algorithms and applying them to real systems. We show that previous evaluations can substantially overestimate the benefits of using such algorithms in practice, owing to their tendency to reward predictions that can be deduced to be redundant. We also show, however, that these and other deductions can be harnessed to substantially recover the benefits of prediction. Second, we propose an approach that significantly simplifies the use of misconfiguration prediction algorithms. We remove the need to hand-tune (and empirically determine the effects of) various parameters, and instead replace them with a single, intuitive tuning parameter. We show empirically that this approach is generally competitive in terms of benefit and accuracy with algorithms that require hand-tuned parameters.

As traffic volumes and the types of analysis grow, network intrusion detection systems (NIDS) face a continuous scaling challenge. Management realities, however, limit NIDS hardware upgrades to occur typically once every 3-5 years. Given that traffic patterns can change dramatically, this leaves a significant scaling challenge in the interim. This motivates the need for practical solutions that can help administrators better utilize and augment their existing NIDS infrastructure. To this end, we design a general architecture for network-wide NIDS deployment that leverages three scaling opportunities: on-path distribution to split responsibilities, replicating traffic to NIDS clusters, and aggregating intermediate results to split expensive NIDS processing. The challenge here is to balance both the compute load across the network and the total communication cost incurred via replication and aggregation. We implement a backwards-compatible mechanism to enable existing NIDS infrastructure to leverage these benefits. Using emulated and trace-driven evaluations on several real-world network topologies, we show that our proposal can substantially reduce the maximum computation load, provide better resilience under traffic variability, and offer improved detection coverage.

We take a detailed look at how users, while focusing on non-permission tasks, notice and fix access-control permission errors depending on where the access-control policy is spatially located on a photo-sharing website. The access-control policy was placed on an online photo-sharing website under the photo or album, on the sidebar, or on a separate settings page. We find that placing the access-control policy directly under photos and album thumbnails improves participants' ability to notice errors in their access-control settings without negatively impacting non-access-control tasks.

Audit logs are an integral part of modern computer systems due to their forensic value. Protecting audit logs on a physically unprotected machine in hostile environments is a challenging task, especially in the presence of active adversaries. It is critical for such a system to have forward security and append-only properties such that when an adversary compromises a logging machine, she cannot forge or selectively delete the log entries accumulated before the compromise. Existing public-key-based secure logging schemes are computationally costly. Existing symmetric secure logging schemes are not publicly verifiable and open to certain attacks. In this article, we develop a new forward-secure and aggregate signature scheme called Blind-Aggregate-Forward (BAF) , which is suitable for secure logging in resource-constrained systems. BAF is the only cryptographic secure logging scheme that can produce publicly verifiable, forward-secure and aggregate signatures with low computation, key/signature storage, and signature communication overheads for the loggers, without requiring any online trusted third party support . A simple variant of BAF also allows a fine-grained verification of log entries without compromising the security or computational efficiency of BAF. We prove that our schemes are secure in Random Oracle Model (ROM). We also show that they are significantly more efficient than all the previous publicly verifiable cryptographic secure logging schemes.

File system virtual appliances (FSVAs) address the portability headaches that plague file system (FS) developers. By packaging their FS implementation in a virtual machine (VM), separate from the VM that runs user applications, they can avoid the need to port the file system to each operating system (OS) and OS version. A small FS-agnostic proxy, maintained by the core OS developers, connects the FSVA to whatever OS the user chooses. This article describes an FSVA design that maintains FS semantics for unmodified FS implementations and provides desired OS and virtualization features, such as a unified buffer cache and VM migration. Evaluation of prototype FSVA implementations in Linux and NetBSD, using Xen as the virtual machine manager (VMM), demonstrates that the FSVA architecture is efficient, FS-agnostic, and able to insulate file system implementations from OS differences that would otherwise require explicit porting.

Although malleability is undesirable in traditional digital signatures, schemes with limited malleability properties enable interesting functionalities that may be impossible to obtain otherwise (e.g., homomorphic signatures). In this paper, we introduce a new malleable signature scheme called bounded vector signatures. The proposed scheme allows a user to sign a multi-dimensional vector of values, along with a description of the context within which the vector should be interpreted. The scheme includes a unique malleability property, which we refer to as the stretch property, that allows the components of the signed vector to be increased up to a pre-defined limit without access to the signing key. Decreasing these values, however, remains computationally infeasible. We prove the security of our construction under the strong RSA and decisional Diffie-Hellman assumptions in the random oracle model. Finally, we underscore the utility of bounded vector signatures by discussing their use in distributed systems security applications.

In access-control systems, policy rules conflict when they prescribe different decisions (allow or deny) for the same access. We present the results of a user study that demonstrates the significant impact of conflict-resolution method on policy-authoring usability. In our study of 54 participants, varying the conflict-resolution method yielded statistically significant differences in accuracy in five of the six tasks we tested, including differences in accuracy rates of up to 78%. Our results suggest that a conflict-resolution method favoring rules of smaller scope over rules of larger scope is more usable than the Microsoft Windows operating system's method of favoring deny rules over allow rules. Perhaps more importantly, our results demonstrate that even seemingly small changes to a system's semantics can fundamentally affect the system's usability in ways that are beyond the power of user interfaces to correct.

We present a methodology for identifying sensitive data in packet payloads, motivated by the need to sanitize packets before releasing them (e.g., for network security/dependability analysis). Our methodology accommodates packets recorded from an incompletely documented protocol, in which case it will be necessary to consult a human expert to determine what packet data is sensitive. Since expert availability for such tasks is limited, however, our methodology adopts a hierarchical approach in which most packet inspection is done by less-trained workers whose designations of sensitive data in selected packets best match the expert's. At the core of our methodology is a data reduction and presentation algorithm that selects candidate workers based on their evaluations of a small number of packets; that solicits these workers' designations of sensitive data in a larger (but still minuscule) subset of packets; and then applies these designations to mark sensitive data in the entire data set. We detail our algorithms and evaluate them in a realistic user study.

Most network deployments respond to changing application, workload, and policy requirements via the deployment of specialized network appliances or "middleboxes". Despite the critical role that middleboxes play in introducing new network functionality, they have been surprisingly ignored in recent efforts for designing networks that are amenable to innovation. We make the case that enabling innovation in middleboxes is at least as important, if not more important, as that for traditional switches and routers. To this end, our vision is a world with software-centric middlebox implementations running on general-purpose hardware platforms that are managed via open and extensible management APIs. While these principles have been applied in other contexts, they introduce unique opportunities and challenges in the context of middleboxes that we highlight in this paper.

Security is a major barrier to enterprise adoption of cloud computing. Physical co-residency with other tenants poses a particular risk, due to pervasive virtualization in the cloud. Recent research has shown how side channels in shared hardware may enable attackers to exfiltrate sensitive data across virtual machines (VMs). In view of such risks, cloud providers may promise physically isolated resources to select tenants, but a challenge remains: Tenants still need to be able to verify physical isolation of their VMs. We introduce Home Alone, a system that lets a tenant verify its VMs' exclusive use of a physical machine. The key idea in Home Alone is to invert the usual application of side channels. Rather than exploiting a side channel as a vector of attack, Home Alone uses a side-channel (in the L2 memory cache) as a novel, defensive detection tool. By analyzing cache usage during periods in which "friendly" VMs coordinate to avoid portions of the cache, a tenant using Home Alone can detect the activity of a co-resident "foe" VM. Key technical contributions of Home Alone include classification techniques to analyze cache usage and guest operating system kernel modifications that minimize the performance impact of friendly VMs sidestepping monitored cache portions. Home Alone requires no modification of existing hyper visors and no special action or cooperation by the cloud provider.

Access-control policy misconfigurations that cause requests to be erroneously denied can result in wasted time, user frustration, and, in the context of particular applications (e.g., health care), very severe consequences. In this article we apply association rule mining to the history of accesses to predict changes to access-control policies that are likely to be consistent with users' intentions, so that these changes can be instituted in advance of misconfigurations interfering with legitimate accesses. Instituting these changes requires the consent of the appropriate administrator, of course, and so a primary contribution of our work is how to automatically determine from whom to seek consent and how to minimize the costs of doing so. We show using data from a deployed access-control system that our methods can reduce the number of accesses that would have incurred costly time-of-access delays by 43%, and can correctly predict 58% of the intended policy. These gains are achieved without impacting the total amount of time users spend interacting with the system.

Online gaming is a lucrative and growing industry but one that is slowed by cheating that compromises the gaming experience and hence drives away players (and revenue). In this paper we develop a technique by which game developers can enable game operators to validate the behavior of game clients as being consistent with valid execution of the sanctioned client software. Our technique employs symbolic execution of the client software to extract constraints on client-side state implied by each client-to-server message, and then uses constraint solving to determine whether the sequence of client-to-server messages can be “explained” by any possible user inputs, in light of the server-to-client messages already received. The requisite constraints and solving components can be developed either simultaneously with the game or retroactively for existing games. We demonstrate our approach in three case studies on the open-source game XPilot , a game similar to Pac-Man of our own design, and an open-source multiplayer version of Tetris .

A power grid is a complex system connecting electric power generators to consumers through power transmission and distribution networks across a large geographical area. System monitoring is necessary to ensure the reliable operation of power grids, and state estimation is used in system monitoring to best estimate the power grid state through analysis of meter measurements and power system models. Various techniques have been developed to detect and identify bad measurements, including interacting bad measurements introduced by arbitrary, nonrandom causes. At first glance, it seems that these techniques can also defeat malicious measurements injected by attackers. In this article, we expose an unknown vulnerability of existing bad measurement detection algorithms by presenting and analyzing a new class of attacks, called false data injection attacks , against state estimation in electric power grids. Under the assumption that the attacker can access the current power system configuration information and manipulate the measurements of meters at physically protected locations such as substations, such attacks can introduce arbitrary errors into certain state variables without being detected by existing algorithms. Moreover, we look at two scenarios, where the attacker is either constrained to specific meters or limited in the resources required to compromise meters. We show that the attacker can systematically and efficiently construct attack vectors in both scenarios to change the results of state estimation in arbitrary ways. We also extend these attacks to generalized false data injection attacks , which can further increase the impact by exploiting measurement errors typically tolerated in state estimation. We demonstrate the success of these attacks through simulation using IEEE test systems, and also discuss the practicality of these attacks and the real-world constraints that limit their effectiveness.

This paper presents the first large-scale study of the success of password expiration in meeting its intended purpose, namely revoking access to an account by an attacker who has captured the account's password. Using a dataset of over 7700 accounts, we assess the extent to which passwords that users choose to replace expired ones pose an obstacle to the attacker's continued access. We develop a framework by which an attacker can search for a user's new password from an old one, and design an efficient algorithm to build an approximately optimal search strategy. We then use this strategy to measure the difficulty of breaking newly chosen passwords from old ones. We believe our study calls into question the merit of continuing the practice of password expiration.

As digital content becomes more prevalent in the home, non-technical users are increasingly interested in sharing that content with others and accessing it from multiple devices. Not much is known about how these users think about controlling access to this data. To better understand this, we conducted semi-structured, in-situ interviews with 33 users in 15 households. We found that users create ad-hoc access-control mechanisms that do not always work; that their ideal policies are complex and multi-dimensional; that a priori policy specification is often insufficient; and that people's mental models of access control and security are often misaligned with current systems. We detail these findings and present a set of associated guidelines for designing usable access-control systems for the home environment.

Traditional efforts for scaling network intrusion detection (NIDS) and intrusion prevention systems (NIPS) have largely focused on a single-vantage-point view. In this paper, we explore an alternative design that exploits spatial, network-wide opportunities for distributing NIDS and NIPS functions. For the NIDS case, we design a linear programming formulation to assign detection responsibilities to nodes while ensuring that no node is overloaded. We describe a prototype NIDS implementation adapted from the Bro system to analyze traffic per these assignments, and demonstrate the advantages that this approach achieves. For NIPS, we show how to maximally leverage specialized hardware (e.g., TCAMs) to reduce the footprint of unwanted traffic on the network. Such hardware constraints make the optimization problem NP-hard, and we provide practical approximation algorithms based on randomized rounding.

Zzyzx is a Byzantine fault-tolerant replicated state machine protocol that outperforms prior approaches and provides near-linear throughput scaling. Using a new technique called Byzantine Locking, Zzyzx allows a client to extract state from an underlying replicated state machine and access it via a second protocol specialized for use by a single client. This second protocol requires just one round-trip and 2 f + 1 responsive servers-compared to Zyzzyva, this results in 39-43% lower response times and a factor of 2.2-2.9× higher throughput. Furthermore, the extracted state can be transferred to other servers, allowing non-overlapping sets of servers to manage different state. Thus, Zzyzx allows throughput to be scaled by adding servers when concurrent data sharing is not common. When data sharing is common, performance can match that of the underlying replicated state machine protocol.

Peer-to-peer (P2P) substrates are now widely used for both file-sharing and botnet command-and-control. Despite the commonality of their substrates, we show that the different goals and circumstances of these applications give rise to behaviors that can be distinguished in network flow records. Using features related to traffic volume, “churn” among peers, and differences between human-driven and machine-driven traffic, we develop a technique for identifying P2P bots (the Plotters) and, in particular, separating them from file-sharing hosts (the Traders). Evaluations performed on traffic recorded at the edge of a university network show that we can achieve, e.g., 87.50% detection of Storm bots with a 0.47% false positive rate. We also demonstrate the significant extent to which Plotter behaviors would need to change to evade our technique.

Network management applications require accurate estimates of a wide range of flow-level traffic metrics. Given the inadequacy of current packet-sampling-based solutions, several application-specific monitoring algorithms have emerged. While these provide better accuracy for the specific applications they target, they increase router complexity and require vendors to commit to hardware primitives without knowing how useful they will be to meet the needs of future applications. In this paper, we show using trace-driven evaluations that such complexity and early commitment may not be necessary. We revisit the case for a "minimalist" approach in which a small number of simple yet generic router primitives collect flow-level data from which different traffic metrics can be estimated. We demonstrate the feasibility and promise of such a minimalist approach using flow sampling and sample-and-hold as sampling primitives and configuring these in a network-wide coordinated fashion using cSamp. We show that this proposal yields better accuracy across a collection of application-level metrics than dividing the same memory resources across metric-specific algorithms. Moreover, because a minimalist approach enables late binding to what application level metrics are important, it better insulates router implementations and deployments from changing monitoring needs.

The web is a complicated graph, with millions of websites interlinked together. In this paper, we propose to use this web sitegraph structure to mitigate flooding attacks on a website, using a new web referral architecture for privileged service (“WRAPS”). WRAPS allows a legitimate client to obtain a privilege URL through a simple click on a referral hyperlink, from a website trusted by the target website. Using that URL, the client can get privileged access to the target website in a manner that is far less vulnerable to a distributed denial-of-service (DDoS) flooding attack than normal access would be. WRAPS does not require changes to web client software and is extremely lightweight for referrer websites, which makes its deployment easy. The massive scale of the web sitegraph could deter attempts to isolate a website through blocking all referrers. We present the design of WRAPS, and the implementation of a prototype system used to evaluate our proposal. Our empirical study demonstrates that WRAPS enables legitimate clients to connect to a website smoothly in spite of a very intensive flooding attack, at the cost of small overheads on the website's ISP's edge routers. We discuss the security properties of WRAPS and a simple approach to encourage many small websites to help protect an important site during DoS attacks.

A power grid is a complex system connecting electric power generators to consumers through power transmission and distribution networks across a large geographical area. System monitoring is necessary to ensure the reliable operation of power grids, and state estimation is used in system monitoring to best estimate the power grid state through analysis of meter measurements and power system models. Various techniques have been developed to detect and identify bad measurements, including the interacting bad measurements introduced by arbitrary, non-random causes. At first glance, it seems that these techniques can also defeat malicious measurements injected by attackers.

In this paper, we present a new approach to performing important classes of genomic computations (e.g., search for homologous genes) that makes a significant step towards privacy protection in this domain. Our approach leverages a key property of the human genome, namely that the vast majority of it is shared across humans (and hence public), and consequently relatively little of it is sensitive. Based on this observation, we propose a privacy-protection framework that partitions a genomic computation, distributing the part on sensitive data to the data provider and the part on the pubic data to the user of the data. Such a partition is achieved through program specialization that enables a biocomputing program to perform a concrete execution on public data and a symbolic execution on sensitive data. As a result, the program is simplified into an efficient query program that takes only sensitive genetic data as inputs. We prove the effectiveness of our techniques on a set of dynamic programming algorithms fundamental to genomic computing. We develop a program transformation tool that automatically instruments a legacy program for specialization operations. We also demonstrate that our techniques can greatly facilitate secure multi-party computations on large biocomputing problems.

In this work we ask the question: what are the challenges of managing a physical or file system access-control policy for a large organization? To answer the question, we conducted a series of interviews with thirteen administrators who manage access-control policy for either a file system or a physical space. Based on these interviews we identified three sets of real-world requirements that are either ignored or inadequately addressed by technology: 1) policies are made/implemented by multiple people; 2) policy makers are distinct from policy implementers; and 3) access-control systems don't always have the capability to implement the desired policy. We present our interview results and propose several possible solutions to address the observed issues.

Busy networks today cannot afford to log all traffic traversing them, and consequently many network-monitoring applications make due with coarse traffic summaries. In this talk we will describe an approach we have developed to improve the fidelity of these traffic summaries, by coordinating the monitoring performed by the network's routers so as to achieve network-wide monitoring goals while respecting each router's processing constraints. We will also describe our use of traffic summaries to detect a variety of stealthy network abuses—e.g., file-sharing traffic masquerading on other application ports, "hit-list" scans and malware propagation, data exfiltration by spyware, and botnet command-and-control traffic—and even to identify the origin of epidemic malware spreads.

A number of research systems have demonstrated the benefits of accompanying each request with a machine-checkable proof that the request complies with access-control policy - a technique called proof-carrying authorization. Numerous authorization logics have been proposed as vehicles by which these proofs can be expressed and checked. A challenge in building such systems is how to allow delegation between institutions that use different authorization logics. Instead of trying to develop the authorization logic that all institutions should use, we propose a framework for interfacing different, mutually incompatible authorization logics. Our framework provides a very small set of primitives that defines an interface for communication between different logics without imposing any fundamental constraints on their design or nature. We illustrate by example that a variety of different logics can communicate over this interface, and show formally that supporting the interface does not impinge on the integrity of each individual logic. We also describe an architecture for constructing authorization proofs that contain components from different logics and report on the performance of a prototype proof checker.

In wide-area settings, unpredictable events, such as flash crowds caused by nearly instantaneous popularity of services, can cause servers that are expected to respond quickly to instead suddenly respond slowly. This presents a problem for achieving consistently good performance in quorum-based distributed systems, in which clients must choose which quorums (sets of servers) to access. Typically,clients are motivated to choose quorums containing the servers that respond fastest. Often, these may be the closest servers, but when the closest servers are particularly slow to respond, e.g., because of a changed workload, servers that are farther may actually respond faster. In this paper, we show how clients can locally change their quorum selections efficiently such that the overall system performance rapidly converges to that of the best global strategy for the current conditions. Moreover, we discuss how to benefit even when changes in quorums must be accompanied by expensive state-transfer operations.

Many host-based anomaly detection techniques have been proposed to detect code-injection attacks on servers. The vast majority, however, are susceptible to "mimicry" attacks in which the injected code masquerades as the original server software, including returning the correct service responses, while conducting its attack. "Behavioral distance," by which two diverse replicas processing the same inputs are continually monitored to detect divergence in their low-level (system-call) behaviors and hence potentially the compromise of one of them, has been proposed for detecting mimicry attacks. In this paper, we present a novel approach to behavioral distance measurement using a new type of hidden Markov model, and present an architecture realizing this new approach. We evaluate the detection capability of this approach using synthetic workloads and recorded workloads of production Web and game servers, and show that it detects intrusions with substantially greater accuracy than a prior proposal on measuring behavioral distance. We also detail the design and implementation of a new architecture, which takes advantage of virtualization to measure behavioral distance. We apply our architecture to implement intrusion-tolerant Web and game servers, and through trace-driven simulations demonstrate that it experiences moderate performance costs even when thresholds are set to detect stealthy mimicry attacks.

We explore the extent to which newly available CPU-based security technology can reduce the Trusted Computing Base (TCB) for security-sensitive applications. We find that although this new technology represents a step in the right direction, significant performance issues remain. We offer several suggestions that leverage existing processor technology, retain security, and improve performance. Implementing these recommendations will finally allow application developers to focus exclusively on the security of their own code, enabling it to execute in isolation from the numerous vulnerabilities in the underlying layers of legacy code.

Although biometrics have garnered significant interest as a source of entropy for cryptographic key generation, recent studies indicate that many biometric modalities may not actually offer enough uncertainty for this purpose. In this paper, we exploit a novel source of entropy that can be used with any biometric modality but that has yet to be utilized for key generation, namely associating uncertainty with the way in which the biometric input is measured. Our construction poses only a modest requirement on a user: the ability to remember a low-entropy password. We identify the technical challenges of this approach, and develop novel techniques to overcome these difficulties. Our analysis of this approach indicates that it may offer the potential to generate stronger keys: In our experiments, 40% of the users are able to generate keys that are at least 230 times stronger than passwords alone.

Significant effort has been invested in developing expressive and flexible access-control languages and systems. However, little has been done to evaluate these systems in practical situations with real users, and few attempts have been made to discover and analyze the access-control policies that users actually want to implement. We report on a user study in which we derive the ideal access policies desired by a group of users for physical security in an office environment. We compare these ideal policies to the policies the users actually implemented with keys and with a smartphone-based distributed access-control system. We develop a methodology that allows us to show quantitatively that the smartphone system allowed our users to implement their ideal policies more accurately and securely than they could with keys, and we describe where each system fell short.

We introduce the Expandable Grid, a novel interaction technique for creating, editing, and viewing many types of security policies. Security policies, such as file permissions policies, have traditionally been displayed and edited in user interfaces based on a list of rules, each of which can only be viewed or edited in isolation. These list-of-rules interfaces cause problems for users when multiple rules interact, because the interfaces have no means of conveying the interactions amongst rules to users. Instead, users are left to figure out these rule interactions themselves. An Expandable Grid is an interactive matrix visualization designed to address the problems that list-of-rules interfaces have in conveying policies to users. This paper describes the Expandable Grid concept, shows a system using an Expandable Grid for setting file permissions in the Microsoft Windows XP operating system, and gives results of a user study involving 36 participants in which the Expandable Grid approach vastly outperformed the native Windows XP file-permissions interface on a broad range of policy-authoring tasks.

An important yet largely uncharted problem in malware defense is how to automate generation of infection signatures for detecting compromised systems, i.e., signatures that characterize the behavior of malware residing on a system. To this end, we develop AGIS, a host-based technique that detects infections by malware and automatically generates an infection signature of the malware. AGIS monitors the runtime behavior of suspicious code according to a set of security policies to detect an infection, and then identifies its characteristic behavior in terms of system or API calls. AGIS then statically analyzes the corresponding executables to extract the instructions important to the infectionpsilas mission. These instructions can be used to build a template for a static-analysis-based scanner, or a regular-expression signature for legacy scanners. AGIS also detects encrypted malware and generates a signature from its plaintext decryption loop. We implemented AGIS on Windows XP and evaluated it against real-life malware, including keyloggers, mass-mailing worms, and a well-known mutation engine. The experimental results demonstrate the effectiveness of our technique in detecting new infections and generating high-quality signatures.

We present Flicker, an infrastructure for executing security-sensitive code in complete isolation while trusting as few as 250 lines of additional code. Flicker can also provide meaningful, fine-grained attestation of the code executed (as well as its inputs and outputs) to a remote party. Flicker guarantees these properties even if the BIOS, OS and DMA-enabled devices are all malicious. Flicker leverages new commodity processors from AMD and Intel and does not require a new OS or VMM. We demonstrate a full implementation of Flicker on an AMD platform and describe our development environment for simplifying the construction of Flicker-enabled code.

We present a novel protocol for restructuring a tree- based overlay network in response to the workload of the application running over it. Through low-cost restructuring operations, our protocol incrementally adapts the tree so as to bring nodes that tend to communicate with one another closer together in the tree. It achieves this while respecting degree bounds on nodes so that, e.g., no node degenerates into a "hub" for the overlay. Moreover, it limits restructuring to those parts of the tree over which communication takes place, avoiding restructuring other parts of the tree unnecessarily. We show via experiments on PlanetLab that our protocol can significantly reduce communication latencies in workloads dominated by clusters of communicating nodes.

Access-control policy misconfigurations that cause requests to be erroneously denied can result in wasted time, user frustration and, in the context of particular applications (e.g., health care), very severe consequences. In this paper we apply association rule mining to the history of accesses to predict changes to access-control policies that are likely to be consistent with users' intentions, so that these changes can be instituted in advance of misconfigurations interfering with legitimate accesses. Instituting these changes requires consent of the appropriate administrator, of course, and so a primary contribution of our work is to automatically determine from whom to seek consent and to minimize the costs of doing so. We show using data from a deployed access-control system that our methods can reduce the number of accesses that would have incurred costly time-of-access delays by 44%, and can correctly predict 58% of the intended policy. These gains are achieved without increasing the total amount of time users spend interacting with the system.

In biology, a vaccine is a weakened strain of a virus or bacterium that is intentionally injected into the body for the purpose of stimulating antibody production. Inspired by this idea, we propose a packet vaccine mechanism that randomizes address-like strings in packet payloads to carry out fast exploit detection and signature generation. An exploit with a randomized jump address behaves like a vaccine: it will likely cause an exception in a vulnerable program’s process when attempting to hijack the control flow, and thereby expose itself. Taking that exploit as a template, our signature generator creates a set of new vaccines to probe the program in an attempt to uncover the necessary conditions for the exploit to happen. A signature is built upon these conditions to shield the underlying vulnerability from further attacks. In this way, packet vaccine detects exploits and generates signatures in a black-box fashion, that is, not relying on the knowledge of a vulnerable program’s source and binary code. Therefore, it even works on the commodity software obfuscated for the purpose of copyright protection. In addition, since our approach avoids the expense of tracking the program’s execution flow, it performs almost as fast as a normal run of the program and is capable of generating a signature of high quality within seconds or even subseconds. We present the design of the packet vaccine mechanism and an example of its application. We also describe our proof-of-concept implementation and the evaluation of our technique using real exploits.

We present Quiver, a system that coordinates service proxies placed at the "edge" of the Internet to serve distributed clients accessing a service involving mutable objects. Quiver enables these proxies to perform consistent accesses to shared objects by migrating the objects to proxies performing operations on those objects. These migrations dramatically improve performance when operations involving an object exhibit geographic locality, since migrating this object into the vicinity of proxies hosting these operations will benefit all such operations. Other workloads benefit from Quiver, dispersing the computation load across the proxies and saving the costs of sending operation parameters over the wide area when these are large. Quiver also supports optimizations for single-object reads that do not involve migrating the object. We detail the protocols for implementing object operations and for accommodating the addition, involuntary disconnection, and voluntary departure of proxies. We also evaluate Quiver through experiments on PlanetLab. Finally, we discuss the use of Quiver to build an e-commerce application and a distributed network traffic modeling service.

A quorum system is a collection of sets (quorums) of servers,where any two quorums intersect. Quorum-based protocols underly modern edge-computing architectures and throughput-scalable service implementations. In this paper we propose new algorithms for placing quorums in wide-area networks and tuning which quorums clients access, so as to optimize clients' average response time in quorum-based protocols. We examine scenarios in which the service is lightly loaded and hence network latency is the dominant delay, and in which client-induced load contributes significantly to the delay that clients observe.In each case, we evaluate our algorithms on topologies ranging from 50 to over 150 wide-area locations.

Erasure coding can reduce the space and band width overheads of redundancy in fault-tolerant data storage and delivery systems. But it introduces the fundamental difficulty of ensuring that all erasure-coded fragments correspond to the same block of data. Without such assurance, a different block may be reconstructed from different subsets of fragments. This paper develops a technique for providing this assurance without the bandwidth and computational overheads associated with current approaches. The core idea is to distribute with each fragment what we call homomorphic fingerprints. These fingerprints preserve the structure of the erasure code and allow each fragment to be independently verified as corresponding to a specific block. We demonstrate homomorphic fingerprinting functions that are secure, efficient, and compact.

This paper presents an erasure-coded Byzantine fault-tolerant block storage protocol that is nearly as efficient as protocols that tolerate only crashes. Previous Byzantine fault-tolerant block storage protocols have either relied upon replication, which is inefficient for large blocks of data when tolerating multiple faults, or a combination of additional servers, extra computation, and versioned storage. To avoid these expensive techniques, our protocol employs novel mechanisms to optimize for the common case when faults and concurrency are rare. In the common case, a write operation completes in two rounds of communication and a read completes in one round. The protocol requires a short checksum comprised of cryptographic hashes and homomorphic fingerprints. It achieves throughput within 10% of the crash-tolerant protocol for writes and reads in failure-free runs when configured to tolerate up to 6 faulty servers and any number of faulty clients.

Grey is a smartphone-based system by which a user can exercise her authority to gain access to rooms in our university building, and by which she can delegate that authority to other users. We present findings from a trial of Grey, with emphasis on how common usability principles manifest themselves in a smartphone-based security application. In particular, we demonstrate aspects of the system that gave rise to failures, misunderstandings, misperceptions, and unintended uses; network effects and new flexibility enabled by Grey; and the implications of these for user behavior. We argue that the manner in which usability principles emerged in the context of Grey can inform the design of other such applications.

We propose an architecture that allows code to execute in complete isolation from other software while trusting only a tiny software base that is orders of magnitude smaller than even minimalist virtual machine monitors. Our technique also enables more meaningful attestation than previous proposals, since only measurements of the security-sensitive portions of an application need to be included. We achieve these guarantees by leveraging hardware support provided by commodity processors from AMD and Intel that are shipping today.

This paper investigates the general problem of efficiently performing key-value search at untrusted servers without loss of user privacy. Given key-value pairs from multiple owners that are stored across untrusted servers, how can a client efficiently search these pairs such that no server, on its own, can reconstruct the key-value pairs? We propose a system, called Peekaboo, that is applicable and practical to any type of key-value search while protecting both data owner privacy and client privacy. The main idea is to separate the key-value pairs across different servers. Supported by access control and user authentication, Peekaboo allows search to be performed by only authorized clients without reducing the level of user privacy.

In biology,a vaccine is a weakened strain of a virus or bacterium that is intentionally injected into the body for the purpose of stimulating antibody production.Inspired by this idea, we propose a packet vaccine mechanism that randomizes address-like strings in packet payloads to carry out fast exploit detection, vulnerability diagnosis and signature generation. An exploit with a randomized jump address behaves like a vaccine: it will likely cause an exception in a vulnerable program's process when attempting to hijack the control flow,and thereby expose itself. Taking that exploit as a template, our signature generator creates a set of new vaccines to probe the program, in an attempt to uncover the necessary conditions for the exploit to happen. A signature is built upon these conditions to shield the underlying vulnerability from further attacks. In this way, packet vaccine detects and fllters exploits in a black-box fashion,i.e., avoiding the expense of tracking the program's execution flow. We present the design of the packet vaccine mechanism and an example of its application. We also describe our proof-of-concept implementation and the evaluation of our technique using real exploits.

Despite the proliferation of detection and containment techniques in the worm defense literature, simple threshold-based methods remain the most widely deployed and most popular approach among practitioners. This popularity arises out of the simplistic appeal, ease of use, and independence from attack-specific properties such as scanning strategies and signatures. However, such approaches have known limitations: they either fail to detect low-rate attacks or incur very high false positive rates. We propose a multi-resolution approach to enhance the power of threshold-based detection and rate-limiting techniques. Using such an approach we can not only detect fast attacks with low latency, but also discover low-rate attacks - several orders of magnitude less aggressive than today’s fast propagating attacks with low false positive rates. We also outline a multi-resolution rate limiting mechanism for throttling the number of new connections a host can make, to contain the spread of worms. Our trace analysis and simulation experiments demonstrate the benefits of a multiresolution approach for worm defense.

We present a technique to achieve anonymous multicasting in mix networks to deliver content from producers to consumers. Employing multicast allows content producers to send (and mixes to forward) information to multiple consumers without repeating work for each individual consumer. In our approach, consumers register interest for content by creating paths in the mix network to the content’s producers. When possible, these paths are merged in the network so that paths destined for the same producer share a common path suffix to the producer. When a producer sends content, the content travels this common suffix toward its consumers (in the reverse direction) and "branches" into multiple messages when necessary. We detail the design of this technique and then analyze the unlinkability of our approach against a global, passive adversary who controls both the producer and some mixes. We show that there is a subtle degradation of unlinkability that arises from multicast. We discuss techniques to tune our design to mitigate this degradation while retaining the benefits of multicast.

We present the design of a Network Forensic Alliance (NFA), to allow multiple administrative domains (ADs) to jointly locate the origin of epidemic spreading attacks. ADs in the NFA collaborate in a distributed protocol for post-mortem analysis of worm-like attacks. Information exchange between any two participating ADs is limited to traffic records that are known to both sides, maintaining the privacy of participants. Such an architecture is incentive-compatible - participants benefit by gaining better local investigative capabilities, even with partial deployment. Further, we show that by sharing local investigation results, ADs can achieve global investigative capabilities that are comparable to a centralized implementation with access to global traffic records. Our evaluation demonstrates that it is feasible for large-scale attack investigation to be incrementally deployed in an Internet-like federation.

A quorum system over a universe of logical elements is a collection of subsets (quorums) of elements, any two of which intersect. In numerous distributed algorithms, the elements of the universe reside on the nodes of a physical network and the participating nodes access the system by contacting every element in some quorum, potentially causing the added network congestion induced by these quorum accesses to play a limiting factor in the performance of the algorithm.In this paper we initiate the study of algorithms to place universe elements on the nodes of a physical network so as to minimize the network congestion that results from quorum accesses, while also ensuring that no physical node is overloaded by access requests from clients. We consider two models, one in which communication routes can be chosen arbitrarily and one in which they are fixed in advance. We show that in either model, the optimal congestion (with respect to the load constraints) cannot be approximated to any factor (unless P=NP). However, we show that at most doubling the load on nodes allows us to achieve a congestion that is close to this optimal value. We also shed some light on the extent to which element migration can reduce congestion in this context.

The Web is a complicated graph, with millions of Web sites interlinked together. In this paper, we propose to use this Web sitegraph structure to mitigate flooding attacks on a Web site, using a new Web referral architecture for privileged service ("WRAPS"). WRAPS allows a legitimate client to obtain a privilege URL through a click on a referral hypher-link, from a Web site trusted by the target Web site. Using that URL, the client can get privileged access to the target Web site in a manner that is far less vulnerable to a DDoS flooding attack. WRAPS does not require changes to Web client software and is extremely lightweight for referrer Web sites, which eases its deployment. The massive scale of the Web sitegraph could deter attempts to isolate a Web site through blocking all referrers. We present the design of WRAPS, and the implementation of a prototype system used to evaluate our proposal. Our empirical study demonstrates that WRAPS enables legitimate clients to connect to a Web site smoothly in spite of an intensive flooding attack, at the cost of small overheads on the Web site's ISP's edge routers

A quorum system is a family of sets (themselves called quorums), each pair of which intersect. In many distributed algorithms, the basic unit accessed by a client is a quorum of nodes. Such algorithms are used for applications such as mutual exclusion, data replication, and dissemination of information. However, accessing spread-out quorums causes access delays that we would like to minimize. Furthermore, every member of the quorum incurs processing load to handle quorum accesses by clients.In this paper we study the problem of placing quorums in a physical network so as to minimize the delay that clients incur by accessing quorums, and while respecting each physical node's capacity (in terms of the load of client requests it can handle). We provide approximation algorithms for this problem for two natural measures of delay (the max-delay and total-delay). All our algorithms ensure that each node's load is within a constant factor of its capacity, and minimize delay to within a constant factor of the optimal delay for all capacity-respecting solutions. We also provide better approximations for several well-known quorum systems.

A fault-scalable service can be configured to tolerate increasing numbers of faults without significant decreases in performance. The Query/Update (Q/U) protocol is a new tool that enables construction of fault-scalable Byzantine fault-tolerant services. The optimistic quorum-based nature of the Q/U protocol allows it to provide better throughput and fault-scalability than replicated state machines using agreement-based protocols. A prototype service built using the Q/U protocol outperforms the same service built using a popular replicated state machine implementation at all system sizes in experiments that permit an optimistic execution. Moreover, the performance of the Q/U protocol decreases by only 36% as the number of Byzantine faults tolerated increases from one to five, whereas the performance of the replicated state machine decreases by 83%.

We present a distributed algorithm for assembling a proof that a request satisfies an access-control policy expressed in a formal logic, in the tradition of Lampson et al. (1992). We show analytically that our distributed proof-generation algorithm succeeds in assembling a proof whenever a centralized prover utilizing remote certificate retrieval would do so. In addition, we show empirically that our algorithm outperforms centralized approaches in various measures of performance and usability notably the number of remote requests and the number of user interruptions. We show that when combined with additional optimizations including caching and automatic tactic generation, which we introduce here, our algorithm retains its advantage, while achieving practical performance. Finally, we briefly describe the utilization of these algorithms as the basis for an access-control framework being deployed for use at our institution.

Current mechanisms for authenticating communication between devices that share no prior context are inconvenient for ordinary users, without the assistance of a trusted authority. We present and analyze seeing-is-believing, a system that utilizes 2D barcodes and camera-telephones to implement a visual channel for authentication and demonstrative identification of devices. We apply this visual channel to several problems in computer security, including authenticated key exchange between devices that share no prior context, establishment of a trusted path for configuration of a TCG-compliant computing platform, and secure device configuration in the context of a smart home.

So far sensor network broadcast protocols assume a trustworthy environment. However in safety and mission-critical sensor networks this assumption may not be valid and some sensor nodes might be adversarial. In these environments, malicious sensor nodes can deprive other nodes from receiving a broadcast message. We call this attack a denial-of-message attack (DoM). In this paper we model and analyze this attack, and present countermeasures. We present SIS, a secure implicit sampling scheme that permits a broadcasting base station to probabilistically detect the failure of nodes to receive its broadcast, even if these failures result from an attacker motivated to induce these failures undetectably. SIS works by eliciting authenticated acknowledgments from a subset of nodes per broadcast, where the subset is unpredictable to the attacker and tunable so as to mitigate acknowledgment implosion on the base station. We use a game-theoretic approach to evaluate this scheme in the face of an optimal attacker that attempts to maximize the number of nodes it denies the broadcast while remaining undetected by the base station, and show that SIS significantly constrains such an attacker even in sensor networks exhibiting high intrinsic loss rates. We also discuss extensions that permit more targeted detection capabilities.

We propose a novel technique that can determine both the host responsible for originating a propagating worm attack and the set of attack flows that make up the initial stages of the attack tree via which the worm infected successive generations of victims. We argue that knowledge of both is important for combating worms: knowledge of the origin supports law enforcement, and knowledge of the causal flows that advance the attack supports diagnosis of how network defenses were breached. Our technique exploits the "wide tree" shape of a worm propagation emanating from the source by performing random "moonwalks" backward in time along paths of flows. Correlating the repeated walks reveals the initial causal flows, thereby aiding in identifying the source. Using analysis, simulation, and experiments with real world traces, we show how the technique works against both today's fast propagating worms and stealthy worms that attempt to hide their attack flows among background traffic.

Verification of write operations is a crucial component of Byzantine fault-tolerant consistency protocols for storage. Lazy verification shifts this work out of the critical path of client operations. This shift enables the system to amortize verification effort over multiple operations, to perform verification during otherwise idle time, and to have only a subset of storage-nodes perform verification. This paper introduces lazy verification and describes implementation techniques for exploiting its potential. Measurements of lazy verification in a Byzantine fault-tolerant distributed storage system show that the cost of verification can be hidden from both the client read and write operation in workloads with idle periods. Furthermore, in workloads without idle periods, lazy verification amortizes the cost of verification over many versions and so provides a factor of four higher write bandwidth when compared to performing verification during each write operation.

We present an algorithm by which nodes arranged in a tree, with each node initially knowing only its parent and children, can construct a fault-tolerant communication structure (an expander graph) among themselves in a distributed and scalable way. The tree overlayed with this logical expander is a useful structure for distributed applications that require the intrinsic "treeness" from the topology but cannot afford any obstruction in communication due to failures. At the core of our construction is a novel distributed mechanism that samples nodes uniformly at random from the tree. In the event of node joins, node departures or node failures, the expander maintains its own fault tolerance and permits the reformation of the tree. We present simulation results to quantify the convergence of our algorithm to a fault tolerant network having both good vertex connectivity and expansion properties.

Many host-based anomaly detection systems monitor a process by observing the system calls it makes, and comparing these calls to a model of behavior for the program that the process should be executing. In this paper we introduce a new model of system call behavior, called an execution graph. The execution graph is the first such model that both requires no static analysis of the program source or binary, and conforms to the control flow graph of the program. When used as the model in an anomaly detection system monitoring system calls, it offers two strong properties: (i) it accepts only system call sequences that are consistent with the control flow graph of the program; (ii) it is maximal given a set of training data, meaning that any extensions to the execution graph could permit some intrusions to go undetected. In this paper, we formalize and prove these claims. We additionally evaluate the performance of our anomaly detection technique.

No matter how well designed and engineered, a mix server offers little protection if its administrator can be convinced to log and selectively disclose correspondences between its input and output messages, either for profit or to cooperate with an investigation. In this paper we propose a technique, fragile mixing, to discourage an administrator from revealing such correspondences, assuming he is motivated to protect the unlinkability of other communications that flow through the mix (e.g., his own). Briefly, fragile mixing implements the property that any disclosure of an input-message-to-output-message correspondence discloses all such correspondences for that batch of output messages. We detail this technique in the context of a re-encryption mix, its integration with a mix network, and incentive and efficiency issues.

We present congestion puzzles (CP), a new countermeasure to bandwidth-exhaustion attacks. Like other defenses based on client puzzles, CP attempts to force attackers to invest vast resources in order to effectively perform denial-of-service attacks. Unlike previous puzzle-based approaches, however, ours is the first designed for the bandwidth-exhaustion attacks that are common at the network (IP) layer. At the core of CP is an elegant distributed puzzle mechanism that permits routers to cooperatively impose and check puzzles. We demonstrate through analysis and simulation that CP can effectively defend networks from flooding attacks without relying on the formulation of attack signatures to filter traffic. Moreover, as many such attacks are conducted by "zombie" computers that have been silently commandeered without the knowledge of their owners, the overheads that CP imposes on heavily engaged zombies can increase the likelihood that the computer's owner detects the compromise and takes action to remedy it.

This paper describes a decentralized consistency protocol for survivable storage that exploits local data versioning within each storage-node. Such versioning enables the protocol to efficiently provide linearizability and wait-freedom of read and write operations to erasure-coded data in asynchronous environments with Byzantine failures of clients and servers. By exploiting versioning storage-nodes, the protocol shifts most work to clients and allows highly optimistic operation: reads occur in a single round-trip unless clients observe concurrency or write failures. Measurements of a storage system prototype using this protocol show that it scales well with the number of failures tolerated, and its performance compares favorably with an efficient implementation of Byzantine-tolerant state machine replication.

Numerous techniques have been proposed by which an end-system, subjected to a denial-of-service flood, filters the offending traffic. In this paper, we provide an empirical analysis of several such proposals, using traffic recorded at the border of a large network and including real DoS traffic. We focus our analysis on four filtering techniques, two based on the addresses from which the victim server typically receives traffic (static clustering and network-aware clustering), and two based on coarse indications of the path each packet traverses (hop-count filtering and path identifiers). Our analysis reveals challenges facing the proposed techniques in practice, and the implications of these issues for effective filtering. In addition, we compare techniques on equal footing, by evaluating the performance of one scheme under assumptions made by another. We conclude with an interpretation of the results and suggestions for further analysis.

Modern distributed, object-based systems support nested method invocations, whereby one object can invoke methods on another. In this paper we present a framework that supports nested method invocations among Byzantine fault-tolerant, replicated objects that are accessed via quorum systems. A challenge in this context is that client object replicas can induce unwanted method invocations on server object replicas, due either to redundant invocations by client replicas or Byzantine failures within the client replicas. At the core of our framework are a new quorum-based authorization technique and a novel method invocation protocol that ensure the linearizability and failure atomicity of nested method invocations despite Byzantine client and server replica failures. We detail the implementation of these techniques in a system called Fleet, and give preliminary performance results for them.

We present the design and implementation of a compiler that automatically generates protocols that perform two-party computations. The input to our protocol is the specification of a computation with secret inputs (e.g., a signature algorithm) expressed using operations in the field Zq of integers modulo a prime q and in the multiplicative subgroup of order q in Z*p for q|p-1 with generator g. The output of our compiler is an implementation of each party in a two-party protocol to perform the same computation securely, i.e., so that both parties can together compute the function but neither can alone. The protocols generated by our compiler are provably secure, in that their strength can be reduced to that of the original cryptographic computation via simulation arguments. Our compiler can be applied to various cryptographic primitives (e.g., signature schemes, encryption schemes, oblivious transfer protocols) and other protocols that employ a trusted party (e.g., key retrieval, key distribution).

Although client puzzles represent a promising approach to defend against certain classes of denial-of-service attacks, several questions stand in the way of their deployment in practice: e.g., how to set the puzzle difficulty in the presence of an adversary with unknown computing power, and how to integrate the approach with existing mechanisms. In this paper, we attempt to address these questions with a new puzzle mechanism called the puzzle auction. Our mechanism enables each client to "bid" for resources by tuning the difficulty of the puzzles it solves, and to adapt its bidding strategy in response to apparent attacks. We analyze the effectiveness of our auction mechanism and further demonstrate it using an implementation within the TCP protocol stack of the Linux kernel. Our implementation has several appealing properties. It effectively defends against SYN flooding attacks, is fully compatible with TCP, and even provides a degree of interoperability with clients with unmodified kernels: Even without a puzzle-solving kernel, a client still can connect to a puzzle auction server under attack (albeit less effectively than those with puzzle-solving kernels, and at the cost of additional server expense).

A capture protection server protects a cryptographic key on a device that may be captured by authenticating the user of the device (e.g., by password) before permitting the key to be used. Delegation from one capture protection server to another enables the new server to perform this capture protection function for the device. Delegation, however, opens the system to new vulnerabilities, including difficulties in limiting online password-guessing attacks and in disabling a device that has been stolen by an attacker who knows the password. Here we propose a lightweight protocol for coordinating capture protection servers that eliminates these vulnerabilities. We also report on the implementation of our protocol in a JCA-compliant cryptographic service provider, and ramifications of the JCA interfaces for our approach.

This paper presents the design, implementation and evaluation of Mingle, a secure distributed search system. Each participating host runs a Mingle server, which maintains an inverted index of the local file system. Users initiate peer-to-peer keyword searches by typing keywords to lightweight Mingle clients. Central to Mingle are its access control mechanisms and its insistence on user convenience. For access control, we introduce the idea of access-right mapping, which provides a convenient way for file owners to specify access permissions. Access control is supported through a single sign-on mechanism that allows users to conveniently establish their identity to Mingle servers, such that subsequent authentication occurs automatically, with minimal manual involvement. Preliminary performance evaluation suggests that Mingle is both feasible and scalable.

Abstract Developing concurrent applications is not a trivial task. As programs grow larger and become more complex, advanced concurrency control mechanisms are needed to ensure that application consistency is not compromised. Managing mutual exclusion on a per‐object basis is not sufficient to guarantee isolation of sets of semantically‐related actions. In this paper, we consider ‘atomic blocks’, a simple and lightweight concurrency control paradigm that enables arbitrary blocks of code to access multiple shared objects in isolation. We evaluate various strategies for implementing atomic blocks in Java, in such a way that concurrency control is transparent to the programmer, isolation is preserved, and concurrency is maximized. We discuss these concurrency control strategies and evaluate them in terms of complexity and performance. Copyright © 2002 John Wiley & Sons, Ltd.

A device that performs private key operations (signatures or decryptions), and whose private key operations are protected by a password, can be immunized against offline dictionary attacks in case of capture by forcing the device to confirm a password guess with a designated remote server in order to perform a private key operation. Recent proposals for achieving this allow untrusted servers and require no server initialization per device. In this paper we extend these proposals to enable dynamic delegation from one server to another; i.e., the device can subsequently use the second server to secure its private key operations. One application is to allow a user who is traveling to a foreign country to temporarily delegate to a server local to that country the ability to confirm password guesses and aid the user's device in performing private key operations, or in the limit, to temporarily delegate this ability to a token in the user's possession. Another application is proactive security for the device's private key, i.e., proactive updates to the device and servers to eliminate any threat of offline password guessing attacks due to previously compromised servers.

Presents a simple and efficient protocol for mutual exclusion in synchronous message-passing distributed systems subject to failures. Our protocol borrows design principles from prior work in backoff protocols for multiple access channels such as the Ethernet. Our protocol is adaptive in that the expected amortized system response time - informally, the average time a process waits before entering the critical section - is a function only of the number of clients currently contending and is independent of the maximum number of processes that might contend. In particular, in the contention-free case, a process can enter the critical section after only one round-trip message delay. We use this protocol to derive a protocol for ordering operations on a replicated object in an asynchronous distributed system subject to failures. This protocol is always safe, is probabilistically live during periods of stability and is suitable for deployment in practical systems.

Motivated by the application of private statistical analysis of large databases, we consider the problem of selective private function evaluation (SPFE). In this problem, a client inter-acts with one or more servers holding copies of a database z = zt,...,z, in order to compute f(z~t,...,z~,,,) , for some function f and indices i = it,...,i, ~ chosen by the client. Ideally, the client must learn nothing more about the database than f(zit,..., zi,,~), and the servers should learn nothing. Generic solutions for this problem, based on standard techniques for secure function evaluation, incur communi-cation complexity that is at least linear in n, making them prohibitive for large databases even when f is relatively sim-ple and m is small. We present various approaches for con-structing sublinear-communication $PFE protocols, both for the general problem and for special cases of interest. Our so-lutions not only offer sublinear communication complexity, but are also practical in many scenarios. 1.

We present a simple technique by which a device that performs private key operations (signatures or decryptions) in networked applications, and whose local private key is activated with a password or PIN, can be immunized to offline dictionary attacks in case the device is captured. Our techniques do not assume tamper resistance of the device, but rather exploit the networked nature of the device, in that the device's private key operations are performed using a simple interaction with a remote server. This server however, is untrusted-its compromise does not reduce the security of the device's private key unless the device is also captured and need not have a prior relationship with the device. We further extend this approach with support for key disabling, by which the rightful owner of a stolen device can disable the device's private key even if the attacker already knows the user's password.

We propose a technique to reliably generate a cryptographic key from a user's voice while speaking a password. The key resists cryptanalysis even against an attacker who captures all system information related to generating or verifying the cryptographic key. Moreover, the technique is sufficiently robust to enable the user to reliably regenerate the key by uttering her password again. We describe an empirical evaluation of this technique using 250 utterances recorded from 50 users.

We present a protocol for diffusion of updates among replicas in a distributed system where up to b replicas may suffer Byzantine failures. Our algorithm ensures that no correct replica accepts spurious updates introduced by faulty replicas, by requiring that a replica accepts an update only after receiving it from at least b+1 distinct replicas (or directly from the update source). Our algorithm diffuses updates more efficiently than previous such algorithms and, by exploiting additional information available in some practical settings, sometimes more efficiently than known lower bounds predict.

Public key management has received considerable attention from both the research and commercial communities as a useful primitive for secure electronic commerce and secure communication. While the mechanics of certifying and revoking public keys and escrowing and recovering private keys have been widely explored, less attention has been paid to access control frameworks for regulating access to stored keys by different parties. In this article we propose such a framework for a key management service that supports public key registration, lookup, and revocation, and private key escrow, protected use (e.g., to decrypt selected messages), and recovery. We propose an access control model using a policy based on principal, ownership, and authority relationships on keys. The model allows owners to grant to others (and revoke) privileges to execute various actions on their keys. The simple authorization language is very expressive, enabling the specification of authorizations for composite subjects that can be fully specified (ground) or partially specified, thus making the authorizations applicable to all subjects satisfying some conditions. We illustrate how the access control policy and the authorizations can easily be expressed through a simple and restricted, hence efficiently computable, form of logic language.

In this paper, we explore techniques to detect Byzantine server failures in asynchronous replicated data services. Our goal is to detect arbitrary failures of data servers in a system where each client accesses the replicated data at only a subset (quorum) of servers in each operation. In such a system, some correct servers can be out-of-date after a write and can therefore, return values other than the most up-to-date value in response to a client's read request, thus complicating the task of determining the number of faulty servers in the system at any point in time. We initiate the study of detecting server failures in this context, and propose two statistical approaches for estimating the risk posed by faulty servers based on responses to read requests.

In this paper, we investigate the k-set consensus problem in asynchronous distributed systems. In this problem, each participating process begins the protocol with an input value and by the end of the protocol must decide on one value so that at most k total values are decided by all correct processes. We extend previous work by exploring several variations of the problem definition and model, including for the first time investigation of Byzantine failures. We show that the precise definition of the validity requirement, which characterizes what decision values are allowed as a function of the input values and whether failures occur, is crucial to the solvability of the problem. For example, we show that allowing default decisions in case of failures makes the problem solvable for most values of k despite a minority of failures, even in face of the most severe type of failures (Byzantine). We introduce six validity conditions for this problem (all considered in various contexts in the literature), and demarcate the line between possible and impossible for each case. In many cases, this line is different from the one of the originally studied k-set consensus problem.

Several organizations are setting up Public Key Infrastructures, examples are:the Corporation for Research and Educational Networking (CREN),• the Federal Government plans to fund 7 Public Key Infrastructure Models pilot programs at different federal agencies.However, experts have quite different viewpoints on how to set up such Public Key Infrastructure (PKI).Indeed, X500 and X509 are hierarchically organized (i.e.vertical), but PGP (see also Rivest-Lampson) is horizontally organized.Variants of PGP (see Reiter-Stubblebine (CCCS, ACM) and Burmester-Desmedt-Kabatianski (DIMACS)) require a minimum connectivity, i.e., a minimum number of disjoint paths in order to deal with hackers breaking into certifying entities (authorities).Moreover, Ellison-Schneier have questioned the need for a Public Key Infrastructure (PKI).Before one builds such an expensive infrastructure, experts should debate what method to use and whether a PKI is needed.While a hierarchical PKI may become the next target of computer hackers, a multiple-connected one seems much more expensive to build.

Byzantine quorum systems enhance the availability and efficiency of fault-tolerant replicated services when servers may suffer Byzantine failures. An important limitation of Byzantine quorum systems is their dependence on a static threshold limit on the number of server faults. The correctness of the system is only guaranteed if the actual number of faults is lower than the the threshold at all times. However, a threshold chosen for the worst case wastes expensive replication in the common situation where the number of faults averages well below the worst case. In this paper, we present protocols for dynamically raising and lowering the resilience threshold of a quorum-based Byzantine fault-tolerant data service in response to current information on the number of server failures. Using such protocols, a system can operate in an efficient low-threshold mode with relatively small quorums in the absence of faults, increasing and decreasing the quorum size (and thus the tolerance) as faults appear and are dealt with, respectively.

We present an architecture for global customization of web content, by w h i c h a w eb site can customize content for each visitor based on the activities undertaken by the same user on other, unrelated sites.Our architecture distinguishes itself in the privacy mechanisms it provides: each u s e r c o n trols what information a merchant can learn about her activities at other merchants, and each merchant controls to what other merchants the information it contributes is revealed.To a c hieve t h i s w e i n troduce novel data protection mechanisms for merchants and users.We further describe aspects of a prototype implementation of our architecture.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy

Replicated services accessed via quorums enable each access to be performed at only a subset (quorum) of the servers and achieve consistency across accesses by requiring any two quorums to intersect. Recently, b-masking quorum systems, whose intersections contain at least 2b+1 servers, have been proposed to construct replicated services tolerant of b-arbitrary (Byzantine) server failures. In this paper we consider a hybrid fault model allowing benign failures in addition to the Byzantine ones. We present four novel constructions for b-masking quorum systems in this model, each of which has optimal load (the probability of access of the busiest server) or optimal availability (probability of some quorum surviving failures). To show optimality we also prove lower bounds on the load and availability of any b-masking quorum system in this model.

Coordination among processes in a distributed system can be rendered very complex in a large-scale system where messages may be delayed or lost and when processes may participate only transiently or behave arbitrarily, e.g. after suffering a security breach. In this paper, we propose a scalable architecture to support coordination in such extreme conditions. Our architecture consists of a collection of persistent data servers that implement simple shared data abstractions for clients, without trusting the clients or even the servers themselves. We show that, by interacting with these untrusted servers, clients can solve distributed consensus, a powerful and fundamental coordination primitive. Our architecture is very practical, and we describe the implementation of its main components in a system called Fleet.

Mobile code presents a number of threats to machines that execute it. We introduce an approach for protecting machines and the resources they hold from mobile code and describe a system based on our approach for protecting host machines from Java 1.1 applets. In our approach, each Java applet downloaded to the protected domain is rerouted to a dedicated machine (or set of machines), the playground, at which it is executed. Prior to execution, the applet is transformed to use the downloading user's Web browser as a graphics terminal for its input and output, and so the user has the illusion that the applet is running on his own machine. In reality, however, mobile code runs only in the sanitized environment of the playground, where user files cannot be mounted and from which only limited network connections are accepted by machines in the protected domain. Our playground thus provides a second level of defense against mobile code that circumvents language-based defenses. This paper presents the design and implementation of a playground for Java 1.1 applets and discusses extensions of it for other forms of mobile code, including Java 1.2.

We present a novel approach to improving the security of passwords. In our approach, the legitimate user's typing patterns (e.g., durations of keystrokes, and latencies between keystrokes) are combined with the user's password to generate a hardened password that is convincingly more secure than conventional passwords against both online and offline attackers. In addition, our scheme automatically adapts to gradual changes in a user's typing patterns while maintaining the same hardened password across multiple logins, for use in file encryption or other applications requiring a longterm secret key. Using empirical data and a prototype implementation of our scheme, we give evidence that our approach is viable in practice, in terms of ease of use, improved security, and performance

In this paper we investigate the k-set consensus problem in asynchronous, message-passing distributed systems.In this problem, each participating process begins the protocol with an input value and by the end of the protocol must decide on one value so that at most k different values are decided by all correct processes.We extend previous work by exploring several variations of the problem definition and model, including for the first time investigation of Byzantine failures.We show that the precise definition of the validity requirement, which characterizes what decision values are allowed as a function of the input values and whether failures occur, is crucial to the solvability of the problem.For example, we show that allowing default decisions in case of failures makes the problem solvable for most values of k despite a minority of failures, even for the most severe type of failures (Byiantine).We introduce six validity conditions for this problem (all considered in various contexts in the literature), and demarcate the line between possible and impossible for each case.In many cases this line is different from the one of the originally studied k-set consensus problem.

We study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (Byzantine) failures. We assume that strictly fewer than t replicas fail, and that each update is initially received by at least t correct replicas. The goal is to diffuse each update to all correct replicas while ensuring that correct replicas accept no updates generated spuriously by faulty replicas. To achieve reliable diffusion, each correct replica accepts an update only after receiving it from at least t others. We provide the first analysis of epidemic-style protocols for such environments. This analysis is fundamentally different from known analyses for the benign case due to our treatment of fully Byzantine failure-which, among other things, precludes the use of digital signatures for authenticating forwarded updates. We propose two epidemic-style diffusion algorithms and two measures that characterize the efficiency of diffusion algorithms in general. We characterize both of our algorithms according to these measures, and also prove lower bounds with regards to these measures that show that our algorithms are close to optimal.

Authentication using a path of trusted intermediaries, each able to authenicate the next in the path, is a well-known technique for authenicating entities in a large-scale system. Recent work has extended this technique to include multiple paths in an effort to bolster authentication, but the success of this approach may be unclear in the face of intersecting paths, ambiguities in the meaning of certificates, and interdependencies in the use of different keys. Thus, several authors have proposed metrics to evaluate the confidence afforded by a set of paths. In this paper we develop a set of guiding principles for the design of such metrics. We motivate our principles by showing how previous approaches failed with respect to these principles and what the consequences to authentication might be. We then propose a new metric that appears to meet our principles, and so to be a satisfactory metric of authenticaiton.

In this paper we present probabilistic masking quorum systems, a technique for replicating data that can mask, with high probability, the arbitrary (Byzantine) failure of data servers from clients. This technique generalizes previous work on probabilistic quorum systems to mask Byzantine server failures in their full generality, and improves over previous masking quorum systems by offering better data availability and access efficiency. We define probabilistic masking quorum systems, demonstrate a novel access protocol for implementing replicated data with them, and prove general and tight lower bounds on the performance that they can achieve. We also present a probabilistic masking quorum construction that outperforms strict masking constructions in measures of both availability and efficiency.

Mobile code presents a number of threats to machines that execute it. We introduce an approach for protecting machines and the resources they hold from mobile code, and describe a system based on our approach for protecting host machines from Java 1.1 applets. In our approach, each Java applet downloaded to the protected domain is rerouted to a dedicated machine (or set of machines), the playground, at which it is executed. Prior to execution, the applet is transformed to use the downloading user's Web browser as a graphics terminal for its input and output, and so the user has the illusion that the applet is running on her own machine. In reality, however, mobile code runs only in the sanitized environment of the playground, where user files cannot be mounted and from which only limited network connections are accepted by machines in the protected domain. Our playground thus provides a second level of defense against mobile code that circumvents language based defenses.

Phalanx is a software system for building a persistent, survivable data repository that supports shared data abstractions (e.g., variables, mutual exclusion) for clients. Phalanx implements data abstraction that ensures useful properties without trusting the servers supporting these abstractions or the clients accessing them, i.e., Phalanx can survive even the arbitrarily malicious corruption of clients and (some number of) servers. At the core of the system are survivable replication techniques that enable efficient scaling to hundreds of Phalanx servers. In this paper we describe the implementation of some of the data abstractions provided by Phalanx, discuss their ability to scale to large systems, and describe an example application.

Reaching consensus among multiple processes in a distributed system is fundamental to coordinating distributed actions. We present a new approach to building survivable consensus objects in a system consisting of a (possibly large) collection of persistent object servers and a transient population of clients. Our consensus object implementation requires minimal support from servers, but at the same time enables clients to reach coordinated decisions despite the arbitrary (Byzantine) failure of any number of clients and up to a threshold number of servers.

Authentication using a path of trusted intermediaries, each able to authenticate the next in the path, is a well-known technique for authenticating channels in a large distributed system. In this paper, we explore the use of multiple paths to redundantly authenticate a channel and focus on two notions of path independence-disjoint paths and connective paths-that seem to increase assurance in the authentication. We give evidence that there are no efficient algorithms for locating maximum sets of paths with these independence properties and propose several approximation algorithms for these problems. We also describe a service we have deployed, called PathServer, that makes use of our algorithms to find such sets of paths to support authentication in PGP applications.

In this paper we introduce a system called Crowds for protecting users' anonymity on the world-wide-web. Crowds, named for the notion of “blending into a crowd,” operates by grouping users into a large and geographically diverse group (crowd) that collectively issues requests on behalf of its members. Web servers are unable to learn the true source of a request because it is equally likely to have originated from any member of the crowd, and even collaborating crowd members cannot distinguish the originator of a request from a member who is merely forwarding the request on behalf of another. We describe the design, implementation, security, performance, and scalability of our system. Our security analysis introduces degrees of anonymity as an important tool for describing and proving anonymity properties.

We present new protocols for two parties to exchange documents with fairness, i.e., such that no party can gain an advantage by quitting prematurely or otherwise misbehaving.We use a third party that is L'semi-trusted", in the sense that it may misbehave on its own but will not conspire with either of the main parties.In our solutions, disruption by any one of the three parties will not allow the disrupter gain any useful new information about the documents.Our solutions are efficient and can be based on any of several cryptographic assumptions (e.g., factoring, discrete log, graph isomorpbism).We also discuss the application of our techniques to electronic commerce protocols to achieve fair payment.

Authenticating the source of a message in a large distributed system can be difficult due to the lack of a single authority that can tell for whom a channel speaks.This has led many to propose the use of a path of authorities, each able to authenticate the next in the path, such that the first in the path can be authenticated by the message recipient and the last can authenticate the message source.In this paper we suggest the use of multiple paths to provide redundant confirmation of the message source, and focus on two related notions of path independence that seem to bolster authentication.We formalize the problems of locating maximum sets of paths with these independence properties in a graph-theoretic framework, give evidence that they are not polynomial-time solvable, and propose approximation algorithms for these problems.We also introduce PathServer for PGP, a service for fmding sets of such paths to support authentication in PGP applications.

Distributed coordination is difficult, especially when the system may suffer intrusions that corrupt some component processes. We introduce the abstraction of a failure detector that a process can use to (imperfectly) detect the corruption (Byzantine failure) of another process. In general, our failure detectors can be unreliable, both by reporting a correct process to be faulty or by reporting a faulty process to be correct. However, we show that if these detectors satisfy certain plausible properties, then the well known distributed consensus problem can be solved. We also present a randomized protocol using failure detectors that solves the consensus problem if either the requisite properties of failure detectors hold or if certain highly probable events eventually occur. This work can be viewed as a generalization of benign failure detectors popular in the distributed computing literature.

Replicated services accessed via quorurmcnable each access to be performed at only a subset (quorum) of the servers, and achieve consistency across accesses by requiring any two quorums to intersect.Recently, bmasking quorum systems, whose intersections contain at least 2b+l servers, have been proposed to construct replicated services tolerant of barbitrary (B ymntine) server failures.In this paper we consider a hybrid fault model allowing benign failures in addition to the Byzantine ones.We present four novel constructions for bmasking quorum systems in this model, each of which has optimal load (the probability of access of the busiest server) or optimal availability (probabllit y of some quorum surviving failures).To show optimalit y we also prove lower bounds on the load and availabilityy of any bmasking quorum system in this model.I&mission to make digilnlflmrd copies of all or piIIIof(hi~nu}icri:ll fix personal or classroom use is grw!cd without ~cc prm idcd III;IIIIICcopies are not mwlc or distrihukd I'orpmlil or wmncrciid :IdvmIIogc.theCXWrlght notice, (he title of the pohlic:it ion mMlils d:IIcnppcw.xnd WIicc is given that urpyrighl is hy pwmission OI"IIW ACM, INC. '1"0 copy otherwise.to republish, In post on wrws or to rcdistrihu[c 10 lists.ruplircs specilic pem~ission andlor 13c 1997 I'OD(' 97 .Srlnta 13m+ora [ '.4 1 I*Y.4

Services replicated using a quorum system allow operations to be performed at only a subset (quorum) of the servers, and ensure consistency among operations by requiring that any two quorums intersect. In this paper we explore the consequences of requiring this intersection property to hold only with very high probability. We show that doing so can offer dramatic improvements in the performance and availability of the service, both for services tolerant of benign server failures and services tolerant of arbitrary (Byzantine) ones. We also prove a lower bound on the performance that can be achieved with this technique. 1 Introduction Quorums are tools for increasing the availability and efficiency of replicated services. A quorum system is a set of subsets of servers, every pair of which intersect. Intuitively, the intersection property guarantees that if a "write" operation is performed at one quorum, and later a "read" operation at another quorum, then there is some server that obse...

Authentication using a path of trusted intermediaries, each able to authenticate the next one in the path, is a well-known technique for authenticating entities in a large-scale system. Recent work has extended this technique to include multiple paths in an effort to bolster authentication, but the success of this approach may be unclear in the face of intersecting paths, ambiguities in the meaning of certificates, and interdependencies in the use of different keys. Several authors have thus proposed metrics to evaluate the confidence afforded by a set of paths. In this paper, we develop a set of guiding principles for the design of such metrics. We motivate our principles by showing how previous approaches fail with respect to them and what the consequences to authentication might be. We then propose a direction for constructing metrics that come closer to meeting our principles and thus, we believe, to being satisfactory metrics for authentication.

Quorum systems are well-known tools for ensuring the consistency and availability of replicated data despite the benign failure of data repositories. In this paper we consider the arbitrary (Byzantine) failure of data repositories and present the first study of quorum system requirements and constructions that ensure data availability and consistency despite these failures. We also consider the load associated with our quorum systems, i.e., the minimal access probability of the busiest server. For services subject to arbitrary failures, we demonstrate quorum systems over n servers with a load of O( 1 p n ), thus meeting the lower bound on load for benignly faulttolerant quorum systems. We explore several variations of our quorum systems and extend our constructions to cope with arbitrary client failures. 1 Introduction A well known way to enhance the availability and efficiency of replicated data is by using quorums . A quorum system for a universe of data servers is a collection o...

A (secure) reliable multicast protocol enables a process to multicast a message to a group of processes in a way that ensures that all honest destination-group members receive the same message, even if some group members and the multicast initiator a

In this paper we i.ntroduce R, a distributed public key management service for open networks. f’l offers interfaces by which clients can register, retrieve, and revoke public keys, and escrow, use (to decrypt messages), and recover private keys, all of which can be subjected to access control policy. R is built using multiple servers in a way that ensures its correct operation despite the malicious corruption of fewer than one-third of its component servers. We describe the design of R, the protocols underlying its operation, performance in our present implementation, and an experimental application of the service.

A reliable multicast protocol enables a process to multicast a message to a group of processes in a way that ensures that all honest destination-group members receive the same message, even if some group members and the multicast initiator are maliciously faulty. Reliable multicast has been shown to be useful for building multiparty cryptographic protocols and secure distributed services. We present a high-throughput reliable multicast protocol that tolerates the malicious behavior of up to fewer than one-third of the group members. Our protocol achieves high-throughput using a novel technique for chaining multicasts, whereby the cost of ensuring agreement on each multicast message is amortized over many multicasts. This is coupled with a novel flow-control mechanism that yields low multicast latency.

In this paper we introduce Ω, a distributed public key management service for open networks. Ω offers interfaces by which clients can register, retrieve, and revoke public keys, and escrow, use (to decrypt messages), and recover private keys, all of which can be subjected to access control policy. Ω is built using multiple servers in a way that ensures its correct operation despite the malicious corruption of fewer than one-third of its component servers. We describe the design of Ω, the protocols underlying its operation, performance in our present implementation, and an experimental application of the service.

We present the design and implementation of a distributed service for performing sealed bid auctions. This service provides an interface by which clients, or "bidders", can issue secret bids to the service for an advertised auction. Once the bidding period has ended, the auction service opens the bids, determines the winning bid, and provides the winning bidder with a ticket for claiming the item bid upon. Using novel cryptographic techniques, the service is constructed to provide strong protection for both the auction house and correct bidders, despite the malicious behavior of any number of bidders and fewer than one third of the servers comprising the auction service. Specifically, it is guaranteed that: bids of correct bidders are not revealed until after the bidding period has ended; the auction house collects payment for the winning bid; losing bidders forfeit no money; and only the winning bidder can collect the item bid upon. We also discuss techniques to enable anonymous bidding.

A group membership protocol enables processes in a distributed system to agree on a group of processes that are currently operational. Membership protocols are a core component of many distributed systems and have proved to be fundamental for maintaining availability and consistency in distributed applications. We present a membership protocol for asynchronous distributed systems that tolerates the malicious corruption of group members. Our protocol ensures that correct members control and consistently observe changes to the group membership, provided that in each instance of the group membership, fewer than one-third of the members are corrupted or fail benignly. The protocol has many potential applications in secure systems and, in particular, is a central component of a toolkit for constructing secure and fault-tolerant distributed services that we have implemented.

We present the design and implementation of a distributed service for performing sealed-bid auctions. This service provides an interface by which clients, or "bidders", can issue secret bids to the service for an advertised auction. Once the bidding period has ended, the auction service opens the bids, determines the winning bid, and provides the winning bidder with a ticket for claiming the item bid upon. Using novel cryptographic techniques, the service is constructed to provide strong protection for both the auction house and correct bidders, despite the malicious behavior of any number of bidders and even a constant fraction of the servers comprising the auction service. Specifically, it is guaranteed that (i) bids of correct bidders are not revealed until after the bidding period has ended, (ii) the auction house collects payment for the winning bid, (iii) losing bidders forfeit no money, and (iv) only the winning bidder can collect the item bid upon. We also discuss techniques to enable anonymous bidding.>

In a distributed system, it is often important to detect the causal relationships between events, where event e1 is causally before event e2 if e1 happened before e2 and could possibly have affected the occurrence of e2. In this paper we argue that it can be essential to security that a process determine, in the face of malicious attack, how two events are causally related. We formulate attacks on causality detection in terms of causal denial and forgery, formalize possible security goals with respect to causality, and present simple algorithms to attain these goals in some situations.

Reliable and atomic group multicast have been proposed as fundamental communication paradigms to support secure distributed computing in systems in which processes may behave maliciously. These protocols enable messages to be multicast to a group of processes, while ensuring that all honest group members deliver the same messages and, in the case of atomic multicast, deliver these messages in the same order. We present new reliable and atomic group multicast protocols for asynchronous distributed systems. We also describe their implementation as part of Rampart, a toolkit for building high-integrity distributed services, i.e., services that remain correct and available despite the corruption of some component servers by an attacker. To our knowledge, Rampart is the first system to demonstrate reliable and atomic group multicast in asynchronous systems subject to process corruptions.

A group membership protocol enables processes in a distributed system to agree on a group of processes that are currently operational. Membership protocol are a core component of many distributed systems and have proved to be fundamental for maintaining availability and consistency in distributed applications. We present a membership protocol for asynchronous distributed systems that tolerates the malicious corruption of group members. Our protocol ensures that correct members control and consistently observe changes to the group membership, provided that in each instance of the group membership, fewer than one-third of the members are corrupted or fail benignly. The protocol has many potential applications in secure systems and, in particular, is a central component of a toolkit for constructing high-integrity distributed services that we are presently implementing.>

Process groups are a common abstraction for fault-tolerant computing in distributed systems. We present a security architecture that extends the process group into a security abstraction. Integral parts of this architecture are services that securely and fault tolerantly support cryptographic key distribution. Using replication only when necessary, and introducing novel replication techniques when it was necessary, we have constructed these services both to be easily defensible against attack and to permit key distribution despite the transient unavailability of a substantial number of servers. We detail the design and implementation of these services and the secure process group abstraction they support. We also give preliminary performance figures for some common group operations.

We present a method for constructing replicated services that retain their availability and integrity despite several servers and clients being corrupted by an intruder, in addition to others failing benignly. We also address the issue of maintaining a causal order among client requests. We illustrate a security breach resulting from an intruder's ability to effect a violation of causality in the sequence of requests processed by the service and propose an approach to counter this attack. An important and novel feature of our techniques is that the client need not be able to identify or authenticate even a single server. Instead, the client is required to possess only a single public key for the service. We demonstrate the performance of our techniques with a service we have implemented using one of our protocols.

In a distributed system, it is often important to detect the causal relationships between events, where event e/sub 1/ is causally before event e/sub 2/ if e/sub 1/ happened before e/sub 2/ and could possibly have affected the occurrence of e/sub 2/. The authors argue that detecting causal relationships among events can be important for security, in the sense that it may be essential to the correct implementation of a security policy that a process be able to determine if two events are causally related, and if so, how. They formulate attacks on causality in terms of causal denial and forgery, formalize possible security goals with respect to causality, and present simple algorithms to attain these goals in some situations.>

A distributed security architecture is proposed for incorporation into group oriented distributed systems, and in particular, into the Isis distributed programming toolkit. The primary goal of the architecture is to make common group-oriented abstractions robust in hostile settings in order to facilitate the construction of high-performance distributed applications that can tolerate both component failure and malicious attacks. These abstractions include process groups and causal group multicast. A delegation and access control scheme is also proposed for use in group-oriented systems. The focus is on the security architecture; particular cryptosystems and key exchange protocols are not emphasized.>