c4-project / c4f

The C4 Concurrent C Fuzzer
MIT License
14 stars 1 forks source link

Keep recently-used constants in fuzzer state #241

Open MattWindsor91 opened 3 years ago

MattWindsor91 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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.