Calcul des données binaires similarité

StackOverflow https://stackoverflow.com/questions/579981

Question

Je l'ai vu quelques questions ici liées à la détermination de la similitude des fichiers, mais ils sont tous liés à un domaine particulier (images, sons, textes, etc.). Les techniques proposées comme solutions exigent la connaissance du format de fichier sous-jacent des fichiers comparées. Ce que je cherche est une méthode sans cette exigence, où les fichiers binaires arbitraires peuvent être comparés sans avoir besoin de comprendre quel type de données qu'ils contiennent. C'est, je cherche à déterminer le pourcentage de similarité de deux fichiers de données binaires .

Pour donner un peu plus en détail pour vous de travailler avec, même si cela est potentiellement applicable à beaucoup de choses, j'ai un problème spécifique que je travaille. J'ai actuellement aussi une solution de travail, mais je ne pense pas qu'il est idéal. Il y a probablement de nombreuses optimisations en termes de la méthode de comparaison, et le stockage des résultats. ici Espérons que certaines personnes seront en mesure de me donner quelques idées nouvelles. Je vais probablement modifier quelques informations au sujet de ma méthode actuelle après quelques jours, mais je ne veux pas les pensées des peuples de biais sur le problème en vous disant ce que je fais déjà.

Le problème que je travaille sur détection de clone pour les images ROM de jeux vidéo . Pour ceux qui n'ont pas d'expérience avec l'émulation, ROM sont des décharges des données sur les cartouches de jeu. Une ROM « clone » est généralement une version modifiée du même jeu, le type le plus commun étant une version traduite. Par exemple, les versions japonaise et anglaise de l'original Final Fantasy pour la NES sont des clones. Les jeux partagent la quasi-totalité de leurs actifs (sprites, musique, etc.), mais le texte a été traduit.

Il existe actuellement plusieurs groupes qui travaillent sur le maintien des listes de clones pour les différents systèmes, mais pour autant que je peux dire, tout cela est fait manuellement. Ce que je tente de faire est de trouver une méthode pour détecter les images ROM similaires automatiquement et objectivement, sur la base de la similitude des données au lieu de « ceux-ci semblent comme le même jeu ». Il y a plusieurs raisons pour la détection des clones, mais l'une des motivations principales doit être utilisé avec une compression solide . Cela permet la compression de tous les clones de jeu ensemble dans la même archive, avec le clone complet est compressé mis en prenant souvent seulement un peu plus d'espace que l'un des ROM individuels.

Certaines préoccupations à considérer lors de venir avec des approches possibles:

  • ROM varient fortement en taille, en fonction du système. Certains sont petits, mais les systèmes modernes peuvent avoir grandes, 256 Mo ou plus. Certains (tous?) Les systèmes ne sont des puissances de 2 tailles possibles, comme un jeu de 130Mo sur un de ces systèmes aurait une rom, 256MB en grande partie vide. Notez que pour cette raison, certains clones peuvent avoir des tailles très différentes, si une version du jeu franchit le seuil et doit utiliser une cartouche qui est deux fois la taille.
  • Il y a actuellement des milliers de ROM connus sur de nombreux systèmes, avec la plupart des systèmes ayant encore de nouveaux libérés en permanence. Même pour les systèmes plus anciens, il y a une importante communauté de piratage ROM qui produit souvent modifiés ROM.
  • Le stockage des données de similarité pour chaque paire possible de ROM entraînerait des millions de lignes de données pour l'un des systèmes les plus populaires. Un système avec 5000 ROM, il faudrait 25 millions de lignes de données de similarité, avec un seul nouveau jeu en ajoutant un autre 5000 lignes.
  • État du traitement doit être recouvrable, de sorte que si elle est interrompue, il peut ramasser où il l'avait laissé. Avec toute méthode, beaucoup de traitement sera nécessaire, et en supposant que le tout se déroulera en un seul lot n'est pas sûr.
  • De nouvelles ROM peuvent être ajoutés à tout moment, la méthode ne doit pas supposer qu'il a déjà un ensemble « complet ». Autrement dit, même après que vous avez déjà compris similitude pour tous les ROM existants, si un nouveau est ajouté (et cela pourrait également se produire avant précédenteLe traitement a été entièrement terminée) il doit y avoir une méthode pour comparer à tous les précédents, afin de déterminer quels (le cas échéant) est un clone de.
  • Une vitesse plus élevée de traitement doit être la priorité sur la précision (à un point). Savoir si deux ROM sont 94% ou 96% similaires ne sont pas particulièrement important, mais si elle prend un jour de traitement pour comparer une nouvelle ROM pour toutes les précédentes, le programme serait sans doute jamais vraiment complet.

Il a été un problème intéressant de travailler, je suis impatient de voir ce que les autres peuvent venir avec. Faites-moi savoir dans les commentaires si vous voulez plus de détails, et je vais essayer de les fournir.

Était-ce utile?

La solution

