Abstract
Deep neural networks (DNNs) have a wide range of applications, and softwareemploying them must be thoroughly tested, especially in safety criticaldomains. However, traditional software testing methodology, including testcoverage criteria and test case generation algorithms, cannot be applieddirectly to DNNs. This paper bridges this gap. First, inspired by thetraditional MC/DC coverage criterion, we propose a set of four test criteriathat are tailored to the distinct features of DNNs. Our novel criteria areincomparable and complement each other. Second, for each criterion, we give analgorithm for generating test cases based on linear programming (LP). Thealgorithms produce a new test case (i.e., an input to the DNN) by perturbing agiven one. They encode the test requirement and a fragment of the DNN by fixingthe activation pattern obtained from the given input example, and then minimizethe difference between the new and the current inputs. Finally, we validate ourmethod on a set of networks trained on the MNIST dataset. The utility of ourmethod is shown experimentally with four objectives: (1)~bug finding; (2)~DNNsafety statistics; (3)~testing efficiency and (4)~DNN internal structureanalysis.