mikrocontroller.net

Forum: PC-Programmierung Programm um Binärdateien auf gleiche Muster zu vergleichen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
Autor: Thomas W. (thomas_v2)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich würde gerne in zwei Binärdateien Muster-Übereinstimmungen von 
bestimmter Mindest-Länge feststellen. Die Dateien sind ausführbare 
Dateien, und es geht mir darum festzustellen ob es Funktionen oder 
andere Daten gibt die identisch sind.

Also es läuft darauf hinaus, ein Byte-Stream von z.B. 20 oder mehr 
aufeinander folgende Bytes aus Datei a beliebiger Stelle in Datei b zu 
finden und mir alle Übereinstimmungen anzuzeigen.

Gibt es da etwas fertiges in der Richtung (Linux oder Windows)?

Autor: A. S. (rava)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
schau dir mal die matched filter an:
https://en.wikipedia.org/wiki/Matched_filter

wenn du mit dem umgekehrten Signal faltest, kannst du mehrere Matches an 
verschiedenen Stellen finden.

Sollte nicht weiter schwer zu programmieren sein.
Falls Multiplikation zu lange dauert, kannst du auch einfach mit if 
vergleichen.

edit: ach du möchtest die Datenströme korrelieren, das heißt, du kennst 
das Suchsignal nicht?


Wie machen das denn diff-tools?

: Bearbeitet durch User
Autor: Thomas W. (thomas_v2)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. S. schrieb:
> edit: ach du möchtest die Datenströme korrelieren, das heißt, du kennst
> das Suchsignal nicht?

Genau das. Mit diff habe ich bisher nichts sinnvolles herausbekommen.

Einfaches Beispiel mit Texten:

Datei-A:
Hallo
dieses
ist
ein
Test

Datei-B:
Hallo
ein
ist
Test
dieses

Dann würde ich gerne sehen, dass "dieses" aus Datei A in Datei B an der 
Stelle steht, usw. Aber mit Binärdaten und nicht mit Texten.

Autor: nuJa (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ganz Trival habe ich das mal 1988 wegen "Blackjack, 1704, Herbst(laub), 
Cascade A-Virus" gemacht. Virus-Signatur Identifiziert, Stream byteweise 
geprüft. Wenn gefunden, korrigieren, Int-Vektoren bereinigen und die 
ursprüngliche *.com-Datei wiederherstellen ( war noch MS-DOS...). War 
wohl damals eins der ersten Virenreparatur-Programme ( :-))). Heute kann 
man es so machen, aber das ist mittlerweile viel smarter zu lösen. 
Damals hat es mich drei Tage gekostet. Heute ... ?? Weiss  nicht, 
zwei,drei Stunden???
Hat mir aber sehr viel über das Verständnis von Suchalgorithmen 
gebracht.
Kurz gesagt: Mach es selbst! Dann verstehst du auch besser was du 
willst!

cu

