Product Managment and QA: Constraining the Test Cases

by dj on February 2, 2005

As anybody who has ever tried to build test cases for an application or system of moderate complexity knows, you quickly run into the well-known multiple-branching problem. Essentially, it's very easy to generate more test cases (by tweaking different paramenters) than is logistically possible to test. Everybody is well aware of the tester's lament: They never get enough time to complete all the testing. Well, the multiple-branching problem ensures that matter how much time you give the tester, they never will get enough time. I will illustrate with a simple example.

Let's say you have an application with 8 options or choices (or branches) on-screen. Clicking on one of the 8 options takes you to another screen that presents you with more choices. Each option, or new screen presents you with an average of five choices.

Let's pretend the app goes only one option deep ie when you click to another screen, you cannot click to yet another screen which presents you with more options.

Let's pretend the app doesn't take in external data (ie data is created and manipulated solely within the context of the app).

If we want to generate a test plan that covers all the parameters (100% code coverage), you see that we come to: 5x5x5x5x5x5x5x5= 390,625 test cases.

Now even if you script all those test cases so they run automatically, I don't think you can execute 390,000 test cases in a reasonable amount of time: Assume that a test is executed once a second, and it would take you about four and a half-days, to do one complete run.

Of course, you can pretend that each branch has absolutely no dependencies on other branches. Whatever. Make that assumption (a big one) and you cut the cases down to 40. Wow, guess what happens: Most test plans constrain the test cases by limiting the number of parameters picked when doing a complete system test (aka "sanity test"). Then all other features (hopefully) are tested in a group where the dependencies are obvious. And the branches that have hidden dependencies don't get tested and that's where most of your bugs creep in. This happens because everybody believes you can't get anywhere close to 100% code coverage in your tests because of the branching conundrum.

However, there is a testing theory does lead one to believe that you can get upward of 90% code coverage. It's called pairwise testing or CATS (Constrained Array Testing System). There is a web site that explains the theory in mind-numbing detail here, but I will try to explain it in plain English.

What you really want to do is eliminate redundacy by only testing each parameter with every other parameter once. There is no algorithm (that I know of) that can generate the test cases for you, you need to sit down with colored pencils and a paper and draw up columns of letters that represent the parameters you need to tweak to generate the test cases. For the example above, you need to have 8 columns of five parameters, or 8 columns of parameters ABCDE. Let's generate the first test run, which will be all the parameter that will be tested with parameter A in the first column:

1. AAAAAAAA

2. ABCDEDCB

3. ACBCCBDC

4. ADEBCBBD

5. AEDEDEEE

Now we will generate all the test runs for parameter B in the first column (use a different color pencil or it gets confusing).

1. BABDCEDB

2. BBABDCBE

3. BCDCEDAE

4. BDCEABCE

5. BEEABAED

Move to C. Change color of your pencil.

1. CDACCDEC

2. CECEEABA

3. CABABBAB

4. CBDBACCD

5. CCEDDEDE

Oh, so boring and tedious. But not as boring as testing 390,000 test cases. Change the color of your pencil.

1. DADDACAB

2. DBBBBECA

3. DCCCDBDC

4. DDEECABE

5. DEABEDED

The last run. I promise.

1. EAEDDCEB

2. EBDAEDDE

3. ECAEAEBC

4. EDBBCBAA

5. EECCBACD

Whew, that was a lot of work, and I'm not sure I did it right. What we should have is just 25 test cases, with every parameter tested with every other parameter. That's right, you have even less test cases than if you were to test the parameters in isolation with one another. Another beautiful thing about pairwise testing is that the maximum number of test cases is X times Y where X is the column with the highest number of parameters and Y is the column with the second-highest number of test cases. It doesn't matter how many columns you have.

I first encountered this theory back in 1998 when I was the tester for the Prescript team. It allowed me to generate all the test cases for GUI testing and be very confident that I had covered all reasonable possibilities. Interestingly, when I tried to get developers to develop an program for me that would generate pairwise test cases for me, nobody was interested.

I guess this tells you what developers think about testing. Anyways, if you are in Q & A and you know about this theory, it can totally save your rear end (it did save mine), as it makes testing manageable (which is the name of the game). Quite frankly, it can make testing almost easy (in the sense you'll find the bugs really fast with these test runs).

Mind you, companies don't seem to hire QA people who have good theory knowledge of QA, rather they seem to leaning towards cheap talent that know some apps that purport to make testing easy (like the Mercury suite). Pity.

Comments on this entry are closed.