Una metodología para la detección de anomalías en una red a partir de las trazas de ejecución de los servicios Idis González-Castaño, Marisel Bueno-Rojas, Alfredo Somoza-Moreno, Yudivián Almeida-Cruz Universidad de La Habana {idis, marisel, somoza, vudv}@uh.cu

Resumen. La detección y corrección de situaciones anómalas en los servicios que brinda una red de computadoras es tarea de suma importancia para su buena gestión. El presente trabajo brinda una metodología que ayuda a analizar las trazas de ejecución de los servicios de una red, permitiendo detectar anomalías a partir de la información obtenida del análisis. El modelo está basado en la utilización de técnicas de minería de datos sobre las trazas que permitan encontrar patrones y relaciones entre los datos de los registros, logrando identificar anomalías en el comportamiento regular de un servicio. Dentro de la minería de datos se identificaron estas situaciones como outliers. Dadas las características de los datos se seleccionaron las técnicas de detección de outliers que mejor se ajustaron a dichos datos. Con el fin de validar la metodología propuesta se seleccionó como caso de estudio el análisis de las trazas del servicio de proxy Squid para poder analizar los resultados obtenidos y permitir la generalización del modelo a los demás servicios de una red.

1 Introducción La detección de situaciones anómalas es un objetivo de suma importancia en la gestión de los servicios de una red de computadoras. Dichas situaciones pueden ser consecuencia de errores de configuración o de ejecución de los servicios, o aparecer como resultado de la ocurrencia de algún evento excepcional. La detección y corrección temprana de estas anomalías es imprescindible para medir la eficiencia en la gestión de una red de computadoras. En la actualidad, existe una multitud de aplicaciones de gestión de redes que incorporan procesos automáticos de detección de anomalías. El presente trabajo no tiene como objetivo proponer un nuevo sistema en esta dirección, sino incursionar en una nueva metodología que mejore el proceso de gestión y en particular el de gestión de fallos. Se trata de una técnica que permita descubrir de forma automática o semiautomática información de gestión útil a partir de las trazas de ejecución de los servicios con el objetivo de detectar anomalías. Con el fin de realizar el diseño e instrumentación de un prototipo de aplicación que permita analizar las trazas de un servicio de redes utilizando técnicas de minería de datos se proponen los siguientes objetivos:  Proponer una metodología para la extracción de conocimiento útil de gestión a partir de las trazas de un servicio de redes utilizando técnicas de minería de

302

I. Gonzalez et al.

datos.  Diseñar e implementar una aplicación que contribuya a ejemplificar dicha propuesta, así como realizar un análisis de los resultados que se puedan obtener.

2 Diseño de la metodología La detección de fallos es una de las áreas funcionales de la gestión de redes[1]. Su objetivo fundamental es la localización y solución de los problemas que se presentan en una red, ofreciendo un soporte preventivo y correctivo a su funcionamiento. En muchos casos, permite incluso detectar y subsanar los problemas antes de que se percaten los usuarios. Cuando una falla o funcionamiento raro se detecta en la red se dedica un tiempo a identificar la causa que le dio origen y, en caso de que sea necesario, se toman medidas para evitar su repetición. Las trazas de ejecución de un servicio son una fuente importante de la que se puede extraer gran cantidad de información acerca de su comportamiento. Por esta razón, es usual que los administradores de una red las examinen cuando se están buscando las causas de un error. Sin embargo, ocurre con frecuencia que el cúmulo de datos que se almacena en estos archivos es tan grande que termina por agotar al administrador sin haber encontrado nada útil. Con la propuesta que se hace en este trabajo se pretende brindar el prototipo de una herramienta de gestión que ayude a analizar las trazas de un servicio dentro de la red y permita detectar anomalías a partir de la información obtenida de este análisis. Para lograr este objetivo se definen determinadas variables a tener en cuenta a partir de los datos que aparecen en los archivos de trazas y por cada una se construye un perfil de comportamiento normal asociado a ella. Una vez terminada esta fase se procede al análisis de nuevas trazas con el objetivo de detectar comportamientos anómalos. En esta nueva etapa se comparan, por cada variable, los valores obtenidos de las nuevas trazas con los que se tenían en el perfil. Aquellos que se ajusten son sencillamente descartados o se almacenan para posibles procesamientos a realizarse en el futuro, mientras que aquellos que no se adecúen serán tratados como anomalías. Para construir el perfil que describe el comportamiento normal de un servicio se propone la utilización de técnicas de minería de datos que operen sobre las trazas. El objetivo es ser capaces de construir un modelo matemático simple que cubra el rango completo de comportamientos normales y que excluya, con la mayor precisión posible, las anomalías u outliers. Dado que el prototipo a desarrollar no es más que una aplicación de minería de datos, se tomó como guía de trabajo el modelo CRISPDM [2]. 2.1 Entendiendo el dominio del problema Se tomó como caso de estudio el análisis de las trazas de ejecución del servicio que se utiliza como intermediario para la navegación por Internet en la red de la Universidad

