Boosting the Robustness Verification of DNN by Identifying the Achilles's Heel

Chengdong Feng, Zhenbang Chen, Weijiang Hong, Hengbiao Yu, Wei Dong, Ji WangarXiv 2018 · arXiv

Abstract

Formal verification of Deep Neural Networks (DNNs) is essential for safety-critical applications but remains computationally prohibitive. This paper presents a novel "boosting" framework that accelerates the search for adversarial counter-examples by identifying a network's "Achilles's heel"—inputs where the margin between the top two predicted classes is minimal. By combining a continuity proof for ReLU-based networks with a greedy pre-analysis heuristic, the proposed method achieves up to a 10x speedup over traditional verification tools like Reluplex.

Introduction

As Deep Neural Networks (DNNs) are increasingly integrated into safety-critical systems, such as autonomous vehicles and airborne collision avoidance systems (ACAS-Xu), ensuring their robustness against adversarial perturbations is paramount. Formal verification aims to provide mathematical guarantees that small input changes will not lead to incorrect classifications. However, for ReLU-based networks, this task is NP-complete, often leading to significant computational overhead.

A standard Deep Neural Network architecture consisting of input, hidden, and output layers.

Current verification tools frequently spend hours searching for counter-examples. This research addresses the efficiency gap by prioritizing the search in regions where the model is most vulnerable, effectively "boosting" the verification process.

Methodology

The proposed approach relies on identifying the "Achilles's heel" of a network through a multi-step process:

  1. Continuity Proof: The authors mathematically demonstrate that DNNs utilizing ReLU activation functions are continuous. This ensures that small input perturbations lead to predictable output changes, justifying the use of local search heuristics.
  2. The Achilles's Heel Metric: The core innovation is the metric $N_d(x) = V_1 - V_2$, where $V_1$ and $V_2$ are the highest and second-highest output scores, respectively. A small $N_d(x)$ indicates high model uncertainty.
  3. Selective Sampling and Greedy Search: Instead of exhaustive or random verification, the algorithm samples many points and selects only those with the lowest $N_d(x)$ values. A lightweight greedy search then attempts to find adversarial examples at these points before invoking heavy-duty SMT solvers.
MNIST digits with associated confidence scores, illustrating varying levels of model certainty.

Experimental Results

The method was evaluated on the ACAS-Xu benchmark and the MNIST handwritten digit dataset.

  • Efficiency Gains: The boosting method demonstrated a 10x speedup in finding counter-examples compared to random sampling. On the MNIST dataset, where traditional methods often timed out, the proposed approach achieved a success rate exceeding 90%.
  • Attack Enhancement: Integrating the "Achilles's heel" selection with standard attacks like FGSM or DeepFool resulted in a 3.2x average improvement in attack success rates.

Conclusion

By reframing verification as a targeted search for vulnerabilities, this work significantly reduces the time required to identify non-robust behavior in DNNs. While currently optimized for ReLU activations and tested on tools like Reluplex, future work aims to extend these principles to broader activation functions and larger-scale architectures.

Summary updated

BibTeX
@misc{feng2018boosting,
  author = {Chengdong Feng and Zhenbang Chen and Weijiang Hong and Hengbiao Yu and Wei Dong and Ji Wang},
  title = {{Boosting the Robustness Verification of DNN by Identifying the Achilles's Heel}},
  year = {2018},
  eprint = {1811.07108},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.07108},
}
Figure