Support coverage-guided generation

[vlsi]

Hi,

There's https://github.com/rohanpadhye/jqf by @rohanpadhye The idea here is that a randomized-input generation can be guided based on the feedback from the test execution.

For instance, guidance can observe code coverage and it could attempt to produce inputs that explore uncovered branches. Another example might be to measure the performance (e.g. performance counters or just heap allocation) and attempt to produce an input that triggers performance issues.

Relevant information

https://www.fuzzingbook.org/html/MutationFuzzer.html#Guiding-by-Coverage (and other parts of the book)

Suggested Solution

If we take Zest (which is coverage-guided fuzzer), then ZestGuidance provides an input stream that can be considered as the source of randomness: https://github.com/rohanpadhye/jqf/blob/48d3b663ad68a7b615c2a8b9716da0ca8b6ef4e6/fuzz/src/main/java/edu/berkeley/cs/jqf/fuzz/junit/quickcheck/FuzzStatement.java#L136

As far as I can see, the current RandomizedShrinkablesGenerator never exposes Random instance, so there's no way to take a random stream input from the guidance and pass it to RandomizedShrinkablesGenerator (see https://github.com/jlink/jqwik/blob/2517d6d8cd612137fcff730a9114169260fad4bf/engine/src/main/java/net/jqwik/engine/execution/CheckedProperty.java#L155 )

As far as I understand, jqwik does not provide a way to plug guided fuzzing: https://github.com/jlink/jqwik/blob/5632ef8ca3d51ff083380257fb0b2b9bd7383920/engine/src/main/java/net/jqwik/engine/properties/GenericProperty.java#L38

So I would like to hear your opinion on the way to integrate guided fuzzing. It looks like it would be nice to be able to use pluggable guidances, so what do you think if the random in question was taken from a Guidance instance and the guidance get notified on the test outcomes?

PS. I wonder if jqwilk engine can be integrated with JUnit5's default one.

I know JUnit5's default engine does not suit very well for property-based tests, however, can you please clarify what are the major issues that prevent the use of JUnit5 engine for jqwik?

For instance, JUnit5 (e.g. TestTemplate) keeps all the test outcomes (which results in OOM), however, in property-based tests we don't need that, and we need to just count the number of passed tests. On the other hand, it looks like that can be improved in JUnit (e.g. by adding @AggregateSuccessfulExecutionsAsCount or something like that).

I just thought that the default JUnit5 engine would make the tests easier to write as the documentation would be consolidated. For instance, there's net.jqwik.api.Disabled, and there's org.junit.jupiter.api.Disabled which are more or less the same thing. It is unfortunate that regular annotations do not work with jqwik. Of course, it would be illegal to mix @jupiter.api.Test with @Property, however, that looks like a corner case that can be validated.

[vlsi]

Stream in Java is always lazy so it's not possible (or at least not straightforward) to consume one integer after the other until no longer needed

There's

java.util.stream.Stream#iterator.

IntStream is specialized as PrimitiveIterator.OfInt iterator();, so it is more-or-less the same as regular iterator, yet is has no boxing overhead. So IntStream seems to convey the proper semantics, it has close(), and it is easy to instantiate in the client code (e.g. Arrays.stream(int[]))

---

Just in case: Stream#spliterator produces a Spliterator which can be processed item by item via Spliterator#tryAdvance. In other words, Stream should be fine for item-by-item pull processing.

[jlink]

That's what I meant with "not straightforward". I don't think Stream should be used that way. It's against what I'd call the assumed lazyness of a stream.

I'll go with either Iterator<Integer> or a specialized type like ByteStream as described above.

[vlsi]

I don't think it is worth spending time on the discussion like this, however, I truly do not see why assumed lazyness prevents the use of IntStream as an API.

Stream does support the notion of java.util.Spliterator#ORDERED. Java 1.8 has even java.util.Random#ints() that returns java.util.stream.IntStream. Spliterator has tryAdvance which is designed to consume elements one by one.

