Berechnung der Ähnlichkeit binärer Daten

https://stackoverflow.com/questions/579981

06-09-2019
|

Frage

Ich habe hier ein paar Fragen zur Bestimmung der Ähnlichkeit von Dateien gesehen, aber sie sind alle mit einer bestimmten Domäne verknüpft (Bilder, Töne, Text usw.).Die als Lösungen angebotenen Techniken erfordern Kenntnisse über das zugrunde liegende Dateiformat der verglichenen Dateien.Was ich suche, ist eine Methode ohne diese Anforderung, mit der beliebige Binärdateien verglichen werden können, ohne dass man verstehen muss, welche Art von Daten sie enthalten.Das heißt, ich möchte das bestimmen Ähnlichkeitsprozentsatz der Binärdaten zweier Dateien.

Um Ihnen etwas mehr Details zu geben, mit denen Sie arbeiten können: Auch wenn dies möglicherweise auf viele Dinge anwendbar ist, habe ich ein spezifisches Problem, an dem ich arbeite.Ich habe derzeit auch eine funktionierende Lösung, aber ich denke nicht, dass sie ideal ist.Es gibt wahrscheinlich viele Optimierungen hinsichtlich der Vergleichsmethode und der Speicherung der Ergebnisse.Hoffentlich können mir einige Leute hier neue Ideen geben.Ich werde wahrscheinlich nach ein paar Tagen einige Informationen zu meiner aktuellen Methode hinzufügen, aber ich möchte die Meinung der Leute über das Problem nicht beeinflussen, indem ich Ihnen erzähle, wie ich es bereits mache.

Das Problem, an dem ich arbeite, ist Klonerkennung für Videospiel-ROM-Images.Für diejenigen, die keine Erfahrung mit Emulation haben: ROMs sind Dumps der Daten auf Spielekassetten.Ein ROM-„Klon“ ist typischerweise eine modifizierte Version desselben Spiels, wobei die häufigste Art eine übersetzte Version ist.Zum Beispiel die japanische und die englische Version des Originals Final Fantasy denn das NES sind Klone.Die Spiele teilen fast alle ihre Vorzüge (Sprites, Musik usw.), aber der Text wurde übersetzt.

Derzeit gibt es mehrere Gruppen, die an der Pflege von Klonlisten für die verschiedenen Systeme arbeiten, aber soweit ich das beurteilen kann, wird dies alles manuell erledigt.Ich versuche, eine Methode zu finden, um ähnliche ROM-Bilder automatisch und objektiv zu erkennen, basierend auf Datenähnlichkeit statt „diese scheinen das gleiche Spiel zu sein“.Es gibt mehrere Gründe für die Erkennung von Klonen, aber einer der Hauptgründe ist die Verwendung mit Solide Kompression.Dies ermöglicht die Komprimierung aller Spieleklone zusammen in das gleiche Archiv, wobei der gesamte komprimierte Klonsatz oft nur geringfügig mehr Platz einnimmt als eines der einzelnen ROMs.

Einige Bedenken, die bei der Entwicklung möglicher Ansätze berücksichtigt werden sollten:

