Fuzzing Java with JQF

As we mentioned in our our last blog post, Tobias Ospelt of Pentagrid AG lately broke down the idea of Java fuzzing with JQF into simple steps and presented it at Swiss Cyber Storm in Bern, Switzerland and at the Black Alps conference in Yverdon-Les-Bain, Switzerland. The recordings of the talks are not online, yet.

We wanted to describe our work in written form as well, so you get a better idea of what can be done by fuzzing Java with JQF. It also allows you to copy and paste commands if you want to try it yourself. We also uploaded the talk slides as a pdf and the video with the JQF tutorial and Bouncycastle ASN.1 parser fuzzing run, which were shown during the talks.

Introduction to fuzzing

Fuzzing is a topic in the IT security world that was able to keep its mysteriousness. Every now and then a new fuzzer tool is created and every new fuzzer finds new bugs. Various organisations run fuzzing projects for various reasons and use CPU-years to find security issues. We believe it is still by far the most common way to find memory corruption security issues. The reason why fuzzing is so successful is simple: Fuzzing is the very abstract concept of feeding input in an automated, clever and partially random way to a target program and try to observe undesired behaviour. We are sure there are more exact definitions of fuzzing, but they do not matter for this blog post.

The fuzzing field is very big and a lot of people spend their entire professional lives with it. There are many fuzzers available online. If you want to learn about fuzzing in general, you can check out the fuzzing book for example.

AFL

The AFL fuzzer was first released in 2014 by Michal Zalewski when he was still at Google. There were many other fuzzers before it, but the combination of an easy way to instrument the code, ease of use in general and the usage of a genetic algorithm with a feedback loop that favours inputs that trigger new code paths revolutionized the field. If you want to know more about AFL and see the impressive bugs it found, you better head over to the original AFL project page. There are as well numerous forks of AFL, the one we currently recommend for runs is AFL++ that seems to be the best maintained one while still aiming for the same goals as the original AFL.

The thing is, AFL was written to be able to fuzz programs written in memory-unsafe languages, especially C and C++. It operates on files and feeds them to target programs. For this blog post it is important to know that AFL will usually put files that result in crashes of targeted programs into the crash directory. Hangs refer input files that took too long to process, as AFL sets a timeout limit on how long an input can take to process. This means a hang file might just take a little longer than AFL was willing to wait, but it might also mean you found an infinite loop or similar in a program. There is also the path metric which shows how many code paths in the target program were triggered by the input files that were tested so far. This is a very important metric to see if instrumentation works and the genetic algorithm can do its magic.

Fuzzing Java

The ideas of what kind of security issues can be found with Java fuzzing came up already before Pentagrid AG was founded (blog post in Tobias' blog: Java Bugs with and without Fuzzing – AFL-based Java fuzzers and the Java Security Manager). However, since then the fuzzers evolved. While most fuzzers that were evaluated back then didn't move much on until today, the JQF fuzzer developed by Rohan Padhye at University of Berkeley took a big leap forward. And that's why we only talk about JQF here.

JQF-AFL

JQF's capabilities were already really impressive when JQF-AFL came out about two years ago. It takes the AFL idea and implements the genetic algorithm approach for Java programs. The JQF-AFL core stayed similar and still uses the AFL binary for fuzzing and therefore shows the original AFL UI. However, as the original AFL UI will show the number of "crashes", this is somehow misleading for JQF-AFL, as they are only uncaught exceptions such as IndexOutOfBoundsException, which in C programs would typically lead to a memory corruption. The hangs and paths discovered mean the same as in the original AFL. More about JQF can be found on the JQF github project page and wiki.

The good side of JQF-AFL is that you can operate on file inputs, meaning you can start a fuzzing run of a PNG library with a PNG file. This also simplifies reproduction of the bugs, as the file is the reproducer. However, this also means JQF-AFL is limited, as it is necessary to write a test class that takes an InputStream as an input. You can see JQF-AFL in action (in cooperation with the AFL++ fork) in the video that shows how to run the JQF-AFL tutorial against Java ImageIO and then change it to fuzz GIF inputs rather than PNG inputs. The difference is that PNG bugs AFL-JQF found in ImageIO were already reported and fixed, whereas that's not the case for the GIF parser.

JQF-AFL allowed us to find various security issues in the past.

JQF-Zest

JQF-Zest is the newer approach that still does the genetic algorithm approach of AFL. Hangs and "crashes" (uncaught exceptions) as well assertion violations are all now named "unique failures" and "total paths" are are now in the "total coverage" metric as branches. Apart from that it behaves similarly to JQF-AFL. However, it implements a couple of improvements and is aiming at developers and people who would like to use fuzzing in their continuous integration. But it also kept its usefulness for security researchers. Developers will be more familiar with this JUnit test approach and might be able to reuse large parts of their Unit Tests for fuzzing.

JQF-Zest supports other Java types than InputStreams. It will automatically understand types such as int, String and Map because there are JUnit quickcheck generators for them. If a test case you have in mind takes an argument where no generator is available, you can still write your own generator. In the simple case of a single argument of InputStream the input file will correspond directly to the InputStream. However, in all other cases the mapping of an input file to Unit Test arguments is non-trivial and therefore you will later need the jqf-repro program to reproduce function arguments from input files. The good thing is that this file approach will still allow you to reuse past runs for subsequent runs with JQF-Zest to improve coverage. However, as the input and output files do not contain direct values but rather represent seed values for JUnit Quickcheck Generators, it is hard to reuse existing corpus data that wasn't produced by JQF-Zest.

When writing tests, the assume* methods can be used to abort a test early, if the (often randomly) generated inputs don't have a certain form. While on one hand this can be regarded as additional instrumentation and you have to take care that you don't prevent bugs from being found by assuming too much, it can be really powerful on the other hand. By adding an assume statement at the beginning of the Unit Test, JQF-Zest will try to pass the assume statements with its inputs and therefore make as many tests pass the assume statement as possible. This allows to target certain tests cases a little more focused than it would otherwise be possible. A good example is the PatriciaTrie example in the JQF repository:

1
2
3
4
5
6
7
8
@Fuzz
public void testCopy(Map<String, Integer> map, String key) {
    assumeTrue(map.containsKey(key));
    // Create new trie with input `map`
    Trie trie = new PatriciaTrie(map);
    // The key should exist in the trie as well
    assertTrue(trie.containsKey(key));
}

The test is requiring a Map and a String to be passed as arguments and the first assume statement will make sure that the String is in the Map (as a key). JQF-Zest will know this requirement and will try to comply with it. On the other hand, we will never be able to find issues in PatriciaTrie's containsKey method with this test that only occurs when a non-existing key is passed to PatriciaTrie's containsKey.

While JQF-Zest is available as a command line tool, it is also available as a maven plugin, meaning you don't have to install JQF yourself and maven will do it transparently for you. It allows easy continuous integration and you can choose to do a fuzzing run for a limited time by specifying the -Dtime=5m argument to the maven jqf-zest plugin.

In our experience JQF-Zest is also faster than JQF-AFL, although we haven't benchmarked it.

JQF-Zest tutorial

To show how easy it can be to run JQF-Zest if you have maven installed already, you can watch the Bouncycastle ASN.1 parser fuzzing run video. But here, let's recreate Rohan Padhye's PatriciaTrie bug and create a new folder and add the following two files:

    pom.xml
    src/test/java/examples/PatriciaTrieTest.java

Where pom.xml is:

    <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
      xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
        <modelVersion>4.0.0</modelVersion>

        <groupId>examples</groupId>
        <artifactId>zest-tutorial</artifactId>
        <version>1.0-SNAPSHOT</version>

        <properties>
        <maven.compiler.source>1.8</maven.compiler.source>
        <maven.compiler.target>1.8</maven.compiler.target>
        </properties>
        <dependencies>
            <!-- Apache commons with PatriciaTrie: we want to test this library -->
            <dependency>
                <groupId>org.apache.commons</groupId>
                <artifactId>commons-collections4</artifactId>
                <version>4.4</version>
            </dependency>

            <!-- JQF: test dependency for @Fuzz annotation -->
            <dependency>
                <groupId>edu.berkeley.cs.jqf</groupId>
                <artifactId>jqf-fuzz</artifactId>
                <!-- confirm the latest version at: https://mvnrepository.com/artifact/edu.berkeley.cs.jqf -->
                <version>1.3</version>
                <scope>test</scope>
            </dependency>

            <!-- JUnit-QuickCheck: API to write generators -->
            <dependency>
                <groupId>com.pholser</groupId>
                <artifactId>junit-quickcheck-generators</artifactId>
                <version>0.9</version>
                <scope>test</scope>
            </dependency>

        </dependencies>

        <build>
            <plugins>
                <!-- The JQF plugin, for invoking the command `mvn jqf:fuzz` -->
                <plugin>
                    <groupId>edu.berkeley.cs.jqf</groupId>
                    <artifactId>jqf-maven-plugin</artifactId>
                    <!-- confirm the latest version at: https://mvnrepository.com/artifact/edu.berkeley.cs.jqf -->
                    <version>1.3</version>
                </plugin>
            </plugins>
        </build>
    </project>

And PatriciaTrieTest.java is:

    package examples;

    import java.util.Map;
    import org.apache.commons.collections4.trie.PatriciaTrie;

    import edu.berkeley.cs.jqf.fuzz.Fuzz;
    import edu.berkeley.cs.jqf.fuzz.JQF;
    import org.junit.runner.RunWith;

    import static org.junit.Assert.assertTrue;
    import static org.junit.Assume.assumeTrue;

    /**
     * @author Rohan Padhye
     * changed example by Tobias Ospelt
     */
    @RunWith(JQF.class)
    public class PatriciaTrieTest {

        @Fuzz
        public void testCopy(Map<String, Integer> map, String key) {
            assumeTrue(!key.isEmpty());
            assumeTrue(map.containsKey(key));
            // Create new trie with input `map`
            PatriciaTrie trie = new PatriciaTrie(map);
            // The key should exist in the trie as well
            assertTrue(trie.containsKey(key));
        }

    }

Inside your folder run the following commands:

    mvn test-compile
    mvn jqf:fuzz -Dclass=examples.PatriciaTrieTest -Dmethod=testCopy -Dtime=1m

Once the fuzzing is done (1 minute), you should have one unique failure. If you get zero failures you were unlucky, remove the "target" directory, compile and run the fuzzer again. If you have more than one unique failure, you found a new bug, which would be interesting. You can run the following command to reproduce the found failure, however:

    mvn jqf:repro -Dclass=examples.PatriciaTrieTest -Dmethod=testCopy -Dinput=target/fuzz-results/examples.PatriciaTrieTest/testCopy/failures/id_000000 -DprintArgs

Unfortunately, the command line parameter -DprintArgs won't help you much with reproducing the bug in this case, as printing non-printable characters is definitely involved. We therefore need to print the inputs created by JQF somehow differently to reproduce the issue. You can write another file in src/test/java/examples/PatriciaTriePrint.java with the following content, which adds some debug print statements that output UTF-16 (Java's default encoding) hexadecimal:

    package examples;

    import java.util.Map;
    import org.apache.commons.collections4.trie.PatriciaTrie;

    import edu.berkeley.cs.jqf.fuzz.Fuzz;
    import edu.berkeley.cs.jqf.fuzz.JQF;
    import org.junit.runner.RunWith;

    import static org.junit.Assert.assertTrue;
    import static org.junit.Assume.assumeTrue;

    /**
     * @author Rohan Padhye
     * changed example by Tobias Ospelt
     */
    @RunWith(JQF.class)
    public class PatriciaTriePrint {

        @Fuzz
        public void testCopy(Map<String, Integer> map, String key) {
            //The easiest way to reproduce:
            for (String mapkey : map.keySet()) {
                System.out.println("Map key in UTF-16 hexadecimal: " + stringToUTF16Hex(mapkey));
            }
            System.out.println("Key in UTF-16 hexadecimal: " + stringToUTF16Hex(key));
            assumeTrue(!key.isEmpty());
            assumeTrue(map.containsKey(key));
            // Create new trie with input `map`
            PatriciaTrie trie = new PatriciaTrie(map);
            // The key should exist in the trie as well
            assertTrue(trie.containsKey(key));
        }

        static String stringToUTF16Hex(String string) {
            StringBuilder buf = new StringBuilder(200);
            for (char ch: string.toCharArray()) {
                if (buf.length() > 0)
                    buf.append(' ');
                buf.append(String.format("%04x", (int) ch));
            }
            return buf.toString();
        }
    }

