# Efficient Global Robustness Certification of Neural Networks via Interleaving Twin-Network Encoding

arXiv: https://arxiv.org/abs/2203.14141 · HTML: https://mlsanity.com/paper/2203.14141/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 53 references that are in the map.
- First posted on arXiv 26 Mar 2022.

## Builds on (most cited first, 22 of 22)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Safety Verification of Deep Neural Networks](https://mlsanity.com/paper/1610.06940/) (2016)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [An approach to reachability analysis for feed-forward ReLU neural networks](https://mlsanity.com/paper/1706.07351/) (2017)
- [Maximum Resilience of Artificial Neural Networks](https://mlsanity.com/paper/1705.01040/) (2017)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [POLAR: A Polynomial Arithmetic Framework for Verifying Neural-Network Controlled Systems](https://mlsanity.com/paper/2106.13867/) (2021)
- [Robustness of Neural Networks: A Probabilistic and Practical Approach](https://mlsanity.com/paper/1902.05983/) (2019)
- [Learning Security Classifiers with Verified Global Robustness Properties](https://mlsanity.com/paper/2105.11363/) (2021)
- [Joint Differentiable Optimization and Verification for Certified Reinforcement Learning](https://mlsanity.com/paper/2201.12243/) (2022)
- [Physics-Aware Safety-Assured Design of Hierarchical Neural Network based Planner](https://mlsanity.com/paper/2201.09140/) (2022)
- [Energy-Efficient Control Adaptation with Safety Guarantees for Learning-Enabled Cyber-Physical Systems](https://mlsanity.com/paper/2008.06162/) (2020)
- [The Unary Fragments of Metric Interval Temporal Logic: Bounded versus Lower bound Constraints (Full Version)](https://mlsanity.com/paper/1305.3204/) (2013)
- [Opportunistic Intermittent Control with Safety Guarantees for Autonomous Systems](https://mlsanity.com/paper/2005.03726/) (2020)
- [End-to-end Uncertainty-based Mitigation of Adversarial Attacks to Automated Lane Centering](https://mlsanity.com/paper/2103.00345/) (2021)
- [Learning-based Framework for Sensor Fault-Tolerant Building HVAC Control with Model-assisted Learning](https://mlsanity.com/paper/2106.14144/) (2021)
- [Cocktail: Learn a Better Neural Network Controller from Multiple Experts via Adaptive Mixing and Robust Distillation](https://mlsanity.com/paper/2103.05046/) (2021)
- [Cross-Layer Design of Automotive Systems](https://mlsanity.com/paper/2005.11842/) (2020)

## Built on by (most cited first, 15 of 15)

- [Semi-supervised Semantics-guided Adversarial Training for Trajectory Prediction](https://mlsanity.com/paper/2205.14230/) (2022)
- [Computing-In-Memory Neural Network Accelerators for Safety-Critical Systems: Can Small Device Variations Be Disastrous?](https://mlsanity.com/paper/2207.07626/) (2022)
- [POLAR-Express: Efficient and Precise Formal Reachability Analysis of Neural-Network Controlled Systems](https://mlsanity.com/paper/2304.01218/) (2023)
- [Verification of Neural Networks' Global Robustness](https://mlsanity.com/paper/2402.19322/) (2024)
- [Learning Representation for Anomaly Detection of Vehicle Trajectories](https://mlsanity.com/paper/2303.05000/) (2023)
- [A Tool for Neural Network Global Robustness Certification and Training](https://mlsanity.com/paper/2208.07289/) (2022)
- [Logic Gate Neural Networks are Good for Verification](https://mlsanity.com/paper/2505.19932/) (2025)
- [Compute-in-Memory based Neural Network Accelerators for Safety-Critical Systems: Worst-Case Scenarios and Protections](https://mlsanity.com/paper/2312.06137/) (2023)
- [The Pros and Cons of Adversarial Robustness](https://mlsanity.com/paper/2312.10911/) (2023)
- [NP-Hard Lower Bound Complexity for Semantic Self-Verification](https://mlsanity.com/paper/2501.15446/) (2025)
- [Solution-aware vs global ReLU selection: partial MILP strikes back for DNN verification](https://mlsanity.com/paper/2507.23197/) (2025)
- [TestifAI: Tomography-Based Testing for Deep Learning Systems](https://mlsanity.com/paper/2608.18900/) (2026)
- [Verifying Global Neural Network Specifications using Hyperproperties](https://mlsanity.com/paper/2306.12495/) (2023)
- [Talking with Verifiers: Automatic Specification Generation for Neural Network Verification](https://mlsanity.com/paper/2603.02235/) (2026)
- [Branch and Bound for Relational Verification of Neural Networks](https://mlsanity.com/paper/2608.13118/) (2026)

## Abstract (arXiv)

The robustness of deep neural networks has received significant interest recently, especially when being deployed in safety-critical systems, as it is important to analyze how sensitive the model output is under input perturbations. While most previous works focused on the local robustness property around an input sample, the studies of the global robustness property, which bounds the maximum output change under perturbations over the entire input space, are still lacking. In this work, we formulate the global robustness certification for neural networks with ReLU activation functions as a mixed-integer linear programming (MILP) problem, and present an efficient approach to address it. Our approach includes a novel interleaving twin-network encoding scheme, where two copies of the neural network are encoded side-by-side with extra interleaving dependencies added between them, and an over-approximation algorithm leveraging relaxation and refinement techniques to reduce complexity. Experiments demonstrate the timing efficiency of our work when compared with previous global robustness certification methods and the tightness of our over-approximation. A case study of closed-loop control safety verification is conducted, and demonstrates the importance and practicality of our approach for certifying the global robustness of neural networks in safety-critical systems.