Multiagent systems detect abnormal network activity
Taking into account the current and future trends in the development of information technology
systems, as well as objective disadvantages described above two approaches to the detection of network
attacks can be concluded on the need to offset the efforts to develop and implement an integrated concept of
building security systems based on distributed computing systems, using mechanisms protection based on
the active audit. The components of such systems should be specialized by type of tasks, interact with each
other to exchange information and consistent decision-making, to adapt to the reconfiguration of the
hardware and software network traffic changes, new types of attacks. Among the possible technologies to
implement this approach as the most promising technology is considered intelligent multi-agent systems.
The main provisions of the proposed approach are as follows. Components of system information
protection (protection agents) are intelligent stand-alone programs that implement certain security features in
order to ensure the required security class. They allow you to implement a comprehensive security mechanisms
built on top of network software, operating systems and applications, increasing the security of the system to the
required level. It is assumed that the agents distributed over the hosts of the protected network, specialized on the
types of tasks and interact with each other to exchange information and consistent decision-making. It is important
to emphasize that there is no explicit "control center" of the family of agents - depending on the current situation
may lead to become any of the agents specializing in management tasks. If necessary, agents can be cloned and
stop functioning. Depending on the situation (type and number of attacks on a computer network, the availability
of computing resources to perform security functions) may be generated by multiple instances of each class of
agents. They adapt to the reconfiguration of the network traffic changes and new types of attacks, using the
experience [6].
The proposed approach is based on the technology of intelligent multi-agent systems will be used in
Intrusion Detection System following new approaches, significantly increases the efficiency of the system of
protection of distributed network attacks:
- Mobility, the system is built on mobile agents, that allows you to make the system flexible, easily
reconfigurable, vitality;
- The activity, the system not only captures the facts of remote network attacks, but also conducts
active measures against a remote attacker;
54
- Self-organization, the use of simplified structure and principles of human immune system, allows
us to solve the problem of recovering the system as a result of failures of self-control to detect their own
mistakes;
- Specialization in the types of tasks;
- Adaptation to the reconfiguration of the hardware and software network traffic changes, new types
of attacks;
- Implementation support making the most rational solution to block the distribution in time and
space of a network attack.
Implementation of the process of forecasting and detection of distributed network attacks is the main
content of specific functions of the multi-agent Intrusion Detection System [7].
Conclusion
Detection of network attacks on systems resources, information technology is quite a complicated
process that is associated with the collection of large amounts of information on the operation of information
technology systems, the analysis of these data and, finally, revealing the fact of attack. To effectively predict
and detect attacks requires integrated application of various methods and techniques of signature detection of
abnormal network activity.
As a solution to improve protection of information in networks is seen in the use of adaptive methods
for real-time detection of exercise-dependent processes by characterizing network attacks, it is advisable to
consider an approach that combines the method of multi-agent systems with methods adequate to detect
signs of attacks based on statistical methods of probability theory, fuzzy probabilistic and statistical methods,
the methods of the theory of intelligent systems, as well as methods of artificial neural networks. These
methods with their harmonized implementation in network attacks should allow a wide range of conditions
of corporate networks and information technology systems adequate to the real-time detection of non-
stationary random dynamical processes of abnormal activity and malicious behavior on the network and
information technology systems for small probability of false alarm and skip network attacks.
References
1.
The DDoS That Almost Broke the Internet – 2013.
2.
CloudFlare blog, Deep Inside a DNS Amplification DDoS Attack. – 30.10.2013.
3.
Global Upgrade Makes Internet More Secure. – 2010.
4.
Peng Liu Denial of Service Attacks. – University Park. – 2004.
5.
A. McLEAN, G. Gates, A. Tse How the Cyberattack on Spamhaus Unfolded. – 2013.
6.
S.Agarwal, T. Dawson, C. Tryfonas DDoS Mitigation via Regional Cleaning Centers. – 2011.
7.
URL: http://www.klerk.ru/soft/articles/73546/
БӨЛІСТІК ЖЕЛІЛІК ШАБУЫЛДАРДЫ АНЫҚТАУ ЖӘНЕ ШЕКТЕУ
Н.П. Карпинский, Г.А. Шангытбаева, Е.А.Оспанов, Е.М.Мухаметов
Мақалада бөлістік желілік шабуылдарды анықтау және шектеу мәселелері
қарастырылып, бөлістік желілерде кездесетін жаман ниетті шабуылдар мен жалпы нормадан
ауытқыған шабуылдар туралы айтылады.
ВЫЯВЛЕНИЯ И ЛОКАЛИЗАЦИЯ РАСПРЕДЕЛЕННЫХ СЕТЕВЫХ АТАК
Н.П. Карпинский, Г.А. Шангытбаева, Е.А.Оспанов, Е.М.Мухаметов
В статье рассматриваются выявления и локализация распределенных сетевых атак, а
также атаки злоумышленного поведения и атаки аномальной активности в распределенных
сетях.
55
УДК 004.74.76.2
А.К. Шайханова
1
, Б.С. Ахметов
1
, Н.П. Карпинский
2
, Д.О. Кожахметова
3
1
Казахский национальный технический университет им. К.И. Сатпаева, Казахстан, г. Алматы
2
Техническо-гуманитарная академия г.Бельско-Бяла, Польша
3
Государственный университет имени Шакарима города Семей, г. Семей
ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ В ИССЛЕДОВАНИИ МЕТОДОВ
МОДУЛЯРНЫХ ЭКСПОНЕНЦИИРОВАНИЙ
Aннотация: Рассмотрены основные понятия оценки сложности алгоритма по объему
используемой им основных ресурсов компьютера: временная сложность и объемная сложность
алгоритма. Проведен сравнительное исследование операций бинарного метода, β-арного
методаиметодскользящегоокнамодулярногоэкспоненциированиясосчитываниембитэкспоненты«сле
ва направо» и «справа налево».
Ключевые
слова:
временная
сложность,
объемная
сложность,
модулярное
экспоненциирование, бинарный метод, β-арный метод, метод скользящего окна.
Введение
Традиционно принято оценивать степень сложности алгоритма по объему используемых им
основных ресурсов компьютера: процессорного времени и оперативной памяти. В связи с этим
вводятся такие понятия, как временная сложность и объемная сложность алгоритма [1].
Затраты времени на выполнение основных операций алгоритмов экспоненциирования
Параметр временной сложности становится особенно важным для задач, предусматривающих
интерактивный режим работы программы или для задач управления в режиме реального времени [2].
На выполнение операций алгоритмов модулярного экспоненциирования (бинарный, β-арный,
скользящего окна) необходимо затратить определенное время. Выполнения одной операции
алгоритма зависит от быстродействия процессора, поэтому можно сказать, что в общем, каждый
отдельный шаг алгоритма выполняется за определенное время. Основные операции алгоритмов
модулярного экспоненциирования и затраты времени на выполнение каждой из них можно
представить в виде табл. 1:
Табл. 1. Затраты времени на выполнение основных операций алгоритмов экспоненциирования
Операция
Время, в тактах Содержание операции
b
a
C
Простое присвоение
m
mod
x
z
B
Присвоение по модулю
FIND(max{
j
i
n
n
}|
w
j
i
1
,
1
j
n
)
Q
Нахождение самой длинной последовательности
битов такой, что и
w
j
i
1
и
1
j
n
2
0
1
n
n
n
k
T
Изображение числа в двоичной системе
счисления
m
mod
x
x
y
R
Возведение в квадрат по модулю
m
mod
y
x
z
S
Умножение по модулю
m
mod
y
z
D
Возведение в степень по модулю
В общем, можно принять, что соотношение между величинами значений этих времен
является таким:
d
s
r
t
q
b
c
(1)
Исходя из данных таблицы 1, можно построить математическую модель исчисления времени,
затраченного на выполнение каждого из алгоритмов реализации методов, описанных в п.1.4.
На выполнение бинарного метода затрачивается время:
56
- при считывании "слева направо":
s
n
H
r
n
log
c
t
s
r
c
t
n
T
k
i
n
|
i
i
i
i
0
1
1
1
(2);
- при считывании "справа налево":
r
n
log
s
n
H
b
c
t
r
s
b
c
t
n
T
k
i
i
n
|
i
i
i
1
0
1
2
(3).
На исполнение β-арного метода затрачивается время:
- при считывании "слева направо":
d
w
n
log
s
w
n
log
c
t
s
d
c
s
c
t
w
,
n
T
w
k
i
i
i
i
i
1
2
2
3
0
1
1
1
(4).
- при считывании "справа налево":
s
n
W
w
n
log
d
w
n
log
b
c
t
s
c
d
s
d
c
b
t
w
,
n
T
w
w
w
w
k
n
|
i
n
|
i
n
|
i
w
w
i
i
i
2
2
1
2
2
2
4
1
0
1
1
1
0
1
1
0
1
1
(5),
где
n
W
0
– количество нулевых битов в изображении числа n по основанию β.
Очевидно, что в бинарном изображении числа являются n є
n
H
n
log
нулевых битов.
Для перевода числа в β-арную систему счисления бинарное изображение
n
разбивают на окна длиной
w . Отсюда следует, что верхняя оценка
n
W
0
:
w
n
H
n
log
n
W
max
0
(6)
С другой стороны, нижняя оценка легко может быть определена как:
n
log
w
w
n
H
n
log
n
W
min
1
0
(7)
На выполнение метода скользящего окна затрачивается время:
- при считывании "слева направо":
57
pq
s
p
r
n
log
c
n
H
n
log
p
b
t
c
n
H
k
c
s
q
p
s
kr
c
b
t
w
w
r
c
s
q
p
c
r
n
H
k
c
t
s
s
b
r
c
s
q
c
r
c
t
s
s
b
w
,
n
T
i
i
i
i
i
i
w
w
w
i
o
w
k
i
n
|
i
n
|
i
j
j
i
2
2
2
2
2
1
2
2
5
1
0
0
0
1
2
1
(8).
- при считывании "справа налево":
c
s
d
c
s
q
p
c
r
n
H
k
c
b
t
c
s
d
c
s
q
c
r
c
c
b
t
w
n
T
i
i
i
w
i
i
i
w
w
w
v
v
k
i
n
i
n
i
j
j
i
1
2
2
2
3
,
5
,
,
1
2
0
1
0
|
0
|
1
2
,
,
3
,
1
2
1
2
2
,
6
pd
pq
s
p
r
n
H
n
c
p
n
H
n
b
t
i
i
w
w
1
2
2
2
2
log
log
2
2
, (9)
где p - количество окон,
i
w
w
0
- сумма всех нечетных окон, равная весу Хемминга, поскольку эти окна
состоят только из единичных битов.
Очевидно, что,
2
n
log
p
max
, а
i
min
w
)
n
(
H
p
(10).
Итак, в общем, для исследования времени выполнения этого алгоритма можно рассматривать
среднее значение:
2
2
n
log
w
)
n
(
H
p
i
(11).
Определение самого производительного алгоритма модулярного экспоненциирования
Очевидно, что для повышения производительности асимметричных криптоустройств
возникает необходимость определения самого производительного алгоритма из всех известных
алгоритмов модулярного экспоненциирования, которые в них используются.
58
Путь решения этой задачи рассмотрим на примере описанных выше бинарного, β-арного
методов и метода скользящего окна.
Как отмечалось выше, общее время выполнения алгоритма бинарного метода зависит только
от длины двоичного изображения числа n. Время выполнения алгоритма β-арного метода зависит не
только от длины бинарного изображения числа n, но и от значения β (т.е. от числа w). Время, которое
занимает выполнение алгоритма метода скользящего окна, зависит от длины двоичного изображения
числа n и ширины нечетного окна [11]. Учитывая это, можно исследовать зависимость времени
выполнения алгоритма от длины двоичного изображения числа n.
На рис. 1 изображено эту зависимость при усредненных значениях веса Хемминга (
)
n
(
H
) и
количества нулей в β-арном изображении числа n (
n
W
0
), а также при различных значениях w,
ширины нечетного окна и значениях
1
c
,
5
1.
b
,
6
1.
q
,
6
1.
t
,
15
r
,
16
s
,
19
d
(соотношение между переменными соответствуют количеству тактов, которые затрачивает процессор
на выполнение соответствующих операций [11]). В данном случае
)
(
1 n
T
и
)
(
2 n
T
-
)
2
,
(
3 n
T
и
)
4
,
(
3 n
T
- время выполнения бета-арного алгоритма модулярного экспоненциирования «слева
направо» при
2
w
и
4
w
, соответственно.
)
2
,
(
4 n
T
и
)
4
,
(
4 n
T
- время выполнения бета-арного
алгоритма модулярного экспоненциирования «справа налево» при
2
w
и
4
w
, соответственно.
)
3
,
(
5 n
T
и
)
3
,
(
6 n
T
- время выполнения метода скользящего окна «слева направо» и «справа
налево» при длине окна
3
i
w
.
Анализ рис. 1 показывает, что время выполнения алгоритмов модулярного
экспоненциирования имеет линейный характер. Кроме того, самыми являются алгоритмы β-арного
метода "слева направо" и "справа налево", а больше всего времени занимает выполнение алгоритма
бинарного метода.
На рис. 2 и рис. 3 изображено, соответственно, зависимость быстродействия алгоритмов β-
арного метода "слева направо" и "справа налево" от значения степени основы w в зависимости от
различной длины ключа и при усредненном значении веса Хемминга.
Рис. 1. Оценка производительных характеристик исследуемых алгоритмов
59
Рис. 2. Зависимость быстродействия алгоритма β-арного метода "слева направо" от значения
степени основы w
Рис. 3. Зависимость быстродействия алгоритма β-арного метода "справа налево" от значения
степени основы w
По данным рисунков 2 и 3 можно определить оптимальную основу, при которой
осуществляется наименьшая задержка работы алгоритма, то есть минимальные
3
T
и
4
T
,
соответственно, а следовательно, обеспечивается его максимальная производительность при
заданных значениях экспоненты
n
. Для алгоритмов β-арного метода лучшими будут значения
w
,
представленные в табл. 2.
Табл. 2. Оптимальные значения степени основы β-арного метода при разной длине ключа
n
.
Длина ключа
n
w
β-арный метод
" слева направо”
β-арный метод
“справа налево”
4096
8
7
2048
7
6
1024
6
5
512
6
5
256
5
4
Объемная сложность алгоритма, т.е. затраты памяти компьютера на его выполнение,
становится критической, когда объем обрабатываемых данных оказывается на грани объема
оперативной памяти. На современных компьютерах острота этой проблемы снижается благодаря
60
росту объема оперативных запоминающих устройства (ОЗУ) и использования многоуровневой
системы запоминающих устройств. Программе, реализующей алгоритм, оказывается доступной
очень большая, практически неограниченная область памяти (виртуальная память). Недостаток
основной памяти приводит лишь к некоторому замедлению работы через обмен данными с диском.
Используются приемы, позволяющие минимизировать потери времени при таком обмене. Это
использование кэш-памяти и аппаратного просмотра команд программы на необходимое число ходов
вперед, что позволяет заблаговременно переносить с диска в основную память нужные значения [5].
При выполнении рассмотренных алгоритмов модулярного экспоненциирования в памяти
компьютера занято максимальное количество регистров, показанной в табл. 3.
Табл. 3 Максимальное количество ячеек памяти, занятых при выполнении алгоритмов модулярного
экспоненцирования
Алгоритм модулярного
экспоненциирования
Количество ячеек памяти
Бинарный
2
β-арный
w
2
Скользящего окна
i
w
2
Анализ табл.3 показывает, что наибольшие затраты памяти в случае выполнения алгоритма
скользящего окна, поскольку длина наибольшего окна может равняться половине длины ключа. В
случае применения β-арного алгоритма модулярного экспоненциирования затраты памяти зависят от
выбранной системы счисления, т.е. от значения.
Достарыңызбен бөлісу: |