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

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

2

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТЕСТИРУЕМОЙ РЕАЛИЗАЦИИ ПРОТОКОЛОВ ИНФОРМАЦИОННОГО ОБМЕНА

Парамохина Т.М.

The mathematical model of tested realization of information exchange protocols which based on not determined final automatic device (NDFAD) model with predicates in the form of integer inequalities is presented, and its properties are investigated. Formal statement of testing problem for reports with an establishment of connection and correction of mistakes is given. The analysis of procedure of test sequence NDFAD generation with predicates in the form of integer inequalities is considered.

целочисленное неравенство протокол автоматическое устройство

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

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

В описании ПИО можно выделить два основных аспекта:

- логическую характеристику ПИО, как описание кодирования протокольных блоков данных, пересылаемых между логическими объектами;

- процедурную характеристику ПИО, как описание поведения логических объектов протокола [1] .

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

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

Рисунок 1 - Функциональная схема протокола информационного обмена, описываемого автоматом

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

Рассмотрим множество тестируемых объектов J*. Будем считать, что каждый объект J из множества J* обладает следующими свойствами:

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

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

При тестировании сравниваются эталонная модель и объект, представленные конечными автоматами E_э и E_j , на основе понятия псевдо-эквивалентности конечных автоматов. Процедура тестирования заключается в применении к объекту тестовой последовательности г Г; Г - множество тестовых последовательностей. Под тестовой последовательностью будем понимать последовательность пар входного и выходного сигналов:

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

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

.

При построении теста возникает подзадача достижения выбранного перехода эталонной модели из начального состояния s₀. Выполнение перехода НКА происходит при выполнении предиката перехода. В общем случае вид предиката перехода расширенного автомата может быть произвольным. Например, предикат может представлять собой булеву функцию. Решение же общего случая булева уравнения можно найти только с помощью полного перебора значений переменных. Трудоемкость перебора может быть сокращена за счет выбора предикатов специального вида, например, линейных.

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

НКА с предикатами в виде целочисленных линейных неравенств назовем расширенный конечный автомат , где:

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

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

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

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

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

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

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

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

Вычислительная сложность поиска покрытия перехода в НКА с произвольными предикатами переходов составляет . Nt - среднее количество переходов, исходящих из одного состояния; L - длина покрывающего пути; Rx - мощность множества сигналов одного типа. Вычислительная сложность поиска покрытия перехода в НКА с предикатами в виде целочисленных линейных неравенств составляет .

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

ЛИТЕРАТУРА

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

2.Еременко В.Т. Концепция обнаружения и коррекции логических ошибок в реализациях профилей протоколов безопасности // Телекоммуникации - 2003. - №8. - С.30-35.

3.Еременко В.Т., Парамохина Т.М. Методика оценки неопределенных данных при аттестационном тестировании реализации профилей протоколов информационного обмена // Вестник компьютерных и информационных технологий - 2005. - №8. - с.45-48.

4.Фунтиков В.Б. Проблемы автоматизированного построения аттестационных тестов для протоколов передачи данных. - сборн. «Перспективы развития российского сегмента Интернет», деп. в ЦНТИ «Информсвязь», №2166 от 14.04.2000. - с.38-49.

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