CN120162269A - A multi-objective black-box test case selection method for deep neural networks - Google Patents

Abstract

The invention discloses a multi-target black box test case selection method facing a deep neural network, which comprises multi-target optimization, search space reduction and equidistant partition optimization, and aims to select as many test inputs capable of detecting different errors of a model for the test of the deep neural network as possible through two targets of optimization uncertainty and diversity under a given test budget; in the subsequent selection, the candidate set is divided into subgroups with equal size and similar uncertainty distribution by adopting the equidistant partition mode, and then an optimal test input is iteratively selected from each subgroup by utilizing a greedy strategy, so that the selected input has stronger error triggering capability and can also greatly improve the diversity of the selected test input.

Description

Deep neural network-oriented multi-target black box test case selection method

Technical Field

The invention relates to the technical field of software testing, and in particular relates to a multi-target black box test case selection method for a deep neural network, which is mainly applied to the field of testing of the deep neural network.

Background

In the actual test process of DNN, two key challenges are faced, namely, firstly, in order to comprehensively evaluate the performance of a model, a large number of test inputs need to be collected to detect the performance of the model under different scenes, however, a large amount of time and resources are required to be consumed for manually marking the test inputs, secondly, in certain specific application scenes, the number of the actually executable test inputs is often strictly limited due to the limitation of computing resources, the current DNN test selection method is mainly divided into a white box method and a black box method, the white box method guides the test selection by analyzing indexes such as neuron coverage, mutation test or model surprise evaluation, and the like, and the black box method only depends on the output result of the model or the characteristics of the test inputs per se to select, so that the method has better applicability.

While the early black box approach was based primarily on the "uncertainty" concept, while a number of studies demonstrated the effectiveness of uncertainty-based selection methods in triggering mispredictions, such approaches have a significant drawback in that excessive attention to uncertainty ignores the diversity of test inputs, possibly resulting in redundancy of the selected test set, and insufficient coverage of the various failure modes of DNN, to overcome the limitations described above, prior art DeepGD achieved more efficient test selection by optimizing both the two key objectives of uncertainty and diversity, but the approach had significant performance bottlenecks in that the non-dominant ranking genetic algorithm (NSGA-II) employed was computationally complex, along with considerable computational costs of the diversity metric, resulting in excessive overall computational overhead. This high computational cost severely limits the applicability of DeepGD to large-scale datasets.

Disclosure of Invention

The invention aims to provide a multi-target black box test case selection method oriented to a deep neural network, so as to solve the problems in the background technology.

In order to solve the technical problems, the invention provides a multi-target black box test case selection method facing a deep neural network, which comprises a reduction stage and a selection stage, wherein the reduction stage is used for screening candidate test inputs with higher uncertainty from an original test input set, introducing a dynamic reduction coefficient and a quick screening mechanism based on the uncertainty, and the selection stage is used for selecting a subset from the candidate set, equally dividing strategy and greedy selection mechanism by simultaneously optimizing the uncertainty and diversity

Preferably, the specific operating steps of the reduction phase are as follows:

Running all test inputs on a model to be tested to obtain corresponding output probabilities;

selecting uncertainty index to construct uncertainty calculation function ;

Calculating uncertainty values of all test inputs;

sequencing test inputs according to uncertainty values;

Setting a reduction coefficient ;

Determining a candidate set。

Preferably, the specific operating steps of the selection phase are as follows:

equidistant dividing of candidate sets ;

Selecting a diversity index to construct a diversity value calculation function;

Extracting characteristics of test input;

Calculating candidate test inputs for a selected set of test inputs As its diversity value;

Calculating the fitness value of the candidate test input;

Iteratively selecting an optimal test input in each subgroup;

Iteration end returns to the final selected subset of test inputs Manual labeling was performed for DNN testing.

Compared with the prior art, the invention has the following beneficial effects:

(1) According to the invention, through effective test input reduction and candidate set equidistant partition optimization, the calculation cost is obviously reduced, and the test input selection can be completed in a shorter time;

(2) In the test input selection process, uncertainty and diversity are optimized at the same time, and a new evaluation mechanism is designed, so that the selected test set can cover more various faults, and the efficiency is improved while higher fault detection capability is maintained;

(3) The selected test input has higher representativeness and information quantity, can provide more valuable guidance for model retraining, and in conclusion, the invention realizes remarkable improvement in the aspects of test efficiency, fault detection capability and model optimization guidance and provides a more efficient and reliable solution for the test and optimization of the deep neural network.

Drawings

The accompanying drawings are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate the invention and together with the embodiments of the invention, serve to explain the invention. In the drawings:

FIG. 1 is pseudo code of an algorithm implementation provided by an embodiment of the present invention;

Fig. 2 is a diagram illustrating an example of an overall flow provided by an embodiment of the present invention.

