Wie findet man wiederkehrende Muster auf einem Hexdump?

Question

Ich muss wiederkehrende Muster von einem Hexdump-Ausgang finden. Jede Zeile in meiner Ausgabedatei ist so etwas wie:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 

Wo 00 ein Byte in hexadezimal ist.

Die Muster haben keine feste Länge, aber sie liegen immer in einer Linie.

Ich habe eine Idee, wie man das macht, aber ich würde gerne wissen, was die effizienteste Methode Ihrer Meinung nach wäre, als ob es eine Art von bekanntem Algorhitmus gibt, dessen ich mir nicht bewusst bin.

Auch ich möchte das in Python kodieren.

Jeder Vorschlag ist grealty geschätzt :)

Dank

EDIT: Ich brauche Partitions-Boot-Sektoren in einem Plattenabbild zu finden. Das Problem ist, dass das Dateisystem ungewöhnlich ist, deshalb muss ich den Hexdump scannen, um Muster zu finden, die häufig verwendet werden, um den Forschungsbereich einzuschränken.

Zum Beispiel ich suche Byte-Muster wie:

00 56 f0 43 d0 

Answer 1

Es ist nicht ersichtlich, ob den Teil wissen, die Sie suchen möchten, oder ob Sie zunächst eine Reihe von Abfrage-Strings entdecken . Ich denke, dass Entdeckung gefunden werden kann, indem häufig vorkommende N-Gramme gefunden werden. Wenn Sie eine Gruppe von Abfrageteilstrings haben, können Sie fortfahren, wo sie sind und wie weit sie voneinander entfernt sind (z. B. wenn ein Teilstring alle 1024 Bytes auftritt, was eine Blockgröße sein kann).

Schritt 1: Lesen Sie Ihre Hexdump-Datei und konvertieren Sie sie zurück in eine einzige Zeichenfolge. Ich werde die Details dir überlassen.

Schritt 2: für jeden interessanten Wert von n (etwa 3, 4, 5 (wie Ihr Beispiel), 6, usw.) verwenden Sie diese Funktion:

from collections import Counter # needs 2.7 
from operator import itemgetter 
def get_ngrams(strg, n, top=10, min_count=2): 
    counter = Counter() 
    for i in xrange(len(strg) - n + 1): 
     gram = strg[i:i+n] 
     counter[gram] += 1 
    sort_these = [(gram, count) for gram, count in counter.iteritems() if count >= min_count] 
    best = sorted(sort_these, key=itemgetter(1), reverse=True)[:top] 
    return best 

Das gibt Ihnen den häufigsten auftretenden Teil .

Schritt 3: wo diese Strings auftreten:

def multifind(strg, gram): 
    positions = [] 
    end = len(strg) 
    pos = 0 
    while pos < end: 
     pos = strg.find(gram, pos) 
     if pos == -1: 
      break 
     positions.append(pos) 
     pos += 1 
    return positions 

Schritt 4: wie weit auseinander diese Vorkommen sind:

deltas = [b - a for a, b in zip(positions, positions[1:])]