On dirait que vous voulez un delta binaire ou peut-être un indice dérivé de l'application d'un delta binaire (comme sa taille). Vous pouvez ensuite comparer cet indice à une base que vous déterminer expérimentalement pour décider si elle est un « clone » ou non.

Il y a beaucoup de similitudes entre la compression et à la création de delta, donc je dirais que vous n'êtes pas loin avec votre implémentation actuelle.

Cela étant dit, la comparaison par paires de chaque fichier binaire dans votre base de données est probablement prohibitif (O (n 2 ), je pense). Je voudrais essayer de trouver un hachage simple pour identifier les candidats possibles aux fins de comparaison. Quelque chose sur le plan conceptuel semblable à ce que spdenne et Eduard suggérez. Autrement dit, trouver un hachage qui peut être appliqué à chaque élément une fois, trier cette liste, puis utiliser une comparaison à grain plus fin sur les éléments dont hash sont proches dans la liste.

Construire hash utiles pour le cas général a été un sujet de recherche menée activement à CS depuis plusieurs années. La bibliothèque logicielle LSHKit implémente des algorithmes de ce genre. Internet accessible papier Recherche de fichiers SIMILAIRES DANS UN SYSTÈME GRAND FICHIER semble que cela pourrait être ciblé plus à comparer les fichiers texte, mais peut être utile pour vous. Le article plus récent hash de similarité multi-résolution décrit un algorithme plus puissant. Il ne semble pas être accessible sans abonnement, cependant. Vous voulez sans doute de garder l'article wikipedia sur pratique que vous naviguez sur les autres ressources. Ils reçoivent tous assez technique et l'entrée de wikipedia lui-même est assez lourd de mathématiques. Comme une alternative plus conviviale que vous pourriez être en mesure d'appliquer quelques idées (ou même) executables du champ de acoustique Fingerprinting.

Si vous êtes prêt à abandonner le cas général, il est probable que vous pouvez trouver beaucoup plus simple (et plus rapide) fonction de hachage domaine spécifique qui fonctionne pour vos ROM. Peut-être quelque chose qui implique la mise en place de standards, ou communes, des séquences d'octets et la valeur des bits de sélection près d'eux. Je ne sais pas vraiment beaucoup au sujet de votre format binaire, mais je me fais des choses qui signalent le début des sections dans le fichier comme régions de son, des images ou du texte. Les formats binaires stockent souvent les adresses de ces sortes de sections près du début du fichier. Certains utilisent également un mécanisme qui stocke de chaînage l'adresse de la première section à un endroit connu avec sa taille. Cela vous permet de passer à la section suivante, qui contient également une taille, etc. Une petite enquête vous permettra sans doute de découvrir toute mise en forme pertinente, si vous n'êtes pas déjà au courant, et devrait vous mettre sur votre chemin à la construction un hachage utile.

Si les fonctions de hachage ne vous obtenez pas tout le chemin (ou dont ils ont besoin d'une sorte d'entrée pour définir une distance métrique /) puis il y a plusieurs algorithmes delta binaires et implémentations disponibles sur le web. Celui que je suis plus familier est utilisé par le système de contrôle de version de subversion. Il utilise un algorithme delta binaire appelé xdelta pour stocker efficacement des révisions de fichiers binaires. Voici un lien direct vers le fichier dans leur répertoire qui l'implémente: xdelta .c. Il y a probablement un outil sur le web qui faitcela plus accessible.

Autres conseils

Vous pouvez regarder bsdiff , qui est un diffing binaire / système rapiéçage. Il y a aussi une thèse avec beaucoup de théorie.

Utilisez quelques idées à partir des algorithmes de Plagiat détection.

Mon idée:

Afin de créer une « signature » comparable pour chaque ROM, qui varie légèrement de petites portions changent, produisent quelque chose comme un graphique de la fréquence des mots, mais au lieu d'enregistrer les fréquences des mots, vous pourriez hachage sections très courtes de la ROM et enregistrer les fréquences des valeurs de hachage.

Il ne suffit pas hacher une section, la section suivante à partir de la fin de la première section, mais au lieu d'utiliser une fenêtre glissante, le hachage de la section à partir de l'octet 1, puis hacher la section de même taille à partir de l'octet 2, puis à partir de l'octet 3, etc. Cela annulera l'effet de taille variable des portions variant au sein de votre ROM.

Si vous avez utilisé une simple fonction de hachage comme XOR de chaque octet 8 bits, de sorte que vous pouvez facilement calculer le hachage de la position suivante de la fenêtre par XOR le hachage en cours avec les 8 bits sortants et XOR les 8 bits entrants. Une autre fonction de hachage alternative peut être simplement d'utiliser la longueur du code instruction de mot. Cela peut être suffisant pour créer des motifs statiques pour les codes représentant les instructions de la machine. La chose importante est que vous voulez une fonction de hachage qui se traduit par de courtes séquences communes dans le code d'instruction résultant dans les mêmes valeurs de hachage.

