How to calculate reliability (or confidence of no more errors) after a large run with no errors? I have a (software) system which was failing, with a particlular failure mode, about 0.5% of the time. This was low enough that it was not noticed during inital development.
After performing several regression tests however we found a particular intermittent (race condition) failure mode.
One bug was fixed, which dropped the rate to 0.01%
Later a second bug was fixed, which after an overnight run of 20,000 tests, there have been no more errors.
So either the bug/falure mode has been eliminated completely or the probability of it occurring is (very?) low.
How can I calculate the confidence / probability of being free of this fault, given the 20,000 error free test run?
Given that I have X reliability, how many more test runs would I need to exceed the reliability Y, that our hosting providers guarantees? (and is that enough?)
 A: 
Hat tip to @soakley for his comment.

The rule of three (3/number of test runs) can be used to test with a 95% confidence interval that failures will occur less than 1 in N times. 
As an example if you have performed 1500 test runs with no failures, then  3/1500 gives a 95% confidence that failures will occur less than 1/500 of the time.
For higher confidence then numerator can be calculated with the formula -ln(1 - p)
So the numerator values of 3.51, 4.61, 5.3, and 11.52 may be used for the 97%, 99%, 99.5%, 99.999% confidence intervals, respectively.
So performing 11,520,000 test runs (with no failures) gives a 99.999% confidence that there will be less than 1 failure in 1,000,000 
A: You can document what you have in fact tested, and you can try to ensure you've covered all conditions, and document the conditions you've covered, but ultimately, there remains the probability of encountering conditions correlated with each other, or with external factors, such as eg date of the year, or time of day.
As an example, if you were testing software involving a hardware clock, and now is 1995, and you didnt test for eg years greater than 1999, maybe your system might fail catastrophically when you reach the year 2000.  Although all your tests for dates and times in 1995 would work perfectly :)
Generally speaking, many/most system failures are the result of some unforeseen error. You cannot foresee what these errors will be, therefore cannot test for them. You can however foresee that you will have unforeseen errors :P
Typically, the way to mitigate such errors is to eliminate SPOFs ("single points of failure"), and ensure the systems are redundant, so that if they do fail, other systems keep running. Of course you can still have correlated failures... hence why you try to eliminate SPOFs, as much as possible.
Edit: OP asks:

I am not looking at testing all failures across the whole system. I am looking to see how many tests I need to run to see if one particular failure mode has been eliminated; with a high degree of confidence. 

So, from a mathematics point of view, it looks like you really want to say that the probability of failure = 0 failures / 20,000 tests = 0.0000% :) However, even if assume that your tests are drawn uniformally from the actual distribution that you will encounter in prod, there's still uncertainty in this estimate, which you'd need to calculate.
In reality, I strongly doubt that your test distribution matches your production distribution. I'm going to guess your tests are heavily skewed towards testing things associated with the bug(s) you've already encountered/fixed, and thus will plausibly under-represent samples from other parts of the distribution.
In my opinion, communication of what you've done/tested, and your opinion that there is no further requirement for testing is a question of communications and negotiations, rather than pure mathematics, and such things are outside of the scope of Cross Validated.
