Introduction
Deep Neural Networks (DNNs) are notoriously vulnerable to adversarial perturbations. While significant research has focused on local robustness under $L_\infty$ or $L_2$ norms, the Hamming distance ($L_0$ norm) remains under-explored. The $L_0$ norm, which counts the number of modified pixels, is a critical metric for physical attacks, such as placing stickers on road signs. However, its non-differentiable nature makes standard gradient-based methods inapplicable. Furthermore, existing tools often provide only pointwise local robustness rather than a global measure of reliability across an entire dataset.
The DeepTRE Framework
To address these gaps, we introduce DeepTRE (Tensor-based Robustness Evaluation), an "anytime" algorithm designed to quantify the global robustness of DNNs with formal guarantees. DeepTRE offers several technical advantages:
- Anytime Convergence: The algorithm generates intermediate upper and lower bounds that tighten over time, allowing for early termination once a desired precision is reached.
- Provable Guarantees: Unlike heuristic searches, DeepTRE is guaranteed to converge to optimal robustness values in finite time.
- Tensor-based Parallelization: By reformulating the optimization problem into tensor operations, the framework leverages GPU acceleration to process batches of inputs simultaneously, significantly enhancing computational efficiency.
- Subspace Sensitivity Analysis: The search process identifies critical pixel combinations (subspaces) that most impact network confidence, streamlining the search for the minimal $L_0$ perturbation.
Experimental Evaluation
The framework was evaluated on standard benchmarks and large-scale models:
- MNIST: Used to study convergence properties on standard and resized (14x14) models.
- ImageNet: Applied to state-of-the-art architectures including AlexNet, VGG-16/19, and ResNet-50/101 to demonstrate scalability.
Key Results and Insights
Convergence of Robustness Bounds
A primary strength of DeepTRE is the rapid convergence of its bounds. For individual images, the uncertainty radius regarding the $L_0$ distance typically narrows significantly within a few iterations as the subspace dimension $t$ increases.
Global Robustness Quantification
By defining global robustness as the expected maximum safe radius across a dataset, DeepTRE provides a holistic reliability metric. For instance, evaluations on MNIST models showed a final global robustness of approximately 2.1 pixels, with the gap between upper and lower bounds closing rapidly.
Performance and Architectural Implications
DeepTRE achieves significant speedups, ranging from 18x to 1050x compared to existing $L_0$ attack methods like JSMA and C&W. Beyond speed, the tool provides architectural insights; for example, results indicate that deeper networks are not inherently more robust under $L_0$ metrics, and techniques like batch normalization can measurably improve robustness.
Conclusion
DeepTRE represents a significant step toward rigorous, scalable evaluation of DNN global robustness under the Hamming distance. While currently focused on additive perturbations, future work aims to incorporate invariance-based attacks (e.g., rotations) and integrate these guarantees directly into the training process to develop certified robust models.
Summary updated