Оценка временных затрат для осуществления распределенного перебора в гетерогенных системах при помощи временных волновых систем

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 75 И.А. Трещёв
Оценка временных затрат для осуществления распределенного перебора в гетерогенных системах при помощи временных волновых систем
Рассматривается метод получения априорной верхней и нижней оценок временных затрат на осуществление распределенного перебора в гетерогенных системах при помощи временных волновых систем. Приведены временные оценки для различных вариантов построения гетерогенных систем.
Ключевые слова: распределенный перебор, оценка временных затрат.
Для задач защиты информации актуальной является проблема распределенного перебора в неоднородных (гетерогенных) системах. Пусть область перебора вариантов D, например для задачи отыскания неприводимого многочлена над заданным полем [1], состоит из векторов x = (xi, X2,…, xn), если данную область можно представить в виде объединения непересекающихся
подобластей, то представляется возможным применение методики распределенного перебора. Данная методика заключается в распределении непересекающихся подобластей исходной области D между различными вычислительными узлами так, чтобы свести обмены информацией между узлами к минимуму, наилучший вариант — к нулю. Довольно часто при реализации распределенного перебора используют парадигму «один ведущий, много ведомых» [2].
Одной из формальных математических моделей для организации распределенного перебора и оценки временных затрат на его исполнение является модель временных волновых систем [4]. Данная модель вполне адекватно описывает вычислительный процесс для неоднородных сред за счет введения времени исполнения каждой операции, выполняемой в процессе вычислений, и времени передачи данных по коммуникационной среде.
Например, в настоящее время в сети Internet существует проект по распределенному перебору всех чисел Мерсена, но до сих пор не ясно, сколько времени будет потрачено в рамках данного проекта для оценки простоты очередного числа. В связи с этим актуальной является проблема оценки времени исполнения некоторого вычислительного процесса для распределенных, разнородных, объединенных вычислительных узлов, таких как компьютеры в сети Internet.
Теоретические сведения
Рассмотрим гетерогенную вычислительную систему, состоящую из различных вычислительных узлов (со стандартными процессорами, устройствами хранения данных, блоками питания и т. д.), подключенных к сети (локальной или глобальной) при помощи стандартных протоколов передачи информации, например Ethernet, Fast Ethernet, Gigabit Ethernet.
Для каждого вычислительного узла заданы его производительность (количество операций с плавающей точкой в секунду) и время выполнения простых операций (сложение, вычитание, умножение, деление и т. д.) на нем. Для сети и используемых в ней протоколов заданы параметры передачи информации (пропускная способность, латентность, которая складывается из программной и аппаратной задержек), причем сеть — однородна в том смысле, что все узлы передают данные друг другу по одному и тому же протоколу. Размеры передаваемых между вычислительными узлами блоков данных одинаковы. Пусть для рассматриваемой вычислительной системы латентность на прием данных не совпадает с латентностью на передачу данных.
Определение. Моделью волновой системы или просто волновой системой [3] будем называть простой ацикличный частичный орграф
G = (A, V, dom, cod),
у которого для каждой вершины v e V, её прообразы dom 1 (v), cod 1 (v), если они определены, являются конечными линейноупорядоченными множествами. Предполагается, что в состав волновой системы включено отношение порядка, обозначаемое символом & lt-.
Под временной волновой системой понимается волновая система, для которой определены пара вещественных чисел т& gt-0 и т& gt-0, и функция t: V^R во множество вещественных чисел, принимающая неотрицательные значения. Числа т & gt- 0 и т & gt- 0 интерпретируются как время записи в канал и чтения из канала, связывающего два вычислительных узла. Значения t (v) — время выполнения
операции, соответствующей вершине частичного орграфа.
Вершинам орграфа временной волновой системы можно поставить в соответствие вычислительные узлы гетерогенной системы, которые выполняют различные операции по ребрам связи между ними. Функция t будет определять время исполнения вычислений для каждой из вершин, числа
т и т в сумме определяют время передачи данных между вычислительными узлами.
В работе [4] было показано, что для временной волновой системы время её функционирования не превзойдет времени функционирования всех вершин и времени передачи данных по всем ребрам:
Z t (v)+1A 1(т + т)& gt-TAWS & gt-d (max (l)).
veV leTraceAWS
Величину Z t (v)+1A | (т + т) назовем верхней оценкой времени работы данной временной вол-
veV
новой системы и обозначим T^WS, а d (max (l)) — нижней оценкой и обозначим T^^Ws.
leTraceAWS
Определим AWS* - множество всевозможных волновых систем. Определим отношение равенства на множестве AWS* следующим образом:
V AWSi, AWS2 e AWS* AWSi = AWS2 тогда и только тогда, когда Ai = A2, V1 = V2, dom1=dom2,
codi=cod2.
Параллельная композиция
Определим операцию «+» параллельной композиции для двух волновых систем следующим образом:
Пусть AWS = (A, V, dom, cod), AWS' = (A'-, V, dom', cod), тогда AWS + AWS' = AWS+, в случае, если AnA' = 0, Vn V = 0. AWS+ = (AuA'-, VuV, domudom'-, coducod).
Утверждение 1. Операция «+» — коммутативна и ассоциативна. Доказательство:
1) Коммутативность: Докажем, что AWS + AWS = AWS + AWS = = AWS+, AWS + AWS = AWS+, AWS+ = (AuA'-, VuV, domudom', coducod), AWS'- + AWS = AS, AS = (A'- u A, V u V, dom'- u dom, cod ucod), AWS+ =AS (это следует из коммутативности объединения).
2) Ассоциативность: AWS1 + (AWS2 + AWS3) = (AWS1 + AWS2) + + A WS3 = A WSДоказательство аналогично предыдущему и следует из ассоциативности объединения.
Обозначим AWS0 — волновую систему, у которой множество, А пусто, множество V пусто, множество dom пусто и множество cod пусто: AWS0=(0, 0, 0, 0). AWS0 e AWS'-* (по определению AWS*).
Утверждение 2. (AWS*, +) — коммутативная полугруппа.
Доказательство: по определению V AWS1, AWS2, AWS1 + AWS2 e AWS* и операция «+» коммутативна и ассоциативна (Утверждение 1).
В дальнейшем AWS0 будем называть пустой волновой системой. Как видно из рис. 1, параллельная композиция волновых систем соответствует независимому их выполнению.
Утверждение 3. (AWS*, +) — коммутативный моноид.
Доказательство:
Необходимость: единицей этого моноида является пустая волновая система. Нетрудно убедиться в том, что V AWS e AWS* AWS+AWS0 = A WS0+A WS = A WS.
Достаточность: докажем от противного. Предположим, что 3 AWS ф AWS0, такая, что V AWS e AWS* имеет место AWS + AWS'- = AWS'-+AWS = AWS. По определению AWS+AWS = (AuA'-, VuV, domudom'-, coducod). AWS+AWS'- = AWS+ = AWS, AWS+ = (AuA'-, VuV, domudom'-, coducod), отсюда следует AuA'- =A, VuV=V, domudom'-=dom, coducod =cod, откуда заключаем, что A'-=0, V=0,
Рис. 1. Пример параллельной композиции двух волновых систем
dom'-=0, cod=0 — противоречие, т. е. AWS =AWS0, а значит, пара (AWS*, +) — коммутативный моноид (единица единственна).
Утверждение 4. (AWS*, +) — не группа.
Доказательство: пусть V AWS e AWS1*, такой, что AWS' ф AWS0 и 3 AWS1eAWS*, AWS1^AWS0 такая, что AWS'-+AWS1 = AWS1+AWS'-=AWS0. По определению AWS' + AWS = (A'-uA1, VuV1, dom'-udom1, coducod1).
Одно из множеств A, V, dom, cod не равно пустому множеству и одно из множеств A, V, dom, cod не равно пустому множеству. Отсюда следует, что VAWS, AWS1, не равных AWS0, AWS1 + AWS'- ф ф AWS0. Значит, получено противоречие — утверждение доказано.
Временные оценки параллельной композиции временных волновых систем
Пусть
AWS = (V, A, dom, cod, т, т,^),
AWS'- = (V'-, A'-, dom'-, cod'-, т '-, т, t'-), тогда AWS + AWS'- = AWS+, в случае, если AnA'-=0, VnV=0. AWS+ = (AuA '-, VuV, domudom'-,
coducod).
Предложение 1
X t (v) + X t'-(v)
veV veV
-\A |(т + т)+1A'- 1 (т'- + т'-)] & gt- TAWS+ & gt-min
d (max (l)), d (max (l))
leTraceAWS leTraceAWS'-
Доказательство:
Запишем в более сжатой форме формулировку предложения
7^max T^max ^ n-,. /^min ^min
AWS + TawS'- & gt-TAWS+ & gt-mm (TAWS'-TAWS), ясно, что параллельная композиция двух волнов^іх систем не может функционировать быстрее, чем функционирует самая медленная ее составляющая, и медленнее, чем суммарное время, затраченное на функционирование каждой волновой системы в отдельности.
Предложение 1 допускает обобщение для семейства гибридных временных волновых систем.
Теорема 1. Пусть AWS+ =XAWS, тогда справедливо XTmaS & gt-TAWS+ & gt-min (TAWS).
і і 1 1 1
Доказательство:
Для случая двух временных волновых систем утверждение теоремы следует из предложения 1. Для произвольного количества временных волновых систем доказательство может быть получено по индукции.
Приведенная теорема позволяет получать априорные оценки времени функционирования временной волновой системы полученной в результате параллельной композиции произвольного числа взаимодействующих вычислительных процессов (узлов), если заданы оценки каждой составляющей.
Отметим, что параллельная композиция на множестве временных волновых систем — конструкция общая, что позволяет находить априорную верхнюю и нижнюю оценки функционирования результирующей временной волновой системы, даже в случае, когда исходные временные волновые системы описывали различные вычислительные процессы в различных вычислительных средах.
Последовательная композиция волновых систем
Пусть AWS = (A, V, dom, cod), AWS'- = (A'-, V, dom '-, cod), AnA'- = VnV = domndom'- = codncod = = 0, V = Vin u Vfu V0ut, V = Vin'- u Vf u uV0uf.
И пусть заданаf V0ut -& gt- Vin- - биективное отображение.
Тогда определим операцию последовательной композиции на множестве волновых систем следующим образом, см. рис. 2:
AWS — AWS = AWS0, AWS0 = (A0, V0, dom0, cod0), Vа = V u V, A0 = Au u A'- u Aa, cod0 = cod u cod u c0da, dom0 = dom u dom'- u doma, |Aa| = | V0ut| и для V ve V0ut З aeAa такая, что dom°(a) = v, и эти стрелки образуют doma, VaeAa coC0(a)=/(Com0(a)).
Утверждение 5. Операция — ассоциативна
(AWS- AWS'-) — AWS'- '- = AWS — (AWS'- - AWS'-'-).
Доказательство: следует непосредственно из определения.
лжб
ЛЖБ'-
о
у0
01,1
Рис. 2. Пример последовательной композиции двух волновых систем
Утверждение 6. Операция -^не коммутативна.
Доказательство: существование биекции между УоШ и в общем случае не влечёт существование биекции между? т и Ко^'-.#.
Утверждение 7. Пара (ЛНБ*, — полугруппа.
Доказательство: по утверждению 5 операция ^ ассоциативна и V ЛЖБ и ЛЖ8'-, ЛЖБ ^ ЛЖБ'- е ЛЖБ*.
Утверждение 8. Пара (ЛЖБ'-*, ^) — не моноид.
Доказательство: аналогично доказательству утверждения 4.
Последовательная композиция волновых систем определяет новую волновую систему, которая функционирует подобно первой, а после ее выполнения — как вторая, причем данные с выхода первой передаются на вход второй.
Временные оценки последовательной композиции гибридных временных волновых систем
Пусть заданы две гибридные временные волновые системы:
ЛЖБ = (V, Л, ёот, соё, т, т,?),
Л НБ'- = (V'-, Л', ёот, соа'-, т '-, 7,? '-), тогда ЛЖБ ^ ЛЖБ'- = ЛЖЪ°, а для Ла время посылки данных равно а, приема Ь, тогда справедливо следующее
Предложение 2
X? (у) + X? (у) уе? уеГ
Доказательство: Запишем в
тах, т^шах
[|Л|(т+т)+|Л'-|(Т + т'-)]+|Ко"г|(а+Ь)& gt-ТЛто & gt-й (шах (/)) + й (шах (/)) + (а+Ь).
1еТгасвЛж$ 1еТгасвЛж$'-
более сжатой форме формулировку предложения ТшаХ'- + ТшЖЖХ& quot- + Кои? |(а + Ь) & gt-Тлж$+ & gt-ТЛЖъ'- + ТЛЖ + (а + Ь), очевидно, что последовательная композиция двух гибридных временных волновых систем не может функционировать быстрее, чем сумма минимальных времен функционирования каждой из них, учитывая затраты на пересылку пусть даже одного экземпляра данных между составляющими композиции. Также ясно, что время функционирования этой композиции не превзойдет суммарное время, затраченное на функционирование каждой гибридной временной волновой системы в отдельности и пересылки всех экземпляров данных, между выходными вершинами первой волновой системы и входными вершинами второй.
Предложение 2 допускает обобщение для семейства гибридных временных волновых систем.
Теорема 2. Пусть ЛЖБ0 = ЛЖБЛН52 ^ЛЖБп, для Л1а время посылки данных равно
а], приема Ь, для Л2а время посылки данных равно а2, приема Ь2 и т. д., тогда справедливо Х (| Чи, | (а, — + Ь)+ТШ,") & gt- ТЛ нь & gt- ХТЛи, + а, +Ь).
Доказательство:
Для случая двух гибридных временных волновых систем утверждение теоремы следует из предложения 2. Для произвольного количества волновых систем доказательство может быть получено по индукции.
Приведенная теорема позволяет получать априорные оценки времени функционирования гибридной временной волновой системы, полученной в результате последовательной композиции произвольного числа взаимодействующих вычислительных систем, выполняющих некоторые вычисления параллельно, если заданы оценки каждой составляющей.
Причем так же, как и для параллельной композиции, не делается никаких предположений относительно состава вычислительных сред, которые были описаны при помощи исходных временных волновых систем.
Методика расчета времени, необходимого на перебор
Рассмотрим классический пример распределенного перебора ключей из множества X. Пусть мощность множества X кратна 4. Пусть процесс шифрования исходного сообщения размером 10 бит состоял в последовательном применении алгоритма Ба8е64, затем проводилось гаммирование по ключу из множества X, далее выполнялся циклический сдвиг каждого разряда сообщения на 4 бита влево.
Пусть у нас имеется гетерогенная (неоднородная) вычислительная система с 24 вычислительными узлами, для данной вычислительной системы на прием данных одним вычислительным узлом тратится 1 с, на посылку — 2 с. Пусть специализированные узлы способны сдвигать некоторую последовательность на 1 бит вправо за 1 такт, другие могут выполнять сложение по модулю 2 последовательности из 10 бит за 1 такт, третьи — выполнять дешифрование по алгоритму Ба8е64 последовательности из 10 бит за 1 такт. Пусть каждый такт каждого вычислительного узла составляет 1 с.
Рассмотрим временную волновую систему ЛНЪ1 (рис. 3), вершина которой выполняют сдвиг вправо на 1 бит исходной последовательности, множество ее ребер пусто, время исполнения операции в вершине — 1 такт, т = 2 и т = 1.
Рассмотрим временную волновую систему ЛЖБ' (рис. 4), вершина которой выполняют сложение по модулю 2 последовательности из 10 бит, множество ее ребер пусто, время исполнения операции в вершине — 1 такт, т = 2 и т = 1.
Рассмотрим временную волновую систему ЛН$ 1 (рис. 5), вершина которой выполняет дешифрование последовательности из 10 бит по алгоритму Ба8е64, множество ее ребер пусто, время исполнения операции в вершине — 1 такт, т = 2 и т = 1.
Используя введенную операцию последовательной композиции, можно получить новую временную волновую систему, которая будет соответствовать сдвигу вправо на четыре разряда:
Далее рассмотрим последовательную композицию временной волновой системы, соответствующей сдвигу на 4 разряда вправо, затем выполнению гаммирования по ключу из множества X и
AWS
AWSl
AWS'-
Рис. 3. Временная волновая система
для сдвига вправо на 1 бит
Рис. 4. Временная волновая система для сложения по модулю 2
Рис. 5. Временная волновая система для сложения по модулю 2
По теореме 2 для последовательной композиции временных волновых систем получим:
І і
Е (1*(т+т) + 1)& gt-TAWS0 & gt-Е (1 + т+т),
І і
3*4& gt-TAwSo & gt-3*4, TAWS0 =12.
выполнению дешифрования по алгоритму Ба8е64 — Л = ЛН$ 0 ^ Л НЗЛНЗ!
По теореме 2 для последовательной композиции временных волновых систем получим:
і і
X (1*(т+т) + 12) & gt-ТШ81 & gt-Х (1 + т+т),
і і
Отметим, что время, затрачиваемое на выполнение вычислений данной временной волновой системой, равно 20 с, но теорему 2 возможно применять и в случаях, когда время передачи данных между вычислительными узлами различно.
При функционировании временной волновой системы были задействованы 6 вычислительных узлов рассматриваемой нами вычислительной системы — четыре выполняют сдвиг, один — гаммиро-вание по ключу, последний — дешифрование по алгоритму Ба8е64.
Далее рассмотрим параллельную композицию четырех временных волновых систем ЛЖЯ1 см (рис. 6), они осуществляют схожие действия, но с различными ключами из множества X:
Заключение
В данной работе рассмотрен метод получения априорной верхней и нижней оценок времени проведения распределенного перебора в гетерогенных системах, построенных как последовательная и параллельная композиция более простых неоднородных или однородных вычислительных систем, на основе временных волновых систем. Моделирование задач распределенного перебора с использованием временных волновых систем дает возможность оценить время, которое будет потрачено на поиск решения, а введенные операции позволяют на основе волновых систем, описывающих некоторые простые стадии поиска решения, исполняемые в некоторой неоднородной среде, получать укрупненную модель и на основе времени функционирования каждой стадии получать время, кото -рое будет затрачено на весь процесс поиска.
Литература
1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. -
2. Топорков В. В. Модели распределенных вычислений. — М.: Физматлит, 2004. — 320 с.
3. Трещёв И. А. Математическое моделирование волновых систем // XXXII Дальневосточная математическая школа-семинар им. академика Е. В. Золотова. — Владивосток: Дальнаука, 2007. -
Aws2 = л11 + л1 + лт1.
AWS2
По теореме 1 для параллельной композиции временных волновых систем получим:
Отметим, что время, затрачиваемое на выполнение вычислений данной временной волновой системой, равно 20 в силу того, что все временные волновые системы, вошедшие в параллельную
композицию, функционируют независимо и каждая вершина соответствует отдельному вычислительному узлу. Верхняя и нижняя границы времени, необходимого для перебора всех ключей в рассматриваемой вычислительной системе определяются
соотношением
Рис. 6. Временная волновая система для сдвига вправо на 1 бит
328 с.
С. 101−102.
4. Трещев И. А. Математическая модель гибридной временной волновой системы // Системы управления и информационные технологии. — 2007. — № 4(30). — С. 19−21.
Трещев Иван Андреевич
Канд. техн. наук, доцент, зав. каф. «Информационная безопасность автоматизированных систем» Комсомольского-на-Амуре государственного технического университета Тел.: 8 (4217) 54-68-54 Эл. почта: kalkt@yandex. ru
Treshchov I.A.
Evaluation of time-cost for implementation of distributed brute force attack in heterogeneous systems using time wave systems
In this work the method of reception of aprioristic top and bottom estimations of time expenses for realization of distributed brute force attack in heterogeneous systems using time wave systems are considered. Time estimations for various variants of construction of heterogeneous systems are shown.
Keywords: distributed brute force attack, time-consuming estimate.

ПоказатьСвернуть
Заполнить форму текущей работой