Score-Based Attack Techniques

Moving from attacks that require full knowledge of the model's architecture and parameters (white-box attacks), we now consider scenarios where the attacker has significantly less information. Score-based attacks represent a common and practical black-box setting. Here, the attacker can query the target model $f$ with an input $x$ and receive the model's output confidence scores (e.g., probabilities from a softmax layer), but does not have access to the model's gradients, architecture, or weights.

The objective remains the same as other evasion attacks: find a minimally perturbed input $x_{adv} = x + \delta$ such that $f(x_{adv})$ leads to a misclassification, while $||\delta||_p \le \epsilon$. The challenge lies in optimizing the perturbation $\delta$ without the direct gradient information $\nabla_x L(f(x), y)$, where $L$ is a suitable loss function (like cross-entropy) and $y$ is the true or target label.

The Black-Box Challenge: Optimizing Without Gradients

Gradient-based methods like PGD rely explicitly on the gradient to iteratively move the input towards regions causing misclassification. Optimization-based methods like C&W also typically use gradients within their optimization loop. Without access to these gradients, how can an attacker effectively search for an adversarial perturbation?

The core idea behind most score-based attacks is gradient estimation. If the attacker can approximate the gradient of the loss function with respect to the input, even crudely, they can adapt iterative gradient-based techniques. The model's output scores provide the necessary signal to perform this estimation.

Gradient Estimation via Queries

Imagine we want to estimate the gradient $\nabla_x L(f(x), y)$ at a point $x$. Since we only have access to the model's output scores, we can compute the loss $L(f(x), y)$ for any input $x$ we query. The gradient tells us the direction of steepest ascent of the loss function. We can approximate this direction by querying the model at nearby points.

A basic approach is using finite differences. To estimate the partial derivative with respect to the $i$-th input feature $x_i$, we can query the model at $x + h \cdot e_i$ and $x - h \cdot e_i$, where $e_i$ is a unit vector along the $i$-th dimension and $h$ is a small step size. The central difference formula gives an approximation:

$$\frac{\partial L}{\partial x_i} \approx \frac{L(f(x + h \cdot e_i), y) - L(f(x - h \cdot e_i), y)}{2h}$$

By doing this for all input dimensions, we can construct an estimate $\hat{g}$ of the full gradient $\nabla_x L$. However, this requires $2 \times D$ queries to the model for each gradient estimation step, where $D$ is the input dimensionality (e.g., number of pixels in an image). For high-dimensional inputs like images, this quickly becomes computationally prohibitive.

Common Score-Based Attack Techniques

More sophisticated techniques aim to estimate the gradient more efficiently, reducing the number of required model queries.

Natural Evolution Strategies (NES)

NES is a family of algorithms that uses a randomized search strategy to estimate the gradient. Instead of probing along each dimension individually, NES samples multiple points from a search distribution (often a Gaussian centered at the current input $x$) and uses the loss values at these points to estimate the gradient direction.

The intuition is to slightly perturb the input $x$ in various random directions $u_k$, query the model to get $L(f(x + \sigma u_k), y)$ for each perturbation, and then compute a weighted average of the perturbation directions $u_k$, where the weights are based on the observed losses. Directions that increase the loss significantly get higher weight. This approach often requires far fewer queries than finite differences for high-dimensional problems to get a reasonable gradient estimate.

Flow of gradient estimation using a method like NES. Random directions are sampled, evaluated via model queries, and used to estimate the gradient for the next update step.

Zeroth-Order Optimization (ZOO) Attacks

The ZOO attack specifically adapts the highly effective C&W attack to the score-based setting. It typically uses coordinate-wise finite differences (or sometimes symmetric difference quotients) to estimate the partial derivative for one coordinate at a time. While still potentially requiring many queries if optimizing all coordinates simultaneously, ZOO often employs techniques like coordinate descent, where only the most promising coordinate(s) are updated in each step, making it more manageable than full finite difference gradient estimation. It directly estimates $\frac{\partial L}{\partial x_i}$ using two queries and uses this within an optimization framework similar to C&W.

Other Related Methods

Techniques like Simultaneous Perturbation Stochastic Approximation (SPSA) also exist, offering another way to estimate gradients with only two queries per step, regardless of input dimensionality, by perturbing all dimensions simultaneously using a random vector.

Practical Hurdles and Considerations

The primary challenge for score-based attacks is query complexity.

• High Query Count: Even efficient methods like NES or SPSA can require thousands or tens of thousands of queries to the target model to craft a single successful adversarial example, especially for high-resolution images or complex models. Finite differences are often impractical for large inputs.
• Rate Limiting and Detection: Many real-world systems (like online APIs) implement rate limiting or monitoring for excessive queries from a single source, which can hinder or reveal these attacks.
• Loss Calculation: The attacker needs to define a suitable loss function based solely on the output scores. For targeted attacks, this might be maximizing the score of the target class or minimizing the score of the true class. For untargeted attacks, maximizing the loss with respect to the original class often works.

Effectiveness and Comparison

Despite the query cost, score-based attacks demonstrate that even limited access to model outputs can be sufficient to generate effective adversarial examples.

• Comparison to White-Box: They are generally less efficient (require more queries) and sometimes find slightly larger perturbations compared to white-box attacks like PGD or C&W, which can exploit exact gradients.
• Comparison to Decision-Based: They typically require fewer queries than decision-based attacks (which only use the final class label) to find an initial adversarial example, as scores provide more granular information about the model's decision boundary proximity. However, decision-based attacks might be applicable in even more restricted scenarios.

Score-based attacks occupy an important middle ground in the spectrum of black-box attacks. They represent a realistic threat model against deployed systems where confidence scores are available, forcing defenders to consider security past just hiding gradients or model weights. Understanding these techniques is essential for evaluating the security of models exposed via APIs or other interfaces where output probabilities are accessible.