Formal Analysis of Deep Binarized Neural Networks

Nina Narodytska

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.

Architecture of a BNN showing internal blocks and the output layer.

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.

Mathematical structure of internal and output blocks used for Boolean encoding.

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:

  1. MNIST Robustness: Testing the network's resilience to adversarial perturbations on handwritten digits.
  2. 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

Abstract

Understanding properties of deep neural networks is an important challenge in deep learning. Deep learning networks are among the most successful artificial intelligence technologies that is making impact in a variety of practical applications. However, many concerns were raised about `magical' power of these networks. It is disturbing that we are really lacking of understanding of the decision making process behind this technology. Therefore, a natural question is whether we can trust decisions that neural networks make. One way to address this issue is to define properties that we want a neural network to satisfy. Verifying whether a neural network fulfills these properties sheds light on the properties of the function that it represents. In this work, we take the verification approach. Our goal is to design a framework for analysis of properties of neural networks. We start by defining a set of interesting properties to analyze. Then we focus on Binarized Neural Networks that can be represented and analyzed using well-developed means of Boolean Satisfiability and Integer Linear Programming. One of our main results is an exact representation of a binarized neural network as a Boolean formula. We also discuss how we can take advantage of the structure of neural networks in the search procedure.
BibTeX
@inproceedings{narodytska2018formal,
  author = {Nina Narodytska},
  title = {{Formal Analysis of Deep Binarized Neural Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/811},
}
Figure