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)?
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
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.
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
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]
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.
:
Bearbeitet durch User
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...
:
Bearbeitet durch User
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.
Beitrag #5826825 wurde vom Autor gelöscht.
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' |
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
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.