Mathematical Formulation of Adversarial Examples

Having established that machine learning models can be vulnerable and that attackers have various goals and capabilities, let's formalize the central concept of an adversarial example. At its core, an adversarial example is an input deliberately crafted to fool a model, looking almost identical to a legitimate input yet causing the model to produce an incorrect output.

Consider a machine learning model, represented by a function $f$, which maps an input $\boldsymbol{x}$ from some domain (like an image or text) to an output $y$ (like a class label). Let $y = f(\boldsymbol{x})$ be the correct output for a given input $\boldsymbol{x}$.

An untargeted adversarial example, $\boldsymbol{x}'$, is a modified input that satisfies two conditions:

1. Misclassification: The model outputs an incorrect label for $\boldsymbol{x}'$. $$f(\boldsymbol{x}') \neq y$$
2. Proximity: The modified input $\boldsymbol{x}'$ is "close" to the original input $\boldsymbol{x}$.

In a targeted attack, the goal is more specific: to make the model output a particular incorrect label $y_{target}$ (where $y_{target} \neq y$). The first condition becomes:

$$f(\boldsymbol{x}') = y_{target}$$

Defining the Perturbation

The difference between the original input and the adversarial example is the perturbation, denoted by $\boldsymbol{\delta}$:

$$\boldsymbol{\delta} = \boldsymbol{x}' - \boldsymbol{x}$$

So, we can write the adversarial example as $\boldsymbol{x}' = \boldsymbol{x} + \boldsymbol{\delta}$. The "proximity" condition means that the perturbation $\boldsymbol{\delta}$ must be small according to some measure.

Measuring Perturbation Size: $L_p$ Norms

How do we mathematically quantify "small"? The standard approach in adversarial machine learning is to use $L_p$ norms to measure the magnitude of the perturbation vector $\boldsymbol{\delta}$. The choice of norm reflects different assumptions about what constitutes an "imperceptible" or "allowable" change.

Let $\boldsymbol{\delta}$ be a vector of dimension $d$ (e.g., $d$ pixels in an image). Common norms include:

• $L_\infty$ Norm (Maximum Change): Measures the largest absolute change to any single element of the input. It's defined as:

  $$\|\boldsymbol{\delta}\|_\infty = \max_{i=1, \dots, d} |\delta_i|$$

  An $L_\infty$ constraint $\|\boldsymbol{\delta}\|_\infty \le \epsilon$ means no single input feature (e.g., pixel value) is changed by more than $\epsilon$. This is widely used for image attacks as small uniform changes are often hard to spot. For images with pixel values normalized to $[0, 1]$, a common $\epsilon$ value is $8/255$.

• $L_2$ Norm (Euclidean Distance): Measures the standard Euclidean distance between $\boldsymbol{x}$ and $\boldsymbol{x}'$.

  $$\|\boldsymbol{\delta}\|_2 = \sqrt{\sum_{i=1}^{d} \delta_i^2}$$

  An $L_2$ constraint $\|\boldsymbol{\delta}\|_2 \le \epsilon$ limits the overall magnitude of the change vector. The changes might be concentrated in a few features or spread out thinly.

• $L_1$ Norm (Sum of Absolute Changes): Measures the sum of the absolute changes across all elements.

  $$\|\boldsymbol{\delta}\|_1 = \sum_{i=1}^{d} |\delta_i|$$

  An $L_1$ constraint $\|\boldsymbol{\delta}\|_1 \le \epsilon$ encourages sparsity, meaning the perturbation might involve larger changes but only to a very small number of features (relevant for high-dimensional sparse data like text features).

• $L_0$ Norm (Number of Changed Elements): Counts the number of elements in $\boldsymbol{\delta}$ that are non-zero.

  $$\|\boldsymbol{\delta}\|_0 = \sum_{i=1}^{d} \mathbb{I}(\delta_i \neq 0)$$

  where $\mathbb{I}(\cdot)$ is the indicator function (1 if true, 0 otherwise). An $L_0$ constraint $\|\boldsymbol{\delta}\|_0 \le k$ means that at most $k$ features (e.g., pixels) can be altered. This is computationally harder to work with but directly models changes to a limited number of input components.

The choice of $L_p$ norm and the perturbation budget $\epsilon$ (or $k$ for $L_0$) are essential components of the threat model, defining the attacker's capability.

Adversarial Example Generation as Optimization

Finding an adversarial example can often be framed as an optimization problem. There are two common formulations:

1. Minimize Perturbation: Find the smallest perturbation $\boldsymbol{\delta}$ (measured by some $L_p$ norm) that causes misclassification.

   $$\min_{\boldsymbol{\delta}} \|\boldsymbol{\delta}\|_p \quad \text{subject to} \quad f(\boldsymbol{x} + \boldsymbol{\delta}) \neq y$$

   We also usually need to ensure the resulting $\boldsymbol{x}' = \boldsymbol{x} + \boldsymbol{\delta}$ remains a valid input (e.g., pixel values stay within the allowed range like $[0, 1]$).

2. Maximize Loss (within Budget): Find the perturbation $\boldsymbol{\delta}$ that maximizes the model's prediction error (loss) while staying within a predefined perturbation budget $\epsilon$.

   $$\max_{\boldsymbol{\delta} \text{ s.t. } \|\boldsymbol{\delta}\|_p \le \epsilon} \mathcal{L}(f(\boldsymbol{x} + \boldsymbol{\delta}), y)$$

   Here, $\mathcal{L}$ is a loss function (like cross-entropy) that measures the discrepancy between the model's prediction on the perturbed input $f(\boldsymbol{x} + \boldsymbol{\delta})$ and the original correct label $y$. For targeted attacks, we would maximize the loss with respect to the original label or minimize it with respect to the target label $y_{target}$. This formulation directly leads to gradient-based attack methods, which we will explore in the next chapter.

Geometric Viewpoint

Imagine the high-dimensional space where inputs live. The model $f$ partitions this space into regions corresponding to different classes, separated by decision boundaries. An original input $\boldsymbol{x}$ lies within the region for its correct class $y$. An adversarial example $\boldsymbol{x}'$ is found by moving $\boldsymbol{x}$ just slightly (within the $L_p$-ball of radius $\epsilon$) across a decision boundary into a region corresponding to a different class $y'$.

Illustration of an adversarial example. The original input $\boldsymbol{x}$ (blue dot) is correctly classified. A small perturbation $\boldsymbol{\delta}$ is added, resulting in $\boldsymbol{x}'$ (red dot), which lies just across the decision boundary and is misclassified. The perturbation magnitude is constrained, often by an $L_p$ norm ($\|\boldsymbol{\delta}\|_p \le \epsilon$).

This mathematical framework allows us to precisely define adversarial examples and the constraints under which they are generated. It forms the foundation for developing specific attack algorithms (like those based on gradients or optimization) and for designing and evaluating defenses, which are the subjects of the following chapters. Understanding this formulation is essential for analyzing the security properties of machine learning models.