Differentially-private network trace analysis

By Frank McSherry, Ratul Mahajan. 2010

143 citations recorded by the source corpus.

We consider the potential for network trace analysis while providing the guarantees of "differential privacy." While differential privacy provably obscures the presence or absence of individual records in a dataset, it has two major limitations: analyses must (presently) be expressed in a higher level declarative language; and the analysis results are randomized before returning to the analyst. We report on our experiences conducting a diverse set of analyses in a differentially private manner. We are able to express all of our target analyses, though for some of them an approximate expression is required to keep the error-level low. By running these analyses on real datasets, we find that the error introduced for the sake of privacy is often (but not always) low even at high levels of privacy. We factor our learning into a toolkit that will be likely useful for other analyses. Overall, we conclude that differential privacy shows promise for a broad class of network analyses.

Subfields: Artificial Intelligence, Sociology and Political Science, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Privacy & Security

Citations in the corpus

Prochlo: Strong Privacy for Analytics in the Crowd (2017, background): “Those mechanisms support analysis ranging from simple statistics through domain-specific network analysis, to generalpurpose deep learning of neural networks by stochastic gradient descent [4, 27, 51].”
Functional Mechanism: Regression Analysis under Differential Privacy (2012, methodology): “…[2] and Ding et al. [8] consider the publication of data cubes; Xu et al. [31] and Li et al. [18] focus on publishing histograms; McSherry and Mironov [20], Rastogi and Nath [24], and McSherry and Mahajan [19] devise methods for re-leasing counts on particular types of data, such as time series.”
Differential Privacy: An Economic Method for Choosing Epsilon (2014, background): “ empi rical attacks on private algorithms, to shed light 25 In some experiments, people give up their private data for as little as a dollar [4]. 23 Authors Value(s) of ε Application McSherry-Mahajan [32] 0.1—10 Network Trace Analysis Chaudhuri-Monteleoni [7] 0.1 Logistic Regression Machanavajjhala ”
Towards Statistical Queries over Distributed Private User Data (2012, background): “In spite of the fact that an increasing number of queries can lead to increased privacy loss, we find differential privacy to be an attractive model both because it does provide measurable privacy, and because there is substantial ongoing effort in developing its uses [32, 38, 39, 40, 47] and unders”
PrivBayes: private data release via bayesian networks (2014, background): “Even if the data is skewed in the domain space, i.e., there are some entries x[i] with high counts, such peaks are infrequent and so the vast majority of published values x∗[i] are useless.”
Differential Privacy (2015, methodology): “For example, in the network analysis example of McSh-erry and Mahajan [16] the ﬁrst transformation of the dataset is to group network requests by IP address.”
Privacy-Preserving Data Exploration in Genome-Wide Association Studies (2013, methodology): “It has been successfully applied to search logs [16], movie-viewing records [21], network traces [20], and social networks [11].”
Handling a trillion (unfixable) flaws on a billion devices: Rethinking network security for the Internet-of-Things (2015, methodology): “To address the privacy challenge (2), we can institute anonymization routines or use other types of privacy-preserving techniques to limit information leakage [28, 29].”
A Practical Application of Differential Privacy to Personalized Online Advertising (2011, background): “∗This work was supported by a starting grant from the European Research Council.”
Differentially private histogram publication (2012, methodology): “Korolova et al. [16] and G¨otz et al. [11] present methods for publishing statistics in search logs, while McSherry and Mahajan [19] develop techniques for network trace analysis.”
Human mobility modeling at metropolitan scales (2012, methodology): “Similar techniques have been successfully applied to network traffic traces [23].”
On significance of the least significant bits for differential privacy (2012, background): “Realizations of differentially private mechanisms include privacy-preserving histograms [MKA + 08], logistic regressions [CM08], recommender systems [MM09], network-analysis tools [ MM10 ], and many others.”
Differentially private sequential data publication via variable-length n-grams (2012, methodology): “As a reference point, for count query, we compare the utility of our solution with the approach proposed in [4], which relies on a prefix tree structure (referred to as Prefix); for frequent sequential pattern mining, we compare our approach with both Prefix and the method designed in [16] for findi”
Differential Privacy for Deep and Federated Learning: A Survey (2022, background): “There are many works that speciﬁcally handle the case of sequential datasets 6 [74], [105], [106].”
Differential privacy based on importance weighting (2013, background): “Some of them answer unrestricted queries without publishing data (Smith 2008; McSherry and Mironov 2009; Li et al. 2010; McSherry and Mahajan 2010; Rastogi and Nath 2010).”
PROCHLO: Strong Privacy for Analytics in the Crowd (2017, background): “Those mechanisms support analysis ranging from simple statistics through domain-specific network analysis, to generalpurpose deep learning of neural networks by stochastic gradient descent [4, 27, 51].”