Software Testing for Machine Learning

Challenges of testing ML stem from the innate complexity of the underlying stochastic reasoning. Unlike traditional systems, for which the code is built deductively, ML systems are generated inductively. The logic defining system behavior is inferred from training data. Consequently, a fault could originate not only from a faulty software code, but also errors in training data. However, existing approaches often assume that high quality datasets are warranted, without applying systematic quality evaluation. Furthermore, ML systems require advanced reasoning and learning capabilities that can give answers in conditions where the correct answers are previously unknown (?). Even though this may be the case for traditional systems, ML systems have inherent non-determinism which makes them constantly change behavior as more data becomes available, unlike traditional systems (?). Furthermore, for a system containing multiple ML models, the models will affect each other’s training and tuning, potentially causing non-monotonic error propagation (?).

We elaborate further challenges of testing ML in the following sections. Specifically, we identify six key challenge areas and discuss their implications. We synthesize existing work pertaining to these challenges and provide its structured presentation corresponding to the identified challenges.

Metamorphic testing is another approach to testing of software without test oracles. In this approach, a transformation function is used to modify the existing test case input, and produce a new output. If the actual output for the modified input differs from the expected output, it is indicative of errors in the software under test. Metamorphic testing has been applied to machine learning classifiers (?) (?). However, in testing ML systems with a large input space, writing metamorphic transformations is laborious, and there is a great potential for ML to circumvent this difficulty by automating the creation of metamorphic relationships.

Since automated oracles are typically not available for testing of big and realistic ML models, there is a great effort involved in manual labeling of test data for ML models. DeepGini (?) is an initial work on reducing the effort in labeling test data for DNNs by prioritizing tests that are likely to cause misclassifications. The assumption made by DeepGini is that a test is likely to be misclassified if a DNN outputs similar probabilities for each class. The limitation of this approach is that it requires running all tests first, to obtain the output vectors used to calculate the likelihood of misclassification.

The first attempts to define coverage metrics for testing of neural networks are inspired by the traditional code coverage metrics. A metric called neuron coverage was proposed in DeepXplore (?) for testing deep neural networks (DNN). DeepXplore measures the amount of unique neurons activated by a set of inputs out of the total number of neurons in the DNN. The limitation of this coverage metric is that a test suite that has full neuron coverage (all neurons activated) can still miss to detect erroneous behavior if there was an error in all other DNNs that were part of a differential comparing (?) used by neuron coverage (DeepXplore leverages the concept of differential testing). Furthermore, it has been shown that neuron coverage can be too coarse a coverage metric, meaning that a test suite that achieves full neuron coverage can be easily found, but the network can still be vulnerable to trivial adversarial examples (?). Sun et al. therefore proposed DeepCover, a testing methodology for DNNs with four test criteria, inspired by the modified condition/decision coverage (MC/DC) for traditional software. Their approach includes a test case generation algorithm that perturbs a given test case using linear programming with a goal to encode the test requirement and a fragment of the DNN. The same author also developed a test case generation algorithm based on symbolic approach and the gradient-based heuristic (?). The difference between their coverage approach, based on MC/DC criterion, and neuron coverage is that the latter only considers individual activations of neurons, while the former considers causal relations between features at consecutive layers of the neural network.

Neuron coverage has been further extended in DeepGauge (?), which aims to test DNN by combining the coverage of key function regions as well as corner case regions of DNN, represented by neuron boundary coverage. Neuron boundary coverage measures how well the test datasets cover upper and lower boundary values. DeepRoad (?) is another test generation approach for DNN-based autonomous driving. DeepRoad is based on generative adversarial networks and it generates realistic driving scenes with various weather conditions. DeepCruiser is an initial work towards testing recurrent-neural-network (RNN)-based stateful deep learning (?). DeepCruiser represents RNN as an abstract state transition system and defines a set of test coverage criteria for generating test cases for stateful deep learning systems. Other approaches were proposed extending the notion of neuron coverage, such as DeepTest (?) for testing other types of neural networks. DeepTest applies image transformations such as contrast, scaling, blurring to generate synthetic test images. However, such generated images were found to be insufficiently realistic for testing real-world systems.

