Output Range Analysis for Deep Neural Networks

Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, Ashish TiwariarXiv 2017 · arXiv

Introduction

As deep neural networks (DNNs) are increasingly integrated into high-assurance systems such as autonomous vehicles and robotic controllers, the need for formal safety guarantees becomes paramount. Unlike traditional software, DNNs often act as "black boxes," making it difficult to predict their behavior under all possible conditions. A critical challenge in verifying these systems is range estimation: determining the absolute maximum and minimum values a network can output given a specific range of inputs (often defined as a convex polyhedron).

Because DNNs are non-linear and non-convex, finding these global extrema is notoriously difficult. Traditional optimization methods frequently converge on local minima, while exhaustive formal verification techniques often fail to scale to the depth and complexity of modern architectures. To bridge this gap, researchers have introduced SHERLOCK, a hybrid tool designed to efficiently calculate guaranteed output ranges for ReLU-based networks.

Methodology: The Hybrid Search Approach

SHERLOCK employs a dual-mode algorithm that alternates between fast local exploration and rigorous global certification. This strategy exploits the fact that networks using Rectified Linear Unit (ReLU) activation functions are piecewise affine, meaning they behave linearly within specific local regions.

  1. Local Search (The Sprinter): This phase utilizes a steepest projected gradient ascent. By identifying locally active regions where the network is linear, SHERLOCK solves a fast Linear Program (LP) to reach a local peak quickly.
  2. Global Search (The Certifier): When the local search plateaus, the algorithm switches to a Mixed Integer Linear Program (MILP). Rather than solving the entire global optimization problem—which is computationally prohibitive—it asks a simpler feasibility question: "Does any input exist that produces an output higher than our current peak plus a small tolerance $\delta$?"
Figure 2: Illustration of the hybrid search process, showing local search steps ($L_i$) interspersed with global jumps ($G_i$) to find the global maximum.

If the global search identifies a better point (a "witness"), it hands that coordinate back to the local search to continue climbing. If the global search returns no such point, the current value is mathematically certified as the global maximum within the specified tolerance.

Experimental Evaluation

The effectiveness of SHERLOCK was evaluated across several diverse benchmarks:

  • Randomly Generated Networks: 100 networks of varying depth and width were used to test raw scalability.
  • Microbenchmarks: Six 2-input, 1-output functions with highly non-convex landscapes were used to test the algorithm's ability to escape local minima.
  • Nonlinear Control Plant: A model simulating a robotic controller to test real-world control applications.
  • MNIST Robustness: A classic image classification task where the tool was used to prove that small perturbations (noise) would not cause misclassification.

Key Results and Scalability

SHERLOCK demonstrates significant improvements over previous state-of-the-art solvers like Reluplex. In scalability tests, SHERLOCK successfully processed networks with up to 1,500 neurons, whereas competing tools often timed out on networks with as few as 250 neurons. On complex microbenchmarks, SHERLOCK consistently found global ranges in under 10 minutes, tasks that took other solvers over an hour or resulted in failure.

Figure 4: Robustness analysis on an MNIST digit '5'. SHERLOCK can mathematically guarantee that noise within a specific pixel block will not change the network's classification.

In practical applications, the tool was used to verify the robustness of an MNIST classifier. It mathematically proved that no amount of tampering within a $5 \times 10$ pixel block could flip the classification label of a specific digit, providing a level of certainty unattainable through standard testing.

Limitations and Future Directions

While SHERLOCK represents a major step forward, it currently has limitations. It is optimized for ReLU activation functions and does not yet support smooth activations like Sigmoid or Tanh. Additionally, it is restricted to feedforward architectures. Future work will focus on extending these techniques to Recurrent Neural Networks (RNNs) and exploring faster alternatives to MILP to further reduce the computational cost of the global search phase.

Summary updated

Abstract

Deep neural networks (NN) are extensively used for machine learning tasks such as image classification, perception and control of autonomous systems. Increasingly, these deep NNs are also been deployed in high-assurance applications. Thus, there is a pressing need for developing techniques to verify neural networks to check whether certain user-expected properties are satisfied. In this paper, we study a specific verification problem of computing a guaranteed range for the output of a deep neural network given a set of inputs represented as a convex polyhedron. Range estimation is a key primitive for verifying deep NNs. We present an efficient range estimation algorithm that uses a combination of local search and linear programming problems to efficiently find the maximum and minimum values taken by the outputs of the NN over the given input set. In contrast to recently proposed "monolithic" optimization approaches, we use local gradient descent to repeatedly find and eliminate local minima of the function. The final global optimum is certified using a mixed integer programming instance. We implement our approach and compare it with Reluplex, a recently proposed solver for deep neural networks. We demonstrate the effectiveness of the proposed approach for verification of NNs used in automated control as well as those used in classification.
BibTeX
@misc{dutta2017output,
  author = {Souradeep Dutta and Susmit Jha and Sriram Sankaranarayanan and Ashish Tiwari},
  title = {{Output Range Analysis for Deep Neural Networks}},
  year = {2017},
  eprint = {1709.09130},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.09130},
}
Figure