EvoSuite Tutorial – Part 4: Extending EvoSuite

What you will learn in this tutorial

• Building EvoSuite
• Modifying the search algorithm
• Adding new fitness functions
• Adding new runtime variables

Prerequisites

In this tutorial, we will be extending EvoSuite with some new features. In order to do so, we will require a couple of things:

• A git client to check out the EvoSuite source code
• JDK (version 8)
• Apache Maven (version 3.1 or newer)
• An IDE (e.g., IntelliJ or Eclipse) in order to edit the source code

Obtaining the EvoSuite source code

The source code of EvoSuite is available on GitHub in a public Git repository. The first step of this tutorial consists of checking out the source code. How to do this will differ depending on which IDE you prefer to use. EvoSuite uses Maven as build infrastructure, so in IntelliJ you can simply check out the repository and mark it as a Maven project. In Eclipse you can do the same if you have the M2E plugin installed. If you prefer working on the command line, then check out the repository with git directly:

git clone https://github.com/EvoSuite/evosuite.git

The source code is organised into several Maven sub-modules. That is, there is one parent pom.xml in the main directory of the source code you just checked out, and then there are several separate sub-projects in subdirectories. Let’s have a closer look at the main sub-modules:

• master: EvoSuite uses a master-client architecture because things can go wrong when executing randomly generated tests (e.g., we could run out of memory). The client sends the current search result to the master process every now and then, so that even if things go wrong, we still get some tests in the end. The master module handles the user input on the command line (e.g., parsing of command line options), and then spawns client processes to do the actual test generation.
• client: The client contains all the heavy lifting. The genetic algorithm is in here, the internal representation of test cases and test suites used by the algorithm, the search operators, mechanisms to execute the test cases, all the bytecode instrumentation that is needed to produce trace information from which to calculate fitness values.
• runtime: This is the runtime library, i.e., all the instrumentation that is needed to make test execution deterministic, the mocked Java API, etc.
• plugins: There are several sub-projects in here that are plugins for various third-party tools, such as Maven, IntelliJ, Eclipse, or Jenkins.

Besides these Maven modules, there are several other modules or sub-directories. You will not usually need to access any of these, but in case you are curious what they are:

• standalone_runtime: There is no source code in this library, this is simply a Maven sub-module that produces a standalone jar file, i.e., one that includes all the dependencies of the runtime library.
• shaded: There is no source code in here either; this is a Maven module that produces a version of EvoSuite where the package name is renamed from org.evosuite to something else. This is to allow EvoSuite to be applied to itself (which otherwise wouldn’t work, as EvoSuite refuses to instrument its own code).
• generated: This is a sub-module in which we are putting tests generated by EvoSuite to test EvoSuite. This is still work in progress.
• release_results: This is not a Maven sub-module, it is just a collection of data that represents the results of the experiment on the SF110 dataset we conduct every time we perform a release.
• src: No Java source code in here, only some Maven-related meta-data.
• removed: Some source code files that are not used in the main source tree but have been useful to keep as a reference.

Building EvoSuite

It will probably not come as a surprise to you that, using Maven, Evosuite can be compiled using:

mvn compile

Most likely, your IDE will do this for you automatically. However, it is important that your IDE supports Maven, and that you have configured the project as a Maven project. If you haven’t done this, what you will get are error message complaining that the compiler cannot find classes in the package org.evosuite.xsd. These classes are generated automatically by jaxb based on an XML schema – and this is only done if you properly compile the project with Maven.

Recall from part 1 of the tutorial that the EvoSuite distribution consists of two jar files – one with the standalone runtime dependencies, and one for test generation. You can generate these by invoking:

mvn package

The main EvoSuite jar file is generated by the master sub-module: master/target/evosuite-master-1.0.4-SNAPSHOT.jar. You can validate that this is the case by invoking the executable with Java:

java -jar master/target/evosuite-master-1.0.4-SNAPSHOT.jar

You should now see the help text with the usage instructions. The standalone runtime library is, no surprises there, standalone_runtime/target/evosuite-standalone-runtime-1.0.4-SNAPSHOT.jar.

Building EvoSuite can take a while, but a lot of that time is spent executing unit tests. Although we don’t recommend doing that, if you do need to build a jar file quickly and can’t wait for the unit tests to complete, you can add -DskipTests=true to the Maven command line.

Testing EvoSuite

As with any Maven project, you will find the source code in src/main/java for every sub-module, and the tests in src/test/java.

EvoSuite has a fair number of unit tests, but it has a lot more system and integration tests (executing all system tests takes somewhere between 1-2 hours, depending on your machine). You can distinguish between the two types of tests based on the classname: all system tests have the suffix SystemTest in their name. Most of these system tests consist of a class under test that captures a specific testing challenge, and then invoke EvoSuite to check that it is able to cover the class fully, using a specific configuration.

In the test directories of the various sub-packages, you will find two main packages of classes: Everything with a package name starting with org.evosuite are the actual tests; the classes under test are in the com.examples.with.different.packagename package.

Let’s take a closer look at one of the system tests. For example, open the class org.evosuite.basic.NullStringSystemTest, which you can find in the file ./master/src/test/java/org/evosuite/basic/NullStringSystemTest.java:

public class NullStringSystemTest extends SystemTestBase {

