What is the theory behind testing fixes for intermittent bugs?

Question

I ask this question because I deal with alot of intermittent bugs and want to be able to answer the question "Can I be at least 95% sure that my changes to the code fix the bug?". I've got some ideas on how one could formalize the problem, but I'm guessing that someone else has done this.

I'm particularly interested in theory where we do NOT already know a value of $p$ - the probability that a bug will hit. This means we'll likely have to assume some distribution on $p$.

It seems like this should be a known thing, especially within TDD. Some problems are just so hard that we have to rely on testing results. Thanks for any direction you can give me.

Answer 1

You juggle with "probabilities" without defining any. There are two different questions here.

For practical programs, can I use random testing to establish that any given execution has close to 100% success probability?

Not in the strict sense, no. Even if input spaces are finite, they are typically huge. Without further information, you'd have to test a lot of inputs (and/or contexts), which is not feasible. As in, solving most NP-complete problems is faster.

You could try to perform statistical testing, that is get some bound on the error for some statistical significance -- but that would assume that you have a model for the error distribution. Which I would be surprised to hear if you had. And even if, it's probably not one of those that mathematicians have bothered to explore. So, ballpark guess, statistical tests are impossible (or meaningless, if you went ahead and did the numbers assuming a normal model or something).

Can I formalize programs and their execution so that I can make meaningful statements about (stochastic) bug-freeness?

Yes, sure. What you need are

• formal semantics,
• formal specifications, and
• a distribution of inputs.

Then, you can (in principle) prove (not test!) what the expected error rate is. I've never seen it done, though -- probably because it's at least as hard as proving the program correct in the first place.

If you ask me, you are better served with reasonable heuristics and solid processes. Specification testing may be helpful in certain contexts, just because it makes it easy to test many different variants.