Результаты экспериментов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

Кафедра математического моделирования и анализа данных

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

Курсовая работа

Батуры Олега Владимировича

студента 3 курса,

специальность

«Компьютерная безопасность»

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

доктор физ.-мат. наук,

заведующий кафедрой ММАД

Ю. С. Харин

Минск, 2015

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ математики и информатики

Кафедра математического моделирования и анализа данных

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

Студент Батура Олег Владимирович, 3 курс, 9 группа

1. Тема работы Цепь Маркова с частичными связями и переменным шаблоном

2. Срок сдачи студентом законченной работы________ 2015 г.

3. Перечень вопросов, подлежащих разработке

· Исследовать вероятностные характеристики модели цепи Маркова с частичными связями и переменным шаблоном. Найти -мерное распределение вероятностей .

· Построить компьютерную модель ЦМ с переменным шаблоном.

· Построить статистические оценки параметров модели при известной функции шаблона , исследовать свойства оценок.

· Построить оценки параметров модели при периодически изменяющемся, но неизвестном шаблоне.

Руководитель курсовой работы______________ / Ю. С. Харин/ ______ 2015 г.

Задание принял к исполнению_______________ 2015 г.

ОГЛАВЛЕНИЕ

Введение. 4

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 5

1.1. Цепь Маркова порядка . 5

1.2.Цепь Маркова с частичными связями ЦМ . 7

1.3.Цепь Маркова с частичными связями и переменным шаблоном ЦМ 9

1.4.Статистическое оценивание параметров ЦМ , состоятельность оценок 11

1.5.Статистическое оценивание параметров ЦМ . 15

2.ПРАКТИЧЕСКАЯ ЧАСТЬ. 16

2.1.Описание программы.. 16

2.2.Моделирование временного ряда длительности . 17

2.3.Построение оценок максимального правдоподобия и . 18

2.4.Результаты экспериментов. 21

2.5.Вывод. 23

Заключение. 24

Список использованной литературы.. 25

Введение

При математическом моделировании сложных систем и процессов в различных научных сферах часто возникает необходимость построения вероятностно-статистических моделей дискретных временных рядов , где пространство состояний — конечное множество мощности с длинной памятью [1]. Известной моделью таких дискретных временных рядов является цепь Маркова достаточно высокого порядка , определяющего длину памяти; если , то цепь Маркова называется простой, если — сложной. Однако для такой модели число параметров растет экспоненциально при увеличении порядка : , и для статистического оценивания параметров требуется иметь реализацию не всегда доступной на практике длительности . В связи с этим актуальна проблема построения малопараметрических моделей цепей Маркова высокого порядка. В данной работе исследуется малопараметрическая модель цепи Маркова порядка с частичными связями ЦМ , рассмотренная в [2], для которой шаблон связей зависит от времени, исследуются ее вероятностные характеристики, строятся статистические оценки параметров при известной функции шаблона, а также при периодически изменяющемся, но неизвестном шаблоне.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1. Цепь Маркова порядка

В криптологии для моделирования дискретных временных рядов с глубиной памяти используется цепь Маркова порядка (ЦМ ), обобщающая модель простой цепи Маркова [3].

Определение.Цепь Маркова , порядка с пространством состояний , определенная на вероятностном пространстве ( ) и временной области , характеризуется обобщенным марковским свойством:

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

Цепь Маркова ЦМ( ) характеризуется -мерным начальным распределением вероятностей

и -мерной матрицей вероятностей одношаговых переходов в момент времени :

=

Матрица при этом удовлетворяет условиям нормировки (если она не зависит от времени, то есть , ЦМ( ) в таком случае называется однородной):

В таком случае -мерное распределение вероятностей имеет вид:

Число независимых параметров, определяющих матрицу вероятностей одношаговых переходов для однородной ЦМ( ), равно .

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

Возникает задача поиска малопараметрической модели цепи Маркова высокого порядка, для которой число параметров в матрице задается числом параметров . Одной из таких моделей является цепь Маркова порядка с частичными связями (ЦМ ) [2].

1.2. Цепь Маркова с частичными связями ЦМ

Пусть – однородная ЦМ( ), заданная на вероятностном пространстве ( ) с некоторой ( )-мерной матрицей вероятностных переходов

Рассмотрим – параметр, который называется числом связей; – произвольный целочисленный -вектор с упорядоченными компонентами:

Этот вектор называется шаблоном связей, – множество всевозможных таких векторов с компонентами, мощность – некоторая -мерная стохастическая матрица.

Определение.Цепь Маркова называется цепью Маркова -го порядка с -частичными связями и обозначается ЦМ( ), если ее вероятности одношаговых переходов имеют вид:

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

В данном случае, вместо параметров ЦМ( ) данная модель полностью определяется параметрами , что играет существенную роль на практике.

