An Abstraction-Refinement Approach to Verifying Convolutional Neural Networks

Matan Ostrovsky, Clark W. Barrett, Guy Katz

Introduction

Formal verification is the "gold standard" for ensuring neural networks behave safely, especially against adversarial attacks. However, as networks grow in complexity—particularly Convolutional Neural Networks (CNNs)—the computational cost of proving they are "error-free" becomes astronomical.

In their paper, "An Abstraction-Refinement Approach to Verifying Convolutional Neural Networks," researchers from The Hebrew University and Stanford University introduce Cnn-Abs, a framework designed to make CNN verification significantly faster and more scalable.

The Challenge of CNN Verification

Deep Neural Networks (DNNs) are notoriously "opaque." Even state-of-the-art models can be tripped up by adversarial inputs—tiny, human-imperceptible perturbations that cause the model to make a confident, incorrect classification.

Formal verification aims to mathematically prove that no such perturbation exists within a certain range. While tools like Marabou or Reluplex work well for standard fully connected networks, they struggle with CNNs. Most verifiers treat CNNs as massive, sparse, fully connected layers, failing to exploit the structural "compactness" of convolutions. This leads to a "scalability wall" where verifying even moderately sized CNNs takes too long or runs out of memory.

A typical CNN architecture showing the flow of data through convolutional, ReLU, and max-pooling layers.

The Cnn-Abs Framework

The paper introduces two primary innovations to overcome these hurdles:

1. Abstraction-Refinement for CNNs

The core of the approach is an "over-approximation" strategy. By simplifying the network, the verifier can reach a conclusion faster.

  • Abstraction: The framework creates an abstract version of the CNN by deleting certain convolutional connections and replacing them with calculated bounds. This often allows the verifier to "prune" entire cones of neurons that no longer affect the output.
  • Verification: A backend engine (like Marabou) checks the simpler, abstract network. If the property holds on the abstract network, it is mathematically guaranteed to hold on the original.
  • Refinement: If the verifier finds a "counterexample" that only exists because the network was too simple (a spurious counterexample), the framework "refines" the network by restoring the most important connections and tries again.
Illustration of network abstraction where a node is replaced by its value interval to simplify verification.

The authors tested five different "scoring" policies to decide which neurons to restore first. The "Single Class" policy—which ranks neurons based on their average activation for a specific target class—was found to be the most effective.

2. Tighter Max-Pooling Bounds

Max-pooling layers are non-linear and difficult for solvers to handle. The authors proposed a novel linear relaxation—a way to approximate the max function using linear constraints—that is mathematically tighter than previous methods used in tools like Planet or DeepPoly.

Evaluation and Key Insights

The framework was evaluated using the MNIST digit recognition dataset across three distinct CNN architectures ranging from ~2,700 to ~4,600 neurons. These networks served as the benchmark for testing adversarial robustness queries.

Key findings include:

  • The "Cone Effect": The real power of abstraction in CNNs comes from local connectivity. Removing a few edges in a deep layer can make many preceding neurons irrelevant, allowing the solver to ignore them entirely.
  • Efficiency in "UNSAT" Cases: Abstraction is incredibly effective for instances where the property is true (no attack is possible). These can often be proven on very small, highly abstracted networks.
  • Performance Gains: Integrated with the Marabou verifier, Cnn-Abs reduced average runtime by 15.7% and achieved a median runtime reduction of 24.6%. Out of 900 test queries, Cnn-Abs solved 573, while vanilla Marabou solved only 506—a ~13% improvement.

Conclusion and Future Directions

Cnn-Abs demonstrates that abstraction-refinement is a powerful tool for scaling CNN verification. While currently limited to layer-by-layer abstraction, future work may explore multi-layer abstraction and better utilization of spurious counterexamples to speed up "SAT" results (where an attack is found). The principles established here could potentially be adapted for other complex, non-convolutional architectures.

Summary updated

BibTeX
@inproceedings{ostrovsky2022abstraction,
  author = {Matan Ostrovsky and Clark W. Barrett and Guy Katz},
  title = {{An Abstraction-Refinement Approach to Verifying Convolutional Neural Networks}},
  booktitle = {ATVA},
  year = {2022},
  doi = {10.1007/978-3-031-19992-9\_25},
}
Figure