In summary, a common limitation of techniques based on neuron coverage is that they can easily lead to combinatorial explosion. Ma et al. initiated the work on the adaptation of combinatorial testing techniques for the systematic sampling of a large space of neuron interactions at different layers of DNN (?). This approach can be promising for taming combinatorial explosion in testing of DNN based systems, given that its current limitations are overcome. First, only 2-way interactions of input parameters are supported, while real systems typically have much higher interaction levels of inputs. Second, the approach has been found to face scalability problems for large and complex DNNs.

Since the input space of DNNs is typically large and highly-dimensional, selecting test data for DNNs can be highly laborious. One approach to deal with this challenge is fuzzing, which generates large amounts of random input data that is checked for failures. TensorFuzz is an initial work that applies fuzzing to testing of TensorFlow DNNs (?). TensorFuzz uses a coverage metric consisting of user-specified constraints to randomly mutate inputs. The coverage is measured by a fast approximate nearest neighbour algorithm. TensorFuzz has showed to outperform random testing. Another similar approach is DeepHunter (?). This is an initial work on automated feedback-guided fuzz testing for DNNs. DeepHunter runs metamorphic mutation to generate new semantically preserved tests, and uses multiple coverage criteria as a feedback to guide test generation from different perspectives. The limitation of this approach is that it uses only a single coverage criteria at the time, not supporting multi-criteria test generation. Moreover, the general limitation of fuzzing is that it cannot ensure that certain test objectives will be satisfied.

To provide more effective input selection that increases test coverage, a concolic testing approach has been proposed in DeepConcolic (?). The approach is parameterised with a set of coverage requirements. The requirements are used to incrementally generate a set of test inputs with a goal to improve the coverage of requirements by alternating between concrete execution (testing on particular inputs) and symbolic execution. For an unsatisfied requirement, a test input within the existing test suite that is close to satisfying that requirement is identified, based on concrete execution. Later, a new test input that satisfies the requirement is generated through symbolic execution and added to the test suite, improving test coverage.

To evaluate the quality of test dataset for DNNs, DeepMutation (?) proposes an initial work, inspired by traditional mutation testing concepts. DeepMutation first designs a set of mutation operators to inject faults into training data. Then, it retrains models with the mutated training data to generate mutated models, which means that faults are injected in the models. After that, mutated models are tested using a test dataset. Finally, the quality of the test dataset is evaluated by analysing to what extent the injected faults are detected. The limitation of this approach is that it employs basic mutation operators covering limited aspects of deep learning systems, so that the injected faults may not be representative enough of real faults. MuNN (?) is another mutation testing approach for neural networks, which needs further work for the application on DNNs. Specifically, the authors of the approach showed that neural networks of different depth require different mutation operators. They also showed the importance of developing domain-dependent mutation operators rather than using common mutation operators.

Adversarial examples can be generated for the purpose of attack or defense of an ML classifier. The former often use heuristic algorithms to find adversarial examples that are very close to correctly classified examples. The latter aim to improve the robustness of ML classifiers.

Some approaches to adversarial example generation include Fast Gradient Sign Method (FGSM) (?), which showed that linear behavior in high-dimensional spaces is sufficient to cause adversarial examples. Later, FGSM was shown to be less effective for black-box attacks (?), and the authors developed RAND-FGSM method which adds random perturbations to modify adversarial perturbations. DeepFool (?) is another approach that generates adversarial examples based on an iterative linearization of the classifier to generate minimal perturbations that are sufficient to change classification labels. The limitation of this approach lies in the fact that it is a greedy heuristic, which cannot guarantee to find optimal adversarial examples. Further, a two-player turn-based stochastic game approach was developed for generating adversarial examples (?). The first player tries to minimise the distance to an adversarial example by manipulating the features, and the second player can be cooperative, adversarial, or random. The approach has shown to converge to the optimal strategy, which represents a globally minimal adversarial image. The limitation of this approach is long runtime. Extending the idea of DeepFool, a universal adversarial attack approach was developed (?). This approach generates universal perturbations using a smaller set of input data, and uses DeepFool to obtain a minimal sample perturbation of input data, which is later modified into a final perturbation.