    @Test
    public void testNullString() {
        EvoSuite evosuite = new EvoSuite();

        String targetClass = NullString.class.getCanonicalName();

        Properties.TARGET_CLASS = targetClass;

        String[] command = new String[] { "-generateSuite", "-class", targetClass };

        Object result = evosuite.parseCommandLine(command);
        GeneticAlgorithm<?> ga = getGAFromResult(result);
        TestSuiteChromosome best = (TestSuiteChromosome) ga.getBestIndividual();
        System.out.println("EvolvedTestSuite:\n" + best);

        int goals = TestGenerationStrategy.getFitnessFactories().get(0).getCoverageGoals().size(); // assuming single fitness function
        Assert.assertEquals("Wrong number of goals: ", 3, goals);
        Assert.assertEquals("Non-optimal coverage: ", 1d, best.getCoverage(), 0.001);
    }
}

The first thing worth noting is that this system test extends SystemTestBase. This is important for system tests, as it resets the state of EvoSuite (e.g., properties) and prepares everything for test execution (e.g., classpath). It also sets a couple of important properties for tests – if you are interested to see which ones they are, check out method setDefaultPropertiesForTestCases in the SystemTestBase class. In particular, it sets this property:

Properties.CLIENT_ON_THREAD = true;

This tells EvoSuite not to spawn a new process for the client (i.e., the part that runs the search and executes the tests). The reason for this is that is that a standard Java debugger will only allow you to work in the process it is attached to, not in any child processes spawned. So, if you want to, for example, set some breakpoints, it is essential that Properties.CLIENT_ON_THREAD is set to true, otherwise the debugger will not be involved when the breakpoint is passed.

The testNullString test starts by creating a new instance of EvoSuite; then, it tells EvoSuite what the class under test is, by setting Properties.TARGET_CLASS to the fully qualified name of the class under test. As you can see, if you want to set any specific properties of EvoSuite for your test, you can simply set them in the test. The SystemTestBase will ensure that these properties are reset to their defaults after test execution. In our example, the class under test is NullString, which is the following class:

package com.examples.with.different.packagename;

public class NullString {

    public boolean isNull(String s){
        if(s==null){
            return true;
        } else {
            return false;
        }
    }
}

On this class, we can only achieve 100% branch coverage if EvoSuite is able to provide a null and a non-null value for String parameters. Thus, this class serves to test whether EvoSuite properly supplies null values for strings.

The test next invokes EvoSuite for the target class using these two lines:

String[] command = new String[] { "-generateSuite", "-class", targetClass };

Object result = evosuite.parseCommandLine(command);

This essentially is the same as calling EvoSuite on the command line and passing in some arguments, which are captured in the command array here. EvoSuite will then generate some tests, and return an object that summarizes the test generation. SystemTestBase provides a helper function to extract the genetic algorithm instance from this result object:

GeneticAlgorithm<?> ga = getGAFromResult(result);

We can query the search about various things, and most importantly, we can ask it for the best individual, i.e., the result of the test generation:

TestSuiteChromosome best = (TestSuiteChromosome) ga.getBestIndividual();

Now that we’ve got the test suite, we can do what we want with it – for example print it to stdout:

System.out.println("EvolvedTestSuite:\n" + best);       

Or, more importantly, we can write some assertions to check that the result is as expected. In this particular test, there are two assertions:

int goals = TestGenerationStrategy.getFitnessFactories().get(0).getCoverageGoals().size(); // assuming single fitness function
Assert.assertEquals("Wrong number of goals: ", 3, goals);
Assert.assertEquals("Non-optimal coverage: ", 1d, best.getCoverage(), 0.001);

The first assertion checks if the number of coverage goals for the class under test is 3. The second assertion checks that we have achieved 100% coverage. Checking the number of coverage goals has proven quite useful over time, as a change in the number of coverage goals (for whatever reason) will usually have implications on the coverage that can be achieved. Debugging this case is much easier if we know explicitly that this has happened, rather than when trying to guess why the coverage percentage is not as expected.

Try to execute the the test and see if it passes.

Now, before the call to evosuite.parseCommandLine, insert the following line:

Properties.NULL_PROBABILITY = 1.0;

Re-run the test again – EvoSuite is now configured to only generate null objects, so it should only achieve 67% branch coverage (it covers the default constructor and the true branch in the target method isNull).

Now let’s remove that line again from the test to make sure we don’t have a broken test! (Re-run the test after removing the line to make sure it passes again.)

Extending the search algorithm

Now let’s make some changes to EvoSuite. The first example scenario we will consider is the actual search algorithm. As you might know, EvoSuite uses a Genetic Algorithm to drive the test generation. In a nutshell, this means that there is a population of candidate solutions (chromosomes, which are test suites in this case), and these test suites are evolved using search operators that are intended to simulate natural evolution. A fitness function estimates how good each candidate solution is. The fittest individuals have the highest likelihood of reproducing, and if they are selected for reproduction, then two parent individuals are combined to produce two new offspring individuals using a crossover operator, and then mutation makes smaller changes to these offspring.