Detailed Description

In order to further describe the technical means and effects adopted by the present invention for achieving the intended purpose, the following detailed description will refer to the specific implementation, structure, characteristics and effects according to the present invention with reference to the accompanying drawings and preferred embodiments.

The embodiment of the invention provides a multi-target black box test case selection method facing a deep neural network, which comprises a reduction stage and a selection stage by combining with fig. 1 and 2

In this embodiment, the pseudo code shown in fig. 1 shows the detailed flow of the present invention, and compared with the prior art, the core innovation point of the present invention is that the calculation overhead is significantly reduced by optimizing the strategy in stages, and simultaneously, the uncertainty and diversity of the selected test input are ensured, so that the present invention still maintains higher fault detection capability;

In this embodiment, the reduction stage is shown in lines 3-6 of fig. 1, where the objective of the reduction stage is to screen candidate test inputs with higher uncertainty from the original test input set, so as to reduce the search space of subsequent selection, and compared with the prior art, the innovation point of the reduction stage is to introduce a dynamic reduction coefficient and a quick screening mechanism based on uncertainty, so that the computational complexity of subsequent selection can be obviously reduced while the screening effect is ensured;

Exemplary, specific operational steps of the curtailment stage are as follows:

running all test inputs on a model to be tested to obtain corresponding output probabilities;

exemplary, given a set of raw test input sets And testing budgetPerforming all test inputs on the DNN model to be tested once, and obtaining the model as each test inputPredicted output probabilityShaped likeWhereinAs a total number of tags,Considered as the model to be testedBelonging to the firstProbability of individual tags, andThe method is applicable to a black box test scene only depending on the output probability of the model without accessing the internal structure or training set data of the DNN model.

Selecting uncertainty index to construct uncertainty calculation function;

The present invention can illustratively employ any existing uncertainty index to construct a functionThe user can select proper index to construct uncertainty calculation function according to the actual requirementThe default uncertainty index of the present invention is Maxp, the Maxp index will output the maximum value of probability (i.e) As the confidence of the model to the test input, the higher the value thereof represents the more definite the output of the model to the test input, thereby the uncertainty calculation function can be constructed。

Calculating uncertainty values of all test inputs;

illustratively according to the step of Output probability obtained in (a)And steps ofThe uncertainty calculation function constructed in the process calculates each test outputThe higher the uncertainty value, the greater the likelihood that the test input triggers a misprediction, and vice versa.

Sequencing test inputs according to uncertainty values;

illustratively, all test inputs are ordered in descending order according to the calculated uncertainty values to obtain an ordered set WhereinRepresenting uncertainty value NoHigh test inputs. The step is used for rapidly positioning high-uncertainty test input through sequencing, and provides a basis for subsequent screening.

Setting a reduction coefficient;

Illustratively, the present invention introduces a reduction factorTo dynamically adjust the size of the candidate set in the selection stage and to set the candidate setIs of the size ofThus, the size of the candidate set can be dynamically adjusted, and the search space can be ensured to be along with the testing budgetThe dynamic change not only avoids the calculation cost caused by overlarge search space, but also ensures the diversity of the candidate set. It should be noted that the number of the components,Although the device can be set by the user according to the needs of the user, the device cannot be too small or too large, if too small, such asThe size of the candidate set is the size of the test budget, and the next selection cannot be performed, if the size is too large, the efficiency improvement caused by reducing the test set is weakened, and the invention defaultsThe value is 3.

Determining a candidate set;

Illustratively, according to the steps ofSet reduction coefficientCalculating to obtain a candidate setIs of the size of (a)Ordered test setFront of (a)Selecting from the test inputs to form a candidate set。

Through the steps, the reduction stage significantly reduces the search space of the subsequent selection stage while preserving key test inputs that may trigger mispredictions

In the present embodiment, the selection phase is shown in FIGS. 1, 9-15, and the goal of the selection phase is to optimize uncertainty and diversity from the candidate set by both increasing the ability to trigger mispredictions and ensuring that the mispredictions are triggered by different root faultsSelecting a subset of. The innovation point of the stage is that the equidistant partition strategy and the efficient greedy selection mechanism can ensure the effect of multi-objective optimization while obviously reducing the calculation times of the fitness;

Exemplary, specific operational steps of the selection phase are as follows:

equidistant dividing of candidate sets ;

The invention uses equidistant partitioning to divide the candidate setEvenly divided intoSubgroup ofWherein each subgroup isAnd is also provided withComprisesThe invention considers candidate sets by testing inputHas been ordered by uncertainty values, so that subgroups are partitioned with equidistant partitioning such that the uncertainty distribution of each subgroup is close toIs avoided, excessive concentration or dispersion of test inputs at the uncertainty level.

