Black-box software testing with statistical learning

Patent metadata

Field	Value
Publication number	US-2016239401-A1
Application number	US-201514623399-A
Country	US
Kind code	A1
Filing date	Feb 16, 2015
Priority date	Feb 16, 2015
Publication date	Aug 18, 2016
Grant date	—

Abstract

A method to determine a relationship between inputs and outputs based on a parametric model may include receiving a data set that includes known inputs and corresponding known outputs associated with a component. The method also includes generating a parametric model to automatically determine a functionality of the component based on the data set by selecting the parametric model from multiple types of parametric models based on a data type associated with the data set. The method also includes determining whether the parametric model applies to the data set. The method also includes, responsive to determining that the parametric model applies to the data set, receiving a new output associated with the component. The method also includes determining a new input from the new output based on the parametric model.

First claim

1 . A method to determine a relationship between inputs and outputs based on a parametric model, the method comprising:
receiving a data set that includes known inputs and corresponding known outputs associated with a software component under test and with unknown functionality; generating, using a processor device programmed to perform or control performance of the generating, a parametric model to automatically determine a functionality of the software component under test based on the data set by selecting the parametric model from multiple types of parametric models based on a data type associated with the data set; determining whether the parametric model applies to the data set; responsive to determining that the parametric model applies to the data set, receiving a new output associated with the software component under test; and determining a new input from the new output based on the parametric model.

2 . The method of claim 1 , wherein:
the data type includes a non-primitive data type; and a regression model is selected as the parametric model based on the data type including the non-primitive data type.

3 . The method of claim 2 , wherein the regression model includes a regular expression model that is configured to identify extraction regular expressions for each known output, unite the extraction regular expressions, and generate a generalized regular expression.

4 . The method of claim 2 , wherein the regression model includes an operation sequence based model that is configured to determine an operation that causes the known inputs to result in the corresponding known outputs.

5 . The method of claim 1 , further comprising:
determining whether a next data item from the data set is unanalyzed, the next data item including an unanalyzed known input and a corresponding unanalyzed known output; and responsive to the next data item from the data set being analyzed, determining a constraint for the parametric model.

6 . The method of claim 1 , wherein the multiple types of parametric models include one or more of a linear regression model, a polynomial regression model, a non-linear regression model, a regular expression model, or an operation sequence based model.

7 . The method of claim 1 , further comprising:
generating an initial model for the parametric model by analyzing a first data item in the data set; determining whether a next data item from the data set is unanalyzed, the next data item including an unanalyzed known input and a corresponding unanalyzed known output; responsive to the next data item from the data set being unanalyzed, analyzing the unanalyzed known input based on the initial model to determine a predicted output; determining whether the predicted output matches the corresponding unanalyzed known output; and responsive to the predicted output matching the corresponding unanalyzed known output, determining whether another data item from the data set is unanalyzed.

8 . The method of claim 7 , further comprising:
responsive to the predicted output failing to match the corresponding unanalyzed known output, determining an error rate between the predicted output and the corresponding unanalyzed known output; determining whether the error rate exceeds a threshold value; responsive to the error rate failing to exceed the threshold value, determining whether the initial model can be generalized to apply to the next data item; responsive to the initial model being capable of being generalized to apply to the next data item, updating model parameters associated with the initial model to incorporate the unanalyzed known input and the corresponding unanalyzed known output; and determining whether another data item from the data set is unanalyzed.

9 . The method of claim 8 , further comprising:
responsive to the error rate exceeding the threshold value, selecting a new model based on the next data item; generating new parameters for the new model based on the next data item; and determining whether another data item from the data set is unanalyzed.

10 . The method of claim 9 , further comprising:
responsive to the predicted output failing to match the corresponding unanalyzed known output, generalizing the initial model; determining whether the generalized initial model applies to the next data item; responsive to the generalized initial model failing to apply to the next item, classifying the first data item as being associated with the initial model; and classifying the next data item as being associated with the new model.

11 . A method to relate inputs and outputs without assuming a specific model, the method comprising:
receiving a data set that includes known inputs and corresponding known outputs associated with a software component under test and with unknown functionality; identifying a constraint; identifying neighbor data items based on proximity to a target, wherein each neighbor data item includes a neighbor input and a corresponding neighbor output; determining a new input based on averaging neighbor inputs for the neighbor data items; determining a corresponding new output based on the new input; determining whether the corresponding new output satisfies the constraint; and generating, using a processor device programmed to perform or control performance of the generating, a non-parametric model to automatically determine a functionality of the software component under test.

12 . The method of claim 11 , further comprising:
setting a number of iterations to 1; responsive to the corresponding new output failing to satisfy the constraint, determining whether the number of iterations exceed a threshold value; and responsive to the number of iterations failing to exceed the threshold value, updating the data set by adding the new input and the corresponding new output to the data set and increasing the number of iterations by one.

13 . The method of claim 12 , further comprising responsive to the number of iterations exceeding the threshold value generating a parametric model.

14 . A method to analyze code whose functionality is unknown, the method comprising:
receiving a data set that includes known inputs and corresponding known outputs associated with a software component under test and with unknown functionality; generating, using a processor device programmed to perform or control performance of the generating, a parametric model based on the data set; determining whether the parametric model applies to the data set; responsive to the parametric model failing to apply to the data set, identifying a constraint; determining a new input and a corresponding new output that satisfy the constraint based on one or more data items of the data set; and generating a non-parametric model to automatically determine a functionality of the software component under test.

15 . The method of claim 14 , further comprising:
responsive to the parametric model applying to the data set, receiving a new output associated with the software component under test; and determining a new input from the new output based on the parametric model.

16 . The method of claim 15 , wherein generating the parametric model based on the data set comprises:
generating an initial model by applying a first item in the data set; determining whether a next data item from the data set is unanalyzed, the next data item including an unanalyzed known input and a corresponding unanalyzed known output; and responsive to the next data item from the data set being unanalyzed, analyzing the unanalyzed known input based on the

Assignees

• Fujitsu Ltd

Inventors

• Li Guodong

Classifications

• G06F11/3608 Primary

  using formal methods, e.g. model checking, abstract interpretation (theorem proving G06N5/013) · CPC title

• G06F11/3684

  for test design, e.g. generating new test cases · CPC title