Conv-Reluplex: A Verification Framework For Convolution Neural Networks

Jin Xu, Zishan Li, Miaomiao Zhang, Bowen DuarXiv 2026 · DOI · arXiv

TL;DR

Conv-Reluplex extends the powerful Reluplex SMT solver to provide formal verification for Convolutional Neural Networks (CNNs). By introducing novel "reverse calculation" algorithms for unpooling and deconvolution, the framework can map adversarial perturbations from internal feature layers back to the original input image, enabling both safety guarantees and effective adversarial training.

What Problem Does This Paper Address?

Deep Neural Networks (DNNs) are notoriously "brittle." Small, imperceptible perturbations to an input—known as adversarial examples—can cause a model to misclassify with high confidence. For safety-critical applications like autonomous vehicles or medical diagnostics, we need more than just high test accuracy; we need formal guarantees that a model will behave correctly within a certain "neighborhood" of an input.

Existing tools like Reluplex use Satisfiability Modulo Theories (SMT) to verify these properties, but they were originally designed for Multi-Layer Perceptrons (MLPs). They struggle with the specific architectural components of CNNs, namely convolutional and pooling layers. This paper bridges that gap, allowing researchers to verify the adversarial robustness of CNNs and generate counter-examples (adversarial images) when that robustness fails.

Methods

The authors propose a six-step framework that treats the CNN as a hybrid structure. The core idea is to use Reluplex for what it does best (verifying fully connected layers) and then "back-propagate" the results to the image level.

  1. Forward Pass & Storage: A correctly classified image is passed through the CNN. The framework stores the "rough features" (after convolution) and "dominant features" (after pooling).
  2. FC Verification: The fully connected (FC) layers are treated as a standard DNN. Reluplex is used to check if a small perturbation $\delta$ in the dominant features could change the final classification.
  3. Intermediate Adversarial Example: If Reluplex finds a violation, it produces an "intermediate adversarial example"—a set of perturbed features.
  4. Unpooling Algorithm: This new algorithm reverses the pooling process. It makes minimal changes to the original "rough features" so that their pooled output matches the intermediate adversarial example.
  5. Deconvolution Algorithm: The most complex step. The authors formulate the inversion of the convolutional and ReLU layers as a Linear Programming (LP) problem. Using the PuLP library, they solve for an input image $X$ that satisfies the specific weights, biases, and ReLU constraints of the first layer.

Datasets

The framework was evaluated using the MNIST dataset, the standard benchmark for handwritten digit recognition (0-9).

  • Training set: 60,000 samples.
  • Test set: 10,000 samples.
  • Model: A CNN with one convolutional layer (9x9 kernel), one max-pooling layer (2x2), and a fully connected layer (24x24x10).

Key Insights and Ideas

  • Decoupling Verification: The authors realized they didn't need to solve the entire CNN as one massive SMT problem. By verifying the FC layers first and then mathematically "reversing" the earlier layers, they made the problem tractable.
  • Minimal Perturbation via LP: The use of Linear Programming for deconvolution ensures that the generated adversarial image is as close to the original as possible, satisfying the physical constraints of image data (e.g., pixel values must be between 0 and 1).
  • Adversarial Training Loop: The tool isn't just for "finding bugs." By generating a large volume of these formal counter-examples, the authors could retrain the model, significantly hardening it against the very attacks the tool discovered.

Key Results

  • Robustness Thresholds: For a digit '6', the model was proven $\delta$-locally-robust at $\delta=0.2$. However, at $\delta=0.3$, the tool successfully found adversarial examples that caused the model to misclassify the '6' as a '5'.
  • Adversarial Training Success:
    • Before training, the model's accuracy on adversarial examples was 0%.
  • After training with 200 Conv-Reluplex generated examples per digit, the accuracy on adversarial samples jumped to 99.65%.
  • Crucially, the accuracy on original, clean samples barely budged (dropping only 0.09% from 94.98% to 94.89%), showing that robustness didn't come at the cost of general performance.

Limitations and Future Work

  • Scalability: Like all SMT-based methods, the complexity is exponential. The current experiments were limited to relatively small networks (around 4,000 ReLU nodes). Handling massive architectures like ResNet on ImageNet remains a significant challenge.
  • Color Images: The current implementation focuses on grayscale MNIST digits. The authors aim to extend the tool to handle three-channel color images (RGB).
  • Architectural Variety: The paper primarily addresses standard CNNs. Future work is needed to incorporate Recurrent Neural Networks (RNNs) into the Reluplex verification ecosystem.
  • Efficiency: The high nonlinearity of neural formulas remains a bottleneck for SMT solvers, requiring further optimization of the underlying algorithms.

Summary updated

Abstract

In recent years, machine learning has demonstrated impressive performance in many real-world tasks, especially in computer vision and natural language processing. However, to apply them in safety-critical systems one needs formal guarantees on the neural network outputs. The Reluplex tool is proposed to verify the safety of deep neural networks (DNNs), and in case the DNN fails to give a correct output, can generate adversarial examples. Since the tool can only handle DNNs, it is necessary to extend the tool to process image data. Therefore, in this paper, we propose the Conv-Reluplex framework, which is designed to verify the convolutional layer and pooling layer in convolutional neural networks (CNNs), and generate adversarial examples when classification is misguided. We conduct several experiments on MNIST to evaluate our approaches. The results show that the original CNN is improved using the adversarial examples generated by our tool, and the precision of classification can be increased significantly.
BibTeX
@misc{xu2026conv,
  author = {Jin Xu and Zishan Li and Miaomiao Zhang and Bowen Du},
  title = {{Conv-Reluplex: A Verification Framework For Convolution Neural Networks}},
  year = {2026},
  eprint = {2611.18753},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.18753},
}
Figure