Detección de anomalías en una red

303

de La Habana (UH). Este es el servicio de proxy conocido con el nombre de Squid [3]. 2.1.1 Squid Entre sus características más importantes se encuentran:  Permite la navegación a través de sitios HTTP, HTTPS, FTP y GOPHER con la capacidad de acelerar los pedidos a través de un cache Web.  Es posible establecer relaciones jerárquicas entre varios servidores Squid. Estas pueden ser relaciones de padre/hijo o relaciones entre hermanos.  Brinda un conjunto amplio de directivas para instrumentar restricciones de acceso. Estas permiten establecer políticas de control centralizado, simplificando la administración de la red. Squid, como la mayoría de las aplicaciones que instrumentan servicios de redes, genera durante su ejecución información referente a las actividades que va realizando. 2.1.2 Trazas de ejecución Squid crea varios archivos de trazas [3]. Los tres ficheros de trazas más importantes de Squid son: cache.log, store.log y access.log. De los tres ficheros se seleccionó para el trabajo el tercero debido a que es el que permite conocer información acerca de cada solicitud realizada al servicio de proxy de Squid. 2.1.2.1 Archivo de trazas de acceso (access.log) Cada registro del fichero de trazas access.log contiene los campos: time duration client action/code bytes method url rfc931 peerstatus/peerhost type El fichero access.log acumula diariamente, de acuerdo a la demanda de Internet de la UH, un promedio de 80MB de información textual. Dentro de este gran cúmulo de datos existe conocimiento que no es posible extraer con una simple inspección y que puede ser muy importante para los administradores de la red. Sin embargo, la extracción de este conocimiento oculto, con la necesaria eliminación de datos superfluos, redundantes o que desvirtúen su significado, es posible lograrla utilizando técnicas más avanzadas. Es aquí donde entra a jugar un papel muy importante la minería de datos. Con el propósito de dar un paso de avance en la aplicación de técnicas de minería de datos a las trazas de los servicios y así poder enriquecer la información de gestión de la red de la UH, se formula el siguiente problema: Analizar las trazas de acceso del servicio de proxy Squid con el objetivo de:  Identificar variables con un comportamiento estable en el tiempo, es decir, que fluctúen dentro de determinados parámetros acotables para intervalos específicos de tiempo.

304