All this is implemented in the client module, in the org.evosuite.ga package. There is an abstract superclass org.evosuite.ga.metaheuristics, and then there are several concrete implementations, such as the StandardGA, a SteadyStateGA, or EvoSuite’s default, the MonotonicGA. If you look at the GeneticAlgorithm class you will see that the search algorithm has plenty of members, such as a selection operator selectionFunction, the crossover operator crossoverFunction, and a population (population). The population is a list because individuals are ranked by their fitness value; this value is calculated by the fitnessFunctions. This, in turn, is a list because EvoSuite typically is used with several fitness functions at the same time, and there is a fitness value for every fitness function. If you want to know more details about how genetic algorithms work, you could go and read Darrell Whitley’s excellent tutorial (or some of the countless tutorials on the web).

As you can see, the GeneticAlgorithm class is instantiated with a SinglePointCrossOver by default. Let’s have a closer look at how this class looks like – open up the class org.evosuite.ga.operators.crossover.SinglePointCrossover in an editor. The class extends the abstract class CrossOverFunction, and implements the method crossOver. The method receives two individuals as parents and chooses two crossover points point1 and point2 randomly, one for each of the two individuals. Then, it clones the parents, and on the resulting individuals it invokes the crossover method to do the actual work. This is the beauty of meta-heuristic search algorithms: The algorithm is independent of what the chromosomes represent.

Let’s assume that we would like to implement an alternative crossover operator, which always cuts chromosomes in the middle, unlike the existing crossover operators which all choose random crossover points. Let’s create a new Java class org.evosuite.ga.operators.crossover.MiddleCrossOver in the client module (file client/src/main/java/org/evosuite/ga/operators/crossover/MiddleCrossOver.java). The class should extend the abstract class CrossOverFunction, which means it has to implement the method crossOver. The skeleton thus looks like this:

package org.evosuite.ga.operators.crossover;

import org.evosuite.ga.Chromosome;
import org.evosuite.ga.ConstructionFailedException;

public class MiddleCrossOver extends CrossOverFunction {
    @Override
    public void crossOver(Chromosome parent1, Chromosome parent2) throws ConstructionFailedException {
       // TODO   
    }
}

In order to implement this crossover function, we need to understand one important aspect: Textbook examples on genetic algorithms will usually assume a fixed number of genes in a chromosome. However, unlike many other standard applications of genetic algorithms, the size of individuals in EvoSuite can vary, as we cannot know the right number of test cases before we even start the search. Thus, what is the “middle” is different for every individual.

Thus, the first thing we need to check is whether our individuals even have more than one test case. If they don’t there’s no way we can do any crossover:

if (parent1.size() < 2 || parent2.size() < 2) {
    return;
}

After this, we can assume that both parent chromosomes have at least 2 tests, and so we can calculate the middle of each of them:

int middle1 = (int) Math.round(parent1.size() / 2.0);
int middle2 = (int) Math.round(parent2.size() / 2.0);

The crossover operator in EvoSuite changes a chromosome in place. That means we first need to create the offspring as direct copies of the parents:

Chromosome t1 = parent1.clone();
Chromosome t2 = parent2.clone();

Now we can change the offspring using the crossOver method, which takes as parameters (1) the other chromosome with which to cross over, (2) the crossover point in the chromosome the method is invoked on, and (3) the crossover point in the other chromosome:

parent1.crossOver(t2, middle1, middle2);
parent2.crossOver(t1, middle2, middle1);

That’s it!

Does it work? Let’s write a test case to find out. Let’s add a new file client/src/test/java/org/evosuite/ga/operators/crossover/MiddleCrossOverTest.java.

The tests in the client module have a DummyChromosome implementation that we use for the test. A DummyChromosome takes a list of integers, and does mutation and crossover. For example, we could create to parents with different sizes (e.g., 4 and 2), and then check if the resulting individuals have the right genes. For example, the test could look like this:

@Test
public void testSinglePointCrossOver() throws ConstructionFailedException {
    DummyChromosome parent1 = new DummyChromosome(1, 2, 3, 4);
    DummyChromosome parent2 = new DummyChromosome(5, 6);

    MiddleCrossOver xover = new MiddleCrossOver();

    DummyChromosome offspring1 = new DummyChromosome(parent1);
    DummyChromosome offspring2 = new DummyChromosome(parent2);

    xover.crossOver(offspring1, offspring2);

    assertEquals(Arrays.asList(1, 2, 6), offspring1.getGenes());
    assertEquals(Arrays.asList(5, 3, 4), offspring2.getGenes());
}

If you did everything correctly, then this test should pass. Does it?

Now that we’ve got this wonderful new crossover operator, the big question is: How do we make EvoSuite use it?

EvoSuite is highly configurable, and the configuration is controlled by the class org.evosuite.Properties, which is in the client module. In this class, you’ll find all the different properties that EvoSuite supports – there are a lot of them. Each property consists of a public static field in all caps, which is how the properties are accessed from within code. In addition, each property has @Parameter annotation, in which we define a key – this is the key we use on the command line, if we set properties using the -Dkey=value syntax. If we look for crossover, we will find the following relevant code:

public enum CrossoverFunction {
    SINGLEPOINTRELATIVE, SINGLEPOINTFIXED, SINGLEPOINT, COVERAGE
}

@Parameter(key = "crossover_function", group = "Search Algorithm", description = "Crossover function during search")
public static CrossoverFunction CROSSOVER_FUNCTION = CrossoverFunction.SINGLEPOINTRELATIVE;

