Fuzzing with Zest

This tutorial walks through the process of writing a standalone test driver using JQF, a structured input generator using junit-quickcheck, and fuzzing with the Zest algorithm using command-line scripts. If your test program is built using Maven, then it is much easier to use the JQF Maven Plugin, which does not require you to install JQF locally or to run bash scripts.

Requirements

For this tutorial, you will need: Java 8+, Apache Maven (to build JQF), Bash (to launch fuzzing scripts). This tutorial has been tested on MacaOS and Ubuntu Linux. It may also work on Windows under Cygwin or Git bash.

Step 1: Build JQF

git clone https://github.com/rohanpadhye/jqf
cd jqf
mvn package

From here on, the tutorial will refer to the directory in which JQF has been cloned as /path/to/jqf.

Step 2: Write a test driver

In this tutorial, we are going to test two properties about GregorianCalendar objects, which represent dates in the widely used Gregorian calendar system.

First, let's say that we want to check that Gregorian calendar objects obey leap year rules.

Here is a first draft of the test driver:

import java.util.*;
import static java.util.GregorianCalendar.*;
import static org.junit.Assert.*;
import static org.junit.Assume.*;

public class CalendarTest {

    public void testLeapYear(GregorianCalendar cal) {
        // Assume that the date is Feb 29
        assumeTrue(cal.get(MONTH) == FEBRUARY);
        assumeTrue(cal.get(DAY_OF_MONTH) == 29);

        // Under this assumption, validate leap year rules
        int year = cal.get(YEAR);
        assertEquals(year + " should be multiple of 4", 0, year % 4);
        assertNotEquals(year + " should not be multiple of 100", 0, year % 100);
    }
}

Let's save this file as CalendarTest.java.

The method testLeapYear() checks the following property: assuming that an input GregorianCalendar represents the date February 29, then it must belong to a year that is divisible by 4, but not divisible by 100. Astute readers among you would notice that this assertion is actually incorrect. We expect an AssertionError to be thrown when provided with a valid counter-example. However, we need something that can generate random instances of GregorianCalendar.

Step 2: Write an input generator

JQF leverages the junit-quickcheck framework to produce structured inputs. In order to generate inputs for type T, we need a class that extends Generator<T>. Such a subclass need only provide a method that can produce random instances of T using a provided source of randomness. The following is our generator for GregorianCalendar objects, in a file called CalendarGenerator.java:

import java.util.GregorianCalendar;
import java.util.TimeZone;

import com.pholser.junit.quickcheck.generator.GenerationStatus;
import com.pholser.junit.quickcheck.generator.Generator;
import com.pholser.junit.quickcheck.random.SourceOfRandomness;

import static java.util.GregorianCalendar.*;

public class CalendarGenerator extends Generator<GregorianCalendar> {

    public CalendarGenerator() {
        super(GregorianCalendar.class); // Register the type of objects that we can create
    }

    // This method is invoked to generate a single test case
    @Override
    public GregorianCalendar generate(SourceOfRandomness random, GenerationStatus status) {
        // Initialize a calendar object
        GregorianCalendar cal = new GregorianCalendar();
        cal.setLenient(true); // This allows invalid dates to silently wrap (e.g. Apr 31 ==> May 1).

        // Randomly pibkc a day, month, and year
        cal.set(DAY_OF_MONTH, random.nextInt(31) + 1); // a number between 1 and 31 inclusive
        cal.set(MONTH, random.nextInt(12) + 1); // a number between 1 and 12 inclusive
        cal.set(YEAR, random.nextInt(cal.getMinimum(YEAR), cal.getMaximum(YEAR)));

        // Optionally also pick a time
        if (random.nextBoolean()) {
            cal.set(HOUR, random.nextInt(24));
            cal.set(MINUTE, random.nextInt(60));
            cal.set(SECOND, random.nextInt(60));
        }

        // Let's set a timezone
        // First, get supported timezone IDs (e.g. "America/Los_Angeles")
        String[] allTzIds = TimeZone.getAvailableIDs();

        // Next, choose one randomly from the array
        String tzId = random.choose(allTzIds);
        TimeZone tz = TimeZone.getTimeZone(tzId);

        // Assign it to the calendar
        cal.setTimeZone(tz);

		// Return the randomly generated calendar object
        return cal;
    }
}

Step 3: Annotate test driver

Now that we have a class that can generate random instances of GregorianCalendar, we can specify in our test driver that we want to use this particular generator to create our inputs. To do this, we use the @From(CalendarGenerator.class) annotation on the cal parameter to our test method testLeapYear(). Check out the junit-quickcheck documentation for advanced ways of composing generators (e.g. automatically synthesizing generators from constructors or public fields).

We also need a couple of other annotations to make this a test driver that JQF can fuzz. First, we need to annotate the test class with @RunWith(JQF.class). This tells JUnit that we are using the JQF engine to invoke test methods. Second, we must annotate the test method with @Fuzz. This helps JQF find the methods in the test class for which it can generate inputs. JQF test classes extend standard JUnit test classes, so you can also have parameter-less methods annotated with @Test for example, just like you would with old-school JUnit. Here is our updated test driver CalendarTest.java with the @RunWith, @Fuzz, and @From annotations applied:

import java.util.*;
import static java.util.GregorianCalendar.*;
import static org.junit.Assert.*;
import static org.junit.Assume.*;

import org.junit.runner.RunWith;
import com.pholser.junit.quickcheck.*;
import edu.berkeley.cs.jqf.fuzz.*;

@RunWith(JQF.class)
public class CalendarTest {

    @Fuzz
    public void testLeapYear(@From(CalendarGenerator.class) GregorianCalendar cal) {
        // Assume that the date is Feb 29
        assumeTrue(cal.get(MONTH) == FEBRUARY);
        assumeTrue(cal.get(DAY_OF_MONTH) == 29);

        // Under this assumption, validate leap year rules
        int year = cal.get(YEAR);
        assertEquals(year + " should be multiple of 4", 0, year % 4);
        assertNotEquals(year + " should not be multiple of 100", 0, year % 100);
    }
}

Step 4: Compile test driver and generator

Let's compile CalendarTest.java and CalendarGenerator.java using javac. Since we are using classes from JQF and its dependencies (such as JUnit and junit-quickcheck), we also need to list all of those JARs on the classpath. Fortunately, JQF provides a handy script called classpath.sh which simply expands to the long list of JARs that contain JQF and everything else it depends on. So, the final class path is the current directory (.) which contains the test driver and generator, appended to the output of the classpath.sh script, using the Java class-path separator :.

javac -cp .:$(../scripts/classpath.sh) CalendarGenerator.java CalendarTest.java

Of course, this step is not needed if you are using Maven/Gradle and simply listing jqf-fuzz as a dependency. The build system will take care of resolving any required transitive dependencies.

Optional: Test with JUnit and QuickCheck

Every JQF test is also a junit-quickcheck test, which means that it can simply run like any other JUnit test. For example, you can run the test in your IDE (green button in IntelliJ), run using Maven (mvn test), or run on the command-line:

java -cp .:$(../scripts/classpath.sh) org.junit.runner.JUnitCore CalendarTest

You might see an error message like Assumption is too strong; too many inputs discarded. This is because by default junit-quickcheck randomly samples GregorianCalendar objects by making calls to CalendarGenerator.generate() with a pseudo-random source. Of course, most dates that are randomly generated by this generator will NOT fall on February 29 and therefore most of the generated inputs lead to a violation of the assumptions at the beginning of the testLeapYear() method. Therefore, QuickCheck by itself cannot perform a meaningful test.

Step 5: Fuzz with Zest

To run the Zest algorithm, launch the script jqf-ei from the bin directory in the JQF repository, and provide the name of the class and method that needs to be tested on the command-line. Note that this script configures the classpath using the -c option; use the classpath.sh script as before to include the JQF classes and their dependencies.

/path/to/jqf/bin/jqf-ei -c .:$(../scripts/classpath.sh) CalendarTest testLeapYear

Again, these scripts are not needed if you are using Maven.

Zest status screen

Upon launching the above command, you should see a status screen that looks like this:

JQF: Feedback-directed Generator-based Fuzzing
----------------------------------------------
Test name:            CalendarTest#testLeapYear
Results directory:    /path/to/tutorial/fuzz-results
Elapsed time:         5s (no time limit)
Number of executions: 6,569
Valid inputs:         363 (5.53%)
Cycles completed:     4
Unique failures:      1
Queue size:           3 (3 favored last cycle)
Current parent input: 0 (favored) {68/400 mutations}
Execution speed:      1,396/sec now | 1,182/sec overall
Total coverage:       5 (0.01% of map)
Valid coverage:       3 (0.00% of map)

This screen indicates the method that is being fuzzed, the directory where the results of fuzzing will be stored (this can be overriden using an extra command-line argument to jqf-ei), and various statistics about the fuzzing process. For example, in 10 seconds, Zest has produced over 6,500 inputs at an average of 1,182 inputs per second. Of these, 5.53% are valid, which means that they passed all the assumeTrue() statements in our test driver -- in our case, it means there were 363 inputs that fell on February 29. This is great because the probability of a randomly generated date falling on February 29 is less than 0.3%! Zest's validity fuzzing algorithm allows it to generate a higher proportion of valid inputs.

The status screen also shows how many branches have been exercised in our application by all inputs ("Total coverage") and by valid inputs ("Valid coverage") -- this includes the implicit branches introduced by assume/assert. Since our test was tiny, this number is quite small. If you are fuzzing a complex application like a compiler or web server, this number is usually in the tens of thousands. Step 6 below shows a test with several more branches.

Interestingly, there is "Unique failure". A failure is an input that triggers an undocumented run-time exception or assertion violation while executing the test. Failing inputs are saved in fuzz-results/failures. Apart from failures, Zest saves a corpus of successful inputs in the directory fuzz-results/corpus. These inputs cover different control-flow paths in the test program. The size of this corpus is given by "Queue size" in the status screen, since these inputs are stored in a cyclic queue for continuous mutational fuzzing.

Fuzzing can be stopped at any time by pressing CTRL+C. We can repro the failure to see what went wrong using the jqf-repro script:

/path/to/jqf/bin/jqf-repro -c .:$(../scripts/classpath.sh) CalendarTest testLeapYear fuzz-results/failures/id_000000 

This will print something like:

java.lang.AssertionError: 3600 should not be multiple of 100. Actual: 0
	at org.junit.Assert.fail(Assert.java:88)
	at org.junit.Assert.failEquals(Assert.java:185)
	at org.junit.Assert.assertNotEquals(Assert.java:199)
	at org.junit.Assert.assertNotEquals(Assert.java:211)
	at CalendarTest.testLeapYear(CalendarTest.java:22)

Showing that the second assertion was violated when the year was 3600. But of course! Years that are multiples of 100 can be leap years if they are also multiples of 400. This is clearly a bug in our test, which we can go and fix in CalendarTest.java:

...
        int year = cal.get(YEAR);
        assertEquals(year + " should be multiple of 4", 0, year % 4);
        if (year % 100 == 0) {
            assertEquals(year + " should be multiple of 400", 0, year % 400);
        }
...

Re-compiling CalendarTest.java and re-running Zest will lead to 0 unique failures.

Step 6: Add a more complex test method

TODO