Lecture06 (Лекции в ПДФ), страница 2

То есть, ∀s1 ∈ S s1 ≠ s ⇒ λ(s, u) ≠ λ(s1, u).Различающая последовательность является UIO-последовательностью сразу для всехсостояний автомата. В автомате, изображенном на Рис. 1, UIO-последовательностью длясостояния 1 является также b, а для состояния 2 — a.Есть автоматы, в которых нет различающих последовательностей, ни статической, ниадаптивной, но для каждого состояния есть UIO-последовательность. К сожалению, бываюти автоматы, ни одно состояние которых не имеет UIO-последовательности.

Примеризображен на Рис. 2.В таких случаях можно использовать характеризующее или диагностическое множествопоследовательностей (characterizing set) W автомата. Это такое множество входныхпоследовательностей, что для каждых двух разных состояний автомата в нем найдетсяпоследовательность, результаты применения которой в этих состояниях различны.

То есть,∀s1, s2 ∈ S s1 ≠ s2 ⇒ ∃α ∈ W λ(s1, α) ≠ λ(s2, α).Диагностическое множество всегда существует для минимального автомата, поскольку внем поведение в разных состояниях отличается. Для автомата, имеющего различающуюпоследовательность d, можно в качестве W взять {d}. Для автомата, в котором все состоянияимеют UIO-последовательности любое множество, содержащее по UIO-последовательностидля каждого состояния, является диагностическим.

Для автомата, изображенного на Рис. 2,диагностическим является множество {a, b} — легко проверяется, что возможные реакции наэто множество во всех его состояниях различны.Для вычисления статической и адаптивной различающих последовательностей, UIOпоследовательностей и диагностического множества можно использовать следующийалгоритм.Упорядочим каким-либо образом множество I. Перебираем входные последовательностив лексикографическом порядке.

Для каждой из них определяем возможные выходныепоследовательности при ее применении в разных состояниях, разбиение множествасостояний на группы состояний, для которых выходные последовательности одинаковы, атакже покрытие множества состояний группами состояний, в которых можно оказатьсяпосле получения определенной выходной последовательности. Делать это можноитеративно, основываясь на результатах таких же вычислений для префиксов даннойпоследовательности.b/xb/x0a/x1a/y2a/x, b/xa/y, b/x5a/x, b/x4a/y, b/x3Рассмотрим автомат, изображенный на рисунке выше. Попробуем применить к нему этоталгоритм.abaaabbabb0 x/1x/0xy/2xx/0xx/1xx/01 y/2x/0yx/3yx/3xx/1xx/02 x/3x/3xy/4xx/4xy/4xx/43 y/4x/4yx/5yx/5xx/5xx/54 x/5x/5xy/0xx/0xy/0xx/05 y/0x/0yx/1yx/0xx/1xx/0{0,2,4}x{0,2,4}xy {0,2,4}xx {0,1,3,5}xx{1,3,5}y{1,3,5}yx {1,3,5}yx {2,4}xyx{1,3,5}yx{1,3,5} xx{0,4}xx{1,5}y{0,2,4}xy{0,2,4} yx{0,3,5} xy{0,4}После построения разбиений для всех последовательностей длины 2 видно, чтомногократное применение a не будет давать новой информации, просто сдвигая текущеесостояние по циклу.

Если же использовать 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Рассмотрим два автомата, изображенных выше.