¿Existe un algoritmo hash que pueda identificar cadenas o archivos similares?

8

¿Existe un algoritmo hash que te ayude a identificar archivos o cadenas similares? Por ejemplo, el hash para ABC y XBC sería similar en lugar de radicalmente diferente, como suele ser el caso. Sé de una medida de similitud, Editar distancia ( enlace ). Pero esto no le da un hash para cada entrada para comparar, solo una puntuación entre cualquiera de las dos entradas.

Actualizar

El comentario de Andan (hash sensible a la localidad, LSH) es lo que estaba buscando. Mi motivo para hacer la pregunta es que me preguntaba cómo podría usarse LSH en la búsqueda de malware. ¿Se utiliza para identificar malware? ¿Por qué o por qué no?

Actualizar

En línea con la de Tom Leek, respondí que hice una investigación por mi cuenta. Escribí un programa que XOR los bytes de un archivo con un patrón "aleatorio" predeterminado (la semilla no cambió). Entonces sumaría el total de 1 bits. Esto produciría la distancia de Hamming desde el patrón aleatorio hasta el archivo. Realmente, no era una métrica muy útil, ya que básicamente (en promedio) solo estaba reduciendo a la mitad el tamaño del archivo para obtener un número.

Algunos ejemplos:

Dos ejecutables relacionados que examiné obtuvieron una puntuación de 2684964 y 2738772 con una diferencia de 53808. Están definitivamente relacionados (diferentes versiones de los programas que escribí) pero el valor de 53k es casi la mitad de la diferencia de tamaño de archivo en bits: ~ 128k. Por lo tanto, no es una métrica útil para determinar la similitud.

Escanee dos archivos JPEG de tamaño similar que definitivamente eran imágenes diferentes. Escanearon como 3124915 y 3110981 para una diferencia de 13934. Así que su diferencia fue "más pequeña" que la diferencia entre el ejecutable relacionado, a pesar de que no están relacionados. Así que tampoco es una métrica útil para determinar la diferencia.

Conclusión:

Como dijo Tom Leek, es un problema abierto por una razón.

    
pregunta John 31.10.2013 - 17:33
fuente

3 respuestas

5

Hay buenas razones teóricas por las que este hash no puede existir, o no puede ser "un hash" en el sentido criptográfico del término . En pocas palabras, si los valores hash de dos entradas "similares" son ellos mismos "similares" entre sí, entonces puede usar eso para recuperar de manera eficiente una entrada de una salida dada, lo que contradice resistencia de preimagen .

Desde sus etiquetas, supongo que está intentando diseñar un software antivirus que conoce las "firmas" del virus N y qué detectar cualquier virus que sea "similar" (para cierta noción de similitud ) a cualquiera de estos valores de N , pero con un costo computacional sustancialmente más bajo que las comparaciones de N (porque N puede ser muy alto). Cuando la noción de similitud es "igualdad exacta", puede ordenar las firmas y hacer una búsqueda binaria con un costo O (log N) (las funciones hash se utilizan para hacer el proceso aún más rápido al garantizar que todas las "firmas" tienen un tamaño constante fijo). Sin embargo, para una noción de similitud que no es tan clara, el problema se vuelve difícil.

La búsqueda de similitud de base de datos es un problema conocido de bioinformática donde se usa para secuencias de nucleótidos y objetos similares que deben combinarse en grandes bases de datos a pesar de las diferencias ocasionales. La conclusión es que:

  • Hay posibles soluciones, pero se basan en un modelo probabilístico de las diferencias reales que se pueden encontrar.
  • La gente ha estado buscando una buena solución durante décadas y sigue buscando.

Los métodos reales utilizados por el software antivirus para buscar firmas sin reducir la velocidad de la máquina a un rastreo son el núcleo de su negocio, por lo que, comprensiblemente, no son muy habladores al respecto. Podemos suponer que cualquiera que sea la solución que encuentren es probable que implique muchos ajustes e hipótesis sobre las variaciones reales de virus observadas en la naturaleza.

    
respondido por el Tom Leek 31.10.2013 - 18:24
fuente
6

Los "algoritmos de coincidencia aproximados" (aún un borrador del NIST) o las "funciones de hash que preservan la similitud" podrían ser de su interés. Estos algoritmos están diseñados específicamente para determinar la similitud entre dos objetos digitales. Algunos de los algoritmos propuestos hasta ahora (y útiles) son (cronológicamente): ssdeep , sdhash , mrsh -v2 .

Para determinar la similitud entre los objetos, estos algoritmos requieren una porción mínima de datos. Mrsh-v2 se desempeña mejor en términos de tamaño mínimo requerido.

Mrsh-v2 parece ser realmente prometedor en términos de rendimiento y tamaño de pieza mínimo requerido, pero aún está en desarrollo. Espero que potencialmente resuelva su problema de manejar archivos similares.

    
respondido por el Jor-el 31.10.2013 - 22:29
fuente
1

El hash está diseñado específicamente para hacer que las entradas se vean lo más diferentes posible. Lo que desea es un algoritmo de agrupación en clústeres para clasificar los elementos "similares" en la misma bandeja o en una bandeja adyacente. La similitud no es un concepto bien definido, necesitará una definición específica de dominio.

Como un experimento mental, suponga que desea detectar el término fraude de papel realizado mediante el corte y pegado de otros documentos. Podrías hacer algo como:

  1. Hash cada secuencia de 4 palabras y cuente el número de ocurrencias de cada hash.
  2. Descarte todos los hashes que aparecen en un gran diccionario de documentos comunes.
  3. Compartiendo los n hashes más comunes que quedan.

Para comparar la similitud de dos documentos, cuente cuántos hashes agrupados tienen en común.

    
respondido por el ddyer 31.10.2013 - 18:11
fuente

Lea otras preguntas en las etiquetas