Optimization-Based Attacks: Carlini & Wagner Methods

While gradient-based attacks like Projected Gradient Descent (PGD) provide a strong baseline for generating adversarial examples, they primarily focus on finding any adversarial example within a predefined perturbation budget ($\epsilon$-ball). They don't necessarily find the example with the smallest possible perturbation that achieves misclassification. For situations where minimizing the perceptibility of the perturbation is critical, or when evaluating the absolute breaking point of a model, optimization-based attacks offer a more direct approach.

The Carlini & Wagner (C&W) attacks, introduced by Nicholas Carlini and David Wagner, represent a powerful class of optimization-based evasion attacks. Instead of just finding an adversarial example within a constraint, C&W methods frame the search as a formal optimization problem: find the minimum distortion $\delta$ such that $x_{adv} = x + \delta$ is misclassified and satisfies input constraints (e.g., pixel values remain valid).

Formulating the Optimization Problem

The core idea is to minimize the perturbation size, measured by an $L_p$ norm, subject to the condition that the model misclassifies the perturbed input. Let $x$ be the original input, $x'$ be the adversarial input ($x_{adv}$), and $f$ be the model (often represented by its logits $Z(x')$ before the final softmax). The goal is to find $x'$ that solves:

$$\text{minimize } ||x' - x||_p \quad \text{subject to } f(x') \text{ is misclassified and } x' \in [0, 1]^n$$

Directly enforcing the "misclassified" constraint is difficult in standard optimization frameworks. C&W cleverly replace this constraint with a specially designed loss function, $g(x')$, which is minimized when the model misclassifies $x'$. The optimization problem then becomes:

$$\text{minimize } ||x' - x||_p + c \cdot g(x')$$

Here:

• $||x' - x||_p$ is the distortion term, measuring the distance between the original and adversarial input using an $L_p$ norm (commonly $L_0$, $L_2$, or $L_\infty$).
• $g(x')$ is the classification loss function.
• $c$ is a balancing constant, carefully chosen (often via binary search) to ensure the classification constraint is met while keeping the distortion low. A larger $c$ places more emphasis on achieving misclassification.

The C&W Classification Loss

The genius of the C&W attack lies in the design of $g(x')$. For a targeted attack, where the goal is to make the model classify $x'$ as a specific target class $t$, a common loss function is:

$$g(x') = \max( \max_{i \neq t} Z(x')_i - Z(x')_t, -\kappa )$$

Let's break this down:

• $Z(x')_i$ is the logit value for class $i$.
• $\max_{i \neq t} Z(x')_i$ finds the highest logit value among all classes except the target class $t$.
• $Z(x')_t$ is the logit value for the target class $t$.
• The difference $\max_{i \neq t} Z(x')_i - Z(x')_t$ measures how much "stronger" the most likely incorrect class is compared to the target class. We want this difference to be negative and large (in magnitude) for the target class $t$ to be the most likely prediction.
• The outer $\max(\dots, -\kappa)$ introduces a confidence margin $\kappa \ge 0$. The loss becomes negative only when $Z(x')_t$ is greater than all other logits by at least $\kappa$. Minimizing this loss encourages the target logit to surpass the next highest logit by this margin, increasing the confidence of the misclassification. Setting $\kappa = 0$ simply requires the target class logit to be the highest.

For an untargeted attack, where the goal is simply to make the model misclassify $x'$ away from its original class $y_{true}$, the loss can be defined as:

$$g(x') = \max( Z(x')_{y_{true}} - \max_{i \neq y_{true}} Z(x')_i, -\kappa )$$

Here, the goal is to minimize the loss by making the true class logit $Z(x')_{y_{true}}$ smaller than the highest logit of any other class by at least $\kappa$.

Solving the Problem

C&W attacks typically use standard gradient-based optimizers like Adam to minimize the combined objective function $||x' - x||_p + c \cdot g(x')$. However, a technical detail arises: the input $x'$ must often satisfy box constraints (e.g., pixel values in $[0, 1]$). Directly applying gradient descent and clipping $x'$ at each step can hinder convergence.

C&W proposed using a change of variables. For example, instead of optimizing $x'$ directly, they optimize a variable $w$ where $x' = \frac{1}{2} (\tanh(w) + 1)$. Since the output of $\tanh$ is always in $(-1, 1)$, $x'$ is guaranteed to be in $(0, 1)$, satisfying the box constraints naturally. The optimization is performed with respect to $w$, and the distortion $||x' - x||_p$ and classification loss $g(x')$ are calculated based on the transformed $x'$.

C&W Attack Variants ($L_2$, $L_\infty$, $L_0$)

The C&W framework was developed for different $L_p$ norms:

• C&W $L_2$ Attack: This is the most common variant. It minimizes the Euclidean distance $||x' - x||_2$. It typically uses the loss function described above and the $\tanh$ change-of-variables trick. It's known for finding very low-distortion $L_2$ adversarial examples, often outperforming PGD in terms of perturbation magnitude, albeit usually slower.
• C&W $L_\infty$ Attack: This variant aims to minimize the maximum change to any single feature, $||x' - x||_\infty$. It uses a slightly modified optimization approach, often involving iterative steps similar to PGD but incorporating the C&W loss function. It aims to find the smallest $\epsilon$ for which an $L_\infty$ attack succeeds.
• C&W $L_0$ Attack: This attack minimizes the number of pixels changed, $||x' - x||_0$. It's computationally harder. The approach typically involves iteratively fixing pixels that are not contributing significantly to the loss and only optimizing the remaining ones.

Difference between PGD and C&W ($L_2$) approaches. PGD iteratively steps and projects to stay within a fixed-size $L_p$ ball around the original input $x$, seeking any misclassification. C&W directly minimizes the $L_2$ distance from $x$ while satisfying a misclassification loss, effectively finding the closest point across the decision boundary.

Strengths and Trade-offs

Strengths:

• Effectiveness: C&W attacks, particularly the $L_2$ variant, are highly effective and often find adversarial examples with smaller perturbations compared to PGD for a given model.
• Circumvents Gradient Masking: Because C&W uses an optimization objective that relies on logits and includes the distortion term, it can sometimes overcome defenses that attempt to mask or obfuscate gradients, which might fool simpler gradient-based methods.
• Flexibility: The framework can be adapted for targeted/untargeted attacks and different $L_p$ norms.

Trade-offs:

• Computational Cost: C&W attacks are significantly slower than FGSM or PGD. They involve an iterative optimization process, and finding the optimal constant $c$ typically requires a binary search, running the attack multiple times.
• Complexity: The implementation is more involved than basic gradient-based methods, requiring careful handling of the optimization objective and constraints.

Despite their computational cost, C&W attacks serve as a critical benchmark for evaluating the robustness of machine learning models and defenses. Their ability to find near-minimal perturbations makes them a standard tool for security evaluations. If a defense holds up against a strong C&W attack, it provides greater confidence in its effectiveness compared to only testing against faster methods like FGSM or PGD.