PDF de programación - Clasificación de patrones de tráfico de redes utilizando herramientas de aprendizaje automático en entornos de computación distribuida

UNIVERSIDAD DE MENDOZA

FACULTAD DE INGENIERÍA

MAESTRÍA EN TELEINFORMÁTICA

"Cai
a
iódeaede
de
ede iizadhea
ieade
aedizajea 
i
eede

 a
iódiib ida"

Autor: Carlos A. Catania

Director: Dr. Carlos García Garino

Codirector: Dra. Cristina Párraga

2007

Tesis: "Clasificación de patrones de tráfico de redes utilizando herramientas de computación evolutiva en

entornos de computación distribuida"

II

Alumno: Carlos A. Catania

A mi padres, Carlos y Delia, ya que sin su ayuda, paciencia y esfuerzo no

hubiera sido capaz de llevar a cabo esta tarea. También a Lili, mi chica y

futura esposa, por ser "la alegría del hogar".

Agradecimientos

Este trabajo desarrollado durante los últimos 18 meses no hubiera sido po-
sible sin la colaboración de quienes me ayudaron a concretarlo. Por este
motivo debo agradecer profundamente a todos los que me brindaron su
apoyo.

A mi director de tesis, Carlos Garcia Garino, por su confianza y por todo el
tiempo que le dispuso a mi tarea, por sus aportes, sugerencias y correccio-
nes.

A Cristina Párraga, mi codirectoria de tesis, por sus sugerencias y correc-
ciones.

A mis compañeros del LAPIC, Claudio Careglio, Julio Monetti, Osvaldo Ma-
rianeti, Sergio Salinas, Emiliano Lopez y Paula Martinez. Por las horas com-
partidas.

A la Agencia Nacional de Promoción Científica y Tecnológica (ANPCyT),
por el apoyo económico recibido mediante el Proyecto PICTR 184, el cual
me permitió dedicarme completamente a esta tarea.

Tesis: "Clasificación de patrones de tráfico de redes utilizando herramientas de computación evolutiva en

entornos de computación distribuida"

IV

Alumno: Carlos A. Catania

Resumen

Desde hace algunos años, los sistemas de detección de intrusos (IDS) se
emplean como una herramienta de apoyo a las actividades del ingeniero en
seguridad de redes de datos. Estos sistemas ayudan a reconocer diferentes
tipos de ataques o anomalías en la red, a partir del reconocimiento de patro-
nes del tráfico de red, que resulta uno de los componentes fundamentales
de los mismos.

Con este fin, se estudian las posibilidades de aplicación de un algoritmo
genético para obtener un conjunto de reglas que permitan reconocer las
instancias de tráfico normales. Luego toda nueva instancia de tráfico que
no pueda ser reconocida por el conjunto de reglas se considera como una
posible anomalía.

El enfoque propuesto es distinto respecto a otros trabajos del estado del
arte que clasifican patrones de tráfico de las instancias que presentan ano-
malías. En este sentido presenta la ventaja de permitir la detección de ata-
ques no conocidos, a la vez que aporta información sobre el tráfico de red
que puede resultar valiosa para el ingeniero en seguridad de redes.

En esta tesis se presenta una arquitectura para un sistema de detección de
intrusos y se discuten los módulos que componen la misma. Para el mó-
dulo de aprendizaje se propone un algoritmo genético de tipo estacionario,
para lo cual se discute la representación de la población, la función de fit-
ness, las técnicas de nicho para garantizar la convergencia hacia múltiples
soluciones y los operadores genéticos utilizados.

Debido a que el proceso de entrenamiento del algoritmo genético propues-
to requiere una gran cantidad de recursos computacionales, tanto para su

Tesis: "Clasificación de patrones de tráfico de redes utilizando herramientas de computación evolutiva en

entornos de computación distribuida"

V

Alumno: Carlos A. Catania

procesamiento como para su validación, se estudian distintas alternativas
para su ejecución en ambientes distribuidos fuerte y debílmente acoplados.

Tesis: "Clasificación de patrones de tráfico de redes utilizando herramientas de computación evolutiva en

entornos de computación distribuida"

VI

Alumno: Carlos A. Catania

Índice general

Agradecimientos

Índice de figuras

Índice de cuadros

Lista de algoritmos

1.

Introducción
1.1. Descripción del problema . . . . . . . . . . . . . .
1.2. Propuesta . . . . . . . . . . . . . . . . . . . . . . .
1.3. Objetivos.
. . . . . . . . . . . . . . . . . . . . . . .
1.4. Estructura del trabajo . . . . . . . . . . . . . . . .

IV

X

XIII

XV

1
1
3
4
5

2. Estado del arte

2.1. Reglas de clasificación . . . . . . . . . . . . . . . .

6
6
2.1.1. Selección de atributos . . . . . . . . . . . . 10
2.1.2. Esquemas de Representación . . . . . . . 15
2.1.3. Función de optimización . . . . . . . . . . . 18
2.1.4. Otros operadores.
. . . . . . . . . . . . . . 22
2.1.5. Técnicas de nicho. . . . . . . . . . . . . . . 23

2.2. Otras aplicaciones de algoritmos genéticos en el

contexto de IDS.
. . . . . . . . . . . . . . . . . . . 24
2.2.1. Clasificadores difusos . . . . . . . . . . . . 24
2.2.2. Selección de atributos. . . . . . . . . . . . . 26
2.2.3. Evolución de modelos matemáticos . . . . 29
2.3. Conclusiones . . . . . . . . . . . . . . . . . . . . . 30

3. Detección de Anomalías Basada en Algoritmos Gené-

