XRay: Enhancing the Web's Transparency with Differential Correlation

Mathias Lécuyer, Guillaume Ducoffe, Francis Lan, Andrei Papancea, Theofilos Petsios, Riley Spahn, Augustin Chaintreau, Roxana Geambasu

TL;DR

This paper introduces XRay, a novel system that provides unprecedented transparency into how personal data is used by web services. By employing a "differential correlation" technique, XRay can pinpoint which specific user inputs (like emails or search queries) are used to generate targeted outputs (like ads or recommendations), even across different services, with high accuracy and scalability. This empowers users and auditors to understand and potentially challenge opaque data practices.

What Problem Does This Paper Address?

In today's "big data" world, web services like Google, Amazon, and Facebook collect and analyze vast amounts of personal data for various purposes, from personalization to targeted advertising and dynamic pricing. However, users often have little insight into how their data is being used, leading to a lack of informed choices and potential for data abuses. Existing tools are either too specialized, focus only on data leakage from a device, or require significant service-side changes. There's a critical need for a generic, robust, and scalable system that can track data within and across web services to reveal specific targeting mechanisms.

Methods

XRay's core innovation is its differential correlation mechanism. Instead of directly observing a service's internal logic (which is often proprietary), XRay compares outputs from multiple "shadow accounts" that have similar but not identical subsets of user data. By observing which outputs consistently appear when a specific data input is present across these shadow accounts, and absent when it's not, XRay can infer a correlation.

Key aspects of the method include:

  • Service Agnostic Design: XRay's core correlation engine is designed to work independently of specific web services.
  • Shadow Accounts: The system creates multiple "shadow" accounts for each user, each containing a carefully curated subset of the user's data.
  • Differential Correlation: By comparing outputs across these shadow accounts, XRay identifies data inputs that are strongly correlated with specific outputs.
  • Bayesian Inference: XRay employs Bayesian models to predict targeting and self-tune parameters, allowing it to adapt to different services and noise levels.
  • Input Matching: To handle "overlapping inputs" (where multiple distinct inputs might trigger similar targeting), XRay uses a novel system-level technique to group similar inputs, mimicking how the web service itself might group them. This significantly improves accuracy.

Datasets

The paper does not explicitly mention training datasets. Instead, XRay is evaluated using data generated from experiments on real-world web services:

  • Gmail: Emails were crafted to represent various categories and topics.
  • Amazon: Products were selected from specific categories.
  • YouTube: Videos were chosen based on AdSense categories.

The authors also created "workloads" for these services, including both non-overlapping (distinct categories) and overlapping (multiple items per category) scenarios.

Key Insights and Ideas

  • Transparency is Achievable: The paper demonstrates that it's possible to gain fine-grained insights into opaque web service targeting without direct access to their internal algorithms.
  • Differential Correlation is Powerful: Comparing outputs across subtly different data sets is a surprisingly effective way to infer targeting, even with limited data.
  • Scalability is Logarithmic: A major theoretical and empirical finding is that the number of shadow accounts needed for accurate tracking scales logarithmically with the number of data inputs, making it practical for real-world scenarios.
  • Input Matching is Crucial for Realism: Overlapping inputs, common in real-world data, significantly degrade accuracy without specialized handling. XRay's input matching, which groups inputs based on observed targeting behavior, is essential for practical effectiveness.
  • Behavioral and Contextual Targeting are Distinct: The paper shows that combining insights from both behavioral (past actions) and contextual (current content) targeting mechanisms leads to higher recall.

Key Results

  • High Accuracy: XRay achieved 80-90% precision and recall in experiments on Gmail, Amazon, and YouTube.
  • Scalability: The number of shadow accounts required grew logarithmically with the number of inputs, demonstrating practical scalability. For example, tracking 51 Gmail inputs required only 21 accounts to reach high accuracy.
  • Input Matching Effectiveness: With overlapping inputs, XRay's recall improved by a factor of 3 (from 30% to 93%) and precision by 2.6 times (from 34% to 88%) after implementing input matching.
  • Cross-Service Tracking: The system was able to track data use across services, for example, correlating YouTube activity with Gmail ads.
  • Revealing Targeted Practices: Experiments uncovered instances of sensitive topics (e.g., health, financial issues) being targeted by ads, and highlighted potential issues with semantic understanding in ad targeting.

Limitations and Future Work

  • Honest-but-Curious Model: XRay assumes web services are not actively trying to thwart its auditing efforts (e.g., by identifying and disabling shadow accounts). While robust against common defenses like spam filters, it could be challenged by malicious services.
  • Independent Targeting Assumption: The current algorithms assume targeting is independent across accounts and over time. Real-world scenarios like daily ad budgets or dynamic pricing might violate this, requiring future work to account for such dependencies.
  • Bounded Noise Hypothesis: The system assumes targeting noise is bounded and smaller than the targeting signal. Services with highly localized or complex decision-making (e.g., social networks using friend data) might present challenges.
  • Future Work: The authors suggest extending XRay to handle more complex targeting functions (e.g., disjunctive combinations), incorporating collaborative auditing approaches for increased robustness, and further investigating adversarial models. They also plan to explore detecting targeting based on linear combinations of inputs.

Summary updated

Abstract

Today's Web services - such as Google, Amazon, and Facebook - leverage user data for varied purposes, including personalizing recommendations, targeting advertisements, and adjusting prices. At present, users have little insight into how their data is being used. Hence, they cannot make informed choices about the services they choose. To increase transparency, we developed XRay, the first fine-grained, robust, and scalable personal data tracking system for the Web. XRay predicts which data in an arbitrary Web account (such as emails, searches, or viewed products) is being used to target which outputs (such as ads, recommended products, or prices). XRay's core functions are service agnostic and easy to instantiate for new services, and they can track data within and across services. To make predictions independent of the audited service, XRay relies on the following insight: by comparing outputs from different accounts with similar, but not identical, subsets of data, one can pinpoint targeting through correlation. We show both theoretically, and through experiments on Gmail, Amazon, and YouTube, that XRay achieves high precision and recall by correlating data from a surprisingly small number of extra accounts.
BibTeX
@inproceedings{lecuyer2014xray,
  author = {Mathias Lécuyer and Guillaume Ducoffe and Francis Lan and Andrei Papancea and Theofilos Petsios and Riley Spahn and Augustin Chaintreau and Roxana Geambasu},
  title = {{XRay: Enhancing the Web's Transparency with Differential Correlation}},
  booktitle = {USENIX Security},
  year = {2014},
  url = {https://openreview.net/forum?id=AGhn-itM8V7},
}
Figure