Calcular la similitud de datos binarios

Question

He visto algunas preguntas aquí relacionadas con determinar la similitud de archivos, pero todas están vinculadas a un dominio particular (imágenes, sonidos, texto, etc.).Las técnicas ofrecidas como soluciones requieren 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 brindarle un poco más de detalles con los que pueda trabajar, 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 que funciona, pero no creo que sea ideal.Probablemente haya muchas optimizaciones en términos del método de comparación y almacenamiento de los resultados.Con suerte, algunas personas aquí podrán darme algunas ideas nuevas.Probablemente editaré alguna información sobre mi método actual después de un par de días, pero no quiero sesgar los pensamientos de la gente sobre el problema diciéndoles cómo ya lo estoy haciendo.

El problema en el que estoy trabajando es Detección de clones para imágenes ROM de videojuegos..Para aquellos que no tienen experiencia con la emulación, las ROM son volcados de datos en los cartuchos del juego.Un "clon" de ROM suele ser una versión modificada del mismo juego, siendo el tipo más común una versión traducida.Por ejemplo, las versiones japonesa e inglesa del original Fantasía Final para 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 yo sé, todo esto se hace manualmente.Lo que intento hacer es encontrar un método para detectar imágenes ROM similares de forma automática y objetiva, basándose en la similitud de datos en lugar de "parecen el mismo juego".Hay varias razones para detectar clones, pero una de las principales es su uso con Compresión sólida.Esto permite la compresión de todos los clones de juegos juntos en el mismo archivo, y el conjunto completo de clones comprimidos a menudo ocupa solo un poco más de espacio que una de las ROM individuales.

Algunas preocupaciones a considerar al pensar en posibles enfoques:

• Las ROM varían mucho en tamaño, según el sistema.Algunos son pequeños, pero los sistemas modernos pueden tener otros grandes, de 256 MB o más.Algunos (¿todos?) sistemas solo tienen potencias de 2 tamaños posibles, un juego de 130 MB en uno de estos sistemas tendría una rom de 256 MB, prácticamente 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 del doble de tamaño.
• Actualmente hay miles de ROM conocidas en muchos sistemas, y la mayoría de los sistemas todavía lanzan nuevas constantemente.Incluso para los sistemas más antiguos, existe una importante comunidad de piratería de ROM que produce ROM modificadas con frecuencia.
• Almacenar datos de similitud para cada par posible 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, y un solo juego nuevo agregaría otras 5000 filas.
• El estado del procesamiento debe ser recuperable, de modo que si se interrumpe pueda continuar donde lo dejó.Con cualquier método, se requerirá mucho procesamiento y asumir que todo se ejecutará en un solo lote no es seguro.
• Se pueden agregar nuevas ROM en cualquier momento, por lo que el método no debe asumir que ya tiene un conjunto "completo".Es decir, incluso después de haber descubierto la similitud de todas las ROM existentes, si se agrega una nueva (y esto también podría ocurrir antes de que el procesamiento anterior haya terminado por completo), debe haber un método para compararla con todas las anteriores, para determinar del cual (si lo hay) es un clon.
• Se debe dar prioridad a una mayor velocidad de procesamiento sobre la precisión (hasta cierto punto).Saber si dos ROM son similares en un 94% o un 96% no es particularmente importante, pero si se necesita un día de procesamiento para comparar una nueva ROM con todas las anteriores, el programa probablemente nunca se completará del todo.

Ha sido un problema interesante en el que trabajar, espero ver qué se les ocurre a otras personas.Déjame saber en los comentarios si quieres más detalles e intentaré proporcionártelos.

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 en cierta línea de base que se determina experimentalmente para decidir si se trata de 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.

Una vez dicho esto, la comparación por pares de cada archivo binario en su base de datos es probablemente prohibitivamente caro (O (n ² ), creo). Me gustaría tratar de encontrar un hash simple para identificar posibles candidatos para la comparación. Algo similar a lo que conceptualmente spdenne y Eduard están sugiriendo. Es decir, encontrar un hash que se puede aplicar a cada artículo una vez, ordenar la lista y luego usar una comparación de grano más fino en artículos cuyos valores hash están cercanos en la lista.

La construcción de hashes útiles para el caso general ha sido un tema de investigación perseguido activamente en CS durante varios años. El href="http://lshkit.sourceforge.net/" rel="noreferrer"> LSHKit biblioteca de software la búsqueda de archivos similares en el gran sistema de archivos parece que podría estar dirigida más en archivos de texto que comparan, pero podría ser útil para usted. El documento más reciente Multi-resolución similitud hash describe un algoritmo más potente. No parece que sea accesible sin una suscripción, sin embargo. Es posible que desee mantener el artículo de Wikipedia sobre Localidad Sensible Hashing mano cada vez que navega por los demás recursos. Todos ellos se ponen muy técnica y la entrada de Wikipedia en sí es bastante pesado matemáticas. Como una alternativa más fácil de usar que podría ser capaz de aplicar algunas ideas (o incluso archivos ejecutables) desde el campo de la acústica toma de huellas dactilares.

Si usted está 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 implica 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 acerca de su formato binario, pero me estoy imaginando cosas que señalan el inicio de las secciones en el archivo como regiones de sonido, imágenes o texto. formatos binarios con frecuencia almacenan las direcciones de este tipo de secciones cerca del principio del archivo. Algunos también utilizan un mecanismo de encadenamiento que almacena la dirección de la primera sección en un lugar conocido, junto con su tamaño. Esto le permite pasar a la siguiente sección, que también contiene un tamaño, etc. Un poco de investigación, probablemente, le permitirá descubrir cualquier formato relevante, si no está ya consciente de ello, y debe colocar bien en su camino a la construcción un hash útil.

Si las funciones de hash no lo hace llegar hasta el final (o que requieren la introducción de algún tipo para definir una métrica / distancia) entonces hay varios algoritmos de diferencias de código binario y las implementaciones disponibles en la web. El que estoy más familiarizado es utilizado por el sistema de control de versiones Subversion. Utiliza un algoritmo de diferencias de código binario llamado xdelta para almacenar de manera eficiente las revisiones de archivos binarios. Aquí hay un enlace directo al archivo en su repositorio que lo implementa: xdelta .c. Probablemente hay una herramienta en la web que haceesto más accesible también.

Answer 2

Es posible que desee ver en bsdiff , que es un sistema binario diffing / parches. También hay una tesis con una gran cantidad de teoría.

Answer 3

Utilice algunas ideas a partir de algoritmos plagio de detección .

Mi idea:

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

No se limite a hash de una sección, a continuación, la siguiente sección a partir del final de la primera sección, pero en lugar de utilizar una ventana deslizante, hashing la sección que comienza a partir del byte 1, entonces hash de la misma sección de tamaño a partir del byte 2, luego de byte 3, etc. que va a anular el efecto de porciones diferentes de tamaño variable dentro de su ROM.

Si ha utilizado una función hash simple como XOR de cada byte de 8 bits, por lo que se puede calcular fácilmente el hash de la siguiente posición del cristal a xor el hash actual con los salientes 8 bits, y los entrantes xor 8 bits. Otra función hash alternativa puede ser simplemente utilizar la longitud del código de instrucciones palabra. Eso puede ser suficiente para crear patrones estáticos para los códigos que representan instrucciones de la máquina. Lo importante es que usted querrá una función hash que se traduce en secuencias cortas comunes en el código de instrucción que resulta en 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 ir demasiado amplia, o tendrá que tener un montón de frecuencias muy pequeñas, haciendo la comparación duro de nuevo.

Guarde este gráfico por ROM. Comparar las gráficas de frecuencias para las dos ROMs diferentes mediante el cálculo de la suma de los cuadrados de la diferencia de frecuencias para cada valor hash. Si que resume a cero, entonces las ROMs es probable que sean idénticas. Cuanto más lejos de cero que es, los menos similares los ROMs serán.

Answer 4

A pesar de que ha sido mucho más que "un par de días", pensé que probablemente debería añadir 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 archivado sólida, pensé que sólo podría intentar comprimir las dos ROMs juntos y ver cuánto espacio se salvó. Estoy utilizando el algoritmo LZMA en 7zip para esto.

El primer paso es el de comprimir cada ROM de forma individual y tenga en cuenta el tamaño comprimido, a continuación, intente archivar las dos ROMs juntos y ver hasta qué punto el tamaño resultante difiere de sus tamaños comprimidos individuales. Si el tamaño combinado es el mismo que la suma de los tamaños individuales, son 0% similar, y si el tamaño es el mismo que uno de ellos (el más grande), que son idénticos.

Ahora, esto es un gran número de intentos de compresión requerida, así que tengo un par de optimizaciones hasta el momento (y me gustaría averiguar más):

1. Dar prioridad a las comparaciones basadas en la similitud de los tamaños son comprimidas. Si ROM A tiene un tamaño comprimido de 10 MB y ROM B tiene un tamaño comprimido de 2 MB, es imposible que puedan ser más de un 20% similar, por lo que la comparación de ellos para obtener el resultado real puede dejarse para más tarde. Que ejecuta el mismo algoritmo de compresión de archivos altamente similares tiende a producir resultados similares de tamaño, por lo que este se encuentra una gran cantidad de los clones muy rápidamente.

