Label Inference Attacks from Log-loss Scores

Abhinav Aggarwal, Shiva Prasad Kasiviswanathan, Zekun Xu, Oluwaseyi Feyisetan, Nathanael Teissier

Common wisdom in machine learning suggests that a single aggregate performance metric, such as a log-loss score, is a safe summary that reveals little about individual data points. This paper challenges that assumption, demonstrating that log-loss scores are surprisingly "leaky." The authors reveal that an adversary can reconstruct the entire ground truth labeling of a dataset using only reported log-loss scores, without ever seeing the features or training a single model.

Introduction and Problem Statement

In machine learning competitions (like Kaggle) and privacy-sensitive applications, models are frequently evaluated using log-loss (cross-entropy loss). Standard practice dictates keeping the test set labels private and only releasing the final aggregate loss score to the participant.

The authors investigate whether this score acts as a vulnerability. Specifically, they ask: Can an adversary—who can submit arbitrary prediction vectors and receive the resulting log-loss—infer the true labels? If so, a participant could "game" a competition by learning the test labels to build a perfect (but fake) classifier, or a malicious actor could extract sensitive information, such as medical diagnoses, from a private database.

Methodology: Label Inference Attacks

The researchers developed several "label inference attacks" based on the constraints of the attacker's environment, specifically regarding arithmetic precision and the presence of noise.

1. The Prime Factorization Attack (No Noise, Arbitrary Precision) For an adversary with arbitrary precision, the authors leverage the Fundamental Theorem of Arithmetic. By assigning a unique prime number to each data point, they demonstrate that the log-loss equation can be rearranged into a product of primes. Because every integer has a unique prime factorization, the attacker can simply factor the resulting score to determine which primes—and thus which labels—were present in the dataset.

2. Handling Bounded Precision (No Noise, Finite Precision) Real-world computers use finite floating-point precision (e.g., 64-bit) and cannot handle the massive numbers required for a single-query prime attack on large datasets. To bypass this, the authors introduce an algorithm that breaks the problem into multiple queries, inferring a small "chunk" of labels at a time.

3. The Subset Sum Attack (Noisy Scores) If a server adds noise to the score to protect privacy, the authors employ combinatorial techniques related to Sidon sequences and sets with distinct subset sums. They construct prediction vectors such that the loss scores for any two different labelings are separated by a margin larger than the maximum possible noise. This allows the attacker to "de-noise" the result and pinpoint the unique matching labeling.

The complexity and query requirements for these attacks are summarized below:

Table 1: Overview of results for binary label inference across different noise and precision models.

Key Insights and Mechanisms

  • Log-loss is a Product in Disguise: Because log-loss involves the logarithm of probabilities, exponentiating the score converts the sum back into a product. This mathematical structure is precisely what makes it vulnerable to prime-based encoding.
  • Model-Agnostic: These attacks do not require the attacker to know anything about the features (images, text, etc.) or the model architecture. The adversary only needs the ability to control the submitted prediction vector.
  • The Precision-Query Tradeoff: There is a direct relationship between the available bits of arithmetic precision and the number of queries needed. Higher precision allows an attacker to pack more labels into a single query.
  • Noise is Not a Silver Bullet: Even if a system adds noise to the scores, an attacker can still recover labels by ensuring the "signal" (the difference between possible loss scores) outscales the noise.

Experimental Setup and Results

The authors evaluated their attacks on simulated datasets (randomly generated binary strings up to $N=10,000$) and real-world binary classification datasets from the UCI repository, including IMDB movie reviews ($N=25,000$), Banknote authentication ($N=1,372$), and Wisconsin Cancer data ($N=569$).

The results highlight the severe practical threat of these vulnerabilities:

  • Efficiency: On the IMDB dataset ($N=25,000$), the bounded-precision attack achieved 100% accuracy in just 53.41 milliseconds using $N/5$ queries.
  • Robustness: In the noisy setting, the researchers successfully recovered all labels even when the injected noise was as high as 100% of the raw log-loss score.
  • Scalability: While previous heuristic attacks struggled to scale, these number-theoretic approaches handle tens of thousands of data points with ease.

Limitations and Future Defenses

While highly effective, the attacks face practical limitations. The most robust attacks require multiple queries; if a platform strictly limits the number of submissions, execution becomes significantly harder. Furthermore, the theoretical case of arbitrary precision with noise requires exponential time to find the best-fit labeling, though polynomial-time alternatives exist for bounded precision.

To defend against these vulnerabilities, the authors suggest platforms could employ Warner’s randomized response (adding noise directly to the labels before calculating the loss) or report scores based on a randomly chosen, unknown subset of the data. Determining the optimal balance between utility and these privacy defenses remains a critical area for future research.

Summary updated

Abstract

Log-loss (also known as cross-entropy loss) metric is ubiquitously used across machine learning applications to assess the performance of classification algorithms. In this paper, we investigate the problem of inferring the labels of a dataset from single (or multiple) log-loss score(s), without any other access to the dataset. Surprisingly, we show that for any finite number of label classes, it is possible to accurately infer the labels of the dataset from the reported log-loss score of a single carefully constructed prediction vector if we allow arbitrary precision arithmetic. Additionally, we present label inference algorithms (attacks) that succeed even under addition of noise to the log-loss scores and under limited precision arithmetic. All our algorithms rely on ideas from number theory and combinatorics and require no model training. We run experimental simulations on some real datasets to demonstrate the ease of running these attacks in practice.
BibTeX
@inproceedings{aggarwal2021label,
  author = {Abhinav Aggarwal and Shiva Prasad Kasiviswanathan and Zekun Xu and Oluwaseyi Feyisetan and Nathanael Teissier},
  title = {{Label Inference Attacks from Log-loss Scores}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=1M5O6gUilr},
}
Figure