Generalized Likelihood Ratio Test for Adversarially Robust Hypothesis Testing

Bhagyashree Puranik, Upamanyu Madhow, Ramtin PedarsaniIEEE TSP 2022 · DOI

TL;DR

This paper proposes a novel defense against adversarial attacks on machine learning models by framing the problem as a composite hypothesis testing scenario. They introduce a Generalized Likelihood Ratio Test (GLRT) that jointly estimates the true class and the adversarial perturbation, offering a more adaptable defense than traditional minimax approaches, especially against weaker attacks.

What Problem Does This Paper Address?

Machine learning models, particularly deep neural networks, are notoriously vulnerable to adversarial attacks. These attacks involve subtly altering input data to cause misclassification, even with high confidence. While many defenses exist, they often rely on empirical adversarial training and lack theoretical guarantees, making them susceptible to future, more sophisticated attacks. This paper aims to provide fundamental insights into robust hypothesis testing against adversarial perturbations by stepping back from complex deep learning architectures and leveraging classical statistical methods. The core challenge is to develop a defense that is both theoretically grounded and practically effective, offering a better trade-off between robustness and accuracy compared to existing methods.

Methods

The paper's central contribution is the application of the Generalized Likelihood Ratio Test (GLRT) to adversarially robust hypothesis testing. The GLRT is a statistical framework for composite hypothesis testing, where the parameters of interest (the class label) and nuisance parameters (the adversarial perturbation) are estimated jointly.

Here's a breakdown of their approach:

  • Composite Hypothesis Testing: They model the problem as deciding between hypotheses $H_k: X \sim p_k(x, \theta)$, where $p_k$ is the class-conditional distribution and $\theta$ represents the adversarial perturbation, which is constrained within a set $\Theta_k$.
  • GLRT Formulation: The GLRT defense aims to maximize the likelihood function over both the class $k$ and the perturbation $\theta$: $k = \arg \max_k \max_{\theta \in \Theta_k} p_k(x, \theta)$. This is achieved by minimizing a cost function $C_k = ||g_\epsilon(X - \mu_k)||^2$, where $g_\epsilon$ is a novel "double-sided ReLU" function that effectively "soft-thresholds" the difference between the observation and the class mean, adapting to the attack budget $\epsilon$.
  • Binary Gaussian Hypothesis Testing: They first evaluate the GLRT for binary hypothesis testing with $l_\infty$-bounded adversarial perturbations. This setting is chosen because a minimax optimal defense is known, providing a benchmark.
  • Minimax vs. GLRT: They contrast their GLRT approach with minimax strategies, which optimize for the worst-case attack. While minimax is theoretically optimal against the worst-case, it can be overly pessimistic. The GLRT, by estimating the perturbation, is expected to adapt better to weaker attacks and offer a more favorable robustness-accuracy trade-off.
  • Multi-class Extension: The GLRT framework is extended to multi-class problems, where minimax strategies are often intractable. They propose heuristic approaches for finding optimal noise-aware and noise-agnostic attacks in this setting.
  • Asymptotic Analysis: They use Central Limit Theorem (CLT) based approximations to analyze the performance of the GLRT defense in high-dimensional settings, showing its asymptotic equivalence to the minimax defense.

Datasets

The paper does not explicitly mention or use any specific named datasets for training or evaluation. Instead, it focuses on theoretical analysis and simulations using synthetic data generated under controlled Gaussian models with specified parameters (means, variances, attack budgets).

Key Insights and Ideas

  • GLRT as a Unified Defense: The GLRT provides a statistically principled and generalizable framework for robust hypothesis testing against adversarial perturbations, applicable beyond specific attack models or network architectures.
  • Adaptability to Attack Strength: Unlike minimax defenses that are designed for the absolute worst-case, the GLRT's ability to estimate the perturbation allows it to adapt to varying attack strengths, leading to better robustness-accuracy trade-offs when attacks are weaker than the maximum budget.
  • "Double-Sided ReLU" as a Key Component: The novel $g_\epsilon$ function is crucial. It effectively shrinks or zeros out signal components that are within the attack budget, providing robustness without completely discarding potentially useful information, unlike some linear minimax approaches.
  • Theoretical Guarantees in High Dimensions: The asymptotic analysis using CLT demonstrates that the GLRT defense achieves performance comparable to the theoretically optimal minimax defense in high-dimensional settings, providing strong theoretical backing.
  • Noise-Aware vs. Noise-Agnostic Attacks: The paper clearly distinguishes between these two types of adversaries and shows that for binary settings, the same worst-case attack can be optimal for both under the GLRT defense. This simplifies the analysis and defense design.
  • Nearest Neighbor Class for Multi-class Attacks: For multi-class problems, they introduce the concept of a "nearest neighbor class" to guide the construction of heuristic attacks, providing a practical approach when optimal attacks are intractable.

Key Results

  • Binary Gaussian Testing: The GLRT defense is shown to be competitive with the minimax strategy under the worst-case $l_\infty$-bounded attack. Crucially, it offers better robustness-accuracy trade-offs for weaker attacks.
  • Asymptotic Performance: In high SNR and large dimensions, the GLRT's asymptotic performance approaches that of the minimax defense.
  • Multi-class Performance: Simulations illustrate the GLRT's effectiveness in multi-class settings, where minimax strategies are often unknown or intractable. They show its performance against both noise-aware and noise-agnostic adversaries.
  • Worst-Case Attack Derivation: For binary settings, they derive the specific worst-case attack for the GLRT defense, which is shown to be optimal for both noise-aware and noise-agnostic adversaries.
  • Heuristic Attacks for Multi-class: They provide methods for finding near-optimal noise-aware attacks and heuristic noise-agnostic attacks for multi-class problems, enabling better evaluation of defenses.

Limitations and Future Work

  • Computational Complexity: While the GLRT is more general than minimax, estimating the perturbation can still be computationally intensive, especially in high dimensions or for complex distributions.
  • Convergence Speed: The paper notes that the convergence of the CLT approximation to the true error probability can be slow in some settings, particularly when the distributions of per-coordinate cost differences have narrow asymmetric tails.
  • Heuristic Nature of Multi-class Attacks: The noise-agnostic attacks for multi-class problems are heuristic and may not be truly optimal, especially in low SNR regimes.
  • Future Work: The authors suggest extending the GLRT approach to more complex data and attack models. They also propose exploring the minimax formulation in such settings, even if finding optimal minimax rules is difficult, by combining insights from both minimax and GLRT. Further research into the practical implementation and computational efficiency of the GLRT defense is also implied.

Summary updated

BibTeX
@article{puranik2022generalized,
  author = {Bhagyashree Puranik and Upamanyu Madhow and Ramtin Pedarsani},
  title = {{Generalized Likelihood Ratio Test for Adversarially Robust Hypothesis Testing}},
  journal = {IEEE TSP},
  year = {2022},
  doi = {10.1109/tsp.2022.3198169},
}
Figure