2. En combinación con lo anterior, mantener ambos "límites" superior e inferior sobre la posible similitud entre cualquier par de ROMs. Esto permite que más de priorización. Si ROMs A y B son 95% similar, y la ROM B y C son sólo el 2% similar, entonces usted ya sabe que A y C son entre el 0% y el 7%. Esto es demasiado bajo para ser un clon, por lo que esta comparación puede ser pospuesta de forma segura o incluso ignorado por completo, a menos que realmente quiero saber las similitudes exactas de todo.

Answer 5

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. A continuación, concatenar los dos archivos en un solo archivo, grande y comprimirlo así.

La diferencia en los tamaños le dará una estimación aproximada cuán similares son los archivos.

Le sugiero que pruebe la Transformación Madriguera Wheeler (bzip2) para hacer la compresión. La mayoría de los otros algoritmos de compresión sólo tienen un historial limitado. El algoritmo BWT Otoh puede trabajar en muy grandes cantidades de datos. El algoritmo "ve" los dos archivos al mismo tiempo y cualquier similitud se traducirá en una mayor relación de compresión.

Answer 6

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

Answer 7

Puede iniciar mediante el almacenamiento de algo así como hash árboles . Sólo se necesita para almacenar una de tales conjunto de hashes para cada ROM, y el espacio de almacenamiento requerido es únicamente proporcional a (pero mucho menor que) el tamaño de la ROM, suponiendo que el tamaño de bloque constante. El tamaño de bloque elegido debe dar suficiente granularidad para asegurar la exactitud, por ejemplo: para un tamaño mínimo de 128MiB, restricción de exactitud de 1% y Tiger-128 almohadilla (similar a lo que utilizan para comprobar los archivos transferidos a través de DirectConnect), un tamaño de bloque de 1MiB hace bien y puede almacenar todos los valores hash de 128 * 128/8 = 2048 bytes! Así lo hace por 10.000 ROMs requieren sólo sobre 20MiB del espacio. Además, se puede elegir un hash menos seguro, pero más rápido y / o más pequeños. Adición / comprobación de similitud una nueva ROM implicaría algo como:

1. Dividir la nueva ROM en bloques y croquetas de cada uno de ellos.
2. Para cada ROM que ya están en la base de datos, comparar (véase más adelante) con sus hashes de hashes de la nueva ROM.

La función de comparación debe comprobar si hay similitud. Pero debe tratar a cada uno de hash como un valor indivisible, es decir, no se moleste en tratar de encontrar una función de diferencia significativa entre los dos lógicamente hashes. Mientras el tamaño de bloque es lo suficientemente bajo y colisiones hash son lo suficientemente rara, la precisión está garantizada por una simple es-igual comparación.

Como se ve, el problema se reduce a una más simple en cuanto al rendimiento:. Conjuntos de datos mucho más pequeñas comprobación de similitud

Answer 8

Dos pensamientos:

• Considere organizar el archivo como un gráfico de flujo de datos y haciendo algunas canónicos en que represention. Dado que se conoce el conjunto de instrucciones, esto puede ser factible, tal vez sólo los flejes de hasta 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 cierta idea de si los binarios tienen mucho en común.

Answer 9

Como dijo Waylon Flinn, es posible que necesite un algoritmo de diferencias de código binario. El rsync algoritmo es una buena. Es rápido y fiable. Véase también el .

Answer 10

La dificultad aquí es que, dado que se trata de código ejecutable, cambios simples pueden propagarse por toda la ROM.Las direcciones y compensaciones de TODOS los valores pueden cambiar con la adición de una sola variable o instrucción no operativa.Eso hará que incluso el hash basado en bloques sea inútil.

Una solución rápida y sucia sería idear una solución con difflib (o el equivalente con su idioma favorito), ya que le brinda una comparación deslizante que puede abordar la adición o eliminación de datos.Divida la ROM en secciones ejecutables y de datos (si es posible).La sección de datos se puede comparar directamente y relación de similitud calculada, aunque seguirás teniendo problemas con direcciones o compensaciones.

La sección ejecutable es más interesante.Lea sobre el formato 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 de "carga útil"/"inmediata" (donde carga las direcciones variables).Entregue también la información resultante a la calculadora de índice de similitud.

Lo desafortunado es que esto sigue siendo una operación O(n^2) en la cantidad de ROM que rastrea, pero eso se puede aliviar con agrupación (incremental) o un orden de comparación basado en frecuencia para reducir la cantidad de comparaciones necesarias.