¿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.