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

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 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 symbol , pak bude platit, že pokud vezmeme všechna umístění v a promítneme je na , 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 existuje právě n-1 párově ortogonálních latinských čtverců.

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

Pokud je 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 , 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 maximální počet úrovní přes všechny faktory a nalezneme libovolné prvočíslo tak, aby $n \\geq m$ a $n-1 \\geq počet\\;faktorů$ . Nalezené číslo 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 až n-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 (množství se liší dle způsobu čtení výsledku). Řekněme, že naše bylo číslo .

$\\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 ve čtverci 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 ), druhým $[0,\\;1,\\;1]$ (souřadnice $[0,\\;1]$ , hodnota ), posledním $[6,\\;6,\\;5]$ (souřadnice $[6,\\;6]$ , hodnota ),

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

Java

    /**
     * @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.