Лекция 5. Комбинаторные методы построения тестов (1186164), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Такой алгоритм называется жадным и выглядит примерно так.Упорядочим n1, …, nk по убыванию (IPO) и построим исходную таблицу из всехвозможных комбинаций значений первых 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.Примеры графов де Бройна изображены на рисунке ниже.000000000010000001001001001000010000111010100120011211110211222210111101101001000101 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.

Характеристики

Список файлов лекций