Х а б а р ш ы с ы в е с т н и к государственного


Multiagent systems detect abnormal network activity



Pdf көрінісі
бет8/53
Дата03.03.2017
өлшемі7,62 Mb.
#7253
1   ...   4   5   6   7   8   9   10   11   ...   53

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
,  Д.О. Кожахметова

1
Казахский национальный технический университет им. К.И. Сатпаева, Казахстан, г. Алматы 
2
Техническо-гуманитарная академия г.Бельско-Бяла, Польша 
3
Государственный университет имени Шакарима города Семей, г. Семей 
 
ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ В ИССЛЕДОВАНИИ МЕТОДОВ  
МОДУЛЯРНЫХ ЭКСПОНЕНЦИИРОВАНИЙ 
 
Aннотация:  Рассмотрены  основные  понятия  оценки  сложности  алгоритма  по  объему 
используемой  им  основных  ресурсов  компьютера:  временная  сложность  и  объемная  сложность 
алгоритма.  Проведен  сравнительное  исследование  операций  бинарного  метода,  β-арного 
методаиметодскользящегоокнамодулярногоэкспоненциированиясосчитываниембитэкспоненты«сле
ва направо» и «справа налево». 
 
Ключевые 
слова: 
временная 
сложность, 
объемная 
сложность, 
модулярное 
экспоненциирование, бинарный метод, β-арный метод, метод скользящего окна
 
Введение 
Традиционно  принято  оценивать  степень сложности  алгоритма  по  объему используемых  им 
основных  ресурсов  компьютера:  процессорного  времени  и  оперативной  памяти.  В  связи  с  этим 
вводятся такие понятия, как временная сложность и объемная сложность алгоритма [1].  
Затраты времени на выполнение основных операций алгоритмов экспоненциирования 
Параметр временной сложности становится особенно важным для задач, предусматривающих 
интерактивный режим работы программы или для задач управления в режиме реального времени [2].  
На выполнение операций алгоритмов модулярного экспоненциирования (бинарный, β-арный, 
скользящего  окна)  необходимо  затратить  определенное  время.  Выполнения  одной  операции 
алгоритма  зависит  от  быстродействия  процессора,  поэтому  можно  сказать,  что  в  общем,  каждый 
отдельный  шаг  алгоритма  выполняется  за  определенное  время.  Основные  операции  алгоритмов 
модулярного  экспоненциирования  и  затраты  времени  на  выполнение  каждой  из  них  можно 
представить в виде табл. 1:  
 
Табл. 1. Затраты времени на выполнение основных операций алгоритмов экспоненциирования  
 
Операция 
Время, в тактах  Содержание операции 
b
a

 

  Простое присвоение 
m
mod
x
z

 

  Присвоение по модулю 
FIND(max{
j
i
n

}|
w
j
i



1
,
1

j
n

 Q 
Нахождение самой длинной последовательности 
битов такой, что и 
w
j
i



1
и
1

j
n
 


2
0
1
n
n
n
k



 

Изображение числа в двоичной системе 
счисления 
m
mod
x
x
y


 

Возведение в квадрат по модулю 
m
mod
y
x
z


 

Умножение по модулю 
m
mod
y
z


 

Возведение в степень по модулю 
 
В  общем,  можно  принять,  что  соотношение  между  величинами  значений  этих  времен 
является таким:  
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
H
n
log

 нулевых  битов. 
Для перевода числа в β-арную систему счисления бинарное изображение 
n
разбивают на окна длиной 
. Отсюда следует, что верхняя оценка 
 
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]).  В  данном  случае 
)
(
n
T
и 
)
(
n
T

)
2
,
(
n
T
 и 
)
4
,
(
n
T
-  время  выполнения  бета-арного  алгоритма  модулярного  экспоненциирования  «слева 
направо» при 
2

w
 и 
4

w
, соответственно. 
)
2
,
(
n
T
и 
)
4
,
(
n
T
- время выполнения бета-арного 
алгоритма  модулярного  экспоненциирования  «справа  налево»  при 
2

w
и 
4

w
,  соответственно. 
)
3
,
(
n
T
и 
)
3
,
(
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 


2048 


1024 


512 


256 


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

60 
 
росту  объема  оперативных  запоминающих  устройства  (ОЗУ)  и  использования  многоуровневой 
системы  запоминающих  устройств.  Программе,  реализующей  алгоритм,  оказывается  доступной 
очень  большая,  практически  неограниченная  область  памяти  (виртуальная  память).  Недостаток 
основной памяти приводит лишь к некоторому замедлению работы через обмен данными с диском. 
Используются  приемы,  позволяющие  минимизировать  потери  времени  при  таком  обмене.  Это 
использование кэш-памяти и аппаратного просмотра команд программы на необходимое число ходов 
вперед, что позволяет заблаговременно переносить с диска в основную память нужные значения [5].  
При  выполнении  рассмотренных  алгоритмов  модулярного  экспоненциирования  в  памяти 
компьютера занято максимальное количество регистров, показанной в табл. 3.  
Табл. 3 Максимальное количество ячеек памяти, занятых при выполнении алгоритмов модулярного 
экспоненцирования 
 
Алгоритм модулярного 
экспоненциирования 
Количество ячеек памяти 
Бинарный 

β-арный  
w
2
 
Скользящего окна  
i
w
2
 
 
Анализ  табл.3  показывает,  что  наибольшие  затраты  памяти  в  случае  выполнения  алгоритма 
скользящего  окна,  поскольку  длина  наибольшего  окна  может  равняться  половине  длины  ключа.  В 
случае применения β-арного алгоритма модулярного экспоненциирования затраты памяти зависят от 
выбранной системы счисления, т.е. от значения. 

Достарыңызбен бөлісу:
1   ...   4   5   6   7   8   9   10   11   ...   53




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет