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:
- 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