Thus, there is a property Properties.CROSSOVER_FUNCTION, and it is of type CrossoverFunction, which is an enum that contains all the possible crossover functions. In the future maybe EvoSuite will see some way to make it extensible at runtime, but for now we need to add our new crossover operator to the enum:

public enum CrossoverFunction {
    SINGLEPOINTRELATIVE, SINGLEPOINTFIXED, SINGLEPOINT, COVERAGE, MIDDLE
}

The final thing we need to change is the place where this property is read and the crossover function is instantiated. If we follow the usages of the Properties.CROSSOVER_FUNCTION field, we see that it is used in org.evosuite.strategy.PropertiesSuiteGAFactory and org.evosuite.strategy.PropertiesTestGAFactory. These are two factory classes that create and configure a genetic algorithm object based on the values in the Properties class. As we are doing whole test suite generation (it’s EvoSuite’s default), let’s edit PropertiesSuiteGAFactory. Find the method getCrossoverFunction(). It contains a switch over the value of our property, and calls the corresponding constructor. Thus, we need to add a new case:

case MIDDLE:
    return new MiddleCrossOver();

That’s it! Now we’re ready to generate a jar file and use EvoSuite with our new crossover function. Recall that you can generate the jar file (which will be located in master/target) using:

mvn package

When we now run EvoSuite with this jar file, we can specify to use our new crossover function using -Dcrossover_function=Middle. How about running some experiments to see if the crossover operator makes a difference? (Disclaimer: Likely it will not, it’s just an example for illustration purposes.)

Adding a new coverage criterion and fitness function

We now know how to make changes to the search algorithm, but we have not yet touched what constitutes a majority of EvoSuite’s code: Dealing with tests.

Let’s assume we want to have EvoSuite support a new coverage criterion. In software testing, pairwise testing is all the rage these days. Maybe we should also aim to cover all pairs of method calls? Suppose we have the following class:

public class Foo {
    public void bar() { ... }

    public void foo() { ... }

    public void zoo() { ... }
}

With default coverage criteria, EvoSuite will aim to cover each of the three methods as thoroughly as possible. With our fantastic new idea of pairwise method coverage, we would like to get EvoSuite to also create objects that call bar and foo, bar and zoo, and foo and zoo in sequence. As with the crossover operator above, this is just a hypothetical example – we’re not saying that this is something we should really do in practice.

Coverage criteria in EvoSuite are implemented as fitness functions. For each coverage criterion, there are three main classes:

• A test suite fitness function, which guides the search in the space of test suites towards achieving full coverage of the criterion.
• A test case fitness function, which guides the search in the space of test cases towards satisfying an individual coverage goal. This is also used to determine whether an individual coverage goal is covered by a test suite.
• A test goal factory which produces a set of test case fitness function, such that a test suite that covers each of these test case fitness functions also has optimal fitness when measured with the test suite fitness function.

You can find plenty of examples in the client module in the package org.evosuite.coverage.

Let’s add a new package: org.evosuite.coverage.methodpair. We will start by adding a fitness function for individual tests. Although the default in EvoSuite is to evolve test suites rather than individual tests, EvoSuite can also evolve populations consisting of individual tests, for example by using the baseline approach -generateTests, or by using the new many-objectives ‘MOSA’ approach -generateMOSuite. Furthermore, even when EvoSuite evolves test suites, all postprocessing requires that a coverage criterion is represented as a set of test fitness functions. Create the class org.evosuite.coverage.methodpair.MethodPairTestFitness. This class will inherit from org.evosuite.testcase.TestFitnessFunction:

public class MethodPairTestFitness extends TestFitnessFunction {

A test fitness function is instantiated for a specific pair of methods, so we need to somewhere store the names of these methods in the fitness function. Let’s simply use strings to remember the classname and the names of the two methods:

    private final String className;
    private final String methodName1;
    private final String methodName2;

Of course we also need the usual boiler plate code to handle setting and reading of these properties. We will set these values in the constructor, and add some getters:

    public MethodPairTestFitness(String className, String methodName1, String methodName2) {
        this.className = className;
        this.methodName1 = methodName1;
        this.methodName2 = methodName2;
    }

    public String getClassName() {
        return className;
    }

    public String getMethodName1() {
        return methodName1;
    }

