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

Keep recently-used constants in fuzzer state #241

Open
MattWindsor91 opened this issue Nov 6, 2020 · 2 comments
Open

Keep recently-used constants in fuzzer state #241

MattWindsor91 opened this issue Nov 6, 2020 · 2 comments
Labels
Type:Enhancement New feature or request

Comments

@MattWindsor91
Copy link
Collaborator

Per YARPgen paper: one of the things they do is store constants that they've used in fuzzer state, then randomly choose to replay those constants (and permutations thereof) when constructing expressions; this helps set up certain algebraic optimisations.

We might not be able to get the constants stored into the state while we're generating, owing to monad transformation fun (the quickcheck generator monad for expressions is outside of the state monad - don't you just wish I'd written OCaml or Haskell instead of Haskell-in-OCaml?), so we might need to traverse the generated expression to mine for constants.

Another fairly galaxy-brained idea might be to then use the fuzzer state constants as known-values, thereby causing a neat little crossover between the two and possibly setting up some serendipitous atomic-action optimisations.

@MattWindsor91 MattWindsor91 added the Type:Enhancement New feature or request label Nov 6, 2020
@MattWindsor91
Copy link
Collaborator Author

They also do the same for common subexpressions, though this might be difficult for us to do as some of our subexpressions are side-effectful.

@MattWindsor91
Copy link
Collaborator Author

We'd do this, I think, in the same pass in the fuzzer where we currently register dependencies. Either two traversals (one for constants, one for lvalues) or a fused custom traversal (ew).
If we did common subexpression generation, we'd probably need to tag expressions we want to save with metadata.

This, annoyingly, wouldn't let us reuse components in the same expression. We could always carry around a separate environment through the generator, but this would be kinda gross; as would using mutable state, given how pure most of the rest of the code is.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Type:Enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant