Skip to content

Así funciona una heurística antivirus. Segunda parte

Publicado por Sergio Hernando el 4 julio 2006

Tal y como comenté ayer, hoy vamos a terminar de hablar de heurísticas, y de su aplicación en productos antivirus.

Ayer nos quedamos en los 5 métodos típicos que se emplean en matemáticas y estadísticas explotarorias y de modelado. Estos métodos son:

  • Tabú search (TS, Búsqueda tabú)
  • Genetic algorithms (GA, Algoritmos genéticos)
  • Método Hero
  • Random ascent (RA, Subida azarosa)
  • Simulated annealing (SA, Temple simulado)

La búsqueda tabú

Este algoritmo es francamente útil. Teóricamente, se emplea para poder evitar caer en el cálculo de óptimos locales, que evidentemente no serán óptimos en todo el espacio de soluciones. Este efecto se consigue empleado estructuras de memoria, que retienen las soluciones ya exploradas y que por tanto, serán evitadas en futuras exploraciones, incurriendo en un ahorro computacional interesante.

En motores antivirus heurísticos, las listas tabú pueden emplearse con fines similares: evitar la caída en soluciones locales óptimas que no sean proyectable a un espacio de soluciones mayor. Un buen motor heurístico debe evitar excelentes detecciones proactivas de ciertas familias a costa de no explorar soluciones en otras familias de muestras.

Universidad de Sevilla: La búsqueda tabú, a diferencia de otros algoritmos basados en técnicas aleatorias de búsqueda de soluciones cercanas, se caracteriza porque utiliza una estrategia basada en el uso de estructuras de memoria para escapar de los óptimos locales, en los que se puede caer al "moverse" de una solución a otra por el espacio de soluciones.

Este algoritmo se dota, por tanto, de una "memoria" donde se almacenan los últimos movimientos realizados, y que puede ser utilizada para "recordar" aquellos movimientos que hacen caer de nuevo en soluciones ya exploradas. Esta "memoria" serviría para impedir la evolución hacia esas soluciones.

Algoritmos genéticos

Muy interesantes para determinar soluciones heurísticas. En este caso, se toma un universo de soluciones determinada, y se hace un ajuste de puntaje, en función a la calidad de la solución. Se descartan las soluciones menos óptimas y se refunden las restantes en universos menores, a los que se les vuelve a hacer el puntaje. Este proceso iterativo acaba, en un paralelismo con la teoría evolutiva, en la elección de las mejores soluciones.

Este sistema puede ser empleado por motores antivirus para clasificar las posibles soluciones y asignar, para cada caso, puntaciones para poder filtrar en función de la bondad del resultado obtenido para cada aproximación. Sobre el papel, la detección heurística final es la más adecuada.

Wikipedia: En los años setenta, de la mano de John Holland surgió una de las líneas más prometedoras de la inteligencia artificial, la de los algoritmos genéticos. Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular.

Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinación genética), así como también a una selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.

Método Hero

Un método que suele aplicarse bastante en cosas muy distantes a las soluciones antivirus, la gestión del régimen selvícola y forestal, pero que puede ser empleado en una solución antivirus.

En este caso, se escoge aleatoriamente una solución inicial, en este caso un régimen de comportamiento en la detección. Esta solución inicial se enfrenta a otras soluciones de un modo secuencial, con el fin de determinar si otras solucione splausibles mejorarían la primera elección. En caso de que se produzca la mejora, la solución original es sustituída por aquella que la mejora. Este proceso se repite hasta que la secuencia finaliza.

Subida azarosa

Parecido al anterior, pero en este caso la secuencia se detiene cuando se alcanza el número máximo de iteraciones de mejora inicialmente establecido, aún no habiendo acabado la secuencia de todas las soluciones posibles a enfrentar con la inicialmente escogida.

Temple simulado

Muy vinculado con las Redes Neuronales, este método está especialmente orientado a universos muestrales tremendamente grandes, donde el tiempo de computación es crítico, y donde por motivos obvios, no podemos invertir años para determinar la solución óptima.

Las iteraciones de optimización parte de un estado actual s0, y contempla estados próximos de solución s1, s2 ... sn. El paso a estos estados se realiza si probabilísticamente el estado final se adecúa mejor a los requisitos de optimización establecidos. En motores antivirus, obviamente, los estados sn son estados de solución, entre los que se salta buscando el resultado óptimo.

Wikipedia: Simulated annealing (SA) es una meta-heurística para problemas de optimización global, es decir, encontrar una buena aproximación al óptimo global de una función en un espacio de búsqueda grande.

