лекции, страница 21

Уже видно, чтопотребуется как минимум 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Тестирование на основе моделейВ.

В. КуляминЛекция 6. Автоматные методы построения тестов. ОсновныепонятияАвтоматные методы построения тестов основаны на предположении, что реальноеповедение тестируемой системы может быть полностью описано некоторым автоматом. Ввиде автомата описывается также требуемое ее поведение, после чего ставится рядэкспериментов, состоящих в выполнении определенных последовательностей воздействий, сцелью выяснить, отличается ли реальное поведение от требуемого.В рамках автоматных методов предлагаются различные способы построения такихнаборов тестовых последовательностей, что корректная работа тестируемой системы на нихпозволяет при некоторых ограничениях уверенно утверждать, что она корректно работаетвсегда. Основная проблема здесь — построить достаточно небольшой такой набор.В целом автоматные методы хорошо автоматизируются, обеспечивают хорошую полнотутестирования и позволяют находить весьма сложные ошибки.

Однако, они требуют наличияточного и полного описания требований к поведению тестируемой системы, определенныхнавыков работы с автоматными моделями ПО от разработчиков тестов и некоторых затрат навыполнение тестов. При росте сложности используемых моделей затраты на разработкутестов при помощи таких методов возрастают нелинейно.Самой простой разновидностью автоматов являются конечные автоматы.

Большинствоавтоматных методов построения тестов основано именно на них. На всякий случай повторимопределение конечного автомата из Лекции 4.Конечный автомат — это набор (S, s0, I, O, T), гдеS — конечное множество, элементы которого называются состояниями автомата;s0 — элемент S, называемый начальным состоянием;I — конечное множество, элементы которого называются входными символами, входамиили стимулами, само I называют входным алфавитом автомата;O — конечное множество, элементы которого называются выходными символами,выходами или реакциями, само O называют выходным алфавитом автомата;T ⊆ S×I×O×S — множество переходов автомата.

Каждый переход — четверка (s1, i, o, s2)— имеет начальное состояние s1, конечное состояние s2, стимул i и реакцию o. Говорят, чтоон выходит из s1 и ведет в s2, помечен стимулом i и реакцией o. Этот переход изображаютстрелкой, ведущей из s1 и в s2 и помеченной i/o.Автомат может выполнять некоторую последовательность стимулов следующим образом.Сначала он считается находящимся в начальном состоянии. При получении очередногостимула в некотором состоянии недетерминированным образом выбирается один изпереходов, выходящих из текущего состояния и помеченных принятым стимулом.Следующим состоянием автомата становится конечное состояние выбранного перехода, авовне выдается реакция, которой помечен выбранный переход.

Выполнение автомата неопределено, если в текущем состоянии нет переходов, помеченных получаемым стимулом.Автомат называется полностью определенным, если в каждом его состоянии для каждогостимула есть выходящий из этого состояния переход, помеченный этим стимулом.Автомат детерминирован, если в каждом его состоянии для каждого стимула есть неболее одного выходящего из этого состояния перехода, помеченного этим стимулом.Автомат наблюдаемо детерминирован, если в каждом его состоянии для каждого стимула икаждой реакции есть не более одного выходящего из этого состояния перехода, помеченногоэтим стимулом и этой реакцией.В детерминированном автомате текущее состояние и принятый стимул однозначноопределяют новое состояние автомата и выдаваемую реакцию.