Programmatischen Ansatz in Java für Dateivergleich

Question

Was ist der beste Ansatz wäre, zwei hexadezimalen Dateisignaturen gegeneinander um Ähnlichkeiten zu vergleichen.

Genauer gesagt, was würde ich tun möchte, ist die hexadezimale Darstellung einer Exe-Datei zu nehmen und vergleichen Sie sie gegen eine Reihe von Virensignaturen. Für diesen Ansatz plane ich die Datei (exe) hexadezimale Darstellung in einzelne Gruppen von N Zeichen zu brechen (dh. 10 hex Zeichen) und das gleiche zu tun mit der Virensignatur. Ich bin mit dem Ziel, eine Art von Heuristiken durchzuführen und daher statistisch zu prüfen, ob diese exe-Datei hat X% der Ähnlichkeit mit dem bekannten Virensignatur.

Die einfachste und wahrscheinlich sehr falsch, wie ich dachte, dies zu tun ist, zu vergleichen exe [n, n-1] gegen Virus [n, n-1], wobei jedes Element im Array ist ein Unterfeld, und daher exe1 [0,9] gegen virus1 [0,9]. Jede Teilmenge wird statistisch bewertet werden.

Wie Sie dort erkennen kann eine massive Anzahl von Vergleichen wäre und daher sehr sehr langsam. Also dachte ich, zu fragen, ob euch ein besserer Ansatz denken kann ein solcher Vergleich zu tun, zum Beispiel unterschiedliche Datenstrukturen Umsetzung zusammen.

Diese für ein Projekt am ist für meinen BSc tun, wo ich versuche, einen Algorithmus zu entwickeln, polymorphen Malware zu erkennen, dies ist nur ein Teil des gesamten Systems, wo die anderen auf genetische Algorithmen basieren die statischen zu entwickeln Virensignatur. Jede Beratung, Kommentare oder allgemeine Informationen wie Ressourcen sind sehr willkommen.

---

Definition : Polymorphe Malware (Viren, Würmer, ...) unterhält die gleiche Funktionalität und Nutzlast als "Original" -Version, während scheinbar unterschiedliche Strukturen (Varianten). Sie erreichen, dass durch Code-Verschleierung und damit ihre Hex-Signatur zu ändern. Einige der Techniken für Polymorphismus verwendet werden; Formatänderung (insert remove Rohlingen), variable Umbenennungs, statement Umordnung, Junk-Code hinaus Anweisung Ersatz (x = 1 Änderungen x = y / 5 wobei Y 5 =), Austausch von Steueranweisungen. So ähnlich wie die Grippe-Virus mutiert und deshalb Impfung ist nicht wirksam, polymorpher Malware mutiert zu vermeiden Erkennung.

---

Update: Nach dem rät ihr haben mich in Bezug auf was zu tun ist zu lesen; Ich tat das, aber es mich etwas verwirrt mehr. Ich fand einige Entfernung Algorithmen, die für mein Problem anwenden kann, wie zum Beispiel;

• Längste gemeinsame Teilfolge
• Levenshtein Algorithmus
• Needleman-Wunsch-Algorithmus
• Smith-Waterman Algorithmus
• Boyer Moore-Algorithmus
• Aho Corasick Algorithmus

Aber jetzt weiß ich nicht, welche zu verwenden, sie scheinen alles, was er elbe auf verschiedene Weise zu tun. Ich werde auch weiterhin Forschung tun, so dass ich jeden besser zu verstehen; aber in der Zwischenzeit könnten Sie geben Sie mir Ihre Meinung zu which might be more suitable so, dass ich ihm Priorität bei meinen Recherchen geben kann und es zu studieren tiefer.

---

Update 2: Ich landete eine Verschmelzung der LCSubsequence up verwenden, LCSubstring und Levenshtein Entfernung. Vielen Dank für die Anregungen.

Es ist eine Kopie des fertigen Papiers auf GitHub

Answer 1

Für Algorithmen wie diese ich Ihnen vorschlagen, schauen in den Bereich der Bioinformatik. Es gibt ein ähnliches Problem Einstellung gibt, dass Sie große Dateien (Genomsequenzen), in der Sie suchen bestimmte Signaturen (Gene, spezielle bekannte kurze Basensequenzen, etc.).

Auch für polymorphe Malware bedenkt, soll dieser Sektor bietet Ihnen viel, weil in der Biologie es ähnlich schwierig scheint genaue Treffer zu erhalten. (Leider bin ich nicht bekannt, entsprechende approximative Suche / Matching-Algorithmen Sie zu verweisen.)

Ein Beispiel aus dieser Richtung etwas wie das Aho Corasick Algorithmus, um für mehr Malware-Signaturen zur gleichen Zeit zu suchen.

In ähnlicher Weise Algorithmen wie der Boyer Moore Algorithmus Geben Sie fantastische Suche Runtimes vor allem für längere Sequenzen ( durchschnittlicher Fall von O (N / M) für einen Text der Größe N, in dem Sie nach einem Muster der Größe M aussehen, also sublinear suchen mal).

Answer 2

Eine Reihe von Papieren wurde auf der Suche in der Nähe von doppelten Dokumenten in einem großen Korpus von Dokumenten im Zusammenhang mit der websearch veröffentlicht. Ich glaube, Sie werden feststellen, sie nützlich. Siehe zum Beispiel diese Präsentation .

Answer 3

Es hat sich in letzter Zeit eine ernsthafte Menge an Forschung, die Erkennung doppelter Fehlerberichte in Bug-Repositories zu automatisieren. Dies ist im Wesentlichen das gleiche Problem Sie konfrontiert sind. Der Unterschied besteht darin, dass Sie binäre Daten verwenden. Sie sind ähnliche Probleme, weil Sie für Strings suchen wird, die das gleiche Grundmuster haben, obwohl die Muster einige geringfügige Unterschiede aufweisen. Ein straight-up Entfernung Algorithmus wahrscheinlich werden Sie nicht dienen auch hier.

Dieses Papier gibt einen guten Überblick über das Problem sowie einige seiner Zitate nähert sich die versucht worden sind.

ftp://ftp.computer.org/ Presse / outgoing / Verfahren / Patrick / apsec10 / data / 4266a366.pdf

Answer 4

Als jemand hat darauf hingewiesen, Ähnlichkeit mit bekannten String und Bioinformatik Problem helfen könnte. Längste gemeinsame Teilkette ist sehr spröde, was bedeutet, dass eine Differenz die Länge einer solchen Zeichenfolge halbieren kann. Sie müssen eine Form von String-Ausrichtung, aber effizienter als Smith-Waterman. Ich würde versuchen, und Blick auf Programme wie BLAST, BLAT oder MUMMER3 zu sehen, ob sie Ihren Bedürfnissen passen. Beachten Sie, dass die Standardparameter für diese Programme basieren auf einer Biologie-Anwendung (wie viel eine Insertion zu bestrafen oder eine Substitution zum Beispiel), so dass Sie wahrscheinlich bei Wieder Schätzen von Parametern auf der Grundlage Ihrer Anwendungsdomäne aussehen sollten, möglicherweise auf der Grundlage eines Trainingsset. Dies ist ein bekanntes Problem, denn auch in der Biologie unterschiedliche Anwendungen unterschiedliche Parameter erfordern (basierend zum Beispiel auf dem evolutionären Abstand zweier Genome vergleichen). Es ist auch möglich, aber, dass auch bei Ausfall einer dieser Algorithmen könnten brauchbare Ergebnisse liefern. Das Beste von allem wäre ein generatives Modell zu haben, wie Viren ändern und das könnte führt Sie in einer optimalen Wahl für einen Abstand und Vergleichsalgorithmus.