Abstract
Deep neural networks are often viewed as "black boxes," lacking formal guarantees for safety-critical applications. This paper presents a framework for the formal verification of Binarized Neural Networks (BNNs) by translating them into exact Boolean formulas. By leveraging SAT and ILP solvers, the authors demonstrate how to mathematically prove properties such as local robustness and invertibility, moving beyond heuristic testing to rigorous mathematical certainty.
Introduction
While deep learning has achieved remarkable success, the opacity of these models poses significant risks in safety-critical domains. Two primary concerns are adversarial robustness—where small, imperceptible perturbations can lead to catastrophic failure—and the lack of formal trust. Standard networks using floating-point arithmetic are difficult to model logically. This work addresses these challenges by focusing on Binarized Neural Networks (BNNs), where weights and activations are restricted to binary values (\pm 1).
Methodology: Exact Boolean Encoding
The core contribution is an exact Boolean encoding of BNN architectures. Unlike previous approaches that rely on approximations, this method provides a precise mapping from the neural network to formal logic.
Compositional Block Encoding
The authors utilize a compositional approach to handle the mixture of binary and real-valued operations within a BNN. While inputs and outputs are binary, intermediate steps like Batch Normalization (BN) involve real numbers.
As shown in Figure 1, the network is viewed as a sequence of blocks. The internal blocks consist of a Linear (LIN) layer, Batch Normalization (BN), and Binarization (BIN). The output block replaces binarization with an ARGMAX operation.
Mathematical Formulation
The encoding treats each block as a thresholding operation. By composing these layers, the real-valued intermediate steps are simplified into "reified cardinality constraints," which count the number of active inputs to determine the binary output.
Figure 3 details the mathematical transformations within each block. By representing the sign function and batch normalization as a single thresholding step, the authors bypass the complexity of real-valued arithmetic, making the model digestible for Boolean Satisfiability (SAT) and Integer Linear Programming (ILP) solvers.
Experimental Evaluation
The framework was evaluated on two distinct tasks:
- MNIST Robustness: Testing the network's resilience to adversarial perturbations on handwritten digits.
- Porous Media Inversion: A design task involving 16x16 images of physical structures. The goal was to "invert" the network to find input structures that satisfy specific physical property requirements (dispersion coefficients).
Key Results and Insights
- Verified Robustness: The authors successfully proved that specific MNIST images were "certifiably \epsilon-robust." In cases where robustness failed, the framework identified the exact minimal perturbation required to flip the classification.
- Successful Inversion: For the porous media dataset, the framework successfully synthesized input images that met complex output constraints, demonstrating the power of formal methods in generative-style tasks.
- Logic-Friendly BNNs: The study highlights that BNNs are uniquely suited for formal verification because the "gap" between the neural network and a logic circuit is significantly smaller than in traditional floating-point networks.
Conclusion and Future Work
This research provides a rigorous path toward trustworthy AI through exact formal analysis. While the current framework handles medium-sized networks, scalability remains a challenge for state-of-the-art "giant" models. Future work includes extending these techniques to generative models like GANs and leveraging formal proofs to extract human-readable explanations for model decisions.
This paper was originally presented at IJCAI-18.
Summary updated