Při testování funkcí se dostáváme často do situace, ve které máme množinu vstupních parametrů a ke každému z nich množinu významných hodnot. Pro perfektní otestování by bylo zapotřebí vyzkoušet každou kombinaci, což ovšem není vzhledem ke kombinatorické explozi možné.

Pokud bychom měli funkci deseti parametrů, z nichž každý nabývá právě osmi významných hodnot, pak by byl celkový počet kombinací roven


8^{10} = 1073741824

Testování dvojic

Z tohoto důvodu musíme množství kombinací nějakým způsobem omezit. Jednou takovouto strategií je testování všech dvojic významných parametrů (all-pairs testing). Tato strategie vychází z toho, že nejjednodušším typem chyb jsou ty, které závisí na jednou parametru. Další, co do složitosti, jsou chyby způsobené nějakou dvojicí parametrů. Chyby způsobené trojicemi, případně vyššími n-ticemi, jsou výrazně méně časté.

Pokud se vrátíme k původnímu příkladu, tak z desetice parametrů můžeme vytvořit \\binom{10}{2} = 45 různých párů, kde každý pár může nabývat 8^{2} = 64 hodnot. Počet různých párů parametrových hodnot je proto 45 \\cdot 64 = 2880. Pokud se nám je podaří vyskládat do volání funkce zcela ideálním způsobem, pak nám bude stačit {{2880}/{45}} = 64 testů.

Párově ortogonální latinské čtverce

Latinský čtverec je matice n \\times n, ve které se každý z n symbolů vyskytuje na každé řádce a v každém sloupci právě jednou.


\\begin{bmatrix}
0& 1& 2& 3& 4 \\\\
1& 2& 3& 4&0 \\\\
2& 3& 4& 0& 1 \\\\
3& 4& 0& 1& 2 \\\\
4& 0& 1& 2& 3 \\\\
\\end{bmatrix}

Za párově ortogonální nazveme takovou sérii latinských čtverců, pro kterou platí, že zvolíme-li libovolný libovolné dva čtverce A a B a symbol S, pak bude platit, že pokud vezmeme všechna umístění S v A a promítneme je na B, tak nalezneme každý symbol právě jednou.


\\begin{bmatrix}
0& 1& 2& 3& 4 \\\\
1& 2& 3& 4&0 \\\\
2& 3& 4& 0& 1 \\\\
3& 4& 0& 1& 2 \\\\
4& 0& 1& 2& 3 \\\\
\\end{bmatrix}

\\begin{bmatrix}
0& 1& 2& 3& 4 \\\\
2& 3& 4& 0& 1 \\\\
4& 0& 1& 2& 3 \\\\
1& 2& 3& 4& 0 \\\\
3& 4& 0& 1& 2 \\\\
\\end{bmatrix}

\\begin{bmatrix}
0& 1& 2& 3& 4 \\\\ 
3& 4& 0& 1& 2 \\\\
1& 2& 3& 4& 0 \\\\
4& 0& 1& 2& 3 \\\\
2& 3& 4& 0& 1 \\\\
\\end{bmatrix}

Zároveň platí, že pro libovolnou mocninu pročísla n existuje právě n-1 párově ortogonálních latinských čtverců.

Konstrukce párově ortogonálních latinských čtverců

Pokud je n prvočíslo, pak lze zkonstruovat sérii čtverců pomocí následujícího vzorce (pro k,\\;i,\\; j \\in \\{1, 2, \\cdots, n\\}).

A_{k}(i, \\; j) = [k \\cdot (i-1) + (j-1)] \\bmod n

Latinské čtverce ze zkonstruovat také pro n, které je mocninou prvočísla, ale tento postup je výrazně složitější.

Postup při řešení úlohy

Pokud chceme úlohu testovat pomocí latinských čtverců, tak nejprve musíme zjistit, kolik má faktorů (parametrů) a kolik má každý z faktorů úrovní (významných hodnot). Poté označíme jako m maximální počet úrovní přes všechny faktory a nalezneme libovolné prvočíslo n tak, aby n \\geq m a n-1 \\geq počet\\;faktorů. Nalezené číslo n představuje velikost latinského čtverce.

Posledním krokem přípravy je zakódování jednotlivých faktorů. Každé úrovni každého faktoru přiřadíme jedno číslo z množiny 0n-1. Pokud nám některá čísla zbydou, tak je můžeme dle svého uvážení přiřadit libovolné úrovni (tato úroveň pak bude v důsledku více otestována).

