Output Range Analysis for Deep Neural Networks based on Simulated Annealing Processes

Unquestionably, in recent decades, Deep Neural Networks (DNNs) have been by far the most widely used tools to perform complex machine learning tasks. More recently, DNNs have been used in cyber-physical systems critical to public security and integrity; such as autonomous vehicle driving and air traffic systems. Therefore, it is of pressing interest to implement security verification systems for DNNs. One of the objectives in this line of interest is the verification of the maximum and minimum values assumed by a DNN, an objective commonly known as the range estimation problem, see Dutta et al. [2018], Wang et al. [2018]. However, the relationships established between the inputs and outputs of a DNN are highly non-linear and complex, difficult to understand with existing tools today. Due to this inability, DNNs are commonly referred to as black boxes. This nature of DNN makes the range estimation problem particularly challenging, because there is no geometric information about the response surface generated by a DNN. For example, if local geometric information about the generated surface were obtained, such as the gradient vector and the Hessian matrix at each point, the problem could be addressed with conventional nonlinear programming techniques. However, in a DNN it is only possible to obtain point information about the estimated response, without any local knowledge around that point.