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

Class ImprovedDeltaDebugging

  • All Implemented Interfaces:
    FaultCharacterizationAlgorithm
    Direct Known Subclasses:
    GeneratingImprovedDD
    public class ImprovedDeltaDebugging
extends Object
implements FaultCharacterizationAlgorithm
    An implementation of the Improved Delta Debugging algorithm as described in "Improved Delta Debugging Based on Combinatorial Testing". Basically, the algorithm performs a binary search on failed test inputs to discover failure-inducing combinations. This is done in two steps. The Isolation Algorithm computes one value in the test input which is responsible for failure, while the RI algorithm uses this isolation algorithm to find complete failure-inducing combinations. This implementation goes a bit further by allowing the discovery of failure-inducing combinations for multiple test inputs. All failed test inputs are therefore searched test input by test input, except if failure-inducing combinations found for previous test inputs already explanation a failure. Then it is assumed that no other combination is present in the test input.

    Important Information:

    • Generates a very predictable amount of test inputs due to binary search
    • Does not generate many test inputs per failure inducing combination
    • Does not work well if two failure-inducing combinations are present in one failed test input or if failure-inducing combinations overlap each other.
    • Does not consider constraints

    • Constructor Detail

      • ImprovedDeltaDebugging

        public ImprovedDeltaDebugging​(FaultCharacterizationConfiguration configuration)
        Creates a new Improved Delta Debugging algorithm for the given configuration. The ConstraintsChecker is ignored.
        Parameters:
        configuration - the configuration for the algorithm

    • Method Detail

      • improvedDeltaDebugging

        public static FaultCharacterizationAlgorithmFactory improvedDeltaDebugging()
        Returns:
        a factory always returning new instances of the Improved Delta Debugging algorithm

      • computeNextTestInputs

        public List<int[]> computeNextTestInputs​(Map<int[],​TestResult> testResults)
        Description copied from interface: FaultCharacterizationAlgorithm
        Refines the internal list of suspicious of faulty combinations. If this method is called for the first time, an initial list of suspicious combinations is created. This process may take a while. After the refinement of the list, test inputs are generated. These test inputs should be executed and this method should then be called with the results of these test inputs until no test inputs are returned. Through this process the underlying algorithm can refine and shorten it's list of suspicious combinations over time.

        When no combinations are returned any more, FaultCharacterizationAlgorithm.computeFailureInducingCombinations() can be used to compute a final list of most likely faulty combinations.

        Specified by:
        computeNextTestInputs in interface FaultCharacterizationAlgorithm
        Parameters:
        testResults - the results of the initial test suite or previous test inputs generated by this method. Must not be null or empty.
        Returns:
        a list of further test inputs which need to be executed to refine the list of suspicious combinations

      • 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.
        Specified by:
        computeFailureInducingCombinations in interface FaultCharacterizationAlgorithm
        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