Model based/stateful testing with .Repeat does not test sufficiently different distributions of each operation

[danwt]

Because of this it is necessary to have bogus logic to implement it yourself

[flyingmutant]

Can you expand a bit, what kind of distribution do you want to achieve?

[danwt]

Hi thanks for getting back so quick

So for example, given operations A,B, a program bug may be exposed only with a sequence of operations

AAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAA

or other such 'skewed' distributions

Obviously it's not easy to guess the distribution that would find the bug beforehand, that's the goal of the library in this case.

So I would suppose a naive approach, but one that might be useful in practice, is to have distributions such as

A,B,C
0.33,0.33,0.33
1,0,0
0,1,0
0,0,1
0.5,0.5,0
0.5,0,0.5
0,0.5,0.5
0.99,0.01,0.01
0.01,0.99,0.01
0.01,0.01,0.99
...
etc

I appreciate this is not an easy problem, per say

[flyingmutant]

Yep, that's definitely something I would like to add/improve. Are you aware of any formalization that can be used as the basis for implementation instead of doing it completely ad-hoc?

The only paper on the subject that I remember right now is this one, but I'd say the method used in it is rather ad-hoc.

[danwt]

I'm not sure to be honest it's been a while since I was looking into the area. I recall some papers on doing a series of flips on operations. There is also the whole field of model checking to draw from. A good search term is 'test case diversity'

[evanmcc]

I started a patch around this based on the alias method for weighted distributions described here: https://www.keithschwarz.com/darts-dice-coins/

Adding something like this would allow both specifying weights (which is common in a lot of other stateful pbt libraries) as well generating distributions at the start of the run so it isn't always 1/n per step.

I ran into trouble though trying to tie in the weighting code here to the bitstream object, though. I suspect that I'd need to vendor that library and rewrite .Next() to take a bitstream pointer, but I wasn't sure you'd want to carry the extra code.

Would this be of interest?

[flyingmutant]

Just for the reference: I believe that the proper way to solve this problem is an approach I've used (invented?) for a Rust property-based library I've written: https://github.com/flyingmutant/chaos_theory. I call it "universal swarm testing". The core of the idea is that we use a stateless permutation + subset generator for all indexed choice, and re-seed it when we feel like we are getting stuck. It is conceptually simple, fast and works great, but right now I don't have the time to refactor rapid internals to use it.