Efficient Preimage Approximation for Neural Network Certification
This work addresses the need for reliable neural network certification in safety-critical applications like traffic sign recognition, representing an incremental improvement over existing methods.
The paper tackles the problem of certifying neural networks against patch attacks by extending the PREMAP method with tighter bounds, adaptive Monte Carlo sampling, and improved branching heuristics, enabling scaling to convolutional neural networks and outperforming the original approach.
The growing reliance on artificial intelligence in safety- and security-critical applications demands effective neural network certification. A challenging real-world use case is "patch attacks", where adversarial patches or lighting conditions obscure parts of images, for example, traffic signs. A significant step towards certification against patch attacks was recently achieved using PREMAP, which uses under- and over-approximations of the preimage, the set of inputs that lead to a specified output, for the certification. While the PREMAP approach is versatile, it is currently limited to fully-connected neural networks of moderate dimensionality. In order to tackle broader real-world use cases, we present novel algorithmic extensions to PREMAP involving tighter bounds, adaptive Monte Carlo sampling, and improved branching heuristics. Firstly, we demonstrate that these efficiency improvements significantly outperform the original PREMAP and enable scaling to convolutional neural networks that were previously intractable. Secondly, we showcase the potential of preimage approximation methodology for analysing and certifying reliability and robustness on a range of use cases from computer vision and control.