Programm um Binärdateien auf gleiche Muster zu vergleichen

[Thomas W. (thomas_v2)]

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)?

[A. S. (rava)]

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?

[Thomas W. (thomas_v2)]

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.

[nuJa (Gast)]

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

[Eiei Ei (Gast)]

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]

[A. S. (rava)]

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.

[imonbln (Gast)]

ist vielleicht bindiff das Werkzeug das du suchst?

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

[Thomas W. (thomas_v2)]

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.

[A. S. (rava)]

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...

[Peter M. (r2d3)]

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?

[A. S. (rava)]

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.

[A. S. (rava)]

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'

[Egon D. (Gast)]

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

[Weingut P. (weinbauer)]

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.