Query Provenance Analysis for Robust and Efficient Query-based Black-box Attack Defense

Shaofei Li, Ziqi Zhang, Haomin Jia, Ding Li, Yao Guo, Xiangqun ChenarXiv 2024 · OpenReview

TL;DR

This paper introduces Query Provenance Analysis (QPA), a novel defense mechanism for machine learning models against query-based black-box attacks. QPA leverages the historical relationships between sequential queries, represented as a graph, to detect malicious patterns more effectively than existing methods, achieving significantly lower attack success rates and improved efficiency.

What Problem Does This Paper Address?

Machine learning models, especially those deployed as services (MLaaS), are increasingly vulnerable to "black-box" adversarial attacks. In these attacks, adversaries don't need full knowledge of the model's internals; they can simply query the model repeatedly with slightly modified inputs to generate "adversarial examples" that cause misclassification. Existing defenses, known as Stateful Defense Models (SDMs), try to detect these attacks by identifying queries that are too similar to past queries. However, a new class of "adaptive" attacks, like Oracle-guided Adaptive Rejection Sampling (OARS), can cleverly bypass these SDMs by fine-tuning their queries based on the defense's feedback, achieving very high success rates. The core problem is developing a defense that is both robust against these sophisticated adaptive attacks and efficient enough for real-time deployment.

Methods

The authors propose Query Provenance Analysis (QPA), a defense that shifts focus from individual queries to the sequence of queries – what they call "query provenance." The key idea is that malicious query sequences exhibit structured patterns due to the iterative nature of attacks, while benign queries are more random.

Here's how it works:

  • Query Provenance Graph: Each incoming query is linked to its most similar historical queries, forming a graph. This graph captures the relationships and similarities between queries over time.
  • Two-Phase Detection:
    1. Statistics Analysis: A lightweight initial step calculates a "Provenance Anomaly Score" (PAS) for each query provenance graph. This score reflects the overall similarity within the graph. Grubbs's test is used to identify potential outliers (suspicious graphs).
  • Graph Classifier: A more sophisticated Graph Neural Network (GNN) then analyzes the PAS and the graph's structure to make a final decision, reducing false positives.
  • Dynamic Management: To handle the potentially infinite growth of query history, QPA employs a graph eviction strategy (keeping suspicious graphs in memory, offloading benign ones) and periodic graph resets to maintain efficiency.

Datasets

The authors evaluated their system on four widely-used image classification datasets:

  • MNIST
  • CIFAR10
  • ImageNet
  • CelebaHQ

Key Insights and Ideas

  • Sequence Matters More Than Single Queries: The most crucial insight is that the pattern of queries over time (provenance) is a much stronger indicator of malicious activity than the similarity of any single query to past ones. Adversarial attacks create structured sequences, while normal user behavior is more erratic.
  • Adaptive Attacks Can't Hide Everything: Even sophisticated adaptive attacks that can evade individual query similarity checks still leave a traceable "fingerprint" in the query sequence's structure.
  • Graphs as a Natural Representation: Representing query history as a graph is an intuitive and powerful way to capture the complex relationships between queries.
  • GNNs for Graph Analysis: Graph Neural Networks are well-suited for learning from the structure and features of these query provenance graphs.

Key Results

QPA demonstrated significant improvements over existing defenses (BlackLight and PIHA):

  • Robustness:
    • Reduced the Attack Success Rate (ASR) of the OARS adaptive attack to an average of 4.08%, a massive reduction compared to baselines (77.63% for BlackLight, 87.72% for PIHA).
  • Achieved excellent detection coverage and precision for non-adaptive attacks, with a very low False Positive Rate (FPR) of 0.04% on average.
  • Efficiency:
    • Achieved significantly higher throughput: 7.67x faster than BlackLight and 2.25x faster than PIHA.
  • Lower latency: 3.39x to 11.09x faster than BlackLight and 1.59x to 4.49x faster than PIHA.

Limitations and Future Work

  • Feature Extractor Dependency: The effectiveness of QPA relies on the chosen feature extractor for calculating query similarity. The authors suggest that defenders should carefully select this component based on the deployment scenario.
  • Storage Overhead: QPA requires storing query provenance graphs, leading to additional memory and disk usage. However, they argue this is manageable as the number of edges is proportional to the number of nodes.
  • Hyperparameter Tuning: QPA's performance is sensitive to hyperparameters like minimum graph size (s) and the number of top graphs to retain (K). The authors recommend tuning these based on specific deployment contexts.
  • Future Work: The paper suggests exploring new challenges for stronger black-box attack algorithms and adaptive strategies.

Summary updated

Abstract

Query-based black-box attacks have emerged as a significant threat to machine learning systems, where adversaries can manipulate the input queries to generate adversarial examples that can cause misclassification of the model. To counter these attacks, researchers have proposed Stateful Defense Models (SDMs) for detecting adversarial query sequences and rejecting queries that are "similar" to the history queries. Existing state-of-the-art (SOTA) SDMs (e.g., BlackLight and PIHA) have shown great effectiveness in defending against these attacks. However, recent studies have shown that they are vulnerable to Oracle-guided Adaptive Rejection Sampling (OARS) attacks, which is a stronger adaptive attack strategy. It can be easily integrated with existing attack algorithms to evade the SDMs by generating queries with fine-tuned direction and step size of perturbations utilizing the leaked decision information from the SDMs. In this paper, we propose a novel approach, Query Provenance Analysis (QPA), for more robust and efficient SDMs. QPA encapsulates the historical relationships among queries as the sequence feature to capture the fundamental difference between benign and adversarial query sequences. To utilize the query provenance, we propose an efficient query provenance analysis algorithm with dynamic management. We evaluate QPA compared with two baselines, BlackLight and PIHA, on four widely used datasets with six query-based black-box attack algorithms. The results show that QPA outperforms the baselines in terms of defense effectiveness and efficiency on both non-adaptive and adaptive attacks. Specifically, QPA reduces the Attack Success Rate (ASR) of OARS to 4.08%, comparing to 77.63% and 87.72% for BlackLight and PIHA, respectively. Moreover, QPA also achieves 7.67x and 2.25x higher throughput than BlackLight and PIHA.
BibTeX
@misc{li2024query,
  author = {Shaofei Li and Ziqi Zhang and Haomin Jia and Ding Li and Yao Guo and Xiangqun Chen},
  title = {{Query Provenance Analysis for Robust and Efficient Query-based Black-box Attack Defense}},
  year = {2024},
  eprint = {2405.20641},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.20641},
}
Figure