Research map / Adversarial robustness and security / Certified and empirical robustness
Relational Verification Leaps Forward with RABBit
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RABBit, a branch-and-bound relational verifier for k-UAP properties that combines cross-executional bound refinement with branching over multiple DNN executions and a final MILP, improving worst-case UAP accuracy over SOTA verifiers.
Problem
Relational verification of DNNs (e.g., universal adversarial perturbation robustness) where existing complete L∞ verifiers ignore cross-execution dependencies and existing relational verifiers apply only a single bounding step without branching, yielding imprecise results.
Approach
Combines branching over multiple executions with cross-executional bound refinement via two BaB variants (strong bounding over execution subsets, strong branching with fixed target linear approximations per execution), then unifies them in a MILP with only O(k) integer variables.
Key results
- On CIFAR-10 ConvSmall networks, RABBit improves worst-case UAP accuracy by up to +4.8% over baselines (k=50).
- On MNIST networks, RABBit gains up to +3.2% in worst-case UAP accuracy over SOTA verifiers.
- Strong bounding improves the t* bound by up to 108.7% on CIFAR-10 networks versus RACoon and alpha-beta-CROWN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine strong bounding and strong branching in RABBit | relational UAP verification · CIFAR10 and MNIST networks in Table 1 | worst-case UAP accuracy: up to +4.8% and up to +3.2% | Helped |
| use strong bounding instead of strong branching alone (ablation) | RABBit relational UAP verification · CIFAR10 and MNIST networks in Table 1 | worst-case UAP accuracy: 63.8 (+1.6) vs 63.2 (+1.0); 83.0 (+3.0) vs 83.8 (+3.8) | Mixed |
Surprising findings
- Strong bounding outperforms strong branching on some DNNs while the reverse holds on others, motivating the combined approach.
Limitations
- Does not scale to DNNs trained on large datasets such as ImageNet.
- Sound but incomplete for relational properties; cannot prove some true properties.
- Restricted to ReLU networks in the current formulation.
Experimental setup
Datasets: MNIST CIFAR-10
Benchmarks: MNIST CIFAR-10
Metrics: worst-case UAP accuracy top-k accuracy verification time
Baselines: CROWN alpha-CROWN alpha-beta-CROWN MN-BaB GCP-CROWN I/O formulation RACoon RaVeN
Builds on: RACoon alpha-beta-CROWN BaBSR RaVeN
Closest papers by meaning
- Relational DNN Verification With Cross Executional Bound Refinement (ICML 2024 · similarity 0.92)
- Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification (NeurIPS 2025 · similarity 0.83)
- ProofAug: Efficient Neural Theorem Proving via Fine-grained Proof Structure Analysis (ICML 2025 · similarity 0.83)
- Certified but Private: Scalable Zero-Knowledge Proofs for the Formal Verification of Neural Networks (NeurIPS 2026 · similarity 0.83)
- Stress-Testing Neural Network Verifiers with Provably Robust Instances (NeurIPS 2026 · similarity 0.83)
- VNN: Verification-Friendly Neural Networks with Hard Robustness Guarantees (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.