While gradient-based and optimization-based attacks leverage detailed model information (gradients), and score-based attacks use output probabilities, there exists an even more restrictive scenario: what if the attacker only receives the final prediction label (e.g., "cat" or "dog") from the model? This is known as the hard-label black-box setting. Decision-based attacks are designed specifically for this challenging situation, making them relevant for attacking systems where output scores are withheld or quantized.

The fundamental difficulty lies in finding a direction to modify the input $x$ to make it adversarial without any gradient or score information to guide the search. Decision-based methods essentially perform a clever search, often requiring many queries to the model to infer information about the location of the decision boundary.

The Boundary Attack

One of the most prominent decision-based techniques is the Boundary Attack. It operates based on a simple yet effective intuition:

Start with an input that is already adversarial. This initial adversarial example $x_{adv}^{(0)}$ doesn't need to be close to the original input $x$ ; it could even be random noise that happens to be misclassified as the target class, or an adversarial example generated through other means (like a transfer attack).
Iteratively refine the adversarial example $x_{adv}^{(t)}$ to make it closer to the original input $x$ while ensuring it remains adversarial.

The core idea is to "walk" along the decision boundary between the original class and the target adversarial class. At each step $t$ , the algorithm attempts to find a new point $x_{adv}^{(t+1)}$ by taking a small step from $x_{adv}^{(t)}$ . This step is carefully chosen:

Direction: The step is typically taken in a random direction, but constrained to be roughly tangential to the boundary. The goal is to move along the boundary towards $x$ , not directly towards it (which might cross back into the original class) or directly away from it (which increases the perturbation).
Magnitude: The step size is adjusted. If a proposed step makes the example correctly classified, the step size is reduced to stay closer to the boundary.
Criterion: A step is accepted if the new candidate $x'_{adv}$ $x_{a d v}^{'}$ satisfies two conditions:
- It remains adversarial: $f(x'_{adv}) \neq f(x)$ .
- It reduces the distance to the original input: $||x'_{adv} - x||_p < ||x_{adv}^{(t)} - x||_p$ for a chosen norm $p$ (usually $p=2$ ).

This iterative process gradually reduces the perturbation magnitude $||x_{adv}^{(t)} - x||_p$ , finding adversarial examples that are progressively closer to the original input.

2d illustration of the Boundary Attack. Starting from an initial adversarial point (red), the attack iteratively moves along the decision boundary (dashed line) towards the original input (blue), maintaining the adversarial classification while reducing the perturbation distance.

Query Complexity and Other Methods

A significant characteristic of decision-based attacks is their query complexity. Because they lack direct gradient or score information, they must query the model many times (often thousands or even millions) to make progress. Each query involves sending a candidate input to the model and observing the output label. This makes them potentially slow and expensive, especially if the model has rate limits or query costs.

While the Boundary Attack is foundational, other decision-based methods exist, such as:

HopSkipJumpAttack: Builds upon the ideas of boundary exploration, often achieving better query efficiency or finding smaller perturbations compared to the original Boundary Attack.
Sign-OPT: Uses optimization techniques guided by estimations of the gradient direction obtained using only decision outcomes.

These methods generally attempt to improve the search strategy to reduce the number of required queries.

Advantages and Disadvantages

Advantages:

Minimal Information Required: They work even when only the final predicted label is available, making them applicable to highly restrictive black-box systems.
Broad Applicability: They don't rely on model differentiability or specific architectures.

Disadvantages:

High Query Cost: Often require a very large number of model queries, making them impractical in many real-world scenarios with query limits or costs.
Potentially Larger Perturbations: Compared to white-box attacks like PGD or C&W, decision-based attacks might sometimes find adversarial examples with larger $L_p$ distortions, although they aim to minimize this.
Slower Convergence: Finding a high-quality adversarial example can take considerable time due to the iterative nature and high query count.

Decision-based attacks represent the extreme end of the spectrum in evasion attacks concerning attacker knowledge. Understanding these methods is important for evaluating security in scenarios where model internals and outputs are heavily guarded. They demonstrate that even with minimal feedback, vulnerabilities can still be exploited, albeit often at a higher computational cost.