I. Gonzalez et al.

 Elaborar para cada una de estas variables un perfil de comportamiento sobre la base del análisis de las mismas dentro de un conjunto inicial de archivos de trazas. Una vez obtenidos los modelos del comportamiento se pueden examinar nuevos registros de Squid con el objetivo de buscar un valor para las mismas variables dentro de estos nuevos ficheros y compararlos con los perfiles definidos para cada una de ellas. 2.2 Entendiendo los datos Para la aplicación de esta fase al problema que se está resolviendo se identificó, en primera instancia, un conjunto inicial de variables o atributos a partir de toda la información que se brinda en las trazas de acceso de Squid. Para la selección de estas variables no se tuvo en cuenta ninguna característica especial, aunque sí se consideró el hecho de que se encontraban muy relacionadas con el comportamiento del ancho de banda de Internet que tiene la UH. Finalmente las escogidas fueron:  cantidad total de solicitudes realizadas (cs),  cantidad total de solicitudes que no se encontraron en cache (css),  cantidad total de bytes entregados a los clientes (cb),  cantidad total de bytes bajados directamente de Internet (cbs). Para construir la colección de datos inicial se analizaron las trazas de acceso en un intervalo de 150 días de ejecución del servicio Squid. Se agruparon los datos en intervalos de 5 minutos y se contabilizaron resúmenes por cada uno de estos intervalos para las 4 variables seleccionadas. Se puede observar que después de haber agrupado los datos en intervalos de 5 minutos se obtiene como resultado un número fijo de entradas diarias. A diferencia de los datos iniciales, ahora cada día consta de una cantidad fija de registros (288 en este caso). Tomando como base las imágenes del MRTG[4], donde se grafica el comportamiento del canal de Internet de la UH y la experiencia de los administradores, se pudo detectar un patrón similar para cada horario dentro de una semana. ¿Pasaría lo mismo si se analizara el comportamiento de cada una de las 4 variables seleccionadas en cada uno de los intervalos de una semana? Con el fin de responder a dicha pregunta se examinó la información que se tenía de todos los lunes comprendidos en los 150 días de análisis. Se graficó la variable cs para cada lunes por separado y luego se solaparon todas en un mismo gráfico. En la figura 1 se puede observar el patrón seguido por tres lunes diferentes. La figura 2 ilustra la imagen obtenida al solapar todo el conjunto de lunes. Se obtuvieron resultados similares al construir luego las mismas gráficas para otros tres días (martes, sábados y domingos) y para el resto de las variables.

Detección de anomalías en una red

305

Fig. 1. Gráfico de cantidad de solicitudes para tres lunes

Fig. 2. Cantidad de solicitudes durante 21 lunes

2.3 Preparación de los datos Si se presta atención a las imágenes 1 y 2, presentadas en el epígrafe anterior, se puede observar como las funciones que ahí se grafican siguen un comportamiento más o menos similar. Sin embargo, también es posible percatarse de la existencia de algunos puntos que se alejan de ese comportamiento común. Estos puntos afectan la construcción de un modelo que permita establecer un perfil de comportamiento normal para cada una de las variables definidas en cada uno de lo intervalos de una semana. Estos puntos, que pueden ser vistos como anomalías u outliers, no deben ser tenidos en cuenta para permitir la creación de un modelo correcto. En este sentido, se hace necesario poder identificar, para cada uno de los intervalos de 5 minutos de una semana, todos aquellos puntos que se salen fuera de un comportamiento natural. 2.3.1 Detección de outliers basados en distribución Cada una de las variables hasta aquí identificadas —dígase cs, css, cb y cbs—tiene una sola dimensión. Por esta razón tiene sentido pensar en la aplicación de alguna de las técnicas basadas en distribución. Sin embargo, para poder aplicarlas es necesario

306

I. Gonzalez et al.

conocer como distribuyen dichas variables. Para resolver este problema existen las técnicas llamadas pruebas de bondad de ajuste [6, 10]. 2.3.1.1 Pruebas de bondad de ajuste Para poder determinar la naturaleza de los datos, se realizaron histogramas para cada variable (cs, css, cb, cbs) por cada intervalo, los cuales se compararon con la función de densidad de la distribución normal que mejor ajusta los datos, o sea, con la N(μ, σ2), donde μ y σ2 pueden ser diferentes para cada intervalo. En la figura 3 se presenta un ejemplo de estos gráficos para el intervalo número 2 con valores de μ = 1699,43 y σ2 = 451032,26 para la variable cs. Por lo tanto, se puede decir que debido a la forma del histograma de frecuencias, los datos parecen seguir una distribución normal. Sin embargo, esta simple apariencia no es suficiente. Es por esta razón que se procede a aplicarle a los datos las pruebas χ2ó KS.

Fig. 3. Histograma de frecuencia del intervalo 2.

De estas dos pruebas solo fue posible aplicar la prueba KS. Esto se debió al reducido número de datos que se tenía para cada intervalo. Se contaba con tan solo 21 registros. Los resultados obtenidos al aplicársele la prueba KS a los cuatro días de la semana seleccionados, se muestran en la tabla 1. En la misma se pueden observar varios intervalos donde se rechaza la hipótesis H0. Esto quiere decir que los datos no parecen seguir una distribución normal, con un nivel de significación del 5%. Dicho resultado puede estar derivado de la existencia de pocos datos o deberse a que la distribución de estos sea diferente. En cualquier caso se llegó a la conclusión de rechazar la aplicación de técnicas de detección de outliers pertenecientes al enfoque basado en distribución, debido a que no en todos los intervalos los datos se pueden ajustar por la distribución normal. Por ejemplo, si se analizan las muestras de un sábado, el 8.3% de estas parecen no ajustarse correctamente.

Detección de anomalías en una red

307

Tabla 4. Resultados de aplicar la prueba de Kolmogorov-Smirnov

.Día de la semana

Lunes Martes Sábado Domingo

Total intervalos 288 288 288 288

de

Total de intervalos en que se rechaza la hipótesis H0 3 5 24 5

Como se rechazó la aplicación de técnicas basadas en distribución, se comenzó el estudio de un método de clustering para detectar outliers. Teniendo en cuenta la naturaleza de los datos se identificó que un algoritmo de clustering basado en densidad podría arrojar buenos resultados [8]. Por esta razón se tuvo en cuenta el estudio y la aplicación del método DBSCAN para la detección de outliers. 2.3.2 Detección de outliers utilizando DBSCAN Para la aplicación del algoritmo DBSCAN [7] se debían tener en cuenta dos cuestiones importantes. Estas son:  La selección de los valores de los parámetros ε y MinPts. Después de realizar algunas pruebas sobre los datos, utilizando varios valores para los parámetros, se determinó que los mejores resultados se obtenían cuando ε = 0,1 y MinPts = 4.  La selección de la función de distancia. La distancia euclidiana fue la métrica seleccionada para establecer una medida de disimilitud entre dos elementos del conjunto de datos. Puesto que las variables seleccionadas son unidimensionales la función de distancia se redujo a computar la diferencia modular. En la figura 4a) se ilustra el conjunto de datos sin limpiar perteneciente a un intervalo del conjunto de datos para la variable cs, por su parte la imagen 4b) fue realizada después de aplicar DBSCAN al mismo intervalo. En esta última figura los puntos que tienen color rojo son aquellos que el algoritmo clasificó como outliers.

308

I. Gonzalez et al.

Fig. 4. Aplicación del Dbscan. a) antes de aplicar el método y b) después de aplicarlo.

2.4 Creación del modelo En la realización de esta fase se trabaja con el conjunto de datos que se obtuvo como resultado de aplicar el algoritmo DBSCAN. Para construir el modelo que representa el comportamiento normal para las variables seleccionadas se definieron umbrales (mínimo y máximo) por cada intervalo para cada uno de los atributos. Ver la figura 5. Esta decisión estuvo basada en las características de los datos y del problema en sí mismo, pues justamente se querían definir ciertas cotas por cada intervalo que permitieran establecer la diferencia entre un comportamiento normal y una posible anomalía en el servicio.

Detección de anomalías en una red

309

Fig. 5. Modelo de la variable cs para el lunes.

2.5 Evaluación del modelo Una vez obtenido el modelo, se debe proceder a su validación comprobando que las conclusiones que arroja son válidas y cumplen con los requerimientos del problema de minería de datos planteado [1]. Después de creado el modelo en la fase anterior surgió la incógnita de si entre las variables seleccionadas —dígase cs, css, cb y cbs— existía solapamiento de información y por ende se podían establecer correlaciones entre ellas. Con este objetivo se realizó un estudio de dichas variables que es explicado a continuación. 2.5.1 Verificando solapamiento de información Para poder investigar acerca de la relación entre las variables se acumuló un total de 20 nuevos ficheros de trazas del servicio de Squid (un total de 5277 registros) y se realizaron gráficos para observar cómo era la interrelación entre cada par de variables. Los mismos se pueden examinar en la figura 6 que fue elaborada utilizando la herramienta R (R es una aplicación para la elaboración de gráficas y análisis estadístico).

