Package randoop.generation

Class OrienteeringSelection

  • public class OrienteeringSelection
extends InputSequenceSelector
    Implements the Orienteering 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 .

    Biases input selection towards sequences that have lower execution cost. Execution cost is measured by the number of method calls in a sequence and the time it takes to execute.

    Our implementation of Orienteering differs from that described in the GRT paper in that we do not measure the time of every execution of a sequence. Instead, we assume that a sequence's execution time is equal to the execution time of its first run. We believe this assumption is reasonable since a sequence does not take any inputs (it is self-contained), so its execution time probably does not differ greatly between separate runs.

    The GRT paper also does not describe how to handle input sequences that have an execution time of zero, such as one that only includes the assignment of a primitive type byte byte0 = (byte)1;. We assign these input sequences an execution time of 1 nanosecond to prevent division by zero when computing weights.

    The GRT paper also does not describe how to handle input sequences that have not yet been selected. We start ecah input sequences with a selection count of 1 to prevent division by zero when computing weights.

    • Field Detail

      • weightMap

        private final Map<Sequence,​Double> weightMap
        Map from a sequence to its weight. For every sequence s, weightMap.get(s) == sequenceDetailsMap.get(s).getWeight(). This is needed because Randomneess#randomMemberWeighted takes a Map<T, Double> as an argument.

    • Constructor Detail

      • OrienteeringSelection

        public OrienteeringSelection​(Set<Sequence> seedSequences)
        Initialize OrienteeringSelection and assign a weight to each Sequence within the given set of seed sequences. This ensures that later, Orienteering will always have a corresponding OrienteeringSelection.SequenceDetails and therefore a corresponding weight for every Sequence within a list of candidates for selection.
        Parameters:
        seedSequences - set of seed sequences

    • Method Detail

      • computeTotalWeightForCandidates

        private double computeTotalWeightForCandidates​(SimpleList<Sequence> candidates)
        Compute the total weight of the list of candidate Sequences.
        Parameters:
        candidates - list of candidate sequences
        Returns:
        the total weight of the input candidate list

      • createSequenceDetailsWithExecutionTime

        private void createSequenceDetailsWithExecutionTime​(Sequence sequence,
                                                    long executionTimeNanos)
        Creates and stores a OrienteeringSelection.SequenceDetails for the given Sequence with the corresponding execution time.
        Parameters:
        sequence - the sequence to add
        executionTimeNanos - the execution time of the sequence, in nanoseconds

      • methodSizeSquareRoot

        private static double methodSizeSquareRoot​(Sequence sequence)
        Returns the the square root of the number of method call statements within the given sequence.

        To prevent division by zero, we use 1 for a sequence with no method calls.

        Parameters:
        sequence - a sequence
        Returns:
        square root of the number of method calls in the given sequence