  This paper proposes a black box based approach for analysing deep neural
networks (DNNs). We view a DNN as a function $\boldsymbol{f}$ from inputs to
outputs, and consider the local robustness property for a given input. Based on
scenario optimization technique in robust control design, we learn the score
difference function $f_i-f_\ell$ with respect to the target label $\ell$ and
attacking label $i$. We use a linear template over the input pixels, and learn
the corresponding coefficients of the score difference function, based on a
reduction to a linear programming (LP) problems. To make it scalable, we
propose optimizations including components based learning and focused learning.
The learned function offers a probably approximately correct (PAC) guarantee
for the robustness property. Since the score difference function is an
approximation of the local behaviour of the DNN, it can be used to generate
potential adversarial examples, and the original network can be used to check
whether they are spurious or not. Finally, we focus on the input pixels with
large absolute coefficients, and use them to explain the attacking scenario. We
have implemented our approach in a prototypical tool DeepPAC. Our experimental
results show that our framework can handle very large neural networks like
ResNet152 with $6.5$M neurons, and often generates adversarial examples which
are very close to the decision boundary.