310

I. Gonzalez et al.

Fig. 6. Interrelación de las cuatro variables.

Detección de anomalías en una red

311

Cada uno de los gráficos que se observan en la figura fue construido de forma tal que en el eje de las x se ha representado una variable y en el eje de las y la otra. Se puede decir que visualmente, entre cada pareja de variables, parece existir una correlación lineal, aunque esto no es suficiente para afirmarlo. Sin embargo, el cálculo del coeficiente de correlación lineal entre cada pareja de variables da la posibilidad de afirmar dicha relación con mayor seguridad. 2.5.1.1 Coeficiente de correlación lineal Se procede entonces a calcular este valor para las posibles combinaciones de las cuatro variables. Los resultados se pueden ver en la tabla 2. Después de observados los valores en la tabla se puede decir, bajo el criterio de la existencia o no de correlación lineal a partir de un valor de r, que todas las posibles combinaciones con las variables parecen tener una relación lineal positiva. Vale aclarar que usualmente se considera que existe correlación lineal cuando r > 0.75 [9]. Por tanto, bajo este criterio solamente se consideran correlacionadas las parejas y . Tabla 2. Cálculo del coeficiente de correlación. Variables



R

6.077598e-01 9.922090e-01 5.172269e-01 6.052734e-01 9.880280e-01 5.181871e-01

Sin embargo, en el problema que se está tratando de resolver se quiere producir una alerta a los administradores solo cuando se tiene una fuerte sospecha de la existencia de un error o comportamiento inusual en la red. En este sentido se ha considerado la alternativa de tomar como sospechosa una tupla solo cuando los cuatro valores queden fuera del perfil construido para dicho intervalo de tiempo. Si se toman los nuevos ficheros de trazas, utilizados para la prueba estadística anterior, como casos de prueba se puede observar que las cuatro variables a la vez se ajustan al perfil o discrepan de este un porciento alto de veces. Los resultados por parejas y entre las cuatro variables se ilustran en la tabla 3.

312

I. Gonzalez et al.

Tabla 3. Relación entre las variables del problema

Cantidad de tuplas donde existen ajustes o desajustes simultáneos para: cs y cb cs y css cs y cbs cb y cbs cb y css css y cbs cs, cb,css y cbs

Valor

% del total

3918 4615 3825 4860 3930 3863 3373

74.25 87.45 72.45 92.10 74.47 73.20 63.92

Aplicación de la metodología Para esta fase se desarrolló una aplicación con el objetivo de validar la metodología planteada en el capítulo anterior. La misma obtiene las trazas del servidor Squid y va formando tuplas con la información acumulada por intervalos de 5 minutos, de forma similar a como se realizó en la fase de comprensión de los datos. Luego estas tuplas deberán ser clasificadas en anomalías o comportamiento normal sobre la base de conocer si se ajustan o no al perfil modelado. En la aplicación se lograron identificar dos componentes fundamentales: un recolector de datos y un clasificador. Para garantizar una mayor flexibilidad en el momento del despliegue se consideró adecuado permitir una comunicación clienteservidor entre estas componentes. La figura 7 ilustra la arquitectura finalmente adoptada.

Fig. 7. Arquitectura de la aplicación.

Detección de anomalías en una red

313

