In this position paper, we are interested in what test coverage measures can, and cannot, tell us about neural networks. We begin with a review of the role of test coverage measures in traditional development approaches for safety-related software. We show how those coverage measures, in the neural network sense, cannot achieve the same aims as their equivalents in the traditional sense. We provide indications of approaches that can partially meet those aims. We also indicate the utility of current neural network coverage measures.
Neural Networks (NNs) have demonstrated significant
utility in a range of safety and security related applications (e.g.
autonomous cars
NNs are different to traditional software. We contend that: these differences fundamentally change the meaning of several types of test coverage (e.g. requirements and structural measures); there are approaches that can partially achieve the intent of these traditional test coverage measures in an NN context; and currently-proposed measures of NN test coverage have utility in different ways.
The remainder of this paper is structured as follows: Section 2 provides an overview of the role of test coverage measures in the development of traditional safety-related software; Section 3 summarises a selection of NN test coverage measures proposed in the literature; Section 4 outlines NNbased approaches that can achieve some of the aims of traditional test coverage; Section 5 summarises the value that can be gained from current NN coverage measures; Section 6 concludes the paper.
Our discussion of safety-related software development is
based on DO-178C
Before the discussion, we note that although a
significant amount of practical experience provides confidence in
DO-178C, and its predecessor, DO-178B, there is little, if
any, explicit evidence to support the specific coverage
criteria that are used
The development of safety-related software begins with system-level requirements that have been allocated to software. These high-level requirements are hierarchically decomposed, in a traceable manner, from requirements that detail ‘what’ behaviour is needed, down to requirements that detail ‘how’ to achieve this. The software requirements are also independently used to produce test cases in a Requirements-Based Testing (RBT) approach. The tests are run and the coverage of the code structure is measured dynamically. RBT is an attractive approach to test design since it acknowledges that exhaustive testing is (generally speaking) infeasible and it focusses on the demonstration of the intended behaviour.
Assuming all tests pass, if structural coverage is incomplete then one of the following three conditions holds, where the notion of correctness directly relates to the intent of the high-level requirements:
The software’s behaviour is correct, but the software-level requirements are incomplete; The software-level requirements are correct, but the software includes additional, unnecessary behaviour (we include unreachable as well as redundant code here); The software behaviour and software-level requirements are correct, but the test set is incomplete. This includes, for example, cases where development tools introduce code for runtime efficiency.
Considering all three of these conditions provides confidence that (once a suitable level of coverage has been achieved) the code sufficiently implements the requirements and, furthermore, it contains no undesirable additional behaviour. The link between requirements and behaviour is important, because requirements are the key mechanism for communicating expectations about software behavoiur with actors in the development, test and integration of the software.
Structural coverage is typically measured at the software unit level. Equivalently, at this level behaviour can be defined, and verified. Hierarchical decomposition of requirements, supported by architectural design, provides confidence that unit-level behaviour can be aggregated to provide the required system-level behaviour. Not all behaviour can be tested at this level, thus testing continues through the integration processes.
The type of structural coverage that is required depends
on the criticality of the software. In less-critical cases,
statement coverage suffices; more demanding cases require
branch coverage; and the most critical cases require
Modified Condition / Decision Coverage (MCDC)
The combination of RBT and coverage measurement is
important. Even though behaviour is, typically, not strongly
data-dependent, there is still value in using suitably realistic
test values. Simply optimising a test set to achieve a given
level of coverage, with little or no consideration of the
requirements, is less effective than RBT
In summary, for traditional software: hierarchical decomposition of requirements means that software behaviour can be understood at the unit level; independent interpretation of requirements provides confidence that requirements have been implemented correctly; and the combination of RBT and structural test coverage provide confidence that the requirements suitably describe the software’s behaviour, both what it does and what it does not do.
Our main interest is in Artificial Intelligence (AI), particularly AI implemented using Machine Learning (ML) techniques. Due to their prevalence, we focus on NNs, but much of what follows is applicable to other forms of ML.
Historically, NN testing was based on measures like
precision and recall, calculated using a set of data that was held
back from training. The inadequacy of these measures is
demonstrated by adversarial inputs
More recently, a variety of coverage measures, based on internal properties of an NN, have been proposed. It should be noted that, to the best of our knowledge, use of these measures has thus far been demonstrated using von Neumann architecture hardware. For some, different, architectures it may not be efficient or even possible to collect the information on which these measures are based.
Some notable example coverage measures are summarised below.
DeepXplore
DeepGauge
Neuron-level coverage splits the output range of each neuron (established during the training phase) into k equal sections. The k-multisection coverage of that neuron is the fraction of sections that the neuron’s output falls into across all inputs in the test set. The k-multisection coverage of the NN is the average of these neuron coverages. Layer-level coverage is based on the l neurons, and combinations thereof, in each layer that have the greatest output value. Top-l neuron coverage is the fraction of neurons that are in the top l neurons in their layer for at least one of the test inputs.
DeepCT
Sparse coverage considers the fraction of m-way subsets in which all neurons are activated for at least one test input. For example, a layer of four neurons will have six 2-way subsets.
Dense coverage considers the fraction of m-way activation patterns that are activated for at least one test input. For example, a 2-way subset has four activation patterns.
DeepConcolic
Sign-sign coverage measures whether the change in output sign (i.e. moving from zero to non-zero) of a neuron in layer n independently affects the output sign of a specific neuron in layer n + 1 (i.e. the subsequent layer). Value-value coverage measures whether a change in output value (e.g. similar to the k-sections used by DeepGauge) of a neuron in layer n independently affects the output value of a specific neuron in layer n + 1. The notions of sign-value and value-sign coverage naturally follow.
These measures show a progression, from simple aspects of individual neuron behaviour (e.g. activation or nonactivation), through more complex aspects of individual neuron behaviour, to the joint behaviour of combinations of neurons, either in the same layer or in neighbouring layers. 4
For the purposes of this paper, we are primarily concerned
with structural coverage (although we remain interested in
requirements throughout). For completeness, we note that
other attributes will be important in an overall assurance
argument supporting the use of an NN. A key area is the NN
development process. This is covered in detail in
Recall, traditional software test structural coverage measures, when used in conjunction with RBT, provide a level of confidence that software satisfies requirements and requirements cover software behaviour. When viewed in that light it is apparent that the types of NN coverage measures discussed above cannot achieve the same aims as traditional software coverage measures. As illustrated in the following paragraphs, none of the requisite building blocks, which allow traditional coverage to work in this way, are present in the NN context.
We do not have a complete set of requirements. There is often a good understanding of the purpose of an NN, for example: ‘recognise hand-written digits’ or ‘determine sentiment from social media messages’. However, in our experience, there is rarely, if ever, a set of requirements that is accurate, complete, unambiguous and verifiable.
Not all NN requirements can be hierarchically
decomposed. Some level of methodical decomposition is often
possible; for example, ‘recognise hand-written digits’ could be
decomposed to explicitly cater for ‘triangular 4s’, ‘open 4s’
and ‘crossed 7s’. But, requirements like these cannot be
decomposed to a level that can be directly coded against. In
particular, in a safety-related environment, if we could
decompose to a directly-codeable level then there would be no
need to use an NN and traditional software would be the
preferred approach
We do not have a meaningful software unit level at which
software behaviour can be described. As indicated
previously, current NN coverage measures focus on neuron
behaviour, either individually or in patterns. Although this
behaviour controls the network’s output, it does not (and
cannot) describe software behaviour in a way that is meaningful
to a user. Some approaches to explainability may help, for
example: identifying pixels that positively weight towards a
particular class
One of the strengths of NNs is their ability to generalise from incomplete specifications. It may seem that asking for a demonstration that an NN satisfies a set of requirements negates this strength.
From our perspective, the distinction is in the level at which requirements are expressed. Placing, and verifying, requirements on the network’s internals does not provide traceability between requirements and behaviour. That traceability might be achieved by placing (an appropriate set of) requirements on the NN’s Input ! Output behaviour.
Adversarial examples
DeepPoly
Marabou (Katz et al. 2019) is an SMT-based tool that can
be used to check whether a particular NN satisfies a specific
property. If the property is not satisfied then a concrete input
for which the property is violated (i.e. a counter-example)
is provided. Amongst other things, the tool has been used
to prove properties about an Airborne Collision Avoidance
System (ACAS) for unmanned aircraft
Deep Learning with Differentiable Logic (DL2)
Even if the (suitably-measured) performance of an NN
is adequate, this does not necessarily mean that an NN is
making decisions in the same way as a human would. There
is evidence that NNs use highly-predictive, but non-intuitive
(to a human) features to support classification
As noted earlier, a key question is whether there are aspects of software behaviour that are not captured by the requirements. That is, if a user fully understands the requirements then will they ever be surprised by the software’s behaviour? This latter formulation is helpful as it clarifies what we mean by ‘behaviour’. In particular, we are interested in behaviour that is externally observable. From the perspective of an NN, we are primarily interested in behaviour in the sense of Input ! Output mappings.
In the NN context, one way of categorising different
contributors to behaviour is by considering different types of
input. Four related spaces are defined in
Using this structure there are a number of techniques
that can help increase coverage of potential NN behaviour:
space-filling designs for computer experiments
These approaches provide a ‘forward-looking’ way of understanding behaviour; they rely on choosing inputs to invoke behaviour. This differs from the approach to traditional software requirements and structural coverage, where behaviour is invoked, in a sense, from within the behavioural regimes defined in the low-level requirements structure.
Generative Adversarial Networks (GANs) could help fill this gap. For example, they could be used to find plausible operational domain inputs that exhibit different behaviours to those observed in the training data. These could be inputs that are similar to training samples but result in different outputs; for classification networks, this is the same as finding adversarial inputs. Alternatively, they could be used to find inputs that are sufficiently different from any sample in the training data.
Another approach involves looking for specific undesirable behaviours in an NN. Detection and mitigation of backdoor attacks (Wang et al. 2019) is one example.
In some cases, specifically for feed-forward networks, it may be possible to automatically infer formal properties (Gopinath et al. 2019). This is a helpful way of understanding aspects of the NN’s behaviour. However, there is no guarantee that the inferred properties will be meaningful, in the sense of system-level requirements.
The way that NN are constructed means test coverage measures cannot perform the same function as they do for traditional software. There are a number of approaches that can be used to provide some confidence that the NN satisfies requirements. There are also approaches that can provide some confidence that the NN’s behaviour is understood. 5
The previous discussion highlights a distinction between the implicit motivation for NN coverage measures and their utility. We propose four ways in which NN coverage measures, like those discussed in Section 3, could have utility.
Firstly, following the analogy that training data represent the low-level behavioural requirements, the measures could be used to optimise training data, for example, by identifying whether a larger, or more diverse, training set was exercising a larger portion of internal network behaviour. If it is then this is an argument for using an alternative, possibly larger, data set, despite the additional overheads and increased risk of over fitting.
Secondly, the measures could be used to compare training data, used during development, with verification data, used by an independent team. Suppose, for example, that the full set of training and verification data achieves greater coverage than just the training data. This outcome would demonstrate the independent verification activity is exercising additional types of internal NN behaviour to those observed during the development phase. This could be evidence that a suitably independent verification activity has been conducted.
Thirdly, many of the approaches used to measure NN coverage can also be used to generate additional inputs that would extend coverage. As such, they provide an indication of ways in which training data could be meaningfully extended. Obviously, for situations where the NN is being developed using supervised learning, the appropriate output needs to be produced for each of these new inputs.
Fourthly, the measures can be used to choose between two different NNs that otherwise offer similar levels of performance. In such situations, the NN for which a fixed set of training data achieves greater coverage might be preferred. In general, this would be expected to be the NN with the simpler structure.
6
NNs have demonstrated significant utility. Their use in safety-related systems is predicated on confidence in their behaviour, both what they do and what they do not do. For traditional safety-related software much of this confidence comes from test coverage measures in an RBT context. The approaches used to measure test coverage for NNs cannot provide an equivalent confidence.
There are approaches that can provide some aspects of this confidence. Appropriate consideration of different input spaces can help, as can GAN-based methods for finding ‘new’ inputs. NN test coverage measures can provide value in other ways. They can, for example, provide a principled, structured way of choosing between different training data sets, or between different trained models.
In conclusion, NN test coverage measures can have significant utility. They represent different types of confidence than is found in their traditional software testing forebears. However, more work is required before a holistic and complete understanding is achieved in the relationship between the coverage measures and confidence in NN behaviour.
This document is an overview of UK MOD sponsored research and is released for informational purposes only. The contents of this document should not be interpreted as representing the views of the UK MOD, nor should it be assumed that they reflect any current or future UK MOD policy. The information contained in this document cannot supersede any statutory or contractual requirements or liabilities and is offered without prejudice or commitment.