Tesis: "Clasificación de patrones de tráfico de redes utilizando herramientas de computación evolutiva en

entornos de computación distribuida"

VII

Alumno: Carlos A. Catania

ticos
32
3.1. Sistema de Detección de Anomalías. . . . . . . . . 33
3.2. Módulo de Captura de Tráfico . . . . . . . . . . . . 35
3.3. Módulo de Preprocesamiento . . . . . . . . . . . . 36
3.4. Módulo de Aprendizaje . . . . . . . . . . . . . . . 39
3.4.1. Esquema General del Algoritmo . . . . . . 40
3.4.2. Representación de la Población.
. . . . . . 41
3.4.3. Función de Optimización.
. . . . . . . . . . 43
3.4.4. Operador Selección . . . . . . . . . . . . . 45
3.4.5. Operador de Cruzamiento . . . . . . . . . . 46
3.4.6. Crowding Determinístico . . . . . . . . . . 46
3.4.7. Operador de Descarte de Condición . . . . 48
3.4.8. Operador de Mutación . . . . . . . . . . . . 49
3.4.9. Obtención de los mejores individuos . . . . 49
3.5. Módulo de Evaluación . . . . . . . . . . . . . . . . 50
3.6. Conclusiones . . . . . . . . . . . . . . . . . . . . . 51

4.

54
Implementación Computacional
4.1.
Implementación Secuencial. . . . . . . . . . . . . . 54
4.2. Análisis de Concurrencia . . . . . . . . . . . . . . 57
4.2.1. Algoritmo genético clásico . . . . . . . . . . 58
4.2.2. Algoritmo genético propuesto . . . . . . . . 65
4.3. Procesamiento en ambientes distribuidos . . . . . 72

4.3.1. Procesamiento en ambientes fuertemente

acoplados . . . . . . . . . . . . . . . . . . . 74

4.3.2. Procesamiento en ambientes débilmente aco-

plados . . . . . . . . . . . . . . . . . . . . . 76
4.4. Conclusiones . . . . . . . . . . . . . . . . . . . . . 79

5. Experimentos

81
5.1. Conjuntos de entrenamiento y prueba . . . . . . . 81
5.2. Comportamiento del Algoritmo Genético Secuen-

. . . . . . . . . . . . . . . . . . . . . . . . . . 82

cial
5.2.1. Estudio de la influencia de la función de
distancia para Crowding y Crowding deter-
minístico . . . . . . . . . . . . . . . . . . . 83

Tesis: "Clasificación de patrones de tráfico de redes utilizando herramientas de computación evolutiva en

entornos de computación distribuida"

VIII

Alumno: Carlos A. Catania

5.2.2. Estudio de la influencia de la función de

peso en la función de optimización.

. . . . 86

5.2.3. Resultados obtenidos con 1800 generacio-

5.3. Procesamiento distribuido

nes . . . . . . . . . . . . . . . . . . . . . . 89
5.2.4. Detección de anomalías . . . . . . . . . . . 90
. . . . . . . . . . . . . 91
5.3.1. Tiempo secuencial . . . . . . . . . . . . . . 92
5.3.2. Resultados de los Tiempos en ambientes

fuertemente acoplados . . . . . . . . . . . 94

5.3.3. Resultados de los Tiempos en ambientes

débilmente acoplados . . . . . . . . . . . . 97
5.4. Conclusiones . . . . . . . . . . . . . . . . . . . . . 99

6. Conclusiones y trabajos futuros

101
6.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . 101
. . . . . . . . . . . . . . . . . . . 102
6.2. Trabajos futuros

Bibliografía

104

Tesis: "Clasificación de patrones de tráfico de redes utilizando herramientas de computación evolutiva en

entornos de computación distribuida"

IX

Alumno: Carlos A. Catania

Índice de figuras

do al esquema de representación propuesto por Li [2]

esquema de representación propuesto por Sinclair [1]

2.1. Estructura del cromosoma compuesto por 29 genes según el
. . . .
2.2. Estructura del cromosoma compuesto por 57 genes de acuer-
. . . .
2.3. Cromosoma que representa una regla de tráfico.
. . . . . . .
2.4. Regla obtenida a partir del cromosoma de la figura 2.3 . . . .
2.5. Orden de importancia en los atributos de una instancia de
. . . . . . . . . . . . . . . . . . . . . . . .

19
2.6. Cromosoma que representa una regla de tráfico generalizada. 23
25
2.7. Representación de cinco conjuntos difusos . . . . . . . . . .

tráfico según Li[2].

15

17
17
17

fico de red.

evaluación.

mación de los atributos.

3.1. Arquitectura del sistema de detección de anomalías en el trá-
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Arquitectura del sistema. Módulos que participan en la etapa
de aprendizaje. . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Arquitectura del sistema . Módulos que participan en la etapa
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Campos de los protocolos IP y TCP utilizados para la confor-
. . . . . . . . . . . . . . . . . . . . .
3.5. Secuencia de mensajes para el inicio y finalización de la co-
nexión TCP. Utilizadas para calcular el tiempo de duración de
. . . . . . . . . . . . . . . . . . . . .
una instancia de tráfico.
. . . . . . . . . . . . . . . . . .
3.6. Cromosoma de un individuo
3.7. Cromosoma de un individuo generalizado . . . . . . . . . . .
3.8. Orden de importancia en los atributos de una instancia de
tráfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .

3.9. Cruzamiento en 2 puntos (DPX)

33

34

35

37

38
42
42

45
46

Tesis: "Clasificación de patrones de tráfico de redes utilizando herramientas de computación evolutiva en