Lecture04 (Лекции в ПДФ)

Тестирование на основе моделейВ. В. КуляминЛекция 4. Основные техники построения тестовВ этой лекции рассматриваются основные техники построения тестов и используемыедля этого модели. Начнем с разных видов моделей.Виды моделей, используемых при построении тестовДля разработки тестов необходима информация о корректном поведении тестируемойсистемы и о разнообразии ситуаций, которые могут возникать при ее взаимодействии сдругими системами или людьми. Чаще всего при использовании моделей для построениятестов различные тестовые ситуации стараются выделить из структуры этих моделей.

Самиже модели описывают, прежде всего, поведение системы или требования к этому поведению.Все модели, используемые для описания поведения ПО делятся на два основных вида —исполнимые (или операционные) и логико-алгебраические.Исполнимые модели дают описание поведения системы в терминах ее действий,определяя как она работает: какие воздействия она получает извне, что делает в ответ, какиереакции выдает. Такое описание либо можно непосредственно выполнить, либо для еговыполнения нужна некоторая виртуальная машина. Обычно из самого вида моделиустройство такой машины примерно понятно, хотя многие детали ее устройства могутоказаться нетривиальны.

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

Чаще всего они не могут быть выполненынепосредственно.Есть, однако, промежуточные разновидности моделей, которые хотя имеют логикоалгебраическую природу, но и достаточно легко исполнимы, или совмещают элементыобоих классов моделей.Исполнимые моделиПрактически все виды исполнимых моделей являются обобщенными и расширеннымиавтоматами разных типов.Конечные автоматы (Finite State Machines, FSM, Finite Automata).Конечный автомат — набор (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.Автомат работает следующим образом. В начале он считается находящимся в начальномсостоянии. На вход он получает извне некоторую последовательность стимулов. Приполучении очередного стимула в некотором состоянии недетерминированным образомвыбирается один из переходов, помеченных принятым стимулом и выходящих из текущегосостояния.

Очередным текущим состоянием автомата становится конечное состояниевыбранного перехода, и наружу выдается реакция, которой помечен выбранный переход.Выполнение автомата не определено, если в текущем состоянии нет переходов, помеченныхполучаемым стимулом.Таким образом, автомат реализует некоторое соответствие последовательностейсимволов из I и последовательностей символов из O, φ ⊆ I*×O*. Это соответствие, однако,описывается не прямо, а через возможные сценарии работы автомата. Часто его называютповедением автомата и рассматривают автомат как способ реализации этого соответствия.a/y0b/xa/x1b/zb/ya/z2b/x3a/yНа рисунке выше изображен конечный автомат с множеством состояний {0,1,2,3},множеством стимулов {a,b}, множеством реакций {x,y,z} и множеством переходов{<0,a,x,1>, <0,b,x,2>, <1,a,y,0>, <1,b,z,2>, <2,a,z,0>, <2,b,x,3>, <3,a,y,3>, <3,b,y,1>}.Реализуемое им соответствие φ является отображением всех возможных конечныхпоследовательностей {a,b}* в конечные последовательности {x,y,z}*.

Например, φ(aaaaaa) =xyxyxy, φ(abaabaaba) = xzzxzzxzz, φ(bbbbbb) = xxyzxy.Обобщением конечных автоматов являются необязательно конечные автоматы, в которыхмножества состояний, стимулов и реакций уже не всегда являются конечными.Другое обобщение — системы размеченных переходов или просто системы переходов(Labeled Transition Systems, LTS).

В обычных системах переходов не различают стимулы иреакции, называя их просто действиями. Ниже определяется система переходов состимулами и реакциями (Input Output Labeled Transition System, IOLTS) — такие системыболее естественно моделируют По с точки зрения тестирования, при котором всегда естьвоздействия на систему и есть выдаваемые ей реакции на эти воздействия.Конечная система переходов со стимулами и реакциями — набор (S, s0, I, O, τ, T), гдеS — конечное множество состояний системы;s0 — элемент S, называемый начальным состоянием;I — конечное множество входных символов, входов или стимулом, I называют входнымалфавитом системы;O — конечное множество выходных символов, выходов или реакций, O называютвыходным алфавитом системы; I и O не пересекаются;τ — некоторый символ, не являющийся элементом I и O, он называется пустым иливнутренним действием;T ⊆ S×(I∪O∪{τ})×S — множество переходов системы. Каждый переход — тройка (s1, a,s2) — выходит из s1, ведет в s2, и помечен действием a, которое может быть стимулом,реакцией или внутренним действием.

Этот переход изображают стрелкой, ведущей из s1 и вs2 и помеченной a. При этом, чтобы отличить стимулы от реакций, первые обычноизображают с вопросительным знаком, а вторые — с восклицательным: ?a, ?b, !x, !y.Для систем переходов тоже определено выполнение. Сначала система находится вначальном состоянии. На вход она получает извне некоторую последовательность стимулов.При получении очередного стимула в некотором состоянии недетерминированным образомвыбирается один из следующих вариантов.•Система может выполнить переход, помеченный принятым стимулом и выходящийиз текущего состояния. При этом принятый стимул выбирается из входнойпоследовательности, и очередным стимулом становится следующий за ним.•Система может выполнить переход, помеченный реакцией.

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

Нарисунке ниже показана конечная система переходов, реализующая то же поведение, что ипредставленный слева автомат.0b/xa/x10b/z!zb/ya/z2b/x3a/y6!ya/y8?a?b5!z!x?a!x4?b1711!y!y?b?a2?b9!x310?aВообще верно, что любое поведение конечного автомата может быть реализованоконечной системой переходов с теми же входным и выходным алфавитами, а обратное —неверно. Некоторые конечные системы переходов не имеют конечных автоматов с таким жеповедением.Так же, как и автоматы, системы переходов могут быть бесконечными — с бесконечныммножеством состояний или алфавитами.Другие обобщения автоматов связаны с введением дополнительных структур, например,выделением части информации о состоянии в отдельные переменные, а также введениемпараметров стимулов и реакций.