💻 computer science

Enhancing Stateful Detection of Adversarial Attacks with Soft-labels' Temporality and Robust Similarity Approximations

This paper proposes a two-phase stateful detection framework that enhances adversarial attack identification by leveraging the temporal correlation of soft-labels and introducing randomness to similarity matching, thereby achieving high true positive rates while mitigating false positives and vulnerabilities to approximation-based evasion attacks.

Original authors: De Zhang Lee, Han Fang, Ee-Chien Chang

Published 2026-06-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: De Zhang Lee, Han Fang, Ee-Chien Chang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the security guard at a high-security art gallery. Your job is to spot thieves who are trying to sneak in and steal the secrets of how your paintings are classified (which is what an AI model does).

In the world of AI, these "thieves" are called adversarial attackers. They don't break in with a crowbar; they send thousands of slightly tweaked images to the AI, asking "What is this?" over and over again. By analyzing the AI's answers, they slowly figure out how to trick the AI into misidentifying a picture of a cat as a dog.

This paper introduces a new, smarter way for the security guard to catch these thieves. Here is how it works, broken down into simple concepts:

The Old Way: The "Look-Alike" Detector

Previous security systems (like one called Blacklight) worked like a simple "Look-Alike" detector.

The Logic: Thieves have to send very similar images to trick the AI. So, if the guard sees 50 images that look almost identical, they assume, "Aha! This is a thief!"
The Problem: This system is too easily fooled.
1. False Alarms: Imagine a security camera filming a still scene. Every frame looks exactly the same. The old system would scream "THIEF!" at a harmless security camera feed.
2. The "Magic Mask": The paper discovered that thieves can wear a "magic mask." They can add tiny, invisible noise to their images. To the old system's quick check, the images look totally different (so no alarm), but to the actual AI, they are still very similar. The thieves slip right past the guard.

The New Solution: A Two-Phase Detective

The authors propose a two-step detective process that is much harder to fool.

Phase 1: The "Rough Sketch" Check (Similarity)

Instead of just checking if images look the same, the new system uses a Salted Randomized Quantization.

The Analogy: Imagine the old system was like comparing two photos by looking at them with the naked eye. The new system is like putting on goggles that randomly shift the colors every time you look.
How it helps: Even if a thief tries to use their "magic mask" to make the images look different, the random shifting in the goggles makes it nearly impossible for them to predict how the system will see the image. It's like trying to sneak past a guard who changes the rules of the game every second.
The Result: If a group of images passes this rough check and looks suspiciously similar, they get flagged for a second look.

Phase 2: The "Heartbeat" Check (Soft-Label Temporality)

This is the paper's biggest innovation. The system doesn't just look at the images; it listens to the AI's "thought process" over time.

The Analogy:
- Harmless Visitors (Benign): If you show the AI a sequence of photos of a cat, a dog, and a car, the AI's confidence levels (its "soft labels") will jump around randomly. It's like a person walking through a gallery, looking at different things with no pattern.
- The Thief (Adversarial): A thief is trying to find a specific "crack" in the wall. They ask, "Is this a cat?" The AI says "90% cat." The thief tweaks the image slightly and asks again. The AI says "85% cat." They keep tweaking. The AI's confidence levels will drift steadily in one direction as they get closer to the goal.
The Detection: The new system uses a statistical test (called the Ljung-Box test) to listen for this steady "drift" or "heartbeat" in the AI's answers.
- If the answers are random? Safe. (Even if the images look similar, like a security camera feed).
- If the answers show a steady, suspicious trend? Thief detected.

Why This Matters

The paper tested this new detective against the smartest thieves currently known (attacks like Boundary Attack, HSJA, and Square Attack).

The Score: The new system caught 100% of the thieves (True Positive Rate).
The Mistakes: It only made a mistake (flagging a harmless person) about 6% of the time, whereas the old systems made mistakes up to 42% of the time.
The "Magic Mask" Defense: When the thieves tried to use their "magic mask" (adaptive attacks) to bypass the system, the new system forced them to add so much noise to their images that the images became useless garbage. The thieves couldn't win without ruining their own attack.

In a Nutshell

The paper says: "Don't just look at how similar the questions are; listen to how the answers change over time. By adding a little bit of randomness to our checks and listening for the 'heartbeat' of a thief's strategy, we can catch them without accidentally arresting innocent security cameras."

Technical Summary: Enhancing Stateful Detection of Adversarial Attacks with Soft-labels' Temporality and Robust Similarity Approximations

Problem Statement

Deep Neural Networks (DNNs) are highly susceptible to black-box adversarial attacks, where adversaries craft imperceptible perturbations to cause misclassification. These attacks often rely on frequent, adaptive queries to probe the model's decision boundaries. Stateful Detection (SD) is a defense mechanism designed to identify such attacks by detecting sequences of similar queries.

However, existing SD methods (e.g., Blacklight, PIHA) face two critical limitations:

Vulnerability to Approximation Attacks: SD systems often use computationally efficient approximations (e.g., hashing, randomized quantization) of complex similarity metrics to detect similar queries. The authors observe that these approximations can be exploited. An adversary can craft queries that appear dissimilar under the approximation function but remain close under the intended metric, thereby evading detection. The paper refers to this as an "adversarial attack" on the similarity function.
High False Positive Rates (FPR): To minimize false positives, SD systems often set high similarity thresholds. However, this makes them vulnerable to adaptive probing attacks (e.g., Oracle-guided Adaptive Rejection Sampling, or OARS) that add random perturbations to reduce query similarity below the threshold. Furthermore, benign sequences with high similarity (e.g., CCTV stills) are frequently misidentified as malicious.

