How to find recurring patterns on a hexdump?
Question: I need to find recurring patterns from an hexdump output. Every line in my
output file is something like:

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

Where `00` is a byte in hexadecimal.

The patterns aren't of fixed length but they always lie in one line.

I have an idea on how to do this but I'd like to know what would be the most
efficent method in your opinion, like if there is some sort of known algorhitm
I am unaware of.

Also I'd like to code this in Python.

Any suggestion is grealty appreciated :)

Thanks

**EDIT:** I need to find partition boot sectors in a disk dump. The problem is
that the filesystem is uncommon so I need to scan the hexdump to find pattern
frequently used in order to restrict the area of research.

For example I am looking for byte-patterns like:

    
    
    00 56 f0 43 d0 
    


Answer: It is not apparent whether you know the substrings that you want to search
for, or whether you need to discover a set of query substrings first. I think
that discovery can be achieved by finding frequently occurring n-grams. One
you have your set of query substrings, you can proceed to where they are, and
how far apart they are (e.g. if some substring occurs every 1024 bytes, that
may be a block size).

Step 1: read your hexdump file and convert it back to a single string. I'll
leave the details up to you.

Step 2: for each interesting value of n (say 3, 4, 5 (like your example), 6,
etc) use this function:

    
    
    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
    

That will give you the most frequent occurring substrings.

Step 3: where those strings occur:

    
    
    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
    

Step 4: how far apart those occurrences are:

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