Je nach System variieren die ROMs stark in der Größe.Einige sind klein, aber moderne Systeme verfügen möglicherweise über große, 256 MB oder mehr.Einige (alle?) Systeme haben nur Potenzen von 2 möglichen Größen, ein 130-MB-Spiel auf einem dieser Systeme hätte ein 256-MB-ROM, das weitgehend leer wäre.Beachten Sie, dass einige Klone aus diesem Grund stark unterschiedliche Größen haben können, wenn eine Spielversion den Schwellenwert überschreitet und eine Kassette verwenden muss, die doppelt so groß ist.
Derzeit gibt es auf vielen Systemen Tausende bekannter ROMs, wobei auf den meisten Systemen immer noch ständig neue veröffentlicht werden.Selbst für ältere Systeme gibt es eine große ROM-Hacker-Community, die häufig modifizierte ROMs erstellt.
Das Speichern von Ähnlichkeitsdaten für jedes mögliche ROM-Paar würde bei jedem der gängigeren Systeme zu Millionen von Datenzeilen führen.Ein System mit 5000 ROMs würde 25 Millionen Zeilen mit Ähnlichkeitsdaten erfordern, wobei ein einzelnes neues Spiel weitere 5000 Zeilen hinzufügt.
Der Verarbeitungszustand muss wiederhergestellt werden können, sodass er bei einer Unterbrechung dort fortgesetzt werden kann, wo er aufgehört hat.Bei jeder Methode ist ein großer Verarbeitungsaufwand erforderlich, und die Annahme, dass das Ganze in einem Stapel ausgeführt wird, ist nicht sicher.
Neue ROMs könnten jederzeit hinzugefügt werden, daher sollte die Methode nicht davon ausgehen, dass sie bereits über einen „vollständigen“ Satz verfügt.Das heißt, selbst nachdem Sie bereits die Ähnlichkeit aller vorhandenen ROMs herausgefunden haben, muss es eine Methode zum Vergleichen mit allen vorherigen geben, um festzustellen, ob ein neues hinzugefügt wird (und dies kann auch geschehen, bevor die vorherige Verarbeitung vollständig abgeschlossen ist). von dem es (falls vorhanden) ein Klon ist.
Einer höheren Verarbeitungsgeschwindigkeit sollte (bis zu einem gewissen Punkt) Vorrang vor der Genauigkeit eingeräumt werden.Zu wissen, ob zwei ROMs zu 94 % oder 96 % ähnlich sind, ist nicht besonders wichtig, aber wenn die Verarbeitung einen Tag dauert, um ein neues ROM mit allen vorherigen zu vergleichen, würde das Programm wahrscheinlich nie wirklich fertig werden.

Es war ein interessantes Problem, an dem man arbeiten konnte. Ich freue mich darauf zu sehen, was andere Leute sich einfallen lassen können.Lassen Sie es mich in den Kommentaren wissen, wenn Sie weitere Details wünschen, und ich werde versuchen, diese bereitzustellen.

Lösung

Es hört sich so an, als ob Sie ein binäres Delta oder vielleicht einen Index wünschen, der aus der Anwendung eines binären Deltas abgeleitet wird (z. B. seine Größe).Anschließend können Sie diesen Index mit einer experimentell ermittelten Basislinie vergleichen, um zu entscheiden, ob es sich um einen „Klon“ handelt oder nicht.

Es gibt viele Ähnlichkeiten zwischen Komprimierung und Delta-Erstellung, daher würde ich sagen, dass Sie mit Ihrer aktuellen Implementierung nicht weit davon entfernt sind.

Allerdings ist der paarweise Vergleich jeder Binärdatei in Ihrer Datenbank wahrscheinlich unerschwinglich teuer (O(n).²), Ich finde).Ich würde versuchen, einen einfachen Hash zu finden, um mögliche Kandidaten für den Vergleich zu identifizieren.Etwas, das konzeptionell dem ähnelt, was Spdenne und Eduard vorschlagen.Suchen Sie also einen Hash, der auf jedes Element einmal angewendet werden kann, sortieren Sie diese Liste und verwenden Sie dann einen feinkörnigeren Vergleich für Elemente, deren Hashes in der Liste nahe beieinander liegen.

Die Konstruktion von Hashes, die für den allgemeinen Fall nützlich sind, ist seit mehreren Jahren ein aktiv verfolgtes Forschungsthema in CS.Der LSHKit Die Softwarebibliothek implementiert einige Algorithmen dieser Art.Das über das Internet zugängliche Papier FINDEN SIE ÄHNLICHE DATEIEN IN EINEM GROSSEN DATEISYSTEM Es scheint, als wäre es eher auf den Vergleich von Textdateien ausgerichtet, könnte aber für Sie nützlich sein.Das neuere Papier Ähnlichkeits-Hashing mit mehreren Auflösungen beschreibt einen leistungsfähigeren Algorithmus.Ohne Abonnement scheint es jedoch nicht zugänglich zu sein.Wahrscheinlich möchten Sie den Wikipedia-Artikel beibehalten Lokalitätssensitives Hashing praktisch, wenn Sie die anderen Ressourcen durchsuchen.Sie werden alle ziemlich technisch und der Wikipedia-Eintrag selbst ist ziemlich mathematisch.Als benutzerfreundlichere Alternative können Sie möglicherweise einige Ideen (oder sogar ausführbare Dateien) aus dem Bereich anwenden Akustischer Fingerabdruck.