    public String getMethodName2() {
        return methodName2;
    }

So far that was easy. The main part of functionality of the fitness function is the method getFitness, which we have to override. This is an overloaded method; there is one version that takes a TestChromosome as input, and one that takes a TestChromosome and an ExecutionResult as input. The class org.evosuite.testcase.TestChromosome is the genetic encoding of a sequence of method calls. If you look at the class you will see that it contains a test case of the class org.evosuite.testcase.TestCase, and then the main functionality of the TestChromosome lies in the mutate and crossover methods. The TestCase interface, in turn, is implemented by the org.evosuite.testcase.DefaultTestCase class, which consists of a list of org.evosuite.testcase.Statement implementations. There are all sorts of different types of statements implemented in the org.evosuite.testcase.statements package, and it might be a good idea to look around this package a bit. For each statement class, the most crucial functionality is probably the implementation of the execute method, which is where Java reflecton is used to execute tests. Each statement class also makes use of a number of VariableReference instances – these are the variables used in the test, and point to the objects created by the statements of a test. In EvoSuite, each statement creates one such VariableReference – except void methods calls.

For our purposes of creating method-pair coverage, the two statements we need to take a look at are ConstructorStatement and MethodStatement. As the names suggest, these invoke a constructor and, respectively, a method. Again it is worth looking into these classes, but we really just need to know the names of the class and method for our fitness function. This information is provided by three methods: getDeclaringClass, getMethodName, and getDescriptor. What’s a descriptor? A descriptor represents the parameters that a method takes and the value that it returns (See [StackOverflow explanation (http://stackoverflow.com/questions/7526483/what-is-the-difference-between-descriptor-and-signature)]). For example, if we have a method that takes as input two integers and returns a boolean, the descriptor would be “(II)Z”, where I represents an integer and Z the boolean return value. The main important thing for us is that the descriptor allows us to distinguish between overloaded methods. As this needs to be done often in EvoSuite, in most cases EvoSuite actually uses the concatenation of method name and descriptor, rather than just the plain method name.

Let’s go ahead and implement getFitness:

    @Override
    public double getFitness(TestChromosome individual, ExecutionResult result) {

The ExecutionResult contains information (e.g., an execution trace, exceptions raised, etc.) that result from running a test case. In fact, the method getFitness(TestChromosome individual) in TestFitnessFunction simply runs the test to produce this result, and then invokes the method we are looking at now. An important feature of EvoSuite is that it only re-executes a test case when it has changed. The ExecutionResult is cached in the TestChromosome class, and if we want to calculate fitness of a test that has not been mutated we can simply use the cached result, rather than running the test again. This saves a lot of time.

Next, let’s define a variable for our fitness value. We will initialise this with 1.0, and define an optimal value as value 0.0:

        double fitness = 1.0;

Now we just need to iterate over all the statements of the test, pick out the MethodStatements and ConstructorStatements, and check whether we have a pair or not, and update the value of fitness to reflect this (i.e., set it to 0 if we found the method pair we are looking for).

        for (Statement stmt : result.test) {
            // TODO: check if we have hit a pair
        }

        updateIndividual(this, individual, fitness);
        return fitness;
    }

The call to updateIndividual is necessary to do some housekeeping, in particular each chromosome stores the last fitness value for every fitness function with which it was evaluated.

There is a difference between the genotype of the TestChromosome, i.e., it’s sequence of calls, and the resulting test case: Statements along the test execution may lead to uncaught exceptions. By default, EvoSuite stops execution as soon as it hits the first exception, but it can also be configured to continue executing (Properties.BREAK_ON_EXCEPTION). Thus, it might be that the genotype contains pairs of methods, but the test execution does not actually reach them. We can get information about exceptions from the ExecutionResult, for example by calling method getPositionsWhereExceptionsWereThrown, which returns the set of positions where exceptions happened. Let’s add the following line before our loop:

        Set<Integer> exceptionPositions = result.getPositionsWhereExceptionsWereThrown();           

To keep things simple, let’s simply stop looking at method pairs as soon as we find an exception; that is, we need to stop iterating over statements once we’ve hit one that threw an exception:

        for (Statement stmt : result.test) {
            // TODO: check if we have hit a pair

            if(exceptionPositions.contains(stmt.getPosition()))
                break;
        }

The only thing left to do is comparing whether a given statement matches part of a pair we are looking for. For this, we first need to know if the statement is a MethodStatement or ConstructorStatement in the first place, for example like so:

        for (Statement stmt : result.test) {
            if ((stmt instanceof MethodStatement || stmt instanceof ConstructorStatement)) {
                // TODO: Handle name of method
            }
            if(exceptionPositions.contains(stmt.getPosition()))
                break;
        }
        updateIndividual(this, individual, fitness);
        return fitness;
    }

If we know the statement is a MethodStatement or ConstructorStatement, we need to find out the name of the class and the name of the constructor. Recall that when we say method name, we actually mean method name and descriptor. MethodStatement and ConstructorStatement both inherit from the abstract class EntityStatementWithParameters, and so we can use that super class to access the information we need:

                EntityWithParametersStatement ps = (EntityWithParametersStatement)stmt;
                String className  = ps.getDeclaringClassName();
                String methodName = ps.getMethodName() + ps.getDescriptor();

That’s all we need to know about the statements. Now, as we are interested in pairs, we first need to check if we have hit the first method, and then check the next statement against the second method. For example, we could add a simple boolean helper variable to remember when we saw the first call, and when it is set to true, check the second call:

        boolean haveSeenMethod1 = false;

        for (Statement stmt : result.test) {
            if ((stmt instanceof MethodStatement || stmt instanceof ConstructorStatement)) {
                EntityWithParametersStatement ps = (EntityWithParametersStatement)stmt;
                String className  = ps.getDeclaringClassName();
                String methodName = ps.getMethodName() + ps.getDescriptor();

                if(haveSeenMethod1) {
                    if (this.className.equals(className) && this.methodName2.equals(methodName)) {
                        fitness = 0.0;
                        break;
                    }
                } else if (this.className.equals(className) && this.methodName1.equals(methodName)) {
                    haveSeenMethod1 = true;
                    fitness = 0.5;
                } else {
                    haveSeenMethod1 = false;
                }
            }
            if(exceptionPositions.contains(stmt.getPosition()))
                break;
        }

We are comparing the class name and the first method name, and if it matches we set haveSeenMethod1 to true. If it is set to true, we check the second name; else we set our helper variable back to false. As you can see we can provide a little bit of guidance to the search here: If the method is called, we are already half way there to covering the pair, so we are assigning an intermediate value of 0.5; and we assign 0.0 if both are covered. (This could be further refined: For example, we do not handle the case where method 2 is called but not method 1 – here we also could provide a fitness value between 0 and 1.)

That’s it, we have the main functionality. The abstract class TestFitnessFunction requires us to override a couple more methods. For example, we must implement getTargetClass and getTargetMethod – here we could simply return the name of method 1. We also need to override hashCode, equals, and compareTo. The hashCode and equals methods can be generated automatically by Eclipse or IntelliJ. For example, here is what IntelliJ generates:

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    MethodPairTestFitness that = (MethodPairTestFitness) o;

    if (className != null ? !className.equals(that.className) : that.className != null) return false;
    if (methodName1 != null ? !methodName1.equals(that.methodName1) : that.methodName1 != null) return false;
    return methodName2 != null ? methodName2.equals(that.methodName2) : that.methodName2 == null;

}

@Override
public int hashCode() {
    int result = className != null ? className.hashCode() : 0;
    result = 31 * result + (methodName1 != null ? methodName1.hashCode() : 0);
    result = 31 * result + (methodName2 != null ? methodName2.hashCode() : 0);
    return result;
}

The method compareTo we will have to implement ourselves, as this is not generated automatically. This method should return 0 if the two objects compare are equal, and else return +1/-1 to imply an order. We need to implement this method because TestFitnessFunction implements the java.lang.Comparable interface. This is needed because TestFitnessFunctions are sometimes sorted – for example, EvoSuite tries to sort tests in the final JUnit test suite based on the order of the test fitness functions (e.g., to sort the tests in the same order as the methods in the class under test). If you don’t care about the order you could simply make the method return 0, but we could just use the compareTo method on the classname, the first and the second method name.

@Override
public int compareTo(TestFitnessFunction other) {
    if (other instanceof MethodPairTestFitness) {
        MethodPairTestFitness otherMethodFitness = (MethodPairTestFitness) other;
        if (className.equals(otherMethodFitness.getClassName())) {
            if(methodName1.equals(otherMethodFitness.getMethodName1()))
               return methodName2.compareTo(otherMethodFitness.getMethodName2());
            else
                return methodName1.compareTo(otherMethodFitness.getMethodName1());
        }
        else
            return className.compareTo(otherMethodFitness.getClassName());
    }
    return compareClassName(other);
}

That really completes the test fitness function. However, we need more before we can make use of it: This fitness function only helps us to generate a test that covers one method pair. We now need a way to enumerate all the method pairs for a given class. In EvoSuite, this is what a TestFactory does. Let’s create a new class org.evosuite.coverage.methodpair.MethodPairFactory which extends the class AbstractFitnessFactory:

public class MethodPairFactory extends AbstractFitnessFactory<MethodPairTestFitness> {  

In this class, we need to override the method getCoverageGoals, which is the factory method that creates a list of TestFitnessFunctions.

    @Override
    public List<MethodPairTestFitness> getCoverageGoals() {
        List<MethodPairTestFitness> goals = new ArrayList<>();

        // pair each constructor with each method and add to goals

        // pair each method with each other method and add to goals

        return goals;
    }

Basically, we need to find all methods of the class, and then create all pairs using two nested loops. However, we also need to think about the constructors, although it makes less sense to pair them up with each other. In fact, we only need to include constructors as the first method in a pair. Let’s assume we have a helper method getUsableConstructors that returns all public constructors for a given class, and a method getUsableMethods that returns all public methods for a given class, using Java reflection. We can get the class under test by accessing Properties.getTargetClass(), and its name is stored in Properties.TARGET_CLASS. Thus, the combinations of method pairs can be constructed as follows:

    @Override
    public List<MethodPairTestFitness> getCoverageGoals() {
        List<MethodPairTestFitness> goals = new ArrayList<>();

        String className = Properties.TARGET_CLASS;
        Class<?> clazz = Properties.getTargetClass();
        Set<String> constructors = getUsableConstructors(clazz);
        Set<String> methods      = getUsableMethods(clazz);

        for(String constructor : constructors)
            for(String method : methods)
                goals.add(new MethodPairTestFitness(className, constructor, method));

        for(String method1 : methods)
            for(String method2 : methods)
                goals.add(new MethodPairTestFitness(className, method1, method2));

        return goals;
    }

Given two methods A and B, we create pairs (A, B) as well as (B, A), because the order of method calls may make a difference. We also include (A, A) and (B, B), as calling the same method twice might also lead to interesting behaviour. For each par of methods, we instantiate one of our MethodPairTestFitness functions. The method name of a constructor will be ““, we only need to make sure that our helper method getUsableConstructors does just that:

    protected Set<String> getUsableConstructors(Class<?> clazz) {
        Set<String> constructors = new LinkedHashSet<>();
        Constructor<?>[] allConstructors = clazz.getDeclaredConstructors();
        for (Constructor<?> c : allConstructors) {
            if (TestUsageChecker.canUse(c)) {
                String methodName = "<init>" + Type.getConstructorDescriptor(c);
                constructors.add(methodName);
            }
        }
        return constructors;
    }

This method uses reflection to get all constructors that are declared by the class under test (clazz). For each constructor, we then generate a full name consisting of “” as well as the descriptor. To generate the descriptor, we use Type.getConstructorDescripter, which is a helper function provided by the [ASM(http://asm.ow2.org)] library, which EvoSuite uses for bytecode instrumentation and analysis. The TestUsageChecker is a utility class in EvoSuite – a constructor is usable if it is public, and if it is package private or protected and in the same package as the test class. EvoSuite puts the tests it generates in the same package as the class under test, thus the tests can always access the protected and package private constructors of the class under test. We put all the methods that are accessible into a set, and return that. The getUsableMethods function looks similar:

    protected Set<String> getUsableMethods(Class<?> clazz) {
        Set<String> methods = new LinkedHashSet<>();
        Method[] allMethods= clazz.getDeclaredMethods();
        for (Method m : allMethods) {
            if (TestUsageChecker.canUse(m)) {
                String methodName = m.getName()+ Type.getMethodDescriptor(m);
                methods.add(methodName);
            }
        }
        return methods;
    }

The main difference is that we now use the actual method name. Note that we again look only at declared methods; that means we do not include inherited methods. The reason behind this is that if we wanted to test the code written in a superclass, we assume that we would apply EvoSuite to that superclass directly.

Now we have a test fitness function and a factory to generate instances, so all that’s left to do is a fitness function for test suites. Let’s create a new class MethodPairSuiteFitness, which extends the TestSuiteFitnessFunction class:

public class MethodPairSuiteFitness extends TestSuiteFitnessFunction {  

Again, the main method to override is getFitness:

@Override
public double getFitness(AbstractTestSuiteChromosome<? extends ExecutableChromosome> suite) {
    double fitness = 0.0;

    // TODO: calculate fitness value

    updateIndividual(this, suite, fitness);
    return fitness;
}

The parameter is a subclass of AbstractTestSuiteChromosome, which in most cases means it will be an org.evosuite.testsuite.TestSuiteChromosome. A TestSuiteChromosome consists of a list of TestChromosomes, and adds functionality for crossover and mutation.

To keep things simple, we will use a very basic, naive way to implement the test suite fitness function: We will simply create a set of MethodPairTestFitness objects and check for each of them; the fitness value is the number of uncovered goals. Thus, 100% coverage means fitness 0.0.

Let’s add a field allMethodPairs to the class:

private final Set<MethodPairTestFitness> allMethodPairs = new HashSet<>();

We can simply use our factory to determine these method pairs, so let’s do that in the constructor:

public MethodPairSuiteFitness() {
    methodPairGoals.addAll(new MethodPairFactory().getCoverageGoals());
}

Now we can use this set of goals and check them against all the tests in the test suite. There are several ways to do this – the one we’re showing in this tutorial uses the method runTestSuite, which returns a list of ExecutionResult objects for the tests in a test suite. We can then use these results and check them against the goals. A TestFitnessFunction is covered by a test if the ExecutionResult leads to fitness value 0, and this is captured in the method isCovered:

@Override
public double getFitness(AbstractTestSuiteChromosome<? extends ExecutableChromosome> suite) {
    double fitness = 0.0;

    List<ExecutionResult> results = runTestSuite(suite);
    Set<MethodPairTestFitness> coveredMethodPairs = new HashSet<>();
    for(MethodPairTestFitness goal : allMethodPairs) {
        for(ExecutionResult result : results) {
            if(goal.isCovered(result)) {
                coveredMethodPairs.add(goal);
                break;
            }
        }
    }
    fitness = methodPairGoals.size() - coveredMethodPairs.size();   

    updateIndividual(this, suite, fitness);
    return fitness;
}

Done!

Well, not quite: There is some more houskeeping to be done. First, a TestSuiteChromosome is expected to know the coverage value, so our fitness function needs to calculate that. Thus, before returning the fitness value, add:

    suite.setNumOfCoveredGoals(this, coveredMethodPairs.size());        
    if (!allGoals.isEmpty())
        suite.setCoverage(this, (double) calledMethodPairs.size() / (double) methodPairGoals.size());
    else
        suite.setCoverage(this, 1.0);           

The test suite thus knows how many goals it has covered for every fitness function, and it knows its overall fitness value. As the number of goals for a given criterion can be 0 (e.g., if all methods are non-public), we need to check for that to avoid a division by zero error.

A further recommendable step in a fitness function is to check for timeouts. Test cases are executed with a timeout of 4 seconds by default. However, we usually don’t want to keep these test suites around, so we could check all the ExecutionResult objects, and if any of them has a timeout, we would give the test suite the maximum (worst) possible fitness value – which is the value if no method pair is covered, i.e., the size of allMethodPairs:

    for (ExecutionResult result : results) {
        if (result.hasTimeout() || result.hasTestException()) {
            fitness = allMethodPairs.size();
            break;
        }
    }

Testing the pairwise method coverage fitness

Before going ahead and using the new coverage criterion in practice, we should make sure this actually works – so let’s do some testing. Unlike the simple unit test for our middle crossover function, testing a coverage criterion requires that we have a class under test and generally a complex test fixture; this is easier to test using a system test, similar to the NullStringSystemTest we saw earlier. The test class needs to extend SystemTestBase in order to inherit all then ecessary setup/cleanup code to ensure deterministic tests. Let’s create a new test class in master/src/test/java/org/evosuite/coverage/methodpair/MethodPairCoverageSystemTest:

public class MethodPairCoverageSystemTest extends SystemTestBase {

    // TODO
}

First, let’s test the basic case of a class with only one method. EvoSuite has many small example classes that are used during testing, and most of them are in the package com.examples.with.different.packagename. This package name simply reflects that the classes are somewhere outside of EvoSuite’s scope, which is important because EvoSuite will refuse to instrument or test itself. Class com.examples.with.different.packagename.SingleMethod contains a single trivial method:

public class SingleMethod {     
    public String foo(){
        return "foo";
    }
}

What we would expect from applying our new coverage criterion on this class is two goals. Why two? There is an implicitly generated default constructor (SingleMethod()), and thus we have two pairs, one is the pair of constructor and method foo, and the other is the pair of foo with another call to foo. We start the test case by setting up the class under test:

@Test
public void testMethodFitnessSimpleExample() {
    EvoSuite evosuite = new EvoSuite();

    String targetClass = SingleMethod.class.getCanonicalName();
    Properties.TARGET_CLASS = targetClass;      

Next, we need to make sure our test uses our new coverage criterion. We can simply set the criterion property to our new criterion (note that EvoSuite expects a list of criteria, as it can simultaneously optimise for several coverage criteria:)

    Properties.CRITERION = new Properties.Criterion[]{Properties.Criterion.METHODPAIR};

Now we just need to run EvoSuite and retrieve the resulting test suite. We’ve already seen how this is done earlier in the NullStringSystemTest:

    String[] command = new String[] { "-generateSuite", "-class", targetClass };
    Object result = evosuite.parseCommandLine(command);
    GeneticAlgorithm<?> ga = getGAFromResult(result);
    TestSuiteChromosome best = (TestSuiteChromosome) ga.getBestIndividual();        

If we want to see what our goals are and what the resulting test suite is, we can simply print them out like this:

    System.out.println("EvolvedTestSuite:\n" + best);
    for(TestFitnessFunction goal : TestGenerationStrategy.getFitnessFactories().get(0).getCoverageGoals()) {
        System.out.println("Goal: "+goal);
    }

However, the main part of the test will be to check that the result matches our expectation. We want to make sure there are 2 goals; and if EvoSuite doesn’t manage to cover both of them then something would be very wrong, so we can also expect 100% coverage:

    int goals = TestGenerationStrategy.getFitnessFactories().get(0).getCoverageGoals().size(); // assuming single fitness function
    Assert.assertEquals(2, goals );
    Assert.assertEquals("Non-optimal coverage: ", 1d, best.getCoverage(), 0.001);
}

Does the test pass? If it doesn’t, then something is wrong in the implementation and some debugging awaits. If it works (as it should), then maybe it’s time to think about a slightly more involved example. We still want to test a simple class under test to make sure it’s easy to understand, quick to execute, and the result is reliable and deterministic, so how about a class with two method. An example class included in EvoSuite’s collection of test classes is com.examples.with.different.packagenameExampleObserverClass, which has a setter and a getter:

public class ExampleObserverClass {
    private int privateMember = 0;

    public void setMember(int x) {
        privateMember = x;
    }

    public int getMember() {
        return privateMember;
    }
}

With two methods and one default constructor, how many pairs do we expect? That’s right, 6: (Constructor, setMember), (Constructor, getMember), (setMember, getMember), (setMember, setMember), (getMember, setMember), (getMember, getMember). Thus, we can create a test just like the previous one, except that we use a different class under test (ExampleObserverClass), and need to expect 6 goals. It is still reasonable to expect 100% coverage, so we can keep that assertion:

@Test
public void testMethodPairFitness() {
    EvoSuite evosuite = new EvoSuite();

    String targetClass = ExampleObserverClass.class.getCanonicalName();
    Properties.TARGET_CLASS = targetClass;
    Properties.CRITERION = new Properties.Criterion[]{Properties.Criterion.METHODPAIR};

    String[] command = new String[] { "-generateSuite", "-class", targetClass };
    Object result = evosuite.parseCommandLine(command);
    GeneticAlgorithm<?> ga = getGAFromResult(result);
    TestSuiteChromosome best = (TestSuiteChromosome) ga.getBestIndividual();

    System.out.println("EvolvedTestSuite:\n" + best);
    for(TestFitnessFunction goal : TestGenerationStrategy.getFitnessFactories().get(0).getCoverageGoals()) {
        System.out.println("Goal: "+goal);
    }
    int goals = TestGenerationStrategy.getFitnessFactories().get(0).getCoverageGoals().size(); // assuming single fitness function
    Assert.assertEquals(6, goals );
    Assert.assertEquals("Non-optimal coverage: ", 1d, best.getCoverage(), 0.001);
}

If this test also passes, then you’re ready to apply EvoSuite with the new criterion!

If you want to get the source code for the MethodPair coverage criterion rather than extracting it from this tutorial bit-by-bit, then you’ll be happy to hear that Gregory Gay included the relevant classes in the evosuite-tutorial branch on his EvoSuite fork.