автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Исследование и разработка метода аттестационного тестирования протоколов передачи данных



На правах рукописи

гТо ОД

¿ 2 7.-1Г.Л

Фунтиков Василий Борисович

УДК 681.324

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА АТТЕСТАЦИОННОГО ТЕСТИРОВАНИЯ ПРОТОКОЛОВ ПЕРЕДАЧИ ДАННЫХ

Специальность 05.13.13 - Вычислительные машины, комплексы, системы и сети.

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва - 2000

Работа выполнена в Московском техническом университете связи и информатики (МТУСИ), г. Москва

Научный руководитель:

кандидат технических наук,

доцент,

Кремер А.С.

Официальные оппоненты:

доктор технических наук,

профессор,

Лазарев Ю.В.

кандидат технических наук, главный научный сотрудник ЦНИИС, Етрухин Н.В.

Ведущая организация: Ленинградский отраслевой научно-исследовательский институт связи (ЛОНИИС), г. С-Петербург.

Защита состоится _ 13. н. геоо_ _на

заседании диссертационного совета К118.06.02 при Московском Техническом университете связи и информатики по адресу: 111024, Москва, ул. Авиамоторная, д. 8-А, МТУСИ.

С диссертацией можно ознакомится в библиотеке Московского технического университета связи и информатики.