Then run it:

    mvn test-compile
    mvn jqf:repro -Dclass=examples.PatriciaTriePrint -Dmethod=testCopy -Dinput=target/fuzz-results/examples.PatriciaTrieTest/testCopy/failures/id_000000

This will hopefully print something like:

    [...]
    Map key in UTF-16 hexadecimal: d98c dd95 d93d dc62 dbca dda6 da7d dec9 b525 d93f dd5e db81 dd61 dbf3 df55 d9e4 dd3d d908 dc9e
    Map key in UTF-16 hexadecimal: 6629 6255 8dfc 0000 0000 20a5 9306 2e65 d44f 601a b0cc 75a6 77c3 22e5 6210 0f1d 8f90 c418
    Map key in UTF-16 hexadecimal: da06 ddf6
    Map key in UTF-16 hexadecimal: 216c 2a08
    Map key in UTF-16 hexadecimal: 0000
    Map key in UTF-16 hexadecimal:
    Map key in UTF-16 hexadecimal: d806 df87 b2a7 0000 d9a3 df0f db96 dc98 dbea dc5c d91b dec6 001a da79 dc7c db52 de03 d9a5 de59 db75 dd1a d85e dd12
    Map key in UTF-16 hexadecimal: 8e82 6b00 9aeb 9664 ba48 935e 0000 0000
    Key in UTF-16 hexadecimal: 0000
    [...]
    java.lang.AssertionError
    [...]
            at examples.PatriciaTriePrint.testCopy(PatriciaTriePrint.java)
    [...]

