PoolView: stream privacy for grassroots participatory sensing

Raghu K. Ganti, Nam Pham, Yu-En Tsai, Tarek F. AbdelzaherSenSys 2008 · DOI

TL;DR

This paper introduces PoolView, a novel architecture and perturbation technique for preserving individual privacy in grassroots participatory sensing applications. It enables communities to collectively gather and analyze stream data from privately-owned sensors without compromising individual user privacy, even in the absence of a trusted central authority.

What Problem Does This Paper Address?

Grassroots participatory sensing involves individuals voluntarily contributing data from their personal sensors to collectively understand phenomena of mutual interest (e.g., traffic patterns, personal health metrics). A major hurdle in these applications is ensuring user privacy, especially when data is collected and aggregated without a hierarchical trust structure. Traditional privacy methods like anonymization or simple noise addition are often insufficient, as they can be circumvented by sophisticated data analysis techniques that exploit correlations within time-series data. This paper tackles the challenge of providing robust privacy guarantees for stream data in such decentralized, trust-minimizing environments.

Methods

The core of PoolView is a client-side data perturbation mechanism that leverages a "privacy firewall." Instead of directly sharing raw data, users perturb their data using a noise model that approximates the underlying phenomenon they are measuring. This noise model is designed to be similar in structure to the actual data model but with different parameters.

Key methodological contributions include:

  • Privacy-Preserving Perturbation: Users generate "virtual" data streams using a noise model and add this to their actual data. This combined stream is then shared. The noise model is designed such that reconstructing individual data streams from the perturbed data is computationally difficult, while still allowing for accurate community-level aggregation.
  • Community-Wide Reconstruction: The aggregation server (a "pool") uses statistical techniques (specifically, Tikhonov-Miller restoration for deconvolution) to estimate the true community distribution from the aggregated perturbed data. The mathematical foundation relies on the fact that the aggregate noise distribution is known, allowing it to be subtracted from the aggregate perturbed data.
  • Model and Parameter Verification: To combat malicious servers that might provide "bad" noise models to compromise privacy, PoolView includes a client-side verification mechanism. Users can locally test if the announced noise model and its parameter distributions are plausible for their own data, rejecting suspicious models.
  • Grassroots Architecture: PoolView is designed to be decentralized, allowing any arbitrary party to set up a "pool" for a new sensing service with a simple API.

Datasets

The paper evaluates PoolView using two case studies with data collected by the authors:

  • Traffic Analyzer: GPS data collected from two city streets (Green Street and University Avenue) by 30 emulated users over multiple trips.
  • Diet Tracker: Weight data collected from a single user over sixty days, with multiple users emulated based on this data.

The authors do not introduce new public benchmarks but rather use real-world data traces to demonstrate the effectiveness of their approach.

Key Insights and Ideas

  • Noise as a "Virtual User": The concept of using a noise model that mimics the data's underlying dynamics, effectively creating a "virtual user," is a clever way to obscure individual data while preserving aggregate properties.
  • Decentralized Trust is Achievable: The work demonstrates that robust privacy can be achieved in participatory sensing without relying on a central trusted authority, empowering individuals and communities.
  • Client-Side Verification is Crucial: The inclusion of a model verification step on the client side is essential for building trust in a decentralized system where servers might not be trustworthy.
  • Time-Series Correlation is the Key Challenge: The paper highlights that the temporal correlation in stream data is the primary reason simple perturbation methods fail, and their approach specifically addresses this.

Key Results

  • Accurate Community Aggregation: PoolView successfully reconstructs community average speed and weight distributions with high accuracy, even with small community sizes (e.g., 17 users for traffic speed). For instance, the average error for community speed reconstruction was 1.94 mph with 17 users.
  • Robust Privacy Against Attacks: The proposed perturbation scheme proved effective against traditional attacks like PCA and spectral filtering, as well as more sophisticated methods like MMSE. Figure 6 and 7 show that PCA reconstruction on perturbed data using PoolView's method yields results with little correlation to the original data, unlike when white noise is used.
  • Effective Malicious Server Detection: The client-side verification mechanism demonstrated a good trade-off between accepting legitimate servers and rejecting malicious ones, with safe thresholds identified for both model structure and parameter distribution checks.
  • Limited Impact of Malicious Users: The study showed that even with a significant percentage of malicious users (up to 500 in simulations), the impact on reconstruction error was minimal, suggesting the system is resilient to a certain level of data falsification.

Limitations and Future Work

  • Context Privacy Not Addressed: The paper explicitly states that context privacy (e.g., location and time of data collection) is not addressed by their techniques and is a separate research area.
  • Multi-Modal Data Correlation: The current work focuses on single-stream privacy. Future work aims to address privacy issues when multiple, potentially correlated, data streams are shared by clients.
  • Model Checking for Outliers: Investigating how to handle clients with data outliers is also suggested as a future research direction.
  • Scalability of Model Verification: While effective, the computational cost of model verification on the client side might be a consideration for resource-constrained devices.
  • Trust in Noise Model Generation: The paper acknowledges that the generation of the noise model itself relies on some prior knowledge or assumptions about the phenomenon, which could be a point of contention in highly novel sensing scenarios.

Summary updated

BibTeX
@inproceedings{ganti2008poolview,
  author = {Raghu K. Ganti and Nam Pham and Yu-En Tsai and Tarek F. Abdelzaher},
  title = {{PoolView: stream privacy for grassroots participatory sensing}},
  booktitle = {SenSys},
  year = {2008},
  doi = {10.1145/1460412.1460440},
}
Figure