Exhaustive Testing (And Certainty)

Exhaustive testing is the idea of testing every single possible combination of inputs to a function. It’s great if you can do it, but there’s a related idea we need to discuss alongside it. The idea is certainty in testing and certainty through testing, or just in the rawest form – absolute certainty that what you created was/is/and will be correct.

Any sort of testing can pretty easily prove that a program has an error, but it’s probably no surprise that testing won’t prove the absence of any errors. There might even be catastrophic bugs left in a program that’s passed diligent and thorough testing.  Formal proofs seem like they might be a hope for gaining complete control and certainty, but a proof itself could contain an error, just like a program. Even with automated verification tools for proofs, the tool used for verification could have a bug.

So we come back to exhaustive testing. It involves testing every single possible combination of inputs, and verifying each and every output result is correct. It seems like exhaustive testing should be the one and maybe only way to prove, with 100% certainty, that some portion of a program is correct. Unfortunately, it too has insurmountable limitations.  An obvious problem is that the tests themselves could have bugs. But even ignoring this, passing results under exhaustive testing are no guarantee of correctness. Significant bugs could still remain in the tested code, due to undefined behavior.  When program code invokes undefined behavior, one possible result is that everything proceeds exactly as the author planned.  This sounds encouraging… at first. Yet upon changing the compiler, or the hardware used for testing, or the time of day, or upon changing anything at all really, the executable could begin to fail.  Even if program code invokes no undefined behavior at all, a bug in the compiler or a fault in the hardware could conceivably produce false negatives on one or more tests.  In a sense, the tests might lie about correctness. And as for hardware faults, strange thing can happen. One story I read was about a program created via machine learning that found the most optimal solution was to use a short circuit that existed due to a defect in the substrate of the development board.  The program worked perfectly on that one defective board, and nowhere else.

Absolute certainty is impossible. It’s also a distraction. What we really want to gain is better results and more confidence, given the same amount of time (or less). So in that light, if we can do exhaustive testing and it’s fast, why not do it?

Exhaustive testing provides the best test coverage possible, and when it’s possible at all, it’s typically very easy to write the exhaustive tests.  As for feasibility, with today’s hardware it’s usually possible to exhaustively test any pure function that has just a single 32 bit input parameter, or any pure function that has two 16 bit input parameters.  In fact, so long as the combined bit depth of all the input parameters isn’t much beyond 32 bits, a pure function is usually possible to exhaustively test.  Perhaps the test might take fifteen minutes or more, but it could be done when you want to run long tests.  More encouragingly, if you have a function with total input parameter bit depth of 16 bits (or less), you might reasonably expect exhaustive testing of that function to take 10 milliseconds or less.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s