Orthogonal arrays

Arjen Markus (11 may 2008) Orthogonal arrays can be used to reduce the number of test cases you need in a systematic way (see for instance [L1 ]) - this is part of the method of robust design.

To illustrate how this is done, let us have a look at the following (somewhat artificial) procedure: it will read a file, assuming there is one number per line and return a list of numbers that fit a particular condition (above or below some threshold).

proc numbersFromFile {filename threshold method} {
    set infile [open $filename]

    set method above
    while { [gets $infile number] >= 0 } {
        switch -- $method {
            "no" {
                 set selected 1
            }
            "above" {
                 set selected [expr {$number >= $threshold}]
            }
            "below" {
                 set selected [expr {$number <= $threshold}]
            }
            default {
                 set selected 1
            }
        }
        if { $selected } {
            lappend result $number
        }
    }
    close $infile

    return $result
}

We have three input arguments:

Typical values for the first could be: the name of a valid file, the name of a non-existing file, the name of an empty file
Typical values for the second could be: the threshold is somewhere in the middle of the data, the threshold is well below the minimum value, the threshold is well above the maximum
Values for the third are: no (all numbers accepted), above and below

This gives us in total 27 test cases - giving full branch coverage in this fairly straightforward case.

With orthogonal arrays we can reduce this number to nine (with actually a spare argument). The table we can find on http://www.research.att.com/~njas/oadir/ (oa.9.4.3.2) is suitable for four arguments (it has four columns), each taking three values and this table will guarantee that all combinations of two arguments with all their values are tested.

(Of course for a full test of all combinations of all arguments we would need 27 tests, but we want to reduce that number - especially as in general there may be many more arguments and other inputs to consider).

The table looks like this:

Each row is a single test case and the number is the index of the value to take for each argument.

So, let us turn this into a small test procedure:

proc testViaOrthogonalArrays {_arguments_ _body_} {
    #
    # Assumption: oa.9.4.3.2 can be used - no check!
    #
    set _table_ [split \
{0000
0112
0221
1011
1120
1202
2022
2101
2210} \n]

    foreach _row_ $_table_ {
        set _case_ {}
        foreach _argvalues_ $_arguments_ _idx_ [split $_row_ {}] {
            set _arg_    [lindex $_argvalues_ 0]
            set _values_ [lrange $_argvalues_ 1 end]

            set $_arg_ [lindex $_values_ $_idx_]
            lappend _case_ [set $_arg_]
        }

        set _rc_ [catch {
            set _result_ [eval $_body_]
        } _msg_]

        if { $_rc_ == 0 } {
            puts "CASE: [join $_case_ /] RESULT: $_result_"
        } else {
            puts "CASE: [join $_case_ /] ERROR: $_msg_"
        }
    }
}

Let us try this (we add a fourth argument - "dummy" to keep things simple):

File correct.inp contains the numbers 1, 5, 10, 20 and 30 respectively)

testViaOrthogonalArrays {
    {filename  "correct.inp" "empty.inp" "non-existant.inp"}
    {threshold 10.0 -1.0 100.0}
    {method "no" "above" "below"}
    {dummy 1 2 3}
} {numbersFromFile $filename $threshold $method}

The resulting output is:

CASE: correct.inp/10.0/no/1 RESULT: 10.0 20.0 30.0
CASE: correct.inp/-1.0/above/3 RESULT: 1.0 5.0 10.0 20.0 30.0
CASE: correct.inp/100.0/below/2 ERROR: can't read "result": no such variable
CASE: empty.inp/10.0/above/2 ERROR: can't read "result": no such variable
CASE: empty.inp/-1.0/below/1 ERROR: can't read "result": no such variable
CASE: empty.inp/100.0/no/3 ERROR: can't read "result": no such variable
CASE: non-existant.inp/10.0/below/3 ERROR: couldn't open "non-existant.inp": no such file or directory
CASE: non-existant.inp/-1.0/no/2 ERROR: couldn't open "non-existant.inp": no such file or directory
CASE: non-existant.inp/100.0/above/1 ERROR: couldn't open "non-existant.inp": no such file or directory

Besides testing, orthogonal arrays are also used to optimise design parameters: here you need to examine a large number of cases too, but now to find a some optimum.

Lars H: In discrete mathematics, these things are usually called (block) designs [L2 ]. I recall it as being the by far most boring part of my first disc.math. course, but certainly they're nice to have if one actually need to perform an "experiment examining many parameters" as above.

AM Yes, in statistics they are connected to Latin squares and other experiment design methods. Rather abstract (and quite possibly boring to set up) - but you can always fall back to the published tables.

AM A closer look at the above results reveals that the choice of the file name is the dominant factor in the logic: If there is no list of numbers to read, the rest of the code is not run. I must think of a slightly better example, where there is not a single variable that influences the result so much.

Category Testing

Category Mathematics