Publications on Accountability

• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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

Show all publications