МОДЕЛИ И МЕТОДЫ СИНТЕЗА ТЕСТОВ ДЛЯ РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОННЫХ СИСТЕМ НА ОСНОВЕ СЕТЕЙ ПЕТРИ : МОДЕЛІ ТА МЕТОДИ СИНТЕЗУ ТЕСТІВ ДЛЯ РОЗПОДІЛЕНИХ ІНФОРМАЦІЙНИХ СИСТЕМ НА ОСНОВІ МЕРЕЖ ПЕТРІ

Краткое описание

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

на правах рукописи
Васім АльШаріф Мусса Сухад

УДК:004.738:004.94

МОДЕЛИ И МЕТОДЫ СИНТЕЗА ТЕСТОВ
ДЛЯ РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОННЫХ СИСТЕМ
НА ОСНОВЕ СЕТЕЙ ПЕТРИ

05.13.06 – Информационные технологии

Диссертация на соискание научной степени
кандидата технических наук

Научный руководитель
Мартынюк Александр Николаевич
кандидат технических наук, доцент

Одесса – 2013

СОДЕРЖАНИЕ
СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ ……………………….5
ВВЕДЕНИЕ ………………………………………………………………………………6
РАЗДЕЛ 1. АНАЛИЗ МЕТОДОВ ПОСТРОЕНИЯ ТЕСТОВ. ПОСТАНОВКА
ЗАДАЧИ ИССЛЕДОВАНИЯ........................................................................................... 13
1.1 Базовые определения............................................................................................ 13
1.1.1 Системы контроля и диагноза....................................................................... 14
1.1.2 Математические модели объектов диагностирования. .............................. 16
1.1.3 Прямая и обратная задачи диагностирования. ............................................ 17
1.2 Анализ структурных методов построения тестов ............................................. 19
1.2.1 Комбинационные методы.............................................................................. 19
1.2.2 Последовательностные методы. ................................................................... 22
1.2.3 Псевдослучайные методы.............................................................................. 23
1.2.4 Эволюционные методы.................................................................................. 23
1.3 Анализ функциональных методов синтеза тестов ............................................ 24
1.3.1 Тривиальные, переборные тесты. ................................................................ 25
1.3.2 Модульные и микрооперационные тесты.................................................... 26
1.3.3 Тесты на основе модели передач. ................................................................. 27
1.4 Анализ методов синтеза тестов на основе экспериментов с автоматами....... 28
1.4.1 Контрольные эксперименты.......................................................................... 29
1.4.2 Тесты с использованием идентификаторов................................................. 31
1.4.3 Тесты на основе вероятностных экспериментов......................................... 32
1.4.4 Тесты автоматных композиций. ................................................................... 34
1.4.5 Тесты на основе автоматных уравнений...................................................... 39
1.4.6 Потеря тестовой информации. ...................................................................... 41
1.4.7 Тесты на основе экспериментов в иерархиях.............................................. 42
1.5 Анализ методов синтеза тестов на основе сетей Петри ................................... 43
1.5.1 Тестовый анализ корректности поведения сетей Петри. ........................... 44
1.5.2 Бисимуляция в тестировании функций сетей Петри.................................. 47
1.6 Выводы и постановка задачи исследования ...................................................... 51
3
РАЗДЕЛ 2. РАЗРАБОТКА АНАЛИТИЧЕСКИХ И СТРУКТУРНО-
АНАЛИТИЧЕСКИХ МОДЕЛЕЙ ТЕСТИРОВАНИЯ РИС .......................................... 53
2.1 Анализ аналитической модели тестирования.................................................... 55
2.1.1 Представление аналитической модели тестирования. ............................... 55
2.1.2 Представляющий и строчный автоматы для сети Петри. .......................... 60
2.1.3 Представление теста на основе тестовых примитивов. ............................. 63
2.2 Анализ структурно-аналитической модели тестирования............................... 66
2.2.1 Представление структурно-аналитических тестов. .................................... 67
2.2.2 Синхронизация структурно-аналитической модели................................... 69
2.2.3 Модель реализуемого поведения.................................................................. 71
2.2.4 Модель распознаваемого поведения. ........................................................... 74
2.3 Модели тестирования в структурно-аналитическом окружении .................... 81
2.3.1 Частичность тестового поведения. ............................................................... 81
2.3.2 Модели теста СП. ........................................................................................... 83
2.4 Выводы................................................................................................................... 84
РАЗДЕЛ 3. РАЗРАБОТКА СТРУКТУРНО-АНАЛИТИЧЕСКИХ МЕТОДОВ
ПОСТРОЕНИЯ ФУНКЦИОНАЛЬНЫХ ТЕСТОВ........................................................ 86
3.1 Реализация структурно-аналитических методов синтеза тестов..................... 86
3.1.1 Подзадачи аналитического метода. .............................................................. 86
3.1.2 Подзадачи структурно-аналитического метода. ......................................... 88
3.2 Определение шагов подзадач структурно-аналитического метода ................ 90
3.2.1 Подзадача определения входных слов RХ. .................................................. 90
3.2.2 Подзадача определения выходных слов Tr. ................................................ 93
3.2.1 Подзадача задания проверяемых свойств Pr' и идентификаторов Id'. ...... 96
3.2.2 Подзадача задания возможных тестовых примитивов Ex’. ..................... 100
3.3 Аналитические оценки размерности моделей и методов............................... 104
3.3.1 Оценка размерности методов аналитической модели.............................. 105
3.3.2 Оценка размерности структурно-аналитических методов....................... 107
3.4 Выводы................................................................................................................. 110
4
РАЗДЕЛ 4. РЕАЛИЗАЦИЯ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ СИНТЕЗА
ТЕСТОВ НА ОСНОВЕ СЕТЕЙ ПЕТРИ ....................................................................... 111
4.1 Разработка программных средств синтеза ФТ АСТД .................................... 111
4.1.1 Структурная схема ПС синтеза ФТ АСТД. ............................................... 112
4.1.2 Основные режимы работы ПС. ................................................................... 114
4.1.3 Основные функции блоков.......................................................................... 115
4.2 Области применения, информационная поддержка и расширения .............. 122
4.2.1 Области применения. ................................................................................... 122
4.2.2 Информационная поддержка. ..................................................................... 122
4.2.3 Расширения. .................................................................................................. 122
4.3 Разработка прикладной информационной технологии .................................. 123
4.3.1 Этап структурно-функционального анализа. ............................................ 123
4.3.2 Этап компонентного анализа. ..................................................................... 124
4.3.3 Этап композиционного анализа.................................................................. 124
4.4 Анализ результатов............................................................................................. 125
4.4.1 Экспериментальные испытания программ АСТД. ................................... 126
4.5 Выводы................................................................................................................. 127
ВЫВОДЫ ………………………………………………………………………………128
СПИСОК ЛИТЕРАТУРЫ ……………………………………………………………..131
Приложение А. Основные модели и алгоритмы синтеза тестов ……………….…..139
Приложение Б. Акты внедрения программ синтеза тестов …………………………149

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ
РИС – распределенная информационная система
ФТ – функциональный тест
АСТД – автоматизированная система технического диагностирования
ФК – функциональный компонент
АМ – аппаратный модуль
ПМ – программный модуль
АПО – аппаратно-программные средства
ЦФ – целевая функция
АМ – аналитическая модель
САМ – структурно-аналитическая модель
ПС – последовательностная схема
ИКС – итеративная комбинационная схема
ГА – генетический алгоритм
ЦФ – целевая функция
СП – сеть Петри
ССП – композиция (сеть) сетей Петри
КЭ – контрольный эксперимент
РЭ – распознающий эксперимент
КОС – контур обратной связи
ССК – сильносвязанная компонента