Vous voudriez probablement moins de valeurs de hachage avec des fréquences plus élevées de chacun, mais ne pas aller trop loin ou votre graphique sera trop plat, ce qui en difficulté de les comparer. De même ne vont pas trop large, ou vous aurez beaucoup de fréquences très faibles, ce qui rend difficile la comparaison à nouveau.

Entreposez ce graphique par ROM. Comparer les graphiques de fréquences pour les deux ROM différentes en calculant la somme des carrés de la différence de fréquences pour chaque valeur de hachage. Si cette sommes à zéro alors les ROM sont susceptibles d'être identiques. Le plus loin de zéro, il est, moins semblables les ROM seront.

Bien qu'il a été beaucoup plus que « quelques jours », je pensais que je devrais probablement ajouter ma solution actuelle ici.

Nils Pipenbrinck allait dans le même sens que ma méthode actuelle. Étant donné que l'un des principaux résultats de la recherche clones est d'énormes économies d'archivage solide, je me suis dit que je pouvais juste essayer compresser les deux ROM ensemble et de voir la quantité d'espace a été enregistré. J'utilise l'algorithme LZMA 7zip pour cela.

La première étape consiste à compresser chaque ROM individuellement et notez la taille compressée, essayez d'archiver tous les deux ensemble ROM et de voir à quel point la taille résultante diffère de leur taille comprimés individuels. Si la taille combinée est la même que la somme des dimensions individuelles, ils sont 0% similaires, et si la taille est la même que l'un d'entre eux (le plus grand), ils sont identiques.

Maintenant, c'est un grand nombre de tentatives de compression nécessaire, donc je jusqu'à présent quelques optimisations (et voudrais savoir plus):

  1. Prioriser comparaisons basées sur la similitude des tailles compressées sont. Si ROM A a une taille compressée de 10 Mo et ROM B a une taille compressée de 2 Mo, il est impossible pour eux d'être plus de 20% similaires, afin de les comparer pour obtenir le résultat réel peut être à plus tard. Exécution du même algorithme de compression des fichiers très similaires a tendance à entraîner des résultats taille similaire, donc cela trouve un grand nombre de clones très rapidement.

  2. En combinaison avec ce qui précède, garder les deux « bornes » supérieure et inférieure sur la similitude possible entre toute paire de ROM. Cela permet en outre d'établir des priorités. Si ROM A et B sont similaires à 95%, et ROM B et C ne sont que 2% similaires, alors vous savez déjà que A et C sont comprises entre 0% et 7%. Ceci est trop faible pour être un clone, de sorte que cette comparaison peut être reportée en toute sécurité ou même totalement ignoré, à moins que je veux vraiment connaître les similitudes exactes de tout.

Je pense que certaines des techniques empruntées à la compression des données pourrait être intéressant ici:

Supposons que vous avez deux fichiers, A et B.

Compresser chaque fichier individuellement et ajouter les tailles compressées ensemble. Puis concaténer les deux fichiers en un seul gros fichier et compresser ainsi.

La différence dans les tailles vous donnera une estimation approximative comment les fichiers sont similaires.

Je vous suggère d'essayer la transformation Wheeler Burrow (bzip2) pour faire la compression. La plupart des autres algorithmes de compression ont seulement une histoire limitée. L'algorithme de BWT Otoh peut travailler sur de très grandes quantités de données. L'algorithme « voit » les deux fichiers en même temps et toute ressemblance se traduira par un taux de compression plus élevé.

xdelta est très utile pour obtenir diffs binaires décent: http://xdelta.org

Vous pouvez commencer par stocker quelque chose comme

Deux pensées:

Waylon Flinn a dit, vous devrez peut-être un algorithme delta binaire. rsync algorithme est un bon. Il est rapide et fiable. Voir aussi la .

La difficulté ici est que, puisque vous traitez avec le code exécutable, des changements simples peuvent se propager à travers le ROM entier. Les adresses et les décalages pour toutes les valeurs peuvent changer avec l'ajout d'une seule variable ou non-op instruction. Cela fera sans valeur de hachage même par blocs.

Une solution rapide et sale serait de pirater une solution difflib (ou l'équivalent w / votre langue préférée), car il vous obtient une comparaison coulissante qui peut traiter plus de données ou la suppression. Diviser la ROM en sections exécutables et données (si possible). La section de données peuvent être comparées directement et un rapport de similarité calculée , bien que vous » ll ont encore des problèmes w / adresses ou des décalages.

La section exécutable est plus intéressant. Renseignez-vous sur le format asm de la machine, prendre l'exécutable et le diviser en une séquence de opcodes. Laissez le opcode et enregistrer des parties, mais masquez les parties « charge utile » / « immédiates » (où il charge les adresses variables). Distribuez les informations résultant au calculateur de taux de similarité trop.

L'opération partie malheureuse est que cela reste un O (n ^ 2) sur le nombre de ROMs vous voie, mais qui peut être atténué par le regroupement (incrémental) ou un ordre de comparaison basée sur la fréquence pour réduire la quantité de comparaisons nécessaire.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top