🤖 machine learning

Accelerating Targeted Hard-Label Adversarial Attacks in Low-Query Black-Box Settings

This paper introduces the Targeted Edge-informed Attack (TEA), a novel black-box adversarial attack method that leverages edge information from the target image to significantly reduce query counts and improve efficiency compared to existing state-of-the-art techniques in low-query settings.

Original authors: Arjhun Swaminathan, Mete Akgün

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arjhun Swaminathan, Mete Akgün

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

The Big Picture: The "Guessing Game" Gone Wrong

Imagine you are playing a high-stakes game of "Guess the Picture."

The AI (The Guard): It looks at a photo of a Cat and confidently says, "That's a Cat!"
The Attacker (You): You want to trick the AI into thinking that same photo is actually a Dog.
The Catch (Black-Box): You can't see the AI's brain or how it thinks. You can only show it a picture, and it will only tell you the final label (e.g., "Cat" or "Dog"). It won't tell you how close you are to being right.
The Limit (Low-Query): You only have a tiny number of guesses (queries) before the game ends. If you run out of guesses, you lose.

The Problem: Current methods of tricking the AI are like a blindfolded person trying to find a specific door in a massive, dark warehouse. They wander around, bumping into walls, wasting their few guesses just trying to figure out where the walls are. By the time they find the door, they've run out of guesses.

The Solution: TEA (Targeted Edge-Informed Attack)

The authors propose a new strategy called TEA. Instead of blindly wandering, TEA uses a "map" drawn from the target image itself.

Here is the analogy: The Sculptor vs. The Blind Hiker.

1. The Old Way (Blind Hiker)

Imagine you have a block of marble (the Target Image: a Dog) and you want to carve it into a statue that looks like a Cat (the Source Image), but you must keep the label "Dog" until the very last second.

Old Attackers: They are blindfolded. They chip away at the marble randomly, asking the AI, "Is it a Dog yet?" If the AI says "No," they chip again. They waste most of their energy just trying to find the right shape because they don't know which parts of the stone are important.

2. The TEA Way (The Sculptor with a Map)

TEA is like a sculptor who knows exactly what the final statue should look like, but also knows the rules of the game.

The Secret Weapon (Edges): TEA looks at the "Dog" image and identifies the edges—the sharp lines that define the ears, the nose, and the tail. These are the "skeleton" of the image.
The Strategy:
- Don't touch the skeleton: TEA knows that if you mess up the sharp lines (edges), the AI will immediately scream, "That's not a Dog!"
- Smooth out the rest: TEA only changes the "smooth" areas (the fur, the background, the empty space). It slowly morphs the smooth parts of the Dog into the smooth parts of the Cat.
- The Result: Because it preserves the "skeleton," the AI keeps saying "Dog" for much longer, even as the image starts looking more like a Cat. This allows TEA to get very close to the Cat shape using very few guesses.

How It Works in Two Steps

Step 1: The Global Sweep (Zooming Out)
TEA starts by looking at the whole picture. It gently pushes the "smooth" parts of the Dog image toward the Cat image, like smoothing out a blanket. It ignores the sharp lines (edges) so the AI doesn't get suspicious. This gets the image 80% of the way there very quickly.