2.6 Recolector de datos El módulo recolector de datos está diseñado para ejecutarse en el mismo servidor donde esté funcionando el servicio de Squid. Se encarga de recuperar tuplas a partir de las últimas líneas de las trazas del servicio, con el objetivo de enviarle esta información al clasificador, de forma que este último pueda identificar si son anomalías o comportamiento normal. ¿Qué almacena una tupla desde el punto de vista de nuestra aplicación? Una tupla es una lista de valores con la siguiente información: 2.7 Clasificador Una vez obtenida una tupla de valores listos para clasificar se pasa la información utilizando XML-RPC [5] al módulo clasificador. La tarea de este consiste en determinar si esta es o no una anomalía. Por ejemplo, para clasificar la tupla el módulo debe:  Obtener los umbrales de cada una de las variables de esta tupla en el intervalo correspondiente.  Verificar la pertenencia de los valores en la tupla a los perfiles correspondientes.Tres  Una vez clasificada, se procede a almacenar el resultado en una base de datos. El objetivo es permitir la retroalimentación del modelo posteriormente. Con el desarrollo de la herramienta de despliegue se llega a la última etapa en la construcción de la aplicación de minería de datos. Sin embargo, el proceso no culmina aquí. Su propia naturaleza cíclica demanda tareas de retroalimentación para mejorar el modelo a partir de los resultados de la fase de despliegue. Aunque la aplicación no ha sido implantada todavía, ya se vislumbran ciertas modificaciones al modelo, que le permitirían adaptarse a los cambios que ocurren en la red. Por ejemplo, el consumo de Internet en la red de la Universidad de La Habana no es el mismo en situaciones normales que en etapas de receso escolar. Por esta razón, es necesario que el modelo sea capaz de adaptarse a nuevas condiciones de forma que pueda aprender los cambios que ocurran en la red y no se vuelva obsoleto. Para lograr esto se han analizado algunas variantes:  Reiniciar el proceso de aprendizaje cada cierto tiempo, a partir de las trazas de los últimos n días para algún valor de n que se estime conveniente.  Retroalimentar el modelo con cada nueva entrada de forma que se actualicen los umbrales.Tres  Retroalimentar el modelo con cada nueva entrada bajo alguna condición. Por ejemplo: solo si esta fue clasificada como normal o solo si se clasificó como anomalía.

314

I. Gonzalez et al.

Cada una de estas variantes podrá tener sus ventajas o desventajas pero esto solo se conocerá cuando se pongan en práctica. Serán el tiempo y la experimentación que se haga quienes decidirán si alguna de ellas es aplicable o se necesita buscar una variante diferente.

3 Conclusiones y recomendaciones A modo de conclusión se puede decir que se propuso una metodología para la extracción de conocimiento útil de gestión a partir de las trazas de un servicio de redes utilizando técnicas de minería de datos. Se diseñó e implementó una aplicación que contribuye a ejemplificar la metodología propuesta y darle uso en el proceso de detección de fallas para un servicio en la red de la UH. A partir de los resultados obtenidos se tienen un conjunto de acciones a seguir:  Elegir los parámetros automáticamente con técnicas de reducción de dimensionalidad.  Desarrollar un algoritmo de clustering que se adapte mejor a las condiciones del problema.  Proponer una medida diferente a la euclidiana que se adapte mejor a las condiciones del problema.  Lograr una generalización de la metodología, aplicándola a los demás servicios de la red de la UH.  Integrar la aplicación con otras herramientas de detección de fallas.

Referencias 1. 2. 3. 4. 5. 6.

Network Management Basics. URL: http://www.cisco.com Crisp-DM 1.0. Step-by-step data mining guide. Url: http://www.crisp-dm.org Preguntas más frecuentes de Squid. URL: http://www.squid-cache.org/ What is MRTG? URL: http://oss.oetiker.ch/mrtg XML-RPC. URL: http://www.xmlrpc.com/ Vic Barnett and Toby Lewis. “Outliers in statistical data”. John Wiley & Sons. 1994. 7. Martin Ester and Hans-Peter Kriegel and Jorg Sander and Xiaowei Xu. “A DensityBased Algorithm for Discovering Clusters in Large Spatial Databases with Noise”. Evangelos Simoudis and Jiawei Han and Usama Fayyad. 1996. 8. Edwin M. Knorr and Raymond T. Ng and Vladimir Tucakov. “Distance-based outliers: algorithms and applications”. 2000. Volumen 8. 237—253. 9. Juan L. Cué Muñiz y Ernestina Castell Gil. “Estadística”. 1989. 10. Juan L. Cué Muñiz, Ernestina Castell Gil y José M. Hernández Carratalá. “Estadística’. Mayo 2004.