Lecture05 (Лекции в ПДФ), страница 3

Ниже рассматриваются две такие конструкции — для глубины 2 и дляглубины 3.Рекурсивная конструкция для покрывающих наборов глубины 2 и n = pk.Строим набор для nm+1 параметра из набора для m параметров.Обозначим через Aij (i <= N, j <= m) элементы исходного набора из CA(2; m, n).Обозначим также через Bij элементы из нижней части (без n верхних строк)покрывающего набора, построенного с помощью самой первой конструкции, число строк внаборе B равно z = n2–n.Строим новый набор в соответствии с приведенной ниже схемой — в ней первая ипоследняя строки, а также первый столбец, отмечают группировку элементов.nnnN0A11A11A11A12A12A12A1mA1mA1m0A21A21A21A22A22A22A2mA2mA2m…………………………0AN1 AN1AN2AN2ANm ANmAN1 AN2ANmB11 B12B12 B13B13B1(n+1)B1(n+1)………………Bz2 Bz3Bz3Bz(n+1)Bz(n+1)…Bz1 Bz2mmmПолучаем соотношение CAN(2; mpk+1, pk) <= CAN(2; m, pk) + p2k – pk.Пример для n = 3, m = 4 Исходный набор012345678001201201200011122210121202012012201120Получаемый набор размера 15 для 13 параметров выглядит так.01234567891011121314000000000111222000111222012012000111222012012000111222012012012012012012012012012012120201012012012120201012120201120201012120201120201012120201201120012201120201120012201120201120012201120201120Рекурсивная конструкция для покрывающих наборов глубины 3.Строим набор глубины 3 для числа элементов n и 2k параметров из набора глубины 3 длятого же числа элементов и k параметров и набора глубины 2 для того же числа элементов и kпараметров.Обозначим элементы исходного набора глубины 3 через Aij (i <= N, j <= k), элементыисходного набора глубины 2 — через Bij (i <= z, j <= k ).Строим новый набор в соответствии с приведенной ниже схемой — в ней первый столбецотмечает группировку элементов, а все сложения проводятся по модулю n.N12…A11A11A12A12A13A13A1kA1k……………………AN1 AN1AN2 AN2AN3 AN3ANk ANkB11(B11+1)B12(B12+1)B13(B13+1)B1k(B1k+1)……………………Bz1(Bz1+1)Bz2(Bz2+1)Bz3(Bz3+1)Bzk(Bzk+1)B11(B11+2)B12(B12+2)B13(B13+2)B1k(B1k+2)……………………Bz1(Bz1+2)Bz2(Bz2+2)Bz3(Bz3+2)Bzk(Bzk+2)……………………B11(B11+(n-1)) B12(B12+(n-1)) B13(B13+(n-1))B1k(B1k+(n-1))……………(Bz3+(n-1))Bzk(Bzk+(n-1))n-1 …Bz1…(Bz1+(n-1)) Bz2…(Bz2+(n-1)) Bz3Получаем соотношение CAN(3; 2k, n) <= CAN(3; k, n) + (n-1)CAN(2; k, n).Для представленных выше в различных местах наборов с n = 3 и k = 4 можно получитьнабор из CA(3; 8, 3), имеющий 45 строк.Приведенные выше конструкции позволяют строить наборы, число тестов в которыхпримерно пропорционально логарифму числа параметров.

Доказаны следующиесоотношения.При n→∞ CAN(2, k, n) ~ (n/2)log(k)CAN(t, k, 2) <~ t2tlog(k)O(log(t))CAN(t, k, n) <~ (t-1)log(k)/log(nt/(nt-1)), что при nt→∞ можно ограничить выражением(1+ε)tntlog(k) для любой положительной константы ε.Построение неоднородных покрывающих наборовНеоднородные покрывающие наборы часто можно достаточно быстро построить изблизких по конфигурации однородных.Например, самый первый приведенный выше набор из CA(2, 3,⋅2,⋅5,⋅4,⋅3,⋅5) был построентак.

Переставляя параметры его можно свести к CA(2, 5, 5, 4, 3, 3, 2). Уже видно, чтопотребуется как минимум 25 строк. Есть однородный набор CA(2, 5, 5, 5, 5, 5, 5), состоящийв точности из 25 строк — берем его и приводим все параметры с меньшим числом значенийпо модулю этого числа значений.Описанный прием может не дать покрывающий набор, если есть параметры с числомзначений, не взаимно простым с числом значений в исходном однородном наборе.

В такихслучаях часто все равно можно построить соответствующий неоднородный набор, толькодля «проблемных» параметров придется отдельно подбирать расположение их значений.Еще один пример — покрывающий набор из CA(2, 10, 9, 8, 7, 6, 5, 4, 3, 2). Для неготребуется не меньше 90 строк, однако близких однородных наборов с 10 значениями нет.Первые два столбца построим просто как все возможные сочетания 10 и 9 элементов. Адальше можно использовать столбцы, начиная с третьего, из однородного набора для 9элементов из CA(2; 10, 9). Для параметров, число значений которых равно 6 и 3, придетсядополнительно подбирать расстановку, но для этого достаточно несколько раз сместитьвдоль столбца соответствующие значения из однородного набора, взятые по модулю 6 и 3.