Methodology

The authors propose a two-phase detection framework that combines robust query similarity approximation with the temporal analysis of soft-labels.

Phase 1: Robust Similarity Detection

The first phase identifies subsequences of queries that are likely similar, utilizing a salted randomized quantization method to approximate the intended similarity metric.

Intended Metric: The paper defines an "intended similarity function" ( $D$ ) based on the minimum distance between sub-images (sliding windows) of two images.
Approximation Vulnerability: Standard approximations (like those in Blacklight) sample a subset of windows. The authors demonstrate that an adversary can introduce small distortions to reduce the overlap of these sampled windows, effectively creating an $(\epsilon, \delta)$ -adversarial example where the true distance is small ( $\le \epsilon$ ) but the approximated distance is large ( $\ge \delta$ ).
Proposed Solution: To mitigate this, the framework employs salted randomized quantization.
- A random salt is applied to the input before quantization.
- Values are randomly rounded up or down based on a Bernoulli distribution.
- This introduces randomness that is hidden from the adversary, making it difficult to reverse-engineer the quantization boundaries or craft specific perturbations to evade the hash matching.
- Similarity is determined by checking if a sufficient number of randomly selected, non-overlapping windows from the quantized query match previously seen windows in a Bloom filter database.

Phase 2: Temporal Correlation of Soft-Labels

Queries flagged as similar in Phase 1 are passed to Phase 2 to distinguish between benign similar sequences (e.g., video frames) and adversarial sequences.

Observation: Adversarial attacks adaptively generate queries based on previous model outputs (soft-labels), creating a temporal correlation in the sequence of soft-labels. In contrast, benign similar sequences (like CCTV stills) typically exhibit independent soft-labels over time.
Mechanism: The framework extracts the soft-label probabilities for the predicted class of the first query in the subsequence. It then applies the Ljung–Box test to this sequence to detect serial correlation.
Decision: If the $p$ -value of the Ljung–Box test falls below a predetermined threshold, the sequence is flagged as adversarial. This phase effectively filters out the false positives generated by Phase 1.

Key Contributions

Observation of Temporal Behavior: The authors identify that adversarial query sequences exhibit distinct temporal correlations in their soft-labels, which can be leveraged to distinguish them from benign similar queries.
Adversarial Attacks on Similarity Metrics: The paper introduces the concept of "adversarial attacks" on similarity approximation functions. It demonstrates a lightweight attack on Blacklight's similarity metric that allows an adversary to evade detection without requiring extensive probing.
Robust Similarity Approximation: The authors propose salted randomized quantization as a robust approximation method. By hiding the quantization boundaries via randomness, it prevents adversaries from easily crafting inputs that bypass the similarity check while maintaining detection accuracy.
Two-Phase Framework: A novel detection framework that lowers the similarity threshold in Phase 1 (increasing sensitivity) and uses soft-label temporal analysis in Phase 2 to filter false positives. This approach mitigates the trade-off between False Positive Rate (FPR) and vulnerability to adaptive attacks.
Empirical Validation: Comprehensive evaluation against state-of-the-art (SOTA) attacks and adaptive defenses.

Experimental Results

The framework was evaluated on CIFAR-10 and ImageNet datasets against five black-box attacks: Boundary Attack (BA), Hop Skip Jump Attack (HSJA), HSJA with frequency mixup, Square Attack (SA), and SimBA. It was also tested against adaptive attacks (OARS).

True Positive Rate (TPR): The proposed framework achieved a TPR of 1.00 across all tested attacks on both datasets, outperforming or matching tuned versions of Blacklight (which ranged from 0.42 to 0.97).
False Positive Rate (FPR): The framework maintained a low FPR of at most 0.06 (compared to 0.42 for other SOTA SD methods). This is attributed to Phase 2 successfully filtering out benign similar sequences (e.g., camera stills).
Robustness to Adaptive Attacks:
- When tested against OARS-enhanced attacks, the framework required the adversary to introduce a substantial amount of noise to bypass Phase 1.
- Crucially, none of the OARS-enhanced attacks (HSJA or Boundary Attack) succeeded in generating a valid adversarial example within 50,000 queries when defended by the proposed framework, whereas they succeeded against Blacklight.
Efficiency: The method incurs modest time and memory overhead. Storage is approximately 7.5 MB for Bloom filters and up to 17.9 MB for soft-label caches (ImageNet). Processing time is roughly 1.0 minute for CIFAR-10 and 2.5 minutes for ImageNet per 30,000 queries, reducible via multiprocessing.

Significance and Claims

The paper claims that its primary significance lies in addressing the vulnerability of existing SD systems to adaptive probing and approximation attacks. By integrating soft-label temporality, the authors argue that defenders can adopt lower similarity thresholds, thereby increasing the detection of adaptive attacks that rely on perturbing query similarity.

The authors emphasize that their approach is robust against "adversarial attacks" on the similarity function itself, a threat vector previously under-explored in SD literature. They conclude that their two-phase framework offers a practical, scalable, and highly accurate defense that outperforms current SOTA methods in both detection rates and robustness against adaptive evasion strategies.