El nombre e inspiración viene del proceso de templado (annealing, en inglés) en metalurgia, una técnica que incluye calentar y luego enfriar controladamente un material para aumentar el tamaño de sus cristales y reducir sus defectos. El calor causa que los átomos se salgan de sus posiciones iniciales(un mínimo local de energía) y se muevan aleatoriamente; el enfriamiento lento les da mayores probabilidades de encontrar configuraciones con menor energía que la inicial.

Redes neuronales. ¿El futuro en la gestión antimalware?

red neuronal

Todos estos métodos son piezas clave de la inteligencia artificial, ya que a fin de cuentas, son métodos de decisión. Las redes neuronales son, con casi toda probabilidad, el máximo exponente de los métodos exploratorios que hemos visto.

Imaginad el ejemplo que comentábamos ayer, un escáner de detección de bombas en un aeropuerto. Es imposible meterle al sistema todas y cada una de las infinitas posibilidades de aspecto y funcionalidad que puede tener una bomba casera. No podemos identificar, por tanto, la existencia de una bomba en función a patrones conocidos. De hacerlo así, seguramente más de una pasaría por el escáner y no sería detectada.

Esto puede ser aplicable a los motores antivirus. Yo en su día suscribí la opinión de que la detección sólo basada en firmas no vale para nada. Los virus a fin de cuentas, son bombas con una variabilidad tan amplia que fiarnos exclusivamente de patrones prefedinidos es un camino al fracaso.

Los motores antivirus, en mi modesta opinión y siempre basándola en mi criterio matemático, que no es el criterio de un especialista en malware ni el de un director de laboratorio, tienen que tender al modelo de detección de firmas apoyado en decisiones neuronales. Sí, suena fuerte decirlo, pero la alta variabilidad de muestras hace que las detecciones fallidas aumente peligrosamente, con lo que es necesario dotar a estos productos de métodos heurísticos avanzados que permitan atajar las muestras que escapan del análisis contra las firmas.

Las ventanas de un modelo de red neuronal proporcionarían a un antivirus las mejores ventajas de un sistema de este tipo: Aprendizaje autónomo, organización interna automática, tolerancia a los fallos, flexibilidad y respuestas rápidas en tiempo real.

Dentro de algunos años retomaremos el tema y veremos por dónde han ido los derroteros en el I+D+i antimalware :)

Be Sociable, Share!

Categoría/s → Metodos Matematicos

8 comentarios
  1. 4 julio 2006

    PROPOSICION DESHONESTA

    Años atrás entrevisté/tamos al responsable de la heurística del antivirus NOD32 de la empresa ESET, Richard Marko. Una de las carencias de la entrevista entrevista fue la ausencia de preguntas específicas sobre heurística, desaprovechando la gran ocasión.

    Antigua Nautopía Entrevista a Richard Marko para Nautopía

    ¿Qué te parece concertar una futura entrevista, después del verano? Con aportaciones también de los lectores, tal como se demandó entonces. Con la colaboración de algunos virii en el redactado del cuestionario.

    Una entrevista a fondo, exigente, exprimiendo al máximo al entrevistado y sus conocimientos técnicos.

  2. 4 julio 2006
    Ignacio permalink

    Si esperan al SIMO TCI 2006, seguramente ahi estará Richard para ser entrevistado :-)

    PD: Muy buen articulo!

  3. 5 julio 2006

    maty,

    Por mí no hay problema. Puedes contar con ello :)

  4. 7 julio 2006

    Tomo nota.

    Y si nos invitan al SIMO, con gastos pagados, mejor, digo. Aunque, la verdad, año tras año el SIMO madrileño va perdiendo interés.

  5. 8 julio 2006

    Hace milenios que no voy al SIMO, ya que la verdad, su calidad como evento relevante ha caído en picado, pero a caballo regalado, no se le mira el diente :)

    Lo dicho, cuenta con ello.

    Un saludete ;)

  6. 19 julio 2006
    Ignacio permalink

    Son rápidos para pedir, ¿eh? :-)
    Eso habrá que consultarlo a Ontinet… Y sino, veremos qué se pueda hacer ;-P

  7. 15 septiembre 2008

    Sergio.. muchisimas gracias me encanta tu blog, siempre que tocas temas de heuristica (como la primera parte) me encuentro fascinado, veo que tienes muchos conocimientos, estoy estudiando desarrollo de software, me gustaria hablar contigo, estoy seguro que aprenderé muchas cosas! crees que sea posible? por favor responder.

    El mayor saludo desde venezuela

  8. 10 julio 2011

    falto mas informacion acerca de heuristica

Escribir un comentario

Note: XHTML permitido. Tu email nunca será publicado.

Suscribirse a los comentarios via RSS