ВВЕДЕНИЕ
Актуальность темы. Глобальная информатизация общества характеризуется
стремительным ростом разнообразия, сложности, масштабов и распределенного
применения информационных технологий и систем. Исследование, разработка и
внедрение Интернет-технологий для построения сервис-ориентированных систем
выделили актуальность аспектов, связанных с распределением ресурсов и паралле-
лизмом решения различных задач в пространстве многоуровневых сетей с многими
процессами и пользователями, расширили применение распределенных информаци-
онных систем (РИС). Эффективность современных РИС определяется объемами
данных, качеством и надежностью функционирования, оперативностью и достовер-
ностью полученных результатов. Среди существующих методов повышения надеж-
ности информационных и информационно-управляющих систем важное место за-
нимают методы технического диагностирования, составляющие основу для целого
направления исследований - разработки информационных технологий построения и
внедрения автоматизированных систем технического диагностирования (АСТД), в
частности с рабочим и тестовым контролем, который определяет работоспособность
РИС, появление и локализацию ошибок.
Разнообразным аппаратным и программным средствам технического диагно-
стирования, общим и специализированным, лежащим в диапазоне от многоканаль-
ных тест-процессоров с одной стороны и структурных, функциональных тестов и
проведенческих экспериментов с другой стороны, уделялось и уделяется самое при-
стальное внимание. Существенному развитию теории технического диагностирова-
ния способствовали работы ученых Анисимова Н.А., Байды Н.П., Барашко А.С., Бо-
гомолова А.М., Глухова В.С., Глушкова В.А., Горяшко А.П., Грунского И.С., Гуляе-
ва В.А., Дорошенко М.Ю., Дрозда А.В., Евтушенко Н.В., Зайцева Д.А., Казначеева
В.И., Карибского В.В., Клёца Ю.П., Козловского В.А., Козюры В.Е., Кондратьева
А., Мельника , Немолочнова О.Ф., Пархоменко П.П., Петренко А.Ф., Поморовой
О.В., Романкевича А.М., Скляревича А.Н., Скобцова Ю.А., Согомоняна Е.С., Спе-
ранского Д.В., Спивака М.А., Твердохлебова В.А., Тоценко В.Г., Турчиной Е.Д.,
7
Убара Р.Р., Чипулиса В.П., Халчева В.Ф., Харченко В.С., Хаханова В.И., Цейтлина
Г.Е., Шаршунова С.Г., Шеховцова О.И., Ярмолика В.Н., Abraham J.A., Abramovici
M., Autant С., Bennetts R.G., Bieber B., Bolognesi T., Chang H.Y., Esparsa J., Friedman
A.D., Gill E., Graves B., Heljanko K., Hennie F.C., Jensen K., Kohavii Z., Lovalee P.,
Maning E., McMillan K.L., Menon P.R., Metze G., Milner R., Moore E.F., Parker K.P.,
Poadge J.F., Paige R., Reghbati H.K., Roth J.P., Schnoebelen Ph., Sellers F., Tarjan R.E.,
Thatte S.M., Valmari A., Vardy M.Y., Williams T.W., Wallner F.,Wolper P. и других.
Неослабевающий интерес к тестовому контролю, который проверяет досто-
верность работы РИС в паузах рабочего функционирования, связан с его более де-
тальной информацией о состоянии РИС, что недостижимо в рабочем контроле.
Сложность и время синтеза тестов, их длина и полнота проверки ошибок РИС воз-
действуют непосредственно на результаты работы АСТД и косвенно на работоспо-
собность и надежность функционирования РИС.
Современные методы синтеза тестов позволяют проводить проверку РИС вы-
сокой сложности. Применение получили аналитические, имитационные, поведенче-
ские, функциональные, структурные, детерминированные, псевдослучайные, гене-
тические методы, а также их комбинации, которые продолжают развиваться в на-
правлении уменьшения затрат вычислительных ресурсов, повышения размерности и
адекватности моделей. Но для всех методов сохраняется необходимость продолже-
ния исследований, обусловленная их возрастающей сложностью, что требует ис-
пользования дорогих многопроцессорных систем, кроме того, время синтеза тестов,
приближается к сроку эксплуатации самих РИС. Эти проблемы дополнительно ус-
ложняются высокой степенью неполноты и неопределенности проверки. Так, в ме-
тодах синтеза тестов автоматного класса, наглядных и распространенных, рост
сложности РИС экспоненциально увеличивает комбинаторную сложность задач тес-
тирования, переводя их в класс NP-трудных уже для РИС среднего уровня сложно-
сти (около 100 условных автоматных переходов), например, сервисов WiFi или Web.
Улучшают эти результаты методы синтеза тестов на основе сетей Петри, наи-
более мощных моделей автоматного класса, снижающие экспоненциальную зависи-
мость на несколько порядков, дополнительно имеющие параллелизм, асинхрон-
8
ность, событийность, многоуровневость, что естественные для РИС. Предел NP-
трудных задач также отдаляют методы, использующие декомпозицию задач тести-
рования при учете системных, иерархических, сетевых, структурно-
функциональных, временных и иных свойств РИС. В этом случае без потери полно-
ты тестирования уменьшение экспоненциальной сложности может быть логарифми-
ческим, линейным и даже степенным.
Сочетание преимуществ методов на основе сетей Петри и декомпозиционных
методов делает целесообразным развитие их комбинаций с целью объединенного
уменьшения сложности и времени синтеза тестов, их длины, повышения полноты
проверки ошибок РИС.
Актуальность темы исследования обусловлена необходимостью развития су-
ществующих и разработки новых моделей тестирования и методов синтеза тестов на
основе сетей Петри и их композиций, направленных на разработку информационной
технологии для построения и внедрения автоматизированных систем технического
диагностирования РИС, с целью снижения длины тестов, уменьшения времени их
разработки, повышения полноты проверки ошибок, косвенного снижения проектно-
производственных и эксплуатационных расходов, сокращения сроков разработки,
проверки и восстановления работоспособности РИС, повышения их надежности.
Связь работы с научными программами, планами, темами. Исследования
в области разработки моделей и методов тестирования РИС проводились в рамках
научно-исследовательских работ кафедры компьютерных интеллектуальных систем
и сетей (КИСС) Одесского национального политехнического университета (ОНПУ),
в частности, в плановой работе №37-62 «Методы проектирования и рабочего диагно-
стирования сложных цифровых систем и сетей» (2012, №госрегистрации 0110U008194).
Цель и задачи исследования. Целью исследования является разработка мо-
делей тестирования и методов синтеза тестов для информационной технологии по-
строения и внедрения автоматизированных систем технического диагностирования
РИС, которые за счет декомпозиционного развития тестовых расширений сетей
Петри сокращают время построения и длину тестов, увеличивают полноту их про-
верки. Для достижения цели в диссертационной работе решены такие задачи:
9
- Анализ современного состояния моделей и методов синтеза тестов
автоматного класса для информационных, информационно-управляющих и сетевых
систем;
- Совершенствование структурно-аналитических моделей тестирования
РИС, основанных на тестовом анализе поведения сетей Петри, реализуемом и
транслируемом в их композициях;
- Развитие структурно-аналитических методов синтеза тестов для РИС,
реализуемых и транслируемых в композициях сетей Петри;
- Разработка информационной технологии синтеза тестов для построения
и внедрения автоматизированных систем технического диагностирования РИС;
- Разработка алгоритмов, структур данных и программ синтеза тестов на
основе анализа сетей Петри и их композиций, имплементированных в
автоматизированную систему технического диагностирования РИС;
- Апробация информационной технологии и программ синтеза тестов для
сервис-ориентированной РИС на компьютерных предприятиях и в учебном
процессе.
Объектом исследования является процесс тестового контроля с использовани-
ем моделей и методов синтеза тестов РИС на основе сетей Петри в составе инфор-
мационной технологии построения и внедрения автоматизированных систем техни-
ческого диагностирования.
Предметом исследования являются аналитические модели и методы синтеза
тестов РИС на основе сетей Петри в составе информационной технологии построе-
ния и внедрения автоматизированных систем технического диагностирования.
Методы исследования основываются на применении сетей Петри, теории
экспериментов с автоматами, которые используются как математическая база по-
строения моделей и методов синтеза тестов РИС, теорий информационных систем и
технической диагностики в качестве методологической базы тестирования РИС,
теории графов и алгоритмов для оптимизации структур и алгоритмов тестового
обеспечения.
10
Научная новизна полученных результатов исследования заключается в раз-
витии аналитических моделей и методов синтеза тестов для автоматизированной си-
стемы технического диагностирования в составе средств повышения надежности
РИС, которые используют сети Петри и их композиции и отличаются меньшими
временем синтеза тестов и их длиной, большей полнотой проверки. В работе полу-
чены следующие научные результаты:
- Впервые разработана аналитическая модель тестирования РИС на
основе сетей Петри, которая отличается введением понятия тестовых примитивов,
содержащих векторы комплектов позиций, переходы и их характеристическое
поведение, и предоставляет теоретическую основу для аналитического метода
синтеза тестов;
- Получила дальнейшее развитие структурно-аналитическая модель
тестирования РИС на основе композиции сетей Петри, которая отличается
выделением входящей, исходящей частей для некоторой проверяемой сети Петри с
композиции, определением условий построения их тестовых примитивов, и
предоставляет теоретическую основу для структурно-аналитического метода
синтеза тестов;
- Получил дальнейшее развитие аналитический метод синтеза тестов
РИС, который отличается псевдоэйлеровым обходом графа аналитической модели
тестирования с шагами обхода - тестовыми примитивами и обеспечивает
сокращение времени синтеза и длины тестов, повышение полноты проверки ошибок
РИС;
- Получил дальнейшее развитие структурно-аналитический метод синтеза
тестов РИС, который отличается построением, накоплением и использованием в
узлах композиции сетей Петри информации о сформированных тестовых
примитивах для входящей, исходящей частей для некоторой проверяемой сети
Петри композиции и позволяет сократить время синтеза и длину тестов, повысить
полноту проверки ошибок РИС.
Практическое значение полученных результатов. Практическое значение
полученных результатов заключается в применении предложенной информацион-
11
ной технологии синтеза тестов в автоматизированной системе технического диагно-
стирования РИС. В результате использования новых моделей и методов синтеза тес-
тов формализовано построение тестов в классе ошибок функционального типа для
РИС, отображаемых в изменениях отношений инцидентности позиций и переходов
сетей Петри, уменьшено время синтеза тестов и их длина при увеличении полноты
проверки. Для РИС уровня сложности беспроводной сетевой системы «WiFi» при
сравнении автоматных методов и методов сетей Петри получено снижение времени
синтеза тестов до 92% (с 90 мин (100%) до 8 мин (8%)) и сокращение длины тестов
до 40% (с 214 (100%) до 130 (60%) условных переходов) при повышении полноты
до 12% (с 94 (88%) до 107 (100%) условных переходов). Синтез тестов на основе те-
стирования отношения инцидентности сети Петри также повышает гибкость тести-
рования, определяемую многовариантностью синтеза тестов и возможностью учета
особенностей РИС.
Разработанные модели и методы синтеза тестов РИС доведены до организации
вычислительных процессов, базовых алгоритмов, структур данных и программ и
внедрены в состав автоматизированной системы технического диагностирования
РИС предприятия ПКП «Лик» (г. Николаев). Результаты диссертационной работы
также внедрены в учебный процесс ОНПУ.
Личный вклад соискателя. Вклад соискателя состоит в развитии и примене-
нии моделей и методов синтеза тестов РИС на базе сетей Петри, основанных на тес-
товых примитивах с определением векторов комплектов позиций, инцидентных вос-
станавливаемым переходам сетей Петри, и декомпозиционном подходе к восстанов-
лению отношений инцидентности сетей Петри в их композиции на основе тестиро-
вания поведения, реализуемого и транслируемого к границам композиции.
Автором развито и использовано тестирование структуры поведения сетей
Петри в их композициях при синтезе тестов для РИС [1,3,29,30,9,36]. Тесты по-
строены как специальные псевдоэйлеровы обходы с помощью системы тестовых
примитивов. Рассмотрены модели взаимодействий сетей Петри в их композициях,
которые позволили определить условия построения тестовых примитивов, реали-
зуемых и транслируемых в композиции [28,3,29,30,9,10,4]. Разработанная информа-
12
ционная технология реализована в программах синтеза тестов для РИС [2,3,29,10,12]
в составе автоматизированной системы технического диагностирования. Автор при-
нимал участие в проведении испытаний программ, а также в анализе их результатов.
Апробация результатов исследований. Результаты исследований доклады-
вались и обсуждались на шести конференциях и семинарах, в том числе на: между-
народной научно-технической конференции «Гарантоспособные (надежные и безо-
пасные) системы, сервисы и технологии», 25-27 апреля 2010, Кировоград, десятой,
одиннадцатой и двенадцатой международной научно-практической конференции
«Современные информационные и электронные технологии», соответственно 24-28
мая 2010 года, 23-27 мая 2011 года и 4-8 июня 2012 года, Одесса, второй и третьей
международной научно-практической конференции молодых исследователей «Со-
временные информационные технологии», 26-27 мая 2012 года и 25-26 апреля 2013
года, Одесса. Результаты работы также докладывались на научно-техническом се-
минаре института компьютерных систем в ОНПУ.
Основные результаты диссертационной работы опубликованы в одиннадцати
научных работах, в том числе пять работ - в профессиональных изданиях из переч-
ня, утвержденного Министерством образования и науки Украины (из них 2 - едино-
личные), шесть - в сборниках научных трудов конференций.

