-
Notifications
You must be signed in to change notification settings - Fork 116
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.
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.
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.
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.
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;
}
}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 com.pholser.junit.quickcheck.generator.*;
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);
}
}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.
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.
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.
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 5 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.
Now let's add one more test to our test driver class -- CalendarTest: a method testSort(List<GregorianCalendar> cals). This method takes as input a list of calendar objects, sorts them using a custom comparator function, and then ensures that the list is sorted:
public void testSort(List<GregorianCalendar> cals) {
Collections.sort(cals, /* custom comparator */);
/* assert that the list is sorted */
}Since junit-quickcheck ships with a default generator lists, we do not need to annotate the List type with a @From annotation. However, we must annotate the parameter of the generic list type with the @From annotation in order to signal that we want to use the CalendarGenerator to generate GregorianCalendar objects, like so: List<@From(CalendarGenerator.class) GregorianCalendar>. If we do not do this, the default ListGenerator will complain about not knowing how to generate elements of its list.
We can also configure the list generator to generate lists that are no longer than 100 elements by using the @Size(max=100) annotation on the List. @Size also takes a min, which is 0 by default. For more information on how to configure the default generators or how to add custom configuration annotations for your own generators, check out the junit-quickcheck tutorial on configuring generators. Here is what the updated CalendarTest.java looks like with this new test method.
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 com.pholser.junit.quickcheck.generator.*;
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);
}
@Fuzz
public void testSort(@Size(max=100) List<@From(CalendarGenerator.class) GregorianCalendar> cals) {
// Sort list of calendar objects
Collections.sort(cals, (c1, c2) -> {
int cmp;
cmp = Integer.compare(c1.get(YEAR), c2.get(YEAR));
if (cmp == 0) {
cmp = Integer.compare(c1.get(MONTH), c2.get(MONTH));
if (cmp == 0) {
cmp = Integer.compare(c1.get(DAY_OF_MONTH), c2.get(DAY_OF_MONTH));
if (cmp == 0) {
cmp = Integer.compare(c1.get(HOUR), c2.get(HOUR));
if (cmp == 0) {
cmp = Integer.compare(c1.get(MINUTE), c2.get(MINUTE));
if (cmp == 0) {
cmp = Integer.compare(c1.get(SECOND), c2.get(SECOND));
if (cmp == 0) {
cmp = Integer.compare(c1.get(MILLISECOND), c2.get(MILLISECOND));
}
}
}
}
}
}
return cmp;
});
// If they have an ordering, then the sort should succeed
for (int i = 1; i < cals.size(); i++) {
Calendar c1 = cals.get(i-1);
Calendar c2 = cals.get(i);
assumeFalse(c1.equals(c2)); // Assume that we have distinct dates
assertTrue(c1 + " < " + c2, c1.before(c2)); // Then c1 < c2
}
}
}TODO: Show how to fuzz testSort and reveal the bug in the comparator due to absence of time zone checks.
The source code examples in the wiki pages can be freely re-used under the same license as the rest of JQF.