This means that something is not working correctly when it comes to null characters in strings just as described in the bug report by Rohan. If you check the PatriciaTrieTest again, you will see that although a null character is present in map.keySet(), the containsKey function returns false, because the assert statement is violated.

If you liked this tutorial and want to do more with JQF, we recommend following the other tutorials of JQF.

Bug classes

As already said, a broader picture of what can be found with fuzzing in the Java world can be found in another blog post. But let's focus on JQF here. So far JQF was able to find bugs in the area of the following bug classes:

  • Exception issues potentially affecting availability, for example ClassCastException or IndexOutOfBoundsException.

  • Denial of Service issues, for example infinite loops in code and out of memory conditions (OutOfMemoryError).

  • Logic bugs, if the correct assert statements are written such as for the above PatriciaTrie example.

We assume the following bug classes could be found as well by using JQF:

  • Any security issues that would lead to an uncaught exception, for example an SQLSyntaxErrorException for SQL injections. However, this also means that the exceptions is not allowed to be caught before it reaches JQF.

  • Any security issues that can be expressed by assert statements, such as differential fuzzing for cryptographic libraries.

  • Any security issues that can be prohibited by the Java Security Policy Manager, such as Server-Side Request Forgery (SSRF) by preventing network access and subsequently this would throw an Exception when network access is attempted.

In the end, a lot of different bug classes can be found as long as the correct assert statement is created, but it is more a question of how much effort it takes.

Outlook

Knowing JQF-Zest is useful for creating inputs for Unit Tests that improve code coverage, it would be interesting to run JQF-Zest on already present Unit Tests. In this regard it would for example be interesting to see how the Unit Tests in project Wycheproof could be changed to accept JQF-Zest created inputs. While a lot of the Unit Tests of Wycheproof use very precisely engineered problematic inputs, for us it would be interesting to see what happens when JQF-Zest mutates them. There are several obstacles in the way until we could do that, first of all that the Unit Tests in Wycheproof are using hard coded inputs rather than passing arguments to a Unit Test function, so this would need to be refactored. However, we also hit the other limitation of JQF-Zest, as it is currently not possible to provide meaningful arguments as a starting point (corpus) for JQF-Zest. As discussed before, that's because input files represent seed values for JUnit Quickcheck generators.

Another path that is still unexplored is fuzzing with JQF-Zest when the Java Security Policy Manager is in place.