Algoritmos evolutivos y malware, ¿evolucionan los "virus"? (III)

lunes, 28 de noviembre de 2016


En esta serie de artículos se realizará un repaso a la literatura académica en la que se mezclan estos dos conceptos: malware y algoritmos evolutivos. Analizaremos de forma crítica qué trabajos y artículos se han presentado en orden cronológico durante los últimos años, para comprobar si realmente tiene sentido utilizar los algoritmos genéticos para mejorar cualquier aspecto de la lucha contra el malware, ya sea en detección, análisis, predicción… Veremos un buen montón de experimentos basado en la algoritmia evolutiva, que a su vez también resulta apasionante.

Desde la última recopilación de 2009, se han vuelto a realizar diferentes experimentos que mezclan algoritmos evolutivos como herramienta para mejorar de algún modo la detección y clasificación de malware. Mostramos a continuación un resumen con espíritu crítico de nueve artículos académicos relativos a la materia, publicados todos de 2010 en adelante y en orden cronológico.

Malware Detection based on Dependency Graph using Hybrid Genetic Algorithm

Keehyung Kim y Byung-Ro Moon presentan en 2010 un mecanismo de detección de malware de script analizando los grafos de dependencia. La idea es modelizar el grafo de dependencia del malware (fundamentalmente creado en Visual Basic Script), y transformar el problema de detección en el de encontrar isomorfismos entre subgrafos de distintas variantes. Así, aunque el malware mute (modifique código con el fin específico de eludir una firma concreta), si mantiene la esencia de su estructura (algo necesario para garantizar su funcionalidad), podría ser detectado aunque el creador se esfuerce en eliminar su "firma". 

Lo interesante del experimento es resolver el problema de máximo isomorfismo entre grafos. Dos grafos lo son si se encuentra una biyección entre vértices que preserva la adyacencia entre nodos. Se desconoce un algoritmo éptimo (sin recurrir a la fuerza bruta de comprobar las n! biyecciones de nodos). Así que se recurre a algoritmos genéticos para solucionarlo en tiempo razonable.



La elección de malware de script permite disponer de su código tal y como fue escrito por el atacante. En el estudio se trata, calcula y reduce el grafo de cada script (en el que cada nodo es una línea de código). Este se compara entre un candidato a malware, calculando su máximo isomorfismo. Si sobrepasa un umbral, se pasa a un algoritmo genético que intentará clasificarlo como malware o no. El algoritmo utiliza una representación lineal de los vértices para trabajar. Como función de fitness, se evalúa la diferencia entre aristas. Una diferencia de cero, denotaría que un grafo es un completo subgrafo de otro, y por tanto a menor diferencia, mejor fitness (se ha encontrado un programa que, aunque "disfrazado" sigue el mismo flujo). Para elegir a candidatos se utiliza la ruleta y para la mutación, se muta con probabilidad 0.2 el intercambiando genes (que representan la posición de la arista en la disposición). Al margen del algoritmo genético, se utilizan dos aproximaciones heurísticas para optimización local. La primera intercambia aristas al azar. La segunda simplemente reorganiza un vértice insertándolo en otra posición.

En los experimentos usan la heurística (más rápida) como parapeto antes del algoritmo genético, obteniendo un buen resultado con ella simplemente. Para contrastar la eficacia de su sistema, la habitual comparación contra los antivirus sugiere que el algoritmo mejora el ratio de detección con respecto a la mayoría de motores. 

El estudio no resulta demasiado interesante desde el punto de vista de la detección del malware en sí, tal y como está enfocado. Por diversas razones:

  • Para que los resultados de uso de simple heurística sean alcanzados por el algoritmo genético, se utilizan 2000 generaciones como criterio de parada, lo que supone un coste computacional mucho mayor. No se ofrecen comparativas de tiempo al respecto en el artículo, pero se menciona que el coste de GA puede ser prohibitivo para sistemas que demanden una rápida respuesta. De hecho, en las propias conclusiones menciona que quizás podría utilizarse este mecanismo más lento para situaciones que no demanden una respuesta tan rápida, como la detección de copia de software en general. 
  • El uso en malware de script resulta en cierta manera ingenuo. Las muestras recogidas son muy simples (5 muestras), con cambios muy sencillos en su poliformismo (18 variantes en total). Más allá de los resultados, lo más interesante del estudio resulta la adaptación del software de script a grafos, el trabajo de su reducción y comparación buscando el isomorfismo.