Список литературы

ВЫВОДЫ
В диссертационной работе разработаны и научно обоснованы программные
средства синтеза тестов в составе информационной технологии повышения надеж-
ности РИС, являющиеся компонентой автоматизированной системы технического
диагностирования РИС и обеспечивающие восстановление их работоспособности.
Программы основаны на применении структурно-аналитических моделей и методов
синтеза тестов для сетей Петри и их композиций.
В ходе выполнения диссертационной работы получены следующие результаты:
1. Анализ аналитических и структурно-аналитических моделей и методов син-
теза тестов РИС, их расширений и композиций на основе автоматного подхода по-
зволил сделать вывод о необходимости развития декомпозиционного подхода к син-
тезу тестов на основе использования в качестве моделей сетей Петри, что позволяет
уменьшить время построения, сократить длину тестов, повысить полноту проверки
ошибок, как следствие, сократить срок восстановления работоспособности, повы-
сить надежность РИС.
2. Разработка аналитической модели тестирования РИС на базе сетей Петри и
тестовых примитивов показала целесообразность ее использования при определении
условий тестирования отношения инцидентности векторов комплектов позиций, по
сравнению с автоматными моделями уменьшена (до 20%) размерность аналитиче-
ской модели тестирования, ее асинхронность, событийность, параллелизм в большей
степени соответствуют свойствам РИС.
3. Развитие структурно-аналитической модели тестирования РИС на базе ис-
пользования композиции сетей Петри и выделения у нее троек входящей, исходя-
щей частей и проверяемой сети Петри с композиции показал целесообразность ее
использования при определении условий декомпозиционной разработки тестовых
примитивов для сетей Петри, по сравнению с автоматными моделями уменьшена
(до 25%) размерность структурно-аналитической модели тестирования, сама струк-
129
тура связей сетей Петри в композиции соответствует естественной структуре РИС в
среде многоуровневых сетевых систем.
4. Совершенствование метода синтеза тестов РИС на базе построения псевдо-
эйлерова обхода графа аналитической тестовой модели тестирования РИС с компо-
нентами обхода – тестовыми примитивами позволило уменьшить по сравнению с
автоматными методами затраты времени (до 96%) синтеза тестов при уменьшении
их длины (до 50%) и сохранении полноты проверки.
5. Совершенствование структурно-аналитического метода синтеза тестов РИС
на базе определения и многократного использования тестовых примитивов для уз-
лов структурно-аналитической модели тестирования РИС позволило уменьшить по
сравнению с другими сетевыми автоматными методами затраты времени (до 93%)
синтеза тестов при уменьшении их длины (до 45%) и росте полноты проверки (до
10%). Уровень декомпозиции уменьшает затраты времени (до 90%) синтеза тестов и
их длину (до 67%).
6. Разработанные программы прикладной информационной технологии синте-
за тестов РИС и многоуровневых сетевых систем использованы в составе автомати-
зированной системы технического диагностирования предприятия ПКП «Лик» (г.
Николаев). Модели и методы синтеза тестов для РИС нашли применение в учебном
процессе ОНПУ при проектировании информационных, систем и компьютерных се-
тей.
7. Разработанная методика применения информационной технологии синтеза
тестов РИС на основе предложенных аналитических моделей и методов синтеза тес-
тов с помощью соответствующих программ нашла применение в техническом диаг-
ностировании многоуровневых сетевых систем на предприятии ПКП « Лик» (г. Ни-
колаев).
8. Для РИС среднего уровня сложности, в частности , беспроводной сетевой
системы «WiFi» и сервис-ориентированной Web-системы, при сравнении автомат-
ных методов и методов сетей Петри получено снижение времени синтеза тестов до
92% (с 90 мин (100%) до 8 мин (8%)) и сокращение длины тестов до 40% (с 214
130
(100%) до 130 (60%) условных переходов) при повышении полноты до 12% (с 94
(88%) до 107 (100%) условных переходов), что соответствует аналитическим оцен-
кам. Организация тестов на основе тестирования структуры СП повышает гибкость
тестирования, которая определяется многовариантностью синтеза тестов и возмож-
ностью учета в моделях и методах особенностей конкретных РИС.
9. Разработанные модели, методы, программы и методика предложены к вне-
дрению в учебный процесс кафедры компьютерных интеллектуальных систем и се-
тей ОНПУ в дисциплинах «Надежность, контроль, диагностика и эксплуатация
ЭВМ», «Диагностика компьютерных систем».

СПИСОК ЛИТЕРАТУРЫ
1. Аль Шариф, Васим Модели тестирования механизмов Wi-Fi [Текст] /
Васим Аль Шариф // Научно-технический журнал “Электротехнические и
компьютерные системы. Информационные системы и технологии”. – Одесса. – 2012. –
№ 08(84). – С. 105–109.
2. Аль Шариф, Васим Построение моделей для основных механизмов
беспроводных сетей [Текст] / Васим Аль Шариф // Науково-технічний журнал
“Холодильна техніка і технологія”. – Одеса. – 2012. – № 6(140). – С. 65–71.
3. Аль Шариф, Васим Модели и методы синтеза тестов для
многоуровневых сетевых систем на основе сетей Петри [Текст] / Васим Аль Шариф,
А. Н. Мартынюк, С. А. Нестеренко // Науково-технічний журнал “Вісник
Черкаського державного технологічного університету”. – Черкаси. – 2013. № 2. – С.
60–64. Аль Шариф, Васим Модели взаимодействий в кластерной системе
[Текст] / Васим Аль Шариф, С. О. Пустовой // Матеріали третьої міжнародної
конференції студентів і молодих науковців “Сучасні інформаційні технології 2013”,
Одеса, 25 – 26 квітня, 2013. – С. 62–63.
5. Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и
автоматы). – 2-е изд., перераб. и доп. – Л.: Энергия, Ленингр. отд-ние, 1979. – 232
с. 6. Барашко А.С., Скобцов Ю.А., Сперанский Д.В. Моделирование и
тестирование дискретных устройств. - К.: Наукова думка, 1992. – 288 с.
7. Богомолов А.М., Грунский И.С., Сперанский Д.В. Контроль и
преобразования дискретных автоматов. – К.: Наукова думка, 1975. – 176 с.
8. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретних
систем. – М.: Наука, 1997. – 386 с.
9. Васим Аль Шариф, Мартынюк А.Н. Построение и анализ
многоуровневых моделей протоколов компьютерных сетей // Труды одиннадцатой
международной научно-практической конференции «Современные
информационные и электронные технологии», 23 – 27 мая 2011 года, Одесса. С.147.
132
10. Васим Аль Шариф, Мартынюк А.Н. Многоуровневые модели сетевых
сервисов // Труды двенадцатой международной научно-практической конференции
«Современные информационные и электронные технологии», 5 – 7 июня 2012 года,
Одесса. С.98.
11. Васим Аль Шариф Построение моделей для основных механизмов
беспроводных сетей // Науково-технічний журнал “Холодильна техніка і
технологія”, вип. 6(40), 2012 рік, Одеса, С. 65-71.
12. Васим Аль Шариф, Ваззан Ахмад Построение моделей сетевого
протокола 802.11 // Труды второй международной научной конференции студентов
и молодых ученых «Современные информационные технологии», 26 – 27 апреля
2012 года, Одесса. С.48.
13. Глухов В.С. Убудований контроль спецпроцесорів для оброблення
цифрових підписів // Глухов В.С., Еліас Р. Вісник Національного університету
«Львівська політехніка» «Комп’ютерні науки та інформаційні технології» № 686.
Львів, 2010. С.56-62.
14. Глухов В.С. Виявлення помилок при знаходженні оберненого елемента в
гаусівському нормальному базисі типу 2 полів Галуа GF(2m). // Глухов В.С., Еліас Р.
Науково-технічний журнал «Радіоелектронні і комп’ютерні системи 6(47).
Національний аерокосмічний університет ім. М.Є. Жуковського «Харківський
авіаційний інститут». Харків. «ХАІ». 2010. С. 129 – 134.
15. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки.
Программирование. – К.: Наукова думка, 1989. – 376 с.
16. Грунский И.С., Максименко И.И. Распознавание неструктурированных
объектов. // Труды ИПММ НАН Украины. – Т.21 (2010). – С.76-85.
17. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов. –
К.: Наукова думка, 2004. – 246 с.
18. Дорошенко М.Ю. Исследование и разработка конечно-автоматных
методов синтеза проверяющих тестов для управляющих систем. – Автореф. дис...
канд. техн. наук: 05.13.06 / Томск. гос. ун-т. – Томск, 2007. – 18 с.
133
19. Евтушенко Н.В., Жарикова С.В. Решение автоматных уравнений в
различных приложениях // Вестник КрасГУ. – 2007. – №7. – С.35–39.
20. Евтушенко Н.В., Лебедев А.В., Петренко А.Ф. Построение
проверяющего множества для компоненты последовательной автоматной сети //
Автоматика и телемеханика. – 1994. – № 8. – С.145–153.
21. Зайцев Д.А., Верификация телекоммуникационніх протоколов с
помощью декомпозиции сетей Петри // Зв'язок. – 2005. – №1.
22. Зайцев Д.А., Ингибиторная сеть Петри, исполняющая произвольную
заданную машину Тьюринга // ISSN 1681–6048 System Research & Information
Technologies, 2012, № 2. – С.26-41.
23. Зайцев Д.А., Ингибиторная сеть Петри, исполняющая произвольный
заданный нормальный алгорифм Маркова // Моделирование и анализ информацион-
нывх систем, Т.18, №4 (2011). – С.80-93.
24. Кльоц Ю.П. Трудомісткість безсловникового методу діагностування
цифрових систем // Кльоц Ю.П. Вимірювальна та обчислювальна техніка в
технологічних процесах – Хмельницький: ХНУ.- 2008. - №1. - С. 47 -50.
25. Кудрявцев В.Б., Анализ и синтез абстрактных автоматов // В.Б. Кудряв-
цев, И.С. Грунский, В.А. Козловский, Фундаментальная и прикладная математика. –
2009, том 15, № 4. – С.101—175.
26. Куфарева И.Б., Евтушенко Н.В., Петренко А.Ф. Синтез проверяющих
тестов для недетерминированного автомата относительно редукции // Автоматика и
вычислительная техника. – 1998. – № 3. – C.64–70/
27. Мартынюк А.Н. Базовые модели прототипа системы синтеза тестов //
Науково-техніч. журнал «Радіоелектронні і комп'ютерні системи». 8(27) Харків
“ХАІ”, – 2007. – С.157–162.
28. Мартынюк, А. Н. Анализ протокола Wi-Fi вычислительных сетей
[Текст] / А. Н. Мартынюк, Васим Аль Шариф // Науково-технічний журнал
“Радіоелектронні і комп'ютерні системи”. – Харків: ХАІ. – 2010. – № 7(48). – С. 39–
43.
134
29. Мартынюк, А. Н. Модели тестирования для композиций сетей Петри
[Текст] / А. Н. Мартынюк, Васим Аль Шариф // Науково-технічний журнал
“Холодильна техніка і технологія”. – Одеса. – 2013. – № 2(142). – С. 84–87.
30. Мартынюк А.Н., Васим Аль Шариф Модели протоколов беспроводных
сетей // Труды десятой международной научно-практической конференции
«Современные информационные и электронные технологии», 24 – 28 мая 2010 года,
Одесса. С.144.
31. Основы технической диагностики. Кн. 1. Модели объектов, методы и
алгоритмы диагноза / Под ред. П.П. Пархоменко. – М.: Энергия, 1976. – 464 с.
32. Скобцов Ю.А., Скобцов В.Ю. Логическое моделирование и
тестирование цифровых устройств. – Донецк: ИПММ НАН Украины, ДонНТУ,
2005.3 –3 .436 сС. идорова Н.С. Преобразования сетей Петри: Дис. канд. физ.-мат. наук.
Ярославль: ЯрГУ. 1998.
34. Спицына Н.В., Евтушенко Н.В. Трансляция тестов для компоненты
автоматной сети посредством решения автоматных уравнений // Материалы пятой
междунар. конф. «Автоматизация проектирования дискретных систем». – Минск,
НАН Беларуси, – 2004. – Т. 2. – С.96–103.
35. Спицына Н.В. Синтез тестов для проверки взаимодействия дискретных
управляющих систем методами теории автоматов // Автореф. дис. канд. техн. наук:
05.13.06. – Томск, – 2005. – 18 с.
36. Сугак, А. С. Анализ многоуровневых эволюционных мультиагентных
систем [Текст] / А. С. Сугак, Васим Аль Шариф, А. Н. Мартынюк // Труды
одиннадцатой международной научно-практической конференции “Современные
информационные и электронные технологии”, Одесса , 23 – 27 мая, 2011. – 148 c.
37. Тарасюк И.В. Эквивалентностные понятия для моделей параллельных и
распределенных систем: Дис. канд. физ.-мат. наук. Новосибирск: ИСИ СО РАН.
1997.
38. Хоар Ч. Взаимодействующие помледовательные процессы. – М.: Мир,
1989. – 289 с.
135
39. Шмелева Т.П., Параметрическая модель IP-сетей в форме раскрашенных
сетей Петри. // Т.П. Шмелева Наукові записки УНДІЗ, №1(9), 2009. – С.70-77.
40. Abdulla A.P., Purushothaman I., Nylen A. Unfoldings of Unbounded Petri
Nets // Proc. CAV 2000. — Berlin a.o.: Springer-Verlag, 2000. — P. 495—507. — (Lect.
Notes Comput. Sci.; Vol. 1855).
41. Anisimov N.A. A Notion of Petri Net Entity: A Modular Approach to Design
of Distributed Sysytems, Internal Report CN-92-03, Institute of Automation and Control
Processes, Vladivostok, 1992. Submitted.
42. Autant С., Schnoebelen Ph. Place bisimulations in Petri nets // Proc. of
ICATPN'92. Lecture Notes in Computer Science. 1992. V.616. P.45-61.
43. Baeten J.C.M., Weijland W.P. Process Algebra. Cambridge Tracts in
Theoretical Computer Science, 18, Cambridge University Press, 1990.
44. Bieber B., Fleischhack H. Model Checking of Time Petri Nets Based on
Partial Order Semantics // Proc. CONCUR'99. — Berlin a.o.: Springer-Verlag, 1999. — P.
210—225. — (Lect. Notes Comput. Sci.; Vol. 1664).
45. Bolognesi T., Smolka S. A., Fundamental Results for the Verification of
Observational Equivalence: a Survey, in Protocol Specification, Testing, and Veri_cation,
VII: Proc.of the IFIP WG 6.1 7th International Symposium, eds. H. Rudin, C. H. West,
North{Holland, 1987, pp.165-179.
46. Couvreur J.-M., Grivet S., Poitrenaud D. Designing an LTL Model-Checker
Based on Unfolding Graphs // Lect. Notes Comput. Sci. — 2000. — Vol. 1825. — P.
123—145.
47. De Nicola R. Extensional Equivalences for Transition Systems, Acta
Informatica, Vol. 24, 1987, pp.211–237.
48. Esparsa J. Model-Checking Using Net Unfoldings // Lect. Notes Comput. Sci.
— 1993. — Vol. 668. — P. 613—628.
49. Esparza J., Heljanko K. A New Unfolding Approach to LTL Model-Checking
// Lect. Notes Comput. Sci. — 2000. — Vol. 1853. — P. 475—486.
136
50. Esparza J., Heljanko K. Implementing LTL Model Checking with Net
Unfoldings // Lect. Notes Comput. Sci. — 2001. — Vol. 2057. — P. 37—56.
51. Esparsa J., Römer S. An unfolding algorithm for synchronous product of
transition systems // Proc. of CONCUR’99, — Berlin a.o.: Springer-Verlag, 1999. — P.
2—20. — (Lect. Notes Comput. Sci.; Vol. 1664).
52. Esparsa J., Römer S., Volger W. An Improvement of McMillan’s Unfolding
Algorithm // Proc. TACAS'96. — Berlin a.o.: Springer-Verlag, 1997. — P. 87—106. —
(Lect. Notes Comput. Sci.; Vol. 1055).
53. Graves B. Computing reachability properties hidden in finite net unfoldings. //
Lect. Notes Comput. Sci. — 1997. — Vol. 1346. — P. 327—341.
54. Hartmanis J., Stearns R.E. Algebraic structure theory of sequential machines.
– Prentice – Hall, Inc.. – 1966. – C.340.
55. Heljanko K. Model Checking with Finite Complete Prefixes is PSPACEComplete
// Proc. CONCUR'2000. — Berlin a.o.: Springer-Verlag, 2000. — P. 108—122.
— (Lect. Notes Comput. Sci.; Vol. 1877).
56. Jancar P., Moller F. Techniques for decidability and undecidability of
bisimilarity // Proc. of CONCUR'99. Lecture Notes in Computer Science. 1999. V.1664.
P.30-45.
57. Jensen K. Coloured Petri Nets. Vol. 1. — Berlin a.o.: Springer, 1995.
58. Jensen K. Coloured Petri Nets. Vol. 2. — Berlin a.o.: Springer, 1995.
59. Kondratyev A., Kishinevsky M., Taubin A., Ten S. A Structural Approach for
the Analysis of Petri Nets by Reduced Unfoldings // 17th Intern. Conf. on Application and
Theory of Petri Nets, Osaka, June 1996. — Berlin a.o.: Springer-Verlag, 1996 — P. 346—
365. — (Lect. Notes Comput. Sci.; Vol.1091).
60. Kozura V.E. Unfoldings of Coloured Petri Nets. — Novosibirsk, 2000. — 34
p. — (Prepr. /SB RAS. IIS; N 80).
61. Kozura V.E. Unfoldings of Timed Coloured Petri Nets // Proc. Workshop
CS&P'2001, Warsaw, October 3—5, 2001. — P. 128—139.
137
62. Kozura V.E. LTL model checking of coloured Petri nets based on net
unfoldings // Joint Bull. of NCC&IIS. Ser.: Comp. Sci. — 2001. — № 14. — P. 83—101.
63. McMillan K.L. Using Unfolding to Avoid the State Explosion Problem in the
Verification of Asynchronous Circuits // Lect. Notes Comput. Sci. — 1992. — Vol. 663.
— P. 164—174.
64. Melzer S., Römer S. Deadlock Checking Using Net Unfoldings // Proc. Conf.
On Computer Aided Verification (CAV'97), Haifa, 1997. — Berlin a.o.: Springer-Verlag,
1997. — P. 352—363. — (Lect. Notes Comput. Sci.; Vol. 1254).
65. Milner R. A Calculus for Communication Systems. Lecture Notes in
Computer Science, 92, Springer{Verlag, 1980, p.170.
66. Muth P. A nine-valued circuit model for test generation // IEEE Trans.
Comput. – 1976. – N6. – P.630–636.
67. Paige R., Tarjan R.E. Three Partitioning Re_nement Algorithms. SIAM
Journal of Computing, Vol.16, No.6, 1987, pp.973-989.
68. Park D. M. R. Concurrency and Automata on In_nite Sequences, in:
Procedeengs 5th GI Conference, ed.P. Deussen, Lecture Notes in Computer Science, 104,
Springer{Verlag, 1981, pp.167-183.
69. Peterson J.L. Petri Net Theory and the Modelling of Systems, Prentice Hall
Inc., 1981. – 230.
70. Petrenko A., Yevtushenko N., Bochmann G.V. Fault models for testing in
context // Proceedings of the IFIP Joint Intern. Conf. FORTE/PSTV. – 1996. – P.163–178.
71. Schnurmann H.D., Lindbloom E., Carpenter R.G. weighted random testpattern
generator //IEEE Trans. Comput. – 1975. – C24, N7. – P.695–700.
72. Schnoebelen Ph., Sidorova N. Bisinnilation and the reduction of Petri nets //
Proc. of ICATPN'2000. 2000.
73. Sridhar T., Hayes J.P. A Functional Approach to Testing Bit-sliced
Microprocessors // IEEE Trans. On Comput. – 1981. – C-30. – N8. – P.563–571.
74. Valmari A. The State Explosion Problem // Lect. Notes Comput. Sci. —
1998. —Vol.1491. — P. 429—528.
138
75. Valmari A. Stubborn Sets of Coloured Petri Nets // Proc. 12th Intern. Conf.
on Application and Theory of Petri Nets. — Gjern, 1991. — P. 102—121.
76. Van Glabbeek R. J. The Linear Time | Branching Time Spectrum, in:
CONCUR'90, Theories of Concurrency: Uni_cation and Extension, ed. J.C.M.Baeten,
J.W.Klop, Lecture Notes in Computer Science, 458, Springer{Verlag, 1990.
77. Vardy M.Y., Wolper P. An automata-theoretic approach to automatic
program verification // Proc. 1st IEEE Symp. on Logic in Computer Science. — 1986. —
P. 322—331.
78. Wallner F. Model-Checking LTL Using Net Unfoldings // Proc. Conf. on
Computer Aided Verification (CAV'95), Vancouver, 1995. — Berlin a.o.: Springer-
Verlag, 1998.— P. 207—218. — (Lect. Notes Comput. Sci.; Vol. 1427).