Orthogonal arrays - relation to software testing, is that sample true?

Question

When doing ortohognal arrays testing, the process is like this:

Consider a function with 3 variables,each with 3 options.

1. 3 pairs, each with 3*3 values = 27 parametric pairs.
2. Each "function call" contains 3 pairs, i.e. in the optimal arrangement, I need only 27/3=9 test cases to cover all pair-wise combinations. I get that.

But there was an example with 75 binary options, which is 2775 pairs,each with 4 possible outcomes, i.e. 11100. In the ideal arrangement, one program call uses 2775 pairs, hence it seem 11100/2775= 4 test case to cover all pair wise conbimation. Is that even possible?

Answer 1

It's not possible. If we have $4$ rows in the covering array, then there are $2^4=16<75$ possible columns, so there are two identical columns, and for those two columns $10$ and $01$ are not tested.

Thus, there is no $4 \times 75$ binary orthogonal array. But this is unsurprising, orthogonal arrays are very special and fairly rare matrices. The parameters will usually have to be "just right" for one to exist.

The least number of rows where each pair is tested will have $\geq 7$ rows, since $2^6<75$ too (so we can apply the same argument).

Answer 2

I'm the founder of Hexawise, a software test design tool that (among other things) enables testers to create small sets of tests that achieve coverage of all pairs of values. So this is a subject I've spent a fair amount of time thinking about.

No. It is not possible to achieve pairwise coverage in only 4 tests. Not even close. Whatever you do, you will wind up having a great deal of repetition immediately after your second test case. The number of net new pairs you cover in each test case starting with test 3 and onward will be far lower than the number of pairs that you are able to cover for the first time in tests #1 and test #2. A detailed explanation of exactly how diminishing marginal coverage returns happen in situations like these (and why they are inevitable in almost all situations) is described here.

• With your first test you will cover 25% of the total pairs to be covered (e.g., if you use A's for all 75 parameters)

• With your second test, you will cover another 25% of the total pairs to be covered if you use B's for all 75 parameters

• With your third test, it will be impossible to prevent repeating coverage of many, many pairs that have already been covered. Here's an example: For your third test, let's say you choose A for Parameter 1. You would need to select B for Parameter 2 to avoid P1=A & P2=A already covered in your first test. And by Parameter 3, you would be doomed to repeat a pair that has already covered in one of your first two tests. Why? If Parameter 3 = A, you would repeat P1=A and P3=A from your first test. If you select B for Parameter 3, you would repeat P2=B and P3=B from your second test.

Here is a near optimal solution to your specific question that Hexawise calculates. It requires 15 tests to achieve complete coverage of all pairs when the System Under Test contains 75 Parameters which each contain 2 Values.

If you examine the coverage of the pairs achieved after each test, you would notice that the coverage would be characterized by steep coverage in the beginning with a dramatic flattening out of additional coverage per test as tests towards the end were able to cover fewer and fewer "not-yet-covered-already" pairs.

• After test 1: 25% of pairs are covered.

• After 2: 50%

• After 3: 63.0%

• After 4: 76.0%

• After 5: 82.2%

• etc.

One nuance left out of the above explanation: for purposes of software testing, achieving coverage of all possible pairs of values is a NEARLY identical goal to orthogonal array-based coverage but subtly different. Pairwise coverage is an easier to meet goal than orthogonal array-based coverage. Pairwise coverage simply requires that all pairs be covered in as few tests as possible. Orthogonal array-based coverage has the additional requirement that there be "uniform distribution throughout the domain." As a result of this additional requirement, orthogonal array-based solutions often require a greater number of tests as compared to a straightforward 2-way / pairwise / allpairs coverage goal (which can be achieved in a smaller number of tests using a "covering array.") As a software tester, do you benefit much from the added tests that an orthogonal array solution? In my experience, no. Would software testers usually be better off with a smaller set of 2-way tests from a more efficient covering array? In my experience, yes. For more information than you might want to know, please see orthogonal arrays vs. pairwise software tests: which are better?

A second nuance: The above solution is near optimal. It would not surprise me too much if someone figured out a way to pack coverage of all pairs into 14 tests.