US 8,479,171 B2Granted

Generating test sets using intelligent variable selection and test set compaction

AssigneeFujitsu Limited

InventorIndradeep Ghosh

Life of this patent

Estimating the term…

Loading patent…

Abstract

In one embodiment, constructing one or more sets of variables corresponding to one or more input variables of a software module respectively; for each one of the sets of variables, computing an average branching depth that is affected by the set of variables; selecting a first one of the sets of variables that has the smallest average branching depth; assigning a first symbolic value to the input variable of the first set of variables; symbolically executing the software module to generate a first set of test cases for the first set of variables; optionally compacting the first set of test cases by removing the redundant tests that do not increase test coverage and selecting a minimal subset of the first set of test cases that cover all the covered conditional branch points; and validating the software module using the first set of test cases.

Claims29

Dependent claims

A method comprising, executed by one or more computing devices:

accessing a software module, wherein:
the software module comprises:
one or more input variables;
one or more intermediate variables, wherein a value of each one of the intermediate variables directly or indirectly depends on at least one value of at least one of the input variables;
and
one or more conditional branching points, wherein each one of the conditional branching points has a branching condition specified by at least one of the input or intermediate variables, and whether the branching condition is satisfied depend on at least one value of the at least one of the input or intermediate variables;
and
during execution of the software module, at each one of the conditional branching points, the software module proceeds down different paths depending on whether the branching condition of the conditional branching point is satisfied;
constructing one or more sets of variables corresponding to the input variables, wherein each one of the sets of variables comprises one of the input variables and the intermediate variables whose values directly or indirectly depend on the value of the one of the input variables;
for each one of the sets of variables, computing an average branching depth that is affected by the input and intermediate variables of the set of variables;
selecting a first one of the sets of variables that has the smallest average branching depth;
assigning a first symbolic value to the input variable of the first one of the sets of variables;
symbolically executing the software module, with the input variable of the first one of the sets of variables having the first symbolic value, to generate a first set of test cases for the input and intermediate variables of the first set of variables;
and
validating the software module using the first set of test cases.

12 more elements

A method comprising, executed by one or more computing devices:

accessing a software module and a plurality of test cases for the software module, wherein:
the software module comprises:
one or more variables;
and
one or more conditional branching points, wherein each one of the conditional branching points has a branching condition specified by at least one of the variables, and whether the branching condition is satisfied depend on at least one value of the at least one of the variables;
and
during execution of the software module, at each one of the conditional branching points, the software module proceeds down different paths depending on whether the branching condition of the conditional branching point is satisfied;
each one of the test cases covers at least one of the conditional branching points and comprises at least one test value for the at least one of the variables that specify the branching conditions of the at least one of the conditional branching points;
for each one of the conditional branching points, if there are multiple ones of the test cases covering the conditional branching points that cause the software module to proceed down the same path during execution, then removing from the test cases all except one of the multiple ones of the test cases covering the conditional branching points that cause the software module to proceeding down the same path;
selecting from the remaining test cases one or more first test cases, wherein for each one of the first test cases, at least one of the conditional branching points is covered only by the first test case;
iteratively selecting from the remaining test cases one or more second test cases, wherein the second test case selected during each iteration covers the most number of the conditional branching points during that iteration, until all of the conditional branching points are covered by at least one of the first or second test cases;
and
testing the software module using only the selected first and second test cases.

10 more elements

A system comprising:

a memory comprising instructions executable by one or more processors;
and
one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to:
access a software module, wherein:
the software module comprises:
one or more input variables;
one or more intermediate variables, wherein a value of each one of the intermediate variables directly or indirectly depends on at least one value of at least one of the input variables;
and
one or more conditional branching points, wherein each one of the conditional branching points has a branching condition specified by at least one of the input or intermediate variables, and whether the branching condition is satisfied depend on at least one value of the at least one of the input or intermediate variables;
and
during execution of the software module, at each one of the conditional branching points, the software module proceeds down different paths depending on whether the branching condition of the conditional branching point is satisfied;
construct one or more sets of variables corresponding to the input variables, wherein each one of the sets of variables comprises one of the input variables and the intermediate variables whose values directly or indirectly depend on the value of the one of the input variables;
for each one of the sets of variables, compute an average branching depth that is affected by the input and intermediate variables of the set of variables;
select a first one of the sets of variables that has the smallest average branching depth;
assign a first symbolic value to the input variable of the first one of the sets of variables;
symbolically execute the software module, with the input variable of the first one of the sets of variables having the first symbolic value, to generate a first set of test cases for the input and intermediate variables of the first set of variables;
and
validate the software module using the first set of test cases.

15 more elements

A system comprising:

a memory comprising instructions executable by one or more processors;
and
one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to:
access a software module and a plurality of test cases for the software module, wherein:
the software module comprises:
one or more variables;
and
one or more conditional branching points, wherein each one of the conditional branching points has a branching condition specified by at least one of the variables, and whether the branching condition is satisfied depend on at least one value of the at least one of the variables;
and
during execution of the software module, at each one of the conditional branching points, the software module proceeds down different paths depending on whether the branching condition of the conditional branching point is satisfied;
each one of the test cases covers at least one of the conditional branching points and comprises at least one test value for the at least one of the variables that specify the branching conditions of the at least one of the conditional branching points;
for each one of the conditional branching points, if there are multiple ones of the test cases covering the conditional branching points that cause the software module to proceed down the same path during execution, then remove from the test cases all except one of the multiple ones of the test cases covering the conditional branching points that cause the software module to proceeding down the same path;
select from the remaining test cases one or more first test cases, wherein for each one of the first test cases, at least one of the conditional branching points is covered only by the first test case;
iteratively select from the remaining test cases one or more second test cases, wherein the second test case selected during each iteration covers the most number of the conditional branching points during that iteration, until all of the conditional branching points are covered by at least one of the first or second test cases;
and
test the software module using only the selected first and second test cases.

13 more elements

One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computing devices to:

access a software module, wherein:
the software module comprises:
one or more input variables;
one or more intermediate variables, wherein a value of each one of the intermediate variables directly or indirectly depends on at least one value of at least one of the input variables;
and
one or more conditional branching points, wherein each one of the conditional branching points has a branching condition specified by at least one of the input or intermediate variables, and whether the branching condition is satisfied depend on at least one value of the at least one of the input or intermediate variables;
and
during execution of the software module, at each one of the conditional branching points, the software module proceeds down different paths depending on whether the branching condition of the conditional branching point is satisfied;
construct one or more sets of variables corresponding to the input variables, wherein each one of the sets of variables comprises one of the input variables and the intermediate variables whose values directly or indirectly depend on the value of the one of the input variables;
for each one of the sets of variables, compute an average branching depth that is affected by the input and intermediate variables of the set of variables;
select a first one of the sets of variables that has the smallest average branching depth;
assign a first symbolic value to the input variable of the first one of the sets of variables;
symbolically execute the software module, with the input variable of the first one of the sets of variables having the first symbolic value, to generate a first set of test cases for the input and intermediate variables of the first set of variables;
and
validate the software module using the first set of test cases.

12 more elements

One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computing devices to:

access a software module and a plurality of test cases for the software module, wherein:
the software module comprises:
one or more variables;
and
one or more conditional branching points, wherein each one of the conditional branching points has a branching condition specified by at least one of the variables, and whether the branching condition is satisfied depend on at least one value of the at least one of the variables;
and
during execution of the software module, at each one of the conditional branching points, the software module proceeds down different paths depending on whether the branching condition of the conditional branching point is satisfied;
each one of the test cases covers at least one of the conditional branching points and comprises at least one test value for the at least one of the variables that specify the branching conditions of the at least one of the conditional branching points;
for each one of the conditional branching points, if there are multiple ones of the test cases covering the conditional branching points that cause the software module to proceed down the same path during execution, then remove from the test cases all except one of the multiple ones of the test cases covering the conditional branching points that cause the software module to proceeding down the same path;
select from the remaining test cases one or more first test cases, wherein for each one of the first test cases, at least one of the conditional branching points is covered only by the first test case;
iteratively select from the remaining test cases one or more second test cases, wherein the second test case selected during each iteration covers the most number of the conditional branching points during that iteration, until all of the conditional branching points are covered by at least one of the first or second test cases;
and
test the software module using only the selected first and second test cases.

10 more elements

A system stored in a memory comprising:

accessing a software module and a plurality of test cases for the software module, wherein:
the software module comprises:
one or more variables;
and
one or more conditional branching points, wherein each one of the conditional branching points has a branching condition specified by at least one of the variables, and whether the branching condition is satisfied depend on at least one value of the at least one of the variables;
and
during execution of the software module, at each one of the conditional branching points, the software module proceeds down different paths depending on whether the branching condition of the conditional branching point is satisfied;
each one of the test cases covers at least one of the conditional branching points and comprises at least one test value for the at least one of the variables that specify the branching conditions of the at least one of the conditional branching points;
for each one of the conditional branching points, if there are multiple ones of the test cases covering the conditional branching points that cause the software module to proceed down the same path during execution, then means for removing from the test cases all except one of the multiple ones of the test cases covering the conditional branching points that cause the software module to proceeding down the same path;
means for selecting from the remaining test cases one or more first test cases, wherein for each one of the first test cases, at least one of the conditional branching points is covered only by the first test case;
means for iteratively selecting from the remaining test cases one or more second test cases, wherein the second test case selected during each iteration covers the most number of the conditional branching points during that iteration, until all of the conditional branching points are covered by at least one of the first or second test cases;
and
means for testing the software module using only the selected first and second test cases.

10 more elements

Dependencies are inferred from the claim text.