Замечание.Если , , то и ЦМ( ) представляет из себя цепь Маркова порядка , то есть ЦМ( ЦМ .

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

Следует отметить, что -мерное распределение вероятностей для данной модели имеет следующий вид:

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

1.3. Цепь Маркова с частичными связями и переменным шаблоном ЦМ

Пусть – однородная ЦМ( ), заданная на вероятностном пространстве ( ), определенная ранее. Рассмотрим обобщение данной модели, когда шаблон зависит от времени :

причем:

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

.

В частности, при имеются два различных шаблона и которые циклично повторяются:

Для данного частного случая -мерное распределение вероятностей имеет вид:

При произвольной модели зависимости шаблона от времени имеем общую формулу:

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

Далее рассмотрим задачу статистической оценки параметров модели ЦМ при известном шаблоне и поиска свойств оценок.

1.4. Статистическое оценивание параметров ЦМ , состоятельность оценок

Для статистического оценивания параметров ЦМ( ) будем пользоваться методом максимального правдоподобия.

Рассмотрим задачу построения оценок максимального правдоподобия (ОМП) для параметров шаблона и стохастической матрицы по наблюдаемой реализации длительности .

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

– частота -граммы для шаблона , удовлетворяющая условию нормировки:

Для модели ЦМ логарифмическая функция правдоподобия имеет вид:

Для того, чтобы найти ОМП для матрицы , необходимо решить задачу на условный экстремум:

В результате получаем условную ОМП для матрицы ( ):

Далее рассматривается задачу поиска ОМП для шаблона .

Пусть – стационарное распределение вероятностей ЦМ . Пусть ЦМ – стационарна ( ), тогда распределение вероятностей -граммы для шаблона будет иметь следующий вид:

Соответствующая частотная оценка вероятностей:

.

Энтропия -мерного распределения вероятностей запишется в виде:

Количество информации по Шеннону, содержащейся в -грамме о будущем символе :

Логарифмическая функция правдоподобия для оценки имеет следующий вид:

где – подстановочная оценка энтропии, получающаяся при подстановке вместо истинных значений их оценок { }.

Учитывая, что не зависит от , добавляя также не зависящее от слагаемое , а также используя тот факт, что:

приходим к следующей ОМП шаблона :

где – подстановочная оценка количества информации по Шеннону, получающаяся при подстановке вместо истинных значений их оценок { }.

Теорема 1.Если ЦМ является стационарной, то при истинном шаблоне и оценка состоятельна:

Теорема 2.Если ЦМ является стационарной и шаблон идентифицируемый, то при оценка состоятельна:

1.5. Статистическое оценивание параметров ЦМ

Для ЦМ оценки параметров генератора с переменной обратной связью строятся аналогично модели с постоянной обратной связью с учетом периодически изменяющегося шаблона .

Логарифмическая функция правдоподобия имеет следующий вид:

Задача на условный экстремум

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

Теорема 3.Если ЦМ является стационарной, то при истинном шаблоне и оценка состоятельна:

Теорема 4.Если ЦМ является стационарной и шаблон идентифицируемый, то при оценка состоятельна:

ПРАКТИЧЕСКАЯ ЧАСТЬ

Описание программы

Построена компьютерная модель цепи Маркова с частичными связями и переменным шаблоном со следующими входными параметрами:

· глубина предыстории однородной цепи Маркова ЦМ .

· длина временного ряда с пространством состояний .

· Шаблоны и , которые повторяются с периодом

· Стохастическая матрица вероятностей одношаговых переходов для шаблонов:

В частном случае, при данная матрица имеет следующий вид:

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

2.2. Моделирование временного ряда длительности

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

В частности, если предыстория элемента имеет вид

,

то при

Элементы с четными номерами моделируются аналогичным образом с использованием шаблона

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

1. Генерируется число в диапазоне .

2.

В результате имеется временной ряд , где пространство состояний – конечное множество мощности .

2.3. Построение оценок максимального правдоподобия и

Логарифмическая функция правдоподобия имеет вид:

Задача на условный экстремум:

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

Используя тот факт, что матрица стохастическая,

, условная оценка полностью определяется шаблоном

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

В частности, при имеется следующая система уравнений:

где частота выпадения при предыстории .

Условной оценкой максимального правдоподобия является решение данной системы:

.

Логарифмическая функция правдоподобия перепишется в следующей форме:

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

Оценка максимального правдоподобия матрицы имеет вид:

Результаты экспериментов

Экспериментальные оценки параметров построены при следующих входных данных:

Рис. 1.Зависимость числа ошибок распознавания истинного шаблона при 100 экспериментах от

При :

При :

При :

При :

Вывод

Результаты показывают состоятельность оценки при истинном шаблоне и . Также очевидна состоятельность оценки шаблона при .

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

Заключение

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

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

Список использованной литературы

1. Алферов А. П. и др. Основы криптографии / Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. – 2-е изд., испр. и доп. – М.: Гелиос АРВ, 2002. – 480 с.

2. Харин Ю. С., Петлицкий А. И. Цепь Маркова -го порядка с частичными связями и их статистическое оценивание – Дискретная математика, 2007. – Т. 12, вып. 2. С. 109-130.

3. Харин Ю. С. и др. Криптология / Харин Ю. С., Агиевич С. В., Васильев Д. В., Матвеев Г. В. – Мн.: БГУ, 2013. – 511 с.