Publications | Andreas Haeberlen

Topics

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

Show all

Sort by

Type
Date
Topic

Publications on Provenance

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

Show all publications