Accountability for Distributed Systems

Overview | Downloads | Papers | People

Motivation: Faults in distributed systems

Finding faults in distributed systems is difficult. Imagine a large-scale distributed system, like the Internet's routing infrastructure or the international banking network. A system like this can consist of thousands of nodes, run by hundreds of different organizations. Suppose we suspect that some of the nodes may have become faulty - maybe the hardware is malfunctioning, or the nodes have been misconfigured, or a hacker has compromised them and has changed the software they are running. However, we do not know which nodes are faulty, or what the symptoms of the fault are. How can we deal with such a situation?

There are three important problems we must solve:

Secure logging: We must make sure that we have enough information to detect the fault, no matter how complicated or unexpected it may be. Unfortunately, getting reliable information is difficult, since the faulty nodes could report incorrect information, or they could fail to report anything at all. Thus, we cannot expect our information to be either complete or accurate.
Detection: We must decide whether a problem exists, and which nodes are affected. This can be difficult because the problem may not be visible from any individual node, or may appear sporadically. If a hacker is involved, the nodes under his control may actively attempt to evade detection, or they may try to frame other nodes that the attacker wants to appear faulty.
Convincing third parties: Even if an administrator has diagnosed the problem correctly, he may not be able to get it fixed because the faulty nodes can be in another domain. In this case, he must convince the other administrators that the problem is on their side - even if they cannot observe the symptoms themselves.

Our approach: Accountability

We are exploring accountability as a new approach to this problem. In an accountable system, all actions - such as the transmission of a message - are cryptographically linked to the node that performs them, and the system maintains a secure record of past actions. Nodes can use this record to check each other's actions for correctness. Using this approach, it is possible to guarantee that any fault that is observable by a correct node is eventually detected. Moreover, at least one node obtains irrefutable evidence that is linked to a faulty node. This evidence can then be used to convince other nodes (to isolate the faulty node) or a human administrator (to repair the node). At the same time, a correct node can always defend itself against false accusations.

Accountability has both technical and non-technical benefits. On the technical side, accountability provides reliable information about faults, which can be used to build more resilient systems. Because accountability works for such a general class of faults, it can be used as a `safety net' that works even when other techniques fail. On the non-technical side, the ability to inspect a principal's record helps to build trust and reputation. Also, the very presence of an accountability system discourages some types of faults, such as rational/selfish behavior, since all faults are guaranteed to be detected eventually.

Projects

We are working on several projects related to accountability:

PeerReview: We have developed an algorithm called PeerReview that can provably enforce accountability for the very general class of Byzantine faults. 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. You can read more about PeerReview in our SOSP '07 paper; an open-source implementation is available below.
Accountability for interdomain routing: We have built a system called NetReview that enforces accountability for BGP routing. NetReview can help to reduce the large number of routing problems that are being observed in the Internet today. Unlike PeerReview, NetReview can not only detect faults with respect to a given protocol, but also with respect to high-level policies, such as peering agreements between two ISPs. You can read more about NetReview in our NSDI '09 paper.
Accountable virtual machines: PeerReview can only enforce accountability if it is integrated with each individual application. This is not acceptable in scenarios like cloud computing, where service providers may want to be accountable to their customers regardless of what software they install. To remove this limitation, we are working on an accountable VMM, which can deliver accountability for arbitrary programs - or even an entire operating system.
Pretty Good Packet Authentication: PGPA is a simple, easy-to-deploy service that can establish accountability for Internet traffic. Given a packet, a source address and a timestamp, PGPA can determine whether or not the packet was sent from that address at the specified time. You can read more about PGPA in our HotDep '08 paper.
Accountability for probabilistic systems: We are working on a variant of PeerReview that works for randomized algorithms. To make this possible, we provide each node with a special random-number generator. This generator works in such a way that other nodes cannot predict its future output (which would open up correct nodes to attacks), but they can verify whether its past output has been generated correctly. You can read more in our NDSS '09 paper.

Downloads

Latest PeerReview source code (v1.0.8): [tgz]

We are currently adding PeerReview support to FreePastry.

Papers

NetReview: Detecting when interdomain routing goes wrong
Andreas Haeberlen, Ioannis Avramopoulos, Jennifer Rexford, and Peter Druschel.
To appear in: Proceedings of the 6th Symposium on Networked Systems Design and Implementation (NSDI '09), Boston, MA, April 2009.

CSAR: A Practical and Provable Technique to Make Randomized Systems Accountable
Michael Backes, Peter Druschel, Andreas Haeberlen, and Dominique Unruh
To appear in: Proceedings of the 16th Annual Network & Distributed System Security Symposium (NDSS '09), San Diego, CA, February 2009.
[PDF] [BibTex]
Pretty Good Packet Authentication
Andreas Haeberlen, Rodrigo Rodrigues, Krishna P. Gummadi, and Peter Druschel
Proceedings of the Fourth Workshop on Hot Topics in System Dependability (HotDep '08), San Diego, CA, December 2008.
[PDF] [BibTex]
PeerReview: Practical Accountability for Distributed Systems
Andreas Haeberlen, Petr Kuznetsov, and Peter Druschel
Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP '07), Stevenson, WA, October 2007.
[PDF] [BibTex] [Technical report]
The Case for Byzantine Fault Detection
Andreas Haeberlen, Petr Kuznetsov, and Peter Druschel.
Proceedings of the Second Workshop on Hot Topics in System Dependability (HotDep '06), Seattle, WA, November 2006.
[PDF] [BibTex]

Posters

Accountable Virtual Machines
Andreas Haeberlen, Rodrigo Rodrigues, and Peter Druschel
Poster at the 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI '08), San Francisco, CA, April 2008.

Talks

Pretty Good Packet Authentication
Andreas Haeberlen
Fourth Workshop on Hot Topics in System Dependability (HotDep '08), San Diego, CA, December 2008.
[Slides]
PeerReview: Practical Accountability for Distributed Systems
Andreas Haeberlen
21st ACM Symposium on Operating Systems Principles (SOSP '07), Stevenson, WA, October 2007.
[Slides]
The Case for Byzantine Fault Detection
Andreas Haeberlen
Second Workshop on Hot Topics in System Dependability (HotDep '06), Seattle, WA, November 2006.
[Slides]

People

Andreas Haeberlen
Rodrigo Rodrigues
Petr Kuznetsov
Peter Druschel