Витоге получается искомый покрывающий набор из 90 элементов, а значит — минимальныйвозможный.В общем случае для построения покрывающих наборов любой конфигурации,однородных и неоднородных, можно использовать эвристические алгоритмы. Одна извозможных эвристик при построении набора из CA(t, n1, …, nk) — построить сначала всевозможные комбинации из t значений параметров, а затем последовательно пытатьсядобавить новые столбцы, добавляя строки только при необходимости, пока не получимискомый набор.

Такой алгоритм называется жадным и выглядит примерно так.Упорядочим n1, …, nk по убыванию и построим исходную таблицу из всех возможныхкомбинаций значений первых t параметров.1. Если неиспользованных параметров нет — выдаем построенный набор в качестверезультата.Если есть еще неиспользованные параметры, берем первый из них. Строим столбецего значений произвольным образом.2. Вычисляем покрываемые комбинации из значений t уже имеющихся параметров, вкоторых последним параметром является только что добавленный. Если можнорасширить это множество за счет замены значений в только что построенном столбце,делаем это.Если покрыты все возможные комбинации значений t параметров с использованиемдобавленного, идем в пункт 1.Иначе идем в пункт 3.3. Построим новую строку с использованием любой из оставшихся непокрытымикомбинаций значений t параметров с использованием добавленного псоледним.

Еслив ней есть неопределенные значения параметров, определяем их так, чтобы при этомпокрылось как можно больше других непокрытых комбинаций.Добавляем построенную строку к таблице и выбрасываем из множества непокрытыхкомбинаций все, покрываемые ею.Если больше нет непокрытых комбинаций, идем в пункт 1.Иначе возвращаемся в начало пункта 3.Этот и другие эвристические алгоритмы построения покрывающих наборов реализованыв множестве инструментов, как коммерческих, так и доступных свободно, таких, как AETG,TestCover.com, CaseMaker, Pro-test, CATS, IBM Intelligent Test Case Handler, TConfig, TCGJenny (см. [1]).Комбинаторные методы построения тестовых последовательностейРассмотренные выше методы были, в основном, ориентированы на построение тестовыхданных.

Их можно использовать и для разработки более сложных тестов, вводя элементысостояния как дополнительные факторы. Однако при этом надо отдельно заботиться опреобразовании полученных комбинаторных схем в исполнимые тесты. То есть, еслипостроенный тест определяет, что некоторый элемент состояния должен принадлежатьклассу X, разработчик тестов должен сам придумать способ установить этот элемент внужное значение.Существуют и более прямые комбинаторные методы построения тестовыхпоследовательностей, позволяющих покрывать различные состояния тестируемой системы.Наиболее простой такой подход основан на последовательностях де Бройна.Предположим, что в тестируемой системе n операций без параметров, каждая из которыхможет изменять ее состояние.

Каким образом можно построить одну последовательность ихвызовов так, чтобы при этом проверить как можно больше различных вариантов поведениясистемы?Один из возможных ответов — использовать последовательность де Бройна из nзначений глубины k. Это максимально короткая последовательность, которая содержит всевозможные последовательности длины k из n значений в качестве своихподпоследовательностей. Известно, что для любых n и k такие последовательностисуществуют и имеют длину n(k–1)+(k–1). При этом все их подпоследовательности длины kразличны, то есть все возможные последовательности длины k упакованы в такуюпоследовательность максимально плотным образом.Примеры последовательностей де Бройна.n = 2, k = 2 — 00110n = 2, k = 3 — 0001011100n = 2, k = 4 — 0000100110101111000n = 3, k = 2 — 0010211220n = 3, k = 3 — 00010111002012112022210212200n = 4, k = 2 — 00102031121322330Для построения последовательностей де Бройна используют графы де Бройна.

Граф деБройна с параметрами n≥1 и k≥1 B(m, k) — это ориентированный граф с nk–1 вершинами V(n,k) = [0..(n–1)]k–1, являющимися всеми возможными последовательностями из n значенийдлины (k–1), и ребрами E(n, k) = [0..(n–1)]k, являющимися всеми возможнымипоследовательностями из n значений длины k. При этом ребро x1x2…xk-1xk начинается ввершине x1x2…xk-1 и заканчивается в вершине x2…xk-1xk.Примеры графов де Бройна изображены на рисунке ниже.000000000000011000001001001000010000111010100120011211110211222210111101101001000101 101000110210100100001011101110111001100111111110011101111111Рисунок 4.

Графы B(3, 1), B(3, 2), B(2, 3), B(2, 4).Все графы де Бройна — эйлеровы, то есть в них существует путь, содержащий все ребрапо одному разу, с совпадающими началом и концом. Если выписать последовательность,являющуюся первым ребром такого пути, а для каждого следующего ребра добавлять кполученной последовательности последний символ (заметим, что начало длины k–1 этогоребра будет концом получаемой перед ним последовательсноти), получится как разпоследовательность де Бройна.Каждая последовательность де Бройна глубины k для n значений полностью покрываетвсе возможные ситуации в тестируемой системе с n операциями, если предположить, что ееповедение полностью определяется последними k вызванными операциями.Литература[1] http://www.pairwise.org/tools.asp.