Автореферат разослан _ ¿3.(0, гооо

Ученый секретарь диссертационного совета К118.06.02 кандидат технических наук, профессор еег/с ЕВ. Демина.

^ТП П-1. - ОН, Ы О

Общая характеристика работы

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

Необходимым условием решения проблемы совместимости при использовании оборудования различных производителей является установление единых стандартов на протоколы передачи данных. В России с 1994 г. законом "О связи" введена обязательная сертификация оборудования связи (в том числе используемого в вычислительных сетях) на соответствие российским и международным стандартам. Для проведения сертификационных испытаний на соответствие оборудования стандартам необходима разработка эффективных методов проверки такого соответствия (методов аттестационного тестирования).

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

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

Более перспективной с точки зрения гибкости и выразительной мощности является модель расширенного конечного автомата. Наиболее распространенным языком по описанию расширенных автоматов в области связи является язык моделирования SDL. В настоящее время практически все стандарты МСЭ-Т и ETSI, описывающие аспекты поведения протоколов связи, используют в той или иной степени спецификации на языке SDL. Учитывая быстрое развитие инструментов автоматизированного проектирования системы связи, использующих язык SDL, можно ожидать дальнейшего распространения языка SDL для описания протоколов передачи данных.

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

Целью диссертационной работы является исследование и разработка метода автоматизированной генерации аттестационных тестов для оборудования передачи данных, а также разработка программного средства генерации аттестационных тестов на основе описания протокола передачи данных на языке SDL.

В соответствии с поставленной целью в диссертационной работе решаются следующие основные задачи:

- исследование существующих методов автоматизированной генерации тестовых последовательностей для автоматных моделей протоколов передачи данных и анализ возможности их практического применения;

- анализ задач аттестационного тестирования, формулирование типов ошибок, выявляемых при аттестационном тестировании; исследование проявления данных ошибок во внешнем поведении формальной модели протокола передачи данных;

- исследование возможности упрощения общей модели расширенного автомата, разработка математической модели расширенного линейного перехода;

- разработка алгоритмов генерации тестовых последовательностей на основе полученной модели и оценка вычислительной сложности полученных алгоритмов;

- разработка программных средств, реализующих алгоритм автоматизированной генерации тестов и их апробация на примере генерации аттестационного, теста для протокола TCP. широко используемого в сети Интернет.

Методы исследования. В работе использованы методы математической логики, аппарат теории множеств, аппарат теории графов, теория конечных автоматов, методы математического программирования, методы анализа вычислительных алгоритмов, а также методы объектно-ориентированной разработки программных средств.

Научная новизна. По результатам сравнительного анализа характеристик методов генерации аттестационных тестов протоколов передачи данных на основе автоматных моделей поставлена и решена задача автоматизированной генерации тестов для протоколов передачи данных с параметрами, описываемых расширенным конечным автоматом.

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

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

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

Личный вклад автора. Все основные результаты, изложенные в диссертации, получены автором лично.

Практическая ценность работы заключается в разработке на основе предложенной в диссертации модели линейной системы расширенного перехода программного продукта в среде ОС Windows 95/NT, предназначенного для автоматизации аттестационного тестирования протоколов пакетной передачи данных. Разработанное программное средство может использоваться совместно с графическими редакторами стандартного языка SDL.

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

назначения. Разработанная математическая модель и алгоритмы могут использовать в качестве исходных данных как описание на языке SDL, так и описания расширенных конечных автоматов на других языках (например, Estelle).

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

Теоретические и практические результаты работы использованы в НИР по разработке отраслевых руководящих документов РД 45.134-2000 "Средства технические телематических служб. Общие технические требования", РД 45.46-99 "Технические требования к аппаратуре связи, реализующей функции передачи речевой информации по сетям с маршрутизацией пакетов по протоколу IP", а так же в разработке "Программы и методики сертификационных испытаний интерфейсных плат компьютерной телефонии, подключаемых к ТФОП". утвержденной Минсвязи России, 24.05.2000 г.

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

Апробация работы и публикации. Материалы диссертации докладывались на заседаниях кафедры "Технологии электронного обмена данными" МТУСИ, на научно-технических конференциях профессорско-преподавательского состава и аспирантов МТУСИ в период с 1997 по 2000 г; на международной конференции "Think tank telecom exchange conference", Польша, 1999 г.; на конференции Ассоциации документальной электросвязи "Состояние и перспективы развития Интернета в России", Москва, 2000 г.

По теме диссертации опубликовано 5 печатных работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Диссертация содержит 34 рисунка, 2 таблицы. Основной текст диссертации содержит 120 страниц машинописного текста, библиография состоит из 96 наименований.

Основные положения, выносимые на защиту:

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

2. Разработанный набор алгоритмов позволяет получить на основе описания протокола передачи данных на языке SDL модель линейной системы расширенного перехода, а также сгенерировать тестовую последовательность, отвечающую сформулированному критерию псевдо-эквнвалентности эталонной модели и модели тестируемого объекта. Предложенные алгоритмы позволяют получать тестовые последовательности для описаний протоколов с таймерами.

3. Разработанное программное средство позволяет на практике использовать метод генерации тестов на основе модели линейной системы расширенного перехода для получения аттестационных тестов протоколов пакетной передачи данных. Разработанное формальное описание протокола транспортного уровня TCP на языке SDL в совокупности с полученным программным средством позволяет получить набор аттестационных тестов для протокола TCP, отвечающий формальному критерию псевдо-эквивалентности.

Краткое содержание работы

Во введении обоснована актуальность темы, сформулированы цели и задачи исследования, перечислены основные научные результаты диссертации, приведены практическая ценность и область применения результатов.

Первая глава представляет сравнительный анализ методов аттестационного тестирования реализаций протоколов передачи данных, а также методов автоматизированной генерации тестовых последовательностей для автоматных моделей протоколов передачи данных.

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

конечных автоматах ошибки одного или нескольких видов, такие как: ошибка в выходном сигнале; ошибка в конечном состоянии перехода; ошибка "лишнее состояние".

Среди большинства рассмотренных методов генерации аттестационных тестов для моделей конечных автоматов можно выделить по способу идентификации состояний модели методы уникальных последовательностей 1ЛО; методы различающих последовательностей и методы характеристических последовательностей. По типу описываемого протокола рассмотренные методы можно разделить на методы, использующие сигнал "надежного сброса", и метода, не использующие сигнал "надежного сброса". Проведена оценка длины тестовых последовательностей, получаемых перечисленными методами.

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

Рассмотрены методы генерации тестов для моделей расширенного автомата. Существующие методы генерации тестов для расширенного автомата, как правило, основаны на методах генерации тестов для конечных автоматов. Дополнительно они позволяют учитывать значения переменных и параметры сигналов расширенного автомата и получать детерминированные тесты. Недостатком рассмотренных методов является наличие экспоненциальной зависимости времени генерации тестов от диапазонов значений параметров и переменных.

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

Во второй главе диссертации выполнена формальная постановка задачи и разработана математическая модель линейной системы расширенного перехода (ЛСРП). Исследованы свойства ЛСРП.

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

Рис. 1. Ошибки, выявляемые аттестационным тестированием

В описании протокола пакетной передачи данных можно выделить два основных аспекта:

описание кодирования протокольных блоков данных (ПБД), пересылаемых между логическими объектами;

описание поведения логических объектов протокола.

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

ПБД - протокольный блок данных

Рис. 2. Функциональная схема протокола передачи данных, описываемого автоматом

Дается формальная постановка задачи аттестационного тестирования для расширенного автомата. Рассматривается множество тестируемых объектов I*. Каждый объект .1 из множества Д* можно смоделировать конечным автоматом. На объекте 1 е I* может быть проведен эксперимент, заключающийся в установке 5 в начальное состояние (инициализации объекта), подаче входной последовательности а е X* и наблюдении выходной последовательности (1 е У. Под тестовой последовательностью понимается последовательность пар входного и выходного сигналов: «Х|/у1>.....<х,/у|».

При тестировании сравниваются эталонная модель и объект, представленные расширенными автоматами Еэ и Ej. Введено понятие псевдо-эквивалентности расширенных автоматов. Рассматривается приближение Е' = (Х'с, У'е, 5С, Уе, Т'с, 5о) расширенного автомата Е = (X,, Ус, 5С, Ус, Те, во). Множество Хс' является множеством типов входных сообщений, а множество Уе' - множеством типов выходных сообщений расширенного автомата Е. Отношение Т': Эе х Х*1 -> 8е х Уе' определяет множество переходов, которые могут быть запущены в состоянии э е Эс расширенного автомата Е сигналом типа х, е X«'. Е' является в общем случае недетерминированным конечным автоматом (НКА) и назван покрывающим автоматом для расширенного автомата Е. НКА является трасс-эквивалентным другому НКА в состоянии бо Е1' =8о Е2', если для любой входной последовательности, поданной в эо, совпадают множества порождаемых ею выходных последовательностей. Два расширенных автомата Е1 = (Хи Уь V), Т|, Бог) и Е2 = (Х2, У2, Бг, У2, Т2, гог) являются псевдоэквивалентными, если покрывающие их НКА трасс-эквивалентны:

Е1э„Е2 оЕ1ЧоЕ21.

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

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

У(у,1)=1«>Еэ =п Ъ.

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

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

ЛСРП является расширенный конечный автомат

Р(Х, У, Б, 50, V, Т), где

X = { х } - множество входных сигналов, х = <Х],.., ххта„>;

V = { у } - множество выходных сигналов, у = <У|, .., Уут«ж>;

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

