Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
29  
65 Billion (10e9) tests? Is this a practical problem or an interview question? –  MichaelT Jul 10 '13 at 18:16
37  
I'd be very interested to know who wrote 65 billion tests and how many years it took them. –  Rig Jul 10 '13 at 18:17
44  
With 65 billion tests, if you can run 1000 tests/second, it will take about 2 years to run. 10,000 tests/second is a bit over two months. 100,000 tests/second will take about a week. This is describing some serious processing power to run the tests in a reasonable timeframe. –  MichaelT Jul 10 '13 at 18:24
20  
I don't want to be the guy who writes the traceability matrix... –  mouviciel Jul 10 '13 at 18:35
21  
@DanPichelman - Clearly, you need to write another half a billion tests to test that the test generator generates tests correctly. –  Bobson Jul 10 '13 at 19:04
show 29 more comments

6 Answers

up vote 95 down vote accepted

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.

share|improve this answer
11  
+1, especially for "you'd essentially be testing that your processor functions correctly" –  Doc Brown Jul 11 '13 at 6:31
2  
For simple enough functions (bit fiddling etc.) I do tend to test all possible values. It’s fool-proof and thus gives me much better confidence than testing (derived, and thus potentially erroneous) equivalence classes. Of course that doesn’t work any more when your possible inputs go into the billions. –  Konrad Rudolph Jul 11 '13 at 7:14
add comment

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.

share|improve this answer
    
+1 on testing thoroughly but efficiently. –  Marco Jul 18 '13 at 7:41
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
5  
... Of course, at JetBrains, those build agents are free because they develop TeamCity and own it outright. Other "relatively small operations" would likely have a heart attack at the thought of a roughly $15,000 initial cost (just for the software; add 40-50 blademount units and other hardware, and even using a free Linux distro to host it all you're easily talking a senior dev's annual salary) and $6500 annual maintenance fees, plus the time and skill of the IT staff needed to keep the build farm humming along. –  KeithS Jul 10 '13 at 19:41
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.