[rb-general] auto-analyzing indeterminism

Ximin Luo infinity0 at debian.org
Tue Jul 18 15:00:00 CEST 2017

Bernhard M. Wiedemann:
> Hi,
> during the r-b summit in Berlin I heard of an idea to automatically
> 'bisect' sources of indeterminism to make it easier to fix software.
> Yesterday (when I could not sleep), I did a quick proof of that
> concept in 60 lines of code in
> https://github.com/bmwiedemann/reproducibleopensuse/blob/devel/autoclass
> ify
> This will get further refined, but already seems useful enough so that
> I'm currently running it with the ~500 smaller unreproducible packages
> in openSUSE.
> [..]

Very nice! Could you explain a bit how your "bisect" algorithm works? I'm not very good at reading perl..

Does "0 0 1 0 1 0" mean the package was unreproducible with either

- only the third variation, or
- only the fifth variation,

or some other meaning? If I guessed correctly, it would also be good do one final test with:

- the first, second, fourth *and* sixth variations

this would confirm that varying all of these, still retains reproducibility. (It's unlikely but possible that varying two things would cause unreproducibility, even if varying each of them in isolation would still appear reproducible.)

The corresponding reprotest bug report is here https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=850284 and the blocker for me so far, was that we can't really do a "bisection" algorithm since the variations can't be ordered linearly.

So take for example a git bisect:

1 <- 2 <- 3 <- 4 <- 5

when testing commit 5, we are actually testing the subset {1,2,3,4,5} etc. So these form a linear order and we can do an efficient O(log) bisect. However with reproducibility variations, we could take arbitrary subsets of the whole set of variations.

So I was leaning towards just testing {1}, {2}, {3}, ... etc each individually. I'm not sure if that's what you implemented though.


GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE

More information about the rb-general mailing list