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

Тестирование на основе моделейВ. В. КуляминЛекция 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.Автомат может выполнять некоторую последовательность стимулов следующим образом.Сначала он считается находящимся в начальном состоянии. При получении очередногостимула в некотором состоянии недетерминированным образом выбирается один изпереходов, выходящих из текущего состояния и помеченных принятым стимулом.Следующим состоянием автомата становится конечное состояние выбранного перехода, авовне выдается реакция, которой помечен выбранный переход. Выполнение автомата неопределено, если в текущем состоянии нет переходов, помеченных получаемым стимулом.Автомат называется полностью определенным, если в каждом его состоянии для каждогостимула есть выходящий из этого состояния переход, помеченный этим стимулом.Автомат детерминирован, если в каждом его состоянии для каждого стимула есть неболее одного выходящего из этого состояния перехода, помеченного этим стимулом.Автомат наблюдаемо детерминирован, если в каждом его состоянии для каждого стимула икаждой реакции есть не более одного выходящего из этого состояния перехода, помеченногоэтим стимулом и этой реакцией.В детерминированном автомате текущее состояние и принятый стимул однозначноопределяют новое состояние автомата и выдаваемую реакцию.

В наблюдаемодетерминированном новое состояние можно однозначно определить, зная предыдущее,принятый стимул и выданную реакцию.Для детерминированного автомата (S, s0, I, O, T) пусть δ и λ обозначают функциипереходов и вывода, т.е. (s1, i, o, s2) ∈ T тогда и только тогда, когда δ(s1, i) = s2, и λ(s1, i) = o.Оба этих отображения можно расширить до отображений состояния и принятойпоследовательности стимулов в последовательность реакций и итоговое состояние.

Именно,для состояния автомата s ∈ S и последовательности входных символов α ∈ Ι* определим δ(s,α) ∈ S и λ(s, α) ∈ O* рекурсивно следующим образом.Если α — пустая последовательность ε, то δ(s, α) = s и λ(s, α) = ε.Если α — непустая и α = α’a, где α’ ∈ Ι* и a ∈ Ι, то δ(s, α) = δ(δ(s, α’), a) и λ(s, α) = λ(s,α’)λ(δ(s, α’), a).Конечный автомат реализует некоторое соответствие последовательностей символов из Iи последовательностей символов из O, φ ⊆ I*×O*. Это соответствие называется егоповедением. Для детерминированных автоматов φ = λ(s0, ⋅), то есть поведение являетсяотображением входных последовательностей в выходные для начального состояния.С точки зрения внешнего наблюдателя, не имеющего возможности «увидеть» текущеесостояние автомата, два автомата с одинаковым поведением неотличимы. Точно также длянего неотличимы состояния, в которых на одну и те же последовательности входныхсимволов всегда может быть выдана одна и та же последовательность реакций.

Такиесостояния (даже в разных автоматах) называются эквивалентными или неотличимыми.Автоматы называются эквивалентными, если эквивалентны их начальные состояния.Для любого автомата можно построить эквивалентный ему наблюдаемодетерминированный автомат. Этот факт доказывается примерно так же, как возможностьиспользовать детерминированный автомат в качестве распознавателя регулярного языка.Понятно, что внешнему наблюдателю отличить друг от друга эквивалентные автоматыневозможно. Чаще всего, это и не нужно, поскольку автомат обычно предназначен как раздля того, чтобы реализовывать некоторое соответствие между входными и выходнымипоследовательностями, и любой автомат, делающий это правильно, считается подходящим.Поэтому с точки зрения тестирования автоматов важен только их класс эквивалентности.В каждом классе эквивалентности автоматов есть единственный (с точностью доизоморфизма, т.е. взаимно-однозначного отображения состояний, сохраняющего начальноесостояние и сопоставляющего эквивалентные) автомат с минимальным числом состояний.Такой автомат называют минимальным или приведенным.

