library for lazy generators with observable demand
I want to mutate an input in some way that the new input runs more of the program being tested.
Could I run gradient descent on random test inputs?
To be able to do that, I would need some way to generate an input and then find a "nearby" input to exercise parts of the program that haven't been evaluated yet.
Trynocular is an attempt to define "nearby" as well as a framework for detecting which parts of the input were used by the program under test.
You can represent any value by a binary tree of the choices you made to reach that value.
The fundamental idea here is that a rerunGenerator constructs values from
GenKeys in a strictness-preserving way. That is to say that partially
forcing the result of rerunGenerator will force the nodes of the GenKey
structure only when corresponding parts of the resulting value are forced.
To test with a Generator, one would:
- Initialize probabilities to 0.5 for each Choice node of the generator.
- Initialize the coverage expectation to some initial value.
- Loop as follows:
- Generate a random test case that differs from past test cases in some portion that was forced by that test case.
- Run the test and see if it fails.
- Observe the demand on the key, and the percent of additional coverage generated by the test.
- Compare the observed additional coverage to the expectation. a. If the observed additional coverage is less than the expectation, update probabilities of each Choice node that was forced in the key to decrease their probability. b. If the observed additional coverage is greater than the expectation, update probabilities of each Choice node that was forced in the key to increase their probability.
- Update the coverage expectation using the observed additional coverage, using an exponentially weighted moving average. That is, new coverage expectation = alpha * old coverage expectation + (1 - alpha) * observed new coverage.
- Repeat until some termination condition is satisfied.