Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support automatic 'swarm testing' for example selection #1637

Closed
Zac-HD opened this issue Oct 11, 2018 · 0 comments · Fixed by #2238
Closed

Support automatic 'swarm testing' for example selection #1637

Zac-HD opened this issue Oct 11, 2018 · 0 comments · Fixed by #2238
Labels
new-feature entirely novel capabilities or strategies

Comments

@Zac-HD
Copy link
Member

Zac-HD commented Oct 11, 2018

To paraphrase Swarm Testing (Groce et al, 2012),

Swarm testing is way to improve the diversity of generated test cases. Instead of potentially including all features in every test case, a large “swarm” of randomly generated configurations is used, each of which omits some features. ... First, some features actively prevent the system from executing interesting behaviors; e.g., pop calls may prevent an overflow bug from executing. Second, test features compete for space in each test, limiting the depth to which logic driven by features can be explored. Experimental results show that swarm testing increases coverage and can improve fault detection dramatically.

This is at minimum worth evaluating for Hypothesis - stateful testing would be a close match to the paper, while the benefits of swarm testing for data generation in general are less well explored but potentially substantial for e.g. Unicode text. The latter would require exposing data structure to the Conjecture engine as proposed in e.g. #1621.

Quoting @DRMacIver from #1401, which prompted this issue:

I've thought a bit about how to do shrinker friendly swarm testing under the current model. It's actually not too bad, though I haven't actually tried it so there's probably some annoying bits that I'm missing. The main points are:

  1. You need swarm flags to "shrink open" so that once the shrinker has run to completion, all flags are enabled. e.g. you could do this by generating a set of banned flags.
  2. You need to use rejection sampling rather than anything more clever.

Basically if you can then do characters().filter(character_class_is_enabled), then what happens during shrinking is follows:

  1. We delete all of the initial iterations of the loop. Now, as if by magic, we just happen to have picked only values that are enabled.
  2. The flags now shrink open, so we've left swarm mode and everything is now enabled.
  3. We can now shrink the values as normal characters.

[To ensure that choosing swarm flags works well with the shrinker:] ensure that every time we check whether a flag is enabled, if it's already been set we call data.write to record the flag in the data stream, so that if we delete the first use the subsequent uses turn into an initialisation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
new-feature entirely novel capabilities or strategies
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant