Cálculo de similitud de datos binarios

Question

He visto algunas preguntas relacionadas con la determinación de la similitud de los archivos, pero todas están vinculadas a un dominio en particular (imágenes, sonidos, texto, etc.). Las técnicas que se ofrecen como soluciones requieren el conocimiento del formato de archivo subyacente de los archivos que se comparan. Lo que estoy buscando es un método sin este requisito, donde se puedan comparar archivos binarios arbitrarios sin necesidad de entender qué tipo de datos contienen. Es decir, estoy buscando determinar el porcentaje de similitud de los datos binarios de dos archivos.

Para darle un poco más de detalle para que trabaje, aunque esto es potencialmente aplicable a muchas cosas, tengo un problema específico en el que estoy trabajando. Actualmente también tengo una solución de trabajo, pero no creo que sea ideal. Probablemente haya muchas optimizaciones en términos del método de comparación y el almacenamiento de los resultados. Espero que algunas personas aquí puedan darme algunas ideas nuevas. Probablemente edite alguna información sobre mi método actual después de un par de días, pero no quiero sesgar los pensamientos de las personas sobre el problema diciéndoles cómo lo estoy haciendo.

El problema en el que estoy trabajando es detección de clones para imágenes ROM de videojuego. Para aquellos que no tienen experiencia con la emulación, los ROM son volcados de los datos en los cartuchos de juego. Un "clon" ROM es típicamente una versión modificada del mismo juego, el tipo más común es una versión traducida. Por ejemplo, las versiones en japonés e inglés del original Final Fantasy para el NES son clones. Los juegos comparten casi todos sus recursos (sprites, música, etc.), pero el texto ha sido traducido.

Actualmente hay varios grupos que trabajan en el mantenimiento de listas de clones para los distintos sistemas, pero hasta donde sé, todo esto se hace de forma manual. Lo que intento hacer es encontrar un método para detectar imágenes de ROM similares de forma automática y objetiva, en función de la similitud de los datos en lugar de "estos parecen el mismo juego". Existen varias razones para detectar clones, pero una de las principales motivaciones es usarlo con Solid compression. Esto permite la compresión de todos los clones de juegos en el mismo archivo, con todo el conjunto de clones comprimidos ocupando a menudo solo un poco más de espacio que una de las ROM individuales.

Algunas de las preocupaciones a tener en cuenta cuando sube con enfoques posibles:

• ROM varían altamente en tamaño, dependiendo del sistema. Algunos son pequeños, pero los sistemas modernos pueden tener grandes, 256 MB o más. Algunos sistemas (¿todos?) Solo tienen potencias de 2 como posibles tamaños, un juego de 130MB en uno de estos sistemas tendría una ROM de 256MB, en gran parte vacía. Tenga en cuenta que debido a esto, algunos clones pueden tener tamaños muy diferentes, si una versión del juego cruza el umbral y tiene que usar un cartucho que es dos veces el tamaño.
• En la actualidad, existen miles de ROM conocidas en muchos sistemas, y la mayoría de los sistemas aún tienen nuevas liberadas constantemente. Incluso para sistemas más antiguos, existe una gran comunidad de hackers ROM que produce ROM modificados a menudo.
• Almacenar los datos de similitud para cada posible par de ROM daría como resultado millones de filas de datos para cualquiera de los sistemas más populares. Un sistema con 5000 ROM requeriría 25 millones de filas de datos de similitud, con un solo juego nuevo que agrega otras 5000 filas.
• El estado del procesamiento debe ser recuperable, de modo que si se interrumpe puede continuar donde lo dejó. Con cualquier método, se requerirá mucho procesamiento, y asumir que todo se ejecutará en un lote no es seguro.
• Se pueden agregar nuevas ROM en cualquier momento, por lo que el método no debe suponer que ya tiene un conjunto "completo".Es decir, incluso después de haber calculado la similitud para todas las ROM existentes, si se agrega una nueva (y esto también podría ocurrir antes de que el procesamiento anterior haya finalizado por completo) debe haber un método para compararla con todas las anteriores, para determinar cuál (si hay alguno) es un clon de.
• Mayor velocidad de procesamiento debe tener prioridad sobre la precisión (hasta cierto punto). Saber si dos ROM son 94% o 96% similares no es particularmente importante, pero si se tarda un día de procesamiento para comparar una nueva ROM con todas las anteriores, el programa probablemente nunca se complete realmente.

Ha sido un problema interesante en el que trabajar, espero ver lo que otras personas pueden proponer. Déjame saber en los comentarios si quieres más detalles, y trataré de proporcionarlos.

Answer 1

Parece que usted quiere un delta binaria o tal vez un índice derivado de la aplicación de un delta binaria (como su tamaño). A continuación, puede comparar este índice con una línea de base que determine experimentalmente para decidir si es un "clon" o no.

Hay muchas similitudes entre la compresión y la creación delta, así que diría que no está muy lejos con su aplicación actual.

Dicho esto, la comparación por pares de cada archivo binario en su base de datos es probablemente prohibitivamente costosa (O (n), creo). Intentaría encontrar un hash simple para identificar posibles candidatos para comparar. Algo conceptualmente similar a lo que sugieren spdenne y Eduard. Es decir, busque un hash que se pueda aplicar a cada elemento una vez, ordene esa lista y luego use una comparación de granulado más fino en los elementos cuyos hash están muy juntos en la lista.

hashes La construcción de útiles para el caso general ha sido un tema de investigación perseguido activamente en CS durante varios años. La biblioteca de software LSHKit implementa algunos algoritmos de este tipo. El documento accesible en Internet FINDING SIMILAR FILES IN A LARGE FILE SYSTEM parece que podría estar destinado más a la comparación de archivos de texto, pero podría serle útil. El documento más reciente Multi-resolution similarity hashing describe un algoritmo más poderoso. Sin embargo, no parece ser accesible sin una suscripción. Es probable que desee mantener el artículo de wikipedia en Locality Sensitive Hashing a mano mientras navega por los otros recursos. Todos se vuelven bastante técnicos y la entrada de la wikipedia en sí es bastante pesada. Como alternativa más fácil de usar, es posible que pueda aplicar algunas ideas (o incluso ejecutables) desde el campo Acoustic Fingerprinting.

Si estás dispuesto a abandonar el caso general es probable que se puede encontrar una función hash mucho más simple (y más rápido) de dominio específico que funciona sólo para ROMs. Posiblemente algo que implique la colocación de secuencias de bytes estándar o comunes, y el valor de los bits de selección cerca de ellos. Realmente no sé mucho sobre tu formato binario pero estoy imaginando cosas que señalan el inicio de secciones en el archivo como regiones para sonido, imágenes o texto. Los formatos binarios almacenan con frecuencia las direcciones de este tipo de secciones cerca del comienzo del archivo. Algunos también usan un mecanismo de encadenamiento que almacena la dirección de la primera sección en una ubicación conocida junto con su tamaño. Esto le permite pasar a la siguiente sección que también contiene un tamaño, etc. Una pequeña investigación probablemente le permitirá descubrir cualquier formato relevante, si aún no lo sabe, y debería ayudarlo a construir un hash útil.

Si las funciones hash no lo llevan hasta el final (o requieren entradas de algún tipo para definir una métrica/distancia), entonces hay varios algoritmos delta binarios e implementaciones disponibles en la web. Con el sistema de control de versiones de Subversion utilizo el que estoy más familiarizado. Utiliza un algoritmo delta binario llamado xdelta para almacenar eficientemente las revisiones de archivos binarios. Aquí hay un enlace directamente al archivo en su repositorio que lo implementa: xdelta.c. Probablemente haya una herramienta en la web que hace esto más accesible también.

Answer 2

Es posible que desee mirar bsdiff, que es un sistema binario de parchado/difuminado. También hay una tesis con mucha teoría.

Answer 3

Puedes comenzar almacenando algo como hash trees. Solo es necesario almacenar uno de esos hashes para cada ROM, y el espacio de almacenamiento requerido es solo proporcional (pero muy inferior) al tamaño de la ROM, suponiendo un tamaño de bloque constante. El tamaño de bloque elegido debe proporcionar suficiente granularidad para garantizar la precisión, por ejemplo: para un tamaño mínimo de 128MiB, restricción de precisión del 1% y Tiger-128 hash (similar a lo que utilizan para verificar los archivos transferidos a través de DirectConnect), un tamaño de bloque de 1MiB funciona bien y ¡puedes almacenar todos los hashes en 128 * 128/8 = 2048 bytes! Así que hacerlo por 10,000 ROMs solo requeriría unos 20MiB de espacio. Además, puede elegir un hash menos seguro, pero más rápido y/o más pequeño. Agregar/verificar la similitud de una nueva ROM implicaría algo como:

1. Dividir la nueva ROM en bloques y asignar hash a cada uno de ellos.
2. Para cada ROM que ya se encuentra en la base de datos, compare (vea a continuación) sus hash con los hashes de la nueva ROM.

La función de comparación debe verificar la similitud. Pero debe tratar cada hash como un valor indivisible, es decir, no se moleste en tratar de encontrar una función de diferencia lógicamente significativa entre dos hashes. Siempre que el tamaño del bloque sea lo suficientemente bajo y las colisiones hash sean lo suficientemente raras, la precisión está garantizada por una simple comparación igual.

Como ve, el problema se reduce a uno más simple en términos de rendimiento: verificando conjuntos de datos mucho más pequeños en busca de similitudes.

Answer 4

Creo que algunas técnicas tomadas de datos de compresión podría ser interesante aquí:

Suponga que tiene dos archivos, A y B.

Comprimir cada archivo individualmente y añadir los tamaños comprimidos juntos. Luego concatenar los dos archivos en un solo archivo grande y comprimirlo también.

La diferencia en los tamaños le dará una estimación aproximada de la similitud de los archivos.

Sugiero que pruebe la Transformación de Burrow Wheeler (bzip2) para hacer la compresión. La mayoría de los otros algoritmos de compresión solo tienen un historial limitado. El algoritmo BWT otoh puede trabajar en grandes cantidades de datos. El algoritmo "ve" ambos archivos al mismo tiempo y cualquier similitud dará como resultado una relación de compresión más alta.

Answer 5

dos pensamientos:

• la posibilidad de organizar el archivo como un gráfico de flujo de datos y haciendo algunas canónicos en que represention. Ya que conoce el conjunto de instrucciones, esto puede ser factible, tal vez simplemente ajustando un desensamblador y haciendo algo de procesamiento de texto.
• Un clasificador entrenable como CRM114 puede ser útil para darle una representación compacta que le da una idea de si los archivos binarios tienen mucho en común.

Answer 6

Aunque ha pasado mucho más que "un par de días", calculé que probablemente debería agregar mi solución actual aquí.

Nils Pipenbrinck iba en la misma dirección que mi método actual. Dado que uno de los principales resultados de la búsqueda de clones es un gran ahorro de un sólido archivado, pensé que podría intentar comprimir dos ROM juntos y ver cuánto espacio se guardaba. Estoy usando el algoritmo LZMA en 7zip para esto.

El primer paso es comprimir cada ROM individualmente y observar el tamaño comprimido, luego intente archivar las dos ROM juntas y vea cuánto difiere el tamaño resultante de sus tamaños comprimidos individuales. Si el tamaño combinado es igual a la suma de los tamaños individuales, son 0% similares, y si el tamaño es el mismo que uno de ellos (el más grande), son idénticos.

Ahora bien, esta es una enorme cantidad de intentos de compresión requerida, así que tengo un par de optimizaciones hasta el momento (y le gustaría averiguar más):

1. Priorizar comparaciones basadas en la similitud de la comprimido los tamaños son Si la ROM A tiene un tamaño comprimido de 10 MB y la ROM B tiene un tamaño comprimido de 2 MB, es imposible que tengan más del 20% de similitud, por lo que compararlos para obtener el resultado real puede dejarse para más tarde. Ejecutar el mismo algoritmo de compresión en archivos muy similares tiende a producir resultados de tamaño similar, por lo que encuentra muchos clones muy rápidamente.

2. Combinado con lo anterior, mantenga los "límites" superiores e inferiores en la posible similitud entre cualquier par de ROM. Esto permite una mayor priorización. Si las ROM A y B son 95% similares, y las ROM B y C son solo 2% similares, entonces usted ya sabe que A y C están entre 0% y 7%. Esto es demasiado bajo para ser un clon, por lo que esta comparación se puede posponer con seguridad o incluso ignorar por completo, a menos que realmente quiera saber las similitudes exactas de todo.

Answer 7

Utiliza algunas ideas de Plagiarism Detection algoritmos.

Mi idea:

Con el fin de crear una "firma" comparable para cada ROM, que varía ligeramente a medida que pequeñas porciones cambian, producen algo así como un gráfico de frecuencia de palabras, pero en lugar de registrar las frecuencias de palabras, podría hash secciones muy cortas de la ROM, y registrar las frecuencias de los valores hash.

No solo hash una sección, luego la siguiente sección comenzando desde el final de la primera sección, sino una ventana deslizante, hash la sección comenzando desde byte 1, luego hash la misma sección de tamaño comenzando desde byte 2 , luego desde el byte 3, etc. Eso anulará el efecto de las porciones variables de diferentes tamaños dentro de su ROM.

Si usó una función hash simple como xor de cada byte de 8 bits, para que pueda calcular fácilmente el hash de la siguiente posición de ventana por xor el hash actual con los 8 bits salientes y xor los 8 bits entrantes. Otra función hash alternativa puede ser simplemente usar la longitud de palabra del código de instrucción. Eso puede ser suficiente para crear patrones estáticos para los códigos que representan las instrucciones de la máquina. Lo importante es que querrá una función hash que dé como resultado secuencias breves comunes en el código de instrucción, dando como resultado los mismos valores hash.

Es probable que desee un menor número de valores hash con frecuencias más altas de cada uno, pero no ir demasiado lejos o su gráfico será demasiado plana, lo que resulta en dificultades para compararlos. Del mismo modo, no vayas demasiado lejos, o tendrás muchas frecuencias muy pequeñas, lo que dificultará la comparación otra vez.

tienda por este gráfico ROM. Compare gráficos de frecuencia para dos ROM diferentes calculando la suma de los cuadrados de la diferencia en frecuencias para cada valor de hash. Si eso suma cero, las ROM probablemente sean idénticas. Cuanto más alejado esté del cero, menos serán los ROM.

Answer 8

Como se ha dicho Waylon Flinn, es posible que necesite un algoritmo de diferencias de código binario. El rsync algorithm es bueno. Es rápido y confiable. Vea también el utility's documentation.

Answer 9

La dificultad aquí es que, dado que se trata de código ejecutable, cambios simples pueden propagarse a través de toda la ROM. Las direcciones y compensaciones para TODOS los valores pueden cambiar con la adición de una sola variable o instrucción no operativa. Eso hará que incluso el hashing basado en bloques carezca de valor.

Una solución rápida y sucia, sería la de cortar una solución con difflib (o el equivalente w/su idioma favorito), ya que se obtiene una comparación deslizante que se puede tratar con la adición de datos o remoción. Divida la ROM en secciones ejecutables y de datos (si es posible). La sección de datos se puede comparar directamente y un similarity ratio calculated, aunque todavía tendrá problemas con direcciones o desplazamientos.

La sección ejecutable es más interesante. Lea en el formato de ASM de la máquina, tome el ejecutable y divídalo en una secuencia de códigos de operación. Deje el código de operación y registre las partes, pero enmascare las partes "carga útil"/"inmediata" (donde carga las direcciones de las variables). Entregue la información resultante a la calculadora de relación de similitud también.

La parte desafortunada es que esta sigue siendo una operación O (n^2) en el número de ROM que rastrea, pero que se puede aliviar con clústeres (incrementales) o una orden de comparación basada en frecuencia para reducir la cantidad de comparaciones necesarias

Answer 10

Xdelta es bastante útil para conseguir diffs binarios decente: http://xdelta.org