Selecting a diversity index to construct a diversity value calculation function;

The present invention can use any existing diversity index to construct a functionThe user can select a proper index structure diversity value calculation function according to the actual requirement. The default diversity index of the invention is Geometric Diversity (GD), the GD index evaluates the diversity of the collection through determinant of the characteristic matrix of the test input in the collection, and can construct a diversity calculation functionWhereinRepresents a line-type of the line-type,Representing a given collectionEach row of the matrix representing a respective test inputThe dimension of the feature vector is determined,Representative ofIs a transpose of (a).

Extracting characteristics of test input;

For example, this step is an optional step, which is determined according to the calculation requirement of the selected diversity index, and if the default option of the present invention is used, this step may not be omitted, that is, the default diversity index GD of the present invention requires obtaining the feature representation of the test input, and the user may select an appropriate feature extraction model to obtain the feature representation of the test input, and the present invention defaults to obtain the feature representation of the test input using the VGG16 model.

Calculating candidate test inputs for a selected set of test inputsAs its diversity value;

Illustratively, due to the diversity value function Only the diversity of the set can be calculated, so the invention innovatively proposes to compare the setAdding a test inputThe difference of front-back diversity is used as test inputThe diversity value of (2) is calculated as follows:。

Calculating the fitness value of the candidate test input;

Illustratively, the uncertainty value of the test input has been calculated during the reduction phase, at step Also defines how to test the input diversity value, and further can calculate the test inputIs adapted to the degree of adaptation value of (a)Evaluation for subsequent selection, which is calculated as follows:

Wherein, The method is used for limiting the diversity value to be in the range of 0,1 as a minimum-maximum normalization function, so that the diversity value is in the same order of magnitude as the uncertainty value, the adaptability evaluation deviation caused by different orders of magnitude is avoided, the uncertainty and the diversity are comprehensively considered by the adaptability value, the larger the value is, the better the test input is,

Another innovation of this step is to combine uncertainty and diversity by multiplication, avoiding choosing test inputs that perform poorly on either index.

Iteratively selecting an optimal test input in each subgroup;

Exemplary, the partitioned subgroups are traversed in order (I.e. total ofIteration), each iteration only processes one subgroup, traverses all test inputs within the current subgroup, according to the steps ofThe defined fitness value function calculates the corresponding fitness value, selects the test input with the largest fitness value and puts the test input into the final subsetIs a kind of medium. The step realizes high-efficiency selection through greedy strategy, and the steps are as followsThe number of the adaptive degree calculation times in the selection process is obviously reduced, and the efficiency is greatly improved.

Iteration end returns to the final selected subset of test inputsManual labeling was performed for DNN testing.

Exemplary, upon completion of the selection, the selected subset of test inputs is ultimately obtainedThe subset not only contains test inputs with higher uncertainty values, but also has good diversity, and can trigger more faults of different types, so that the performance of the deep neural network model can be comprehensively tested as much as possible in a test budget, and finally the test inputs are manually marked to form test cases for testing the DNN model.

In this embodiment, the overall workflow of the present invention is illustrated by an example in which the present invention seeks to extract from the original test set, as shown in connection with FIG. 2() Selecting a subset ofThe test budget is;

Specifically, in the reduction phase, the present invention first performsTo obtain its output probability, then according toThe test inputs are ordered in descending order by uncertainty values of the function calculation to obtain an ordered setWhereinRepresenting uncertainty value NoHigh test inputs, corresponding to FIG. 2 (1), where the present invention uses default reduction coefficientsTherefore, the invention selects the first 6%) As shown in fig. 2 (2), the test inputs form a candidate set;

Specifically, in the selection phase, as shown in FIG. 2 (3), the present invention will order candidate setsThe method is divided into two subgroups by an equidistant dividing method: And By this division, each subgroup contains test inputs of different uncertainty levels, and its uncertainty distribution andFinally, the invention uses greedy strategy from each subgroupAndThe test input with the highest fitness value is iteratively selected and added to the subset shown in fig. 2 (4)In (a) and (b);

further, the final selected subset Not only is there a high diversity, but it also contains test inputs with high uncertainty values that trigger more mispredictions and reveal a wider range of unique faults in the model.

The present invention is not limited in any way by the above-described preferred embodiments, but is not limited to the above-described preferred embodiments, and any person skilled in the art will appreciate that the present invention can be embodied in the form of a program for carrying out the method of the present invention, while the above disclosure is directed to equivalent embodiments capable of being modified or altered in some ways, it is apparent that any modifications, equivalent variations and alterations made to the above embodiments according to the technical principles of the present invention fall within the scope of the present invention.

Claims (10)

