Abstract
Robustness verification is a promising technique for rigorously proving Recurrent Neural Networks (RNNs) robustly. A key challenge is to over-approximate the nonlinear activation functions with linear constraints, which can transform the verification problem into an efficiently solvable linear programming problem. Existing methods over-approximate the nonlinear parts with linear bounding planes individually, which may cause significant over-estimation and lead to lower verification accuracy. In this paper, in order to tightly enclose the three-dimensional nonlinear surface generated by the Hadamard product, we propose a novel truncated rectangular prism formed by two linear relaxation planes and a refinement-driven method to minimize both its volume and surface area for tighter over-approximation. Based on this approximation, we implement a prototype DeepPrism for RNN robustness verification. The experimental results demonstrate that DeepPrism has significant improvement compared with the state-of-the-art approaches in various tasks of image classification, speech recognition and sentiment analysis.
Introduction
Verifying the robustness of neural networks involves mathematically proving that small perturbations to an input—such as a single changed pixel or background noise—will not alter the model's prediction. While this is well-studied for standard Feedforward Neural Networks (FNNs), Recurrent Neural Networks (RNNs) like LSTMs present unique challenges due to their "gated" nature.
Operations such as the Hadamard product ($\odot$), where two nonlinear functions are multiplied, create complex 3D surfaces. To make the verification problem computationally tractable, these surfaces are typically "over-approximated" using simple linear planes. However, if these planes are too loose, the verifier may incorrectly report vulnerability. Existing methods often solve for upper and lower bounding planes independently, leading to significant over-estimation.
Methodology: The DeepPrism Approach
DeepPrism introduces a geometric approach to finding tighter linear bounds by modeling the space between the upper and lower planes as a 3D "truncated rectangular prism."
Truncated Rectangular Prism Approximation
Instead of optimizing bounding planes in isolation, DeepPrism treats the enclosure as a single geometric entity. By minimizing a hybrid objective function—a weighted sum of the prism's volume and surface area—the framework achieves a tighter fit. Mathematical deduction reveals that volume is primarily controlled by the height of the centroid between the planes, while surface area relates to the spread or "roundness" of the approximation.
Multi-plane Refinement
To further enhance precision, DeepPrism employs a "divide-and-conquer" strategy. The input region is partitioned into smaller sub-regions (using either triangular or rectangular divisions). Gradient descent is then used to optimize the combination of these local approximations into a global bound. The researchers found that rectangular divisions generally provide more uniform coverage, particularly under higher levels of input perturbation.
Experimental Evaluation
DeepPrism was evaluated across three distinct domains to prove its versatility:
- Image Classification: MNIST (70,000 images of handwritten digits).
- Speech Recognition: Google Speech Commands (GSC) and the Free Spoken Digit Dataset (FSDD).
- Sentiment Analysis: Rotten Tomatoes Movie Review (RT) dataset (text-based classification).
Key Results
DeepPrism consistently outperformed state-of-the-art (SOTA) tools like Prover and RNN-Guard:
- Higher Accuracy: On the MNIST dataset, DeepPrism achieved 83% verification accuracy, compared to 45% for Prover and 40% for RNN-Guard.
- Better Scaling: As the number of layers or the dimension of the hidden state increased, DeepPrism maintained a significant lead in accuracy.
- Efficiency: Despite the more complex geometric optimization, DeepPrism often maintained competitive or even faster running times than baselines because it requires solving fewer Linear Programming (LP) problems (one joint problem vs. two independent ones).
- Multi-plane Gains: Moving from a single-plane to a 16-rectangle division significantly boosted accuracy in high-perturbation scenarios (e.g., jumping from 54% to 64% accuracy on MNIST at $\epsilon=0.020$).
Conclusion and Future Work
The authors acknowledge that while multi-plane refinement significantly increases accuracy, it comes with a computational trade-off. Finer divisions require more processing time, which might be a bottleneck for very large-scale models. Future work will focus on reducing the computational overhead of the multi-plane approach and enhancing the time efficiency of the gradient descent used to optimize sub-region weights.
Summary updated