Idea: bounded cratering

[felix91gr]

So one issue with Crater, as mentioned in the Rustfest Barcelona talk, is that it will eventually have too many crates to test. I think we can keep the amount of testing bounded by using statistical tools, such as the ones described in this paper for efficient antialiasing in raytracing.

The idea I have in mind is as follows.

Crater with bounded precision

Preamble

• Let's assume that we've listed every crate in crates.io and can test any of them.
• Whether or not we first filter out malware and dead crates, I think is orthogonal to the algorithm's performance, as long as they aren't a large percentage of the crates.
• I think that having a thousand or so crates labelled as "remarkable", "in-use" or "important", would help us sample less randomly.

Idea for the Algorithm

Let's suppose there are N crates in total and that we test M crates at random from the list. How likely is it, then, that we find no regressions, given there are some? I believe we can study this question and come up with at least a bounded answer for it.

Our plan is to have that probability be as small as possible. Then, we pick a sample size M such that this probability is below some bound that we are satisfied with.

After running M tests, then:

• If no regressions have been found, we're alright.
• If some regressions have been found, then AWESOME! We've found some.

That's the basic idea.

Further Work?

There will be two unanswered questions here:

1. If we've found regressions, then how likely is it that by running K more tests we'll find more examples of the same regression?
2. In the same context, how likely is it that by running K more tests we'll find examples of a different regression?

My original idea was to answer (2), and thus have a Crater with adaptive precision, much like the raytracing paper I mentioned at the beginning. But I'm afraid that my statistical prowess only comes so far, and I can't currently think of a way to answer that and adaptively increase the number of tested crates based on how many regressions we find.

This is made harder as well because it's not immediately obvious when two failed tests are actually caused by the same regression and when they're actually caused by different ones. If such a question (are these the same regression?) could be answered, then I think an Adaptive Cratering is possible :)