Pregunta Enfoque programático en Java para comparación de archivos


¿Cuál sería el mejor enfoque para comparar dos firmas de archivos hexadecimales entre sí por similitudes.

Más específicamente, lo que me gustaría hacer es tomar la representación hexadecimal de un archivo .exe y compararlo con una serie de firmas de virus. Para este enfoque, planeo romper la representación hexadecimal del archivo (exe) en grupos individuales de N caracteres (es decir, 10 caracteres hexadecimales) y hacer lo mismo con la firma del virus. Mi objetivo es realizar algún tipo de heurística y, por lo tanto, verificar estadísticamente si este archivo ejecutable tiene un X% de similitud con la firma del virus conocido.

La manera más simple y probable de equivocarme que pensé hacer esto es comparar el exe [n, n-1] contra el virus [n, n-1] donde cada elemento de la matriz es una matriz secundaria, y por lo tanto exe1 [0, 9] contra virus1 [0,9]. Cada subconjunto será calificado estadísticamente.

Como se puede ver, habría una gran cantidad de comparaciones y, por lo tanto, sería muy, muy lento. Así que pensé en preguntar si ustedes pueden pensar en un mejor enfoque para hacer tal comparación, por ejemplo implementando diferentes estructuras de datos juntas.

Esto es para un proyecto que estoy haciendo para mi BSc donde estoy tratando de desarrollar un algoritmo para detectar malware polimórfico, esta es solo una parte de todo el sistema, mientras que el otro se basa en algoritmos genéticos para desarrollar la firma del virus estático. Cualquier consejo, comentario o información general como recursos son bienvenidos.


Definición: El malware polimórfico (virus, gusano, ...) mantiene la misma funcionalidad y carga útil que su versión "original", mientras que aparentemente tiene estructuras diferentes (variantes). Lo logran mediante la ofuscación del código y, por lo tanto, alteran su firma hexadecimal. Algunas de las técnicas utilizadas para el polimorfismo son; alteración de formato (insertar eliminar espacios en blanco), cambio de nombre de variable, reordenamiento de extracto, adición de código no deseado, reemplazo de extracto (x = 1 cambia a x = y / 5 donde y = 5), intercambio de instrucciones de control. Tanto como el virus de la gripe muta y, por lo tanto, la vacunación no es efectiva, el malware polimórfico muta para evitar la detección.


Actualizar: Después del consejo que ustedes me dieron respecto a qué lectura hacer; Lo hice, pero me confundió un poco más. Encontré varios algoritmos de distancia que pueden aplicarse a mi problema, como;

  • La subsecuencia común más larga
  • Algoritmo de Levenshtein
  • Algoritmo Needleman-Wunsch
  • Algoritmo de Smith-Waterman
  • Algoritmo de Boyer Moore
  • Algoritmo de Aho Corasick

Pero ahora no sé qué usar, todos parecen hacer lo mismo de diferentes maneras. Seguiré investigando para poder entender mejor a cada uno; pero, mientras tanto, ¿podría darme su opinión sobre which might be more suitable para que pueda darle prioridad durante mi investigación y estudiarla más profundamente.


Actualización 2: Terminé usando una amalgama de LCSubsequence, LCSubstring y Levenshtein Distance. Gracias por todas las sugerencias.

Hay una copia del trabajo terminado en GitHub


10
2017-11-01 10:49


origen


Respuestas:


Para algoritmos como estos, sugiero que busque en el área de bioinformática. Existe un problema similar al establecer que se tienen archivos grandes (secuencias de genoma) en los que se buscan determinadas firmas (genes, secuencias base breves especiales bien conocidas, etc.).

También para considerar el malware polimórfico, este sector debería ofrecerte mucho, porque en biología parece igualmente difícil obtener coincidencias exactas. (Desafortunadamente, no conozco los algoritmos apropiados de búsqueda / coincidencia para señalarlo).

Un ejemplo de esta dirección sería adaptar algo como el Aho Corasick algoritmo para buscar varias firmas de malware al mismo tiempo.

Del mismo modo, algoritmos como el Boyer Moore Algoritmo le ofrece tiempos de búsqueda fantásticos especialmente para secuencias más largas (caso promedio de O (N / M) para un texto de tamaño N en el que busca un patrón de tamaño M, es decir, tiempos de búsqueda sublineales).


4
2017-11-02 14:15



Se han publicado varios documentos sobre la búsqueda de documentos duplicados en un gran corpus de documentos en el contexto de la búsqueda web. Creo que los encontrarás útiles. Por ejemplo, ver esta presentación.


2
2017-11-02 13:49



Recientemente se ha investigado seriamente la automatización de la detección de informes de errores duplicados en los repositorios de errores. Este es esencialmente el mismo problema que enfrenta. La diferencia es que estás usando datos binarios. Son problemas similares porque buscará cadenas que tengan el mismo patrón básico, aunque los patrones tengan algunas diferencias leves. Un algoritmo de distancia vertical probablemente no le servirá bien aquí.

Este documento ofrece un buen resumen del problema, así como algunos enfoques en sus citas que se han probado.

ftp://ftp.computer.org/press/outgoing/proceedings/Patrick/apsec10/data/4266a366.pdf


1
2017-11-03 14:59



Como alguien ha señalado, la similitud con un problema conocido de cadena y bioinformática podría ayudar. La subcadena común más larga es muy quebradiza, lo que significa que una diferencia puede reducir a la mitad la longitud de una cuerda. Necesitas una forma de alineación de cuerdas, pero más eficiente que Smith-Waterman. Intentaré ver programas como BLAST, BLAT o MUMMER3 para ver si se ajustan a tus necesidades. Recuerde que los parámetros predeterminados, para estos programas, se basan en una aplicación de biología (cuánto penalizar una inserción o una sustitución, por ejemplo), por lo que probablemente debería considerar la reestimación de parámetros en función de su dominio de aplicación, posiblemente en función de un conjunto de entrenamiento. Este es un problema conocido porque incluso en biología diferentes aplicaciones requieren diferentes parámetros (basados, por ejemplo, en la distancia evolutiva de dos genomas para comparar). Sin embargo, también es posible que, incluso por defecto, uno de estos algoritmos produzca resultados utilizables. Lo mejor de todo sería tener un modelo generativo de cómo cambian los virus y que podría guiarlo en una elección óptima para un algoritmo de distancia y comparación.


1
2017-11-03 21:11