Математическое моделирование протоколов информационного обмена на основе расширенных конечных автоматов

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Математическое моделирование протоколов информационного обмена на основе расширенных конечных автоматов

Еременко В.Т., Парамохина Т.М., Кириченко О.Е.

Современный этап развития предприятий электронной промышленности характеризуется повышением функциональной насыщенности средств информационного обмена (СИО). Это серьезно усложняет процессы их аттестационных испытаний, проводимых в заводских условиях специализированными лабораториями. Основной задачей аттестационных испытаний СИО является определение их соответствия техническим условиям или стандартам. Если решение задач бухгалтерских, маркетинговых и прочих офисных приложений успешно решается при помощи стандартных протоколов локальных компьютерных сетей, то привнесение в АСУП задач автоматизированного управления технологическими процессами предъявляет новые требования к ее функционированию: возможность работы в режиме реального времени, максимальный приоритет при работе с объектом управления, надежность протоколов связи с объектами и самотестирование системы на предмет утери связи с контролируемым процессом.

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

Основными характеристиками, определяющими выбор методов и средств аттестационных испытаний, являются время тестирования и полнота проверки свойств протоколов информационного обмена (ПИО). Аттестационные испытания должны проводиться в максимально сжатые сроки и без потери качества.

Одним из перспективных направлений сокращения времени разработки аттестационных тестов для протоколов информационного обмена является использование методов автоматизированной генерации на основе модели конечного автомата. Автоматизированная генерация тестов позволяет сократить расходы на разработку тестов и уменьшить количество ошибок в получаемых тестах.

При постановке задачи аттестационных испытаний ПИО предполагается, что протокольный блок данных (ПБД) с ошибками кодирования отображается в некорректные сигналы. Поэтому для составления тестов достаточно рассматривать только модель поведения протокола.

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

Выделены два основных подхода к обработке некорректных сигналов по умолчанию:

- при получении некорректных сигналов протокол не меняет своего состояния, при этом они либо игнорируются, либо выдается сигнал об ошибке;

- при получении некорректных сигналов протокол переходит в состояние восстановления от ошибки.

Формальная постановка задачи аттестационных испытаний состоит в следующем: рассматривается множество тестируемых объектов J*. Каждый объект J из множества J* можно представить конечным автоматом, при этом каждый объект J из множества J* обладает следующими свойствами:

- для каждого объекта J J* можно выделить множество входных сигналов X и множество выходных сигналов Y. Множество последовательностей входных сигналов (входных последовательностей) будем обозначать X*; множество входных последовательностей будем обозначать Y*;

- на объекте J J* может быть проведен эксперимент, заключающийся в установке J в начальное состояние (инициализации объекта), подаче входной последовательности б X* и наблюдении выходной последовательности в Y*.

При аттестационном испытании сравниваются эталонная модель и объект, представленные конечными автоматами Eэ и Ej , на основе понятия их псевдо-эквивалентности. Процедура испытания заключается в применении к объекту тестовой последовательности г с целью выявления ошибок. Под тестовой последовательностью в исследовании понимается последовательность соответствующих пар входного и выходного сигналов:

.

Тестовая последовательность должна быть построена таким образом, чтобы при тестировании выносился положительный вердикт, если эталонная модель Eэ и автомат Ej, моделирующий объект, псевдо-эквивалентны и отрицательный вердикт в противном случае, что отражается свойством:

.

Подтверждение псевдо-эквивалентности эталонной модели Eэ и модели объекта Ej заключается в проверке наличия в модели объекта всех переходов, представляемых в таблице переходов эталонной модели. Сравнение таблиц переходов двух автоматов осуществляется по внешнему поведению. При этом используемая входная последовательность должна покрывать все переходы эталонной модели, которая, в свою очередь, должна иметь фиксированное начальное состояние s0. Таким образом, задача анализа аттестационных испытаний может быть сведена к подзадаче достижения выбранного перехода эталонной модели из начального состояния s0. При этом выполнение перехода расширенного конечного автомата происходит при исчислении предиката перехода. В общем случае вид предиката перехода может быть произвольным. Однако трудоемкость перебора может быть сокращена за счет выбора предикатов специального вида, например, линейных.

Рассмотрим модель протокола информационного обмена в виде недетерминированного конечного автомата (НКА) с предикатами. Предлагаемая модель позволяет вводить переменные, в виде множества входных и выходных сигналов и предполагает существование разбиений данных множеств по типу сигнала.

НКА с предикатами назовем расширенный конечный автомат