Optimizing Decision Tree in Malware Classification System by using Genetic Algorithm

En este artículo, se utiliza un algoritmo genético como sistema de aprendizaje. En el estudio se intenta no tanto detectar malware, sino clasificar dentro de cuatro clases: Si la muestra estudiada ataca a los datos, aplicaciones, sistema o red. Lo llaman "Anti-Malware System Classifier".

Se utilizan tanto árboles de decisión como un algoritmo genético para comparar resultados. La metodología consiste en clasificar las muestras aleatoriamente dentro de los cuatro grupos y calcular el fitness con la media de los pesos de cada individuo en el grupo. Se usan técnicas estándar para la mutación y cruce. De un total de mil ejemplos, se intentan clasificar 200, tomando 20 comportamientos sospechosos (analizados tras la ejecución en una máquina virtual) como base de características para su clasificación. Los resultados globales mejoran (tras pasar por el algoritmo genético de clasificación) los resultados del árbol de decisión.

Este documento se complementa con la descripción del framework creado para poner en práctica los experimentos, y descrito (aunque de manera muy somera) en "A Framework for Optimizing Malware Classification by Using Genetic Algorithm" de 2011. El artículo resulta pobre en la descripción de detalles. La clasificación mejora con respecto a los árboles de decisión, pero solo para cuatro grupos y muy levemente. En el mejor de los casos se llega al 97% de precisión, con una tasa de falsos positivos excesivamente alta. 



Además, la clasificación del malware de esta forma (basada en qué ataca) no resulta tan interesante como la detección en sí misma.

Adaptive rule-based malware detection employing learning classifier systems

Se trata de una tesis en la que se analizan y experimenta con diferentes técnicas para la detección de malware basadas en árboles de decisión (usando el algoritmo C4.5) y LCS (Learning classifiying system) basados en algoritmos evolutivos (usando a su vez una variante de XCS para definir su fitness). En los algoritmos LCS las reglas son la población del algoritmo, y se centra en definir el mejor clasificador en ese conjunto de reglas. En cierta manera, un trabajo mucho más elaborado que los anteriores por su extensión, complejidad, minuciosidad, número de muestras empelados e intención específica de mejora. Compara el rendimiento del LCS (una adaptación propia de XCS) con diferentes métodos de inicialización, población, etc. La caracterización de las muestras (como es habitual) viene del estudio estático de funcionalidades propias de los archivos ejecutables. Aquí, son interesantes las siguientes conclusiones:
  • LCS mejora la generalización con respecto a C4.5, y detecta mejor malware previamente no visto.
  • LCS no sufre tanto del problema de límite de dimensionalidad que afecta a C4.5

Para los diferentes experimentos, LCS se inicializa con tres métodos diferentes: aleatorio, "covering" (se van creando reglas por cada fichero que llega y no queda clasificado) y la inicialización con C4.5, que parte de un conjunto de reglas ya generadas con ese algoritmo y mejoradas usando la función específica. Luego se usa C4.5 de nuevo como base comparativa.




Sin embargo, el estudio parece basarse en unos datos muy pobres y por tanto no puede tomarse como representativo: todo el malware usado proviene de la familia Poison Ivy. Esto es el cliente de un conocido troyano y por tanto sin diversidad. Sería comparable a crear distinto malware (en el sentido de un fichero con hash diferente) desde un mismo programa. Posee la capacidad de mutar, pero su funcionalidad es fundamentalmente la misma con unas características concretas que lo definen y que por tanto, ya usan los motores antivirus como firmas de los antivirus para detectarlo eficazmente. Aunque no se compara específicamente contra sistemas antivirus, es más que probable que los motores consiguieran resultados más que aceptables ya con sus sistemas de firmas. Además, en el estudio no se habla del tiempo necesario para la creación de reglas, que puede ser de nuevo un impedimento para su uso en tiempo real.

* Algoritmos evolutivos y malware, ¿evolucionan los "virus"? (I)
* Algoritmos evolutivos y malware, ¿evolucionan los "virus"? (II)
* Algoritmos evolutivos y malware, ¿evolucionan los "virus"? (III)
* Algoritmos evolutivos y malware, ¿evolucionan los "virus"? (IV)

Sergio de los Santos
ssantos@11paths.com

No hay comentarios:

Publicar un comentario