Decision Boundary Attack

Unlike Projected Gradient Descent (PGD) or Carlini & Wagner (C&W) attacks, decision boundary attacks require zero access to model gradients or confidence scores. The attacker only needs the hard-label output—the final class decision. The attack formulates the search as a constrained optimization problem, walking along the boundary that separates the true class from the target class. Starting from a large adversarial perturbation, the algorithm iteratively reduces distortion by projecting perturbations toward the original input while maintaining misclassification, effectively solving for the minimal adversarial example through geometric probing.

The core mechanism relies on rejection sampling along the decision boundary. The attack initializes with a sample already classified as the target class, then performs a binary search toward the original input to find the precise boundary crossing point. Once on the frontier, it estimates the local geometry of the boundary through random perturbations orthogonal to the direction of the original sample. By repeatedly sampling and projecting, the attack walks along the boundary toward regions where the distance to the original input is minimized, effectively discovering the minimum-norm adversarial perturbation without ever computing a gradient.

Decision boundary attacks are inherently query-intensive compared to white-box methods, often requiring tens of thousands of model queries to converge. The HopSkipJumpAttack variant improves efficiency by using gradient estimation at the boundary through finite differences of hard-label outputs. Key efficiency factors include:

• Initial perturbation magnitude: Starting closer to the target reduces iterations
• Boundary geometry complexity: Highly non-linear boundaries require more exploration
• Dimensionality: High-dimensional input spaces increase search difficulty
• Step size scheduling: Adaptive step sizes balance convergence speed and precision

To reduce query counts, practitioners often bootstrap decision boundary attacks with adversarial examples generated from surrogate models. A perturbation crafted against a known white-box model is transferred to the black-box target. If the transferred example already causes misclassification, the boundary attack only needs to refine and minimize the perturbation rather than discover it from scratch. This hybrid approach combines the low query cost of transfer attacks with the precision of boundary optimization. The effectiveness depends on the architectural similarity between surrogate and target models, with shared training data distributions significantly improving transfer rates.

Decision boundary attacks naturally circumvent several common defenses:

• Gradient masking: Since no gradients are used, obfuscated or shattered gradients provide no protection
• Defensive distillation: The attack operates on hard labels unaffected by temperature scaling
• Confidence thresholding: Only the final class decision matters, not confidence scores
• Detection-based defenses: Minimal perturbations near the boundary are harder to detect than large-norm attacks However, adversarial training remains effective because it fundamentally reshapes the decision boundary to be smoother and farther from natural inputs, increasing the minimum distortion required for any attack class.

Decision boundary attacks model realistic threat scenarios where adversaries interact with API-only model deployments. Examples include:

• Cloud vision APIs: Attacking Google Cloud Vision or AWS Rekognition with only label outputs
• Content moderation filters: Evading text or image classifiers deployed behind rate-limited endpoints
• Autonomous agent perception: Probing embodied agent object detectors through query feedback loops
• Malware classifiers: Crafting evasive binaries by iteratively querying antivirus engine verdicts The attack's reliance on hard-label queries makes it directly applicable to production systems that expose only classification decisions to end users.

The parent category of decision boundary attacks, executed without access to model gradients or architecture. The attacker only observes input-output pairs through a query interface.

• Score-based: Attacker receives confidence scores or logits
• Decision-based: Attacker receives only the hard-label prediction
• Decision boundary attacks operate in the decision-based subcategory, making them applicable against real-world APIs that return only class labels

The broader attack class that decision boundary attacks fall under. Evasion attacks modify input samples at inference time to cause misclassification without altering the trained model.

• Does not require training pipeline access
• Exploits the model's learned decision surface
• Decision boundary attacks are a query-efficient variant that walks along the classification frontier to find minimal perturbations

The output artifact produced by a decision boundary attack: an input perturbed in a way imperceptible to humans that causes confident misclassification.

• Decision boundary attacks specifically seek minimally distorted adversarial examples
• The perturbation magnitude is measured using Lp-norms (typically L2 distance)
• Unlike gradient-based methods, these examples are found through geometric exploration of the decision frontier

A white-box optimization-based attack that shares the same objective as decision boundary attacks: finding minimal perturbations that cause misclassification.

• Uses a margin-based loss function to defeat defensive distillation
• Formulated as an optimization problem with L0, L2, or L∞ distance constraints
• Decision boundary attacks achieve similar results in the black-box setting where C&W cannot operate due to its gradient requirements

A powerful white-box iterative attack that contrasts sharply with decision boundary methods. PGD requires full gradient access and repeatedly steps toward the loss gradient, projecting back onto an epsilon-ball.

• Decision boundary attacks are the black-box counterpart when gradients are unavailable
• PGD evaluates robustness under a fixed perturbation budget
• Decision boundary attacks discover the true minimum distance to the decision frontier, providing a complementary robustness metric

The defensive property that decision boundary attacks are designed to evaluate. Robustness is quantified as the minimum perturbation magnitude required to change a classification.

• Decision boundary attacks provide a direct measurement of this minimum distance
• They serve as an evaluation tool for certified defenses like randomized smoothing
• A model with a large mean distance to the decision boundary across samples exhibits higher empirical robustness