Package randoop.generation

Class Bloodhound

  • All Implemented Interfaces:
    TypedOperationSelector
    public class Bloodhound
extends Object
implements TypedOperationSelector
    Implements the Bloodhound component, as described by the paper "GRT: Program-Analysis-Guided Random Testing" by Ma et. al (appears in ASE 2015): https://people.kth.se/~artho/papers/lei-ase2015.pdf .

    Bloodhound computes a weight for each method under test by taking a weighted combination of

    • the uncovered branch ratio and
    • the ratio between the number of times the method has been successfully invoked (to be the last statement of a new regression test) and the maximum number of times any method under test has been successfully invoked.
    A method is "successfully invoked" when a method under test is used to create a new sequence and the sequence is kept as a regression test. An alternative definition of "successful invocations" is the total number of times the method appears in any regression test. Both definitions are consistent with the description in the GRT paper. We believe our implementation, which uses the first definition, is likely what was intended by the authors of the GRT paper.

    • Field Detail

      • coverageTracker

        private final CoverageTracker coverageTracker
        Coverage tracker used to get branch coverage information of methods under test.

      • methodWeights

        private final Map<TypedOperation,​Double> methodWeights
        Map from methods under test to their weights. These weights are dynamic and depend on branch coverage.

      • methodSelectionCounts

        private final Map<TypedOperation,​Integer> methodSelectionCounts
        Map from methods under test to the number of times they have been recently selected by the ForwardGenerator to construct a new sequence. This map is cleared every time branch coverage is recomputed.

      • methodInvocationCounts

        private final Map<TypedOperation,​Integer> methodInvocationCounts
        Map from methods under test to the total number of times they have ever been successfully invoked by the AbstractGenerator. The integer value for a given method is non-decreasing during a run of Randoop.

      • operationSimpleList

        private final SimpleArrayList<TypedOperation> operationSimpleList
        List of operations, identical to ForwardGenerator's operation list. Used for making random, weighted selections for a method under test.

      • alpha

        private static final double alpha
        Parameter for balancing branch coverage and number of times a method was chosen. The name "alpha" and the specified value are both from the GRT paper.
        See Also:
        Constant Field Values

      • p

        private static final double p
        Parameter for decreasing weights of methods between updates to coverage information. The name "p" and the specified value are both from the GRT paper.
        See Also:
        Constant Field Values

      • t

        private static final long t
        Time interval, in milliseconds, at which to recompute weights. The name "t" and the specified value are both from the GRT paper.
        See Also:
        Constant Field Values

      • lastUpdateTime

        private long lastUpdateTime
        System.currentTimeMillis() when branch coverage was last updated.

      • branchCoverageInterval

        private static final int branchCoverageInterval
        Branch coverage is recomputed after this many successful invocations (= this many new tests were generated).
        See Also:
        Constant Field Values

      • totalSuccessfulInvocations

        private int totalSuccessfulInvocations
        The total number of successful invocations of all the methods under test.

      • maxSuccM

        private int maxSuccM
        Maximum number of times any method under test has been successfully invoked. This value is initialized to 1 because it is used as the denominator of a division in computing a method's weight. The name is from the GRT paper, which calls this quantity "maxSucc(M)".

      • totalWeightOfMethodsUnderTest

        private double totalWeightOfMethodsUnderTest
        The total weight of all the methods that are under test. This is used by Randomness to randomly select an element from a list of weighted elements.

    • Constructor Detail

      • Bloodhound

        public Bloodhound​(List<TypedOperation> operations,
                  Set<ClassOrInterfaceType> classesUnderTest)
        Initialize Bloodhound. Branch coverage information is initialized and all methods under test are assigned a weight based on the weighting scheme defined by GRT's description of Bloodhound.
        Parameters:
        operations - list of operations under test
        classesUnderTest - set of classes under test

    • Method Detail

      • selectOperation

        public TypedOperation selectOperation()
        Selects a method under test for the ForwardGenerator to use to construct a new sequence. A method under test is randomly selected with a weighted probability.
        Specified by:
        selectOperation in interface TypedOperationSelector
        Returns:
        the chosen TypedOperation for the new sequence

      • updateBranchCoverageMaybe

        private void updateBranchCoverageMaybe()
        When an interval is reached, the branch coverage information for all methods under test is updated and the weight for every method under test is recomputed.

        There are two choices for when to update branch coverage information:

        • Time: branch coverage is updated when more than t milliseconds have elapsed since branch coverage was last updated. This is GRT's approach and is the default. It makes Randoop non-deterministic.
        • Count of successful invocations: branch coverage is updated after every branchCoverageInteral successful invocations (of any method under test).

      • logMethodWeights

        private void logMethodWeights()
        For debugging, print all method weights to standard output.

      • updateWeightsForAllOperations

        private void updateWeightsForAllOperations()
        Computes and updates weights in methodWeights map for all methods under test. Recomputes the totalWeightOfMethodsUnderTest to avoid problems with round-off error.

      • updateWeight

        private double updateWeight​(TypedOperation operation)
        Recompute weight for a method under test. A method under test is assigned a weight based on a weighted combination of
        • the number of branches uncovered and
        • the ratio between the number of times this method has been recently selected and the maximum number of times any method under test has been successfully invoked.
        The weighting scheme is based on Bloodhound in the Guided Random Testing (GRT) paper.
        Parameters:
        operation - method to compute weight for
        Returns:
        the updated weight for the given operation

      • incrementSuccessfulInvocationCount

        public void incrementSuccessfulInvocationCount​(TypedOperation operation)
        Increments the number of times a method under test was successfully invoked.
        Parameters:
        operation - the method under test that was successfully invoked

      • newRegressionTestHook

        public void newRegressionTestHook​(Sequence sequence)
        Increment the number of successful invocations of the last method in the newly-created sequence that was classified as a regression test.
        Specified by:
        newRegressionTestHook in interface TypedOperationSelector
        Parameters:
        sequence - newly-created sequence that was classified as a regression test