Package de.rwth.swc.coffee4j.algorithmic.sequential.characterization.ben

Class Ben

java.lang.Object

de.rwth.swc.coffee4j.algorithmic.sequential.characterization.SuspiciousCombinationAlgorithm

de.rwth.swc.coffee4j.algorithmic.sequential.characterization.ben.Ben

All Implemented Interfaces:

FaultCharacterizationAlgorithm

public class Ben
extends SuspiciousCombinationAlgorithm

The implementation of the BEN fault characterization algorithm based on the paper "Identifying Failure-Inducing Combinations in a Combinatorial Test Set". Generates multiple sets of new test inputs if necessary. This means it is not known at which iteration an empty list is returned to signal the algorithm is stopping. Failure-Inducing combinations are ranked by an internal measure of probability. This means that combinations at the beginning of the returned list are more likely to be failure-inducing. The list of failure-inducing combinations is build out of lists for each combination size. That means first all 1-value-combinations are returned in probability order, then all two-value-combinations, ..., then all t-value combinations where t is the testing strength.

Internally, the algorithm works with two important structures: t-value-combinations and so called components (1-value-combinations). In each iteration all components are ranked according to appearance in failed or successful test inputs as well as suspicious combinations. Next, all suspicious t-value combinations (those combinations appearing in only failed test inputs) are ranked according to the suspiciousness of their contained components, and other components in their test inputs. Consider the following example: There is a failed test input (1, 2, 3) when testing with strength 2. (1, 2, -) appears in no successful test input so its a suspicious combinations. 1 appears in many failed test inputs and suspicious combinations in the whole test suite and it is therefore likely that some failure-inducing combinations contains 1. With 2, the same story is the input. 3 does not appear in any failed test input at all. This means (1, 2, -) is very likely the combination causing the failure of (1, 2, 3). Of course, a combination with fewer than t values can also be failure inducing. Therefore, BEN reduces all t-value- combinations at the end. This is done by looking if all possible containing combinations are suspicious. For example, if each parameter has 2 values and (0, 1) and (0, 2) are suspicious, (0, -) is therefore also suspicious since there is no non-suspicious combination containing (0, -).

Important Information:

• Will not find any failure-inducing combination involving more than t parameters. If you expect such failure-inducing combinations, your t is already chosen wrong
• Can generate many additional test inputs if needed. The number of generated test inputs per iteration is configurable
• Orders failure-inducing combinations by probability
• Considers constraints as an addition to the original algorithm
• Not very efficient if failure-inducing combination is smaller than t values

Field Summary

Fields inherited from class de.rwth.swc.coffee4j.algorithmic.sequential.characterization.SuspiciousCombinationAlgorithm

configuration, previousSuspiciousCombinations, suspiciousCombinations, testResults

Constructor Summary

Constructors

Constructor	Description
Ben(FaultCharacterizationConfiguration configuration)	Builds a new instance of the algorithm for a given configuration.
Ben(FaultCharacterizationConfiguration configuration, int numberOfCombinationsPerStep, int maxGenerationAttempts)	Builds a new instance of the algorithm for the given configuration.

Method Summary

Modifier and Type	Method	Description
static FaultCharacterizationAlgorithmFactory	ben()	Can be used as a convenience method to describe that BEN should be used as a FaultCharacterizationAlgorithmFactory.
static FaultCharacterizationAlgorithmFactory	ben(int numberOfCombinationsPerStep, int maxGenerationAttempts)	Can be used as a convenience method to describe that BEN should be used as a FaultCharacterizationAlgorithmFactory.
List<int[]>	computeFailureInducingCombinations()	Computes a list of most likely failure inducing combinations refined from previous calls to FaultCharacterizationAlgorithm.computeNextTestInputs(Map).
List<IntArrayWrapper>	generateNextTestInputs(Map<int[],TestResult> newTestResults)	The concrete algorithm generates test for which it needs the result for better fault characterization.
Set<IntArrayWrapper>	getRelevantSubCombinations(int[] combination)	Defined which sub-combinations of any given combination can be part of the suspicious set.
boolean	shouldGenerateFurtherTestInputs()

Methods inherited from class de.rwth.swc.coffee4j.algorithmic.sequential.characterization.SuspiciousCombinationAlgorithm

