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

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

Show all publications