IntSteram is easy to instantiate (e.g. Arrays.stream(int[]), Random#ints(), IntStream.of() and so on), while specialized type would couple Guidance implementation to jqwik APIs.

Iterator<Integer> would involve box-unbox of the integers, and it might easily impact performance. There's java.util.PrimitiveIterator.OfInt interface which is iterator over ints without boxing, however, I still think IntStream makes more sense there.

In other words, Java architects were more or less fine with using IntStream for the stream of ints.

I don't see why it does not fit for jqwik.

[jlink]

I don't think it is worth spending time on the discussion like this

Absolutely not worth it. We just don't agree here.

[vlsi]

Just in case:

val iter = IntStream.of(1, 2, 3, 4).iterator()
while (iter.hasNext()) {
    println(iter.nextInt())
}

^^^ the above is straightforward stream processing to me

[jlink]

It's creating an iterator again. And creation would probably have to go through IntStream.iterate() or IntStream.generate(). Let it be.

[jlink]

@vlsi Now that we must accept that we won't agree on every design aspect, do you still consider it worthwhile going forward with a proof of concept?

[jlink]

This is my current best bet:

interface GenerationGuidance {

    /**
     * Returns a reference to a source that will deliver
     * integer values to feed the pseudo-random number generator for the next try.
     *
     * @throws IllegalStateException if there is no next try available
     */
    TryGenerationSource nextTry();

    /**
     * Decide if another sample can be tried.
     * <p>
     * Method could potentially block to wait for guiding algorithm to finish.
     * <p>
     * If it returns false generation will be finished.
     */
    boolean hasNextTry();

    /**
     * Handles the result of a property try.
     */
    void handleResult(TryExecutionResult result);

}

interface TryExecutionResult {
    enum Status {
        SATISFIED,
        FALSIFIED,
        INVALID
    }

    Status status();

    Optional<Throwable> throwable();
}

/**
 * Source for providing integer values.
 */
interface TryGenerationSource extends AutoCloseable {
    int next();

    boolean hasNext();

    /**
     * Will be called when no more values are necessary for
     * generating the parameters of the current try.
     */
    @Override
    default void close() {
        // Optional
    }
}

[vlsi]

This is my current best bet:

LGTM

[jlink]

I wonder if TryGenerationSource could be simplified to

/**
 * Source for providing integer values.
 */
interface TryGenerationSource extends AutoCloseable {

    /** There must always be another value to feed generation */
    int more();

    /**
     * Will be called when no more values are necessary for
     * generating the parameters of the current try.
     */
    @Override
    default void close() {
        // Optional
    }
}

[vlsi]

I wonder if TryGenerationSource could be simplified to

I guess both of them are OK provided there's the following factory method :)

interface TryGenerationSource extends AutoCloseable {
    static TryGenerationSource of(IntStream source);
}

[vlsi]

However, I agree the random generator should better be treated as an infinite source. I don't think the test engine can handle out of randomness exception.

[jlink]

@vlsi Are you still interested in the feature and would have time to experiment with it? If so I'll move (a branch with) the basic mechanism towards the top of my todo list.

[vlsi]

@jlink , that's on my list, however, I don't think I would be able to pick it in the nearest month :-/

[jlink]

@vlsi OK. Then I'll leave it in my plans for the summer.

[jlink]

This paper propagates coverage guided property testing as a more effective variant of what AFL does: https://www.cs.umd.edu/~mwh/papers/fuzzchick.pdf Might be interesting to consider.

[fduminy]

any news on that issue ?

[jlink]

Implementing the basic hook in jqwik is probably possible with reasonable effort. But someone - not me since I’m short on time - would then have to use it for adding AFL-like mutation and coverage it.

Any volunteers? I might push it up in the prioritised todo list.

[vlsi]

While I do not have immediate plans to implement coverage-guided generation yet, however, the following looks useful and relevant: https://tiemoko.com/blog/diff-fuzz/

[vlsi]

Here's an article that suggests to split random generators that affect structure of the input from the ones that affect data.

https://twitter.com/cestlemieux/status/1524806183466541056

[adam-waldenberg]

Any more thoughts on this? I think this would have been very cool in JQWik. Reading the papers and the resources the Zest algorithm sounds particularly interesting.

I'm just wondering what the best way to get something like this implemented is ? It requires instrumentation of the classes being tested, so coverage can actually be tracked. For reference I'm attaching a picture here of the Zest algo.

(Source: https://rohan.padhye.org/files/zest-issta19.pdf)

This might be a fun exercise to implement at some point.... We could probably rip the instrumentation project from JQF and then implement the above logic in a hook that intercepts each try.

Some questions come up though,

How would we deal with @Provide methods? Or even @Provide methods with nested arbitraries...? How would we deal with the generated sets - we don't want to generate series of values that we never get to use.

[jlink]

There's already a Java PBT lib that supports coverage-guided generation: https://github.com/quicktheories/QuickTheories. QT also shows that instrumentation through an agent is feasible. As for plans to implement it, it will probably have to wait for jqwik 2, which I want to start working on this year.

I don't understand the point about @Provide methods - which are not different than any other arbitrary by the way. Generation always happens one by one, i.e. only if another set of values is needed; there's no eager generation of values. But I propbably missed your point.

[vlsi]

I guess https://github.com/jqwik-team/jqwik/pull/424 might be relevant as it would be hard to introduce "coverage-guided" as long as jqwik uses java.util.Random.

[adam-waldenberg]

@jlink Cool. Last time I played with it, it didn't have this feature.

As for @Provide, I have noticed that a provider will be called quite a few times before a property is even executed the first time - with many combinations it can take quite a while. I guess I falsely assumed this was some kind of eager step it was doing. There has not been any point for me to take a closer look at it yet.