При тестировании обычнопытаются проверить соответствие как раз минимальному автомату, описывающемутребуемое поведение тестируемой системы.Специальные типы входных последовательностей автоматовЧтобы уметь проверять соответствие поведение неизвестного автомата заданному, нужноуметь различать автоматы, у которых различия в поведении есть. Для этого используетсянесколько техник, основанных на специфических входных последовательностях.Далее все определения даются для детерминированных автоматов. Для некоторых из этихпонятий есть аналоги для автоматов общего вида, но их определения более сложны.Идентификация состоянийРазличающая последовательность (distinguishing sequence) конечного автомата — этотакая конечная последовательность стимулов d ∈ Ι*, что соответствующие ейпоследовательности реакций в разных состояниях автомата разные.

То есть, ∀s1, s2 ∈ S s1 ≠ s2⇒ λ(s1, d) ≠ λ(s2, d).a/xa/xb/x01b/yb/ya/y2Рисунок 1. Пример конечного автомата, имеющего различающую последовательность.Например,вавтомате,изображенномнарисункевышеразличающейпоследовательностью является последовательность ab, поскольку выполнено λ(0, ab) = xy,λ(1, ab) = xx, λ(2, ab) = yy.Адаптивной последовательностью в алфавитах I и O называется дерево с корнем, чьивершины помечены элементами I, а ребра помечены элементами O. Длиной адаптивнойпоследовательности называется максимальное число вершин в цепочках ее вершин от корнядо листовой.К конечному автомату в определенном состоянии можно применять не только обычныепоследовательности, но и адаптивные.

Результатом такого применения можно считатьотображение цепочки вершин адаптивной последовательности, начинающейся от корня ипродолжающейся вдоль его ребер, в выходной алфавит автомата. На это отображениенакладывается следующие два ограничения.•Если оно определено для некоторой вершины и его значение совпадает с меткойодного из ведущих из нее ребер, оно должно быть определено и для конца этогоребра.•Если оно определено для одного из потомков некоторой вершины, оно должны бытьопределено и для самой вершины и значение его на этой вершине должно совпадатьс пометкой ребра, ведущего к указанному потомку.Интуитивно применение адаптивной последовательности можно описать так: мыприменяем к автомату последовательно, начиная от корня, стимул, стоящий в очереднойвершине, смотрим на полученную реакцию, и если она совпадает с пометкой одного изребер, ведущих из текущей вершины, идем по нему и применяем стимул, стоящий в егоконце, и т.д.Обычная различающая последовательность называется также статической различающейпоследовательностью.

Адаптивной различающей последовательностью автомата называетсятакая адаптивная последовательность в его алфавитах стимулов и реакций, что результаты ееприменения во всех состояниях различны.Например, для представленного выше автомата в качестве адаптивной различающейпоследовательности можно взятьxa⎯⎯→bДлина этой адаптивной последовательности такая же, как у статической, но она позволяетбыстрее определить состояние 2 — для этого достаточно получить y в ответ на a.Различающие последовательности, как статические, так и адаптивные, позволяютоднозначно определять состояние автомата, в котором они были применены.

Однако не увсякого автомата они есть. Ясно, что из существования статической различающейпоследовательности следует существование адаптивной. Более того, есть примерыавтоматов, у которых нет статической различающей последовательности, но есть адаптивная.Ниже показан пример автомата, у которого нет даже адаптивной различающейпоследовательности.a/xb/ya/x01b/xb/xb/y3a/y2a/yРисунок 2. Пример автомата без различающей последовательности.Чтобы убедиться в этом, достаточно проанализировать результаты применения a и b (поотдельности) к этому автомату.

Различающая последовательность не может начинаться с a,поскольку после этого стимула перестают быть различимы пары состояний 0 и 1, 2 и 3 —после принятия a в любом из состояний пары автомат оказывается в одном и том жесостоянии, выдав при этом одну и ту же реакцию. Точно так же b «слепляет» пары состояний0 и 3, 1 и 2, поэтому различающая последовательность не может начинаться с b.Чтобы различать состояния при отсутствии различающей последовательности,необходимы другие техники.Последовательностью однозначных входов/выходов или UIO-последовательностью(unique input-output sequence) для данного состояния s называется такая последовательностьстимулов u, что результат ее применения в состоянии s отличается от результатов ееприменения во всех других состояниях.