Multiagent systems detect abnormal network activity

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  показывает,  что  наибольшие  затраты  памяти  в  случае  выполнения  алгоритма 
скользящего  окна,  поскольку  длина  наибольшего  окна  может  равняться  половине  длины  ключа.  В 
случае применения β-арного алгоритма модулярного экспоненциирования затраты памяти зависят от 
выбранной системы счисления, т.е. от значения. 

жүктеу/скачать 7,62 Mb.

Достарыңызбен бөлісу: