лекции, страница 23
Описание файла
PDF-файл из архива "лекции", который расположен в категории "". Всё это находится в предмете "тестирование на основе моделей" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 23 страницы из PDF
Если же использовать b много раз, все состояния просто «слипнутся».Поэтому дальше имеет смысл пробовать только какие-то сочетания a и b.aababaabbbaababaaba0 xyx/3xxx/1xxx/0xxy/2xxx/0xyxy/41 yxx/4yxy/4yxx/4xxy/2xxx/0yxxx/52 xyx/5xxx/5xxx/5xyx/5xyx/5xyxy/03 yxx/0yxy/0yxx/0xxy/0xxx/0yxxx/14 xyx/0xxx/1xxx/0xyx/1xyx/0xyxx/15 yxx/0yxx/1xxx/0xxy/2xxx/0yxxx/1{0,2,4}xyx {0,2,4}xxx {0,2,4,5}xxx {0,1,3,5}xxy {0,1,3,5}xxx {0,2}xyxy{1,3}yxx{2,4}xyx{2,4}xyx{1,3,5}yxxx{1,3,5}yxx {1,3}yxy{4}xyxx{5}yxxxxx{0,5}xxy{0,2}xxx{0}xyxy{0,4}xyx{0,3,5} xxx{1,5}yxx{0,4}xyx{1,5}xyx{0,5}yxxx{1,5}yxx{0,4}yxy{0,4}xyxx{1}yxx{1}Теперь мы обнаружили UIO-последовательности у двух состояний — aba для 5 и aaba для4. Кроме того, уже видно, что 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.Тестирование на основе моделейВ.