,

где

- множество входных сигналов; ;

- множество выходных сигналов; ;

S - множество состояний;

- начальное обобщенное состояние , , ;

V - множество внутренних переменных ;

T - функция поведения T: .

Функция поведения T задается как кусочно-линейная функция на множестве . Области входных значений, в которых функция имеет линейный вид, задаются системами линейных неравенств (системами ограничений) , причем область линейности включает только одно значение s S. Вид функции в областях линейности задается линейными функциями (системами присваиваний). Область значений каждой линейной функции включает в себя только одно значение s S. информационный сигнал электронный

Проведённый анализ основных свойств модели показывает, что НКА с предикатами может быть представлен ориентированным графом, вершины которого соответствуют состояниям НКА, а дуги - переходам НКА. Дуги помечены системой ограничений и системой присваиваний. Каждому пути в НКА с предикатами можно поставить в соответствие линейную функцию (систему присваиваний) , имеющую область входных значений, описываемую системой линейных неравенств (системой ограничений) (где SIG - столбец сравнений, состоящий из элементов {>, <, , , =}, а матрицы Lpt и Apt состоят из элементов {0, 1, -1}). При этом система ограничений будет задавать область входных значений пути, а система присваиваний - зависимость значений параметров выходных сигналов от начальных условий и значений параметров входных сигналов.

На основе данной модели разработана методика автоматизированной генерации тестов (рис.1), основанная на эвристических методах: анализа уникальных последовательностей, поиска и исправлении ошибок, включающая этапы: поиска уникальных последовательностей в НКА; поиска уникальной входной области; построения тестового комплекта; оптимизации поиска покрытия перехода в НКА. Для каждого этапа разработаны алгоритмы , позволяющие реализовать методику подготовки тестов на практике.

Для расширенных конечных автоматов разработан ряд методов генерации тестовых последовательностей: уникальных последовательностей (УП); различающих последовательностей и характеристических последовательностей [1]. По типу описываемого протокола данные методы можно разделить на методы, использующие сигнал «надежного сброса», и методы, не использующие сигнал «надежного сброса». Функция «надежного сброса», как правило, присутствует в современных технических средствах в виде возможности выполнения цикла включения/выключения (или перезагрузки устройства). В процессе перезагрузки оперативная память устройства в силу конструктивных особенностей гарантированно очищается, поэтому факт возврата в исходное состояние при перезагрузке не требует дополнительной проверки.

Рисунок 1 - Методика автоматизированной генерации тестов для протоколов информационного обмена

Как правило, в современных устройствах цикл перезагрузки занимает достаточно длительное время - от нескольких секунд до нескольких минут. В таких случаях большую часть времени исполнение теста будет приходиться на перезагрузки устройства. Часто перезагрузить устройство можно только по команде с консоли управления, либо разрывая его цепи питания, что затрудняет исполнение теста в полностью автоматическом режиме. Поэтому тесты, использующие сигнал «надежный сброс» как можно меньше, являются более предпочтительными с практической точки зрения.

Для тестирования протоколов без функции «надежный сброс» были предложены модификации W-метода и UIOv-метода. Данные методы значительно сложнее своих аналогов, использующих «надежный сброс». В то же время более простые методы не позволяют в теории достичь 100%-го покрытия при критерии псевдо-эквивалентности.

Результаты исследования покрытия версии метода УП для протоколов без сигнала «надежный сброс», показывают, что метод УП позволяет при сохранении относительной простоты и тестах небольшой длины достичь практически 100%-го покрытия.

На основе оценки общей длины теста, а также количества сигналов «сброса», включаемых в тест, выполнено обоснование выбора в качестве базового метода тестирования конечного автомата - метода уникальных последовательностей (УП).

Разработан алгоритм поиска уникальных последовательностей в недетерминированном конечном автомате (рис. 2), позволяющий выделить уникальные последовательности из множества D-групп (функция ЕXTRACT, D-группа - множество всех DS-групп (множество всех путей, исходящих из заданного состояния S и помеченных входной последовательностью )); производить генерацию нового пути (функция PATH) и сформировать уникальную последовательность. Рассматриваемый алгоритм поиска УП отличается от известных ранее отсутствием проверки наличия состояний, для которых найденные последовательности сохраняют уникальность.

УП существуют практически для всех известных детерминированных конечных автоматов, моделирующих протоколы информационного обмена. Однако при использовании недетерминированного конечного автомата вероятность нахождения УП снижается, так как при переходе от детерминированного автомата к недетерминированному выполняется объединение группы состояний в одно состояние, а группы входных сигналов - в один сигнал. В связи с этим, для идентификации состояний в НКА с предикатами был введен аналог уникальной последовательности - уникальной входной области (УВО).

Рисунок 2 - Алгоритм поиска УП в недетерминированном автомате

УВО можно интерпретировать следующим образом: не существует таких начальных состояний (s0, ), (si, ) и входных последовательностей таких, что подавая на НКА с предикатами в состоянии (s0, ), a на НКА с предикатами в состоянии (si, ), будут получены одинаковые выходные последовательности.

На основе алгоритма поиска УП для НКА построен алгоритм поиска УВО. Единственным различием в алгоритмах поиска УП и поиска УВО является реализация функции IS_UNIQUE (позволяющей выделять уникальные последовательности), поскольку для поиска УВО используется дополнительный критерий: выполнимости условия уникальности выходной последовательности пути.

Для упрощения процедуры тестирования предлагается структурировать тест по тестируемым состояниям. Полученный при этом тестовый комплект будет представляет собой совокупность тестовых примеров, предназначенных для проверки отдельных переходов. Тестовые примеры объединяются в тестовые группы, идентифицирующие переходы, исходящие из одного состояния.

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

На основе оценки вычислительной сложности алгоритмов генерации теста (рис. 3) сделаны следующие выводы: для произвольного НКА с предикатами поиск тестовой последовательности требует полного перебора всех входных значений, что ведёт к недопустимо большой временной сложности решения задачи (вычислительная сложность поиска покрытия перехода растет экспоненциально). При использовании НКА с предикатами в виде целочисленных линейных неравенств вычислительная сложность поиска покрытия перехода является степенной функцией длины пути и не зависит от диапазона значений параметров входных сигналов, что позволяет значительно ограничить область перебора при генерации тестовой последовательности. Поэтому для данной модели могут быть разработаны реализуемые на практике методы генерации тестовых последовательностей.

Рисунок 3 - Оценка вычислительной сложности алгоритмов поиска покрытия перехода НКА

Экспериментальное применение разработанных модели и методики автоматизированной генерации тестов осуществлялось для протокола ТСР , как наиболее распространенного протокола транспортного уровня, используемого в среде АСУП. Основными функциями ТСР являются сегментация данных пользователя; последовательная нумерация сегментов; повторная передача потерянных и испорченных сегментов; управление скоростью передаваемых данных.

С использованием разработанных моделей и методик была получена тестовая последовательность для протокола ТСР. В результате эксперимента для эмуляции запуска теста было сгенерировано около 5000000 автоматов с внесенными ошибками в конечном состоянии и выходном сигнале переходов. Тестом были выявлены все автоматы, неэквивалентные эталонному. Данный результат позволил сделать вывод о том, что полученный тест имеет покрытие ошибок в конечном состоянии и выходном сигнале переходов близкое к 100%.

Методика автоматизированной генерации для протоколов информационного обмена может использоваться специализированными лабораториями предприятий для оптимизации состава протоколов, сервисов, услуг, функций, а также сокращения сроков интеграции и комплексной отладки специализированных средств информационного обмена.

Литература

1. Еременко, В.Т. Моделирование процессов информационного обмена в распределенных управляющих системах: Монография. [Текст] / В.Т. Еременко, под общ. редакцией И.С. Константинова. // - М.: Машиностроение-1, 2004.- 224 с.

2. Еременко, В.Т. Алгоритмы и процедуры генерации тестирования для протоколов информационного обмена [Текст] /В.Т. Еременко, Т.М. Парамохина // Вестник компьютерных и информационных технологий, 2006. - №12. - М.: Машиностроение. - С.46-50.

3. Еременко, А.В. Автоматизированная генерация аттестационных тестов для реализаций протоколов информационного обмена [Текст] / А.В. Еременко, Т.М. Парамохина // Известия ТулГУ. Серия «Технологическая системотехника». Вып.7. Труды участников Четвертой Международной электронной научно-технической конференции «Технологическая системотехника-2005». - Тула: Издательство ТулГУ, 2006. - C.8-15.

4. Парамохина, Т.М. Математическая модель тестируемой реализации протоколов информационного обмена [Текст] / Т.М. Парамохина // «Информационные технологии в науке, образовании и производстве» (ИТНОП). Материалы международной научно-технической конференции. Т.1. - Орел: Издательство Орел-ГТУ, 2006. - С.161-164.

Размещено на Allbest.ru