comparison - sistema - Cálculo de similitud de datos binarios

sistema octal (10)

Creo que algunas técnicas tomadas de la compresión de datos podrían ser interesantes aquí:

Supongamos que tiene dos archivos, A y B.

Comprima cada archivo individualmente y agregue los tamaños comprimidos. 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 cuán similares son los archivos.

Sugiero que pruebes 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.

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 sea 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 la detección de clones para imágenes ROM de videojuegos . 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 Final Fantasy original 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 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 compresión sólida . 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 preocupaciones a considerar cuando se presentan enfoques potenciales:

Las ROM varían mucho en tamaño, según el 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 todavía tienen nuevas ROM lanzadas constantemente. Incluso para sistemas más antiguos, existe una gran comunidad de hackers ROM que produce ROM modificados a menudo.
Almacenar 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 reanudarse 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.
Se debe dar prioridad a una mayor velocidad de procesamiento sobre la precisión (a un 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 para trabajar, espero ver lo que otras personas pueden pensar. Déjame saber en los comentarios si quieres más detalles, y trataré de proporcionarlos.

Dos pensamientos:

Considere organizar el archivo como un gráfico de flujo de datos y realizar una canonización en esa representación. 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 binarios tienen mucho en común.

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

Puedes comenzar almacenando algo como árboles hash . 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 hash Tiger-128 (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:

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

La función de comparación debe verificar la similitud. Pero debería 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 hash. 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 puede ver, 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 similitud.

Aunque ha pasado mucho más que "un par de días", pensé 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 anotar 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, esta es una gran cantidad de intentos de compresión necesarios, así que tengo un par de optimizaciones hasta ahora (y me gustaría saber más):

Priorice las comparaciones según cuán similares sean los tamaños comprimidos. 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 generar resultados de tamaño similar, por lo que encuentra muchos clones muy rápidamente.
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.

Use algunas ideas de los algoritmos de detección de plagio .

Mi idea:

Para crear una "firma" comparable para cada ROM, que varía ligeramente a medida que cambian las porciones pequeñas, se produce algo así como un gráfico de frecuencia de palabras, pero en lugar de registrar las frecuencias de las palabras, se pueden cortar secciones muy cortas de la ROM y grabar 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 que usa una ventana deslizante, mezclando la sección comenzando desde el byte 1, luego hash la misma sección de tamaño comenzando desde el byte 2, luego desde byte 3, etc. Eso negará 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 xo el hash actual con los 8 bits salientes, y xo 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ás una función hash que dé como resultado secuencias cortas comunes en el código de instrucción que den como resultado los mismos valores hash.

Es probable que desee menos valores de hash con frecuencias más altas de cada uno, pero no vaya demasiado lejos o su gráfico será demasiado plano, lo que resulta en una dificultad 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.

Almacene este gráfico por ROM. Compara 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.

Como dijo Waylon Flinn, es posible que necesite un algoritmo binario delta. El algoritmo de rsync es bueno. Es rápido y confiable. Ver también la documentación de la utilidad .

La dificultad aquí es que, dado que se trata de un código ejecutable, se pueden propagar cambios simples en toda la ROM. Las direcciones y desplazamientos 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 piratear una solución con difflib (o el equivalente con su idioma favorito), ya que le ofrece una comparación deslizante que puede manejar 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 se puede calcular un índice de similitud , 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 la cantidad 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.

XDelta es bastante útil para obtener diferencias binarias decentes: http://xdelta.org

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

Hay muchas similitudes entre la compresión y la creación delta, por lo que diría que no está lejos con su implementació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 hashes están muy juntos en la lista.

La construcción de hashes útiles para el caso general ha sido un tema de investigación activamente perseguido en CS durante varios años. La biblioteca de software LSHKit implementa algunos algoritmos de este tipo. El documento accesible en Internet ENCUENTRE ARCHIVOS SIMILARES EN UN SISTEMA DE ARCHIVOS GRANDES 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 de similitud de resolución múltiple hashing describe un algoritmo más poderoso. Sin embargo, no parece ser accesible sin una suscripción. Probablemente desee tener a mano el artículo de wikipedia sobre Locality Sensitive Hashing mientras explora los otros recursos. Todos se vuelven bastante técnicos y la entrada de la wikipedia en sí es bastante pesada. Como una alternativa más fácil de usar, es posible que pueda aplicar algunas ideas (o incluso ejecutables) desde el campo de la huella digital acústica .

Si está dispuesto a abandonar el caso general, es probable que pueda encontrar una función hash específica del dominio mucho más simple (y más rápida) que funcione solo para sus ROM. 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 una especie de entrada 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.