Step 2: The Patch Work (Zooming In)
Once the big picture is close, TEA zooms in on small, random patches (like a tiny square of the dog's ear). It makes tiny, precise adjustments to these patches, again avoiding the sharp lines. It's like doing fine-tuning on a sculpture.

The "Switch":
Once TEA has done its magic and the image is very close to the target, it hands the baton to an older, more complex method (called CGBA-H) to finish the job. Think of TEA as the sprinter who gets you to the finish line quickly, and the other method as the marathon runner who ensures you cross the line perfectly.

Why Is This a Big Deal?

The paper tested this on famous AI models (like ResNet and VGG) and found:

70% Fewer Guesses: To trick the AI, TEA needed only about 250 guesses, while the best previous methods needed 850.
Real-World Impact: Many commercial AI systems (like those used by banks or security cameras) limit how many times you can ask them questions to prevent hacking. TEA is so efficient that it can break these systems before they even realize what's happening.
Works Everywhere: It worked on different types of AI, different image sizes, and even on modern "Zero-Shot" models (AI that hasn't been specifically trained on the data you are attacking).

The "So What?" (Broader Impact)

The Good News: This helps security experts understand how weak their AI defenses are. If an attacker can break a system with only 250 guesses, the system is too vulnerable.

The Bad News: This makes it easier for bad actors to hack into real-world systems (like self-driving cars or medical diagnostic tools) without getting caught.

The Takeaway: The authors are essentially saying, "We found a shortcut to break these locks. Now, you need to build better locks that pay attention to the shape and structure of the image, not just the colors."

Summary in One Sentence

TEA is a smart, efficient hacker that tricks AI by carefully preserving the "outline" of an image while secretly morphing the rest of it, allowing it to break into systems using a fraction of the guesses required by older methods.

1. Problem Statement

The paper addresses the challenge of targeted hard-label adversarial attacks in black-box settings.

Context: Deep neural networks are vulnerable to adversarial examples (imperceptible perturbations causing misclassification).
Constraints:
- Hard-Label (Decision-Based): The attacker only receives the top-1 predicted label, not confidence scores or gradients.
- Black-Box: The attacker has no access to the model's internal parameters.
- Low-Query Budget: Real-world scenarios (e.g., commercial APIs) often limit the number of queries (e.g., <1,000).
The Specific Challenge: Targeted attacks (forcing an image $x_t$ to look like a source $x_s$ while maintaining the label of $x_t$ ) are harder than untargeted attacks because the decision regions for specific target classes are narrow and isolated.
Limitation of Current SOTA: Existing state-of-the-art methods (e.g., HSJA, CGBA-H) rely on geometry-based approaches (tracing decision boundaries or estimating local gradients). These methods are inefficient in the early stages of an attack when the adversarial image is far from the source image and the decision space is wide. They "burn through" queries trying to estimate local geometry before reaching a narrow region where such geometry is useful.

2. Methodology: Targeted Edge-Informed Attack (TEA)

The authors propose TEA, a novel attack strategy that leverages edge information from the target image rather than relying on local decision boundary geometry. The core hypothesis is that preserving low-level structural features (edges) helps maintain the target classification while allowing the image to move closer to the source.

TEA operates in two distinct phases:

Phase A: Global Edge-Informed Search

Goal: Coarsely align the target image ( $x_t$ ) toward the source image ( $x_s$ ) while preserving the target class label.
Mechanism:
1. Soft Edge Mask Generation: Edges are detected in $x_t$ using the Sobel operator. A Gaussian blur is applied to create a "soft edge mask" ( $M_{edge}$ ), where edge regions have values near 1 and smooth regions near 0.
2. Masked Interpolation: The algorithm iteratively updates the image using a momentum-based search. The update rule is:
  $x_{k+1} \leftarrow x_k + \alpha (x_s - x_k) \odot (I - M_{edge})$
  Here, $\odot$ is the element-wise product. The term $(I - M_{edge})$ ensures that interpolation (moving toward the source) only occurs in non-edge (smooth) regions. Edge regions are preserved to maintain the semantic structure required for the target classification.
3. Termination: This phase continues until improvements plateau (consecutive queries fail to reduce distance).

Phase B: Patch-Based Edge-Informed Search

Goal: Refine local discrepancies after the global alignment.
Mechanism:
1. Patch Selection: The image is partitioned into randomly selected patches of varying sizes.
2. Local Masking: A local soft edge mask is applied to the patch.
3. Gaussian Weighting: Updates within the patch are weighted by a Gaussian function to avoid artificial edges at patch boundaries.
4. Optimization: The algorithm searches for the largest step size $\beta$ such that the classifier still predicts the target label.
5. Termination: The process stops after a set number of iterations with no improvement (e.g., 25 consecutive failures).

Hybrid Strategy (TEA*)

Once TEA reduces the distance to a point where the image enters a "narrow decision space," the method switches to a geometry-based state-of-the-art method (CGBA-H) for final refinement. This hybrid approach is denoted as TEA*.

3. Key Contributions

Novel Attack Strategy (TEA): Introduction of an edge-informed perturbation strategy that prioritizes non-edge regions. This allows for rapid progress in the early stages of an attack without needing gradient estimation.
Two-Stage Process: A global search followed by a patch-based local refinement, specifically designed to avoid wasting queries in wide decision spaces.
Significant Efficiency Gains: TEA achieves a 70% reduction in query count compared to the second-best method (AHA) to achieve a 60% reduction in distance.
- Example: To reach a 60% distance reduction, TEA used an average of 251 queries, whereas AHA required 845 queries.
Improved Initialization: TEA provides a superior initialization point for existing geometry-based attacks, enhancing their performance in high-query regimes.

4. Experimental Results

The authors evaluated TEA on the ImageNet validation set (1,000 source-target pairs) across four architectures: ResNet-50, ResNet-101, VGG16, and ViT. They also tested on adversarially trained models and zero-shot CLIP.

Low-Query Performance:
- TEA consistently outperformed HSJA, AHA, CGBA, and CGBA-H in the low-query regime (<1,000 queries).
- AUC (Area Under Curve): TEA achieved the lowest Area Under the Curve for $\ell_2$ distance vs. queries, indicating the fastest rate of distance reduction.
- Success Rate (ASR): TEA achieved higher Attack Success Rates for 50% and 75% distance reductions within fixed query budgets (e.g., 500 queries).
Robustness:
- Adversarially Trained Models: TEA maintained an advantage over baselines even against ResNet-50 trained with adversarial examples.
- Zero-Shot CLIP: TEA was effective against a zero-shot ViT-B/32 CLIP classifier.
- Other Datasets: Results on CIFAR-100 and the Intel Image Classification dataset confirmed the method's generalizability across different resolutions and data distributions.
Ablation Studies:
- Edge Preservation: Perturbing non-edge regions (TEA) was significantly better than perturbing edge regions (INV-TEA) or random regions (HALF-TEA).
- Stability: The random patch selection introduced minimal variance (standard deviation < 0.3) across multiple runs.
Perceptual Quality: While TEA introduces structured perturbations, it maintains high perceptual similarity (FSIM) and achieves lower $\ell_2$ distortion than competitors.

5. Significance and Implications

Real-World Relevance: The method is specifically optimized for scenarios with strict query limits (e.g., pay-per-query APIs), where current geometry-based methods fail to converge efficiently.
Paradigm Shift: Instead of relying on the geometry of the decision boundary (which is hard to estimate far from the boundary), TEA utilizes intrinsic image features (edges) to guide the attack.
Defense Implications: The authors note that because TEA preserves edge structures, standard defenses based on frequency analysis or texture suppression may be less effective. They advocate for defenses that explicitly check for edge-informed distortions.
Limitations: TEA is most effective as an initialization or in low-query settings. When combined with high-query geometry methods, the final performance is comparable to the underlying SOTA method, not strictly superior. Additionally, patch-based updates can sometimes introduce localized artifacts visible to humans.

In conclusion, TEA represents a significant advancement in efficient black-box adversarial attacks by decoupling the initial search strategy from decision boundary geometry and instead leveraging the structural integrity of the target image.