,т0 - начальное обобщенное состояние, $ о = (бо, уо), во еБ, уо е V;

V = {V} - множество внутренних переменных, V = <уь .., ут1ах>;

Т - функция поведения, Т: (Э х X х V) (Э х У х V).

Функция поведения Т задается как кусочно-линейная функция на множестве Б х X х V. Области входных значений, в которых функция имеет линейный вид, задаются системами линейных неравенств (системами ограничений) Р(Б х X х V), причем область линейности включает только одно значение в б Б. Вид функции в областях линейности задается линейными функциями ХхУ->ХхУхБ (системами присваиваний), причем область значений каждой линейной функции включает в себя только одно значение э е Э.

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

будет задавать область входных значений пути, а система присваиваний - зависимость значений параметров выходных сигналов от начальных условий и значений параметров входных сигналов.

+ кп - система присваиваний;

Ж? )Ьп • система ограничений, где

<х >)'

Ап

БЮ - столбец сравнений "<=" и "=", а матрицы ЬРТ и ЛРТ состоят из элементов {0,1, -1}.

Проведена оценка вычислительной сложности алгоритма поиска входной последовательности, покрывающей заданный переход ЛСРП. Вычислительная сложность поиска покрытия перехода в расширенном автомате с произвольными предикатами переходов составляет СХИх1" М1"). № - среднее количество переходов, исходящих из одного состояния; Ь - длина покрывающего пути; Их - мощность множества сигналов одного типа. Вычислительная сложность поиска покрытия перехода в ЛСРП составляет 0(Ь3 Ы^). Как видно из полученных выражений, сложность поиска покрытия перехода в ЛСРП не зависит от диапазона значений параметров входных сигналов.

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

В третьей главе разработаны алгоритмы генерации аттестационных тестов для ЛСРП. На основе оценки общей длины теста, а также количества сигналов "сброса", включаемых в тест, выполнено обоснование выбора в качестве базового метода тестирования конечного автомата метода последовательностей 1110 для протокола без "надежного сброса". Проведена оценка покрытия тестов, полученных методом 1Л0 последовательностей для автоматов без "надежного сброса". Методы генерации тестов для автоматов без "надежного сброса" не позволяют в теории достичь 100%-го покрытия при множественных ошибках в конечном состоянии переходов. Оценка покрытия теста выполнялась с помощью вычислительного эксперимента, в процессе которого

генерировались автоматы с внесенной по отношению к эквивалентной модели ошибкой. Для сгенерированных автоматов эмулировалось выполнение теста. Результаты эксперимента позволяют сделать следующий вывод: для автоматов, моделирующих протоколы передачи данных, метод 1ЛО-последовательностей без использования сигнала "сброс" позволяет достичь 99,99%-го покрытия с доверительной вероятностью 0,99.

Проведена оценка вычислительной сложности алгоритма генерации уникальных последовательностей 1ЛО для детерминированного автомата. Если длина последовательностей 1ЛО не превышает Ь, то вычислительная сложность алгоритма генерации 1ЛО составляет 0(р<и|) * п* 1п(п)). Имеется степенная зависимость времени нахождения последовательностей ШО от количества сигналов р, поэтому не желательной является операция "разложения" сигнала с параметром на различные сигналы при применении данного алгоритма к расширенному автомату.

Разработана процедура генерации тестовой последовательности для ЛСРП. Для идентификации состояний в расширенном автомате введен аналог уникальной последовательности ШО - уникальная входная область (УВО). Тестовая последовательность разбита на независимые тестовые сегменты. Рассматриваемая процедура тестирования является тестированием путем проведения одиночного безусловного эксперимента. Поэтому тестовый сегмент задает одну входную последовательность с точностью до значений параметров и задает корректную выходную последовательность:

ТЭ = < 1п, От >;

1п = <К5Т> <х > <1«Т>; Ои1 = <у >.

Доказано утверждение, что необходимым условием применимости разработанной процедуры является выполнение свойства "корректности" ЛСРП, определенного во второй главе.

Для ЛСРП введена характеристика "глобальной достижимости" Ц. Глобальным состоянием ЛСРП называется совокупность (в, у) состояния ЛСРП в и значения вектора переменных ЛСРП V. численно равна максимальной длине последовательности, переводящей ЛСРП из одного глобального состояния (бо, уо) в другое глобальное состояние (5с, V,). Уточнен алгоритм генерации покрытия перехода для ЛСРП. Оценка вычислительной сложности атгоритма нахождения покрытия перехода для ЛСРП составляет 0(с:1я), где -характерно шка "глобальной достижимости" ЛСРП.

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

рассматриваемых при поиске вариантов. Значительное количество рассматриваемых при поиске путей не изменяют глобальное состояние ЛСРП, то есть являются глобальными циклами. При осуществлении поиска глобальные циклы рассматриваться не должны. Предложена процедура обнаружения глобальных циклов в графе ЛСРП.

Разработана процедура преобразования описания SDL-процесса в ЛСРП. Язык SDL семантически не поддерживает учет длительности временного интервала, в частности, длительности таймера. Предложен метод предварительного преобразования описания модели на языке SDL, использующей таймер, в эквивалентное с точки зрения тестирования описание.

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

В четвертой главе представлена реализация программных средств генерации аттестационных тестов на основе разработанного метода.

Для разработки программного средства использовался объектно-ориентированный язык С++. Функциональная схема программного средства показана на Рис. 3.

Рис. 3. Структура разработанного программного средства