computeNextTestInputs, getChecker, getModel, getReporter

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Ben

public Ben(FaultCharacterizationConfiguration configuration)

Builds a new instance of the algorithm for a given configuration. 10 test inputs will be generated per step, and no further test inputs are generated in the next iteration if no test input can be found for a failure inducing combinations after 50 attempts.

Parameters:

configuration - for knowing which combinations can be failure-inducing/which test inputs can be generated. Must not be null

Throws:

NullPointerException - if configuration is null

Ben

public Ben(FaultCharacterizationConfiguration configuration,
           int numberOfCombinationsPerStep,
           int maxGenerationAttempts)

Builds a new instance of the algorithm for the given configuration.

Parameters:

configuration - for knowing which combinations can be failure-inducing/which test inputs can be generated. Must not be null

numberOfCombinationsPerStep - how many test inputs should be generated per step. Must be positive

maxGenerationAttempts - after how many attempts the algorithm should give up on generating a previously untested test inputs containing a given failure-inducing combination. Must be positive

Throws:

NullPointerException - if configuration is null

IllegalArgumentException - if one of the integers is not positive

Method Detail

ben

public static FaultCharacterizationAlgorithmFactory ben()

Can be used as a convenience method to describe that BEN should be used as a FaultCharacterizationAlgorithmFactory.

Returns:

a factory using ben as a fault characterization algorithm. Each instance of BEN is configured to create 10 new test inputs per iteration and uses 50 generation attempts before considering a combination to be failure-inducing

ben

public static FaultCharacterizationAlgorithmFactory ben(int numberOfCombinationsPerStep,
                                                        int maxGenerationAttempts)

Can be used as a convenience method to describe that BEN should be used as a FaultCharacterizationAlgorithmFactory.

Parameters:

numberOfCombinationsPerStep - see Ben(FaultCharacterizationConfiguration, int, int)

maxGenerationAttempts - see Ben(FaultCharacterizationConfiguration, int, int)

Returns:

a factory using the constructor (Ben(FaultCharacterizationConfiguration, int, int)) to create new FaultCharacterizationAlgorithm instances

Throws:

IllegalArgumentException - if one of the integers is not positive

getRelevantSubCombinations

public Set<IntArrayWrapper> getRelevantSubCombinations(int[] combination)

Description copied from class: SuspiciousCombinationAlgorithm

Defined which sub-combinations of any given combination can be part of the suspicious set. For example, BEN only works on all t-value-combinations while AIFL considers all possible sub-combinations.

Specified by:

getRelevantSubCombinations in class SuspiciousCombinationAlgorithm

Parameters:

combination - for which the relevant sub-combinations are needed

Returns:

all sub-combination the concrete algorithm considers

shouldGenerateFurtherTestInputs

public boolean shouldGenerateFurtherTestInputs()

Specified by:

shouldGenerateFurtherTestInputs in class SuspiciousCombinationAlgorithm

Returns:

Whether further test inputs should be generated. If not, FaultCharacterizationAlgorithm.computeFailureInducingCombinations() will be called next

generateNextTestInputs

public List<IntArrayWrapper> generateNextTestInputs(Map<int[],TestResult> newTestResults)

Description copied from class: SuspiciousCombinationAlgorithm

The concrete algorithm generates test for which it needs the result for better fault characterization. If no further characterization is needed, an empty list should be returned.

Specified by:

generateNextTestInputs in class SuspiciousCombinationAlgorithm

Parameters:

newTestResults - the results from the test inputs generated in the last iteration of the initially generated test inputs if in the first iteration

Returns:

test inputs for which the result is needed

computeFailureInducingCombinations

public List<int[]> computeFailureInducingCombinations()

Description copied from interface: FaultCharacterizationAlgorithm

Computes a list of most likely failure inducing combinations refined from previous calls to FaultCharacterizationAlgorithm.computeNextTestInputs(Map). The combinations returned by this method are not guaranteed to be faulty, but it is guaranteed that no test input executed which contained this combination was successful.

Returns:

a list of faulty combinations. The list may be ranked, depending on the underlying algorithm. If this list is ranked the combinations on positions with smaller indices are more likely to be failure inducing