1. A multi-target black box test case selection method for a deep neural network is characterized by comprising a reduction stage and a selection stage, wherein the reduction stage is used for screening candidate test inputs with higher uncertainty from an original test input set, introducing a dynamic reduction coefficient and a quick screening mechanism based on the uncertainty, and the selection stage is used for selecting a subset from the candidate set, equally dividing a strategy and a greedy selection mechanism by simultaneously optimizing the uncertainty and diversity.

2. The method for selecting the multi-target black box test case for the deep neural network according to claim 1, wherein the specific operation steps of the reduction stage are as follows:

Running all test inputs on a model to be tested to obtain corresponding output probabilities, wherein the output probabilities are output probabilities which are only dependent on the model and do not need to access the internal structure or training set data of the DNN model;

selecting uncertainty index to construct uncertainty calculation function ;

Calculating uncertainty values of all test inputs;

sequencing test inputs according to uncertainty values;

Setting a reduction coefficient ;

Determining a candidate set。

3. The method for selecting a deep neural network-oriented multi-target black box test case according to claim 2, wherein said obtaining the corresponding output probabilities comprises providing a set of original test input setsAnd testing budgetPerforming all test inputs on the DNN model to be tested once, and obtaining the model as each test inputPredicted output probability,WhereinAs a total number of tags,Considered as the model to be testedBelonging to the firstProbability of individual tags, and。

4. The method for selecting a deep neural network-oriented multi-target black box test case according to claim 2, wherein the constructing an uncertainty calculation function comprises constructing a function using an uncertainty indexThe uncertainty index is any uncertainty index including Maxp, maxp, which is the maximum value of the probability that the index will output, i.eAs the confidence of the model to the test input, the higher the value thereof represents the more definite the output of the model to the test input, the uncertainty calculation function is constructed,。

5. The method for selecting a deep neural network-oriented multi-target black box test case according to claim 2, wherein said calculating uncertainty values of all test inputs comprises determining a probability of output based on said outputAnd the uncertainty calculation functionCalculating to obtain each test outputThe higher the uncertainty value, the greater the likelihood that the test input triggers a misprediction;

The sorting test inputs according to the uncertainty values comprises sorting all test inputs in descending order according to the uncertainty values obtained by calculation to obtain an ordered set WhereinRepresenting uncertainty value NoA high test input;

The setting of the reduction coefficient Includes introducing a reduction coefficientDynamically adjusting the size of the candidate set in the selection stage, and setting the candidate setIs of the size of;

The determination of the candidate setComprises according to the reduction coefficientCalculating to obtain a candidate setIs of the size of (a)Ordered test setFront of (a)Selecting from the test inputs to form a candidate set。

6. The method for selecting the multi-target black box test cases for the deep neural network according to claim 1, wherein the specific operation steps of the selection stage are as follows:

equidistant dividing of candidate sets ;

Selecting a diversity index to construct a diversity value calculation function;

Extracting characteristics of test input;

Calculating candidate test inputs for a selected set of test inputs As its diversity value;

Calculating the fitness value of the candidate test input;

Iteratively selecting an optimal test input in each subgroup;

Iteration end returns to the final selected subset of test inputs Manual labeling was performed for DNN testing.

7. The method for selecting multi-target black box test cases for deep neural network according to claim 6, wherein the equally divided candidate sets areIncludes equally dividing candidate setEvenly divided intoSubgroup ofWherein each subgroup isAnd is also provided withComprisesA plurality of test inputs;

The selective diversity index constructs a diversity value calculation function Comprises constructing a function by using various indexesThe diversity index is any diversity index, the random diversity index comprises GD indexes, the GD indexes evaluate the diversity of the set through determinant of the characteristic matrix of the test input in the set, and a diversity calculation function is constructedWhereinRepresents a line-type of the line-type,Representing a given collectionEach row of the matrix representing a respective test inputThe dimension of the feature vector is determined,Representative ofIs a transpose of (a).

8. The method for selecting the multi-target black box test case for the deep neural network of claim 6, wherein the feature of the extracted test input is an optional step, and the feature is determined according to the calculation requirement of the selected diversity index.

9. The method for selecting a multi-target black box test case for a deep neural network of claim 6, wherein the fitness value calculation comprises calculating a test inputIs adapted to the degree of adaptation value of (a)Evaluation for subsequent selection, which is calculated as follows: , wherein, The min-max normalization function is used to limit the diversity value to the [0,1] range to the same order of magnitude as the uncertainty value, while combining uncertainty and diversity by multiplication.

10. The method for selecting a deep neural network oriented multi-target black box test case according to claim 6, wherein said iteratively selecting optimal test inputs in each subgroup comprises sequentially traversing the divided subgroupsEach iteration only processes one subgroup, traverses all test inputs in the current subgroup, calculates corresponding fitness value according to the fitness value function, selects the test input with the largest fitness value and puts the test input into the final subsetIs a kind of medium.