Publications | Andreas Haeberlen

Topics

Differential privacy
Fault tolerance
Provenance
Accountability
Measurement
Peer-to-Peer
Microkernels
Other

Sort by

Type
Date
Topic

Conference papersTopic Date Type

RoboRebound: Multi-Robot System Defense with Bounded-Time Interaction. Neeraj Gandhi, Yifan Cai, Andreas Haeberlen, and Linh Thi Xuan Phan. 20th European Conference on Computer Systems (EuroSys '25), Mar 2024.

× @inproceedings{gandhi-2025-roborebound,
  author = {Neeraj Gandhi and Yifan Cai and Andreas Haeberlen and Linh Thi Xuan Phan},
  title = {{RoboRebound}: {M}ulti-{R}obot {S}ystem {D}efense with {B}ounded-{T}ime {I}nteraction},
  booktitle = {20th European Conference on Computer Systems (EuroSys '25)},
  month = mar,
  year = 2024
}

×
Byzantine Fault Tolerance (BFT) is a classic technique for defending distributed systems against a wide range of faults and attacks. However, existing solutions are designed for systems where nodes can interact only by exchanging messages. They are not directly applicable to systems where nodes have sensors and actuators and can also interact in the physical world — perhaps by blocking each other's path or by crashing into each other.
In this paper, we take a first stab at extending BFT to this larger class of systems. We focus on multi-robot systems (MRS), an emerging technology that is increasingly being deployed for applications such as target tracking, warehouse logistics, and exploration. An MRS can consist of dozens of interacting robots and is thus a bona-fide distributed system. The classic masking guarantee is not practical in a MRS, but we propose a variant called bounded-time interaction that can be implemented, and we present an algorithm that achieves it, in combination with a few small hardware tweaks. We built a simulator and prototyped wheeled robots to show that our algorithm is effective, and that it has a reasonable overhead.

BibTeX Abstract
Metaverse as a Service: Megascale Social 3D on the Cloud. Andreas Haeberlen, Linh Thi Xuan Phan, and Morgan McGuire. 14th ACM Symposium on Cloud Computing (SoCC '23), Oct 2023.

× @inproceedings{haeberlen-2023-metaverse,
  author = {Andreas Haeberlen and Linh Thi Xuan Phan and Morgan McGuire},
  title = {Metaverse as a Service: Megascale Social 3D on the Cloud},
  booktitle = {14th ACM Symposium on Cloud Computing (SoCC '23)},
  month = oct,
  year = 2023
}

×
We present a vision for the future of an emerging category of cloud service: the metaverse of 3D virtual worlds. Today, hundreds of millions of users are active daily in such worlds, but they are partitioned into small groups of at most a few hundred players. Each group joins a different virtual world instance, and players can only interact in 3D with others players in the same group during that session. Current platforms are designed in ways that simply cannot scale much further, and solutions from other cloud services do not generalize to the more interactive, bidirectional, and latency-sensitive interactive 3D domain. We outline some of the technical challenges that currently stand in the way of a metaverse without inherent technical limitations on the number of users in a shared experience. We argue that, although these obviously touch on many other areas of Computer Science such as computer graphics and numerical simulation, the core challenges lie squarely within the systems domain.

PDF BibTeX Abstract Slides
Arboretum: A Planner for Massive-Scale Federated Analytics with Differential Privacy. Elizabeth Margolin, Karan Newatia, Edo Roth, Tao Luo, and Andreas Haeberlen. 29th ACM Symposium on Operating Systems Principles (SOSP '23), Oct 2023.

× @inproceedings{margolin-2023-arboretum,
  author = {Elizabeth Margolin and Karan Newatia and Edo Roth and Tao Luo and Andreas Haeberlen},
  title = {Arboretum: A Planner for Massive-Scale Federated Analytics with Differential Privacy},
  booktitle = {29th ACM Symposium on Operating Systems Principles (SOSP '23)},
  month = oct,
  year = 2023
}

×
Federated analytics is a way to answer queries over sensitive data that is spread across multiple parties, without sharing the data or collecting it in a single place. Prior work has developed solutions that can scale to large deployments with millions of devices but, due to the distributed nature of federated analytics, these solutions can support only a limited class of queries - typically various forms of numerical queries, which can be answered with lightweight cryptographic primitives. Supporting richer queries, such as categorical queries, requires heavier cryptography, whose cost can quickly exceed even the resources of a powerful data center.
In this paper, we present Arboretum, a new federated analytics system that can efficiently answer a broader range of queries, including categorical queries, in deployments with millions or even billions of participants. Arboretum achieves this by 1) automatically optimizing query plans to find highly efficient ways to answer each query, and by 2) including the participant devices in the computation. Our evaluation shows that Arboretum can match the cost of earlier systems that have been hand-optimized for particular kinds of queries, and that it can additionally support a range of new queries for which no efficient solution exists today.

PDF BibTeX Abstract Eli's slides
Mycelium: Large-Scale Distributed Graph Queries with Differential Privacy. Edo Roth, Karan Newatia, Yiping Ma, Ke Zhong, Sebastian Angel, and Andreas Haeberlen. 28th ACM Symposium on Operating Systems Principles (SOSP '21), Oct 2021.

× @inproceedings{roth-2021-mycelium,
  author = {Edo Roth and Karan Newatia and Yiping Ma and Ke Zhong and Sebastian Angel and Andreas Haeberlen},
  title = {Mycelium: Large-Scale Distributed Graph Queries with Differential Privacy},
  booktitle = {28th ACM Symposium on Operating Systems Principles (SOSP '21)},
  doi = {10.1145/3477132.3483585},
  month = oct,
  year = 2021
}

×
This paper introduces Mycelium, the first system to process differentially private queries over large graphs that are distributed across millions of user devices. Such graphs occur, for instance, when tracking the spread of diseases or malware. Today, the only practical way to query such graphs is to upload them to a central aggregator, which requires a great deal of trust from users and rules out certain types of studies entirely. With Mycelium, users’ private data never leaves their personal devices unencrypted, and each user receives strong privacy guarantees. Mycelium does require the help of a central aggregator with access to a data center, but the aggregator merely facilitates the computation by providing bandwidth and computation power; it never learns the topology of the graph or the underlying data. Mycelium accomplishes this with a combination of homomorphic encryption, a verifiable secret redistribution scheme, and a mix network based on telescoping circuits. Our evaluation shows that Mycelium can answer a range of different questions from the medical literature with millions of devices.

PDF BibTeX Abstract Edo's slides Talk
Do Not Overpay for Fault Tolerance! Edo Roth and Andreas Haeberlen. 27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21), May 2021.

× @inproceedings{roth-2021-byzantine,
  author = {Edo Roth and Andreas Haeberlen},
  title = {Do Not Overpay for Fault Tolerance!},
  booktitle = {27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21)},
  doi = {10.1109/RTAS52030.2021.00037},
  month = may,
  year = 2021
}

×
In this paper, we argue that distributed real-time and embedded systems sometimes 'overpay' for fault tolerance, by using a protocol that is more powerful than what is actually needed, or by failing to take advantage of unique features in these systems. As a result, these systems sometimes perform more computation or communication than is strictly necessary, or they can be unnecessarily complex, and thus more difficult to analyze.
We take a look at the design space for two common problems, broadcast and consensus, and we show that, in a number of scenarios that would be common in real-time systems, these problems have trivial solutions. We then examine two solutions from the literature and propose alternatives that are substantially simpler, less expensive, and more reliable.

PDF BibTeX Abstract Slides Talk
DNA: Dynamic Resource Allocation for Soft Real-Time Multicore Systems. Robert Gifford, Neeraj Gandhi, Linh Thi Xuan Phan, and Andreas Haeberlen. 27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21), May 2021.

× @inproceedings{gifford-2021-dna,
  author = {Robert Gifford and Neeraj Gandhi and Linh Thi Xuan Phan and Andreas Haeberlen},
  title = {{DNA}: {D}ynamic Resource Allocation for Soft Real-Time Multicore Systems},
  booktitle = {27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21)},
  doi = {10.1109/RTAS52030.2021.00024},
  month = may,
  year = 2021
}

×
Modern latency-sensitive and real-time systems often use multi-core platforms; thus, tasks on different cores share certain hardware resources, such as the memory bus and certain cache levels. This has two undesirable consequences: (1) tasks can interfere with each other, causing high latency for the system as a whole, and (2) it becomes difficult to meet deadlines, since the worst-case timing of a given task depends on the worst task it might have to compete with. Static partitioning isolates tasks from each other by allocating a certain fraction of the resources to each; however, many tasks execute in different phases (e.g., memory-intensive and CPU-intensive) that have different requirements. Thus, system designers are left with a choice between overprovisioning, based on the most demanding phase, or suboptimal performance.
In this paper, we propose a pair of techniques, called DNA and DADNA, to address the above challenge. DNA increases throughput and decreases latency, by building an execution profile of each task to identify the phases, and then dynamically allocating resources based on which task can benefit the most; DADNA further adds support for soft real-time workloads by taking deadlines into account. We have built a prototype of both techniques in the Xen hypervisor; our experimental results show that, compared to a state-of-the-art solution, DNA and DADNA can substantially improve schedulability, reduce job deadline miss ratios, and cut latencies by more than a factor of two even in extremely overloaded situations.

PDF BibTeX Abstract Talk
REBOUND: Defending Distributed Systems Against Attacks with Bounded-Time Recovery. Neeraj Gandhi, Edo Roth, Brian Sandler, Andreas Haeberlen, and Linh Thi Xuan Phan. 16th European Conference on Computer Systems (EuroSys '21), Apr 2021.

× @inproceedings{gandhi-2021-rebound,
  author = {Neeraj Gandhi and Edo Roth and Brian Sandler and Andreas Haeberlen and Linh Thi Xuan Phan},
  title = {{REBOUND}: {D}efending Distributed Systems Against Attacks with {B}ounded-{T}ime {R}ecovery},
  booktitle = {16th European Conference on Computer Systems (EuroSys '21)},
  doi = {10.1145/3447786.3456257},
  month = apr,
  year = 2021
}

×
This paper shows how to use bounded-time recovery (BTR) to defend distributed systems against non-crash faults and attacks. Unlike many existing fault-tolerance techniques, BTR does not attempt to completely mask all symptoms of a fault; instead, it ensures that the system returns to the correct behavior within a bounded amount of time. This weaker guarantee is sufficient, e.g., for many cyber-physical systems, where physical properties – such as inertia and thermal capacity – prevent quick state changes and thus limit the damage that can result from a brief period of undefined behavior.
We present an algorithm called REBOUND that can provide BTR for the Byzantine fault model. REBOUND works by detecting faults and then reconfiguring the system to exclude the faulty nodes. This supports very fine-grained responses to faults: for instance, the system can move or replace existing tasks, or drop less critical tasks entirely to conserve resources. REBOUND can take useful actions even when a majority of the nodes is compromised, and it requires less redundancy than full fault-tolerance.

PDF BibTeX Abstract Neeraj's slides Talk
Orchard: Differentially Private Analytics at Scale. Edo Roth, Hengchu Zhang, Andreas Haeberlen, and Benjamin C. Pierce. 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20), Nov 2020.

× @inproceedings{roth-2020-orchard,
  author = {Edo Roth and Hengchu Zhang and Andreas Haeberlen and Benjamin C. Pierce},
  title = {Orchard: {D}ifferentially Private Analytics at Scale},
  booktitle = {14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20)},
  month = nov,
  year = 2020
}

×
This paper presents Orchard, a system that can answer queries about sensitive data that is held by millions of user devices, with strong differential privacy guarantees. Orchard combines high accuracy with good scalability, and it uses only a single untrusted party to facilitate the query. Moreover, whereas previous solutions that shared these properties were custom-built for specific queries, Orchard is general and can accept a wide range of queries. Orchard accomplishes this by rewriting queries into a distributed protocol that can be executed efficiently at scale, using cryptographic primitives.
Our prototype of Orchard can execute 14 out of 17 queries chosen from the literature; to our knowledge, no other system can handle more than one of them in this setting. And the costs are moderate: each user device typically needs only a few megabytes of traffic and a few minutes of computation time. Orchard also includes a novel defense against malicious users who attempt to distort the results of a query.

PDF BibTeX Abstract Edo's slides Talk TR
Testing Differential Privacy with Dual Interpreters. Hengchu Zhang, Edo Roth, Benjamin C. Pierce, Aaron Roth, and Andreas Haeberlen. 35th ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA '20), Nov 2020.

× @inproceedings{zhang-2020-testing,
  author = {Hengchu Zhang and Edo Roth and Benjamin C. Pierce and Aaron Roth and Andreas Haeberlen},
  title = {Testing Differential Privacy with Dual Interpreters},
  booktitle = {35th ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA '20)},
  month = nov,
  year = 2020
}

×
Applying differential privacy at scale requires convenient ways to check that programs computing with sensitive data appropriately preserve privacy. We propose here a fully automated framework for testing differential privacy, adapting a well-known 'pointwise' technique from informal proofs of differential privacy. Our framework, called DPCheck, requires no programmer annotations, handles all previously verified or tested algorithms, and is the first fully automated framework to distinguish correct and buggy implementations of PrivTree, a probabilistically terminating algorithm that has not previously been mechanically checked.
We analyze the probability of DPCheck mistakenly accepting a non-private program and prove that, theoretically, the probability of false acceptance can be made exponentially small by suitable choice of test size.
We demonstrate DPCheck's utility empirically by implementing all benchmark algorithms from prior work on mechanical verification of differential privacy, plus several others and their incorrect variants, and show DPCheck accepts the correct implementations and rejects the incorrect variants.
We also demonstrate how DPCheck can be deployed in a practical workflow to test differentially privacy for the 2020 US Census Disclosure Avoidance System (DAS).

PDF BibTeX Abstract
Bounded-Time Recovery for Distributed Real-Time Systems. Neeraj Gandhi, Edo Roth, Robert Gifford, Linh Thi Xuan Phan, and Andreas Haeberlen. 26th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '20), Apr 2020.

× @inproceedings{gandhi-2020-cascade,
  author = {Neeraj Gandhi and Edo Roth and Robert Gifford and Linh Thi Xuan Phan and Andreas Haeberlen},
  title = {Bounded-Time Recovery for Distributed Real-Time Systems},
  booktitle = {26th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '20)},
  month = apr,
  year = 2020
}

×
This paper explores bounded-time recovery (BTR), a new approach to making cyber-physical systems robust to crash faults. Rather than trying to mask the symptoms of a fault with massive redundancy, BTR detects faults at runtime and enables the system to recover from them – e.g., by transferring tasks to other nodes that are still working correctly. When a fault does occur, there is a brief period of instability during which the system can produce incorrect outputs. However, many cyber-physical systems have physical properties – such as inertia or thermal capacity – that limit the rate at which the state of the system can change; thus, a very brief outage is often acceptable, as long as its duration can be bounded, to perhaps a few milliseconds.
BTR has some interesting properties: for instance, it has a much lower overhead than Paxos, and, unlike Paxos, it can take useful actions even when the system partitions or a majority of the nodes fails. However, it also poses a very unusual scheduling problem that involves creating sets of interrelated schedules for different failure modes. We present a scheduling algorithm called Cascade that can quickly find suitable schedules. Using a prototype implementation, we show that Cascade scales far better than a baseline algorithm and reduces the scheduling time from hours to a few seconds, without sacrificing quality.

PDF BibTeX Abstract Neeraj's slides Talk
Honeycrisp: Large-scale Differentially Private Aggregation Without a Trusted Core. Edo Roth, Daniel Noble, Brett Hemenway Falk, and Andreas Haeberlen. 27th ACM Symposium on Operating Systems Principles (SOSP '19), Huntsville, Ontario, Canada, Oct 2019.

× @inproceedings{roth-2019-honeycrisp,
  author = {Edo Roth and Daniel Noble and Brett {Hemenway Falk} and Andreas Haeberlen},
  title = {Honeycrisp: {L}arge-scale Differentially Private Aggregation Without a Trusted Core},
  booktitle = {27th ACM Symposium on Operating Systems Principles (SOSP '19)},
  location = {Huntsville, Ontario, Canada},
  month = oct,
  year = 2019
}

×
Recently, a number of systems have been deployed that gather sensitive statistics from user devices while giving differential privacy guarantees. One prominent example is the component in Apple's macOS and iOS devices that collects information about emoji usage and new words. However, these systems have been criticized for making unrealistic assumptions, e.g., by creating a very high 'privacy budget' for answering queries, and by replenishing this budget every day, which results in a high worst-case privacy loss. However, it is not obvious whether such assumptions can be avoided if one requires a strong threat model and wishes to collect data periodically, instead of just once.
In this paper, we show that, essentially, it is possible to have one's cake and eat it too. We describe a system called Honeycrisp whose privacy cost depends on how often the data changes, and not on how often a query is asked. Thus, if the data is relatively stable (as is likely the case, e.g., with emoji and word usage), Honeycrisp can answer periodic queries for many years, as long as the underlying data does not change too often. Honeycrisp accomplishes this by using a) the sparse-vector technique, and b) a combination of cryptographic techniques to enable global differential privacy without a trusted party. Using a prototype implementation, we show that Honeycrisp is efficient and can scale to large deployments.

PDF BibTeX Abstract Edo's slides TR
Fuzzi: A Three-Level Logic for Differential Privacy. Hengchu Zhang, Edo Roth, Andreas Haeberlen, Benjamin C. Pierce, and Aaron Roth. 24nd ACM SIGPLAN International Conference on Functional Programming (ICFP '19), Berlin, Germany, Aug 2019.

× @inproceedings{zhang-2019-fuzzi,
  author = {Hengchu Zhang and Edo Roth and Andreas Haeberlen and Benjamin C. Pierce and Aaron Roth},
  title = {Fuzzi: {A} Three-Level Logic for Differential Privacy},
  booktitle = {24nd ACM SIGPLAN International Conference on Functional Programming (ICFP '19)},
  location = {Berlin, Germany},
  month = aug,
  year = 2019
}

×
Curators of sensitive datasets sometimes need to know whether queries against the data are differentially private. Two sorts of logics have been proposed for checking this property: (1) type systems and other static analyses, which fully automate straightforward reasoning with concepts like 'program sensitivity' and 'privacy loss,' and (2) full-blown program logics such as apRHL (an approximate, probabilistic, relational Hoare logic), which support more flexible reasoning about subtle privacy-preserving algorithmic techniques but offer only minimal automation.
We propose a three-level logic for differential privacy in an imperative setting and present a prototype implementation called Fuzzi. Fuzzi's lowest level is a general-purpose logic; its middle level is apRHL; and its top level is a novel sensitivity logic adapted from the linear-logic-inspired type system of Fuzz, a differentially private functional language. The key novelty is a high degree of integration between the sensitivity logic and the two lower-level logics: the judgments and proofs of the sensitivity logic can be easily translated into apRHL; conversely, privacy properties of key algorithmic building blocks can be proved manually in apRHL and the base logic, then packaged up as typing rules that can be applied by a checker forthe sensitivity logic to automatically construct privacy proofs for composite programs of arbitrary size.
We demonstrate Fuzzi's utility by implementing four different private machine-learning algorithms and showing that Fuzzi's checker is able to derive tight sensitivity bounds.

PDF BibTeX Abstract Hengchu's slides
DeDoS: Defusing DoS with Dispersion Oriented Software. Henri Maxime Demoulin, Tavish Vaidya, Isaac Pedisich, Bob DiMaiolo, Jingyu Qian, Chirag Shah, Yuankai Zhang, Ang Chen, Andreas Haeberlen, Boon Thau Loo, Linh Thi Xuan Phan, Micah Sherr, Clay Shields, and Wenchao Zhou. 2018 Annual Computer Security Applications Conference (ACSAC '18), San Juan, Puerto Rico, Dec 2018.

× @inproceedings{demoulin-2018-dedos,
  author = {Henri Maxime Demoulin and Tavish Vaidya and Isaac Pedisich and Bob {DiMaiolo} and Jingyu Qian and Chirag Shah and Yuankai Zhang and Ang Chen and Andreas Haeberlen and Boon Thau Loo and Linh Thi Xuan Phan and Micah Sherr and Clay Shields and Wenchao Zhou},
  title = {{DeDoS}: {D}efusing {DoS} with Dispersion Oriented Software},
  booktitle = {2018 Annual Computer Security Applications Conference (ACSAC '18)},
  location = {San Juan, Puerto Rico},
  month = dec,
  year = 2018
}

×
This paper presents DeDoS, a novel platform for mitigating asymmetric DoS attacks. These attacks are particularly challenging sinceeven attackers with limited resources can exhaust the resources of well-provisioned servers. DeDoS offers a framework to deploy code in a highly modular fashion. If part of the application stack is experiencing a DoS attack, DeDoS can massively replicate only the affected component, potentially across many machines. This allows scaling of the impacted resource separately from the rest of the application stack, so that resources can be precisely added where needed to combat the attack. Our evaluation results show that DeDoS incurs reasonable overheads in normal operations, and that it significantly outperforms standard replication techniques when defending against a range of asymmetric attacks.

PDF BibTeX Abstract
A Framework for Adaptive Differential Privacy. Daniel Winograd-Cort, Andreas Haeberlen, Aaron Roth, and Benjamin C. Pierce. 22nd ACM SIGPLAN International Conference on Functional Programming (ICFP '17), Oxford, UK, Sep 2017.

× @inproceedings{winograd-cort-2017-adaptive,
  author = {Daniel Winograd-Cort and Andreas Haeberlen and Aaron Roth and Benjamin C. Pierce},
  title = {A Framework for Adaptive Differential Privacy},
  booktitle = {22nd ACM SIGPLAN International Conference on Functional Programming (ICFP '17)},
  location = {Oxford, UK},
  month = sep,
  year = 2017
}

×
Differential privacy is a widely studied theory for analyzing sensitive data with a strong privacy guarantee – any change in an individual’s data can have only a small statistical effect on the result – and a growing number of programming languages now support differentially private data analysis. A common shortcoming of these languages is poor support for adaptivity. In practice, a data analyst rarely wants to run just one function over a sensitive database, nor even a predetermined sequence of functions with fixed privacy parameters; rather, she wants to engage in an interaction where, at each step, both the choice of the next function and its privacy parameters are informed by the results of prior functions. Existing languages support this scenario using a simple composition theorem, which often gives rather loose bounds on the actual privacy cost of composite functions, substantially reducing how much computation can be performed within a given privacy budget. The theory of differential privacy includes other theorems with much better bounds, but these have not yet been incorporated into programming languages.
We propose a novel framework for adaptive composition that is elegant, practical, and implementable. It consists of a reformulation based on typed functional programming of privacy filters, together with a concrete realization of this framework in the design and implementation of a new language, called Adaptive Fuzz. Adaptive Fuzz transplants the core static type system of Fuzz to the adaptive setting by wrapping the Fuzz typechecker and runtime system in an outer adaptive layer, allowing Fuzz programs to be conveniently constructed and typechecked on the fly. We describe an interpreter for Adaptive Fuzz and report results from two case studies demonstrating its effectiveness for implementing common statistical algorithms over real data sets.

PDF BibTeX Abstract Extended version
DStress: Efficient Differentially Private Computations on Distributed Data. Antonis Papadimitriou, Arjun Narayan, and Andreas Haeberlen. 12th European Conference on Computer Systems (EuroSys '17), Belgrade, Serbia, Apr 2017.

× @inproceedings{papadimitriou-2017-dstress,
  author = {Antonis Papadimitriou and Arjun Narayan and Andreas Haeberlen},
  title = {{DStress}: {E}fficient Differentially Private Computations on Distributed Data},
  booktitle = {12th European Conference on Computer Systems (EuroSys '17)},
  location = {Belgrade, Serbia},
  month = apr,
  year = 2017
}

×
In this paper, we present DStress, a system that can efficiently perform computations on graphs that contain confidential data. DStress assumes that the graph is physically distributed across many participants, and that each participant only knows a small subgraph; it protects privacy by enforcing tight, provable limits on how much each participant can learn about the rest of the graph.
We also study one concrete instance of this problem: measuring systemic risk in financial networks. Systemic risk is the likelihood of cascading bankruptcies – as, e.g., during the financial crisis of 2008 – and it can be quantified based on the dependencies between financial institutions; however, the necessary data is highly sensitive and cannot be safely disclosed. We show that DStress can implement two different systemic risk models from the theoretical economics literature. Our experimental evaluation suggests that DStress can run the corresponding computations in about five hours, whereas a naive approach could take several decades.

PDF BibTeX Abstract Antonis's slides
One Primitive to Diagnose Them All: Architectual Support for Internet Diagnostics. Ang Chen, Andreas Haeberlen, Wenchao Zhou, and Boon Thau Loo. 12th European Conference on Computer Systems (EuroSys '17), Belgrade, Serbia, Apr 2017.

× @inproceedings{chen-2017-spp,
  author = {Ang Chen and Andreas Haeberlen and Wenchao Zhou and Boon Thau Loo},
  title = {One Primitive to Diagnose Them All: {A}rchitectual Support for Internet Diagnostics},
  booktitle = {12th European Conference on Computer Systems (EuroSys '17)},
  location = {Belgrade, Serbia},
  month = apr,
  year = 2017
}

×
Today, network operators are increasingly playing the role of part-time detectives: they must routinely diagnose intricate problems and malfunctions, e.g., routing or performance issues, and they must often perform forensic investigations of past misbehavior, e.g., intrusions or cybercrimes. However, the current Internet architecture offers little direct support for them. A variety of solutions have been proposed, but each solution tends to address only one specific problem. Moreover, each solution proposes a different fix that is incompatible with the others, which complicates deployment.
In this paper, we make the observation that most of the existing solutions share a common 'functional core', which suggests that it may be possible to add a single primitive to the Internet architecture that can support a wide variety of diagnostic and forensic tasks.We then present one specific candidate that we call secure packet provenance (SPP). We show that SPP is easy to add to the current architecture, that it can be implemented efficiently in both software and hardware, and that it can be used to approximate (and sometimes surpass) the capabilities offered by a variety of existing diagnostic and forensic systems.

PDF BibTeX Abstract Ang's slides
Automated Bug Removal for Software-Defined Networks. Yang Wu, Ang Chen, Andreas Haeberlen, Wenchao Zhou, and Boon Thau Loo. 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI '17), Boston, MA, Mar 2017.

× @inproceedings{wu-2017-metaprovenance,
  author = {Yang Wu and Ang Chen and Andreas Haeberlen and Wenchao Zhou and Boon Thau Loo},
  title = {Automated Bug Removal for Software-Defined Networks},
  booktitle = {14th USENIX Symposium on Networked Systems Design and Implementation (NSDI '17)},
  location = {Boston, MA},
  month = mar,
  year = 2017
}

×
When debugging an SDN application, diagnosing the problem is merely the first step: the operator must still find a fix that solves the problem, without causing new problems elsewhere. However, most existing debuggers focus exclusively on diagnosis and offer the network operator little or no help with finding an effective fix. Finding a suitable fix is difficult because the number of candidates can be enormous.
In this paper, we propose a step towards automated repair for SDN applications. Our approach consists of two elements. The first is a data structure that we call meta provenance, which can be used to efficiently find good candidate repairs. Meta provenance is inspired by the provenance concept from the database community; however, whereas standard provenance can only reason about changes to data, meta provenance can also reason about changes to programs. The second element is a system that can efficiently backtest a set of candidate repairs using historical data from the network. This is used to eliminate candidate repairs that do not work well, or that cause other problems.
We have implemented a system that maintains meta provenance for SDNs, as well as a prototype debugger that uses the meta provenance to automatically suggest repairs. Results from several case studies show that, for problems of moderate complexity, our debugger can find high-quality repairs within one minute.

PDF BibTeX Abstract Yang's slides TR
Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead. Ang Chen, Yang Wu, Andreas Haeberlen, Boon Thau Loo, and Wenchao Zhou. 8th Conference on Innovative Data Systems Research (CIDR '17), Chaminade, CA, Jan 2017.

× @inproceedings{chen-2017-provenance,
  author = {Ang Chen and Yang Wu and Andreas Haeberlen and Boon Thau Loo and Wenchao Zhou},
  title = {Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead},
  booktitle = {8th Conference on Innovative Data Systems Research (CIDR '17)},
  location = {Chaminade, CA},
  month = jan,
  year = 2017
}

×
Provenance is a way to answer "why" questions about computations. It has found a number of uses in the database community, such as debugging query answers or tracing unexpected results to database tuples. In fact, the ability to ask "why" can be useful for a much broader range of applications. In this paper, we summarize our experiences over the past few years in adapting provenance for diagnostic and forensic uses in networks and distributed systems. Our work draws inspirations from database provenance, yet the deployment scale, use cases, and distributed nature of networks require a significant redesign of traditional data provenance models. We review a number of use cases, ranging from investigating intrusions to diagnosing (and even automatically fixing) software-defined networks, and present a unified system architecture that we have designed and implemented for provenance in distributed systems. We conclude with a discussion of open issues in this space.

PDF BibTeX Abstract
Big Data Analytics over Encrypted Datasets with Seabed. Antonis Papadimitriou, Ranjita Bhagwan, Nishanth Chandran, Ramachandran Ramjee, Andreas Haeberlen, Harmeet Singh, Abhishek Modi, and Saikrishna Badrinarayanan. 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI '16), Savannah, GA, Nov 2016.

× @inproceedings{papadimitriou-2017-seabed,
  author = {Antonis Papadimitriou and Ranjita Bhagwan and Nishanth Chandran and Ramachandran Ramjee and Andreas Haeberlen and Harmeet Singh and Abhishek Modi and Saikrishna Badrinarayanan},
  title = {Big Data Analytics over Encrypted Datasets with Seabed},
  booktitle = {12th USENIX Symposium on Operating Systems Design and Implementation (OSDI '16)},
  location = {Savannah, GA},
  month = nov,
  year = 2016
}

×
Today, enterprises collect large amounts of data and leverage the cloud to perform analytics over this data. Since the data is often sensitive, enterprises would prefer to keep it confidential and to hide it even from the cloud operator. Systems such as CryptDB and Monomi can accomplish this by operating mostly on encrypted data; however, these systems rely on expensive cryptographic techniques that limit performance in true "big data" scenarios that involve terabytes of data or more.
This paper presents Seabed, a system that enables efficient analytics over large encrypted datasets. In contrast to previous systems, which rely on asymmetric encryption schemes, Seabed uses a novel, additively symmetric homomorphic encryption scheme (ASHE) to perform large-scale aggregations efficiently. Additionally, Seabed introduces a novel randomized encryption scheme called Splayed ASHE, or SPLASHE, that can, in certain cases, prevent frequency attacks based on auxiliary data.

PDF BibTeX Abstract Antonis's slides TR
The Good, the Bad, and the Differences: Better Network Diagnostics with Differential Provenance. Ang Chen, Yang Wu, Andreas Haeberlen, Wenchao Zhou, and Boon Thau Loo. 2016 ACM SIGCOMM Conference (SIGCOMM '16), Florianópolis, Brazil, Aug 2016.

× @inproceedings{chen-2016-diffprov,
  author = {Ang Chen and Yang Wu and Andreas Haeberlen and Wenchao Zhou and Boon Thau Loo},
  title = {The Good, the Bad, and the Differences: {B}etter Network Diagnostics with Differential Provenance},
  booktitle = {2016 ACM SIGCOMM Conference (SIGCOMM '16)},
  location = {Florianópolis, Brazil},
  month = aug,
  year = 2016
}

×
In this paper, we propose a new approach to diagnosing problems in distributed systems. Our approach is based on the insight that many of the trickiest problems are anomalies. For instance, in a network, problems often affect only a small fraction of the traffic (perhaps a certain subnet), or they only manifest infrequently. Thus, it is quite common for the operator to have 'examples' of both working and non-working traffic readily available – perhaps a packet that was misrouted, and a similar packet that was routed correctly. In this case, the cause of the problem is likely to be wherever the two packets were treated differently by the network.
We present the design of a debugger that can leverage this information using a novel concept that we call differential provenance. Differential provenance tracks the causal connections between network states and state changes, just like classical provenance, but it can additionally perform root-cause analysis by reasoning about the differences between two provenance trees. We have built a diagnostic tool that is based on differential provenance, and we have used our tool to debug a number of complex, realistic problems in two scenarios: software-defined networks and MapReduce jobs. Our results show that differential provenance can deliver very concise diagnostic information; in many cases, it can even identify the precise root cause of the problem.

PDF BibTeX Abstract Ang's slides Talk
Verifiable Differential Privacy. Arjun Narayan, Ariel Feldman, Antonis Papadimitriou, and Andreas Haeberlen. 10th European Conference on Computer Systems (EuroSys '15), Bordeaux, France, Apr 2015.

× @inproceedings{narayan-2015-verdp,
  author = {Arjun Narayan and Ariel Feldman and Antonis Papadimitriou and Andreas Haeberlen},
  title = {Verifiable Differential Privacy},
  booktitle = {10th European Conference on Computer Systems (EuroSys '15)},
  location = {Bordeaux, France},
  month = apr,
  year = 2015
}

×
Working with sensitive data is often a balancing act between privacy and integrity concerns. Consider, for instance, a medical researcher who has analyzed a patient database to judge the effectiveness of a new treatment and would now like to publish her findings. On the one hand, the patients may be concerned that the researcher's results contain too much information and accidentally leak some private fact about themselves; on the other hand, the readers of the published study may be concerned that the results contain too little information, limiting their ability to detect errors in the calculations or flaws in the methodology.
This paper presents VerDP, a system for private data analysis that provides both strong integrity and strong differential privacy guarantees. VerDP accepts queries that are written in a special query language, and it processes them only if a) it can certify them as differentially private, and if b) it can prove the integrity of the result in zero knowledge. Our experimental evaluation shows that VerDP can successfully process several different queries from the differential privacy literature, and that the cost of generating and verifying the proofs is practical: for example, a histogram query over a 63,488-entry data set resulted in a 20~kB proof that took 32 EC2 instances less than two hours to generate, and that could be verified on a single machine in about one second.

PDF BibTeX Abstract Antonis's slides
Detecting Covert Timing Channels with Time-Deterministic Replay. Ang Chen, W. Brad Moore, Hanjun Xiao, Andreas Haeberlen, Linh Thi Xuan Phan, Micah Sherr, and Wenchao Zhou. 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI '14), Broomfield, CO, Oct 2014.

× @inproceedings{chen-2014-tdr,
  author = {Ang Chen and W. Brad Moore and Hanjun Xiao and Andreas Haeberlen and Linh Thi Xuan Phan and Micah Sherr and Wenchao Zhou},
  title = {Detecting Covert Timing Channels with Time-Deterministic Replay},
  booktitle = {11th USENIX Symposium on Operating Systems Design and Implementation (OSDI '14)},
  location = {Broomfield, CO},
  month = oct,
  year = 2014
}

×
This paper presents a mechanism called time-deterministic replay (TDR) that can reproduce the execution of a program, including its precise timing. Without TDR, reproducing the timing of an execution is difficult because there are many sources of timing variability – such as preemptions, hardware interrupts, cache effects, scheduling decisions, etc. TDR uses a combination of techniques to either mitigate or eliminate most of these sources of variability. Using a prototype implementation of TDR in a Java Virtual Machine, we show that it is possible to reproduce the timing to within 1.85% of the original execution, even on commodity hardware.
The paper discusses several potential applications of TDR, and studies one of them in detail: the detection of a covert timing channel. Timing channels can be used to exfiltrate information from a compromised machine; they work by subtly varying the timing of the machine's outputs, and it is this variation that can be detected with TDR. Unlike prior solutions, which generally look for a specific type of timing channel, our approach can detect a wide variety of channels with high accuracy.

PDF BibTeX Abstract Ang's slides
Diagnosing Missing Events in Distributed Systems with Negative Provenance. Yang Wu, Mingchen Zhao, Andreas Haeberlen, Wenchao Zhou, and Boon Thau Loo. 2014 ACM SIGCOMM Conference (SIGCOMM '14), Chicago, IL, Aug 2014.

× @inproceedings{chen-2016-diffprov,
  author = {Yang Wu and Mingchen Zhao and Andreas Haeberlen and Wenchao Zhou and Boon Thau Loo},
  title = {Diagnosing Missing Events in Distributed Systems with Negative Provenance},
  booktitle = {2014 ACM SIGCOMM Conference (SIGCOMM '14)},
  location = {Chicago, IL},
  month = aug,
  year = 2014
}

×
When debugging a distributed system, it is sometimes necessary to explain the absence of an event – for instance, why a certain route is not available, or why a certain packet did not arrive. Existing debuggers offer some support for explaining the presence of events, usually by providing the equivalent of a backtrace in conventional debuggers, but they are not very good at answering "Why not?" questions: there is simply no starting point for a possible backtrace.
In this paper, we show that the concept of negative provenance can be used to explain the absence of events in distributed systems. Negative provenance relies on counterfactual reasoning to identify the conditions under which the missing event could have occurred. We define a formal model of negative provenance for distributed systems, and we present the design of a system called Y! that tracks both positive and negative provenance and can use them to answer diagnostic queries. We describe how we have used Y! to debug several realistic problems in two application domains: software-defined networks and BGP interdomain routing. Results from our experimental evaluation show that the overhead of Y! is moderate.

PDF BibTeX Abstract Yang's slides TR
Differential Privacy: An Economic Method for Choosing Epsilon. Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin Pierce, and Aaron Roth. 2014 IEEE Computer Security Foundations Symposium (CSF '14), Vienna, Austria, Jul 2014.

× @inproceedings{hsu-2014-epsilon,
  author = {Justin Hsu and Marco Gaboardi and Andreas Haeberlen and Sanjeev Khanna and Arjun Narayan and Benjamin Pierce and Aaron Roth},
  title = {Differential Privacy: {A}n Economic Method for Choosing Epsilon},
  booktitle = {2014 IEEE Computer Security Foundations Symposium (CSF '14)},
  location = {Vienna, Austria},
  month = jul,
  year = 2014
}

×
Differential privacy is becoming a gold standard notion of privacy; it offers a guaranteed bound on loss of privacy due to release of query results, even under worst-case assumptions. The theory of differential privacy is an active research area, and there are now differentially private algorithms for a wide range of problems.
However, the question of when differential privacy works in practice has received relatively little attention. In particular, there is still no rigorous method for choosing the key parameter epsilon, which controls the crucial tradeoff between the strength of the privacy guarantee and the accuracy of the published results.
In this paper, we examine the role of these parameters in concrete applications, identifying the key considerations that must be addressed when choosing specific values. This choice requires balancing the interests of two parties with conflicting objectives: the data analyst, who wishes to learn something about the data, and the prospective participant, who must decide whether to allow their data to be included in the analysis. We propose a simple model that expresses this balance as formulas over a handful of parameters, and we use our model to choose epsilon on a series of simple statistical studies. We also explore a surprising insight: in some circumstances, a differentially private study can be more accurate than a non-private study for the same cost, under our model. Finally, we discuss the simplifying assumptions in our model and outline a research agenda for possible refinements.

PDF BibTeX Abstract Justin's slides
Peer-Assisted Content Distribution in Akamai NetSession. Mingchen Zhao, Paarijaat Aditya, Ang Chen, Yin Lin, Andreas Haeberlen, Peter Druschel, Bruce Maggs, Bill Wishon, and Miroslav Ponec. 13th ACM SIGCOMM Conference on Internet Measurement (IMC '13), Barcelona, Spain, Oct 2013.

× @inproceedings{zhao-2013-netsession,
  author = {Mingchen Zhao and Paarijaat Aditya and Ang Chen and Yin Lin and Andreas Haeberlen and Peter Druschel and Bruce Maggs and Bill Wishon and Miroslav Ponec},
  title = {Peer-Assisted Content Distribution in {Akamai} {NetSession}},
  booktitle = {13th ACM SIGCOMM Conference on Internet Measurement (IMC '13)},
  location = {Barcelona, Spain},
  month = oct,
  year = 2013
}

×
Content distribution systems have traditionally adopted one of two architectures: infrastructure-based content delivery networks (CDNs), in which clients download content from dedicated, centrally managed servers, and peer-to-peer CDNs, in which clients download content from each other. The advantages and disadvantages of each architecture have been studied in great detail. Recently, hybrid, or "peer-assisted", CDNs have emerged, which combine elements from both architectures. The properties of such systems, however, are not as well understood.
In this paper, we discuss the potential risks and benefits of peer-assisted CDNs, and we study one specific instance, Akamai's NetSession system, to examine the impact of these risks and benefits in practice. NetSession is a mature system that has been operating commercially since 2010 and currently has more than 25 million users in 239 countries and territories. Our results show that NetSession can deliver several of the key benefits of both infrastructure-based and peer-to-peer CDNs – for instance, it can offload 70-80% of the traffic to the peers without a corresponding loss of performance or reliability – and that the risks can be managed well. This suggests that hybrid designs may be an attractive option for future CDNs.

PDF BibTeX Abstract
Distributed Time-Aware Provenance. Wenchao Zhou, Suyog Mapara, Yiqing Ren, Yang Li, Andreas Haeberlen, Zachary Ives, Boon Thau Loo, and Micah Sherr. 39th International Conference on Very Large Data Bases (VLDB '13), Riva del Garda, Italy, Aug 2013.

× @inproceedings{zhou-2013-dtap,
  author = {Wenchao Zhou and Suyog Mapara and Yiqing Ren and Yang Li and Andreas Haeberlen and Zachary Ives and Boon Thau Loo and Micah Sherr},
  title = {Distributed Time-Aware Provenance},
  booktitle = {39th International Conference on Very Large Data Bases (VLDB '13)},
  location = {Riva del Garda, Italy},
  month = aug,
  year = 2013
}

×
The ability to reason about changes in a distributed system's state enables network administrators to better diagnose protocol misconfigurations, detect intrusions, and pinpoint performance bottlenecks. We propose a novel provenance model called Distributed Time-aware Provenance (DTaP) that aids forensics and debugging in distributed systems by explicitly representing time, distributed state, and state changes. Using a distributed Datalog abstraction for modeling distributed protocols, we prove that the DTaP model provides a sound and complete representation that correctly captures dependencies among events in a distributed system. We additionally introduce DistTape, an implementation of the DTaP model that uses novel distributed storage structures, query processing, and cost-based optimization techniques to efficiently query time-aware provenance in a distributed setting. Using two example systems (declarative network routing and Hadoop MapReduce), we demonstrate that DistTape can efficiently maintain and query time-aware provenance at low communication and computation cost.

PDF BibTeX Abstract
TrustForge: Flexible access control for collaborative crowd-sourced environment. Jian Chang, Peter Gebhard, Andreas Haeberlen, Zachary G. Ives, Insup Lee, Oleg Sokolsky, and Krishna K. Venkatasubramanian. 11th International Conference on Privacy, Security and Trust (PST '13), Tarragona, Spain, Jul 2013.

× @inproceedings{chang-2013-trustforge,
  author = {Jian Chang and Peter Gebhard and Andreas Haeberlen and Zachary G. Ives and Insup Lee and Oleg Sokolsky and Krishna K. Venkatasubramanian},
  title = {{TrustForge}: {F}lexible access control for collaborative crowd-sourced environment},
  booktitle = {11th International Conference on Privacy, Security and Trust (PST '13)},
  location = {Tarragona, Spain},
  month = jul,
  year = 2013
}

×
Observing the success of the open source software movement, the Adaptive Vehicle Make (AVM) is a program run by the Defense Advanced Project Agency (DARPA) with the goal of applying crowd-sourced and component-based engineering to the design of military vehicles. In this paper, we present a credentialing system called TrustForge, which enables effective and flexible access control for the AVMcrowd-sourced repository. Credentialing systems are essential in crowdsourcing to ensure quality, since it is potentially open to contributions made by anyone. The open source software community has developed elaborate manual approaches of managing its contributor community, which are often very labor-intensive and inefficient. Our aim with TrustForge is to improve the automation of the credentialing and access control process in the context of component-based systems, where users contribute components at various levels of abstraction. TrustForge takes a hybrid approach that combines trust policy and reputation to address this problem. In TrustForge, a policy language is used to specify the access control rules for users in the system to contribute components. In addition, reputation values computed for users based on the quality of their past component contributions are used to tune the static policies to enable flexibility and adaptiveness. The contributions of this work are as follows: (1) the design of TrustForge - an effective and flexible access control mechanism that combines policy and reputation approaches; (2) the identification of heuristics for component quality measurement and a novel reputation computation algorithm for evaluating user trustworthiness; (3) a data model based on provenance graphs that allows efficient repository information storage and retrieve. We have implemented TrustForge system and integrate it with the VehicleForge repository system to support the operation of the AVM challenge program. The evaluation results based on realworld deployment and systematic simulation demonstrate that TrustForge can effectively discern the trustworthiness of users within the crowd-sourced system.

BibTeX Abstract
Linear Dependent Types for Differential Privacy. Marco Gaboardi, Andreas Haeberlen, Justin Hsu, Arjun Narayan, and Benjamin C. Pierce. 40th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '13), Rome, Italy, Jan 2013.

× @inproceedings{gaboardi-2013-dfuzz,
  author = {Marco Gaboardi and Andreas Haeberlen and Justin Hsu and Arjun Narayan and Benjamin C. Pierce},
  title = {Linear Dependent Types for Differential Privacy},
  booktitle = {40th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '13)},
  location = {Rome, Italy},
  month = jan,
  year = 2013
}

×
Differential privacy offers a way to answer queries about sensitive information while providing strong, provable privacy guarantees, ensuring that the presence or absence of a single individual in the database has a negligible statistical effect on the query's result. Proving that a given query has this property involves establishing a bound on the query's sensitivity – how much its result can change when a single record is added or removed.
A variety of tools have been developed for certifying that a given query is differentially private. In one approach, Reed and Pierce proposed a functional programming language, Fuzz, for writing differentially private queries. Fuzz uses linear types to track sensitivity and a probability monad to express randomized computation; it guarantees that any program with a certain type is differentially private. Fuzz can successfully verify many useful queries. However, it fails when the sensitivity analysis depends on values that are not known statically.
We present DFuzz, an extension of Fuzz with a combination of linear indexed types and lightweight dependent types. This combination allows a richer sensitivity analysis that is able to certify a larger class of queries as differentially private, including ones whose sensitivity depends on runtime information. As in Fuzz, the differential privacy guarantee follows directly from the soundness theorem of the type system. We demonstrate the enhanced expressivity of DFuzz by certifying differential privacy for a broad class of iterative algorithms that could not be typed previously.

PDF BibTeX Abstract
DJoin: Differentially Private Join Queries over Distributed Databases. Arjun Narayan and Andreas Haeberlen. 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI '12), Hollywood, CA, Oct 2012.

× @inproceedings{narayan-2012-djoin,
  author = {Arjun Narayan and Andreas Haeberlen},
  title = {{DJoin}: {D}ifferentially Private Join Queries over Distributed Databases},
  booktitle = {10th USENIX Symposium on Operating Systems Design and Implementation (OSDI '12)},
  location = {Hollywood, CA},
  month = oct,
  year = 2012
}

×
In this paper, we study the problem of answering queries about private data that is spread across multiple different databases. For instance, a medical researcher may want to study a possible correlation between travel patterns and certain types of illnesses. The necessary information exists today – e.g., in airline reservation systems and hospital records – but it is maintained by two separate companies who are prevented by law from sharing this information with each other, or with a third party. This separation prevents the processing of such queries, even if the final answer, e.g., a correlation coefficient, would be safe to release.
We present DJoin, a system that can process such distributed queries and can give strong differential privacy guarantees on the result. DJoin can support many SQL-style queries, including joins of databases maintained by different entities, as long as they can be expressed using DJoin's two novel primitives: BN-PSI-CA, a differentially private form of private set intersection cardinality, and DCR, a multi-party combination operator that can aggregate noised cardinalities without compounding the individual noise terms. Our experimental evaluation shows that DJoin can process realistic queries at practical timescales: simple queries on three databases with 15,000 rows each take between 1 and 7.5 hours.

PDF BibTeX Abstract
Private and Verifiable Interdomain Routing Decisions. Mingchen Zhao, Wenchao Zhou, Alexander J. T. Gurney, Andreas Haeberlen, Micah Sherr, and Boon Thau Loo. 2012 ACM SIGCOMM Conference (SIGCOMM '12), Helsinki, Finland, Aug 2012.

× @inproceedings{zhao-2012-pvr,
  author = {Mingchen Zhao and Wenchao Zhou and Alexander J. T. Gurney and Andreas Haeberlen and Micah Sherr and Boon Thau Loo},
  title = {Private and Verifiable Interdomain Routing Decisions},
  booktitle = {2012 ACM SIGCOMM Conference (SIGCOMM '12)},
  location = {Helsinki, Finland},
  month = aug,
  year = 2012
}

×
Existing secure interdomain routing protocols can verify validity properties about individual routes, such as whether they correspond to a real network path. It is often useful to verify more complex properties relating to the route decision procedure – for example, whether the chosen route was the best one available, or whether it was consistent with the network’s peering agreements. However, this is difficult to do without knowing a network’s routing policy and full routing state, which are not normally disclosed.
In this paper, we show how a network can allow its peers toverify a number of nontrivial properties of its interdomain routing decisions without revealing any additional information. If all the properties hold, the peers learn nothing beyond what the interdomain routing protocol already reveals; if a property does not hold, at least one peer can detect this and prove the violation. We present SPIDeR, a practical system that applies this approach to the Border Gateway Protocol, and we report results from an experimental evaluation to demonstrate that SPIDeR has a reasonable overhead.

PDF BibTeX Abstract TR
Reliable Client Accounting for Hybrid Content-Distribution Networks. Paarijaat Aditya, Mingchen Zhao, Yin Lin, Andreas Haeberlen, Peter Druschel, Bruce Maggs, and Bill Wishon. 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI '12), San Jose, CA, Aug 2012.

× @inproceedings{aditya-2012-rca,
  author = {Paarijaat Aditya and Mingchen Zhao and Yin Lin and Andreas Haeberlen and Peter Druschel and Bruce Maggs and Bill Wishon},
  title = {Reliable Client Accounting for Hybrid Content-Distribution Networks},
  booktitle = {9th USENIX Symposium on Networked Systems Design and Implementation (NSDI '12)},
  location = {San Jose, CA},
  month = aug,
  year = 2012
}

×
Content distribution networks (CDNs) have started to adopt hybrid designs, which employ both dedicated edge servers and resources contributed by clients. Hybrid designs combine many of the advantages of infrastructure-based and peer-to-peer systems, but they also present new challenges. This paper identifies reliable client accounting as one such challenge. Operators of hybrid CDNs are accountable to their customers (i.e., content providers) for the CDN’s performance. Therefore, they need to offer reliable quality of service and a detailed account of content served. Service quality and accurate accounting, however, depend in part on interactions among untrusted clients. Using the Akamai NetSession client network in a case study, we demonstrate that a small number of malicious clients used in a clever attack could cause significant accounting inaccuracies.
We present a method for providing reliable accounting of client interactions in hybrid CDNs. The proposed method leverages the unique characteristics of hybrid systems to limit the loss of accounting accuracy and service quality caused by faulty or compromised clients. We also describe RCA, a system that applies this method to a commercial hybrid content-distribution network. Using trace-driven simulations, we show that RCA can detect and mitigate a variety of attacks, at the expense of a moderate increase in logging overhead.

PDF BibTeX Abstract
Secure Network Provenance. Wenchao Zhou, Qiong Fei, Arjun Narayan, Andreas Haeberlen, Boon Thau Loo, and Micah Sherr. 23rd ACM Symposium on Operating Systems Principles (SOSP '11), Cascais, Portugal, Oct 2011.

× @inproceedings{zhou-2011-snp,
  author = {Wenchao Zhou and Qiong Fei and Arjun Narayan and Andreas Haeberlen and Boon Thau Loo and Micah Sherr},
  title = {Secure Network Provenance},
  booktitle = {23rd ACM Symposium on Operating Systems Principles (SOSP '11)},
  location = {Cascais, Portugal},
  month = oct,
  year = 2011
}

×
This paper introduces secure network provenance (SNP), a novel technique that enables networked systems to explain to their operators why they are in a certain state – e.g., why a suspicious routing table entry is present on a certain router, or where a given cache entry originated. SNP provides network forensics capabilities by permitting operators to track down faulty or misbehaving nodes, and to assess the damage such nodes may have caused to the rest of the system. SNP is designed for adversarial settings and is robust to manipulation; its tamper-evident properties ensure that operators can detect when compromised nodes lie or falsely implicate correct nodes.
We also present the design of SNooPy, a general-purpose SNP system. To demonstrate that SNooPy is practical, we apply it to three example applications: the Quagga BGP daemon, a declarative implementation of Chord, and Hadoop MapReduce. Our results indicate that SNooPy can efficiently explain state in an adversarial setting, that it can be applied with minimal effort, and that its costs are low enough to be practical.

PDF BibTeX Abstract TR
Differential Privacy Under Fire. Andreas Haeberlen, Benjamin C. Pierce, and Arjun Narayan. 20th USENIX Security Symposium, San Francisco, CA, Aug 2011.

× @inproceedings{haeberlen-2011-fuzz,
  author = {Andreas Haeberlen and Benjamin C. Pierce and Arjun Narayan},
  title = {Differential Privacy Under Fire},
  booktitle = {20th USENIX Security Symposium},
  location = {San Francisco, CA},
  month = aug,
  year = 2011
}

×
Anonymizing private data before release is not enough to reliably protect privacy, as Netflix and AOL have learned to their cost. Recent research on differential privacy opens a way to obtain robust, provable privacy guarantees, and systems like PINQ and Airavat now offer convenient frameworks for processing arbitrary user-specified queries in a differentially private way. However, these systems are vulnerable to a variety of covert-channel attacks that can be exploited by an adversarial querier.
We describe several different kinds of attacks, all feasible in PINQ and some in Airavat. We discuss the space of possible countermeasures, and we present a detailed design for one specific solution, based on a new primitive we call predictable transactions and a simple differentially private programming language. Our evaluation, which relies on a proof-of-concept implementation based on the Caml Light runtime, shows that our design is effective against remotely exploitable covert channels, at the expense of a higher query completion time.

PDF BibTeX Abstract Slides
Accountable Virtual Machines. Andreas Haeberlen, Paarijaat Aditya, Rodrigo Rodrigues, and Peter Druschel. 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10), Vancouver, Canada, Oct 2010.

× @inproceedings{haeberlen-2010-avm,
  author = {Andreas Haeberlen and Paarijaat Aditya and Rodrigo Rodrigues and Peter Druschel},
  title = {Accountable Virtual Machines},
  booktitle = {9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10)},
  location = {Vancouver, Canada},
  month = oct,
  year = 2010
}

×
In this paper, we introduce accountable virtual machines (AVMs). Like ordinary virtual machines, AVMs can execute binary software images in a virtualized copy of a computer system; in addition, they can record non-repudiable information that allows auditors to subsequently check whether the software behaved as intended. AVMs provide strong accountability, which is important, for instance, in distributed systems where different hosts and organizations do not necessarily trust each other, or where software is hosted on third-party-operated platforms. AVMs can provide accountability for unmodified binary images and do not require trusted hardware. To demonstrate that AVMs are practical, we have designed and implemented a prototype AVM monitor based on VMware Workstation, and used it to detect several existing cheats in Counterstrike, a popular online multi-player game.

PDF BibTeX Abstract Slides Video TR
The Fault Detection Problem. Andreas Haeberlen and Petr Kuznetsov. 13th International Conference on Principles of Distributed Systems (OPODIS '09), Nimes, France, Dec 2009.

× @inproceedings{haeberlen-2009-detection,
  author = {Andreas Haeberlen and Petr Kuznetsov},
  title = {The Fault Detection Problem},
  booktitle = {13th International Conference on Principles of Distributed Systems (OPODIS '09)},
  location = {Nimes, France},
  month = dec,
  year = 2009
}

×
One of the most important challenges in distributed computing is ensuring that services are correct and available despite faults. Recently it has been argued that fault detection can be factored out from computation, and that a generic fault detection service can be a useful abstraction for building distributed systems. However, while fault detection has been extensively studied for crash faults, little is known about detecting more general kinds of faults.
This paper explores the power and the inherent costs of generic fault detection in a distributed system. We propose a formal framework that allows us to partition the set of all faults that can possibly occur in a distributed computation into several fault classes. Then we formulate the fault detection problem for a given fault class, and we show that this problem can be solved for only two specific fault classes, namely omission faults and commission faults. Finally, we derive tight lower bounds on the cost of solving the problem for these two classes in asynchronous message-passing systems.

PDF BibTeX Abstract TR
NetReview: Detecting when Interdomain Routing Goes Wrong. Andreas Haeberlen, Ioannis Avramopoulos, Jennifer Rexford, and Peter Druschel. 6th Symposium on Networked Systems Design and Implementation (NSDI '09), Boston, MA, Apr 2009.

× @inproceedings{haeberlen-2009-netreview,
  author = {Andreas Haeberlen and Ioannis Avramopoulos and Jennifer Rexford and Peter Druschel},
  title = {{NetReview}: {D}etecting when Interdomain Routing Goes Wrong},
  booktitle = {6th Symposium on Networked Systems Design and Implementation (NSDI '09)},
  location = {Boston, MA},
  month = apr,
  year = 2009
}

×
Despite many attempts to fix it, the Internet’s interdomain routing system remains vulnerable to configuration errors, buggy software, flaky equipment, protocol oscillation, and intentional attacks. Unlike most existing solutions that prevent specific routing problems, our approach is to detect problems automatically and to identify the offending party. Fault detection is effective for a larger class of faults than fault prevention and is easier to deploy incrementally.
To show that fault detection is useful and practical, we present NetReview, a fault detection system for the Border Gateway Protocol (BGP). NetReview records BGP routing messages in a tamper-evident log, and it enables ISPs to check each other’s logs against a high-level description of the expected behavior, such as a peering agreement or a set of best practices. At the same time, NetReview respects the ISPs’ privacy and allows them to protect sensitive information. We have implemented and evaluated a prototype of NetReview; our results show that NetReview catches common Internet routing problems, and that its resource requirements are modest.

PDF BibTeX Abstract Slides
CSAR: A Practical and Provable Technique to Make Randomized Systems Accountable. Michael Backes, Peter Druschel, Andreas Haeberlen, and Dominique Unruh. 16th Annual Network & Distributed System Security Symposium (NDSS '09), San Diego, CA, Feb 2009.

× @inproceedings{backes-2009-csar,
  author = {Michael Backes and Peter Druschel and Andreas Haeberlen and Dominique Unruh},
  title = {{CSAR}: {A} Practical and Provable Technique to Make Randomized Systems Accountable},
  booktitle = {16th Annual Network & Distributed System Security Symposium (NDSS '09)},
  location = {San Diego, CA},
  month = feb,
  year = 2009
}

×
We describe CSAR, a novel technique for generating cryptographically strong, accountable randomness. Using CSAR, we can generate a pseudo-random sequence and a proof that the elements of this sequence up to a given point have been correctly generated, while future values in the sequence remain unpredictable. CSAR enables accountability for distributed systems that use randomized protocols. External auditors can check if a node has deviated from its expected behavior without learning anything about the node’s future random choices. In particular, an accountable node does not need to leak secrets that would make its future actions predictable. We demonstrate that CSAR is practical and efficient, and we apply it to implement accountability for a server that uses random sampling for billing purposes.

PDF BibTeX Abstract TR
Detecting BitTorrent Blocking. Marcel Dischinger, Alan Mislove, Andreas Haeberlen, and Krishna P. Gummadi. 8th ACM/USENIX Internet Measurement Conference (IMC '08), Vouliagmeni, Greece, Oct 2008.

× @inproceedings{dischinger-2008-bittorrent,
  author = {Marcel Dischinger and Alan Mislove and Andreas Haeberlen and Krishna P. Gummadi},
  title = {Detecting {BitTorrent} Blocking},
  booktitle = {8th ACM/USENIX Internet Measurement Conference (IMC '08)},
  location = {Vouliagmeni, Greece},
  month = oct,
  year = 2008
}

×
Recently, it has been reported that certain access ISPs are surreptitiously blocking their customers from uploading data using the popular BitTorrent file-sharing protocol. The reports have sparked an intense and wide-ranging policy debate on network neutrality and ISP traffic management practices. However, to date, end users lack access to measurement tools that can detect whether their access ISPs are blocking their BitTorrent traffic. And since ISPs do not voluntarily disclose their traffic management policies, no one knows how widely BitTorrent traffic blocking is deployed in the current Internet. In this paper, we address this problem by designing an easy-to-use tool to detect BitTorrent blocking and by presenting results from a widely used public deployment of the tool.

PDF BibTeX Abstract Software
SatelliteLab: Adding Heterogeneity to Planetary-Scale Network Testbeds. Marcel Dischinger, Andreas Haeberlen, Ivan Beschastnikh, Krishna P. Gummadi, and Stefan Saroiu. 2008 ACM SIGCOMM Conference (SIGCOMM '08), Seattle, WA, Aug 2008.

× @inproceedings{dischinger-2008-satellitelab,
  author = {Marcel Dischinger and Andreas Haeberlen and Ivan Beschastnikh and Krishna P. Gummadi and Stefan Saroiu},
  title = {{SatelliteLab}: {A}dding Heterogeneity to Planetary-Scale Network Testbeds},
  booktitle = {2008 ACM SIGCOMM Conference (SIGCOMM '08)},
  location = {Seattle, WA},
  month = aug,
  year = 2008
}

×
Planetary-scale network testbeds like PlanetLab and RON have become indispensable for evaluating prototypes of distributed systems under realistic Internet conditions. However, current testbeds lack the heterogeneity that characterizes the commercial Internet. For example, most testbed nodes are connected to well-provisioned research networks, whereas most Internet nodes are in edge networks.
In this paper, we present the design, implementation, and evaluation of SatelliteLab, a testbed that includes nodes from a diverse set of Internet edge networks. SatelliteLab has a two-tier architecture, in which well-provisioned nodes called planets form the core, and lightweight nodes called satellites connect to the planets from the periphery. The application code of an experiment runs on the planets, whereas the satellites only forward network traffic. Thus, the traffic is subjected to the network conditions of the satellites, which greatly improves the testbed’s network heterogeneity. The separation of code execution and traffic forwarding enables satellites to remain lightweight, which lowers the barrier to entry for Internet edge nodes.
Our prototype of SatelliteLab uses PlanetLab nodes as planets and a set of 32 volunteered satellites with diverse network characteristics. These satellites consist of desktops, laptops, and handhelds connected to the Internet via cable, DSL, ISDN, Wi-Fi, Bluetooth, and cellular links. We evaluate SatelliteLab’s design, and we demonstrate the benefits of evaluating applications on SatelliteLab.

PDF BibTeX Abstract Slides Software
PeerReview: Practical Accountability for Distributed Systems. Andreas Haeberlen, Petr Kuznetsov, and Peter Druschel. 21st ACM Symposium on Operating Systems Principles (SOSP '07), Stevenson, WA, Oct 2007.

× @inproceedings{haeberlen-2007-peerreview,
  author = {Andreas Haeberlen and Petr Kuznetsov and Peter Druschel},
  title = {{PeerReview}: {P}ractical Accountability for Distributed Systems},
  booktitle = {21st ACM Symposium on Operating Systems Principles (SOSP '07)},
  location = {Stevenson, WA},
  month = oct,
  year = 2007
}

×
We describe PeerReview, a system that provides accountability in distributed systems. PeerReview ensures that Byzantine faults whose effects are observed by a correct node are eventually detected and irrefutably linked to a faulty node. At the same time, PeerReview ensures that a correct node can always defend itself against false accusations. These guarantees are particularly important for systems that span multiple administrative domains, which may not trust each other.
PeerReview works by maintaining a secure record of the messages sent and received by each node. The record isused to automatically detect when a node's behavior deviates from that of a given reference implementation, thus exposing faulty nodes. PeerReview is widely applicable: it only requires that a correct node's actions are deterministic, that nodes can sign messages, and that each node is periodically checked by a correct node. We demonstrate that PeerReview is practical by applying it to three different types of distributed systems: a network filesystem, a peer-to-peer system, and an overlay multicast system.

PDF BibTeX Abstract Slides TR Software
Characterizing Residential Broadband Networks. Marcel Dischinger, Andreas Haeberlen, Krishna P. Gummadi, and Stefan Saroiu. 7th ACM/USENIX Internet Measurement Conference (IMC '07), San Diego, CA, Oct 2007.

× @inproceedings{dischinger-2007-broadband,
  author = {Marcel Dischinger and Andreas Haeberlen and Krishna P. Gummadi and Stefan Saroiu},
  title = {Characterizing Residential Broadband Networks},
  booktitle = {7th ACM/USENIX Internet Measurement Conference (IMC '07)},
  location = {San Diego, CA},
  month = oct,
  year = 2007
}

×
A large and rapidly growing proportion of users connect to the Internet via residential broadband networks such as Digital Subscriber Lines (DSL) and cable. Residential networks are often the bottleneck in the last mile of today’s Internet. Their characteristics critically affect Internet applications, including voice-over-IP, online games, and peer-to-peer content sharing/delivery systems. However, to date, few studies have investigated commercial broadband deployments, and rigorous measurement data that characterize these networks at scale are lacking.
In this paper, we present the first large-scale measurement study of major cable and DSL providers in North America and Europe. We describe and evaluate the measurement tools we developed for this purpose. Our study characterizes several properties of broadband networks, including link capacities, packet round-trip times and jitter, packet loss rates, queue lengths, and queue drop policies. Our analysis reveals important ways in which residential networks differ from how the Internet is conventionally thought to operate. We also discuss the implications of our findings for many emerging protocols and systems, including delay-based congestion control (e.g., PCP) and network coordinate systems (e.g., Vivaldi).

PDF BibTeX Abstract Data and tools
Monarch: A Tool to Emulate Transport Protocol Flows over the Internet at Large. Andreas Haeberlen, Marcel Dischinger, Krishna P. Gummadi, and Stefan Saroiu. 6th ACM/USENIX Internet Measurement Conference (IMC '06), Rio de Janeiro, Brazil, Oct 2006.

× @inproceedings{haeberlen-2006-monarch,
  author = {Andreas Haeberlen and Marcel Dischinger and Krishna P. Gummadi and Stefan Saroiu},
  title = {Monarch: {A} Tool to Emulate Transport Protocol Flows over the {I}nternet at Large},
  booktitle = {6th ACM/USENIX Internet Measurement Conference (IMC '06)},
  location = {Rio de Janeiro, Brazil},
  month = oct,
  year = 2006
}

×
This paper proposes Monarch, a novel tool that accurately emulates transport protocol flows from an end host controlled by its user to any other Internet host that responds to simple TCP, UDP, or ICMP packet probes. Since many Internet hosts and routers respond to such probes, Monarch can evaluate transport protocols, such as TCP Reno, TCP Vegas, and TCP Nice, over a large and diverse set of Internet paths. Current approaches to evaluating these protocols need control over both end hosts of an Internet path. Consequently, they are limited to a small number of paths between nodes in testbeds like PlanetLab, RON or NIMI. Monarch's ability to evaluate transport protocols with minimal support from the destination host enables many new measurement studies. We show the feasibility of using Monarch for three example studies: (a)understanding transport protocol behavior over network paths that are less explored by the research community, such as paths to cable and DSL hosts, (b) investigating the relative performance of different transport protocol designs, such as TCP Vegas and TCP Reno, and (c) testing protocol implementations under a wide range of experimental conditions.

PDF BibTeX Abstract Slides Software Dataset
Efficient Replica Maintenance for Distributed Storage Systems. Byung-Gon Chun, Frank Dabek, Andreas Haeberlen, Emil Sit, Hakim Weatherspoon, M. Frans Kaashoek, John Kubiatowicz, and Robert Morris. 3rd Symposium on Networked Systems Design and Implementation (NSDI '06), San Jose, CA, May 2006.

× @inproceedings{chun-2006-maintenance,
  author = {Byung-Gon Chun and Frank Dabek and Andreas Haeberlen and Emil Sit and Hakim Weatherspoon and M. Frans Kaashoek and John Kubiatowicz and Robert Morris},
  title = {Efficient Replica Maintenance for Distributed Storage Systems},
  booktitle = {3rd Symposium on Networked Systems Design and Implementation (NSDI '06)},
  location = {San Jose, CA},
  month = may,
  year = 2006
}

×
This paper considers replication strategies for storage systems that aggregate the disks of many nodes spread over the Internet. Maintaining replication in such systems can be prohibitively expensive, since every transient network or host failure could potentially lead to copying a server's worth of data over the Internet to maintain replication levels.
The following insights in designing an efficient replication algorithm emerge from the paper's analysis. First, durability can be provided separately from availability; the former is less expensive to ensure and a more useful goal for many wide-area applications. Second, the focus of a durability algorithm must be to create new copies of data objects faster than permanent disk failures destroy the objects; careful choice of policies for what nodes should hold what data can decrease repair time. Third, increasing the number of replicas of each data object does not help a system tolerate a higher disk failure probability, but does help tolerate bursts of failures. Finally, ensuring that the system makes use of replicas that recover after temporary failure is critical to efficiency.
Based on these insights, the paper proposes the Carbonite replication algorithm for keeping data durable at a low cost. A simulation of Carbonite storing 1 TB of data over a 365 day trace of PlanetLab activity shows that Carbonite is able to keep all data durable and uses 44% more network traffic than a hypothetical system that only responds to permanent failures. In comparison, Total Recall and DHash require almost a factor of two more network traffic than this hypothetical system.

PDF BibTeX Abstract
Experiences in Building and Operating ePOST, a Reliable Peer-to-Peer Application. Alan Mislove, Ansley Post, Andreas Haeberlen, and Peter Druschel. 1st European Conference on Computer Systems (EuroSys '06), Leuven, Belgium, Apr 2006.

× @inproceedings{mislove-2006-epost,
  author = {Alan Mislove and Ansley Post and Andreas Haeberlen and Peter Druschel},
  title = {Experiences in Building and Operating {ePOST}, a Reliable Peer-to-Peer Application},
  booktitle = {1st European Conference on Computer Systems (EuroSys '06)},
  location = {Leuven, Belgium},
  month = apr,
  year = 2006
}

×
Peer-to-peer (p2p) technology can potentially be used to build highly reliable applications without a single point of failure. However, most of the existing applications, such as file sharing or web caching, have only moderate reliability demands. Without a challenging proving ground, it remains unclear whether the full potential of p2p systems can be realized.
To provide such a proving ground, we have designed, deployed and operated a p2p-based email system. We chose email because users depend on it for their daily work and therefore place high demands on the availability and reliability of the service, as well as the durability, integrity, authenticity and privacy of their email. Our system, ePOST, has been actively used by a small group of participants for over two years.
In this paper, we report the problems and pitfalls we encountered in this process. We were able to address some of them by applying known principles of system design, while others turned out to be novel and fundamental, requiring us to devise new solutions. Our findings can be used to guide the design of future reliable p2p systems and provide interesting new directions for future research.

PDF BibTeX Abstract
Glacier: Highly durable, decentralized storage despite massive correlated failures. Andreas Haeberlen, Alan Mislove, and Peter Druschel. nd Symposium on Networked Systems Design and Implementation (NSDI '05), Boston, MA, May 2005.

× @inproceedings{haeberlen-2005-glacier,
  author = {Andreas Haeberlen and Alan Mislove and Peter Druschel},
  title = {Glacier: {H}ighly durable, decentralized storage despite massive correlated failures},
  booktitle = {nd Symposium on Networked Systems Design and Implementation (NSDI '05)},
  location = {Boston, MA},
  month = may,
  year = 2005
}

×
Decentralized storage systems aggregate the available disk space of participating computers to provide a large storage facility. These systems rely on data redundancy to ensure durable storage despite of node failures. However, existing systems either assume independent node failures, or they rely on introspection to carefully place redundant data on nodes with low expected failure correlation. Unfortunately, node failures are not independent in practice and constructing an accurate failure model is difficult in large-scale systems. At the same time, malicious worms that propagate through the Internet pose a real threat of large-scale correlated failures. Such rare but potentially catastrophic failures must be considered when attempting to provide highly durable storage.
In this paper, we describe Glacier, a distributed storage system that relies on massive redundancy to mask the effect of large-scale correlated failures. Glacier is designed to aggressively minimize the cost of this redundancy in space and time: Erasure coding and garbage collection reduces the storage cost; aggregation of small objects and a loosely coupled maintenance protocol for redundant fragments minimizes the messaging cost. In one configuration, for instance, our system can provide six-nines durable storage despite correlated failures of up to 60% of the storage nodes, at the cost of an eleven-fold storage overhead and an average messaging overhead of only 4 messages per node and minute during normal operation. Glacier is used as the storage layer for an experimental serverless email system.

PDF BibTeX Abstract Slides Software
Practical Robust Localization over Large-Scale 802.11 Wireless Networks. Andreas Haeberlen, Eliot Flannery, Andrew M. Ladd, Algis Rudys, Dan S. Wallach, and Lydia E. Kavraki. 10th ACM International Conference on Mobile Computing and Networking (MOBICOM '04), Philadelphia, PA, Sep 2004.

× @inproceedings{haeberlen-2004-localization,
  author = {Andreas Haeberlen and Eliot Flannery and Andrew M. Ladd and Algis Rudys and Dan S. Wallach and Lydia E. Kavraki},
  title = {Practical Robust Localization over Large-Scale 802.11 Wireless Networks},
  booktitle = {10th ACM International Conference on Mobile Computing and Networking (MOBICOM '04)},
  location = {Philadelphia, PA},
  month = sep,
  year = 2004
}

× We demonstrate a system built using probabilistic techniques that allows for remarkably accurate localization across our entire office building using nothing more than the built-in signal intensity meter supplied by standard 802.11 cards. While prior systems have required significant investments of human labor to build a detailed signal map, we can train our system by spending less than one minute per office or region, walking around with a laptop and recording the observed signal intensities of our building's unmodified base stations. We actually collected over two minutes of data per office or region, about 28 man-hours of effort. Using less than half of this data to train the localizer, we can localize a user to the precise, correct location in over 95% of our attempts, across the entire building. Even in the most pathological cases, we almost never localize a user any more distant than to the neighboring office. A user can obtain this level of accuracy with only two or three signal intensity measurements, allowing for a high frame rate of localization results. Furthermore, with a brief calibration period, our system can be adapted to work with previously unknown user hardware. We present results demonstrating the robustness of our system against a variety of untrained time-varying phenomena, including the presence or absence of people in the building across the day. Our system is sufficiently robust to enable a variety of location-aware applications without requiring special-purpose hardware or complicated training and calibration procedures.

PDF BibTeX Abstract Slides Video Software Dataset
User-level Management of Kernel Memory. Andreas Haeberlen and Kevin Elphinstone. 8th Asia-Pacific Computer Systems Architecture Conference (ACSAC '03), Aizu-Wakamatsu City, Japan, Sep 2003.

× @inproceedings{haeberlen-2003-kmem,
  author = {Andreas Haeberlen and Kevin Elphinstone},
  title = {User-level Management of Kernel Memory},
  booktitle = {8th Asia-Pacific Computer Systems Architecture Conference (ACSAC '03)},
  location = {Aizu-Wakamatsu City, Japan},
  month = sep,
  year = 2003
}

×
Kernel memory is a resource that must be managed carefully in order to ensure the efficiency and safety of the system. The useof an inappropriate management policy can weaken the isolation between subsystems, lead to suboptimal performance, and even make the kernel vulnerable to denial-of-service attacks. Yet, many existing kernels use only a single built-in policy, which is always a compromise between performance and generality.
In this paper, we address this problem by exporting control over kernel memory to user-level pagers. Thus, subsystems can implement their own application-specific management policies while independent subsystems can still be isolated from each other.
The pagers have full control over the memory resources they manage; they can even preempt and later restore individual pages of kernel memory. Still, protection is not compromised because the kernel converts its metadata into a safe representation before exporting it. Therefore, pagers need only be trusted by their respective clients.
We describe the model we use to page kernel memory and various techniques for obtaining a safe external representation for kernel metadata. We also report experiences with an experimental kernel that implements our scheme and outline our plans to further develop the approach.

PDF BibTeX Abstract

Workshop papers

The Synchronous Data Center. Tian Yang, Robert Gifford, Andreas Haeberlen, and Linh Thi Xuan Phan. 17th Workshop on Hot Topics in Operating Systems (HotOS '19), Bertinoro, Italy, May 2019.

× @inproceedings{yang-2019-sync,
  author = {Tian Yang and Robert Gifford and Andreas Haeberlen and Linh Thi Xuan Phan},
  title = {The Synchronous Data Center},
  booktitle = {17th Workshop on Hot Topics in Operating Systems (HotOS '19)},
  location = {Bertinoro, Italy},
  month = may,
  year = 2019
}

×
Today, distributed systems are typically designed to be largely asynchronous. Designers assume that the network can drop or significantly delay messages at unpredictable times, that there is no way to know how quickly a node might process a message, or how soon it might respond, and that the clocks of different nodes are at most loosely synchronized. These assumptions are certainly safe, but they come at a price: many applications really do need predictable performance, which, on top of an asynchronous system, has to be approximated at great cost and with lots of redundancy, and many distributed protocols for asynchronous systems are much more complex and expensive than their synchronous counterparts.
The goal of this paper is to start a discussion about whether the asynchronous model is (still) the right choice for most distributed systems, especially ones that belong to a single administrative domain. We argue that 1) by using ideas from the CPS domain, it is technically feasible to build datacenter-scale systems that are fully synchronous, and that 2) such systems would have several interesting advantages over current designs.

PDF BibTeX Abstract Slides
Using Differential Privacy to Efficiently Mitigate Side Channels in Distributed Analytics. Min Xu, Antonis Papadimitriou, Ariel Feldman, and Andreas Haeberlen. 11th European Workshop on Systems Security (EuroSec '18), Porto, Portugal, Apr 2018.

× @inproceedings{xu-2018-hermetic,
  author = {Min Xu and Antonis Papadimitriou and Ariel Feldman and Andreas Haeberlen},
  title = {Using Differential Privacy to Efficiently Mitigate Side Channels in Distributed Analytics},
  booktitle = {11th European Workshop on Systems Security (EuroSec '18)},
  location = {Porto, Portugal},
  month = apr,
  year = 2018
}

×
Distributed analytics systems enable users to efficiently perform computations over large distributed data sets. Recently, systems have been proposed that can additionally protect the data’s privacy by keeping it encrypted even in memory and by performing the computations using trusted execution environments (TEEs). This approach has the potential to make it much safer to outsource analytics jobs to an untrusted cloud platform or to distribute it across multiple parties. TEEs, however, suffer from side channels, such as timing, memory access patterns, and message sizes that weaken their privacy guarantees. Existing privacy-preserving analytics systems only address a subset of these channels, such as memory access patterns, while largely neglecting size and timing. Moreover, previous attempts to close size and timing channels suffer from high performance costs, impracticality, or a lack of rigorous privacy guarantees.
In this paper, we present an approach to mitigating timing and size side channels in analytics based on differential privacy that is both dramatically more efficient than the state-of-the-art while offering principled privacy assurances. We also sketch a design for a new analytics system we are developing called Hermetic that aims to be the first to mitigate the four most critical digital side channels simultaneously. Our preliminary evaluation demonstrates the potential benefits of our method.

PDF BibTeX Abstract
Dispersing Asymmetric DDoS Attacks with SplitStack. Ang Chen, Akshay Sriraman, Tavish Vaidya, Yuankai Zhang, Andreas Haeberlen, Boon Thau Loo, Linh Thi Xuan Phan, Micah Sherr, Clay Shields, and Wenchao Zhou. 15th ACM Workshop on Hot Topics in Networks (HotNets '16), Atlanta, GA, Nov 2016.

× @inproceedings{chen-2016-splitstack,
  author = {Ang Chen and Akshay Sriraman and Tavish Vaidya and Yuankai Zhang and Andreas Haeberlen and Boon Thau Loo and Linh Thi Xuan Phan and Micah Sherr and Clay Shields and Wenchao Zhou},
  title = {Dispersing Asymmetric {DDoS} Attacks with {SplitStack}},
  booktitle = {15th ACM Workshop on Hot Topics in Networks (HotNets '16)},
  location = {Atlanta, GA},
  month = nov,
  year = 2016
}

×
This paper presents SplitStack, an architecture targeted at mitigating asymmetric DDoS attacks. These attacks are particularly challenging, since attackers can use a limited amount of resources to trigger exhaustion of a particular type of system resource on the server side. SplitStack resolves this by splitting the monolithic stack into many separable components called minimum splittable units (MSUs). If part of the application stack is experiencing a DDoS attack, SplitStack massively replicates just the affected MSUs, potentially across many machines. This allows scaling of the impacted resource separately from the rest of the application stack, so that resources can be precisely added where needed to combat the attack. We validate SplitStack via a preliminary case study, and show that it outperforms naive replication in defending against asymmetric attacks.

PDF BibTeX Abstract Ang's slides
Cloud-Based Secure Logger for Medical Devices. Hung Nguyen, Bipeen Acharya, Radoslav Ivanov, Andreas Haeberlen, Linh Thi Xuan Phan, Oleg Sokolsky, Jesse Walker, James Weimer, William Hanson, and Insup Lee. 1st Workshop on Security, Privacy, and Trustworthiness in Medical Cyber Physical Systems (MedSPT '16), Washington, DC, Jun 2016.

× @inproceedings{nguyen-2016-logger,
  author = {Hung Nguyen and Bipeen Acharya and Radoslav Ivanov and Andreas Haeberlen and Linh Thi Xuan Phan and Oleg Sokolsky and Jesse Walker and James Weimer and William Hanson and Insup Lee},
  title = {Cloud-Based Secure Logger for Medical Devices},
  booktitle = {1st Workshop on Security, Privacy, and Trustworthiness in Medical Cyber Physical Systems (MedSPT '16)},
  location = {Washington, DC},
  month = jun,
  year = 2016
}

×
A logger in the cloud capable of keeping a secure, time-synchronized and tamper-evident log of medical device and patient information allows efficient forensic analysis in cases of adverse events or attacks on interoperable medical devices. A secure logger as such must meet requirements of confidentiality and integrity of message logs and provide tamper-detection and tamper-evidence. In this paper, we propose a design for such a cloud-based secure logger using the Intel Software Guard Extensions (SGX) and the Trusted Platform Module (TPM). The proposed logger receives medical device information from a dongle attached to a medical device. The logger relies on SGX, TPM and standard encryption to maintain a secure communication channel even on an untrusted network and operating system. We also show that the logger is resilient against different kinds of attacks such as Replay attacks, Injection attacks and Eavesdropping attacks.

BibTeX Abstract
Differential Provenance: Better Network Diagnostics with Reference Events. Ang Chen, Yang Wu, Andreas Haeberlen, Wenchao Zhou, and Boon Thau Loo. 14th ACM Workshop on Hot Topics in Networks (HotNets '15), Philadelphia, PA, Nov 2015.

× @inproceedings{chen-2015-diffprov,
  author = {Ang Chen and Yang Wu and Andreas Haeberlen and Wenchao Zhou and Boon Thau Loo},
  title = {Differential Provenance: Better Network Diagnostics with Reference Events},
  booktitle = {14th ACM Workshop on Hot Topics in Networks (HotNets '15)},
  location = {Philadelphia, PA},
  month = nov,
  year = 2015
}

×
In this paper, we propose a new approach to diagnosing problems in complex networks. Our approach is based on the insight that many of the trickiest problems are anomalies – they affect only a small fraction of the traffic (e.g., perhaps a certain subnet), or they only manifest infrequently. Thus, it is quite common for the network operator to have "examples" of both working and non-working traffic readily available – perhaps a packet that was misrouted, and a similar packet that was routed correctly. In this case, the cause of the problem is likely to be wherever the two packets were treated differently by the network.
We sketch the design of a network debugger that can leverage this information using a novel concept that we call differential provenance. Like classical provenance, differential provenance tracks the causal connections between network and configuration states and the packets that were affected by them; however, it can additionally reason about the causes of any discrepancies between different provenances. We have performed a case study in the context of software-defined networks, and our initial results are encouraging: they suggest that differential provenance can often identify the root cause of even very subtle network issues.

PDF BibTeX Abstract Ang's slides
Automated Network Repair with Meta Provenance. Yang Wu, Ang Chen, Andreas Haeberlen, Wenchao Zhou, and Boon Thau Loo. 14th ACM Workshop on Hot Topics in Networks (HotNets '15), Philadelphia, PA, Nov 2015.

× @inproceedings{wu-2015-metaprov,
  author = {Yang Wu and Ang Chen and Andreas Haeberlen and Wenchao Zhou and Boon Thau Loo},
  title = {Automated Network Repair with Meta Provenance},
  booktitle = {14th ACM Workshop on Hot Topics in Networks (HotNets '15)},
  location = {Philadelphia, PA},
  month = nov,
  year = 2015
}

×
When debugging an SDN application, diagnosing the problem is merely the first step – the operator must still implement a solution that works, and that does not cause new problems elsewhere. However, most existing SDN debuggers focus exclusively on identifying the problem and offer the network operator little or no help with finding an effective fix. Finding a fix is challenging because the number of potential repairs can be enormous.
In this paper, we propose a first step towards automated repair for SDN applications. Our approach consists of two elements. The first is a data structure we call meta provenance, which can be used to efficiently find good candidate repairs. Meta provenance is inspired by the provenance concept from the database community. However, whereas standard provenance can only reason about changes to data, meta-provenance can also reason about changes to programs. The second element is a system that can efficiently back-test a set of candidate repairs using historical data from the network. This is used to eliminate candidate repairs that do not work well, or that cause other problems. We present initial results from a case study, which suggest our approach is able to efficiently find high-quality repairs.

PDF BibTeX Abstract Yang's slides
PRISM: Private Retrieval of the Internet's Sensitive Metadata. Ang Chen and Andreas Haeberlen. 8th Workshop on Cyber Security Experimentation and Test (CSET '15), Washington, DC, Aug 2015.

× @inproceedings{chen-2015-prism,
  author = {Ang Chen and Andreas Haeberlen},
  title = {{PRISM}: {P}rivate Retrieval of the {I}nternet's Sensitive Metadata},
  booktitle = {8th Workshop on Cyber Security Experimentation and Test (CSET '15)},
  location = {Washington, DC},
  month = aug,
  year = 2015
}

×
The Internet is producing a wealth of data about its own operation, in the form of NetFlow records, routing table entries, traffic statistics, etc. Several previous works – including, for instance, Clark's "knowledge plane" – have considered the idea of building a giant distributed database that (at least conceptually) contains all of this information. Such a database could have many attractive uses, including distributed troubleshooting, attack mitigation, or traffic management. However, so far the idea has not been realized, and it is likely that privacy concerns have played a role.
In this paper, we ask whether differential privacy could provide the strong privacy guarantees that would be needed to put this idea into practice. We discuss some key concerns that have been raised about differential privacy, such as its limited scalability and its finite "privacy budget", and we point out several characteristics of the Internet that could mitigate these concerns. We also sketch the design of PRISM, a system for differentially private queries on NetFlow records that could form the basis of a potential "knowledge plane".

PDF BibTeX Abstract
Fault Tolerance and the Five-Second Rule. Ang Chen, Hanjun Xiao, Andreas Haeberlen, and Linh Thi Xuan Phan. 15th Workshop on Hot Topics in Operating Systems (HotOS XV), Kartause Ittingen, Switzerland, May 2015.

× @inproceedings{chen-2015-btr,
  author = {Ang Chen and Hanjun Xiao and Andreas Haeberlen and Linh Thi Xuan Phan},
  title = {Fault Tolerance and the Five-Second Rule},
  booktitle = {15th Workshop on Hot Topics in Operating Systems (HotOS XV)},
  location = {Kartause Ittingen, Switzerland},
  month = may,
  year = 2015
}

×
We propose a new approach to fault tolerance that we call bounded-time recovery (BTR). BTR is intended for systems that need strong timeliness guarantees during normal operation but can tolerate short outages in an emergency, e.g., when they are under attack. We argue that BTR could be a good fit for many cyber-physical systems. We also sketch a technical approach to providing BTR, and we discuss some challenges that still remain.

PDF BibTeX Abstract Slides
Compute Globally, Act Locally: Protecting Federated Systems from Systemic Threats. Arjun Narayan, Antonis Papadimitriou, and Andreas Haeberlen. 10th Workshop on Hot Topics in System Dependability (HotDep '14), Broomfield, CO, Oct 2014.

× @inproceedings{narayan-2014-systemic,
  author = {Arjun Narayan and Antonis Papadimitriou and Andreas Haeberlen},
  title = {Compute Globally, Act Locally: {P}rotecting Federated Systems from Systemic Threats},
  booktitle = {10th Workshop on Hot Topics in System Dependability (HotDep '14)},
  location = {Broomfield, CO},
  month = oct,
  year = 2014
}

×
Building dependable federated systems is often complicated by privacy concerns: if the domains are not willing to share information with each other, a global or 'systemic' threat may not be detected until it is too late. In this paper, we study this problem using a somewhat unusual example: the financial crisis of 2008. Based on results from the economics literature, we argue that a) the impending crisis could have been predicted by performing a specific distributed computation on the financial information of each bank, but that b) existing tools, such as secure multiparty computation, do not offer enough privacy to make participation safe from the banks' perspective. We then sketch the design of a system that can perform this (and possibly other) computation at scale with strong privacy guarantees. Results from an early prototype suggest that the computation and communication costs are reasonable.

PDF BibTeX Abstract Arjun's slides
Let SDN be your eyes: Secure Forensics in Data Center Networks. Adam Bates, Kevin Butler, Andreas Haeberlen, Micah Sherr, and Wenchao Zhou. NDSS Workshop on Security of Emerging Network Technologies (SENT '14), San Diego, CA, Feb 2014.

× @inproceedings{bates-2014-forensics,
  author = {Adam Bates and Kevin Butler and Andreas Haeberlen and Micah Sherr and Wenchao Zhou},
  title = {Let {SDN} be your eyes: {S}ecure Forensics in Data Center Networks},
  booktitle = {NDSS Workshop on Security of Emerging Network Technologies (SENT '14)},
  location = {San Diego, CA},
  month = feb,
  year = 2014
}

×
Discovering the causes of incorrect behavior in large networks is often difficult. This difficulty is compounded when some machines in the network are compromised, since these compromised machines may use deception or tamper with data to frustrate forensic analysis. Recently proposed forensic tools enable administrators to learn the causes of some system states in a partially compromised network, but these tools are inherently unable to (1) observe covert communication between compromised nodes or (2) detect attempts to exfiltrate sensitive data.
In this paper, we observe that the emergence of Software-Defined Networking (SDN) offers interesting new opportunities for network forensics. We sketch the design of an SDN-based forensic system that can be used to investigate a wide variety of faults in data center networks, including previously unobservable attacks such as data exfiltration and collusion between compromised nodes. Our key insight is that the network itself can be used as a point of observation, which gives us a holistic view of network activity. We show that a collection of lightweight middleboxes would be sufficient to support this functionality, and we discuss several additional challenges and opportunities for SDN-based forensic tools.

PDF BibTeX Abstract
Towards Privacy-Preserving Fault Detection. Antonis Papadimitriou, Mingchen Zhao, and Andreas Haeberlen. 9th Workshop on Hot Topics in Dependable Systems (HotDep '13), Farmington, PA, Nov 2013.

× @inproceedings{papadimitriou-2013-privacy,
  author = {Antonis Papadimitriou and Mingchen Zhao and Andreas Haeberlen},
  title = {Towards Privacy-Preserving Fault Detection},
  booktitle = {9th Workshop on Hot Topics in Dependable Systems (HotDep '13)},
  location = {Farmington, PA},
  month = nov,
  year = 2013
}

×
In this paper, we discuss the problem of detecting general faults in distributed systems that handle confidential information. Detecting non-crash faults is difficult in this setting because, to check the behavior of a given node, we need to know its expected behavior – but that can depend on the confidential information. Classical zero-knowledge proofs are difficult to apply because they are designed to verify functions with a fixed number of inputs, but in many distributed systems, both the size and the number of a node’s "inputs" (the messages it has received from other nodes) are not known.
We propose an approach that can efficiently provide zero-knowledge fault detection for certain systems. Our approach spreads the detection tasks across multiple nodes, leverag-ing a node’s existing knowledge whenever possible. We use epistemic reasoning to infer such knowledge, and we combine classical zero-knowledge proofs with a special data structure to handle inputs of unknown size. We show how our approach can be applied to a simple example system, and we report some initial performance measurements.

PDF BibTeX Abstract
Answering Why-Not Queries in Software-Defined Networks with Negative Provenance. Yang Wu, Andreas Haeberlen, Wenchao Zhou, and Boon Thau Loo. 12th ACM Workshop on Hot Topics in Networks (HotNets-XII), College Park, MD, Nov 2013.

× @inproceedings{wu-2013-negative-provenance,
  author = {Yang Wu and Andreas Haeberlen and Wenchao Zhou and Boon Thau Loo},
  title = {Answering Why-Not Queries in Software-Defined Networks with Negative Provenance},
  booktitle = {12th ACM Workshop on Hot Topics in Networks (HotNets-XII)},
  location = {College Park, MD},
  month = nov,
  year = 2013
}

×
When debugging an SDN, it is sometimes necessary to explain the absence of an event: why a certain rule was not installed, or why a certain packet did not arrive. Existing SDN debuggers offer some support for explaining the presence of events, usually by providing the equivalent of a "backtrace" in conventional debuggers, but they are not very good at answering "Why not?" questions: there is simply no starting point for a possible backtrace.
In this paper, we show that the concept of negative provenance can be used to explain the absence of events in SDNs. Negative provenance relies on counterfactual reasoning to identify the conditions under which the missing event could have occurred. We outline a simple technique that can track negative provenance in SDNs, and we present a case study to illustrate how our technique can be used to answer concrete "Why not?" questions. Using our approach, it should be possible to build SDN debuggers that can explain both the presence and the absence of events.

PDF BibTeX Abstract
Sensitivity analysis using type-based constraints. Loris D'Antoni, Marco Gaboardi, Emilio Jesus Gallego Arias, Andreas Haeberlen, and Benjamin C. Pierce. 1st Workshop on Functional Programming Concepts in Domain-Specific Languages (FPCDSL '13), Boston, MA, Sep 2013.

× @inproceedings{dantoni-2013-sensitivity,
  author = {Loris D'Antoni and Marco Gaboardi and Emilio Jesus Gallego Arias and Andreas Haeberlen and Benjamin C. Pierce},
  title = {Sensitivity analysis using type-based constraints},
  booktitle = {1st Workshop on Functional Programming Concepts in Domain-Specific Languages (FPCDSL '13)},
  location = {Boston, MA},
  month = sep,
  year = 2013
}

×
Function sensitivity – how much the result of a function can change with respect to linear changes in the input – is a key concept in many research areas. For instance, in differential privacy, one of the most common mechanisms for turning a (possibly privacy-leaking) query into a differentially private one involves establishing a boundon its sensitivity.
One approach to sensitivity analysis is to use a type-based approach, extending the Hindley-Milner type system with functional types capturing statically the sensitivity of a functional expression. This approach – based on affine logic – has been used in Fuzz, a language for differentially private queries.
We describe an automatic typed-based analysis that infers and checks the sensitivity annotations for simple functional programs. We have implemented a prototype in Fuzz's compiler. The first component of the analysis extends the typechecker to generate nonlinear constraints over the positive real numbers extended with infinity, which are then checked by the Z3 SMT solver; a solution for them will provide an upper bound on the sensitivity annotations and ensure the correctness of the annotations. We also present a simple sensitivity minimization procedure and demonstrate the effectiveness of the approach by analyzing several examples.

PDF BibTeX Abstract
Querying Provenance for Ranking and Recommending. Zachary G. Ives, Andreas Haeberlen, Tao Feng, and Wolfgang Gatterbauer. 4th USENIX Workshop on the Theory and Practice of Provenance (TaPP '12), Boston, MA, Jun 2012.

× @inproceedings{ives-2012-querying,
  author = {Zachary G. Ives and Andreas Haeberlen and Tao Feng and Wolfgang Gatterbauer},
  title = {Querying Provenance for Ranking and Recommending},
  booktitle = {4th USENIX Workshop on the Theory and Practice of Provenance (TaPP '12)},
  location = {Boston, MA},
  month = jun,
  year = 2012
}

PDF BibTeX
Having your Cake and Eating it too: Routing Security with Privacy Protections. Alexander J. T. Gurney, Andreas Haeberlen, Wenchao Zhou, Micah Sherr, and Boon Thau Loo. 10th ACM Workshop on Hot Topics in Networks (HotNets-X), Cambridge, MA, Nov 2011.

× @inproceedings{gurney-2011-pvr,
  author = {Alexander J. T. Gurney and Andreas Haeberlen and Wenchao Zhou and Micah Sherr and Boon Thau Loo},
  title = {Having your Cake and Eating it too: Routing Security with Privacy Protections},
  booktitle = {10th ACM Workshop on Hot Topics in Networks (HotNets-X)},
  location = {Cambridge, MA},
  month = nov,
  year = 2011
}

×
Internet Service Providers typically do not reveal details of their interdomain routing policies due to security concerns, or for commercial or legal reasons. As a result, it is difficult to hold ISPs accountable for their contractual agreements. Existing solutions can check basic properties, e.g., whether route announcements correspond to valid routes, but they do not verify how these routes were chosen. In essence, today’s Internet forces us to choose between per-AS privacy and verifiability.
In this paper, we argue that making this difficult tradeoff is unnecessary. We propose private and verifiable routing (PVR), a technique that enables ISPs to check whether their neighbors are fulfilling their contractual promises to them, and to obtain evidence of any violations, without disclosing information that the routing protocol does not already reveal. As initial evidence that PVR is feasible, we sketch a PVR system that can verify some simple BGP policies. We conclude by highlighting several research challenges as futurework.

PDF BibTeX Abstract Slides
Challenges in Experimenting with Botnet Detection Systems. Adam J. Aviv and Andreas Haeberlen. 4th USENIX Workshop on Cyber Security Experimentation and Test (CSET '11), San Francisco, CA, Aug 2011.

× @inproceedings{aviv-2011-botnets,
  author = {Adam J. Aviv and Andreas Haeberlen},
  title = {Challenges in Experimenting with Botnet Detection Systems},
  booktitle = {4th USENIX Workshop on Cyber Security Experimentation and Test (CSET '11)},
  location = {San Francisco, CA},
  month = aug,
  year = 2011
}

×
In this paper, we examine the challenges faced when evaluating botnet detection systems. Many of these challenges stem from difficulties in obtaining and sharing diverse sets of real network traces, as well as determining a botnet ground truth in such traces. On the one hand, there are good reasons why network traces should not be shared freely, such as privacy concerns, but on the other hand, the resulting data scarcity complicates quantitative comparisons to other work and conducting independently repeatable experiments.
These challenges are similar to those faced by researchers studying large-scale distributed systems onlya few years ago, and researchers were able to overcome many of the challenges by collaborating to create a global testbed, namely PlanetLab. We speculate that a similar system for botnet detection research could help overcome the challenges in this domain, and we briefly discuss the associated research directions.

PDF BibTeX Abstract
Towards Self-Explaining Networks. Wenchao Zhou, Qiong Fei, Andreas Haeberlen, Boon Thau Loo, and Micah Sherr. NEBULA Workshop, Philadelphia, PA, Jun 2011.

× @inproceedings{zhou-2011-selfexplaining,
  author = {Wenchao Zhou and Qiong Fei and Andreas Haeberlen and Boon Thau Loo and Micah Sherr},
  title = {Towards Self-Explaining Networks},
  booktitle = {NEBULA Workshop},
  location = {Philadelphia, PA},
  month = jun,
  year = 2011
}

×
In this paper, we argue that networks should be able to explain to their operators why they are in a certain state, even if – and particularly if – they have been compromised by an attacker. Such a capability would be useful in forensic investigations, where an operator observes an unexpected state and must decide whether it is benign or an indication that the system has been compromised. Using a very pessimistic threat model inwhich a malicious adversary can completely compromise an arbitrary subset of the nodes in the network, we argue that we cannot expect to get a complete and correct explanation in all possible cases. However, we also show that, based on recent advances in the systems and the database communities, it seems possible to get as lightly weaker guarantee: for any state change that directly or indirectly affects a correct node, we can either obtain a correct explanation or eventually identify at least one compromised node. We discuss the challenges involved in building systems that provide this property, and we report initial results from an early prototype.

PDF BibTeX Abstract
TAP: Time-aware Provenance for Distributed Systems. Wenchao Zhou, Ling Ding, Andreas Haeberlen, Zachary Ives, and Boon Thau Loo. 3rd USENIX Workshop on the Theory and Practice of Provenance (TaPP '11), Heraklion, Greece, Jun 2011.

× @inproceedings{zhou-2011-tap,
  author = {Wenchao Zhou and Ling Ding and Andreas Haeberlen and Zachary Ives and Boon Thau Loo},
  title = {{TAP}: {T}ime-aware Provenance for Distributed Systems},
  booktitle = {3rd USENIX Workshop on the Theory and Practice of Provenance (TaPP '11)},
  location = {Heraklion, Greece},
  month = jun,
  year = 2011
}

×
In this paper, we explore the use of provenance for analyzing execution dynamics in distributed systems. We argue that provenance could have significant practical benefits for system administrators, e.g., for reasoning about changes in a system’s state, diagnosing protocol misconfigurations, detecting intrusions, and pinpointing performance bottlenecks. However, to realize this vision, we must revisit several aspects of provenance management. As a first step, we present time-aware provenance (TAP), an enhanced provenance model that explicitly represents time, distributed state, and state changes. We outline our research agenda towards developing novel query processing, languages, and optimization techniques that can be used to efficiently and securely query time-aware provenance, even in the presence of transient state or untrusted nodes.

PDF BibTeX Abstract
Differential Privacy for Collaborative Security. Jason Reed, Adam J. Aviv, Daniel Wagner, Andreas Haeberlen, Benjamin C. Pierce, and Jonathan M. Smith. 3rd European Workshop on System Security (EuroSec '10), Paris, France, Apr 2010.

× @inproceedings{reed-2010-collaborative,
  author = {Jason Reed and Adam J. Aviv and Daniel Wagner and Andreas Haeberlen and Benjamin C. Pierce and Jonathan M. Smith},
  title = {Differential Privacy for Collaborative Security},
  booktitle = {3rd European Workshop on System Security (EuroSec '10)},
  location = {Paris, France},
  month = apr,
  year = 2010
}

×
Fighting global security threats with only a local view is inherently difficult. Internet network operators need to fight global phenomena such as botnets, but they are hampered by the fact that operators can observe only the traffic in their local domains. We propose a collaborative approach to this problem, in which operators share aggregate information about the traffic in their respective domains through an automated query mechanism. We argue that existing work on differential privacy and type systems can be leveraged tobuild a programmable query mechanism that can express a widerange of queries while limiting what can be learned about individual customers. We report on our progress towards building sucha mechanism, and we discuss opportunities and challenges of the collaborative security approach.

PDF BibTeX Abstract
A Case for the Accountable Cloud. Andreas Haeberlen. 3rd ACM SIGOPS International Workshop on Large-Scale Distributed Systems and Middleware (LADIS '09), Big Sky, MT, Oct 2009.

× @inproceedings{haeberlen-2009-accountablecloud,
  author = {Andreas Haeberlen},
  title = {A Case for the Accountable Cloud},
  booktitle = {3rd ACM SIGOPS International Workshop on Large-Scale Distributed Systems and Middleware (LADIS '09)},
  location = {Big Sky, MT},
  month = oct,
  year = 2009
}

×
For many companies, clouds are becoming an interesting alternative to a dedicated IT infrastructure. However, cloud computing also carries certain risks for both the customer and the cloud provider. The customer places his computation and data on machines he cannot directly control; the provider agrees to run a service whose detail she does not know. If something goes wrong – for example, data leaks to a competitor, or the computation returns incorrect results – it can be difficult for customer and provider to determine which of them has caused the problem, and, in the absence of solid evidence, it is nearly impossible for them to hold each other responsible for the problem if a dispute arises.
In this paper, we propose that the cloud should be made accountable to both the customer and the provider. Both parties should be able to check whether the cloud is running the service as agreed. If a problem appears, they should be able to determine which of them is responsible, and to prove the presence of the problem to a third party, such as an arbitrator or a judge. We outline the technical requirements for an accountable cloud, and we describe several challenges that are not yet met by current accountability techniques.

PDF BibTeX Abstract
Pretty Good Packet Authentication. Andreas Haeberlen, Rodrigo Rodrigues, Krishna P. Gummadi, and Peter Druschel. 4th Workshop on Hot Topics in System Dependability (HotDep '08), San Diego, CA, Dec 2008.

× @inproceedings{haeberlen-2008-pgpa,
  author = {Andreas Haeberlen and Rodrigo Rodrigues and Krishna P. Gummadi and Peter Druschel},
  title = {Pretty Good Packet Authentication},
  booktitle = {4th Workshop on Hot Topics in System Dependability (HotDep '08)},
  location = {San Diego, CA},
  month = dec,
  year = 2008
}

×
Internet addresses are routinely being used to infer the identity of persons who send offending traffic – a capability they were not designed to provide. As a result, problems abound: innocent users are being accused, while the culprits can easily avoid detection.
In this paper, we present Pretty Good Packet Authentication (PGPA), a simple service that can establish whether or not a given host has sent a particular packet. PGPA provides a firm basis on which to act against the culprit, and, at the same time, it enables innocent users to defend themselves against false accusations. We also describe an implementation of PGPA that can be deployed incrementally and with minimal changes to the current Internet.

PDF BibTeX Abstract Slides
Practical Accountability for Distributed Systems. Andreas Haeberlen, Petr Kuznetsov, and Peter Druschel. 3rd Workshop on Future Directions in Distributed Computing (FuDiCo III), Bertinoro, Italy, Oct 2007.

× @inproceedings{haeberlen-2007-accountability,
  author = {Andreas Haeberlen and Petr Kuznetsov and Peter Druschel},
  title = {Practical Accountability for Distributed Systems},
  booktitle = {3rd Workshop on Future Directions in Distributed Computing (FuDiCo III)},
  location = {Bertinoro, Italy},
  month = oct,
  year = 2007
}

PDF BibTeX
The Case for Byzantine Fault Detection. Andreas Haeberlen, Petr Kuznetsov, and Peter Druschel. 2nd Workshop on Hot Topics in System Dependability (HotDep '06), Seattle, WA, Nov 2006.

× @inproceedings{haeberlen-2006-detection,
  author = {Andreas Haeberlen and Petr Kuznetsov and Peter Druschel},
  title = {The Case for {Byzantine} Fault Detection},
  booktitle = {2nd Workshop on Hot Topics in System Dependability (HotDep '06)},
  location = {Seattle, WA},
  month = nov,
  year = 2006
}

PDF BibTeX Slides TR
Fallacies in evaluating decentralized systems. Andreas Haeberlen, Alan Mislove, Ansley Post, and Peter Druschel. 5th International Workshop on Peer-to-Peer Systems (IPTPS '06), Santa Barbara, CA, Feb 2006.

× @inproceedings{haeberlen-2006-fallacies,
  author = {Andreas Haeberlen and Alan Mislove and Ansley Post and Peter Druschel},
  title = {Fallacies in evaluating decentralized systems},
  booktitle = {5th International Workshop on Peer-to-Peer Systems (IPTPS '06)},
  location = {Santa Barbara, CA},
  month = feb,
  year = 2006
}

×
Research on decentralized systems such as peer-to-peer overlays and ad hoc networks has been hampered by the fact that few systems of this type are in production use, and the space of possible applications is still poorly understood. As a consequence, new ideas have mostly been evaluated using common synthetic workloads, traces from a few existing systems, testbeds like PlanetLab, and simulators like ns-2. Some of these methods have, in fact, become the "gold standard" for evaluating new systems, and are often a prerequisite for getting papers accepted at top conferences in the field.
In this paper, we examine the current practice of evaluating decentralized systems under these specific sets of conditions and point out pitfalls associated with this practice. In particular, we argue that (i) despite authors' best intentions, results from such evaluations often end up being inappropriately generalized; (ii) there is an incentive not to deviate from the accepted standard of evaluation, even if that is technically appropriate; (iii) research may gravitate towards systems that are feasible and perform well when evaluated in the accepted environments; and, (iv) in the worst-case, research may become ossified as a result. We close with a call to action for the community to develop tools, data, and best practices that allow systems to be evaluated across a space of workloads and environments.

PDF BibTeX Abstract
Proactive replication for data durability. Emil Sit, Andreas Haeberlen, Frank Dabek, Byung-Gon Chun, Hakim Weatherspoon, Robert Morris, and M. Frans Kaashoek. 5th International Workshop on Peer-to-Peer Systems (IPTPS '06), Santa Barbara, CA, Feb 2006.

× @inproceedings{sit-2006-tempo,
  author = {Emil Sit and Andreas Haeberlen and Frank Dabek and Byung-Gon Chun and Hakim Weatherspoon and Robert Morris and M. Frans Kaashoek},
  title = {Proactive replication for data durability},
  booktitle = {5th International Workshop on Peer-to-Peer Systems (IPTPS '06)},
  location = {Santa Barbara, CA},
  month = feb,
  year = 2006
}

×
Many wide-area storage systems replicate data for durability. A common way of maintaining the replicas is to detect node failures and respond by creating additional copies of objects that were stored on failed nodes and hence suffered a loss of redundancy. Reactive techniques can minimize total bytes sent since they only create replicas as needed; however, they can create spikes in network use after a failure. These spikes may overwhelm application traffic and can make it difficult to provision bandwidth.
This paper explores a proactive approach that creates additional copies not in response to failures, but periodically at a fixed low rate. We introduce Tempo, a distributed hash table that allows each user to specify a maximum maintenance bandwidth and uses it to perform proactive replication. Results from a simulation study suggest that Tempo can deliver high durability despite only using several kilobytes per second of bandwidth, comparable to state-of-the-art reactive systems.

PDF BibTeX Abstract
User-Level Management of L4 Kernel Memory. Andreas Haeberlen. 2th International Workshop on Microkernel-Based Systems, Lake Louise, Canada, Oct 2001.

× @inproceedings{haeberlen-2001-kpages,
  author = {Andreas Haeberlen},
  title = {User-Level Management of {L4} Kernel Memory},
  booktitle = {2th International Workshop on Microkernel-Based Systems},
  location = {Lake Louise, Canada},
  month = oct,
  year = 2001
}

×
In the Hazelnut microkernel, kernel memory is a limited resource. This allows malicious applications to run denial-of-service attacks against the kernel, because there is no way to restrict the amount of kernel memory they may use. I suggest to integrate kernel memory into the normal memory management concept, which permits to control its allocation entirely from user level.

PDF BibTeX Abstract
Stub-Code Performance is Becoming Important. Andreas Haeberlen, Jochen Liedtke, Yoonho Park, Lars Reuther, and Volkmar Uhlig. 1st Workshop on Industrial Experiences with Systems Software (WIESS '00), San Diego, CA, Oct 2000.

× @inproceedings{haeberlen-2000-idl4,
  author = {Andreas Haeberlen and Jochen Liedtke and Yoonho Park and Lars Reuther and Volkmar Uhlig},
  title = {Stub-Code Performance is Becoming Important},
  booktitle = {1st Workshop on Industrial Experiences with Systems Software (WIESS '00)},
  location = {San Diego, CA},
  month = oct,
  year = 2000
}

×
As IPC mechanisms become faster, stub-code efficiency becomes a performance issue for local client/server RPCs and inter-component communication. Inefficient and unnecessary complex marshalling code can almost double communication costs. We have developed an experimental new IDL compiler that produces near-optimal stub code for gcc and the L4 microkernel. The current experimental IDL4 compiler cooperates with the gcc compiler and its x86 code generator. Other compilers or target machines would require different optimizations. In most cases, the generated stub code is approximately 3 times faster (and shorter) than the code generated by a commonly used portable IDL compiler. Benchmarks have shown that efficient stubs can increase application performance by more than 10 percent. The results are applied within IBM’s SawMill project that aims at technology for constructing multi-server operating systems.

PDF BibTeX Abstract

Technical reports

Hermetic: Privacy-preserving distributed analytics without (most) side channels. Min Xu, Antonis Papadimitriou, Andreas Haeberlen, and Ariel Feldman. Technical report MS-CIS-19-01, University of Pennsylvania, Jan 2019.

× @techreport{xu-2019-hermetic,
  author = {Min Xu and Antonis Papadimitriou and Andreas Haeberlen and Ariel Feldman},
  title = {Hermetic: Privacy-preserving distributed analytics without (most) side channels},
  institution = {University of Pennsylvania},
  number = {MS-CIS-19-01},
  month = jan,
  year = 2019
}

×
Trusted execution environment (TEE), such as Intel SGX, is an emerging technology that enables privacy-preservingdistributed analytics on an untrusted cloud platform. TEEs, however, suffer from side channels, such as timing, memory and instruction access patterns, and message sizes that weaken their privacy guarantees. Existing attempts to mitigate these channels in analytics systems are unsatisfactory because they do not attempt to address multiple critical side channels simultaneously and employ mitigations that are inefficient, unprincipled, or difficult to use.
In this paper, we present Hermetic, a data query processing system that offers a principled approach to mitigating four of the most critical digital side channels simultaneously. We introduce an oblivious execution environment that supports fast, non-oblivious computations without leakage, as well as fast secure query operators using this primitive to process large data sets. We apply the differentially private (DP) padding mechanism on execution time and output sizes of query operators, which avoids prohibitive padding overheads as in most prior solutions, with provable privacy. To achieve efficient DP padding in complex query, we further introduce a privacy-aware query planner that can optimize a query plan under user’s privacy constraints. Our experimental evaluation of a Hermetic prototype shows that it is competitive with previous privacy-preserving systems, even though it provides stronger privacy guarantees.

PDF BibTeX Abstract
Fighting Cybercrime with Packet Attestation. Andreas Haeberlen, Pedro Fonseca, Rodrigo Rodrigues, and Peter Druschel. Technical report MPI-SWS-2011-002, Max Planck Institute for Software Systems, Jul 2011.

× @techreport{haeberlen-2011-packetattestation,
  author = {Andreas Haeberlen and Pedro Fonseca and Rodrigo Rodrigues and Peter Druschel},
  title = {Fighting Cybercrime with Packet Attestation},
  institution = {Max Planck Institute for Software Systems},
  number = {MPI-SWS-2011-002},
  month = jul,
  year = 2011
}

×
IP source addresses are often the only initial lead when investigating cybercrime in the Internet. Unfortunately, source addresses are easily forged, which can protect the culprits and lead to false accusations. We describe a new method for packet attestation in the Internet. Packet attestation establishes whether or not a given IP packet was sent by a particular network subscriber. This capability allows network operators to verify the source of malicious traffic and to validate complaints, identity requests, and DMCA take-downnotices against their clients. As a result, innocent users cannot be falsely accused, while the culprits no longer enjoy plausible deniability. Support for packet attestation can be deployed incrementally by ISPs, and requires no changes to end hosts or to the network core.

PDF BibTeX Abstract
Tracking Adversarial Behavior in Distributed Systems with Secure Network Provenance. Wenchao Zhou, Andreas Haeberlen, Boon Thau Loo, and Micah Sherr. Technical report MS-CIS-10-28, University of Pennsylvania, Aug 2010.

× @techreport{zhou-2010-snp,
  author = {Wenchao Zhou and Andreas Haeberlen and Boon Thau Loo and Micah Sherr},
  title = {Tracking Adversarial Behavior in Distributed Systems with Secure Network Provenance},
  institution = {University of Pennsylvania},
  number = {MS-CIS-10-28},
  month = aug,
  year = 2010
}

×
This paper presents secure network provenance (SNP), a novel technique for tracking down compromised nodes in a distributed system and assessing the damage that they may have caused to other nodes. SNP enables operators to ask the system why it is in a certain state – for example, why a suspicious routing table entry is present on a certain router, or where a given cache entry originated. SNP is robust to manipulation; its tamper-evident properties ensure that operators can detect when compromised nodes lie or falsely implicate correct nodes. Thus, compromised nodes can at worst refuse to participate, making their presence evident to operators. We describe analgorithm for answering SNP queries, as well as a proof-of-concept implementation.

PDF BibTeX Abstract
Consistent Key Mapping in Structured Overlays. Andreas Haeberlen, Jeff Hoye, Alan Mislove, and Peter Druschel. Technical report TR05-456, Department of Computer Science, Rice University, Aug 2005.

× @techreport{haeberlen-2005-consistent,
  author = {Andreas Haeberlen and Jeff Hoye and Alan Mislove and Peter Druschel},
  title = {Consistent Key Mapping in Structured Overlays},
  institution = {Department of Computer Science, Rice University},
  number = {TR05-456},
  month = aug,
  year = 2005
}

×
Most structured peer-to-peer overlays rely on consistent hashing to determine the node that is responsible for a given key. For consistent hashing to work properly, it is necessary that the nodes have a consistent view of their neighborhood in the identifier space. However, if routing anomalies occur in the underlying network, this view can become inconsistent, causing unstable overlay behavior and, worse, allowing more than one node to assume responsibility for ranges of keys.
We present a set of techniques for preventing inconsistencies under routing anomalies, and we propose to adopt strategies from mobile ad-hoc networking for maintaining connectivity in the presence of path failures. We evaluate our design in the context of Pastry and present results from a deployment in the PlanetLab testbed.

PDF BibTeX Abstract
Performance of Address-Space Multiplexing on the Pentium. Volkmar Uhlig, Uwe Dannowski, Espen Skoglund, Andreas Haeberlen, and Gernot Heiser. Technical report 2002-1, Department of Computer Science, University of Karlsruhe, May 2002.

× @techreport{uhlig-2002-smallspaces,
  author = {Volkmar Uhlig and Uwe Dannowski and Espen Skoglund and Andreas Haeberlen and Gernot Heiser},
  title = {Performance of Address-Space Multiplexing on the Pentium},
  institution = {Department of Computer Science, University of Karlsruhe},
  number = {2002-1},
  month = may,
  year = 2002
}

×
This paper presents an analysis of the performance potential and limitation of the so-called small-space scheme, where several logical address spaces are securely multiplexed onto a single hardware address space. This can be achieved on the IA-32 architecture by using the segment registers to relocate address spaces transparently to the applications.
Our results show that the scheme can provide significant performance improvements in cases where processes with small working sets interact frequently, as is often the case in client-server applications, and particularly in microkernel-based systems. We also investigate how potentially costly revocation of mappings can be prevented by clustering communicating processes.

PDF BibTeX Abstract Software

Other publications

The NEBULA Future Internet Architecture. Tom Anderson, Ken Birman, Robert Broberg, Matthew Caesar, Douglas Comer, Chase Cotton, Michael J. Freedman, Andreas Haeberlen, Zachary G. Ives, Arvind Krishnamurthy, William Lehr, Boon Thau Loo, David Mazieres, Antonio Nicolosi, Jonathan M. Smith, Ion Stoica, Robbert van Renesse, Michael Walfish, Hakim Weatherspoon, and Christopher S. Yoo. Chapter in The Future Internet, LNCS 7858, Springer Verlag, Alex Galis and Anastasius Gavras, Eds., 2013.

× @incollectionanderson-2013-nebula,
  author = {Tom Anderson and Ken Birman and Robert Broberg and Matthew Caesar and Douglas Comer and Chase Cotton and Michael J. Freedman and Andreas Haeberlen and Zachary G. Ives and Arvind Krishnamurthy and William Lehr and Boon Thau Loo and David Mazieres and Antonio Nicolosi and Jonathan M. Smith and Ion Stoica and Robbert van Renesse and Michael Walfish and Hakim Weatherspoon and Christopher S. Yoo},
  title = {The {NEBULA} Future Internet Architecture},
  booktitle = {The Future Internet, LNCS 7858},
  publisher = {Springer Verlag},
  editor = {Alex Galis and Anastasius Gavras},
  year = 2013
}

BibTeX Book
NetTrails: A Declarative Platform for Maintaining and Querying Provenance in Distributed Systems. Wenchao Zhou, Qiong Fei, Shengzhi Sun, Tao Tao, Andreas Haeberlen, Zachary Ives, Boon Thau Loo, and Micah Sherr. Demo session at the ACM SIGMOD International Conference on Management of Data (SIGMOD '11 Demo), Athens, Greece, Jun 2011.

× @inproceedings{zhou-2011-nettrails,
  author = {Wenchao Zhou and Qiong Fei and Shengzhi Sun and Tao Tao and Andreas Haeberlen and Zachary Ives and Boon Thau Loo and Micah Sherr},
  title = {{NetTrails}: {A} Declarative Platform for Maintaining and Querying Provenance in Distributed Systems},
  booktitle = {Demo session at the ACM SIGMOD International Conference on Management of Data (SIGMOD '11 Demo)},
  location = {Athens, Greece},
  month = jun,
  year = 2011
}

×
We demonstrate NetTrails, a declarative platform for maintaining and interactively querying network provenance in a distributed system. Network provenance describes the history and derivations of network state that result from the execution of a distributed protocol. It has broad applicability in the management, diagnosis, and security analysis of networks. Our demonstration shows the use of NetTrails for maintaining and querying network provenance in a variety of distributed settings, ranging from declarative networks to unmodified legacy distributed systems. We conclude our demonstration with a discussion of our ongoing research on enhancing the query language and security guarantees.

PDF BibTeX Abstract
ePOST. Alan Mislove, Andreas Haeberlen, Ansley Post, and Peter Druschel. Chapter in Peer-to-Peer Systems and Applications, LNCS 3485, Springer Verlag, Ralf Steinmetz and Klaus Wehrle, Eds., Aug 2005.

× @incollectionmislove-2005-epostchapter,
  author = {Alan Mislove and Andreas Haeberlen and Ansley Post and Peter Druschel},
  title = {{ePOST}},
  booktitle = {Peer-to-Peer Systems and Applications, LNCS 3485},
  publisher = {Springer Verlag},
  editor = {Ralf Steinmetz and Klaus Wehrle},
  month = aug,
  year = 2005
}

BibTeX Book Software
Managing Kernel Memory Resources from User Level. Andreas Haeberlen. Diplomarbeit, University of Karlsruhe, Germany, Apr 2003.

× @misc{haeberlen-2003-thesis,
  author = {Andreas Haeberlen},
  title = {Managing Kernel Memory Resources from User Level},
  note = {Diplomarbeit, University of Karlsruhe, Germany},
  month = apr,
  year = 2003
}

×
In order to implement abstractions like threads or address spaces, operating system kernels need to maintain the corresponding metadata. This metadata is usually stored in kernel memory, i.e. in a region of physical memory that is reserved for kernel use. As the amount of available kernel memory is limited, its allocation must be controlled carefully; otherwise, applications can run a denial-of-service attack against the kernel by consuming all of its resources.
Some operating system kernels have addressed this problem by providing powerful management policies. However, with a single global policy,it is difficult to accommodate multiple domains with different requirements at the same time. Also, existing solutions allow only limited control over kernel memory; for example, it is often not possible to reduce an allocation, except by killing the task that currently holds it. This makes it difficult to respond to changing load situations or suspected denial-of-service attacks.
In this thesis, we present a new scheme which uses paged virtual memory to control kernel memory resources from user level. Memory can be preempted from the kernel and restored later; any kernel metadata affected by this is converted into an external representation, which can be safely exported. To demonstrate our approach, we apply it to an existing kernel, the L4 microkernel. We also present an experimental implementation.

PDF BibTeX Abstract
Using Platform-Specific Optimizations in Stub-Code Generation. Andreas Haeberlen. Study Thesis, University of Karlsruhe, Germany, Jul 2002.

× @misc{haeberlen-2002-idl4,
  author = {Andreas Haeberlen},
  title = {Using Platform-Specific Optimizations in Stub-Code Generation},
  note = {Study Thesis, University of Karlsruhe, Germany},
  month = jul,
  year = 2002
}

×
The use of a stub code generator can greatly reduce the effort required to implement a multi-server system on top of a microkernel. However, stub code has traditionally been highly generic and therefore rather slow, which has prevented it from being used in performance-critical applications.
In this work, we show that this restriction can be eliminated by specialization for the underlying platform, i.e. by exploiting specific properties of the kernel, compiler, or hardware platform that are being used. We demonstrate our approach for an example platform, the L4 microkernel, and present a variety of optimization techniques that can be used to improve stub code performance on this platform.
Our techniques are implemented and validated in IDL⁴, our optimizing stub code generator. A comparison with traditional stub code generators shows that IDL⁴ stubs can perform up to an order of magnitude better, and that they can in-crease application performance by more than 10 percent.

PDF BibTeX Abstract Software
The L4Ka Vision. Jochen Liedtke, Uwe Dannowski, Kevin Elphinstone, Gerd Liefländer, Espen Skoglund, Volkmar Uhlig, Christian Ceelen, Andreas Haeberlen, and Marcus Völp. White Paper, University of Karlsruhe, Germany, Apr 2001.

× @misc{liedtke-2001-l4kavision,
  author = {Jochen Liedtke and Uwe Dannowski and Kevin Elphinstone and Gerd Liefl\"ander and Espen Skoglund and Volkmar Uhlig and Christian Ceelen and Andreas Haeberlen and Marcus V\"olp},
  title = {The {L4Ka} Vision},
  note = {White Paper, University of Karlsruhe, Germany},
  month = apr,
  year = 2001
}

×
Microkernels are minimal but highly flexible kernels. Both conventional and non-classical operating systems can be built on top or adapted to run on top of them. Microkernel-based architectures should particularly support extensibility and customizability, robustness including reliability and fault tolerance, protection and security.
After desastrous results in the early 90’s, the microkernel approach now seems to be promising, although it still bears a lot of research risks. Currently, University of Karlsruhe's system architecture group is defining the state of the art in microkernel research.
The L4Ka research project aims at substantiating and establishing a new methodology for system construction that helps to manage ever-increasing OS complexity and minimizes legacy dependence. Our vision is a microkernel technology that can be and is used advantageously for constructing any general or customized operating system including pervasive systems, deep-computing systems, and huge servers.
The technology should help to manage ever-increasing OS complexity, enable stepwise innovations in OS technology while preserving legacy compatibility, and lead to a widely-accepted foundation of system architecture.

PDF BibTeX Abstract Software

Topics

Sort by

Conference papersTopicDateType

Workshop papers

Technical reports

Other publications

Conference papersTopic Date Type