Programm um Binärdateien auf gleiche Muster zu vergleichen

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?

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.

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:

1

    * input: strings A und B, mit A < B

2

    * A schrittweise in immer kleinere substrings zerlegen

3

    * jeden Substring in B suchen

4

    * gefundene Matches aus der Suche ausschließen

Das Zerlegen in Substrings geschieht mit Überlappung

1

    for l in range(len(A)):

2

        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.

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.

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

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?

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.

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

1

file_A = "Hallo. dieses ist ein Test"

2

file_B = "Hallo ein ist Test dieses... Hallo"

liefert es

1

Done. found 7 matches...

2

-> len 7 - file_A locations: [6] | file_B locations: [18]

3

' dieses'

4

-> len 5 - file_A locations: [0] | file_B locations: [0, 29]

5

'Hallo'

6

-> len 5 - file_A locations: [13] | file_B locations: [9]

7

' ist '

8

-> len 4 - file_A locations: [22] | file_B locations: [14]

9

'Test'

10

-> len 3 - file_A locations: [18] | file_B locations: [6]

11

'ein'

12

-> len 1 - file_A locations: [5] | file_B locations: [25, 26, 27]

13

'.'

14

-> len 1 - file_A locations: [21] | file_B locations: [5, 28]

15

' '

Ein anderes Beispiel kommt von hier: 
https://stackoverflow.com/questions/32296937/compare-text-and-highlight-difference

1

file_A = "ThisisasystemgeneratedmentanddoesnotrequiresignatureAnyunauthorizedusedisclosuredisseminationoringofthisdocumentisstrictlyprohibitedandmaybeunlawful"

2

file_B = "Thisisasystemgenerateddocumentanddoesnotrequiresignatureunauthorizedusedisclosuredisseminationorcopyingofthisdocumentisstrictlyprohibitedandmaybeunful"

liefert es

1

Done. found 6 matches...

2

-> len 47 - file_A locations: [95] | file_B locations: [100]

3

'ingofthisdocumentisstrictlyprohibitedandmaybeun'

4

-> len 40 - file_A locations: [55] | file_B locations: [56]

5

'unauthorizedusedisclosuredisseminationor'

6

-> len 30 - file_A locations: [22] | file_B locations: [26]

7

'mentanddoesnotrequiresignature'

8

-> len 22 - file_A locations: [0] | file_B locations: [0]

9

'Thisisasystemgenerated'

10

-> len 3 - file_A locations: [145] | file_B locations: [147]

11

'ful'

12

-> len 1 - file_A locations: [54] | file_B locations: [99]

13

'y'

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.