Nyní musíme vygenerovat potřebný počet párově ortogonálních latinských čtverců velikosti n (množství se liší dle způsobu čtení výsledku). Řekněme, že naše n bylo číslo 7.


\\begin{bmatrix}
0& 1& 2& 3& 4& 5& 6 \\\\
1& 2& 3& 4& 5& 6& 0 \\\\
2& 3& 4& 5& 6& 0& 1 \\\\
3& 4& 5& 6& 0& 1& 2 \\\\
4& 5& 6& 0& 1& 2& 3 \\\\
5& 6& 0& 1& 2& 3& 4 \\\\
6& 0& 1& 2& 3& 4& 5 \\\\

\\end{bmatrix}

\\begin{bmatrix}

0& 1& 2& 3& 4& 5& 6 \\\\
2& 3& 4& 5& 6& 0& 1 \\\\
4& 5& 6& 0& 1& 2& 3 \\\\
6& 0& 1& 2& 3& 4& 5 \\\\
1& 2& 3& 4& 5& 6& 0 \\\\
3& 4& 5& 6& 0& 1& 2 \\\\
5& 6& 0& 1& 2& 3& 4 \\\\

\\end{bmatrix}

\\begin{bmatrix}

0& 1& 2& 3& 4& 5& 6 \\\\
3& 4& 5& 6& 0& 1& 2 \\\\
6& 0& 1& 2& 3& 4& 5 \\\\
2& 3& 4& 5& 6& 0& 1 \\\\
5& 6& 0& 1& 2& 3& 4 \\\\
1& 2& 3& 4& 5& 6& 0 \\\\
4& 5& 6& 0& 1& 2& 3 \\\\
\\end{bmatrix}

Čtení výsledku

Řekněme, že naše funkce má 3 parametry, pak můžeme číst výstup následujícími dvěma ekvivalentními způsoby.

Způsob 1

Vybereme tolik čtverců, kolik má funkce parametrů. Nyní postupujeme po indexech a vždy přečteme hodnotu na daném indexu ze všech tří čtverců. Hodnotu i ve čtverci k interpretujeme jako i-tou úroveň k-tého faktoru.

Prvním testem proto bude volání funkce s hodnotami odpovídajícími úrovním [0,\\;0,\\;0], druhým [1,\\;1,\\;1] a posledním [5,\\;4,\\; 3].

Způsob 2

Druhý způsob vyžaduje vždy o dva čtverce méně než je počet parametrů. Místo hodnot z prvních dvou čtverců vždy napíšeme souřadnici, ze které vybíráme zbylé hodnoty.

Pokud budeme vybírat prvky z prvního čtverce, pak bude prvním testem volání funkce s parametry odpovídající hodnotám [0,\\;0,\\;0] (souřadnice [0,\\;0], hodnota 0), druhým [0,\\;1,\\;1] (souřadnice [0,\\;1], hodnota 1), posledním [6,\\;6,\\;5] (souřadnice [6,\\;6], hodnota 5),


Příklad

Mějme webovou aplikaci, která má 4 verze – 1.0, 1.1, 1.2 a 1.3. Tato aplikace využívá služeb databázového serveru buď prostřednictvím ORM frameworku Hibernate nebo Toplink. Kompatibilitu tohoto spojení chceme prověřit na databázích algoritmyQL, Oracle, MySQL, MS SQL Server a Firebird. Celá aplikace bude nasazena buď na jednom ze serverů Tomcat 6, Tomcat 7, Glassfish 2.1, Glassfish 3 nebo JBoss 4.

Proveďte testování aplikace pomocí metody ortogonálních čtverců.

Kódování

Nejprve úlohu zakódujeme. Faktory zde jsou: verze aplikace, ORM framework, databázový server a aplikační server (servletový kontejner). Úrovně jsou jednotivé verze/typy. Nejvíce úrovní mají společně databázový server a servletový kontejner/aplikační server – oba pět. Jelikož má úloha pouze 4 faktory, tak budeme kódovat pro párově ortogonální čtverce velikosti 5.

Verze aplikace: 0 (1.0), 1 (1.1), 2 (1.2), 3 (1.3), 4 (1.0)
ORM Framework: 0 (Hibernate), 1 (Toplink), 2 (Hibernate), 3 (Toplink), 4 (Toplink)
Databázový server: 0 (algoritmyQL), 1 (Oracle), 2 (MySQL), 3 (MS SQL Server), 4 (Firebird)
Servletový kontejner/Aplikační server: 0 (Tomcat 6), 1 (Tomcat 7), 2 (Glassfish 2.1), 3 (Glashfish 3.0), 4 (JBoss 4)

