65.000.000.000 tests to run

Question

I was asked about how to run a suite of 65.000.000.000 tests and I wonder if it is normal to have a project with such a huge amount of tests.

Have you worked in projects with this characteristic?

Answer 1

With 65 billion tests, it sounds like you're being asked to test all possible inputs. This is not useful--you'd essentially be testing that your processor functions correctly, not that your code is correct.

You should be testing equivalence classes instead. This will drastically reduce your range of test inputs.

Also consider whether you can subdivide your system into smaller pieces. Each piece will be easier to test in isolation, and then you can perform some integration tests which bring all the pieces together.

If you still want that reassurance that some of those input combinations work, perhaps you could try fuzz testing. You will get some of the benefits of testing lots of different inputs, but without running all 65 billion of them.

Answer 2

If this is a real test suite, then you don't want to get anywhere near working on it.

The whole job of a tester is to strike a balance between testing thoroughly enough to be confident you've got the "right" results and writing few enough tests that they can be run in a reasonable amount of time.

Many tests can be abstracted into "equivalence classes", which means that rather than run 3 billion tests, you run 1 that gives you a reasonable level of confidence that all other tests in that equivalence class would run successfully, if you decided to waste the time running them.

You should tell whoever is thinking of running 65 billion tests that they need to do a better job abstracting tests into equivalence classes.

Answer 3

More than likely, you arrived at your figure of 65 billion tests by calculating all possible combinations of inputs into the system under test, or by computing the cyclomatic complexity and assuming a test must be written for each of these unique execution paths.

This is not how real tests are written, because as other posters and commenters have indicated, the technical power required to execute 65 billion tests is staggering. This would be like writing a test that exercises a method to add two integers by plugging in every possible permutation of two 32-bit values and checking the result. It's utter insanity. You have to draw the line and identify a subset of all possible test cases, which between them would ensure that the system will behave as expected throughout the range of inputs. For instance. you test adding a few "ordinary" numbers, you test a few negative-number scenarios, you test technical limits like overflow scenarios, and you test any scenarios that should result in error. As was mentioned, these various types of tests exercise "equivalence classes"; they allow you to take a representative sample of the possible inputs, along with any known "outliers", and say with an extremely high confidence that because these scenarios pass, all scenarios similar to these will pass.

Consider one of the basic code katas, the Roman Numeral Generator. The task, to be performed using TDD techniques in a "dojo" style, is to write a function that can accept any number from 1 to 3000 and produce the correct Roman numeral for that number value.

You don't solve this problem by writing 3000 unit tests, one at a time, and passing them in turn. That's lunacy; the exercise normally takes between one and two hours, and you'd be there for days testing each individual value. Instead, you get smart. You start with the simplest base case (1 == "I"), implement that using a "least-code" strategy (return "I";), and then look for how the code you have will behave incorrectly in another expected scenario (2 == "II"). Rinse and repeat; more than likely, you replaced your initial implementation with something that repeats the "I" character as often as necessary (like return new String('I',number);). That will obviously pass a test for III, so you don't bother; instead, you write the test for 4 == "IV", which you know the current implementation won't do correctly.

Or, in a more analytical style, you examine each conditional decision that is made by the code (or needs to be), and write a test designed to enter the code for each possible outcome of each decision. If you have 5 if statements (each having a true and false branch), each of them fully independent of the other, you code 10 tests, not 32. Each test will be designed to assert two things about a particular possible decision; first that the correct decision is made, and then that the code entered given that condition is correct. You don't code a test for each possible permutation of independent decisions. If the decisions are dependent, then you have to test more of them in combination, but there are fewer such combinations because some decisions are only ever made when another decision had a particular outcome.

Answer 4

Is this "normal"?, no. Where "normal" is defined as the average or typical experience. Can't say I've ever had to work on a project like that, but I have been on a project where one in every few million bits would get flipped. Testing that one was ... a challenge.

Is it potentially required? Well, that depends upon the guarantees and specifics of the project. It's a bit incredulous to comprehend at first, but your question is light on specifics.

As others (MichaelT) have pointed out, the time to complete this task with serial testing makes this impractical. So parallelization becomes your first consideration. How many test systems can you throw at this problem, and what support do you have for collating the results of those multiple systems?

What guarantees do you have that the device or algorithm you're testing is being reliably replicated? Software is pretty reliable in replication, but hardware devices (especially first generation) can have manufacturing issues. A false test failure in that case could indicate either a bad algorithm or the device didn't assemble correctly. Do you need to distinguish between those two cases?

You'll also need to consider how you're going to validate the testing systems themselves. Presuming a legitimate reason for that many test cases, you're going to need a lot of automation. That automation needs to be inspected to make sure it doesn't err in generating your test cases. Spot checks for errors would truly be the equivalent of finding a needle in the haystack.

This arstechnica link may or may not shed some insight on your testing considerations. GPU clusters are commonly used for brute-force cracking passwords. The one cited in the article can can cycle through as many as 350 billion guesses per second, so that kind of puts your 65B tests in perspective. It's likely a different domain, but it shows how approaching the task from different angles may yield a viable solution.

Answer 5

I don't think it is feasible to maintain 6.5e+10 tests it the first place, so running them may be moot. Even biggest projects, like Debian with all its packages, have only several hundred million SLOCs total.

But if you have to run a huge number of tests anyway, there are a few strategies.

• Don't run them all. Most probably not every test depends on every code path. Define dependencies between subsystems and their tests, and between test suites, and you'll be able to only run unit tests relevant to a particular change, only the integration tests depending to these unit tests, etc.

• Run them in parallel. With code base that huge, you probably have a massive build farm (back at JetBrains, a relatively small operation, we used to have 40-50 build agents running on the IDEA continuous build / integration farm alone). Since unit tests are independent, and integration tests can reuse already built code, tests are relatively easy to parallelize.

• Stop running early. If you know that a particular test suite depends for its reasonable functioning on correctness of another test suite, you can cut the whole chain once you see one link fail.

Disclaimer: I'm not a professional testing engineer. Take the above with a grain of salt.

Answer 6

Although there have been several good suggestions here on how to try to sneak by with fewer tests, I seriously doubt your system has only 65 billion input combinations. That is less than 36 bits of input. Let's assume you had already taken all the advice given above.

If each test takes about a millisecond to run and you distribute the tests across only 10 processors (one normal PC), the test will run in a little over 69 days. That is a while, but not completely unreasonable. Distribute across 100 processors (a dozen normal PC's or one reasonable server PC) and the tests will complete in a under 7 days. You could run these every week to check for regressions.