Лекции. Тестирование ПО (all in one) (1186159), страница 27
Текст из файла (страница 27)
Кроме того, уже видно, что baba является UIO-последовательностью для 2, а добавив ba кпоследовательностям aba и aaba, мы сможем разделить группу состояний {0,4}.Далее, уже ясно, что разделяющая последовательность не может состоять только изстимулов a, поскольку такая последовательность всегда оставляет группы {0,2,4} и {1,3,5}неразличимыми, но применив b в любом месте, мы «слепим» 3 состояния, два из которыхпринадлежат одной из таких групп. Поэтому у этого автомата нет статической различающейпоследовательности.Суммируем получаемые UIO-последовательности:0 — aababa/xyxyxy1 — ababa/yxyxy2 — baba/xyxy, aababa/xyxyx3 — ababa/yxyxx4 — aaba/xyxx5 — aba/yxxИз них можно построить адаптивную различающую последовательность. В качествелистовых вершин добавлены исходные состояния после получения соответствующихпоследовательностей реакций.axaybxybaxxax45yybxbaxxax23yy10Если число состояний автомата равно n, а число стимулов — p, то его адаптивнуюразличающую последовательность можно вычислить или показать, что ее не существует(при помощи несколько модифицированного алгоритма), за O(pn2) действий.
Еслиадаптивная последовательность получается, она имеет длину не более n(n–1)/2Если различающая последовательность автомата существует, она может иметьэкспоненциальную от числа его состояний длину.UIO-последовательности, если существуют, тоже могут иметь экспоненциальную длину.Диагностическое множество всегда может быть построено за время O(pn2), при этом внем содержится не более (n–1)-й последовательности длины не более n.Установочные последовательностиПостроение тестовДля построения тестов на соответствие некоторому автомату нужно его знать. Такойавтомат при тестировании называется спецификацией.Мы предполагаем, что реальное поведение тестируемой системы, включающее всеошибки, если они есть, может быть полностью адекватно представлено некоторым конечнымавтоматом.
Этот автомат называется реализацией. Мы не знаем, как он устроен, но в ходетестирования хотим проверить, эквивалентен он спецификации или нет.Чтобы тестирование стало возможно и реализации, и спецификация должныудовлетворять ряду требований.В этом курсе рассматриваются методы тестирования только для детерминированныхавтоматов, поэтому далее будем предполагать, что спецификация и реализациядетерминированы.
Методы построения тестов для недетерминированных автоматов тожеесть, но формулируются существенно сложнее.Поскольку мы хотим только проверить эквивалентность поведения, нам все равно, какойиз эквивалентных автоматов брать в качестве спецификации. Поэтому можно считать, чтоспецификация минимальна.Кроме того, можно предполагать, что в начале работы тестов реализация находится вначальном состоянии и алфавиты стимулов и реакций у спецификации и реализациисовпадают. Если последнее не выполнено, мы любую реакцию реализации, непринадлежащую алфавиту реакций спецификации, можем рассматривать как ошибку, астимул, не являющийся стимулом спецификации, мы просто не будем подавать.Чтобы не возникало неопределенности при применении стимулов в неизвестныхсостояниях, будем считать, что и спецификация, и реализация полностью определены, тоесть всегда можно применять все входные символы.Наконец, чтобы суметь вернуться в исходное состояние, попробовав один из тестов,нужно считать, что либо спецификация и реализация сильно связны, то есть из любого ихсостояния можно, двигаясь по переходам, попасть в любое другое, либо что к обеимприменимо специальное действие reset (далее обозначаемое R), которое переводит автоматиз любого состояния в начальное и не содержит ошибок.При наложенных ограничениях, однако, любой конечный набор тестов будетнедостаточен, если не ограничить размер реализации, например, число состояний в ней.
Еслиспецификация конечна и задан конечный набор тестов для проверки соответствия ей, мывсегда можем построить цепочку состояний, уводящую от начального, и длинную настолько,что применение всех заданных тестов закончится, не дойдя до какого-то ее состояния. Вот вэтом состоянии можно сделать переход, дающий различие в поведении спецификации иреализации. Рассматриваемый тест не сможет обнаружить такую ошибку. Поэтому нужносчитать, что количество состояний в реализации не превосходит некоторого заданного числаN.Итак, от спецификации требуется•детерминизм;•минимальность;•полная определенность;•сильная связность или наличие reset.От реализации требуется•детерминизм;полная определенность;•сильная связность или наличие reset;•согласованность стимулов и реакций со спецификацией;•согласованность начального состояния;•ограниченность.Кроме этих общих требований можно предполагать наличие вспомогательных действий,облегчающих тестирование.••Одно из таких действий — reset (R), переводящий автоматы в начальное состояние.•Другая возможность — наличие специального действия status (S), котороевозвращает правильный идентификатор текущего состояния автомата и не изменяетсостояние автомата.Наконец, очень полезная возможность — наличие действия set (T), которое имеетпараметр-идентификатор состояния и корректно переводит автомат в это состояние.При наличии всех этих возможностей возможно прямое тестирование, самый простойметод тестирования автоматов.
При тестировании мы хотим проверить эквивалентностьавтоматов, значит нужно убедиться, что любой переход реализации (определяемый своимначальным состоянием и стимулом) ведет себя так же, как и соответствующий переход вспецификации, то есть ведет в такое же состояние и возвращает ту же реакцию.•При прямом тестировании для каждого перехода построим тест, который начинаетсяс установки автомата в начальное состояние этого перехода с помощью set, затемвыполняет сам переход и проверяет итоговое состояние с помощью status.Получаем набор тестов {T(s)aS} для всех s ∈ S, a ∈ I. В каждом таком тесте нужнопроверять, что реализация ведет себя так же, как спецификация, то есть выдает ту жереакцию и тот же идентификатор состояния в ответ на S.
Если для каждого переходаэто так, реализация эквивалентна спецификации.Откажемся теперь от возможности по установке состояния, редко встречающейся напрактике. В этом случае полный тест можно построить при помощи обхода автомата, тоесть пути, проходящего по каждому его переходам по крайней мере один раз. Еслиспецификация сильно связна, ее обход существует.•При тестировании на основе обхода берем одну из входных последовательностей,при применении которой выполняется обходов спецификации. В начале и послекаждого стимула вставим действие S.
Полученный тест проверяет каждый переходспецификации, и если реализация возвращает всегда те же реакции и те жеидентификаторы состояний, она эквивалентна спецификации.При использовании методов прямого тестирования и обхода гипотеза об ограниченностичисла состояний в реализации не используется, поскольку есть мощный инструментнаблюдения реальных состояний — действие status.•a/xa/xb/x01b/yb/ya/y2Построим полные тесты по двум описанным методам для изображенного выше автомата.ПометодупрямоготестированияполучаемпоследовательностьT(0)aST(0)bST(1)aST(1)b ST(2)aST(2)bS.
Выходная последовательность при этом должнабыть равна x0y2x1x0y2y1.Обход изображенного автомата выполняется, например, при применении входнойпоследовательности ababab. По методу обхода получаем тест из входной последовательностиSaSbSaSbSaSbS и корректной выходной последовательности 0x0y2y2y1x1x0.Заметим, что при тестировании с помощью обхода действие status дает существеннуюинформацию, без которой этот метод тестирования не может доказать эквивалентностьавтоматов.a/xa/xb/x0a/x10b/y2b/xb/yb/ya/ya/x1b/ya/y2Рассмотрим два автомата, изображенных выше.
Автомат слева (тот же, что в разобранномвыше примере) будет спецификацией, автомат справа — реализацией. Возьмем другой обходспецификации — bababa. Получаем тест SbSaSbSaSbSaS/0y2y2y1x1x0x0. Напредложенной реализации этот тест дает выходную последовательность 0y2y2y1x1x0x1,которая отличается от корректной только в одном месте — последнем идентификаторесостояния.Легко видеть, что сложность тестирования автомата с n состояниями и p стимуламиметодом прямого тестирования равна 3pn. Для метода обхода она не превосходит 2pn2 исуществуют автоматы, для которых она имеет порядок O(pn2).В следующей лекции рассматриваются более сложные методы тестирования автоматов,предназначенные для тех случаев, когда нет надежно работающих действий status и reset.Литература[1] M.
Broy, B. Jonsson, J.-P. Katoen, M. Leucker, A. Pretschner (eds.). Model Based Testing ofReactive Systems. LNCS 3472, Springer, 2005.[2] В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. Введение в теорию автоматов.М.: Наука, 1985.Тестирование на основе моделейВ. В. КуляминЛекция 7. Автоматные методы построения тестов.ПродолжениеНапомним общий контекст различных методов тестирования на основе конечныхавтоматов.Рассматривается описание требований к поведению тестируемой системы,представленное в виде конечного автомата, называемого спецификацией. Реальноеповедение тестируемой системы, со всеми имеющимися в ней ошибками, также может бытьполностью смоделировано конечным автоматом, называемым реализацией. Реализациянеизвестна, известно только, что это конечный автомат, удовлетворяющий ряду условий.Задача состоит в построении как можно более компактного набора тестов — входныхпоследовательностей (и соответствующих им в спецификации выходных), — позволяющихотличить реализацию от спецификации всякий раз, когда они не эквивалентны.Соответственно, если поведение реализации на этом наборе тестов не будет отличаться отповедения спецификации, можно быть уверенным, что они эквивалентны.На спецификацию и реализацию накладываются дополнительные ограничения.Спецификация•детерминирована;•минимальна;•полностью определена;сильно связна или имеет действие reset(R), достоверно приводящее из любогосостояния в начальное.От реализации требуется•детерминизм;•полная определенность;•сильная связность или наличие reset;•согласованность стимулов и реакций со спецификацией — входной и выходнойалфавиты реализации те же;•согласованность начального состояния — в начале работы реализация находится вначальном состоянии;•ограниченность — число состояний в реализации не превосходит некоторого числаN.•Методы, использующие resetМетоды построения тестов, рассматриваемые ниже, условно можно разделить наодношаговые или однофазные и многошаговые.
В первых все тесты строятся по одной и тойже общей процедуре, а вторые используют несколько разных процедур или шагов.Одношаговые методыПервый метод построения тестов для автоматов без специальных действий set или statusбыл разработан в 1973 Василевским [3]. Его более понятное изложение на английском языкеприведено в статье Chow [4], поэтому большинство англоязычных авторов дают ссылки наэту статью. В статье Chow этот метод назван W-методом в честь Василевского.Без действия status проверить, что некоторый переход в реализации ведет в состояние,эквивалентное конечному состоянию соответствующего перехода в спецификации,становится не так просто. W-метод использует для этого диагностическое множество W,которое имеется для каждого минимального детерминированного полностью определенногоавтомата (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