Autor: Eiei Ei (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Thomas W. schrieb:
> A. S. schrieb:
>> edit: ach du möchtest die Datenströme korrelieren, das heißt, du kennst
>> das Suchsignal nicht?
>
> Genau das. Mit diff habe ich bisher nichts sinnvolles herausbekommen.
>
> Einfaches Beispiel mit Texten:
>
> Datei-A:
> Hallo
> dieses
> ist
> ein
> Test
>
> Datei-B:
> Hallo
> ein
> ist
> Test
> dieses
>
> Dann würde ich gerne sehen, dass "dieses" aus Datei A in Datei B an der
> Stelle steht, usw. Aber mit Binärdaten und nicht mit Texten.

Diff: Indirekt, Ausgaben eines hexeditors vergleichen.

diff <(xxd 1.bin) <(xxd 2.bin)

anschaulicher:

diff [-y] <(xxd 1.bin) <(xxd 2.bin) [| colordiff]

Autor: A. S. (rava)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
naja ein Diff-tool findet sicherlich nicht die perfekte Lösung, aber man 
kann sich von der implementierung inspirieren lassen.


Wenn du das vollständige Ergebnis suchst, ist das sicher aufwändiger als 
ein diff-tool:
    * input: strings A und B, mit A < B
    * A schrittweise in immer kleinere substrings zerlegen
    * jeden Substring in B suchen
    * gefundene Matches aus der Suche ausschließen

Das Zerlegen in Substrings geschieht mit Überlappung
    for l in range(len(A)):
        substrings = [A[i:(len(A) - l + i) for i in range(l + 1)]

Die Komplexität ist damit len(A)^2 * len(B)

sollte nur für kleine Dateien machbar sein (< 1kB).

Ansonsten kann man natürlich ohne Überlappung zerteilen und im Anschluss 
prüfen, ob die matches noch größer sind als identifiziert.

: Bearbeitet durch User
Autor: imonbln (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ist vielleicht bindiff das Werkzeug das du suchst?

https://www.zynamics.com/bindiff.html

Autor: Thomas W. (thomas_v2)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielen Dank schon mal für die Informationen.
Ich sehe mir bindiff mal an ob es das tut was ich möchte. Andernfalls 
bleibt wohl wirklich nur selber schreiben.

Autor: A. S. (rava)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
kurze Frage: diff-tools gehen ja gerne der von vorne nach hinten durch 
die Dateien. Meint ihr, dass das in diesem Fall sinnvoll ist? Immerhin 
können subfunktionen ja irgendwo in der Datei stehen, da wild hin und 
herspringen kein problem ist im Binärcode...

: Bearbeitet durch User
Autor: Peter M. (r2d3)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo A. S.,

A. S. schrieb:
> kurze Frage: diff-tools gehen ja gerne der von vorne nach hinten durch
> die Dateien. Meint ihr, dass das in diesem Fall sinnvoll ist? Immerhin
> können subfunktionen ja irgendwo in der Datei stehen, da wild hin und
> herspringen kein problem ist im Binärcode...

gibt es irgendein Argument, die zu durchsuchende Datei bei der Suche 
nicht von vorne nach hinten zu durchlaufen?

Autor: A. S. (rava)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ok, ich hab's mir zu einfach gemacht, das zu erklären.

> Datei-A:
> Hallo
> dieses
> ist
> ein
> Test

> Datei-B:
> Hallo
> ein
> ist
> Test
> dieses


ein normales Diff tool würde (vielleicht) "Hallo", "ist" und "Test" 
finden. Aber nicht "dieses" und "ein", da hier die Auftretensreihenfolge 
nicht zum Rest passt.

Aber wenn jetzt jedes Wort ein subcall in Binär ist, hat der TO 
vermutlich schon interesse daran, alle matches zu finden, denn die 
Reihenfolge ist ja aufgrund von jumps beliebig.

Beitrag #5826825 wurde vom Autor gelöscht.
Autor: A. S. (rava)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Ach egal, das Problem hat mich interessiert. Hier mein Ansatz:

Die Komplexität ist jetzt len(A) * (len(A) + len(B), wobei A die kürzere 
Datei ist.

Das Skript findet alle matches mit folgender Priorisierung:
* lange Sequenzen vor kurzen Sequenzen
* frühes Auftreten in Datei A wird bevorzugt


für
file_A = "Hallo. dieses ist ein Test"
file_B = "Hallo ein ist Test dieses... Hallo"
liefert es
Done. found 7 matches...
-> len 7 - file_A locations: [6] | file_B locations: [18]
' dieses'
-> len 5 - file_A locations: [0] | file_B locations: [0, 29]
'Hallo'
-> len 5 - file_A locations: [13] | file_B locations: [9]
' ist '
-> len 4 - file_A locations: [22] | file_B locations: [14]
'Test'
-> len 3 - file_A locations: [18] | file_B locations: [6]
'ein'
-> len 1 - file_A locations: [5] | file_B locations: [25, 26, 27]
'.'
-> len 1 - file_A locations: [21] | file_B locations: [5, 28]
' '



Ein anderes Beispiel kommt von hier: 
https://stackoverflow.com/questions/32296937/compare-text-and-highlight-difference
file_A = "ThisisasystemgeneratedmentanddoesnotrequiresignatureAnyunauthorizedusedisclosuredisseminationoringofthisdocumentisstrictlyprohibitedandmaybeunlawful"
file_B = "Thisisasystemgenerateddocumentanddoesnotrequiresignatureunauthorizedusedisclosuredisseminationorcopyingofthisdocumentisstrictlyprohibitedandmaybeunful"
liefert es
Done. found 6 matches...
-> len 47 - file_A locations: [95] | file_B locations: [100]
'ingofthisdocumentisstrictlyprohibitedandmaybeun'
-> len 40 - file_A locations: [55] | file_B locations: [56]
'unauthorizedusedisclosuredisseminationor'
-> len 30 - file_A locations: [22] | file_B locations: [26]
'mentanddoesnotrequiresignature'
-> len 22 - file_A locations: [0] | file_B locations: [0]
'Thisisasystemgenerated'
-> len 3 - file_A locations: [145] | file_B locations: [147]
'ful'
-> len 1 - file_A locations: [54] | file_B locations: [99]
'y'

Autor: Egon D. (egon_d)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Thomas W. schrieb:

> Also es läuft darauf hinaus, ein Byte-Stream von z.B.
> 20 oder mehr aufeinander folgende Bytes aus Datei a
> beliebiger Stelle in Datei b zu finden und mir alle
> Übereinstimmungen anzuzeigen.

Das ist ungefähr das, was die Burrows-Wheeler-
Transformation macht:

https://de.wikipedia.org/wiki/Burrows-Wheeler-Transformation

Autor: Weingut P. (weinbauer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hmm ... warum nicht anders rum, wenn n ausführbares Programm in ne 
Subroutine springt wird es erst mal den Program Counter auf den Stack 
werfen, warum nicht nach der Aktion suchen, dann hast Du die 
Sprungadressen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.