An Efficient Method to Measure Robustness of ReLU-Based Classifiers via Search Space Pruning

Deep Neural Networks (DNNs) have achieved high accuracy on image classification. However, a small disturbance to an input may fool the networks to misclassify the label, which can cause a series of security and social problems. Thus, the robustness of DNNs must be ensured, particularly to those safety-critical systems. In this paper, we focus on the problem of measuring the robustness of ReLU-based DNNs, which can be equivalently formulated to solve a Mixed Integer Linear Programming problem (MILP). The complexity of solving MILP is directly related to the number of integer variables. We propose an efficient method for robustness measurement and verification by pruning the search space of MILP problems. Particularly, we design a greedy algorithm based on linear programming (LP) to determine the reasonable boundary. Then the search space is pruned by setting the boundary to integer variables in MILP. The comparison experiments on five classifiers trained on MNIST and CIFAR-10 datasets show our method outperforms other related tools in terms of efficiency and accuracy.