A cryptographic approach to black box adversarial machine learning

Kevin Shi, Daniel Hsu, Allison BishoparXiv 2019 · arXiv

Introduction

Machine learning models, even when deployed as black boxes behind APIs, remain vulnerable to adversarial attacks. This vulnerability stems from transferability: an attacker can train a substitute model, generate adversarial examples for it, and successfully transfer those attacks to the target system. This paper proposes a novel defense that treats model security as a cryptographic challenge, using a "secret key" of hidden random label-splits to create a classifier provably resistant to such transfer attacks.

The Transferability Problem

Traditional defenses often focus on making a single model robust. However, because most models learn similar decision boundaries for the same task, an attacker's substitute model often mirrors the target's weaknesses. The authors aim for computational separation: ensuring that even if an adversarial example exists, finding it is computationally infeasible without knowledge of the model's internal "key."

Methodology: Randomized Ensemble with Secret Keys

The proposed defense uses a Randomized Ensemble Classifier based on error-correcting codes:

  1. The Secret Key ($Z$): A random matrix $Z$ maps each of $N$ classes to a unique binary codeword of length $M$.
  2. The Ensemble: The system trains $M$ independent binary classifiers. Each classifier $j$ distinguishes between two random groups of classes defined by the $j$-th column of $Z$.
  3. Inference & Abstention: Predicted codewords are compared to valid codewords in $Z$ using Hamming distance. If the distance exceeds a threshold $r$, the model abstains (outputs $\omega$), effectively detecting adversarial noise.
  4. Cryptographic Reduction: A mathematical proof demonstrates that attacking the ensemble is as hard as attacking a single random binary classifier. Without knowing $Z$, an attacker cannot easily train a substitute model that mimics the ensemble's specific decision boundaries.

Empirical Evaluation

The defense was tested on MNIST and CIFAR-10 using the CleverHans library with Projected Gradient Descent (PGD) and Momentum Iterative Gradient Method (MIGM).

Heatmap comparison of MIGM and PGD attacks at $\epsilon=8$.

As shown in the heatmaps above, the defense maintains structure across different attack types. Notably, a vertical band appears at class 6 (Frog), indicating its unique vulnerability—a phenomenon where certain classes are so distinct that random splits fail to hide their features.

Key Insights

  • Security through Randomness: By hiding the mapping of multiclass problems to binary tasks, the "key space" becomes exponentially larger as the number of classes $N$ increases.
  • Abstention as a Defense: Forcing an attacker to not only cause misclassification but to mimic a specific valid codeword significantly raises the bar for successful attacks.
Score distributions for MIGM on specific class pairs (5,3) and (4,6).

The histograms illustrate the distribution of scores for specific class pairs. The concentration of scores helps define the threshold $r$ for abstention, balancing natural accuracy against adversarial rejection. For the (4,6) pair (Deer vs. Frog), the skewed distribution highlights the "Frog outlier" effect mentioned in the study.

Conclusion

While the method introduces computational overhead and is currently incompatible with standard robust training, it provides a powerful framework for black-box security. By shifting the focus from boundary robustness to cryptographic secrecy, it offers a new path for securing sensitive ML APIs.

Summary updated

Abstract

We propose a new randomized ensemble technique with a provable security guarantee against black-box transfer attacks. Our proof constructs a new security problem for random binary classifiers which is easier to empirically verify and a reduction from the security of this new model to the security of the ensemble classifier. We provide experimental evidence of the security of our random binary classifiers, as well as empirical results of the adversarial accuracy of the overall ensemble to black-box attacks. Our construction crucially leverages hidden randomness in the multiclass-to-binary reduction.
BibTeX
@misc{shi2019cryptographic,
  author = {Kevin Shi and Daniel Hsu and Allison Bishop},
  title = {{A cryptographic approach to black box adversarial machine learning}},
  year = {2019},
  eprint = {1906.03231},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.03231},
}
Figure