Wenn Sie bereit sind, den allgemeinen Fall aufzugeben, finden Sie wahrscheinlich eine viel einfachere (und schnellere) domänenspezifische Hash-Funktion, die nur für Ihre ROMs funktioniert.Möglicherweise geht es um die Platzierung von Standard- oder allgemeinen Bytesequenzen und den Wert von Auswahlbits in deren Nähe.Ich weiß nicht wirklich viel über Ihr Binärformat, aber ich stelle mir Dinge vor, die den Beginn von Abschnitten in der Datei signalisieren, wie Bereiche für Ton, Bilder oder Text.Binärformate speichern die Adressen dieser Art von Abschnitten häufig am Anfang der Datei.Einige verwenden auch einen Verkettungsmechanismus, der die Adresse des ersten Abschnitts zusammen mit seiner Größe an einem bekannten Ort speichert.Dadurch können Sie zum nächsten Abschnitt wechseln, der auch eine Größe usw. enthält.Eine kleine Recherche wird Ihnen wahrscheinlich dabei helfen, alle relevanten Formatierungen zu entdecken, falls Sie sich dieser noch nicht bewusst sind, und sollte Sie auf dem besten Weg zur Erstellung eines nützlichen Hashs bringen.

Wenn Sie mit den Hash-Funktionen nicht ganz weiterkommen (oder sie irgendeine Eingabe erfordern, um eine Metrik/Distanz zu definieren), stehen im Internet mehrere binäre Delta-Algorithmen und -Implementierungen zur Verfügung.Die Variante, mit der ich am besten vertraut bin, wird vom Versionskontrollsystem Subversion verwendet.Es verwendet einen binären Delta-Algorithmus namens xdelta, um Binärdateirevisionen effizient zu speichern.Hier ist ein Link direkt zu der Datei in ihrem Repository, die es implementiert: xdelta.c.Es gibt wahrscheinlich ein Tool im Internet, das dies auch zugänglicher macht.

Andere Tipps

Sie können unter bsdiff aussehen wollen, das ein binäres diffing / Patching-System. Es gibt auch eine Diplomarbeit mit vielen Theorie.

Mit

einige Ideen von Plagiaterkennung Algorithmen.

Meine Idee:

Um eine vergleichbare „Signatur“ für jeden ROM zu schaffen, das leicht variiert als kleine Portionen zu ändern, erzeugen so etwas wie ein Wortfrequenz Graph, aber statt die Frequenzen von Wörtern aufnehmen, könnten Sie Hash sehr kurze Abschnitte des ROM und die Frequenzen der Hash-Werte aufzeichnen.

Nicht nur ein Abschnitt hash, dann wird der nächste Abschnitt von dem Ende des ersten Abschnitts ausgehend, sondern stattdessen ein Schiebefenster verwenden, den Abschnitt von Byte beginnend Hashing 1 ist, dann die gleiche Größe hash Abschnitt von Byte-Ausgangs-2, dann von Byte 3, usw., die den Effekt von variierenden Abschnitten variabler Größe innerhalb Ihres ROM negiert wird.

Wenn Sie eine einfache Hash-Funktion wie xor jedes 8-Bit-Byte verwendet, so dass Sie bequem die Hash-Wert des nächsten Fensterposition durch xor den aktuellen Hash mit den abgehenden 8 Bits berechnen kann und XOR die eingehenden 8 Bit. Eine weitere Alternative Hash-Funktion kann einfach sein, die Befehlscode Wortlänge zu verwenden. Das kann ausreichend sein, statische Muster darstellen Maschinenbefehle für die Codes zu erstellen. Wichtig ist, dass Sie eine Hash-Funktion mögen, die gemeinsam kurze Sequenzen im Befehlscode führt, was zu den gleichen Hash-Werten.

Sie würden wahrscheinlich wenige Hash-Werte mit höheren Frequenzen von jedem wollen, aber gehen Sie nicht zu weit oder Ihr Diagramm wird zu flach sein, was zu Schwierigkeiten, sie zu vergleichen. Ebenso nicht zu weit gehen, oder werden Sie viele sehr kleine Frequenzen haben, Vergleich wieder hart zu machen.