В процессе проектирования программного средства разработано семейство классов, позволяющих реализовать следующие основные функции: синтаксический разбор описания на я{ыкс SDL: символьное выполнение ЛСРП, позволяющее получать системы ограничений п системы присваиваний для путей ЛСРП; генерация УВО для ЛСРП; построение дерева поиска покрытия перехода; разрешение систем ограничений для переходов и путей ЛСРП с использованием симплекс-метода линейного программирования; построение тестовой последовательности.

С использованием разработанного программного средства была получена тестовая последовательность для протокола TCP. Протокол TCP является наиболее распространенным протоколом транспортного уровня, используемым в сетях IP и. в частности, в сети Интернет. Протокол TCP обеспечивает надежную передачу данных "из конца в конец" по сети с протоколом IP. Основными функциями TCP являются сегментация данных пользователя; последовательная нумерация сегментов; повторная передача потерянных и испорченных сегментов; управление скоростью передаваемых данных.

Стандартное описание протокола TCP не содержит формальное описание. Поэтому для протокола TCP было разработано описание на языке SDL. Разработанное описание состоит из двух взаимодействующих процессов и отражает все основные возможности TCP, описанные документом RFC 793. Использование как минимум двух процессов необходимо для отображения возможности независимого приема и передачи при выполнении сегментации. Рассмотрены другие способы описания на языке SDL независимого приема и передачи. Показано, что при выполнении тестирования учет возможности независимого приема и передачи при сегментации ведет к появлению недегерминированности в поведении тестируемого объекта. Недетерминированностъ обусловлена невозможностью точного наблюдения и управления моментами приема и передачи сообщений в тестируемом объекте. Введено понятие самосинхронизации тестера и объекта во время тестирования. Предложена упрощенная модель TCP, позволяющая достичь самосинхронизации тестера и объекта при тестировании.

В связи с наличием в протоколе TCP таких возможностей, как выполнение над переменными арифметических операций по модулю 2\ случайный выбор начального значения счетчика отправленных октетов приведены дополнительные требования к реализации тестера.

С помощью программного средства получена тестовая последовательность для протокола TCP. Разработана покрывающая модель TCP в виде недетерминированного конечного автомата. Для покрывающей модели сгенерированы последовательности UIO и получен частичный тест. Выполнен вычислительный эксперимент по оценке покрытия

частичного теста. Разработанный метод и программное средство позволяют на практике получать тестовые последовательности для протоколов пакетной передачи данных.

Основные результаты диссертационной работы

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

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

3. Разработан алгоритм генерации уникальных последовательностей, позволяющих идентифицировать состояния автомата при тестировании, для недетерминированного и расширенного автомата. Исследовано покрытие тестов, полученных методом уникальных последовательностей для автомата без сигнала "надежного сброса".

4. Разработан набор алгоритмов автоматической генерации аттестационных тестов для описания протокола в виде линейной системы расширенного перехода. Набор алгоритмов обеспечивает генерацию аттестационных тестов для параметризованных протоколов передачи данных в тех случаях, когда не применимы существовавшие ранее методики, основанные на модели конечного автомата.

5. Предложен эвристический метод отсечения глобальных циклов в дереве поиска, позволяющий снизить время генерации аттестационных тестов для ЛСРП.

6. Разработано программное средство, реализующее алгоритмы генерации аттестационных тестов на основе ЛСРП. Разработанное программное средство позволяет значительно сократить время разработки аттестационных тестов и повысить их качество. Созданное программное средство может использоваться сертификационными лабораториями, а также операторами сетей связи для проведения аттестационного тестирования широкого класса протоколов передачи данных.

7. С помощью разработанного программного средства получен комплект аттестационных тестов для протокола транспортного уровня TCP, широко используемого в сети Интернет.

8. Результаты работы внедрены в учебные курсы "Интернет-обьединяющая основа для сетей и услуг ПД" и "Системы и сети передачи данных" кафедры ТЭОД МТУСИ. Результаты работы использованы при разработке отраслевых руководящих документов РД 45.134-2000 "Средства технические телематических служб. Общие технические требования", РД 45.46-99 "Технические требования к аппаратуре связи, реализующей функции передачи речевой информации по сетям с маршрутизацией пакетов по протоколу IP".

Основные положения диссертации опубликованы в следующих работах:

1. Фунтиков В.Б. Сертификация оборудования IP - телефонии. - Документальная электросвязь, №1, Москва, 1999. - с. 48-50.

2. Фунтиков В.Б. Проблемы сертификации узлов телематических служб Интернет. -сборн. "Электронный обмен данными в Интернет", деп. в ЦН'ГИ "Информсвязь", №2153 св-99 от 27.04.99. - с. 50-52.

3. Волож А.Ю., Амилющенко А.В, Фунтиков В.Б. Интернет-телефония в России. -Научно-техническая конференция профессорско-преподавательского, научного и инженерно-технического состава МТУСИ, тезисы доклада, 1999. - 1 с.

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

5. Fountikov V.B. "Telecom equipment certification procedures in the Russian Federation" -Think tank telecom exchange conference, Warsaw, Poland, 1999. - 10 c.

ВВЕДЕНИЕ.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К АТТЕСТАЦИОННОМУ ТЕСТИРОВАНИЮ ПРОТОКОЛОВ ПЕРЕДАЧИ ДАННЫХ.

1Л. Объект, задачи и проблемы аттестационного тестирования.

1.2. Общая схема аттестационного тестирования. Проблемы аттестационного тестирования.

1.3. Генерация тестов на основе модели протокола.

1.3.1. Использование модели детерминированного конечного автомата

1.3.2. Использование модели недетерминированного конечного автомата

1.3.3. Использование модели расширенного автомата.

1.4. Выводы.

2. РАЗРАБОТКА МОДЕЛИ ЛИНЕЙНОЙ СИСТЕМЫ РАСШИРЕННОГО ПЕРЕХОДА.

2.1. Формальная постановка задачи.

2.2. Модель линейной системы расширенного перехода.

2.2.1. Анализ процедуры генерации тестов на основе модели расширенного автомата.

2.2.2. Основные определения.

СОДЕРЖАНИЕ (продолжение)

2.2.3. Свойства модели.

2.3. Выводы.

3. РАЗРАБОТКА АЛГОРИТМОВ ГЕНЕРАЦИИ ТЕСТОВ.

3.1. Разработка алгоритма генерации тестов для недетерминированного конечного автомата.

3.2. Расширение метода уникальных последовательностей.

3.3. Построение тестового комплекта.

3.3.1. Процедура построения тестового комплекта.

3.3.2. Оптимизация алгоритма поиска покрытия перехода.

3.3.3. Разработка процедуры преобразования описания SDL-процесса . 3.5. Выводы.

4. РАЗРАБОТКА И АПРОБАЦИЯ ПРОГРАММНОГО СРЕДСТВА АВТОМАТИЗИРОВАННОЙ ГЕНЕРАЦИИ ТЕСТОВ.

4.1. Структура программного средства генерации аттестационных тестов

4.2. Пример разработки тестового комплекта для протокола TCP.

4.2.1. Характеристики протокола TCP.

4.2.2. Разработка описания TCP на языке SDL.

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

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

Необходимым условием решения проблемы совместимости при использовании оборудования различных производителей является установление единых стандартов на протоколы передачи данных. Такие организации по стандартизации, как МСЭ, ИСО, ЕТ81 и другие принимают участие в достижении соглашений в рамках индустрии связи по разработке единых интерфейсов и протоколов. Разработка стандартов на протоколы передачи данных является первым шагом на пути к достижению совместимости различных телекоммуникационных устройств. Но стандарты не являются совершенными. Как и в случае других межнациональных соглашений, достижение компромисса между различными точками зрения ведет к появлению большого числа факультативных возможностей и вариантов реализаций, описываемых в стандартах. Кроме 6 того, поскольку стандарты, как правило, написаны на естественных языках (таких, как русский или английский), описание протоколов не является абсолютно точным и может допускать различные трактовки. Перечисленные причины, а также сложность современных стандартных протоколов, ведут к появлению различных реализаций одного и того же протокола и сокращают возможности технических средств по взаимодействию друг с другом.

Аттестационное тестирование представляет собой необходимое звено в обеспечении совместимости оборудования передачи данных, выпущенного различными производителями, предоставляя возможность проверки соответствия реализации протокола установленному стандарту. В России с 1994 г. законом "О связи" введена обязательная сертификация оборудования связи на соответствие российским и международным стандартам. Каждое устройство, подключаемое к взаимоувязанной сети связи России, должно быть подвергнуто сертификационным испытаниям, которые включают в себя и аттестационное тестирование. Для проведения подобных сертификационных испытаний необходима разработка эффективных методов аттестационного тестирования.

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

Более перспективной с точки зрения гибкости и выразительной мощности является модель расширенного автомата. Стандартным языком для описания 7 моделей расширенных автоматов в области связи является язык SDL. В настоящее время большинство рекомендаций МСЭ-Т и ETSI, описывающих аспекты поведения протоколов связи, используют в той или иной степени спецификации на языке SDL. Учитывая быстрое развитие инструментов автоматизированного проектирования систем связи, использующих язык SDL, можно ожидать дальнейшее распространение SDL в качестве языка описания протоколов передачи данных. Поэтому важным направлением является разработка методов автоматизированного получения тестовых последовательностей на основе описания протокола на языке SDL.

Целью данной диссертационной работы является исследование и разработка метода автоматизированной генерации аттестационных тестов для протоколов пакетной передачи данных, а также разработка программного средства генерации аттестационных тестов на основе описания протокола передачи данных на языке SDL.

В соответствии с поставленной целью в диссертационной работе решаются следующие основные задачи:

- исследование существующих методов автоматизированной генерации тестовых последовательностей для автоматных моделей протоколов передачи данных и анализ возможности их практического применения;

- анализ задач аттестационного тестирования, формулировка типов ошибок, выявляемых при аттестационном тестировании, и исследование проявления возможных ошибок во внешнем поведении формальной модели протокола передачи данных;

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

- разработка алгоритмов генерации тестовых последовательностей на основе полученной модели и оценка вычислительной сложности разработанных алгоритмов; 8

- разработка программных средств, реализующих алгоритм автоматизированной генерации тестов и их апробация на примере генерации аттестационного теста для протокола TCP, широко используемого в сети Интернет.

В работе использованы методы математической логики, аппарат теории множеств, аппарат теории графов, теория конечных автоматов, методы математического программирования, методы анализа вычислительных алгоритмов, а также методы объектно-ориентированной разработки программных средств.

К основным научным результатам диссертации можно отнести:

1. Поставлена и решена задача автоматизированной генерации тестов для протоколов передачи данных с параметрами, описываемых расширенным автоматом.

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

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

4. Для модели линейной системы расширенного перехода разработан набор алгоритмов генерации аттестационных тестов, основанный на использовании уникальных входных областей, позволяющий получить тестовый комплект, отвечающий критерию псевдо-эквивалентности. Разработанные алгоритмы 9 применимы для автоматизированной генерации тестов протоколов пакетной передачи данных без сигнала "надежный сброс".

На основе предложенной в диссертации модели линейной системы расширенного перехода разработано программное средство в среде ОС Windows 9 5 /NT, предназначенное для автоматизации аттестационного тестирования протоколов пакетной передачи данных. Разработанное программное средство может использоваться совместно с графическими редакторами стандартного языка SDL.

Разработанные в диссертации модель линейной системы расширенного перехода и алгоритмы генерации тестов могут быть использованы в создании средств автоматизации аттестационного тестирования систем передачи данных различного функционального назначения. Разработанная математическая модель и алгоритмы могут использовать в качестве исходных данных как описание на языке SDL, так и описания расширенных конечных автоматов на других языках (например, Estelle)

Теоретические и практические результаты работы использованы в НИР по разработке отраслевых руководящих документов РД 45.134-2000 "Средства технические телематических служб. Общие технические требования", РД 45.46-99 "Технические требования к аппаратуре связи, реализующей функции передачи речевой информации по сетям с маршрутизацией пакетов по протоколу IP", а так же в разработке "Программы и методики сертификационных испытаний интерфейсных плат компьютерной телефонии, подключаемых к ТФОП", утвержденной Минсвязи России, 24.05.2000 г.

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

Создана лабораторная работа на тему "Методы и средства аттестационного тестирования" по курсу "Интернет - объединяющая основа для сетей и услуг

10

ПД ". Реализация результатов работы подтверждается соответствующими актами о внедрении.

Диссертационная работа состоит из введения, четырех глав, заключения и приложений.

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

152

Заключение

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

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

1. Альберте М.Я., Калниньш A.A., Калныня Д.А. Автоматизированное тестирование телекоммуникационных систем. Автоматика и вычислительная техника. № 5, 1997. - с. 29 - 39.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: "Мир", 1978. - 612 с.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 535 с.

4. Бертсекас Д., Галлагер Р. Сети передачи данных. М.: Мир, 1989. — 542 с.

5. Бичевский Я.Я. Автоматическое построение систем примеров. Программирование, № 3, 1977. - с. 60 - 70.

6. Борзов Ю.В. Тестирование программ с использованием символического выполнения. Программирование, № 1, 1980. - с. 51 - 59.

7. Венцтель Е.С. Теория вероятностей. — М.: Наука, 1969. 576 с.

8. Волож А.Ю., Амилющенко A.B., Фунтиков В.Б. Интернет-телефония в России. Научно-техническая конференция профессорско-преподавательского, научного и инженерно-технического состава МТУ СИ, тезисы доклада, 1999.- 1 с.

9. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966. - 272 с.

10. ГОСТ 28906-91 (ИСО 7498). Системы обработки информации. Взаимосвязь открытых систем. Базовая эталонная модель. М.: Госстандарт России, 1991.

11. ГОСТ Р ИСО/МЭК 9646-1-93. Информационная технология. Взаимосвязь открытых систем. Методология и основы аттестационного тестирования. -М.: Госстандарт России, 1993.

12. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998. - 703 с.

13. Иванов А.Б. Контроль соответствия в телекоммуникациях и связи. Часть 1.- М.: Компания САЙРУС СИСТЕМС, 2000. 375 с.153

14. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. -429 с.

15. Кульгин М. Оптимизация работы протокола ТСР в распределенных сетях. -М.: Сети, №10, 1999. с. 26 - 36.

16. Кульгин М.В. Коммутация и маршрутизация IP/IPX трафика. -М.: Компьютер Пресс, 1998.-319 с.

17. Куфарова И.Б., Евтушенко Н.В., Петренко А.Ф. Синтез проверяющих тестов для недетерминированных автоматов относительно редукции. — Автоматика и вычислительная техника, № 3, 1998. с. 10-20.

18. Липский. В. Комбинаторика для программистов. М.: Мир, 1988. - 213 с.

19. Муртаф. Б. Современное линейное программирование. -М.: Мир, 1984. -224 с.

20. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск, Наука (сибирское отделение), 1990. - 514 с.

21. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000.-304 с.

22. Сэвидж Д.Э. Сложность вычислений. -М.: Изд-во "Факториал", 1998 -368 с.

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

24. Фунтиков В.Б. Проблемы сертификации узлов телематических служб Интернет. сборн. "Электронный обмен данными в Интернет", деп. в ЦНТИ "Информсвязь", №2153 св-99 от 27.04.99. - с. 50-52

25. Фунтиков В.Б. Сертификация оборудования IP телефонии. - Документальная электросвязь, № 1, Москва, 1999. - с. 48-50.154

26. Шевельков В.Л. Метод проверки синтаксиса передачи представительного уровня в тестировании конформности. Автоматика и вычислительная техника, №1, 1994.

27. Шилдт Г. Теория и практика С++. СПб.: BHV - Санкт-Петербург, 1999. -416 с.

28. Aho A., Dahbura A., Lee D. An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Chinese Postman Tours. Symposium of Protocol Specification, Testing, and Verification, IFIP, Elsevier, 1988.-е. 134-147.

29. Anders Ek, Grabowski J., Hogrefe D. Towards the industrial use of validation techniques and automatic test generation methods for SDL specifications. -Technical report, 1998. 22 c.

30. Barry S. Bosik, Uyar M.U. Finite state machine based formal methods in protocol conformance testing: from theory to implementation. Computer Networks and ISDN Systems № 22, 1991. - c. 8 - 26.

31. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов М.: Наука. Гл. ред. физ.-мат. лит., 1985. - 320 с.

32. Besse Cederic, Cavalli A., Lee D. Optimization techniques and automatic test generation for TCP/IP protocols, 1998. -16 c.

33. Bhattacharyya A. Checking experiments in sequential machines. New Delhi etc.: Wiley Eastern, 1989. - 155 c.

34. Bochmann G., Petrenko A., Yao M. Fault coverage of tests based on finite state models. Chapman & Hall, Proc. of IFIP WG 6.1 Protocol Test Systems, 1995 -c. 55-78.

35. Bochmann G., Petremko A., Belial O. Automating the process of test derivation from SDL specifications. Universite de Montreal, 1996. - 12 c.

36. Bourhfir C., Dssouli R., Aboulhamid E.M. Automatic Test Generation for EFSM-based Systems. Canada, Universite de Montreal, DIRO, Publication # 1060, 1995.-60 c.155

37. Brinksma E. A theory for the derivation of tests. Protocol Specification, Testing and Verification, 8, IFIP, Elsevier, 1988. - c. 63 - 74.

38. Brinksma E., Alderden R., Langerak R. Formal approach to conformance testing. Proc. Int. Workshop on Protocol Test Systems, North-Holland, 1989.c. 311 325.

39. Budkowski T., Demobinski P. An Introduction to Estelle: a Specification Language for Distributed Systems, Computer Networks and ISDN Systems, Vol. 14, No 1, 1991, c. 3-24.

40. Chan Wendy Y.L., Vuong Son T., Ito M. R. An Improved Protocol Test Generation Procedure Based on UIOs. Computer Communication Rev., Vol. 19, No. 4, 1989. -c. 283-289.

41. Chanson S.T., Zhu J. A Unified Approach to Protocol Test Sequence Generation. Proc. IEEE INFOCOM, 1993. - c. 106 - 114.

42. Chen Mon-Song, Choi Y., Kershenbaum A. Approaches utilizing segment overlap to minimize test sequences. — Protocol Specification, Testing, and Verification, IFIP, Elsevier, 1990. c. 85 - 98.

43. Chow T.S. Test Design Modeled by Finite-State Machines. IEEE Transactions on SE, No 3, 1978, - c. 178 - 187.

44. Chun W., Amer P.D. Test Case Generation for Protocols Specified in Estelle. -Madrid, Proc. of FORTE, 1990. 18 c.

45. DeMillo R.A., Offutt J. Constraint-Based Automatic Test Data Generation. -IEEE Transactions on SE, Vol. 17, No 9, 1991. -c. 13-24.

46. EG 202 106. Methods for testing and specification (MTS); Guidelines for the use of formal SDL as a descriptive tool. Geneva, ETSI, 1999.

47. Eswara S., Berriman T., VanHoutte P. Towards Execution of TTCN Test Cases. -Proc. of IFIP Protocol Specification, Testing and Verification, X, Elsevier, 1990. -c. 99-112.

48. Fecko M. A., Uyar M. U., Sethi A. S. Issues in conformance testing: multiple semicontrollable interfaces. Paris, Proc. of FORTE/PSTV, 1998. - 17 c.156

49. Ferenc Belina, Hogrefe Dieter. The CCITT-Specification and Description Language SDL", Computer Networks and ISDN Systems, v. 16, 1989. - c. 45 - 61.

50. Fountikov V.B. "Telecom equipment certification procedures in the Russian Federation" Think tank telecom exchange conference, Warsaw, Poland, 1999. -10 c.

51. Fujiwara S., G.v. Bochmann, Khendek F. Test selection based on finite state models. IEEE Trans, on Software Engineering, Vol SE-17, No. 6, 1991, c. 591603.

52. Gill A. Realization of input-output relations by sequential machines. Journal of the ACM, v. 13, No. 1, 1966. - c. 33 - 42.

53. Gonenc G. A Method for the Design of Fault Detection Experiments, IEEE Trans, on Computers, Vol. 19, No. 6, 1970. - c. 550 - 558.

54. Grabowski J. SDL and MSC based test case generation an overall view of the SaMsTaG method - University of Berne, Technical report IAM-94-005, 1994. -25 c.

55. Grabowski J., Hogrefe D., Nahm R. A method for the generation of test cases based on SDL and MSCs. University of Berne, Technical report IAM-93-010, 1993.-25 c.

56. Grabowski J., Scheurer R., Toggweiler D., Hogrefe D. Dealing with the complexity of state space exploration algorithms for SDL systems. — University of Berne, Technical report, IAM-95-010, 1996. 11 c.

57. Hengeveld W., Kroon J. Using Checking Sequences for OSI Session Layer Conformance testing. IFIP, Protocol Specification, Testing, and Verification, 7, 1987.-c. 435-449.

58. Higashino T., Bochmann G. Automatic analysis and test case derivation for a restricted class of LOTOS expressions with data parameters. IEEE Transactions on SE., Vol 20, No 1, 1994. - c. 29-42.

59. Holzmann G. J. Design and validation of computer protocols. London: Prentice-Hall International Inc., 1991. - 500 c.157

60. ISO 8807. LOTOS: a formal description technique based on temporal ordering observational behavior.

61. ISO 9074. Estelle. A formal description technique based on an extended state transition model.

62. ISO/IEC 9646-3. Tree and Tabular Combined Notation.

63. Kohavi Z. Switching and Finite Automata theory. McGraw-Hill, 1978. - 658 c.

64. Language translation using PCCTS and C++. PCCTS Program manual, 1999. -280 c.

65. Lombardi F., Shen Y.-N. Evaluation and Improvement of Fault Coverage of Conformance Testing by UIO Sequences. IEEE Transactions on Communications, Vol. 40, No. 8, 1992. - c. 1288 - 1293.

66. Luo G., Bochmann G. v., Petrenko A.F. Test selection based on communication nondeterministic finite state machines using a generalized Wp-method. IEEE Trans, on SE, v. 20, No. 2, 1994. - c. 149 - 162.

67. Miller R.E. and Paul S. Structural analysis of protocol specifications and generation of maximal fault coverage conformance test sequences. IEEE/ACM Transactions on Networking, vol. 2 no. 5, 1994. - c. 457-470.

68. Miller R.E., Paul S. On generation of minimal length conformance tests for communication protocols, - IEEE/ACM transactions on Networking, v. 2, 1993. -c. 116-129.

69. Petrenko A., Yevtushenko N., Bochmann G. Testing in context: framework and test derivation. Computer Communications Journal, Vol. 29, 1996. - c. 12361249.

70. Petrenko A., Yevtushenko N., Lebedev A. Nondeterministic State Machines in Protocol Conformance Testing. — North-Holland, IFIP Trans., Protocol Test Systems, VI, 1993.-c. 363-378.

71. Pountain D. Constraint Logic Programming. Byte magazine, No 2, 1995. - c. 34-35.158

72. Rayner D. OSI conformance testing. Computer networks and ISDN systems, v. 14 № 1, 1987.-c. 79-98.

73. RFC 793. Transmission control protocol. IETF, 1981.

74. Sabnani K. and Dahbura A. A protocol test generation procedure and its fault coverage. Computer Networks and ISDN Systems, vol 15, 1988. - c. 285 - 297.

75. Sarikaya B., Bochmann G., Cerny E. A test derivation methodology for protocol testing. IEEE transactions on Software Engineering, Vol. 13, No. 9, 1987.c. 989-999.

76. Shen Y.N., Lombardi F., Dahbura A.T. Protocol conformance testing using multiple UIO sequences, IEEE Trans. Communications, v. 40, 1992.c. 1282- 1287.

77. Sidhu Deepinder P. Protocol Testing: The first ten years, the next ten years. -Protocol Specification, Testing, and Verification, IFIP, 1990. c. 47 - 68.

78. Sidhu Deepinder P., Leung Ting-Kau. Formal Methods for Protocol Testing: A Detailed Study. IEEE Trans, on SE, Vol. 15, No 4, 1989. - c. 413 - 426.

79. The meaning of conformance to standards. Geneva, ECMA, TR/18, 1983. -14 p.

80. Tretmans. J. Conformance testing with labeled transition systems: Implementation relations and test generation. Computer networks and ISDN systems, v. 29 No. 1, 1996.-c. 49-79.

81. Ural H., Yang B. A Test Sequence Selection Method for Protocol Testing. -IEEE Transactions on Communications, Vol. 39, No 4, 1991. c. 311 — 325.

82. Ural H., Zhu K. Optimal length test sequence generation using distinguishing sequences. IEEE/ACM Trans. Networking, v. 1, No. 3, 1993. - c. 358 - 371.

83. Uyar M.U., Sherif M.H. Protocol modeling for conformance testing: Case study for the ISDN LAPD protocol. AT&T technical J., vol. 69, 1990. - c. 67-74.

84. Using Formal Description Techniques An Introduction to Estelle, LOTOS and SDL.-John Wiley and Sons Ltd., 1993.-431 c.

85. Vern Paxson. Automated packet trace analysis of TCP implementations. ACM Transactions, 1997.-c. 167- 179.

86. Weyuker E.J., Rapps S. Selecting Software Test Data using Data Flow Information. IEEE Transactions on SE, Vol. 11, No. 4, 1985.- 1985.

87. Wiles A. The Tree and Tabular Combined Notation. A Tutorial. Telia Research, 1990. -210 c.

88. X.208. Specification of Abstract Syntax Notation One (ASN.l) Geneva, ITU-T, 1988.

89. X.680. Information technology Abstract Syntax Notation One (ASN.l): Specification of basic notation. - Geneva, ITU-T, 1997.

90. X.682. Information technology Abstract Syntax Notation One (ASN. 1): Constraint specification - Geneva, ITU-T, 1997.

91. X.683. Information technology Abstract Syntax Notation One (ASN.l): Parameterization of ASN. 1 specifications. - Geneva, ITU-T, 1997.

92. Yao M., Petrenko A., Bochmann G.v. Conformance Testing of Protocols without Reset. Universite de Montreal, Publication 861, 1993. - 28 c.

93. Yevtushenko N., Lebedev A., Petrenko A. On the Checking Experiments with Nondeterministic Automata. — New York, Automatic Control and Computer Sciences, Allerton Press, Inc., v. 25, No. 6, 1991. c. 81 - 85.

94. Yevtushenko N., Petrenko A. A method of constructing a test experiment for an arbitrary deterministic automation. Automatic control and computer sciences, Allerton Press, Inc. New York, v. 24, No. 5, 1990. -c. 65 - 68.

95. Z.100. Specification and Description language (SDL). ITU-T, Geneva, 1996.

96. Z.120 (1996). Message Sequence Chart (MSC). Geneva, ITU-T, 1996.160