enfoque programático en Java para la comparación de archivos
https://stackoverflow.com/questions/4068218
-
28-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cuál sería el mejor método para comparar dos firmas de archivo hexadecimal uno contra el otro en busca de similitudes.
Más específicamente, lo que me gustaría hacer es tomar la representación hexadecimal de un archivo .exe y compararla con una serie de firmas de virus. Para este enfoque planeo para romper el archivo (exe) representación hexadecimal en grupos individuales de N caracteres (es decir. Caracteres 10 hex) y hacer lo mismo con la firma de virus. Mi objetivo es llevar a cabo algún tipo de heurística y por lo tanto estadísticamente comprobar si este archivo exe tiene un X% de similitud con la firma de virus conocidos.
La manera más simple y probablemente muy mal pensé en hacer esto es, para comparar exe [n, n-1] contra el virus [n, n-1], donde cada elemento de la matriz es una matriz de sub, y por lo tanto exe1 [0,9] contra virus1 [0,9]. Cada subconjunto se calificará estadísticamente.
Como puede darse cuenta de que habría un número masivo de las comparaciones y por lo tanto muy lento. Así que pensé que preguntar si ustedes pueden pensar en un mejor enfoque para hacer tal comparación, por ejemplo, la implementación de diferentes estructuras de datos juntos.
Esto es para una am proyecto haciendo para mi BSc donde estoy tratando de desarrollar un algoritmo para detectar malware polimórfico, esto es sólo una parte de todo el sistema, en el que el otro se basa en algoritmos genéticos para evolucionar la estática de firmas de virus. Cualquier consejo, comentarios o información general, como los recursos son muy bienvenidos.
Definición : el malware polimórfico (virus, gusanos, ...) mantiene la misma funcionalidad y la carga útil como su versión "original", si bien tienen estructuras aparentemente diferentes (variantes). Logran que por la ofuscación de código y alterando así su firma hexagonal. Algunas de las técnicas utilizadas para el polimorfismo son; formato de alteración (piezas en bruto de inserción quitar), el cambio de nombre variables, reordenamiento declaración, además código basura, el reemplazo de declaración (x = 1 cambia a x = y / 5 donde y = 5), el intercambio de instrucciones de control. Tanto como el virus muta la gripe, por lo que la vacunación es, muta de malware polimórfico no eficaces para la detección de evitar.
Actualización: Después de que el consejo que ustedes me dio lo que en lo que respecta a la lectura de hacerlo; Lo hice, pero es algo que me confunde más. He encontrado varios algoritmos de distancia que pueden aplicarse a mi problema, tales como;
- más larga subsecuencia común
- Levenshtein algoritmo
- algoritmo de Needleman-Wunsch
- algoritmo de Smith-Waterman
- algoritmo de Boyer Moore
- algoritmo de Aho Corasick
Pero ahora no sé cuál utilizar, que parecen hacer todo lo que él mismo de diferentes maneras. Voy a seguir para hacer la investigación para que pueda entender mejor cada uno de ellos; pero en la media hora podría darme su opinión sobre which might be more suitable para que yo pueda darle prioridad durante mi investigación y el estudio más profundo.
Actualización 2: que terminó usando una amalgama de la LCSubsequence, LCSubstring y Levenshtein Distancia. Gracias por todas las sugerencias.
Hay una copia del papel acabado en GitHub
Solución
Para algoritmos como estos le sugiero mirar en el área de la bioinformática. Existe una configuración de allí en que tiene archivos de gran tamaño (secuencias del genoma) en el que usted está buscando ciertas firmas (genes, secuencias especiales Conocida base corta, etc.) problema similar.
También para considerar el malware polimórfico, este sector debe ofrecer mucho, porque en la biología parece igualmente difícil de obtener coincidencias exactas. (Por desgracia, no estoy al tanto de la búsqueda aproximativa apropiado / algoritmos de correspondencia para señalarle al.)
Un ejemplo de esta dirección sería adaptar algo así como el Aho Corasick algoritmo con el fin de buscar varias firmas de malware al mismo tiempo.
Del mismo modo, los algoritmos como el Boyer Moore algoritmo DOY fantásticos tiempos de ejecución de búsqueda en especial para las secuencias más largas ( caso promedio de O (N / M) para un texto de tamaño N en el que buscar un patrón de tamaño M, es decir, sublineal tiempos de búsqueda).
Otros consejos
Varios trabajos han sido publicados en la búsqueda de documentos duplicados cerca de un gran corpus de documentos en el contexto de la búsqueda en la red. Creo que lo encontrará útil. Por ejemplo, véase este presentación .
Ha habido una cantidad seria de la investigación reciente en la automatización de la detección de los informes de fallos duplicados en los repositorios de errores. Esto es esencialmente el mismo problema que está enfrentando. La diferencia es que está utilizando datos binarios. Son problemas similares porque se le busca cadenas que tienen el mismo patrón básico, a pesar de que los patrones pueden tener algunas pequeñas diferencias. Un algoritmo de distancia recta arriba probablemente no le servirá bien aquí.
Este documento ofrece un resumen bien del problema, así como algunos enfoques en sus citas que se han probado.
Como alguien tiene puntas hacia fuera, similitud con el conocido problema podría ayuda de cuerdas y la bioinformática. Subcadena más larga común es muy frágil, lo que significa que una diferencia puede reducir a la mitad la longitud de una cadena de este tipo. Se necesita una forma de alineación de las cadenas, pero más eficiente que el de Smith-Waterman. Me gustaría probar y ver programas como BLAST, Blat o MUMMER3 para ver si pueden adaptarse a sus necesidades. Recuerde que los parámetros por defecto, para estos programas, se basan en una aplicación de la biología (la cantidad de penalizar una inserción o una sustitución, por ejemplo), por lo que probablemente debería mirar parámetros re-estimar en base a su dominio de aplicación, posiblemente basados ??en una 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). También es posible, sin embargo, que incluso en un defecto de estos algoritmos pueden producir resultados útiles. Lo mejor de todo sería tener un modelo generativo de cómo cambian los virus y que podrían servir de guía en una opción óptima para un algoritmo de distancia y comparación.
