Pareto DNN Verification: Fast for Most Queries
Organizations: The Hebrew University of Jerusalem, Israel · Bar Ilan University, Israel · Ben-Gurion University of the Negev, Israel · University of California, Riverside, USA
Abstract
Formal verification of deep neural networks (DNNs) faces a fundamental scalability challenge: verifying robustness is NP-hard and state-of-the-art tools often time out on modern architectures. We propose PAreto VErification, or PAVE: by augmenting DNNs with early exits (EEs) and verifying exit-by-exit, we solve a large fraction of robustness queries---roughly 80% in our evaluation---in a small fraction of the time required for direct verification. The key insight is that many inputs in a robustness neighborhood exit at an early layer. Verifying this early-exit behavior is often a tractable problem,allowing verification to terminate long before the full network is analyzed. EEs can be added without modifying the base network, and incur at most a 0.3% accuracy change across our tested architectures. We formalize the novel robustness property for EE networks, prove it is Fixed-Parameter Tractable under a trace stability condition (which commonly holds in practice), and present a sound and complete verification algorithm. Two sound optimizations --- break (early termination when the winner dominates) and continue (skipping the inner loop when no runner-up can win) --- reduce SAFE-case verification time by up to 10x. Experiments on MNIST, CIFAR-10, and CIFAR-100 with networks from 600K to 33M parameters demonstrate that PAVE enables solving queries that were not solved otherwise, including formal verification of ResNet-18 on CIFAR-100.
Figures & tables
| Model | Dataset | Size | # Layers | Accuracy | EE Accuracy | Exit Distribution |
|---|---|---|---|---|---|---|
| FC-6 | MNIST | 1,519,720 | 6 | 98.18 | 98.2 | [9772, 152, 46, 30] |
| CNN (LeNet-5) | CIFAR-10 | 596,178 | 5 | 70.02 | 69.93 | [5924, 2066, 2010] |
| ResNet-18 | CIFAR-10 | 11,243,102 | 18 | 86.43 | 86.11 | [6656, 1899, 1445] |
| VGG-16 | CIFAR-10 | 33,769,566 | 13 | 93.45 | 93.14 | [8268, 1278, 454] |
| Benchmark | UNSAFE | SAFE | ||||
|---|---|---|---|---|---|---|
| Mean | Std | Median | Mean | Std | Median | |
| MNIST, FC6 | 0.527 | 1.903 | 0.068 | 13.037 | 3.185 | 13.032 |
| 0.600 | 2.739 | 0.201 | 1.143 | 1.205 | 0.397 | |
| CIFAR10, LeNet | 2.250 | 6.670 | 0.320 | 56.927 | 9.516 | 58.628 |
| 2.279 | 4.556 | 0.688 | 7.255 | 10.550 | 6.185 | |
| CIFAR10, ResNet18 | 3.518 | 12.499 | 1.306 | 409.395 | 74.235 | 375.703 |
| Architecture | Accuracy | Inference Time | # SAFE | # UNSAFE | # UNKNOWN | Safe Ver Time | Unsafe Ver Time |
|---|---|---|---|---|---|---|---|
| RN_ee1 | 0.8757 | 30.56ms | 121 | 109 | 190 | 21.4s | 11.7s |
| RN_ee2 | 0.8921 | 36.94ms | 85 | 108 | 227 | 23.4s | 14.2s |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Train Size | Test Size | #Classes | Input Shape |
|---|---|---|---|---|
| MNIST | 60,000 | 10,000 | 10 | |
| CIFAR-10 | 50,000 | 10,000 | 10 | |
| CIFAR-100 | 50,000 | 10,000 | 100 |
Neural Network Verification
Neural network verification develops methods to prove whether networks satisfy properties such as robustness, safety, and bounded output behavior.
See all 138 papers