Speichern Sie diese Grafik pro ROM. Vergleichen Frequenzdiagramme für zwei verschiedene ROMs durch die Summe der Quadrate der Differenz-Berechnungs in Frequenzen für jeden Hash-Wert. Wenn das auf Null summiert dann sind die ROMs wahrscheinlich identisch sein. Je weiter weg von Null ist, desto weniger ähnlich die ROMs werden.

Obwohl es viel mehr als „ein paar Tage“ gewesen ist, dachte ich, ich wahrscheinlich hier meine aktuelle Lösung hinzufügen sollte.

Nils Pipenbrinck wurde in der gleichen Richtung wie meine aktuelle Methode gehen. Da eines der wichtigsten Ergebnisse der Klone zu finden, enorme Einsparungen aus dem Vollen Archivierung ist, dachte ich, das könnte ich nur alle zwei ROMs zusammen versuchen komprimieren und zu sehen, wie viel Platz gespart wurde. Ich bin mit dem LZMA-Algorithmus in 7zip für diese.

Der erste Schritt ist es, jedes ROM individuell und notieren Sie die komprimierte Größe zu komprimieren, dann versuchen die Archivierung alle zwei ROMs zusammen und sehen, wie viel die resultierende Größe von ihren individuellen Druckgrößen unterscheidet. Wenn die kombinierte Größe gleich der Summe der einzelnen Größen ist, sind sie 0% ähnlich, und wenn die Größe der gleiche wie einer von ihnen (der größte), sie sind identisch.

Nun, dies ist eine große Anzahl von Druckversuche erforderlich, so habe ich ein paar Optimierungen bisher (und würde gerne mehr herauszufinden):

Priorisieren Vergleiche auf, wie ähnlich sich die Druckgrößen sind. Wenn ROM A eine komprimierte Größe von 10 MB hat und ROM B eine komprimierte Größe von 2 MB hat, ist es unmöglich, dass sie mehr als 20% ähnlich zu sein, so dass der Vergleich sich das wirkliche Ergebnis zu erhalten, bis später verlassen werden. Das Ausführen des gleichen Kompressionsalgorithmus auf hoch ähnliche Dateien neigt in ähnlicher Größe Ergebnisse zur Folge haben, so dass diese findet viele der sehr schnell Klone.
In Kombination mit dem oben genannten, hält die obere und untere „Grenze“ auf der mögliche Ähnlichkeit zwischen einem beliebigen Paar von ROMs. Dies ermöglicht eine weitere Priorisierung. Wenn ROMs A und B 95% ähnlich sind, und ROMs B und C sind nur 2% ähnlich, dann wissen Sie bereits, dass A und C zwischen 0% und 7%. Dies ist zu niedrig ein Klon zu sein, so dass dieser Vergleich sicher verschoben werden kann oder sogar ganz ignoriert, es sei denn ich die genauen Ähnlichkeiten wirklich alles wissen wollen.

Ich denke, einige Techniken aus Daten-Kompression entlehnt hier interessant sein könnten:

Angenommen, Sie haben zwei Dateien, A und B.

Komprimieren jede Datei einzeln und fügen Sie die komprimierten Größen zusammen. Dann verketten die beiden Dateien in eine einzige, große Datei und komprimieren sie auch.

Der Unterschied in den Größen geben Ihnen eine grobe Schätzung, wie ähnlich die Dateien sind.

Ich schlage vor, dass Sie die Burrow Wheeler-Transformation (bzip2) versuchen, die Komprimierung zu tun. Die meisten anderen Komprimierungsalgorithmen nur eine begrenzte Geschichte haben. Der BWT-Algorithmus OTOH kann auf sehr große Datenmengen arbeiten. Der Algorithmus „sieht“ beiden Dateien zur gleichen Zeit und jede Ähnlichkeit in einem höheren Verdichtungsverhältnis führen wird.

XDelta ist ziemlich nützlich, um anständig binäre Diffs: http://xdelta.org

