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.

[jlink]

@vlsi Thanks for the suggestion. Guided generation looks interesting. Can you give a concrete example how you imagine the integration of ZEST with jqwik could look like for the user?

As for the integration, it would most probably require a new kind of generation mode and a way to inject the random stream and the guidance. My intuition says it should be possible but it will require deeper understanding on my side how Zest and JQF work. If you can convince me with good examples from user perspective I'm absolutely willing to tackle it :-)

[vlsi]

Can you give a concrete example how you imagine the integration of ZEST with jqwik could look like for the user?

Let us take Apache Calcite as an example.
It is SQL optimization and execution engine.

SQL has expressions (e.g. foo is null and foo >0), and, as you might guess, Calcite uses those expressions all over the place.

Of course, there's an implementation of the expression optimizer.
Here's a test for that: https://github.com/apache/calcite/blob/3acb30875525e029be96726a357ee9950cce3310/core/src/test/java/org/apache/calcite/rex/RexProgramTest.java#L1734-L1738
It verifies that NOT COALESCE(null, true) is simplified to false.

So the optimizer has properties to be verified. For instance, the optimizer must not throw exceptions while doing its optimization.

The current jqwik / junit-quickcheck approach would be to generate expression trees at random, and pass them to the optimizer.
However, ZEST allows to pick input tress better, so it skews input generation in such a way, so it increases the probability to trigger a bug.

This case for the end user could look as follows:

public class RexFuzzerTest {
  private RexSimplify rexOptimizer;

  public JqfFuzzerTest() {
    rexOptimizer = null; // setup the optimizer appropriately
  }

  @Property
  // or @Property(coverageGuidance=true)
  // or @Property @Guidance(type=ZEST) @ZestParams(include="org.apache.calcite.*")
  public void hello(@ForAll RexNode value) {
    rexOptimizer.simplify(value); // we check that optimizer does not throw exceptions 
  }
}

Note: I am not sure regarding the way guidance should be configured. At the end of the day, I don't think you can (easily) add a javaagent via @Annotation :)

The user would have to enable JQF's bytecode instrumentation somehow. It is available as a custom classloader or as a javaagent.
It would be fine to leave javaagent configuration to the build systems. I think it would be more-or-less manageable.

Note: currently JQF is integrated with junit-quickcheck, and JQF itself has only one annotation property

Does that answer your question?

In other words, from an end-user perspective, the very basic case is the same as with simple jqwik.

What ZEST does, it analyzes the execution outcomes, and it provides you with a random bytes, so the next randomized inputs would explore uncovered branches better.

If you ask for more advanced cases then it would be nice to be able to see extra statistics from ZEST itself. For instance, it would be nice to see coverage% in the real-time, so the user can see if the fuzzer is healthy or not.

it will require deeper understanding on my side how Zest and JQF work

You might want to check Guidance interface. It is quite small.

https://github.com/rohanpadhye/jqf/blob/06376192315a80309d6bd298b7517ef50f5bdb16/fuzz/src/main/java/edu/berkeley/cs/jqf/fuzz/guidance/Guidance.java#L53-L72

[jlink]

@vlsi As for your second question:

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

I'm probably never going to do that. Here's my argument:

Jupiter, the default engine, is a jack-of-all-trades, which in turn means that it's not well suited for special needs. Jupiter exentsion points have been designed to be composable, that's e.g. the reason why JUnit4's model of wrapping the execution of tests and suites was given up and replaced by before and after hooks. Nevertheless, generic composability is difficult to get right, and it requires to stick with some limitations. Jupiter's lifecycle is not really well suited for running an indeterminate number of tests scheduled by the feedback coming from previous test runs. Dynamic test generation allows that to some degree but then you will miss out on shrinking, statistics reporting and a few other subtleties that make developer experience of jqwik the way it is now - and as I like it.

That said, it would probably be possible to come up with a jqwik extension for Jupiter that could inject parameters, run the individual tries as dynamic tests and even do standard shrinking. But it would

• Not offer the same developer experience as for the lifecycle (rerun with previous failure, run failing props first, switch platform reporting on/off, etc.)
• Be (much) harder to integrate in Jupiter's lifecycle and make it usable/composable with most other extensions. Just think of the effect that other injected parameters can have on the predictability for shrinking results. And if you take composability away then a Jupiter integration has IMO no additional benefit.

Junit platform test engines - as jqwik is an example - have been introduced to fill the hole that Jupiter extensions leave empty: Different syntax to specify tests, different test lifecycle, difficulties with composability and side effects. BTW, there's a reason that junit-quickcheck has its own JUnit4 runner and is not just a set of JUnit 4 rules: Runners in JUnit 4 are (to some degree) what engines are in JUnit 5; they are not composable.

As you mention with @Disabled the engine approach has one major drawback: some functionality that could be considered cross-engine must be implemented multiple times and might function inconsistently/differently from engine to engine. Since I am still - despite my exit from the JUnit 5 team - in good contact with those folks we've always been looking for opportunities to extract common functionality from individual engines into the platform. Sometimes we find a reasonable solution (e.g. testing kit, annotation discovery), sometimes we don't.

[jlink]

The user would have to enable JQF's bytecode instrumentation somehow. It is available as a custom classloader or as a javaagent.
It would be fine to leave javaagent configuration to the build systems. I think it would be more-or-less manageable.

javaagent configuration is mostly done by the IDE or the build system, so this should be doable.

I still don't get how providing random bytes can direct the generation of certain values since the values generated from certain random bytes cannot really be predicted without knowing the implementation of all generators involved - and that can be many. What do I miss or fail to understand?

[vlsi]

I still don't get how providing random bytes can direct the generation of certain values since the values generated from certain random bytes cannot really be predicted without knowing the implementation of all generators involved - and that can be many

I guess it is described in zest paper (see 3.1 Parametric Generators)

direct

AFAIU, the idea is pretty much the same as the mutation and selection in a typical genetic optimizer directs the population to the desired goal.
In the same way, Zest mutates the input sequence, and it measures the resulting coverage.

Genetic optimizers do not need to know the implementation of the underlying systems.

cannot really be predicted without knowing the implementation of all generators involved

It does not need to predict the output.
For instance, it might learn that mutating bits 0..32 is very bad for coverage (==the first 32bits are magic sequence), so it might focus on mutating other bits. It does not require to know the implementation of the generators as long as they are predictable given the source of randomness.

[luvarqpp]

I would like to see annotation in line with existing approach. For example:

@Property(generation = GenerationMode.ZEST_DRIVEN, shrinking = ShrinkingMode.FULL)
@Report(Reporting.COVERAGE)
void arbitraryUserIsAlwaysValidForSerDes(@ForAll("arbitraryUser") UserForTests arbitraryUser) {
}

PS: I like proposed idea. Does it mean that tuning properties to coverage various cases would not be needed generally? (genetics programming can be good in many cases)

[vlsi]

Does it mean that tuning properties to coverage various cases would not be needed generally?

Frankly speaking, I have no idea at this point. In general, it looks to be useful even without tuning knobs.
ZestGuidance itself has multiple hard-coded parameters that might need to be configurable in the future.
I want to try the thing with real code, and then we could see what needs to be tuned.

The use cases I have in mind are Apache Calcite (RexNode fuzzing or even full SQL fuzzing), and PostgreSQL JDBC driver (e.g. JDBC API fuzzing).

PS. It would probably be fun to have Arbitrary implementation based on JavaCC grammars.

[luvarqpp]

Does it mean that tuning properties to coverage various cases would not be needed generally?

Frankly speaking, I have no idea at this point. In general, it looks to be useful even without tuning knobs.
ZestGuidance itself has multiple hard-coded parameters that might need to be configurable in the future.
I want to try the thing with real code, and then we could see what needs to be tuned.

Thanks for info. I can use it (when integrated with jqwik) as soon as there is something to test. I have spring-data-rest real world project (in alpha version through) which will reach its customers this year and testing is one of our priority.

The use cases I have in mind are Apache Calcite (RexNode fuzzing or even full SQL fuzzing), and PostgreSQL JDBC driver (e.g. JDBC API fuzzing).

To find bugs more easily, you can try also "reactive jdbc driver". See its postgresql client code for example: https://github.com/r2dbc/r2dbc-postgresql

[vlsi]

I have spring-data-rest real world project (in alpha version through) which will reach its customers this year and testing is one of our priority.

I'm not sure the current Zest/JQF supports multi-threaded applications :-/

[luvarqpp]

I have spring-data-rest real world project (in alpha version through) which will reach its customers this year and testing is one of our priority.

I'm not sure the current Zest/JQF supports multi-threaded applications :-/

Jop, you are right, through using it when business logic is in main thread only, would be OK. See rohanpadhye/JQF#41. On the other side, this is not my case. In spring-data-rest there is some tomcat in main thread (perhaps), or main thread is my web test client (http client, which is sending http requests from jqwik test).

[jlink]

@vlsi I looked at the examples coming with JQF. They don't seem to define any special case guidance which confuses me. Take this simple example:

@Fuzz
public void insert(int @Size(min=100, max=100)[] elements) {
     BinaryTree b = new BinaryTree();
     for (int e : elements) {
         b.insert(e);
     }
}

What difference in generated data would you expect - if any - compared to

@Property
public void insert(int @Size(min=100, max=100)[] elements) {
     BinaryTree b = new BinaryTree();
     for (int e : elements) {
         b.insert(e);
     }
}

running on Vanilla junit-quickcheck?

[vlsi]

I looked at the examples coming with JQF. They don't seem to define any special case guidance which confuses me

PS. We can have a small conversation (e.g. Zoom, or https://meet.jit.si/) so screen sharing+voice might be more productive.

JQF implements its own JUnit runner: https://github.com/rohanpadhye/jqf/blob/f0979677984bf61e505104fcbda27b442cc561a1/fuzz/src/main/java/edu/berkeley/cs/jqf/fuzz/JQF.java#L50

which uses FuzzStatement for test execution: https://github.com/rohanpadhye/jqf/blob/f0979677984bf61e505104fcbda27b442cc561a1/fuzz/src/main/java/edu/berkeley/cs/jqf/fuzz/JQF.java#L87

FuzzStatement itself asks Guidance for the next input data to try (==next random bytes): https://github.com/rohanpadhye/jqf/blob/48d3b663ad68a7b615c2a8b9716da0ca8b6ef4e6/fuzz/src/main/java/edu/berkeley/cs/jqf/fuzz/junit/quickcheck/FuzzStatement.java#L136-L137

And it calls generators with the given random (it is the place where usual generators are made to be guided ones): https://github.com/rohanpadhye/jqf/blob/48d3b663ad68a7b615c2a8b9716da0ca8b6ef4e6/fuzz/src/main/java/edu/berkeley/cs/jqf/fuzz/junit/quickcheck/FuzzStatement.java#L139-L141

Then it informs Guidance on the actual test outcome (pass/fail/assumption violation/etc): https://github.com/rohanpadhye/jqf/blob/48d3b663ad68a7b615c2a8b9716da0ca8b6ef4e6/fuzz/src/main/java/edu/berkeley/cs/jqf/fuzz/junit/quickcheck/FuzzStatement.java#L194

[vlsi]

Note: ZestGuidance is instantiated and passed via static field in GuidedFuzzing
I don't quite like that approach, but it works (tm).

Frankly speaking, the current Zest / JQF code seems to be focused to be used as public static void main application rather than to be used as a library.
For instance, ZestGuidance is instantiated in ZestCli

Is it what you are looking for?

[jlink]

PS. We can have a small conversation (e.g. Zoom, or https://meet.jit.si/) so screen sharing+voice might be more productive.

Would be cool. When do you have time this week?