In a standard black-box threat model, an attacker interacts with a machine learning model by providing an input and receiving a vector of continuous confidence scores (soft labels). This continuous feedback allows the attacker to approximate the loss gradient using zeroth-order optimization techniques, such as finite differences. By observing how minor tweaks to the input cause fractional shifts in the output probabilities, the attacker can map out a path toward a successful adversarial perturbation.
However, real-world commercial APIs and deployed systems frequently implement security and privacy measures that restrict outputs to a single top-1 prediction or a binary decision. This constraint is known as the hard-label setting or decision-based feedback constraint (Jie Li et al.).
Soft-Label Setting (Continuous Feedback)
Input x ───> [ Model ] ───> [0.12, 0.85, 0.03] (Rich gradient signal)
Hard-Label Setting (Discrete Feedback)
Input x ───> [ Model ] ───> "Cat" (Zero local gradient signal)
This restriction creates a severe information bottleneck. If you perturb an image or a text sequence slightly within a hard-label system, the discrete output label remains exactly the same. The continuous probability landscape is flattened into a series of discrete plateaus separated by sudden step-like drops. Because the local gradient is zero almost everywhere, standard optimization techniques fail entirely. To bypass this constraint, researchers must shift their focus from estimating local loss slopes to explicitly locating and navigating the model's decision boundaries.
Walking the Decision Boundary
To overcome the lack of granular feedback, decision-based attacks invert the traditional adversarial paradigm. Instead of starting with a benign image and incrementally pushing it until it crosses the decision boundary, the foundational approach proposed by Brendel et al. starts from the opposite direction.
The attack begins with a source image that is already deep within the adversarial territory (for example, an image of a completely different class that the model correctly classifies). The algorithm then performs a binary search along the straight line connecting this adversarial image to the original benign image. Because the endpoint is adversarial and the starting point is benign, a simple bisection search quickly pinpoints the exact threshold where the model's hard label flips—the decision boundary.
Benign (Class A) ───────────────────────●─────────────────────── Adversarial (Class B)
Boundary Found
via Binary Search
Once a point on the boundary is established, the challenge is to move along this boundary to minimize the total distortion relative to the benign image. Brendel et al. achieve this via a rejection sampling strategy. The algorithm proposes random steps on a hypersphere centered at the current boundary point. A step is accepted only if it satisfies two strict criteria:
- It must remain within the adversarial region (preserving the target misclassification).
- It must reduce the distance to the original benign image.
By repeatedly sampling and filtering steps based solely on whether the hard label changes, the attack gradually slides along the decision boundary, minimizing the adversarial perturbation without ever seeing a single confidence score.
Exploiting Local Boundary Geometry
While a purely random walk along the decision boundary is reliable, it is highly query-intensive because many random steps are rejected. To optimize this process, researchers exploit a powerful geometric property of deep neural networks: their decision boundaries are surprisingly flat and smooth at a local macro scale.
Instead of treating the boundary as an arbitrary, jagged surface, methods like qFool (Yujia Liu et al.) and GeoDA (Rahmati et al.) linearize the boundary. By modeling the local decision boundary as a collection of hyperplanes, these frameworks can calculate geometric projections. If a boundary is locally flat, the shortest path to minimize distortion is simply the orthogonal projection onto that hyperplane. Rahmati et al. demonstrate that by strategically distributing queries across iterations to estimate the normal vector of this hyperplane, an attacker can converge on the minimal perturbation orders of magnitude faster than a random walk.
Geometric heuristics can be streamlined even further. For instance, Feiyang Wang et al. proposed the Two-third Bridge Attack (TtBA). They identified a specific geometric weight ($k_{bridge}$) that marks the transition zone into the adversarial region. The authors proved that applying a simple, fixed $2/3$ scaling factor consistently identifies near-optimal perturbation directions along the boundary, bypassing the need for expensive iterative exploration of the local surface.
Gradient Sign Estimation and Prior Guidance
Another way to circumvent the step-function problem is to change what is being estimated. If calculating the exact magnitude of a gradient is impossible due to discrete feedback, can we estimate just its directional sign?
Cheng et al. introduced this concept with Sign-OPT. The core insight is to define a continuous surrogate objective function based on the distance to the decision boundary. For any chosen direction (or ray) from the benign image, the distance required to reach the decision boundary is a continuous scalar value. Even though the model only returns hard labels, an attacker can determine this distance using a quick binary search along that ray.
Distance g(θ) varies continuously
│
▼
Benign Image ───────────────────────► [ Decision Boundary ]
Direction θ
Because this distance function $g(\theta)$ varies continuously as the direction $\theta$ changes, it possesses a well-defined gradient. Sign-OPT estimates the sign of this gradient along a given direction by making a single query to see if a tiny directional perturbation stays inside or outside the boundary. This converts a non-differentiable hard-label problem into a smooth, sign-based stochastic gradient descent problem.
To push query efficiency to its practical limit, attackers can guide this directional search using external knowledge. Chen Ma et al. developed Prior-Sign-OPT, which incorporates transfer-based priors from a local, white-box "surrogate" model. Instead of evaluating random directions blindly, the algorithm biases its ray search along the gradient directions of the surrogate model. Because neural networks trained on similar tasks share similar decision boundaries, these white-box priors drastically reduce the search space, allowing the attack to succeed in highly restricted environments with minimal queries.
Downstream Implications: Stealing and Inversion
The solutions engineered to navigate hard-label boundaries have expanded far beyond evasion attacks. They are now widely used to break models in downstream security contexts, such as functional model extraction (stealing) and model inversion (privacy leakage).
Model Stealing via Boundary Exploration
In a model extraction attack, an attacker attempts to clone a target model's functionality by querying it with synthetic data. Under a soft-label setting, the clone learns from the rich, continuous probability distributions of the target. Under a hard-label constraint, this distribution is lost, making it difficult to know where the target model's boundaries actually lie.
To resolve this, Rosenthal et al. developed DisGUIDE. The framework trains two separate clone models simultaneously. When the two clones disagree on a synthetic sample's label, it signals that the sample lies in a "disputed area" near the target model's true decision boundary. This disagreement guides a data generator to synthesize samples exclusively in these high-information zones. Similarly, the QEDG framework by Pei et al. focuses its query budget on generating data directly along these disputed boundaries, maximizing extraction fidelity while minimizing expensive API calls.
Label-Only Model Inversion
Model inversion attacks attempt to reconstruct private training data (such as faces or medical records) by optimizing an input to maximize the target model's output confidence. When an API implements a hard-label restriction, this optimization path is severed because there are no confidence scores to maximize.
The LOKT framework, introduced by Nguyen et al., bypasses this by using a generative model to transfer knowledge. Instead of optimizing directly against the opaque, hard-label target, the attacker uses boundary-mapping queries to train a transparent, white-box surrogate model. Once the surrogate accurately mirrors the target's decision boundaries, the attacker performs a standard, gradient-based white-box inversion attack against the surrogate. This effectively transforms a discrete, zero-gradient black-box problem into a continuous, solvable white-box optimization.