Sie können durch das Speichern etwas wie Hashbäume . Es ist nur für jeden ROM zu speichern, ein solcher Satz von Hashes benötigt wird, und den erforderlichen Speicherplatz ist nur proportional zu (aber wesentlich geringer als) die Größe des ROM, konstante Blockgröße annimmt. Die gewählte Blockgröße muss eine ausreichende Granularität geben, um Genauigkeit zu gewährleisten, zum Beispiel: für eine Mindestgröße von 128MiB, Genauigkeitsbeschränkung von 1% und Tiger-128 Hash (ähnlich dem, was sie verwenden, um Dateien über Directconnect übertragen zu überprüfen), eine Blockgröße von 1MiB tut gut und man kann in 128 * 128/8 = 2048 alle Prüfsummen Bytes! Damit es für 10.000 ROMs würde nur etwa 20MiB Platz benötigen. Darüber hinaus können Sie eine weniger sicher, aber schneller und / oder kleinere Hash wählen. Hinzufügen / ein neues ROM für Ähnlichkeit Kontrolle mit sich bringen würde so etwas wie:

Teilen Sie die neue ROM in Blöcke und Hash jedem von ihnen.
Für jedes ROM bereits in der Datenbank, vergleichen (siehe unten) seine Hashes mit der neuen ROM-Hashes.

Die Vergleichsfunktion für Ähnlichkeit überprüfen sollte. Aber es sollte jeden Hash als unteilbaren Wert behandeln, das heißt nicht die Mühe, eine logisch signifikanten Unterschied Funktion zwischen zwei Hashes zu finden versuchen. Solange die Blockgröße ist niedrig genug und Hash-Kollisionen sind selten genug, Genauigkeit durch eine einfache garantiert ist-gleich-Vergleich.

Wie Sie sehen, das Problem auf eine einfachere leistungsmäßig reduziert wird. Viele kleineren Datensätze für Ähnlichkeitsprüfung

Zwei Gedanken:

Betrachten Sie die Datei als Datenflußgraphen Organisation und einige Kanonisierung an diesem represention tun. Da Sie den Befehlssatz kennen, kann dies möglich sein, vielleicht auch nur einen Disassembler Umreifung und einige Textverarbeitung zu tun.
Ein trainierbar Klassifikator wie CRM114 eine kompakte Darstellung nützlich sein könnte für das Geben, das Sie einige gibt Idee, ob Binärdateien haben viel gemeinsam.

Wie Waylon Flinn sagte, können Sie eine binäre Delta Algorithmus benötigen. Der rsync Algorithmus ist ein guter. Es ist schnell und zuverlässig. Siehe auch die Dienstprogramm Dokumentation rel="nofollow.

Die Schwierigkeit dabei ist, dass, da Sie mit ausführbarem Code handeln, einfache Änderungen über das gesamte ROM ausbreiten können. Die Adressen und Offsets für alle Werte können mit dem Zusatz einer einzelnen Variablen ändern oder No-op-Befehl. Das wird wertlos macht sogar basierten Block Hashing.

Eine schnelle und unsaubere Lösung wäre, eine Lösung zerhacken mit difflib (oder das Äquivalent w / Ihre Lieblingssprache), da es bekommt man einen gleitenden Vergleich, der mit Daten Hinzufügen oder Entfernen umgehen können. Spaltet das ROM in ausführbare Datei und Datenabschnitte (wenn möglich). Der Datenteil direkt verglichen werden kann und ein Ähnlichkeitsverhältnis berechnet, wenn Sie‘ ll immer noch Probleme w / Adressen oder Offsets haben.

Der ausführbare Abschnitt ist interessanter. Informieren Sie sich über die asm-Format der Maschine, nehmen Sie die ausführbare Datei und spaltet es in eine Sequenz von Opcodes. Lassen Sie den Opcode und Teile registrieren, sondern maskieren die „Nutzlast“ / „sofort“ Teile (wo es lädt die variablen Adressen). Hand, um die resultierenden Daten zu dem Ähnlichkeitsverhältnis Rechner zu.

Der unglückliche Teil ist, dass dies immer noch ein O (n ^ 2) Betrieb auf der Anzahl der ROMs Sie verfolgen, aber das kann mit (inkremental) clustering oder einem frequenzbasierten Vergleich zu reduzieren, um die Menge der Vergleiche verringert werden benötigt werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow