Source-linked AI summary
Collecting Telemetry Data Privately
Bolin Ding, Janardhan Kulkarni, Sergey Yekhanin
TL;DR
Repeated telemetry collection creates a privacy gap because single-round LDP guarantees degrade rapidly over time, especially for counter data. The paper develops LDP mechanisms combining 1-bit responses, α-point rounding, memoization, and output perturbation for mean and histogram estimation. These mechanisms provide formal repeated-collection guarantees with comparable or unchanged accuracy relative to single-round methods, and have been deployed across millions of devices.
Problem
Single-round LDP guarantees degrade rapidly under repeated collection, while prior memoization techniques cannot accommodate small, frequent changes in counter values.
Method
The paper combines 1-bit LDP mechanisms with α-point rounding, memoization, and output perturbation for repeated counter-data collection.
Results
The mechanisms achieve comparable or unchanged accuracy relative to existing single-round LDP collection mechanisms for mean and histogram estimation.
Takeaways & Limitations
The mechanisms support private continuous telemetry collection at the scale of millions of devices and have been deployed by Microsoft.
Takeaways & Limitations
The repeated-collection guarantee is weaker than single-round population-wide LDP and may remain vulnerable to auxiliary-information attacks on subpopulations.
Abstract
from arXiv · showhide
The collection and analysis of telemetry data from users' devices is routinely performed by many software companies. Telemetry collection leads to improved user experience but poses significant risks to users' privacy. Locally differentially private (LDP) algorithms have recently emerged as the main tool that allows data collectors to estimate various population statistics, while preserving privacy. The guarantees provided by such algorithms are typically very strong for a single round of telemetry collection, but degrade rapidly when telemetry is collected regularly. In particular, existing LDP algorithms are not suitable for repeated collection of counter data such as daily app usage statistics. In this paper, we develop new LDP mechanisms geared towards repeated collection of counter data, with formal privacy guarantees even after being executed for an arbitrarily long period of time. For two basic analytical tasks, mean estimation and histogram estimation, our LDP mechanisms for repeated data collection provide estimates with comparable or even the same accuracy as existing single-round LDP collection mechanisms. We conduct empirical evaluation on real-world counter datasets to verify our theoretical results. Our mechanisms have been deployed by Microsoft to collect telemetry across millions of devices.
1 Introduction
The paper targets private, accurate, and scalable continuous collection of counter telemetry, where single-round local privacy guarantees degrade rapidly over time. It introduces mechanisms for repeated collection that combine local randomization, α-point rounding, memoization, and output perturbation.
- Motivation: The paper designs mechanisms for continuous counter collection that preserve privacy, accuracy, and scalability to populations of millions.The target data includes daily app or system usage statistics, and the stated scale is millions of users.
- Prior limitations: Existing memoization approaches protect nearly constant values but are unsuitable when private counter values undergo small, frequent changes.The paper identifies this limitation as a barrier to applying prior continual-collection techniques to counter telemetry.
- Privacy framework: α-point rounding allows memoization for continuously collected counters while avoiding substantial accuracy or privacy losses.The technique is designed for small changes in private values and supports formal privacy guarantees over an arbitrarily long collection period.
- Problem formulation: The paper studies mean estimation and histogram estimation as its two statistical estimation problems.Mean error is measured by the worst-case absolute estimation error, while histogram error is the worst-case absolute frequency error across buckets.
- Motivation: Continuous telemetry requires privacy guarantees that remain meaningful when counter data is collected repeatedly over time.Independent ε-LDP collection over T rounds can provide indistinguishability only up to e^(T·ε), which becomes unreasonable as T increases.
- Privacy framework: The framework combines 1-bit locally private mechanisms, α-point rounding, memoization, and output perturbation for mean and histogram estimation.Rounding discretizes values while preserving expectation, memoization limits leakage during repeated collection, and output perturbation protects usage-change transition points.
2 Single-round LDP mechanisms for mean and histogram Estimation
The section presents simple 1-bit and d-bit local-DP mechanisms for estimating counter means and histograms, emphasizing communication efficiency and formal single-round privacy. Their constructions support practical large-scale telemetry collection, while dBitFlip interpolates communication cost and matches Duchi et al.’s mechanism when d = k.
- Mechanisms: The proposed 1-bit mechanisms estimate counter means and histograms while sending only one bit per counter at each collection time.The mechanisms are designed to be easy to understand and implement, with accuracy gains reported in concrete settings.
- Mean estimation: 1BitMean preserves ϵ-LDP for each user, and the collector estimates the population mean from n users’ reported bits.The theorem establishes the single-round privacy guarantee and an accuracy bound with probability at least 1 − δ.
- Histogram estimation: dBitFlip lets each user sample d buckets and send one randomized bit for each sampled bucket, reducing communication relative to reporting all k buckets.Public coins can generate the sampled bucket numbers, so users need send only the d bits.
- Histogram estimation: The histogram estimator reconstructs each bucket frequency from the randomized responses and provides a single-round ϵ-LDP guarantee.The stated error analysis combines sampling and randomized-response concentration across buckets.
- Histogram estimation: When d = k, dBitFlip is exactly the same as Duchi et al.’s mechanism, while smaller d provides a communication-accuracy trade-off.For each bucket, roughly nd/k users contribute a randomized bit in expectation.
3 Memoization for continual collection of counter data
Repeated collection can leak nearly constant or slowly changing counter values because independent noisy responses accumulate. The paper combines discretization, α-point rounding, and memoization to obtain stronger continual-collection privacy while preserving single-round accuracy guarantees.
- Repeated ϵ-LDP responses can let a collector estimate an unchanged private counter accurately after enough rounds.This motivates mechanisms designed specifically for continuous telemetry collection.
- Naive memoization protects constant values but provides little additional protection when counters change slightly and frequently.Repeated independent responses can reveal approximately stable values despite memoization.
- Naive midpoint discretization limits leakage from small changes but can cause extremely large accuracy loss.If all values equal ℓs + 1, midpoint rounding makes every response use ℓs + s/2.
- 3.1 α-point rounding for mean estimation: α-point rounding randomly discretizes counters so memoization can support continual collection without additional accuracy loss dependent on granularity s.Theorem 3 states that each round retains the accuracy guarantees of the basic single-round mechanism, independently of s.
- 3.1 α-point rounding for mean estimation: The mechanism independently samples α_i, rounds each current counter to a neighboring discretized value, and returns the corresponding memoized 1-bit response.The rounded value is selected according to whether x_i + α_i falls before the neighboring boundary.
- 3.2 Privacy definition using permanent memoization: Users sharing a behavior pattern receive a continual-collection privacy guarantee, but this guarantee is weaker than single-round ϵ-LDP and can remain vulnerable to auxiliary-information attacks.A changed response still reveals that the true counter changed, such as app usage occurring on a particular day.
4 Output Perturbation
Output perturbation flips memoized response bits independently to prevent the data collector from identifying exact behavior-change times. The resulting protection makes changes indistinguishable within a δ-sized time interval while preserving a single-round privacy relationship.
- A memoization-only output change can reveal with certainty when a user’s behavior changes significantly.
- Theorem 5 bounds the likelihood ratio for output sequences when the underlying memoized outputs differ at no more than δ time points.
- Output perturbation independently flips each memoized response bit with probability γ.
- When behavior changes at time t, output perturbation prevents distinguishing t from another change time t′ within [t −δ, t + δ].
- Theorem 6 relates output perturbation with positive γ to invoking 1BitMean with an adjusted privacy parameter in a single collection round.
5 Empirical Evaluation
The empirical evaluation compares repeated-collection mechanisms with one-time LDP baselines for mean and histogram estimation. Across real-world and synthetic settings, the experiments test accuracy under varying privacy levels, population sizes, and data distributions.
- The experiments compare repeated-collection mechanisms with one-time ε-LDP mechanisms while assessing whether added repeated-collection protection preserves estimation accuracy.
- Mean estimation: Mean estimation uses 1BitRRPM and 1BitRRPM+OP(γ), compared with the Laplace mechanism across ε = 0.1-10 and n = 0.3, 1, 3 × 10^6.
- Histogram estimation: Histogram estimation evaluates dBitFlipPM with d = 1, 2, 4 against BinFlip, KFlip, and BinFlip+ using k = 32 buckets.
- Histogram estimation: BinFlip, equivalently 32BitFlipPM, has the best overall histogram accuracy in the reported real-world experiments.
- Histogram estimation: 4bitFlipPM is comparable to KFlip for ε = 0.1-0.5, while 4bitFlipPM-1bitFlipPM outperform BinFlip+ for ε = 5-10.
- Synthetic datasets: Synthetic experiments test whether mean and histogram errors remain similar across constant, uniform, and other data distributions.
6 Deployment
The deployed system collects app-usage counters every six hours using memoization and output perturbation. Its privacy accounting yields bounded single-round guarantees, with only minor additional loss when collecting multiple apps because total active usage is bounded.
- Microsoft deployed the mean-estimation algorithm to collect app usage in seconds every six hours with ε = 1 and output perturbation γ = 0.2.
- With γ = 0.2, Theorem 6 gives a single-round guarantee of ε′ = 0.686-DP.
- Collecting multiple app counters from one user causes only minor additional privacy loss independent of the number of apps.
- The multi-app bound relies on active usage data whose total seconds across apps in six hours is bounded independently of app count.
- Theorem 7 gives ε′′ = 1.672-DP for a single round collecting an arbitrary number of apps.