Adversarial examples can be generated with generative adversarial networks, such as AdvGAN (?). This approach aims to generate perturbations for any instance, which can speed up adversarial training. The limitation of the approach is that the resulting adversarial examples are based on small norm-bounded perturbations. This challenge is further addressed in (?) by developing unrestricted adversarial examples. However, their approach exploits classifier vulnerability to covariate shift and is sensitive to different distributions of input data.

To counter adversarial attacks, reactive and proactive defensive methods against adversaries have been proposed. Defensive distillation is a proactive approach which aims to reduce the effectiveness of adversarial perturbations against DNNs (?). Defensive distillation extracts additional knowledge about training points as class probability vectors produced by a DNN. The probability vectors are fed back into training, producing DNN-based classifier models that are more robust to perturbations. However, it has been shown that such defensive mechanisms are typically vulnerable to some new attacks (?). Moreover, just like in testing, if a defense cannot find any adversarial examples, it does not mean that such examples do not exist.

Automated verification is a reactive defensive approach against adversarial perturbations which analyses the robustness of DNNs to improve their defensive capabilities. Several approaches exist to deal with the robustness challenge. An exhaustive search approach to verifying the correctness of a classification made by a DNN has been proposed (?). This approach checks the safety of a DNN by exploring the region around a data point to search for specific adversarial manipulations. The limitation of the approach is limited scalability and poor computational performance induced by state-space-explosion. Reluplex is a constraint-based approach for verifying the properties of DNNs by providing counter-examples (?), but is currently limited to small DNNs. An approach that can work with larger DNNs is global optimization based on adaptive nested optimisation (?). However, the approach is limited in the number of input dimensions to be perturbed. A common challenge for verification approaches is their computational complexity. For both approaches (?) and (?), the complexity is NP-complete. For the former, the complexity depends on the number of hidden neurons, and for the latter, on input dimensions.

Lack of robustness in neural networks raises valid concerns about the safety of systems relying on these networks, especially in safety-critical domains such as transportation, robotics, medicine, or warfare. A typical approach to improve the robustness of a neural network would be to identify adversarial examples that make the network fail, then augment the training dataset with these examples and train another neural network. The robustness of the new network is the ratio between the number of adversarial examples that failed the original network and that were found for the new network (?). The limitation of this approach is the lack of objective robustness measure (?). Therefore, a metrics for measuring the robustness of DNNs using linear programming (?) was proposed. Other approaches include defining the upper bound on the robustness of classifiers to adversarial perturbations (?). The upper bound is found to depend on a distinguishability measure between the classes, and can be established independently of the learning algorithms. In their work, Fawzi et al. report two findings: first, non-linear classifiers are more robust to adversarial perturbations than linear classifiers, and second, the depth (rather than breath) of a neural network has a key role for adversarial robustness.

There is a difficulty of reproducing some of the methods developed for improving the robustness of neural networks or methods for comparing experimental results, as different sources of adversarial examples in the training process can make adversarial training more or less effective (?). To alleviate this challenge, Cleverhans (?) and Foolbox (?) are adversarial example libraries for developing and benchmarking adversarial attacks and defenses, so that different benchmarks can be compared. The limitation of both of these frameworks is that they lack defensive adversarial generation strategies (?). Robust Vision Benchmark ²²2http://robust.vision/benchmarks/leaderboard extends the idea of Foolbox, by allowing the development of novel attacks which are used to further strengthen robustness measurements of ML models. Other initiatives include a competition organized at NIPS 2017 conference by Google Brain, where researchers were encouraged to develop new methods for generating adversarial examples and new methods for defense against them (?).

For safety-critical domains which need to comply with safety regulation and certification, it is of critical importance to provide formal guarantees of performance of ML under adversarial input perturbations. Providing such guarantees is a real challenge of most of defense approaches, including the approaches discussed above. Existing attempts in this direction include (?), by using regularization in training, and (?), by updating the training objective to satisfy robustness constraints. While these initial approaches are interesting, they can provably achieve only moderate levels of robustness, i.e. provide approximate guarantees. As such, further research advances on providing robustness guarantees for ML models are needed.