Rozhodli jsme se, že výsledek budeme číst prvním způsobem, vygenerujeme proto 4 párově ortogonální latinské čtverce velikosti 5.


\\begin{bmatrix}

0& 1& 2& 3& 4 \\\\
1& 2& 3& 4& 0 \\\\
2& 3& 4& 0& 1 \\\\
3& 4& 0& 1& 2 \\\\
4& 0& 1& 2& 3 \\\\

\\end{bmatrix}

\\begin{bmatrix}

0& 1& 2& 3& 4 \\\\
2& 3& 4& 0& 1 \\\\
4& 0& 1& 2& 3 \\\\
1& 2& 3& 4& 0 \\\\
3& 4& 0& 1& 2 \\\\

\\end{bmatrix}

\\begin{bmatrix}

0& 1& 2& 3& 4 \\\\
3& 4& 0& 1& 2 \\\\
1& 2& 3& 4& 0 \\\\
4& 0& 1& 2& 3 \\\\
2& 3& 4& 0& 1 \\\\

\\end{bmatrix}

\\begin{bmatrix}

0& 1& 2& 3& 4 \\\\
4& 0& 1& 2& 3 \\\\
3& 4& 0& 1& 2 \\\\
2& 3& 4& 0& 1 \\\\
1& 2& 3& 4& 0 \\\\
\\end{bmatrix}

Nyní můžeme číst testovací plán:

1) 1.0, Hibernate, algoritmyQL, Tomcat 6
2) 1.1, Toplink, Oracle, Tomcat 7
3) 1.2, Hibernate, MySQL, Glassfish 3
4) 1.3, Toplink, MS SQL Server, Glashfish 2.1
5) 1.0, Toplink, Firebird, JBoss 4
6) 1.1, Hibernate, MS SQL Server, JBoss 4
7) 1.2, Toplink, Firebird, Tomcat 6
8) 1.3, Toplink, algoritmyQL, Tomcat 7
9) 1.0, Hibernate, Oracle, Glassfish 3
10) 1.0, Toplink, MySQL, Glashfish 2.1
11) 1.2, Toplink, Oracle, Glashfish 2.1
12) 1.3, Hibernate, MySQL, JBoss 4
13) 1.0, Toplink, MS SQL Server, Tomcat 6
14) 1.0, Hibernate, Firebird, Tomcat 7
15) 1.1, Toplink, algoritmyQL, Glassfish 3
16) 1.3, Toplink, Firebird, Glassfish 3
17) 1.0, Hibernate, algoritmyQL, Glashfish 2.1
18) 1.0, Toplink, Oracle, JBoss 4
19) 1.1, Toplink, MySQL, Tomcat 6
20) 1.2, Hibernate, MS SQL Server, Tomcat 7
21) 1.0, Toplink, MySQL, Tomcat 7
22) 1.0, Toplink, MS SQL Server, Glassfish 3
23) 1.1, Hibernate, Firebird, Glashfish 2.1
24) 1.2, Toplink, algoritmyQL, JBoss 4
25) 1.3, Hibernate, Oracle, Tomcat 6

Kód

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int size = 5;
        int[][][] matrix = latinSquares(size);

        String[][] map = {
            {"1.0, ", "1.1, ", "1.2, ", "1.3, ", "1.0, "},
            {"Hibernate, ", "Toplink, ", "Hibernate, ", "Toplink, ", "Toplink, "},
            {"algoritmyQL, ", "Oracle, ", "MySQL, ", "MS SQL Server, ", "Firebird, "},
            {"Tomcat 6", "Tomcat 7", "Glassfish 3", "Glashfish 2.1" ,"JBoss 4"},
        };
        int count = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(++count + ") ");
                for (int k = 0; k < size - 1; k++) {
                    System.out.print(map[k][matrix[k][i][j]] + " ");
                }
                System.out.println("");
            }
        }
    }

    public static int[][][] latinSquares(int size) {
        int[][][] matrix = new int[size][size][size];
        for (int k = 1; k <= size; k++) {
            for (int i = 1; i <= size; i++) {
                for (int j = 1; j <= size; j++) {
                    matrix[k - 1][i - 1][j - 1] = (k * (i - 1) + (j - 1)) % size;
                }
            }
        }
        return matrix;
    }

Literatura

  • MAŘÍK, Radek. Testování a verifikace softwaru, Optimalizace sady testů - slides k přednášce.







Doporučujeme